Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2509.17014

State complexity and phase identification in adaptive quantum circuits

Guoding Liu, J. Chen, Xiongfeng Ma

Published Sep 21, 2025• 0 citations
arXivHTMLPDF

Abstract

Adaptive quantum circuits, leveraging measurements and classical feedback, significantly expand the landscape of realizable quantum states compared to their non-adaptive counterparts, enabling the preparation of long-range entangled states and topological phases at constant depths. However, the ancilla overhead for preparing arbitrary states can be prohibitive, raising a fundamental question: which states can be efficiently realized with limited ancilla and low depth? Addressing this question requires a rigorous quantitative characterization of state complexity, or the minimum depth and ancillas, to realize a state in adaptive circuits. In this work, we tackle this problem by introducing two properties of quantum states: state weight and anti-shallowness, connected to the correlation range and correlation strength within a state, respectively. We prove that these quantities are bounded under limited circuit resources, thereby providing rigorous bounds on the approximate complexity of state preparation and gate implementation. Illustrative examples include the GHZ state, W state, QLDPC code states, and the Toffoli gate. Besides complexity, we show that states within the same quantum phase, defined by a set of quantum states connected with constant-depth circuits, must share the same scaling of weight or anti-shallowness. This establishes these quantities as indicators of quantum phases and their essential roles in many-body physics.

DOI
10.48550/arxiv.2509.17014

Related papers

Characterization of state complexity in adaptive quantum circuits

Guoding Liu, Junjie Chen, Xiongfeng Ma

Preparing long-range entangled states is critical for quantum information processing and many-body physics, but typically requires impractically deep circuits. Recent progress on adaptive circuits, which incorporate mid-circuit measurements and classical feedback, shows that adaptivity can greatly reduce depth and even prepare arbitrary states in constant depth. This advantage, however, comes with a trade-off between depth and ancillary qubits, motivating the study of adaptive state complexity: the minimal depth and number of ancillas needed to prepare a given state. In this work, we investigate adaptive state complexity for generic mixed states and general circuit architectures. Our approach analyzes the growth of correlation range in adaptive circuits and shows that insufficient depth or ancilla resources strictly limit the formation of long-range correlations. This yields rigorous bounds on approximate state and gate complexity given the correlation value. We demonstrate the generality and applicability of our approach with representative examples, including permutation-invariant states, Gibbs states of many-body Hamiltonians, and multi-qubit gates like the Toffoli gate.

npj Quantum Information•Aug 7, 2026•0 citations

Constant-Depth Preparation of Matrix Product States with Adaptive Quantum Circuits

Kevin C. Smith, Abid Khan, Bryan K. Clark +2 more

Adaptive quantum circuits, which combine local unitary gates, midcircuit measurements, and feedforward operations, have recently emerged as a promising avenue for efficient state preparation, particularly on near-term quantum devices limited to shallow-depth circuits. Matrix product states (MPS) comprise a significant class of many-body entangled states, efficiently describing the ground states of one-dimensional gapped local Hamiltonians and finding applications in a number of recent quantum algorithms. Recently, it has been shown that the Affleck-Kennedy-Lieb-Tasaki state—a paradigmatic example of an MPS—can be exactly prepared with an adaptive quantum circuit of constant depth, an impossible feat with local unitary gates alone due to its nonzero correlation length [Smith , PRX Quantum 4, 020315 (2023)]. In this work, we broaden the scope of this approach and demonstrate that a diverse class of MPS can be exactly prepared using constant-depth adaptive quantum circuits, outperforming theoretically optimal preparation with unitary circuits. We show that this class includes short- and long-ranged entangled MPS, symmetry-protected topological (SPT) and symmetry-broken states, MPS with finite Abelian, non-Abelian, and continuous symmetries, resource states for MBQC, and families of states with tunable correlation length. Moreover, we illustrate the utility of our framework for designing constant-depth sampling protocols, such as for random MPS or for generating MPS in a particular SPT phase. We present sufficient conditions for particular MPS to be preparable in constant time, with global on-site symmetry playing a pivotal role. Altogether, this work demonstrates the immense promise of adaptive quantum circuits for efficiently preparing many-body entangled states and provides explicit algorithms that outperform known protocols to prepare an essential class of states. Published by the American Physical Society 2024

arXiv:2404.16083•PRX Quantum•Sep 4, 2024•51 citations

Circuit complexity lower bounds for quantum spin glasses

Omar Al-Ghattas, David Gamarnik

A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum $p$-spin glasses, random Hamiltonians whose interactions act on $p$-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement. We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with $n$, we prove that, for all sufficiently large fixed $p$, any circuit preparing an $n$-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth $Ω_p(\log n)$. In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed $D$, a sufficiently large degree prefactor rules out depth-$D$ preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits. Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.

