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

A Method for Constructing Quasi-Random Peaked Quantum Circuits

O. G. Udalov

Published Aug 10, 2025• 1 citation
arXivHTMLPDF

Abstract

An algorithm is proposed for constructing quasi-random "peaked" quantum circuits, i.e., circuits whose final qubit state exhibits a high probability concentration on a specific computational basis state. These circuits consist of random gates arranged in a brick-wall architecture. While the multiqubit state in the middle of the circuit can exhibit significant entanglement, the final state is, with high probability, a predetermined pure bitstring. A technique is introduced to obscure the final bitstring in the structure of the quantum circuit. The algorithm allows precise control over the probability of the final peaked state. A modified version of the algorithm enables the construction of double- or multi-peaked quantum circuits. The matrix product state (MPS) method is evaluated for simulating such circuits; it performs effectively for shallow peaked circuits but offers no significant advantage for deeper ones.

DOI
10.48550/arxiv.2508.07491

Related papers

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

On verifiable quantum advantage with peaked circuit sampling

Scott Aaronson, Yuxuan Zhang

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.

arXiv:2404.14493•Apr 22, 2024•38 citations

Encoding of matrix product states into quantum circuits of one- and two-qubit gates

Shi-Ju Ran

The matrix product state (MPS) belongs to the most important models in, for example, quantum information sciences and condensed-matter physics. However, realizing an $N$-qubit MPS with large $N$ and large entanglement on a quantum platform is extremely challenging, since it requires high-level qudits or $n$-qubit gates with $n\ensuremath{\gg}2$ to carry or produce the entanglement. In this work, an efficient method that accurately encodes a given MPS into a quantum circuit with only one- and two-qubit gates is proposed. Essentially different from the existing compiling methods, our idea is to construct the unitary matrix product operators that optimally disentangle the MPS to a product state. These matrix product operators form the quantum circuit that evolves a product state to the targeted MPS with a high fidelity. Our benchmark on the ground-state MPSs of the strongly correlated spin models show that the constructed quantum circuits can simulate the MPSs with much fewer qubits than the sizes of the MPSs themselves. This method paves a feasible and efficient path to realizing useful and/or exotic quantum states and MPS-based models as quantum circuits on near-term quantum platforms.

arXiv:1908.07958•Physical Review A•Mar 9, 2020•173 citations

Predictive Structure Behind Rare Outcomes in Random Quantum Circuits

Myeongsu Kim, Travis Humble, Sabre Kais

Local random quantum circuits can occasionally produce unusually large output probabilities. However, the final output distribution containing such a peak does not by itself reveal how the peak formed during circuit evolution. We investigate whether states formed during circuit evolution carry structural signatures that predict subsequent peak formation. In numerical experiments, circuits selected for large terminal peaks exhibit stronger pairwise correlations and probability redistribution, together with lower bipartite entanglement and output entropy, than controls generated by the same random-circuit model. Their intermediate states retain higher fresh-peak event probability when the remaining gates are independently regenerated. Within an unconditioned ensemble, a fixed structural score computed from the initial circuit segment predicts new-peak probability. Averaged equally across n=8-16, a replay with equal numbers of remaining-circuit evaluations shows that score-based allocation yields 1.80 times as many peaks as uniform allocation and about 18% more than a fixed baseline based on probability concentration and redistribution. Randomizing relative phases while preserving computational-basis probabilities strongly attenuates the selected-state advantage, demonstrating a functional contribution from relative-phase organization. Controlled gate-selection tests further show that the identified structure can guide circuit construction to promote peak formation. Together, these results connect rare output events to intermediate-state structure with predictive and constructive value under finite-depth local dynamics.

quant-pharXiv:2609.17482•Sep 16, 2026•0 citations

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

Classical Simulation of Peaked Shallow Quantum Circuits

Sergey B. Bravyi, David Gosset, Yinchen Liu

