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

On verifiable quantum advantage with peaked circuit sampling

Scott Aaronson, Yuxuan Zhang

Published Apr 22, 2024• 2 citations
arXivHTMLPDF

Abstract

Over a decade after its proposal, the idea of using quantum computers to sample hard distributions has remained a key path to demonstrating quantum advantage. Yet a severe drawback remains: verification seems to require classical computation exponential in the system size, $n$. As an attempt to overcome this difficulty, we propose a new candidate for quantum advantage experiments with otherwise random "peaked circuits", i.e., quantum circuits whose outputs have high concentrations on a computational basis state. Naturally, the heavy output string can be used for classical verification. In this work, we analytically and numerically study an explicit model of peaked circuits, in which $τ_r$ layers of uniformly random gates are augmented by $τ_p$ layers of gates that are optimized to maximize peakedness. We show that getting $1/\text{poly}(n)$ peakedness from such circuits requires $τ_{p} = Ω((τ_r/n)^{0.19})$ with overwhelming probability. However, we also give numerical evidence that nontrivial peakedness is possible in this model -- decaying exponentially with the number of qubits, but more than can be explained by any approximation where the output of a random quantum circuit is treated as a Haar-random state. This suggests that these peaked circuits have the potential for future verifiable quantum advantage experiments. Our work raises numerous open questions about random peaked circuits, including how to generate them efficiently, and whether they can be distinguished from fully random circuits in classical polynomial time.

DOI
10.48550/arxiv.2404.14493

Related papers

Complexity and hardness of random peaked circuits

Yuxuan Zhang

Near-term feasibility, classical hardness, and verifiability are the three requirements for demonstrating quantum advantage; most existing quantum advantage proposals achieve at most two. A promising candidate recently proposed is through randomly generated peaked circuits. In this work, we study an explicit construction for random peaked circuits: first selecting a random circuit $C$ of polynomial size, which forms a $k$-design. Subsequently, a second random circuit $C'$ is chosen from the same architecture, subject to a postselection criterion: $C'$ must exhibit a high overlap with $C$ in one of their rows. Utilizing unitary design properties, we demonstrate that the circuits generated by this method are non-trivial; specifically, $C'$ is provably far from $C^\dagger$. Indeed, with overwhelmingly high probability, a random peaked circuit generated this way is non-compressible and is of circuit complexity $\tilde Ω(nk)$. This resolves an open problem posed by Aaronson in 2022. Secondly, we analytically establish that estimating the peakedness of a random peaked circuit to within a $2^{-\text{poly}(n)}$ additive error, is average-case \#P-hard. When the additive error is relaxed to $1/\text{poly}(n)$, we note that the worst-case scenario for this problem is BQP-complete. Under widely accepted assumptions on random quantum circuits, we identify a regime where no classical polynomial-time sequential simulator attains inverse-polynomial additive accuracy on the peak on a non-negligible fraction of instances. Thirdly, we study using peaked circuits as a practical attempt for a verifiable quantum advantage protocol. While the postselection method for generating peaked circuits could be costly, we demonstrate that numerical search for $C'$ with randomized initialization successfully returns a random peaked circuit, achieving the properties as theoretically predicted.

arXiv:2510.00132•Sep 30, 2025•0 citations

The optimization landscape of peaked-circuit generation

Ilyes Jamoussi

Peaked circuits are random quantum circuits whose measurement returns one bitstring far more often than chance. The probability of that string is the peakedness, and a verifier who knows the string checks the device in a few shots. Peaked circuits are a candidate route to verifiable quantum advantage, and classical generation is the bottleneck. Aaronson and Zhang train a variational circuit by gradient descent, and the peakedness they reach decays exponentially with the number of qubits. They state that either their optimizer stalls or no efficient generation method exists. Here we show that no bare fixed base fits the decay we measure and that neither the barren plateau nor fragmentation of the solution set explains it. We measure the optimization landscape on eighteen instances per size, from eight to sixteen qubits, under a protocol whose falsifiers were fixed in advance. The decay steepens as the qubit number grows, leaving extrapolations to larger devices unsupported. A better optimizer exists, but it gains a few percent and the peakedness it reaches decays at nearly the same rate. Aaronson and Zhang attribute the difficulty to a barren plateau. The plateau is present, but the second-order amplitude data are depth-independent while the attained peakedness is not. Independent runs land on uncorrelated solutions, yet paths connecting them stay well above the scale of a random state, so fragmentation fails at that scale. In the deep limit we take the scrambled state Haar-random. There we prove that no search over a polynomial-parameter Lipschitz family, exhaustive search included, beats the scale of a random state by more than a poly(n) factor on average. Both branches of the Aaronson-Zhang alternative therefore stay open. A generation method must beat a preregistered baseline, and a hardness argument must accommodate a solution set connected at the scale of a random state.

