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:2610.02166

Beyond Light Cones: State Preparation Complexity in Quantum Spin Glasses

Omar Al-Ghattas, David Gamarnik, Bobak T Kiani

quant-phcond-mat.dis-nncs.CCmath.PRSubmitted Oct 1, 2026• Announced Oct 2, 2026• 0 citations
v1 · Oct 1, 2026v2 · Nov 2, 2026
arXivHTMLPDF

Abstract

We introduce a method for studying state preparation complexity in dense quantum $p$-spin Hamiltonians on $n$ qubits, going beyond bounds based only on circuit lightcones. The key input is the class's effective profile complexity, which is derived from the metric entropy of its Pauli profiles. These profiles record expectations of all Pauli operators supported on exactly $p$ qubits. Classes with uniformly bounded quadratic effective profile complexity remain separated from the ground-state energy by a positive multiple of $\sqrt n$ for sufficiently large fixed $p$. At subquadratic effective profile complexity, the class cannot outperform a suitable benchmark class at leading order, with product states providing a universal benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem of Berta et al. (arXiv:1810.12197) with Gaussian process entropy bounds. Applying this framework, we show that attaining near-ground-state energy requires $Ω(n^2/\log n)$ one- and two-qubit gates, even with arbitrary discardable ancillas. We also obtain depth-width tradeoffs, entanglement-depth and matrix product state bond-dimension lower bounds, and obstructions for both orientations at every fixed level of Parham's magic hierarchy (arXiv:2504.19966), with total circuit width $O(n)$. In first-level reverse magic, a shallow circuit is followed by an unrestricted Clifford circuit. The latter can spread local observables across the system, preventing a direct application of small-lightcone bounds. For this first-level class, our bounds also allow arbitrarily many clean ancillas at fixed shallow-circuit depth. A sharper benchmark shows that Clifford+$T$ circuits with $o(n)$ $T$-gates have no leading-order energy advantage over product stabilizer states, even with unrestricted Clifford operations and arbitrary discardable ancillas.

Comments
86 pages

Related papers

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•3 citations

Time complexity in preparing metrologically useful quantum states

Carla M. Quispe Flores, Raphael Kaubruegger, Minh C. Tran +3 more

We investigate the fundamental time complexity, as constrained by Lieb-Robinson bounds, for preparing entangled states useful in quantum metrology. We relate the minimum time to the Quantum Fisher Information ($F_Q$) for a system of $N$ quantum spins on a $d$-dimensional lattice with $1/r^α$ interactions with $r$ being the distance between two interacting spins. We focus on states with $F_Q \sim N^{1+γ}$ where $γ\in (0,1]$, i.e., scaling from the standard quantum limit to the Heisenberg limit. For short-range interactions ($α> 2d+1$), we prove the minimum time $t$ scales as $t \gtrsim L^γ$, where $L \sim N^{1/d}$. For long-range interactions, we find a hierarchy of possible speedups: $t \gtrsim L^{γ(α-2d)}$ for $2d < α< 2d+1$, $t \gtrsim \log L$ for $(2-γ)d < α< 2d$, and $t$ may even vanish algebraically in $1/L$ for $α< (2-γ)d$. These bounds extend to the minimum circuit depth required for state preparation, assuming two-qubit gate speeds scale as $1/r^α$. We further show that these bounds are saturable, up to sub-polynomial corrections, for all $α$ at the Heisenberg limit ($γ=1$) and for $α> (2-γ)d$ when $γ<1$. Our results establish a benchmark for the time-optimality of protocols that prepare metrologically useful quantum states.

quant-pharXiv:2511.14855•Nov 20, 2025•3 citations

Low-depth quantum state preparation

Xiao‐Ming Zhang, Man‐Hong Yung, Xiao Yuan

