Quantum circuit lower bounds in the magic hierarchy

• URL: http://arxiv.org/abs/2504.19966v1
• Date: Mon, 28 Apr 2025 16:38:20 GMT
• Title: Quantum circuit lower bounds in the magic hierarchy
• Authors: Natalie Parham,
• Abstract summary: We introduce the magic hierarchy, a quantum circuit model that alternates between arbitrary-sized Clifford circuits and constant-depth circuits with two-qubit gates.<n>We show that certain explicit quantum states cannot be approximately prepared by circuits consisting of a Clifford circuit followed by $textsfQNC0$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce the magic hierarchy, a quantum circuit model that alternates between arbitrary-sized Clifford circuits and constant-depth circuits with two-qubit gates ($\textsf{QNC}^0$). This model unifies existing circuit models, such as $\textsf{QAC}^0_f$ and models with adaptive intermediate measurements. Despite its generality, we are able to prove nontrivial lower bounds. We prove new lower bounds in the first level of the hierarchy, showing that certain explicit quantum states cannot be approximately prepared by circuits consisting of a Clifford circuit followed by $\textsf{QNC}^0$. These states include ground states of some topologically ordered Hamiltonians and nonstabilizer quantum codes. Our techniques exploit the rigid structure of stabilizer codes and introduce an infectiousness property: if even a single state in a high distance code can be approximately prepared by one of these circuits, then the entire subspace must lie close to a perturbed stabilizer code. We also show that proving state preparation lower bounds beyond a certain level of the hierarchy would imply classical circuit lower bounds beyond the reach of current techniques in complexity theory. More broadly, our techniques go beyond lightcone-based methods and highlight how the magic hierarchy provides a natural framework for connecting circuit complexity, condensed matter, and Hamiltonian complexity.

Related papers

• A Localized Reality Appears To Underpin Quantum Circuits [0.0]
  We present evidence for a localized account of any quantum circuit's behavior. Even if the state is massively entangled, the weak values are found to evolve only when they pass through a local circuit element.
  arXiv  Detail & Related papers  (2024-12-06T22:35:45Z)
• Learning State Preparation Circuits for Quantum Phases of Matter [0.294944680995069]
  We introduce a flexible and efficient framework for obtaining a state preparation circuit for a large class of many-body ground states. We use a variant of the quantum Markov chain condition that remains robust against constant-depth circuits.
  arXiv  Detail & Related papers  (2024-10-31T01:10:46Z)
• Geometric Quantum Machine Learning with Horizontal Quantum Gates [41.912613724593875]
  We propose an alternative paradigm for the symmetry-informed construction of variational quantum circuits. We achieve this by introducing horizontal quantum gates, which only transform the state with respect to the directions to those of the symmetry. For a particular subclass of horizontal gates based on symmetric spaces, we can obtain efficient circuit decompositions for our gates through the KAK theorem.
  arXiv  Detail & Related papers  (2024-06-06T18:04:39Z)
• Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement [39.58317527488534]
  Quantum Circuits (PQCs) are still not fully understood outside the scope of their principal application.<n>We analyse the generation of random states in PQCs under restrictions on the qubits connectivities.<n>We place a connection between how steep is the increase on the uniformity of the distribution of the generated states and the generation of entanglement.
  arXiv  Detail & Related papers  (2024-05-03T17:32:55Z)
• Low-overhead non-Clifford fault-tolerant circuits for all non-chiral abelian topological phases [0.7873629568804646]
  We propose a family of explicit geometrically local circuits on a 2-dimensional planar grid of qudits.<n>These circuits are constructed from measuring 1-form symmetries in discrete fixed-point path integrals.<n>We prove fault tolerance under arbitrary local (including non-Pauli) noise for a very general class of topological circuits.
  arXiv  Detail & Related papers  (2024-03-18T18:00:00Z)
• Quantum information spreading in generalised dual-unitary circuits [44.99833362998488]
  We show that local operators spread at the speed of light as in dual-unitary circuits. We use these properties to find a closed-form expression for the entanglement membrane in these circuits.
  arXiv  Detail & Related papers  (2023-12-05T18:09:27Z)
• Circuit depth versus energy in topologically ordered systems [0.0]
  We prove a nontrivial circuit-depth lower bound for preparing a low-energy state of a locally interacting quantum many-body system in two dimensions.
  arXiv  Detail & Related papers  (2022-10-13T07:21:30Z)
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
  Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware. We present an algorithm that compresses the Trotter steps into a single block of quantum gates. This results in a fixed depth time evolution for certain classes of Hamiltonians.
  arXiv  Detail & Related papers  (2021-08-06T19:38:01Z)
• Building a fault-tolerant quantum computer using concatenated cat codes [44.03171880260564]
  We present a proposed fault-tolerant quantum computer based on cat codes with outer quantum error-correcting codes. We numerically simulate quantum error correction when the outer code is either a repetition code or a thin rectangular surface code. We find that with around 1,000 superconducting circuit components, one could construct a fault-tolerant quantum computer.
  arXiv  Detail & Related papers  (2020-12-07T23:22:40Z)
• Circuit lower bounds for low-energy states of quantum code Hamiltonians [17.209060627291315]
  We prove circuit lower bounds for all low-energy states of local Hamiltonians arising from quantum error-correcting codes. We show that low-depth states cannot accurately approximate the ground-energy even in physically relevant systems.
  arXiv  Detail & Related papers  (2020-11-03T22:36:22Z)
• Quantum anomalous Hall phase in synthetic bilayers via twistless twistronics [58.720142291102135]
  We propose quantum simulators of "twistronic-like" physics based on ultracold atoms and syntheticdimensions. We show that our system exhibits topologicalband structures under appropriate conditions.
  arXiv  Detail & Related papers  (2020-08-06T19:58:05Z)
• Hardware-Encoding Grid States in a Non-Reciprocal Superconducting Circuit [62.997667081978825]
  We present a circuit design composed of a non-reciprocal device and Josephson junctions whose ground space is doubly degenerate and the ground states are approximate codewords of the Gottesman-Kitaev-Preskill (GKP) code. We find that the circuit is naturally protected against the common noise channels in superconducting circuits, such as charge and flux noise, implying that it can be used for passive quantum error correction.
  arXiv  Detail & Related papers  (2020-02-18T16:45:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.