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

Quantum advantage from random geometrically-two-local Hamiltonian dynamics

Yihui Quek

Published Oct 7, 2025• 0 citations
arXivHTMLPDF

Abstract

Classical hardness-of-sampling results are largely established for random quantum circuits, whereas analog simulators natively realize time evolutions under geometrically local Hamiltonians. Does a typical such Hamiltonian already yield classically-intractable dynamics? We answer this question in the affirmative for the ensemble of geometrically-2-local Hamiltonians with Gaussian coefficients, evolved for constant time. This naturally leads to a quantum advantage scheme with clear prospects for experimental realization, necessitating only course-grained control. We give strong evidence of hardness for this physically-relevant ensemble. We develop the first worst-to-average-case reduction for approximating output probabilities of (time-independent) geometrically-2-local Hamiltonian evolutions. Our reduction proceeds by nonstandard means: while we also leverage polynomial interpolation, unlike previous works, we reduce directly to an evaluator for the exact distribution over Hamiltonians, from which we are trying to prove that sampling is hard. Previous works instead sampled from various perturbations of the true distribution, introducing additional constraints meant to keep the perturbation, measured in total variation distance, under control. We dispense with this step. Our reduction consists in a robust multivariate polynomial interpolation, reduced to sequential robust univariate interpolations via the symmetries of the Gaussian. We circumvent the fact that random Hamiltonians lack a hiding symmetry, a key property in previous proofs. We also contribute an algorithmic version of Berlekamp-Welch to deal with errored evaluations, solving an open problem from the RCS literature. We expect the machinery we develop to find use in average-case Hamiltonian complexity, filling in a gap in this literature which has thus far focussed on worst-case hardness results.

DOI
10.48550/arxiv.2510.06321

Related papers

Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics

Jonas Haferkamp, Dominik Hangleiter, Adam Bouland +3 more

Demonstrating a quantum computational speed-up is a crucial milestone for near-term quantum technology. Recently, sampling protocols for quantum simulators have been proposed that have the potential to show such a quantum advantage, based on commonly made assumptions. The key challenge in the theoretical analysis of this scheme-as of other comparable schemes such as boson sampling-is to lessen the assumptions and close the theoretical loopholes, replacing them by rigorous arguments. In this work, we prove two open conjectures for a simple sampling protocol that is based on the continuous time evolution of a translation-invariant Ising Hamiltonian: anticoncentration of the generated probability distributions and average-case hardness of exactly evaluating those probabilities. The latter is proven building upon recently developed techniques for random circuit sampling. For the former, we exploit the insight that approximate 2-designs for the unitary group admit anticoncentration. We then develop new techniques to prove that the 2D time evolution of the protocol gives rise to approximate 2-designs. Our work provides the strongest theoretical evidence to date that Hamiltonian quantum simulators are classically intractable.

arXiv:1908.08069•Physical Review Letters•Dec 17, 2020•36 citations

Hardness and Complexity Transition of Noisy Random Circuit Sampling

Byeongseon Go, Changhun Oh, Hyunseok Jeong

Random circuit sampling (RCS) is a leading candidate for demonstrating quantum advantage, supported by strong complexity-theoretic evidence of hardness in the ideal setting and by rapid experimental progress to date. In practice, however, noise is unavoidable, and a central problem is to identify the noise-strength boundary between classically simulable and classically hard regimes. In this work, we establish an architecture-general hardness bound for this boundary for the standard local depolarizing noise of strength $γ$. Assuming the standard average-case #P-hardness conjecture for ideal RCS, we show that, for any circuit architecture satisfying this conjecture, noisy RCS on the same architecture remains hard to simulate classically within any inverse-polynomial total variation distance whenever $γ=O(\log n/(nd))$ for $n$-qubit circuits of depth $d$, unless the polynomial hierarchy collapses. Crucially, noisy-RCS hardness follows without any additional conjectural or architecture-specific assumption beyond those already entering the ideal-RCS hardness framework. Our proof combines a low-degree polynomial extrapolation with a monotonicity reduction showing that efficient classical simulation at one depolarizing noise strength implies efficient simulation at every larger strength. Together, these ingredients transfer the standard ideal-RCS hardness conjecture to sampling hardness at a prespecified noise strength. Finally, combining the convergence-to-uniformity result of Dalzell et al. [Commun. Math. Phys. 405, 78 (2024)] with our monotonicity reduction yields efficient classical simulation for $γ=ω(\log n/(nd))$ on layered, regularly connected architectures. Thus, wherever the two architectural settings overlap, this identifies $γ=Θ(\log n/(nd))$ as the asymptotic complexity-transition scale.