A crucial subroutine in quantum computing is to load the classical data of $N$ complex numbers into the amplitude of a superposed $n=\ensuremath{\lceil}{log}_{2}N\ensuremath{\rceil}$-qubit state. It has been proven that any algorithm universally implementing this subroutine would need at least $O(N)$ constant weight operations. However, the proof assumes that only $n$ qubits are used, whereas the circuit depth could be reduced by extending the space and allowing ancillary qubits. Here we investigate this space-time tradeoff in quantum state preparation with classical data. We propose quantum algorithms with $O({n}^{2})$ circuit depth to encode any $N$ complex numbers using only single- and two-qubit gates, and local measurements with ancillary qubits. Different variances of the algorithm are proposed with different space and runtime. In particular, we present a scheme with $O({N}^{2})$ ancillary qubits, $O({n}^{2})$ circuit depth, and $O({n}^{2})$ average runtime, which exponentially improves the conventional bound. While the algorithm requires more ancillary qubits, it consists of quantum circuit blocks that only simultaneously act on a constant number of qubits, and at most $O(n)$ qubits are entangled. We also prove a fundamental lower bound $\mathrm{\ensuremath{\Omega}}(n)$ for the minimum circuit depth and runtime with an arbitrary number of ancillary qubits, aligning with our scheme with $O({n}^{2})$. The algorithms are expected to have wide applications in both near-term and universal quantum computing.

arXiv:2102.07533•Physical Review Research•Dec 21, 2021•85 citations

Resilience Beyond the Light Cone: Error-Detected Primitives for Practical Dynamic Circuits

Kevin C. Smith, Bibek Pokharel, Satvik Maurya +1 more

Dynamic circuits, which augment unitary operations with mid-circuit measurements and classical feedforward, can generate long-range entanglement in constant depth, enabling low-depth primitives ranging from nontrivial state preparation to many-qubit entangling gates. Escaping the light-cone constraints of unitary circuits, however, comes at a cost: these primitives typically require a number of mid-circuit measurements that scales with system size and that, together with feedforward latency, can introduce errors that degrade the long-range entanglement they rely on. Here, we alleviate this tension by showing that many such primitives, when cast into a common framework, admit an error-detection scheme that trades infidelity for postselection overhead with no additional ancillas. Our framework thus unifies and upgrades a broad class of primitives including fan-out gates, multi-qubit Pauli rotations, the preparation of W and higher-weight Dicke states, and certain non-normal matrix product states. We also introduce a reduced-depth, error-detected implementation of the Hadamard test, extending the use cases of dynamic circuits to a key algorithmic primitive. Finally, we establish the practical utility of our scheme through experiments on a superconducting quantum processor. We demonstrate the error-detected preparation of a long-range entangled Bell pair spanning a 100-qubit chain with fidelity $F=0.59\pm0.02$, surpassing the entanglement-certification threshold $F>0.5$ that the baseline dynamic-circuit implementation fails to reach ($0.39\pm0.01$). Separately, we demonstrate constant-depth preparation of W states of up to 20 qubits by consuming GHZ states of up to 40 qubits, finding absolute fidelity improvements of $ΔF\approx 0.2$ across the largest sizes studied. Altogether, these results bring low-depth dynamic-circuit primitives within practical reach on present-day hardware.

quant-pharXiv:2609.08925•Sep 9, 2026•0 citations

Utility-Scale Quantum State Preparation: Classical Training using Pauli Path Simulation

Cheng-Ju Lin, Hrant Gharibyan, Vincent Paul Su

We use Pauli Path simulation to variationally obtain parametrized circuits for preparing ground states of various quantum many-body Hamiltonians. These include the quantum Ising model in one dimension, in two dimensions on square and heavy-hex lattices, and the Kitaev honeycomb model, all at system sizes of one hundred qubits or more – sizes at which generic quantum circuits are beyond the reach of exact state-vector simulation – thereby reaching utility scale. We benchmark the Pauli Path simulation results against exact ground-state energies when available, and against density-matrix renormalization group calculations otherwise, finding strong agreement. To further assess the quality of the variational states, we evaluate the magnetization in the x and z directions for the quantum Ising models and compute the topological entanglement entropy for the Kitaev honeycomb model. Finally, we prepare approximate ground states of the Kitaev honeycomb model with 48 qubits, in both the gapped and gapless regimes, on Quantinuum's System Model H2 quantum computer using parametrized circuits obtained from Pauli Path simulation. We achieve a relative energy error of approximately 5 % without error mitigation and demonstrate the braiding of Abelian anyons on the quantum device beyond fixed-point models.

