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

Deterministic Reconstruction of HQAP Peaked Circuits via Structural Analysis: An Alternative Explanation to Claimed Quantum Advantage

Halloub, Mohamed Ridha

Published Nov 13, 2025• 0 citations
Publisher

Abstract

This work presents a structural analysis of HQAP (Heuristic Quantum Advan-tage Protocol) Peaked Circuits that challenges claimed quantum advantage. We in-troduce Structural Factor Analysis, a methodology that identifies invariant structuralpatterns in quantum circuits to enable deterministic classical reconstruction of hiddenbitstrings. For the HQAP-1917 circuit, our analysis reveals a structural core of 46invariant qubits, reducing the search space from 256 to 210 = 1024 possibilities. Wedemonstrate 100% successful reconstruction of the peak bitstring using classical compu-tation alone, achieving results in minutes that purportedly require quantum hardware.Our findings suggest that structural vulnerabilities in current HQAP constructions un-dermine claims of quantum advantage, and provide a framework for rigorous classicalverification of quantum circuit outputs.

DOI
10.5281/zenodo.17595616

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

Evaluating System-Level Fidelity with Peaked Random Circuits

Martin Brieger, Florian Krötz, Minh Chung +1 more

Quantum computing is progressing beyond experimental prototypes toward cloud-based services and commercially deployed turnkey systems. Evaluating and comparing platform performance requires robust, standardized measures, yet vendors frequently report heterogeneous metrics that are not directly comparable or may not capture whole-system performance. Peaked Random Circuits (PRCs) have recently been proposed as a viable path to demonstrate quantum advantage: a quantum processor can reliably identify a single known high-probability outcome while the circuits' inherent complexity may render classical simulation infeasible. To support robust, system-level evaluation and comparison, we propose a novel benchmarking protocol based on PRCs. By successively running a set of PRCs with varying qubit counts and circuit depths, we quantify a system's ability to identify the deterministic peak despite cumulative noise, gate errors, and connectivity constraints. We demonstrate the benchmark experimentally on IQM's superconducting and AQT's trapped-ion architectures. Our results show that the PRC benchmark provides a holistic yet high-precision view of hardware performance and offers researchers and industry stakeholders a practical and scalable framework for the continuous comparison and evaluation of current and future quantum systems.

quant-pharXiv:2605.25983•May 26, 2026•0 citations

Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation

Alexandru Gheorghiu, Aparna Gupte, Vojtěch Havlíček +1 more

We construct protocols for classically verifiable quantum advantage and classical verification of $\mathsf{BQP}$ computations using \emph{quantum indistinguishability obfuscation} (qiO). Specifically, given qiO and assuming a slightly stronger version of $\mathsf{BQP}\neq\mathsf{BPP}$, we construct a two-message quantum-advantage protocol that is efficiently and publicly verifiable. Our result can be viewed as a rigorous cryptographic foundation for the heuristic quantum advantage proposals based on \emph{peaked random circuit sampling} of Aaronson and Zhang (arXiv:2404.14493). We also construct two simple protocols for classically verifying arbitrary $\mathsf{BQP}$ computations. The first protocol is privately verifiable and assumes only the existence of qiO. This gives a rare example of a nontrivial cryptographic application of (quantum) iO that does not make additional computational hardness assumptions. The second protocol additionally assumes post-quantum one-way functions and is \emph{publicly verifiable}. To our knowledge, this is the first publicly verifiable protocol for classical verification of $\mathsf{BQP}$ computations under computational assumptions in the standard model. As qiO is the basis for our results, we propose an approach to constructing qiO by adapting the local-mixing framework of Canetti--Chamon--Mucciolo--Ruckenstein.

quant-pharXiv:2609.40289•Oct 1, 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 Verification of Quantum Advantage via Clifford Obfuscation

Bin Yan

Demonstrating quantum advantage in a manner that can be independently verified by classical means remains one of the most pressing open problems in quantum computing. Here we propose a new heuristic approach for constructing quantum circuits that are hard to classically simulate yet whose output distributions can be efficiently verified classically. Our approach is based on Clifford circuit obfuscation. This obfuscation scheme hides the Clifford structure and injects a controlled and rapidly growing non-stabilizer resources that resist known classical attack strategies including reverse engineering and direct simulation. Our protocol is heuristic but is supported by both numerical and theoretical evidence. This work provides a new avenue toward classically verifiable quantum advantage that avoids the stringent implementation requirements of known approaches.