quant-pharXiv:2607.14384•Jul 17, 2026•0 citations

Experimental demonstration of the advantage of adaptive quantum circuits

Michael Foss‐Feig, Arkin Tikku, Tsung-Cheng Lu +16 more

Adaptive quantum circuits employ unitary gates assisted by mid-circuit measurement, classical computation on the measurement outcome, and the conditional application of future unitary gates based on the result of the classical computation. In this paper, we experimentally demonstrate that even a noisy adaptive quantum circuit of constant depth can achieve a task that is impossible for any purely unitary quantum circuit of identical depth: the preparation of long-range entangled topological states with high fidelity. We prepare a particular toric code ground state with fidelity of at least $76.9\pm 1.3\%$ using a constant depth ($d=4$) adaptive circuit, and rigorously show that no unitary circuit of the same depth and connectivity could prepare this state with fidelity greater than $50\%$.

arXiv:2302.03029•Feb 6, 2023•11 citations

Complexity Bounds for Quantum Computation

Steven Homer

This project focused on upper and lower bounds for quantum computability using constant depth quantum circuits, and on the complexity theory of such circuits. It established significant differences between resource bounded quantum and classical computation models, particularly emphasizing new examples of where quantum circuits are more powerful than their classical counterparts. A second focus and outgrowth of this work was the creation of efficient quantum algorithms for specific problems and central combinatorial functions. Recent finding include upper bounds for the computational power of constant depth circuits composed of single qubit and CNOT gates, and lower bounds for the computational power of constant depth circuits with single qubit, CNOT and fanout gates. These results represent the power and the limits of small, possibly realizable quantum circuits. Also examined were bounds on computations with additional storage qubits (ancillae), and natural simple functions (realized by small depth circuits) which require ancillae for their computation.

•Jun 22, 2007•0 citations

Learning and Generating Mixed States Prepared by Shallow Channel Circuits

Fangjun Hu, Christian Kokail, Milan Kornjača +5 more

Learning quantum states from measurement data is a central problem in quantum information and computational complexity. In this work, we study the problem of learning to generate mixed states on a finite-dimensional lattice. Motivated by recent developments in mixed state phases of matter, we focus on arbitrary states in the trivial phase. A state belongs to the trivial phase if there exists a shallow preparation channel circuit under which local reversibility is preserved throughout the preparation. We prove that any mixed state in this class can be efficiently learned from measurement access alone. Specifically, given copies of an unknown trivial phase mixed state, our algorithm outputs a shallow local channel circuit that approximately generates this state in trace distance. The sample complexity and runtime are polynomial (or quasi-polynomial) in the number of qubits, assuming constant (or polylogarithmic) circuit depth and gate locality. Importantly, the learner is not given the original preparation circuit and relies only on its existence. Our results provide a structural foundation for quantum generative models based on shallow channel circuits. In the classical limit, our framework also inspires an efficient algorithm for classical diffusion models using only a polynomial overhead of training and generation.