arXiv:2510.02428•Quantum•Mar 9, 2026•4 citations

A Single Fixed Shallow Circuit for Classical Shadows of Arbitrary n-Qubit States

Yu Wang, Xiuwu Zhu

Classical shadows extract quantum properties from reusable classical records, typically obtained through randomized measurement settings. Although individual settings may be shallow, switching among them introduces control, calibration, and reconfiguration costs beyond conventional metrics. Here we construct, for every $n$, a single fixed shallow quantum analyzer whose Born outcomes replace externally sampled settings as labels for reusable shadow snapshots. The analyzer combines a freshly prepared $n$-qubit fiducial register $A$ with parallel Bell readout of $A$ and the unknown system $S$, producing one $2n$-bit record per copy. The same circuit realizes a rank-one minimal informationally complete measurement: one fixed setting replaces the $3^n$ local-Pauli settings conventionally used for complete reconstruction while retaining the minimum $d^2$ outcomes with $d=2^n$. Its Pauli-diagonal frame admits an analytic inverse. For fixed Hermitian observables, the Haar-averaged conditional variance has a dimension-independent coefficient, whereas the state-uniform coefficient is dimension dependent. For $n\ge3$, worst-state Pauli variances remain bounded in the axial sector and scale as $Θ(d)$ in the mixed sector. Fiducial preparation before system contact uses $n-1$ arbitrary two-qubit gates, no work qubits beyond $A$, and logarithmic depth under all-to-all connectivity. The unknown system undergoes one parallel system-ancilla entangling layer followed by local Hadamards and readout. Measurement-assisted preparation achieves $O(1)$ adaptive quantum depth using $n+1$ extra qubits in the heralded route, or $O(n\log n)$ auxiliaries for deterministic completion. These tradeoffs show that part of the measurement-setting randomness and control complexity normally supplied shot by shot can instead be compiled into a fixed reusable analyzer.