quant-pharXiv:2608.11890•Aug 13, 2026•0 citations

Peaked quantum advantage using error correction

Abhinav Deshpande, Bill Fefferman, Soumik Ghosh +2 more

A key issue of current quantum advantage experiments is that their verification requires a full classical simulation of the ideal computation. This limits the regime in which the experiments can be verified to precisely the regime in which they are also simulatable. An important outstanding question is therefore to find quantum advantage schemes that are also classically verifiable. We make progress on this question by designing a new quantum advantage proposal--Hidden Code Sampling--whose output distribution is conditionally peaked. These peaks enable verification in far less time than it takes for full simulation. At the same time, we show that exactly sampling from the output distribution is classically hard unless the polynomial hierarchy collapses, and we propose a plausible conjecture regarding average-case hardness. Our scheme is based on ideas from quantum error correction. The required quantum computations are closely related to quantum fault-tolerant circuits and can potentially be implemented transversally. Our proposal may thus give rise to a next generation of quantum advantage experiments en route to full quantum fault tolerance.

•Oct 6, 2025•0 citations

Towards verifiable quantum advantage with random circuits: Observables that survive concentration

Antonio A. Mele, Francesco A. Mele, Jarrod R. McClean +1 more

Demonstrating quantum advantage on current quantum hardware is a central goal of quantum computing, and random quantum circuits underpin many leading proposals. Yet sampling-based demonstrations are often difficult to verify, while observable-based approaches face a different challenge: concentration can suppress differences between circuit instances. Recent experiments have put forward the estimation of out-of-time-order correlators (OTOCs) in random circuits as a promising task for verifiable quantum advantage, yet whether their circuit-to-circuit fluctuations survive concentration as system size grows has remained open. Here we show that they do. For broad classes of local random circuits in any fixed spatial dimension, we prove inverse-polynomial fluctuations of fixed-order OTOCs at system-scale depths. In one-dimensional Haar-random brickwork circuits, we further show that macroscopically many gates contribute to these fluctuations, yet in each layer they remain confined to a sublinear-width region. As a byproduct, we develop a classical algorithm exhibiting the first rigorous improvement over brute-force classical simulation of OTOCs in 1D. Although classical hardness remains open, our results rule out strong concentration as an obstruction to OTOC-based proposals for verifiable quantum advantage.

quant-pharXiv:2609.37890•Sep 30, 2026•0 citations

Efficient Classical Simulation of Heuristic Peaked Quantum Circuits

David Kremer, Nicolas Dupuis

Peaked quantum circuits, whose output distribution is sharply concentrated on a single bitstring, have emerged as a promising candidate for verifiable quantum advantage, as the correctness of the quantum output can be checked by simply comparing against the known peak. Recent work by Gharibyan et al. arXiv:2510.25838 claimed heuristic quantum advantage using peaked circuits executed on Quantinuum's 56-qubit H2 processor. These peaked circuits concentrate their output on a single hidden bitstring by training a shallow simulable circuit variationally and inserting an obfuscated permutation to increase the depth to a level that makes classical simulation intractable, with estimated runtimes of years for the largest instances. We show that these circuits can be efficiently simulated classically. We describe a method that efficiently performs a full tensor network contraction, allowing near-exact sampling and extraction of the peaked bitstring. The method exploits the mirrored structure of the circuit and iteratively cancels both halves into a Matrix Product Operator (MPO), and avoids the obfuscated permutation by greedily reducing the MPO bond dimension through a process we call unswapping. The method can fully contract and extract the peak of the largest circuit in approximately one hour on a single GPU, around half the time it took to run on the quantum hardware.

quant-pharXiv:2604.21908•Apr 24, 2026•0 citations

Verifiable quantum advantage based on polynomials with planted structures

Markus Bläser, Michael Gullans, Dominik Hangleiter +2 more

A central question in the theory of quantum advantage is whether there are quantum advantage protocols with similar resource requirements as random circuit sampling that are also verifiable just from the classical outputs of the quantum computation. Here, we develop the idea of simulation secrets for verifiable advantage. A verifier can use a simulation secret to evaluate a cross-entropy test faster than it would take a classical adversary to pass the test. We instantiate this idea using IQP circuits described by cubic polynomials with planted independent spaces. These correspond to the largest independent set in the orbit of a polynomial under the general linear group and yield a low-rank stabilizer decomposition of the corresponding state. We conjecture that large independent spaces are invisible to a computationally bounded adversary, and therefore they cannot exploit them to pass the protocol. A second conjecture regards the fine-grained complexity of producing samples that pass the cross-entropy test for uniformly random polynomials. Under these conjectures, our scheme results in a polynomial gap between the verification time and the time a classical adversary would need to pass the protocol---both are exponential. It has a potential application to generating classically certifiable randomness, since the output distributions have high min-entropy. We estimate that the planted polynomial scheme is implementable using 100 logical qubits at logical error rates around $10^{-6}$.