An n-qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of n. We describe a classical algorithm with quasipolynomial runtime nO(logn) that approximately samples from the output distribution of a peaked constant-depth circuit. We give even faster algorithms for circuits composed of nearest-neighbor gates on a D-dimensional grid of qubits, with polynomial runtime nO(1) if D=2 and almost-polynomial runtime nO(loglogn) for D>2. Our sampling algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error, improving previously known methods. As a simple application, we obtain a quasipolynomial algorithm to estimate the magnitude of the expected value of any Pauli observable in the output state of a shallow circuit (which may or may not be peaked). This is a dramatic improvement over the prior state-of-the-art algorithm which had an exponential scaling in √n.

arXiv:2309.08405•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•16 citations
An algorithm is proposed for constructing quasi-random "peaked" quantum circuits, i.e., circuits whose final qubit state exhibits a high probability concentration on a specific computational basis state. These circuits consist of random gates arranged in a brick-wall architecture. While the multiqubit state in the middle of the circuit can exhibit significant entanglement, the final state is, with high probability, a predetermined pure bitstring. A technique is introduced to obscure the final bitstring in the structure of the quantum circuit. The algorithm allows precise control over the probability of the final peaked state. A modified version of the algorithm enables the construction of double- or multi-peaked quantum circuits. The matrix product state (MPS) method is evaluated for simulating such circuits; it performs effectively for shallow peaked circuits but offers no significant advantage for deeper ones.
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.
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.
The matrix product state (MPS) belongs to the most important models in, for example, quantum information sciences and condensed-matter physics. However, realizing an NNN-qubit MPS with large NNN and large entanglement on a quantum platform is extremely challenging, since it requires high-level qudits or nnn-qubit gates with $n\ensuremath{\gg}2$ to carry or produce the entanglement. In this work, an efficient method that accurately encodes a given MPS into a quantum circuit with only one- and two-qubit gates is proposed. Essentially different from the existing compiling methods, our idea is to construct the unitary matrix product operators that optimally disentangle the MPS to a product state. These matrix product operators form the quantum circuit that evolves a product state to the targeted MPS with a high fidelity. Our benchmark on the ground-state MPSs of the strongly correlated spin models show that the constructed quantum circuits can simulate the MPSs with much fewer qubits than the sizes of the MPSs themselves. This method paves a feasible and efficient path to realizing useful and/or exotic quantum states and MPS-based models as quantum circuits on near-term quantum platforms.
Local random quantum circuits can occasionally produce unusually large output probabilities. However, the final output distribution containing such a peak does not by itself reveal how the peak formed during circuit evolution. We investigate whether states formed during circuit evolution carry structural signatures that predict subsequent peak formation. In numerical experiments, circuits selected for large terminal peaks exhibit stronger pairwise correlations and probability redistribution, together with lower bipartite entanglement and output entropy, than controls generated by the same random-circuit model. Their intermediate states retain higher fresh-peak event probability when the remaining gates are independently regenerated. Within an unconditioned ensemble, a fixed structural score computed from the initial circuit segment predicts new-peak probability. Averaged equally across n=8-16, a replay with equal numbers of remaining-circuit evaluations shows that score-based allocation yields 1.80 times as many peaks as uniform allocation and about 18% more than a fixed baseline based on probability concentration and redistribution. Randomizing relative phases while preserving computational-basis probabilities strongly attenuates the selected-state advantage, demonstrating a functional contribution from relative-phase organization. Controlled gate-selection tests further show that the identified structure can guide circuit construction to promote peak formation. Together, these results connect rare output events to intermediate-state structure with predictive and constructive value under finite-depth local dynamics.
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.
An n-qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of n. We describe a classical algorithm with quasipolynomial runtime nO(logn) that approximately samples from the output distribution of a peaked constant-depth circuit. We give even faster algorithms for circuits composed of nearest-neighbor gates on a D-dimensional grid of qubits, with polynomial runtime nO(1) if D=2 and almost-polynomial runtime nO(loglogn) for D>2. Our sampling algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error, improving previously known methods. As a simple application, we obtain a quasipolynomial algorithm to estimate the magnitude of the expected value of any Pauli observable in the output state of a shallow circuit (which may or may not be peaked). This is a dramatic improvement over the prior state-of-the-art algorithm which had an exponential scaling in √n.