quant-pharXiv:2609.07032•Sep 8, 2026•0 citations
We introduce a method for studying state preparation complexity in dense quantum ppp-spin Hamiltonians on nnn qubits, going beyond bounds based only on circuit lightcones. The key input is the class's effective profile complexity, which is derived from the metric entropy of its Pauli profiles. These profiles record expectations of all Pauli operators supported on exactly ppp qubits. Classes with uniformly bounded quadratic effective profile complexity remain separated from the ground-state energy by a positive multiple of n\sqrt nn​ for sufficiently large fixed ppp. At subquadratic effective profile complexity, the class cannot outperform a suitable benchmark class at leading order, with product states providing a universal benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem of Berta et al. (arXiv:1810.12197) with Gaussian process entropy bounds.
Applying this framework, we show that attaining near-ground-state energy requires Ω(n2/log⁡n)Ω(n^2/\log n)Ω(n2/logn) one- and two-qubit gates, even with arbitrary discardable ancillas. We also obtain depth-width tradeoffs, entanglement-depth and matrix product state bond-dimension lower bounds, and obstructions for both orientations at every fixed level of Parham's magic hierarchy (arXiv:2504.19966), with total circuit width O(n)O(n)O(n). In first-level reverse magic, a shallow circuit is followed by an unrestricted Clifford circuit. The latter can spread local observables across the system, preventing a direct application of small-lightcone bounds. For this first-level class, our bounds also allow arbitrarily many clean ancillas at fixed shallow-circuit depth. A sharper benchmark shows that Clifford+TTT circuits with o(n)o(n)o(n) TTT-gates have no leading-order energy advantage over product stabilizer states, even with unrestricted Clifford operations and arbitrary discardable ancillas.
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.
We investigate the fundamental time complexity, as constrained by Lieb-Robinson bounds, for preparing entangled states useful in quantum metrology. We relate the minimum time to the Quantum Fisher Information (FQF_QFQ​) for a system of NNN quantum spins on a ddd-dimensional lattice with 1/rα1/r^α1/rα interactions with rrr being the distance between two interacting spins. We focus on states with FQ∼N1+γF_Q \sim N^{1+γ}FQ​∼N1+γ where γ∈(0,1]γ\in (0,1]γ∈(0,1], i.e., scaling from the standard quantum limit to the Heisenberg limit. For short-range interactions (α>2d+1α> 2d+1α>2d+1), we prove the minimum time ttt scales as t≳Lγt \gtrsim L^γt≳Lγ, where L∼N1/dL \sim N^{1/d}L∼N1/d. For long-range interactions, we find a hierarchy of possible speedups: t≳Lγ(α−2d)t \gtrsim L^{γ(α-2d)}t≳Lγ(α−2d) for 2d<α<2d+12d < α< 2d+12d<α<2d+1, t≳log⁡Lt \gtrsim \log Lt≳logL for (2−γ)d<α<2d(2-γ)d < α< 2d(2−γ)d<α<2d, and ttt may even vanish algebraically in 1/L1/L1/L for α<(2−γ)dα< (2-γ)dα<(2−γ)d. These bounds extend to the minimum circuit depth required for state preparation, assuming two-qubit gate speeds scale as 1/rα1/r^α1/rα. We further show that these bounds are saturable, up to sub-polynomial corrections, for all ααα at the Heisenberg limit (γ=1γ=1γ=1) and for α>(2−γ)dα> (2-γ)dα>(2−γ)d when γ<1γ<1γ<1. Our results establish a benchmark for the time-optimality of protocols that prepare metrologically useful quantum states.
A crucial subroutine in quantum computing is to load the classical data of NNN complex numbers into the amplitude of a superposed $n=\ensuremath{\lceil}{log}_{2}N\ensuremath{\rceil}$-qubit state. It has been proven that any algorithm universally implementing this subroutine would need at least O(N)O(N)O(N) constant weight operations. However, the proof assumes that only nnn qubits are used, whereas the circuit depth could be reduced by extending the space and allowing ancillary qubits. Here we investigate this space-time tradeoff in quantum state preparation with classical data. We propose quantum algorithms with O(n2)O({n}^{2})O(n2) circuit depth to encode any NNN complex numbers using only single- and two-qubit gates, and local measurements with ancillary qubits. Different variances of the algorithm are proposed with different space and runtime. In particular, we present a scheme with O(N2)O({N}^{2})O(N2) ancillary qubits, O(n2)O({n}^{2})O(n2) circuit depth, and O(n2)O({n}^{2})O(n2) average runtime, which exponentially improves the conventional bound. While the algorithm requires more ancillary qubits, it consists of quantum circuit blocks that only simultaneously act on a constant number of qubits, and at most O(n)O(n)O(n) qubits are entangled. We also prove a fundamental lower bound $\mathrm{\ensuremath{\Omega}}(n)$ for the minimum circuit depth and runtime with an arbitrary number of ancillary qubits, aligning with our scheme with O(n2)O({n}^{2})O(n2). The algorithms are expected to have wide applications in both near-term and universal quantum computing.
Dynamic circuits, which augment unitary operations with mid-circuit measurements and classical feedforward, can generate long-range entanglement in constant depth, enabling low-depth primitives ranging from nontrivial state preparation to many-qubit entangling gates. Escaping the light-cone constraints of unitary circuits, however, comes at a cost: these primitives typically require a number of mid-circuit measurements that scales with system size and that, together with feedforward latency, can introduce errors that degrade the long-range entanglement they rely on. Here, we alleviate this tension by showing that many such primitives, when cast into a common framework, admit an error-detection scheme that trades infidelity for postselection overhead with no additional ancillas. Our framework thus unifies and upgrades a broad class of primitives including fan-out gates, multi-qubit Pauli rotations, the preparation of W and higher-weight Dicke states, and certain non-normal matrix product states. We also introduce a reduced-depth, error-detected implementation of the Hadamard test, extending the use cases of dynamic circuits to a key algorithmic primitive. Finally, we establish the practical utility of our scheme through experiments on a superconducting quantum processor. We demonstrate the error-detected preparation of a long-range entangled Bell pair spanning a 100-qubit chain with fidelity F=0.59±0.02F=0.59\pm0.02F=0.59±0.02, surpassing the entanglement-certification threshold F>0.5F>0.5F>0.5 that the baseline dynamic-circuit implementation fails to reach (0.39±0.010.39\pm0.010.39±0.01). Separately, we demonstrate constant-depth preparation of W states of up to 20 qubits by consuming GHZ states of up to 40 qubits, finding absolute fidelity improvements of ΔF≈0.2ΔF\approx 0.2ΔF≈0.2 across the largest sizes studied. Altogether, these results bring low-depth dynamic-circuit primitives within practical reach on present-day hardware.
We use Pauli Path simulation to variationally obtain parametrized circuits for preparing ground states of various quantum many-body Hamiltonians. These include the quantum Ising model in one dimension, in two dimensions on square and heavy-hex lattices, and the Kitaev honeycomb model, all at system sizes of one hundred qubits or more – sizes at which generic quantum circuits are beyond the reach of exact state-vector simulation – thereby reaching utility scale. We benchmark the Pauli Path simulation results against exact ground-state energies when available, and against density-matrix renormalization group calculations otherwise, finding strong agreement. To further assess the quality of the variational states, we evaluate the magnetization in the x and z directions for the quantum Ising models and compute the topological entanglement entropy for the Kitaev honeycomb model. Finally, we prepare approximate ground states of the Kitaev honeycomb model with 48 qubits, in both the gapped and gapless regimes, on Quantinuum's System Model H2 quantum computer using parametrized circuits obtained from Pauli Path simulation. We achieve a relative energy error of approximately 5 % without error mitigation and demonstrate the braiding of Abelian anyons on the quantum device beyond fixed-point models.
Classical shadows extract quantum properties from reusable classical records, typically obtained through randomized measurement settings. Although individual settings may be shallow, switching among them introduces control, calibration, and reconfiguration costs beyond conventional metrics. Here we construct, for every nnn, a single fixed shallow quantum analyzer whose Born outcomes replace externally sampled settings as labels for reusable shadow snapshots. The analyzer combines a freshly prepared nnn-qubit fiducial register AAA with parallel Bell readout of AAA and the unknown system SSS, producing one 2n2n2n-bit record per copy. The same circuit realizes a rank-one minimal informationally complete measurement: one fixed setting replaces the 3n3^n3n local-Pauli settings conventionally used for complete reconstruction while retaining the minimum d2d^2d2 outcomes with d=2nd=2^nd=2n. Its Pauli-diagonal frame admits an analytic inverse. For fixed Hermitian observables, the Haar-averaged conditional variance has a dimension-independent coefficient, whereas the state-uniform coefficient is dimension dependent. For n≥3n\ge3n≥3, worst-state Pauli variances remain bounded in the axial sector and scale as Θ(d)Θ(d)Θ(d) in the mixed sector. Fiducial preparation before system contact uses n−1n-1n−1 arbitrary two-qubit gates, no work qubits beyond AAA, and logarithmic depth under all-to-all connectivity. The unknown system undergoes one parallel system-ancilla entangling layer followed by local Hadamards and readout. Measurement-assisted preparation achieves O(1)O(1)O(1) adaptive quantum depth using n+1n+1n+1 extra qubits in the heralded route, or O(nlog⁡n)O(n\log n)O(nlogn) auxiliaries for deterministic completion. These tradeoffs show that part of the measurement-setting randomness and control complexity normally supplied shot by shot can instead be compiled into a fixed reusable analyzer.