quant-pharXiv:2604.01197•Apr 2, 2026•0 citations
Adaptive quantum circuits, leveraging measurements and classical feedback, significantly expand the landscape of realizable quantum states compared to their non-adaptive counterparts, enabling the preparation of long-range entangled states and topological phases at constant depths. However, the ancilla overhead for preparing arbitrary states can be prohibitive, raising a fundamental question: which states can be efficiently realized with limited ancilla and low depth? Addressing this question requires a rigorous quantitative characterization of state complexity, or the minimum depth and ancillas, to realize a state in adaptive circuits. In this work, we tackle this problem by introducing two properties of quantum states: state weight and anti-shallowness, connected to the correlation range and correlation strength within a state, respectively. We prove that these quantities are bounded under limited circuit resources, thereby providing rigorous bounds on the approximate complexity of state preparation and gate implementation. Illustrative examples include the GHZ state, W state, QLDPC code states, and the Toffoli gate. Besides complexity, we show that states within the same quantum phase, defined by a set of quantum states connected with constant-depth circuits, must share the same scaling of weight or anti-shallowness. This establishes these quantities as indicators of quantum phases and their essential roles in many-body physics.
Preparing long-range entangled states is critical for quantum information processing and many-body physics, but typically requires impractically deep circuits. Recent progress on adaptive circuits, which incorporate mid-circuit measurements and classical feedback, shows that adaptivity can greatly reduce depth and even prepare arbitrary states in constant depth. This advantage, however, comes with a trade-off between depth and ancillary qubits, motivating the study of adaptive state complexity: the minimal depth and number of ancillas needed to prepare a given state. In this work, we investigate adaptive state complexity for generic mixed states and general circuit architectures. Our approach analyzes the growth of correlation range in adaptive circuits and shows that insufficient depth or ancilla resources strictly limit the formation of long-range correlations. This yields rigorous bounds on approximate state and gate complexity given the correlation value. We demonstrate the generality and applicability of our approach with representative examples, including permutation-invariant states, Gibbs states of many-body Hamiltonians, and multi-qubit gates like the Toffoli gate.
Adaptive quantum circuits, which combine local unitary gates, midcircuit measurements, and feedforward operations, have recently emerged as a promising avenue for efficient state preparation, particularly on near-term quantum devices limited to shallow-depth circuits. Matrix product states (MPS) comprise a significant class of many-body entangled states, efficiently describing the ground states of one-dimensional gapped local Hamiltonians and finding applications in a number of recent quantum algorithms. Recently, it has been shown that the Affleck-Kennedy-Lieb-Tasaki state—a paradigmatic example of an MPS—can be exactly prepared with an adaptive quantum circuit of constant depth, an impossible feat with local unitary gates alone due to its nonzero correlation length [Smith , PRX Quantum 4, 020315 (2023)]. In this work, we broaden the scope of this approach and demonstrate that a diverse class of MPS can be exactly prepared using constant-depth adaptive quantum circuits, outperforming theoretically optimal preparation with unitary circuits. We show that this class includes short- and long-ranged entangled MPS, symmetry-protected topological (SPT) and symmetry-broken states, MPS with finite Abelian, non-Abelian, and continuous symmetries, resource states for MBQC, and families of states with tunable correlation length. Moreover, we illustrate the utility of our framework for designing constant-depth sampling protocols, such as for random MPS or for generating MPS in a particular SPT phase. We present sufficient conditions for particular MPS to be preparable in constant time, with global on-site symmetry playing a pivotal role. Altogether, this work demonstrates the immense promise of adaptive quantum circuits for efficiently preparing many-body entangled states and provides explicit algorithms that outperform known protocols to prepare an essential class of states. Published by the American Physical Society 2024
A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum ppp-spin glasses, random Hamiltonians whose interactions act on ppp-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement. We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with nnn, we prove that, for all sufficiently large fixed ppp, any circuit preparing an nnn-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth Ωp(log⁡n)Ω_p(\log n)Ωp​(logn). In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed DDD, a sufficiently large degree prefactor rules out depth-DDD preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits. Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.
Adaptive quantum circuits employ unitary gates assisted by mid-circuit measurement, classical computation on the measurement outcome, and the conditional application of future unitary gates based on the result of the classical computation. In this paper, we experimentally demonstrate that even a noisy adaptive quantum circuit of constant depth can achieve a task that is impossible for any purely unitary quantum circuit of identical depth: the preparation of long-range entangled topological states with high fidelity. We prepare a particular toric code ground state with fidelity of at least 76.9±1.3%76.9\pm 1.3\%76.9±1.3% using a constant depth (d=4d=4d=4) adaptive circuit, and rigorously show that no unitary circuit of the same depth and connectivity could prepare this state with fidelity greater than 50%50\%50%.
This project focused on upper and lower bounds for quantum computability using constant depth quantum circuits, and on the complexity theory of such circuits. It established significant differences between resource bounded quantum and classical computation models, particularly emphasizing new examples of where quantum circuits are more powerful than their classical counterparts. A second focus and outgrowth of this work was the creation of efficient quantum algorithms for specific problems and central combinatorial functions. Recent finding include upper bounds for the computational power of constant depth circuits composed of single qubit and CNOT gates, and lower bounds for the computational power of constant depth circuits with single qubit, CNOT and fanout gates. These results represent the power and the limits of small, possibly realizable quantum circuits. Also examined were bounds on computations with additional storage qubits (ancillae), and natural simple functions (realized by small depth circuits) which require ancillae for their computation.
Learning quantum states from measurement data is a central problem in quantum information and computational complexity. In this work, we study the problem of learning to generate mixed states on a finite-dimensional lattice. Motivated by recent developments in mixed state phases of matter, we focus on arbitrary states in the trivial phase. A state belongs to the trivial phase if there exists a shallow preparation channel circuit under which local reversibility is preserved throughout the preparation. We prove that any mixed state in this class can be efficiently learned from measurement access alone. Specifically, given copies of an unknown trivial phase mixed state, our algorithm outputs a shallow local channel circuit that approximately generates this state in trace distance. The sample complexity and runtime are polynomial (or quasi-polynomial) in the number of qubits, assuming constant (or polylogarithmic) circuit depth and gate locality. Importantly, the learner is not given the original preparation circuit and relies only on its existence. Our results provide a structural foundation for quantum generative models based on shallow channel circuits. In the classical limit, our framework also inspires an efficient algorithm for classical diffusion models using only a polynomial overhead of training and generation.