quant-pharXiv:2608.15963•Aug 18, 2026•1 citation
This work presents a structural analysis of HQAP (Heuristic Quantum Advan-tage Protocol) Peaked Circuits that challenges claimed quantum advantage. We in-troduce Structural Factor Analysis, a methodology that identifies invariant structuralpatterns in quantum circuits to enable deterministic classical reconstruction of hiddenbitstrings. For the HQAP-1917 circuit, our analysis reveals a structural core of 46invariant qubits, reducing the search space from 256 to 210 = 1024 possibilities. Wedemonstrate 100% successful reconstruction of the peak bitstring using classical compu-tation alone, achieving results in minutes that purportedly require quantum hardware.Our findings suggest that structural vulnerabilities in current HQAP constructions un-dermine claims of quantum advantage, and provide a framework for rigorous classicalverification of quantum circuit outputs.
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.
Quantum computing is progressing beyond experimental prototypes toward cloud-based services and commercially deployed turnkey systems. Evaluating and comparing platform performance requires robust, standardized measures, yet vendors frequently report heterogeneous metrics that are not directly comparable or may not capture whole-system performance. Peaked Random Circuits (PRCs) have recently been proposed as a viable path to demonstrate quantum advantage: a quantum processor can reliably identify a single known high-probability outcome while the circuits' inherent complexity may render classical simulation infeasible. To support robust, system-level evaluation and comparison, we propose a novel benchmarking protocol based on PRCs. By successively running a set of PRCs with varying qubit counts and circuit depths, we quantify a system's ability to identify the deterministic peak despite cumulative noise, gate errors, and connectivity constraints. We demonstrate the benchmark experimentally on IQM's superconducting and AQT's trapped-ion architectures. Our results show that the PRC benchmark provides a holistic yet high-precision view of hardware performance and offers researchers and industry stakeholders a practical and scalable framework for the continuous comparison and evaluation of current and future quantum systems.
We construct protocols for classically verifiable quantum advantage and classical verification of BQP\mathsf{BQP}BQP computations using \emph{quantum indistinguishability obfuscation} (qiO). Specifically, given qiO and assuming a slightly stronger version of BQP≠BPP\mathsf{BQP}\neq\mathsf{BPP}BQP=BPP, we construct a two-message quantum-advantage protocol that is efficiently and publicly verifiable. Our result can be viewed as a rigorous cryptographic foundation for the heuristic quantum advantage proposals based on \emph{peaked random circuit sampling} of Aaronson and Zhang (arXiv:2404.14493). We also construct two simple protocols for classically verifying arbitrary BQP\mathsf{BQP}BQP computations. The first protocol is privately verifiable and assumes only the existence of qiO. This gives a rare example of a nontrivial cryptographic application of (quantum) iO that does not make additional computational hardness assumptions. The second protocol additionally assumes post-quantum one-way functions and is \emph{publicly verifiable}. To our knowledge, this is the first publicly verifiable protocol for classical verification of BQP\mathsf{BQP}BQP computations under computational assumptions in the standard model. As qiO is the basis for our results, we propose an approach to constructing qiO by adapting the local-mixing framework of Canetti--Chamon--Mucciolo--Ruckenstein.
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.
Demonstrating quantum advantage in a manner that can be independently verified by classical means remains one of the most pressing open problems in quantum computing. Here we propose a new heuristic approach for constructing quantum circuits that are hard to classically simulate yet whose output distributions can be efficiently verified classically. Our approach is based on Clifford circuit obfuscation. This obfuscation scheme hides the Clifford structure and injects a controlled and rapidly growing non-stabilizer resources that resist known classical attack strategies including reverse engineering and direct simulation. Our protocol is heuristic but is supported by both numerical and theoretical evidence. This work provides a new avenue toward classically verifiable quantum advantage that avoids the stringent implementation requirements of known approaches.