quant-pharXiv:2607.20804•Jul 24, 2026•0 citations

"Quantum Supremacy" and the Complexity of Random Circuit Sampling

Adam Bouland, Bill Fefferman, Chinmay Nirkhe +1 more

A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS satisfies an anti-concentration property, making it the first supremacy proposal with both average-case hardness and anti-concentration.

arXiv:1803.04402•Leibniz international proceedings in informatics•Mar 12, 2018•63 citations

Efficient Classical Simulation of Random Shallow 2D Quantum Circuits

John C. Napp, Rolando L. La Placa, Alexander M. Dalzell +2 more

A central question of quantum computing is determining the source of the advantage of quantum computation over classical computation.Even though simulating quantum dynamics on a classical computer is thought to require exponential overhead in the worst case, efficient simulations are known to exist in several special cases.It was widely assumed that these easy-to-simulate cases as well as any yetundiscovered ones could be avoided by choosing a quantum circuit at random.We prove that this intuition is false by showing that certain families of constant-depth, 2D random circuits can be approximately simulated on a classical computer in time only linear in the number of qubits and gates, even though the same families are capable of universal quantum computation and are hard to exactly simulate in the worst case (under standard hardness assumptions).While our proof applies to specific random circuit families, we demonstrate numerically that typical instances of more general families of sufficiently shallow constantdepth 2D random circuits are also efficiently simulable.We propose two classical simulation algorithms.One is based on first simulating spatially local regions which are then "stitched" together via recovery maps.The other reduces the 2D simulation problem to a problem of simulating a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements.Similar processes have recently been the subject of an intensive research focus, which has observed that the dynamics generally undergo a phase transition from a low-entanglement (and efficient-to-simulate) regime to a highentanglement (and inefficient-to-simulate) regime as measurement strength is varied.Via a mapping from random quantum circuits to classical statistical mechanical models, we give analytical evidence that a similar computational phase transition occurs for both of our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied and, additionally, that the effective 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime.Implementing the latter algorithm for the depth-3 "brickwork" architecture, for which exact simulation is hard, we find that a laptop could simulate typical instances on a 409 × 409 grid with a total variation distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms.Numerical results support our analytic evidence that the algorithm is asymptotically efficient.

arXiv:2001.00021•Physical Review X•Apr 27, 2022•140 citations

An (almost) efficient classical algorithm for sampling from typical Gibbs states

Saleh Naghdi, Eric R. Anschuetz

Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based quantum learning algorithms and quantum supremacy proposals, but its classical average-case complexity for physically relevant models remains unresolved. Here, we give strong evidence against an exponential quantum advantage in Gibbs sampling for an ensemble of local systems known as the quantum $p$-spin model. We describe a classical algorithm for sampling from the Gibbs state to any polynomially small error in total variation distance. Our algorithm is based on a meta-algorithm known as algorithmic stochastic localization (ASL). Our main technical result is a generalized convergence theorem for ASL which reduces approximate sampling from any distribution on the hypercube to estimating the mean of a related "tilted distribution" to sufficiently low additive error. We then extend known quasi-polynomial time algorithms for computing local expectation values of a related disordered model to compute these "tilted means" for the quantum $p$-spin model. Finally, we give a non-rigorous physics argument that this mean-estimation algorithm works down to the spin glass transition temperature. As efficient quantum algorithms also fail at this transition, this suggests they cannot Gibbs sample the quantum $p$-spin model at temperatures below that for which classical algorithms are also (almost) efficient.

quant-pharXiv:2609.40250•Oct 1, 2026•0 citations

Quantum supremacy and random circuits

Ramis Movassagh

As Moore's law reaches its limits, quantum computers are emerging with the promise of dramatically outperforming classical computers. We have witnessed the advent of quantum processors with over $50$ quantum bits (qubits), which are expected to be beyond the reach of classical simulation. Quantum supremacy is the event at which the old Extended Church-Turing Thesis is overturned: A quantum computer performs a task that is practically impossible for any classical (super)computer. The demonstration requires both a solid theoretical guarantee and an experimental realization. The lead candidate is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of random quantum circuits. Google recently announced a $53-$qubit experimental demonstration of RCS. Soon after, classical algorithms appeared that challenge the supremacy of random circuits by estimating their outputs. How hard is it to classically simulate the output of random quantum circuits? We prove that estimating the output probabilities of random quantum circuits is formidably hard ($\#P$-Hard) for any classical computer. This makes RCS the strongest candidate for demonstrating quantum supremacy relative to all other proposals. The robustness to the estimation error that we prove may serve as a new hardness criterion for the performance of classical algorithms. To achieve this, we introduce the Cayley path interpolation between any two gates of a quantum computation and convolve recent advances in quantum complexity and information with probability and random matrices. Furthermore, we apply algebraic geometry to generalize the well-known Berlekamp-Welch algorithm that is widely used in coding theory and cryptography. Our results imply that there is an exponential hardness barrier for the classical simulation of most quantum circuits.