quant-pharXiv:2609.39918•Oct 1, 2026•0 citations
Over a decade after its proposal, the idea of using quantum computers to sample hard distributions has remained a key path to demonstrating quantum advantage. Yet a severe drawback remains: verification seems to require classical computation exponential in the system size, nnn. As an attempt to overcome this difficulty, we propose a new candidate for quantum advantage experiments with otherwise random "peaked circuits", i.e., quantum circuits whose outputs have high concentrations on a computational basis state. Naturally, the heavy output string can be used for classical verification. In this work, we analytically and numerically study an explicit model of peaked circuits, in which τrτ_rτr​ layers of uniformly random gates are augmented by τpτ_pτp​ layers of gates that are optimized to maximize peakedness. We show that getting 1/poly(n)1/\text{poly}(n)1/poly(n) peakedness from such circuits requires τp=Ω((τr/n)0.19)τ_{p} = Ω((τ_r/n)^{0.19})τp​=Ω((τr​/n)0.19) with overwhelming probability. However, we also give numerical evidence that nontrivial peakedness is possible in this model -- decaying exponentially with the number of qubits, but more than can be explained by any approximation where the output of a random quantum circuit is treated as a Haar-random state. This suggests that these peaked circuits have the potential for future verifiable quantum advantage experiments. Our work raises numerous open questions about random peaked circuits, including how to generate them efficiently, and whether they can be distinguished from fully random circuits in classical polynomial time.
Near-term feasibility, classical hardness, and verifiability are the three requirements for demonstrating quantum advantage; most existing quantum advantage proposals achieve at most two. A promising candidate recently proposed is through randomly generated peaked circuits. In this work, we study an explicit construction for random peaked circuits: first selecting a random circuit CCC of polynomial size, which forms a kkk-design. Subsequently, a second random circuit C′C'C′ is chosen from the same architecture, subject to a postselection criterion: C′C'C′ must exhibit a high overlap with CCC in one of their rows. Utilizing unitary design properties, we demonstrate that the circuits generated by this method are non-trivial; specifically, C′C'C′ is provably far from C†C^\daggerC†. Indeed, with overwhelmingly high probability, a random peaked circuit generated this way is non-compressible and is of circuit complexity Ω~(nk)\tilde Ω(nk)Ω~(nk). This resolves an open problem posed by Aaronson in 2022. Secondly, we analytically establish that estimating the peakedness of a random peaked circuit to within a 2−poly(n)2^{-\text{poly}(n)}2−poly(n) additive error, is average-case \#P-hard. When the additive error is relaxed to 1/poly(n)1/\text{poly}(n)1/poly(n), we note that the worst-case scenario for this problem is BQP-complete. Under widely accepted assumptions on random quantum circuits, we identify a regime where no classical polynomial-time sequential simulator attains inverse-polynomial additive accuracy on the peak on a non-negligible fraction of instances. Thirdly, we study using peaked circuits as a practical attempt for a verifiable quantum advantage protocol. While the postselection method for generating peaked circuits could be costly, we demonstrate that numerical search for C′C'C′ with randomized initialization successfully returns a random peaked circuit, achieving the properties as theoretically predicted.
Peaked circuits are random quantum circuits whose measurement returns one bitstring far more often than chance. The probability of that string is the peakedness, and a verifier who knows the string checks the device in a few shots. Peaked circuits are a candidate route to verifiable quantum advantage, and classical generation is the bottleneck. Aaronson and Zhang train a variational circuit by gradient descent, and the peakedness they reach decays exponentially with the number of qubits. They state that either their optimizer stalls or no efficient generation method exists. Here we show that no bare fixed base fits the decay we measure and that neither the barren plateau nor fragmentation of the solution set explains it. We measure the optimization landscape on eighteen instances per size, from eight to sixteen qubits, under a protocol whose falsifiers were fixed in advance. The decay steepens as the qubit number grows, leaving extrapolations to larger devices unsupported. A better optimizer exists, but it gains a few percent and the peakedness it reaches decays at nearly the same rate. Aaronson and Zhang attribute the difficulty to a barren plateau. The plateau is present, but the second-order amplitude data are depth-independent while the attained peakedness is not. Independent runs land on uncorrelated solutions, yet paths connecting them stay well above the scale of a random state, so fragmentation fails at that scale. In the deep limit we take the scrambled state Haar-random. There we prove that no search over a polynomial-parameter Lipschitz family, exhaustive search included, beats the scale of a random state by more than a poly(n) factor on average. Both branches of the Aaronson-Zhang alternative therefore stay open. A generation method must beat a preregistered baseline, and a hardness argument must accommodate a solution set connected at the scale of a random state.
A key issue of current quantum advantage experiments is that their verification requires a full classical simulation of the ideal computation. This limits the regime in which the experiments can be verified to precisely the regime in which they are also simulatable. An important outstanding question is therefore to find quantum advantage schemes that are also classically verifiable. We make progress on this question by designing a new quantum advantage proposal--Hidden Code Sampling--whose output distribution is conditionally peaked. These peaks enable verification in far less time than it takes for full simulation. At the same time, we show that exactly sampling from the output distribution is classically hard unless the polynomial hierarchy collapses, and we propose a plausible conjecture regarding average-case hardness. Our scheme is based on ideas from quantum error correction. The required quantum computations are closely related to quantum fault-tolerant circuits and can potentially be implemented transversally. Our proposal may thus give rise to a next generation of quantum advantage experiments en route to full quantum fault tolerance.
Demonstrating quantum advantage on current quantum hardware is a central goal of quantum computing, and random quantum circuits underpin many leading proposals. Yet sampling-based demonstrations are often difficult to verify, while observable-based approaches face a different challenge: concentration can suppress differences between circuit instances. Recent experiments have put forward the estimation of out-of-time-order correlators (OTOCs) in random circuits as a promising task for verifiable quantum advantage, yet whether their circuit-to-circuit fluctuations survive concentration as system size grows has remained open. Here we show that they do. For broad classes of local random circuits in any fixed spatial dimension, we prove inverse-polynomial fluctuations of fixed-order OTOCs at system-scale depths. In one-dimensional Haar-random brickwork circuits, we further show that macroscopically many gates contribute to these fluctuations, yet in each layer they remain confined to a sublinear-width region. As a byproduct, we develop a classical algorithm exhibiting the first rigorous improvement over brute-force classical simulation of OTOCs in 1D. Although classical hardness remains open, our results rule out strong concentration as an obstruction to OTOC-based proposals for verifiable quantum advantage.
Peaked quantum circuits, whose output distribution is sharply concentrated on a single bitstring, have emerged as a promising candidate for verifiable quantum advantage, as the correctness of the quantum output can be checked by simply comparing against the known peak. Recent work by Gharibyan et al. arXiv:2510.25838 claimed heuristic quantum advantage using peaked circuits executed on Quantinuum's 56-qubit H2 processor. These peaked circuits concentrate their output on a single hidden bitstring by training a shallow simulable circuit variationally and inserting an obfuscated permutation to increase the depth to a level that makes classical simulation intractable, with estimated runtimes of years for the largest instances. We show that these circuits can be efficiently simulated classically. We describe a method that efficiently performs a full tensor network contraction, allowing near-exact sampling and extraction of the peaked bitstring. The method exploits the mirrored structure of the circuit and iteratively cancels both halves into a Matrix Product Operator (MPO), and avoids the obfuscated permutation by greedily reducing the MPO bond dimension through a process we call unswapping. The method can fully contract and extract the peak of the largest circuit in approximately one hour on a single GPU, around half the time it took to run on the quantum hardware.
A central question in the theory of quantum advantage is whether there are quantum advantage protocols with similar resource requirements as random circuit sampling that are also verifiable just from the classical outputs of the quantum computation. Here, we develop the idea of simulation secrets for verifiable advantage. A verifier can use a simulation secret to evaluate a cross-entropy test faster than it would take a classical adversary to pass the test. We instantiate this idea using IQP circuits described by cubic polynomials with planted independent spaces. These correspond to the largest independent set in the orbit of a polynomial under the general linear group and yield a low-rank stabilizer decomposition of the corresponding state. We conjecture that large independent spaces are invisible to a computationally bounded adversary, and therefore they cannot exploit them to pass the protocol. A second conjecture regards the fine-grained complexity of producing samples that pass the cross-entropy test for uniformly random polynomials. Under these conjectures, our scheme results in a polynomial gap between the verification time and the time a classical adversary would need to pass the protocol---both are exponential. It has a potential application to generating classically certifiable randomness, since the output distributions have high min-entropy. We estimate that the planted polynomial scheme is implementable using 100 logical qubits at logical error rates around 10−610^{-6}10−6.