arXiv:1909.06210•Sep 11, 2019•23 citations
Classical hardness-of-sampling results are largely established for random quantum circuits, whereas analog simulators natively realize time evolutions under geometrically local Hamiltonians. Does a typical such Hamiltonian already yield classically-intractable dynamics? We answer this question in the affirmative for the ensemble of geometrically-2-local Hamiltonians with Gaussian coefficients, evolved for constant time. This naturally leads to a quantum advantage scheme with clear prospects for experimental realization, necessitating only course-grained control. We give strong evidence of hardness for this physically-relevant ensemble. We develop the first worst-to-average-case reduction for approximating output probabilities of (time-independent) geometrically-2-local Hamiltonian evolutions. Our reduction proceeds by nonstandard means: while we also leverage polynomial interpolation, unlike previous works, we reduce directly to an evaluator for the exact distribution over Hamiltonians, from which we are trying to prove that sampling is hard. Previous works instead sampled from various perturbations of the true distribution, introducing additional constraints meant to keep the perturbation, measured in total variation distance, under control. We dispense with this step. Our reduction consists in a robust multivariate polynomial interpolation, reduced to sequential robust univariate interpolations via the symmetries of the Gaussian. We circumvent the fact that random Hamiltonians lack a hiding symmetry, a key property in previous proofs. We also contribute an algorithmic version of Berlekamp-Welch to deal with errored evaluations, solving an open problem from the RCS literature. We expect the machinery we develop to find use in average-case Hamiltonian complexity, filling in a gap in this literature which has thus far focussed on worst-case hardness results.
Demonstrating a quantum computational speed-up is a crucial milestone for near-term quantum technology. Recently, sampling protocols for quantum simulators have been proposed that have the potential to show such a quantum advantage, based on commonly made assumptions. The key challenge in the theoretical analysis of this scheme-as of other comparable schemes such as boson sampling-is to lessen the assumptions and close the theoretical loopholes, replacing them by rigorous arguments. In this work, we prove two open conjectures for a simple sampling protocol that is based on the continuous time evolution of a translation-invariant Ising Hamiltonian: anticoncentration of the generated probability distributions and average-case hardness of exactly evaluating those probabilities. The latter is proven building upon recently developed techniques for random circuit sampling. For the former, we exploit the insight that approximate 2-designs for the unitary group admit anticoncentration. We then develop new techniques to prove that the 2D time evolution of the protocol gives rise to approximate 2-designs. Our work provides the strongest theoretical evidence to date that Hamiltonian quantum simulators are classically intractable.
Random circuit sampling (RCS) is a leading candidate for demonstrating quantum advantage, supported by strong complexity-theoretic evidence of hardness in the ideal setting and by rapid experimental progress to date. In practice, however, noise is unavoidable, and a central problem is to identify the noise-strength boundary between classically simulable and classically hard regimes. In this work, we establish an architecture-general hardness bound for this boundary for the standard local depolarizing noise of strength γγγ. Assuming the standard average-case #P-hardness conjecture for ideal RCS, we show that, for any circuit architecture satisfying this conjecture, noisy RCS on the same architecture remains hard to simulate classically within any inverse-polynomial total variation distance whenever γ=O(log⁡n/(nd))γ=O(\log n/(nd))γ=O(logn/(nd)) for nnn-qubit circuits of depth ddd, unless the polynomial hierarchy collapses. Crucially, noisy-RCS hardness follows without any additional conjectural or architecture-specific assumption beyond those already entering the ideal-RCS hardness framework. Our proof combines a low-degree polynomial extrapolation with a monotonicity reduction showing that efficient classical simulation at one depolarizing noise strength implies efficient simulation at every larger strength. Together, these ingredients transfer the standard ideal-RCS hardness conjecture to sampling hardness at a prespecified noise strength. Finally, combining the convergence-to-uniformity result of Dalzell et al. [Commun. Math. Phys. 405, 78 (2024)] with our monotonicity reduction yields efficient classical simulation for γ=ω(log⁡n/(nd))γ=ω(\log n/(nd))γ=ω(logn/(nd)) on layered, regularly connected architectures. Thus, wherever the two architectural settings overlap, this identifies γ=Θ(log⁡n/(nd))γ=Θ(\log n/(nd))γ=Θ(logn/(nd)) as the asymptotic complexity-transition scale.
A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS satisfies an anti-concentration property, making it the first supremacy proposal with both average-case hardness and anti-concentration.
A central question of quantum computing is determining the source of the advantage of quantum computation over classical computation.Even though simulating quantum dynamics on a classical computer is thought to require exponential overhead in the worst case, efficient simulations are known to exist in several special cases.It was widely assumed that these easy-to-simulate cases as well as any yetundiscovered ones could be avoided by choosing a quantum circuit at random.We prove that this intuition is false by showing that certain families of constant-depth, 2D random circuits can be approximately simulated on a classical computer in time only linear in the number of qubits and gates, even though the same families are capable of universal quantum computation and are hard to exactly simulate in the worst case (under standard hardness assumptions).While our proof applies to specific random circuit families, we demonstrate numerically that typical instances of more general families of sufficiently shallow constantdepth 2D random circuits are also efficiently simulable.We propose two classical simulation algorithms.One is based on first simulating spatially local regions which are then "stitched" together via recovery maps.The other reduces the 2D simulation problem to a problem of simulating a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements.Similar processes have recently been the subject of an intensive research focus, which has observed that the dynamics generally undergo a phase transition from a low-entanglement (and efficient-to-simulate) regime to a highentanglement (and inefficient-to-simulate) regime as measurement strength is varied.Via a mapping from random quantum circuits to classical statistical mechanical models, we give analytical evidence that a similar computational phase transition occurs for both of our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied and, additionally, that the effective 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime.Implementing the latter algorithm for the depth-3 "brickwork" architecture, for which exact simulation is hard, we find that a laptop could simulate typical instances on a 409 × 409 grid with a total variation distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms.Numerical results support our analytic evidence that the algorithm is asymptotically efficient.
Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based quantum learning algorithms and quantum supremacy proposals, but its classical average-case complexity for physically relevant models remains unresolved. Here, we give strong evidence against an exponential quantum advantage in Gibbs sampling for an ensemble of local systems known as the quantum ppp-spin model. We describe a classical algorithm for sampling from the Gibbs state to any polynomially small error in total variation distance. Our algorithm is based on a meta-algorithm known as algorithmic stochastic localization (ASL). Our main technical result is a generalized convergence theorem for ASL which reduces approximate sampling from any distribution on the hypercube to estimating the mean of a related "tilted distribution" to sufficiently low additive error. We then extend known quasi-polynomial time algorithms for computing local expectation values of a related disordered model to compute these "tilted means" for the quantum ppp-spin model. Finally, we give a non-rigorous physics argument that this mean-estimation algorithm works down to the spin glass transition temperature. As efficient quantum algorithms also fail at this transition, this suggests they cannot Gibbs sample the quantum ppp-spin model at temperatures below that for which classical algorithms are also (almost) efficient.
As Moore's law reaches its limits, quantum computers are emerging with the promise of dramatically outperforming classical computers. We have witnessed the advent of quantum processors with over 505050 quantum bits (qubits), which are expected to be beyond the reach of classical simulation. Quantum supremacy is the event at which the old Extended Church-Turing Thesis is overturned: A quantum computer performs a task that is practically impossible for any classical (super)computer. The demonstration requires both a solid theoretical guarantee and an experimental realization. The lead candidate is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of random quantum circuits. Google recently announced a 53−53-53−qubit experimental demonstration of RCS. Soon after, classical algorithms appeared that challenge the supremacy of random circuits by estimating their outputs. How hard is it to classically simulate the output of random quantum circuits? We prove that estimating the output probabilities of random quantum circuits is formidably hard (#P\#P#P-Hard) for any classical computer. This makes RCS the strongest candidate for demonstrating quantum supremacy relative to all other proposals. The robustness to the estimation error that we prove may serve as a new hardness criterion for the performance of classical algorithms. To achieve this, we introduce the Cayley path interpolation between any two gates of a quantum computation and convolve recent advances in quantum complexity and information with probability and random matrices. Furthermore, we apply algebraic geometry to generalize the well-known Berlekamp-Welch algorithm that is widely used in coding theory and cryptography. Our results imply that there is an exponential hardness barrier for the classical simulation of most quantum circuits.