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:2308.07152 · PRX Quantum

Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security

Michael J. Bremner, Bin Cheng, Zhengfeng Ji

Published Apr 22, 2025• 2 citations
arXivHTMLPDF

Abstract

Sampling problems demonstrating beyond classical computing power with noisy intermediate-scale quantum devices have been experimentally realized. In those realizations, however, our trust that the quantum devices faithfully solve the claimed sampling problems is usually limited to simulations of smaller-scale instances and is, therefore, indirect. The problem of verifiable quantum advantage aims to resolve this critical issue and provides us with greater confidence in a claimed advantage. Instantaneous quantum polynomial-time (IQP) sampling has been proposed to achieve beyond classical capabilities with a verifiable scheme based on quadratic-residue codes (QRC). Unfortunately, this verification scheme was recently broken by an attack proposed by Kahanamoku-Meyer. In this work, we revive IQP-based verifiable quantum advantage by making two major contributions. Firstly, we introduce a family of IQP sampling protocols called the , which builds on results linking IQP circuits, the stabilizer formalism, coding theory, and an efficient characterization of IQP-circuit correlation functions. This construction extends the scope of existing IQP-based schemes while maintaining their simplicity and verifiability. Secondly, we introduce the (HSC) problem as a well-defined mathematical challenge that underlies the stabilizer scheme. To assess classical security, we explore a class of attacks based on secret extraction, including Kahanamoku-Meyer’s attack as a special case. We provide evidence of the security of the stabilizer scheme, assuming the hardness of the HSC problem. We also point out that the vulnerability observed in the original QRC scheme is primarily attributed to inappropriate parameter choices, which can be naturally rectified with proper parameter settings.

DOI
10.1103/prxquantum.6.020315

Related papers

Secret-Extraction Attacks against Obfuscated Instantaneous Quantum Polynomial-Time Circuits

David Gross, Dominik Hangleiter

Quantum computing devices can now perform sampling tasks that, according to complexity-theoretic and numerical evidence, are beyond the reach of classical computers. This raises the question of how one can efficiently verify that a quantum computer operating in this regime works as intended. In 2008, Shepherd and Bremner proposed a protocol in which a verifier constructs a unitary from the comparatively easy-to-implement family of so-called and challenges a prover to execute it on a quantum computer. The challenge problem is designed to contain an obfuscated secret, which can be turned into a statistical test that accepts samples from a correct quantum implementation. It was conjectured that extracting the secret from the challenge problem is -hard, so that the ability to pass the test constitutes strong evidence that the prover possesses a quantum device and that it works as claimed. Unfortunately, about a decade later, Kahanamoku-Meyer found an efficient classical secret-extraction attack. Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol. Their has been explicitly designed to circumvent the known weakness. They also suggested that the original construction can be made secure by adjusting the problem parameters. In this work, we develop a number of secret-extraction attacks that are effective against both new approaches in a wide range of problem parameters. In particular, we find multiple ways to recover the 300 -bit secret hidden in a challenge data set published by Bremner, Cheng, and Ji. The important problem of finding an efficient and reliable verification protocol for sampling-based proofs of quantum advantage thus remains open.

arXiv:2312.10156•PRX Quantum•Apr 22, 2025•2 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

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth

Joel Rajakumar, James D. Watson, Yi-Kai Liu

Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, whose depth is greater than a critical O (1) threshold, the output distribution can be efficiently sampled by a classical computer. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit’s architecture, on anti-concentration properties, nor do we require Ω(log (n )) circuit depth. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought. Furthermore, we show that the critical depth threshold of our algorithm is tight, and below this threshold there are noisy IQP circuits which are hard to sample from. Thus we demonstrate that noisy IQP circuits exhibit a phase transition in the computational complexity of sampling, as circuit depth is increased.

arXiv:2403.14607•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2025•7 citations

Forging quantum data: classically defeating an IQP-based quantum test

Gregory D. Kahanamoku–Meyer

Recently, quantum computing experiments have for the first time exceeded the capability of classical computers to perform certain computations – a milestone termed "quantum computational advantage." However, verifying the output of the quantum device in these experiments required extremely large classical computations. An exciting next step for demonstrating quantum capability would be to implement tests of quantum computational advantage with efficient classical verification, such that larger system sizes can be tested and verified. One of the first proposals for an efficiently-verifiable test of quantumness consists of hiding a secret classical bitstring inside a circuit of the class IQP, in such a way that samples from the circuit's output distribution are correlated with the secret. The classical hardness of this protocol has been supported by evidence that directly simulating IQP circuits is hard, but the security of the protocol against other (non-simulating) classical attacks has remained an open question. In this work we demonstrate that the protocol is not secure against classical forgery. We describe a classical algorithm that can not only convince the verifier that the (classical) prover is quantum, but can in fact can extract the secret key underlying a given protocol instance. Furthermore, we show that the key extraction algorithm is efficient in practice for problem sizes of hundreds of qubits. Finally, we provide an implementation of the algorithm, and give the secret vector underlying the "\$25 challenge" posted online by the authors of the original paper.

arXiv:1912.05547•Quantum•Sep 11, 2023•7 citations

Classically simulating intermediate-scale instantaneous quantum polynomial circuits through a random graph approach

Julien Codsi, John van de Wetering

Quantum advantage is a demonstration of a computation by a quantum computer that cannot be performed by the best classical computer in a reasonable time. A well-studied approach to demonstrating this on near-term quantum computers is to use random circuit sampling. It has been suggested that a good candidate for demonstrating quantum advantage with random circuit sampling is to use instantaneous quantum polynomial (IQP) circuits. These are quantum circuits where the unitary it implements is diagonal. In this paper, we introduce improved techniques for exactly classically simulating random IQP circuits. We find a simple algorithm to calculate an amplitude of an $n$-qubit IQP circuit with dense random two-qubit interactions in time $O(\frac{{log}^{2}n}{n}{2}^{n})$, which for sparse circuits (where each qubit interacts with $O(logn)$ other qubits) runs in $o({2}^{n}/\mathrm{poly}(n))$ for any given polynomial. Using a more complicated stabilizer decomposition approach we improve the algorithm for dense circuits to $O(\frac{{(logn)}^{4\ensuremath{-}\ensuremath{\beta}}}{{n}^{2\ensuremath{-}\ensuremath{\beta}}}{2}^{n})$ where $\ensuremath{\beta}\ensuremath{\approx}0.396$. We further discuss how our techniques also lead to improved simulation times for IQP circuits on restricted architectures. We benchmarked our main algorithm and found that we can simulate up to 50-qubit circuits in a couple of minutes on a laptop, with 68-qubit sparse circuits taking a couple of hours. We estimate dense 70-qubit circuits are in range for large computing clusters.

arXiv:2212.08609•Physical Review A•Jan 14, 2025•4 citations

The Impact of Qubit Connectivity on Quantum Advantage in Noisy IQP Circuits

Leonardo Placidi, Enrico Rinaldi, Keisuke Fujii +1 more

Instantaneous Quantum Polynomial-time (IQP) circuits are a candidate for demonstrating near-term quantum advantage, as their sampling task is believed to be classically hard in the ideal theoretical setting under standard complexity-theoretic assumptions. In noisy implementations, however, this hardness can disappear once circuit depth exceeds a noise-dependent critical threshold. We show that qubit connectivity is a key parameter in this transition, since sparse architectures require additional routing to implement long-range interactions, thereby increasing compiled circuit depth. To make this explicit, we present a connectivity-aware analysis of compiled IQP circuits. For a fixed abstract IQP instance, different hardware connectivity graphs yield different compiled depths and thus different effective positions relative to the noisy-IQP simulatability boundary. We quantify this architecture-dependent shift using the compiled depth overhead and the corresponding simulatability margin. We combine analytic depth estimates for sparse geometries, including the two-dimensional grid, with native-gateset-aware compilation experiments across seven hardware-grounded experimental device models derived from publicly available topologies. To compare these device models under a unified empirical framework, we approximate the effective noise level primarily through reported two-qubit gate error rates. This lets us compare how much effective noise sparse and fully connected architectures can tolerate for the same position relative to the noisy-IQP simulatability boundary. Our results show that sparse connectivity requires a lower effective noise level to sustain the same margin relative to the noisy-IQP simulatability boundary, and they provide a quantitative framework for determining when compiled IQP experiments are likely to remain outside, or instead enter, the classically simulatable regime.

quant-pharXiv:2604.12635•Apr 15, 2026•0 citations
Sampling problems demonstrating beyond classical computing power with noisy intermediate-scale quantum devices have been experimentally realized. In those realizations, however, our trust that the quantum devices faithfully solve the claimed sampling problems is usually limited to simulations of smaller-scale instances and is, therefore, indirect. The problem of verifiable quantum advantage aims to resolve this critical issue and provides us with greater confidence in a claimed advantage. Instantaneous quantum polynomial-time (IQP) sampling has been proposed to achieve beyond classical capabilities with a verifiable scheme based on quadratic-residue codes (QRC). Unfortunately, this verification scheme was recently broken by an attack proposed by Kahanamoku-Meyer. In this work, we revive IQP-based verifiable quantum advantage by making two major contributions. Firstly, we introduce a family of IQP sampling protocols called the , which builds on results linking IQP circuits, the stabilizer formalism, coding theory, and an efficient characterization of IQP-circuit correlation functions. This construction extends the scope of existing IQP-based schemes while maintaining their simplicity and verifiability. Secondly, we introduce the (HSC) problem as a well-defined mathematical challenge that underlies the stabilizer scheme. To assess classical security, we explore a class of attacks based on secret extraction, including Kahanamoku-Meyer’s attack as a special case. We provide evidence of the security of the stabilizer scheme, assuming the hardness of the HSC problem. We also point out that the vulnerability observed in the original QRC scheme is primarily attributed to inappropriate parameter choices, which can be naturally rectified with proper parameter settings.
Quantum computing devices can now perform sampling tasks that, according to complexity-theoretic and numerical evidence, are beyond the reach of classical computers. This raises the question of how one can efficiently verify that a quantum computer operating in this regime works as intended. In 2008, Shepherd and Bremner proposed a protocol in which a verifier constructs a unitary from the comparatively easy-to-implement family of so-called and challenges a prover to execute it on a quantum computer. The challenge problem is designed to contain an obfuscated secret, which can be turned into a statistical test that accepts samples from a correct quantum implementation. It was conjectured that extracting the secret from the challenge problem is -hard, so that the ability to pass the test constitutes strong evidence that the prover possesses a quantum device and that it works as claimed. Unfortunately, about a decade later, Kahanamoku-Meyer found an efficient classical secret-extraction attack. Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol. Their has been explicitly designed to circumvent the known weakness. They also suggested that the original construction can be made secure by adjusting the problem parameters. In this work, we develop a number of secret-extraction attacks that are effective against both new approaches in a wide range of problem parameters. In particular, we find multiple ways to recover the 300 -bit secret hidden in a challenge data set published by Bremner, Cheng, and Ji. The important problem of finding an efficient and reliable verification protocol for sampling-based proofs of quantum advantage thus remains open.
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.
Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, whose depth is greater than a critical O (1) threshold, the output distribution can be efficiently sampled by a classical computer. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit’s architecture, on anti-concentration properties, nor do we require Ω(log (n )) circuit depth. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought. Furthermore, we show that the critical depth threshold of our algorithm is tight, and below this threshold there are noisy IQP circuits which are hard to sample from. Thus we demonstrate that noisy IQP circuits exhibit a phase transition in the computational complexity of sampling, as circuit depth is increased.
Recently, quantum computing experiments have for the first time exceeded the capability of classical computers to perform certain computations – a milestone termed "quantum computational advantage." However, verifying the output of the quantum device in these experiments required extremely large classical computations. An exciting next step for demonstrating quantum capability would be to implement tests of quantum computational advantage with efficient classical verification, such that larger system sizes can be tested and verified. One of the first proposals for an efficiently-verifiable test of quantumness consists of hiding a secret classical bitstring inside a circuit of the class IQP, in such a way that samples from the circuit's output distribution are correlated with the secret. The classical hardness of this protocol has been supported by evidence that directly simulating IQP circuits is hard, but the security of the protocol against other (non-simulating) classical attacks has remained an open question. In this work we demonstrate that the protocol is not secure against classical forgery. We describe a classical algorithm that can not only convince the verifier that the (classical) prover is quantum, but can in fact can extract the secret key underlying a given protocol instance. Furthermore, we show that the key extraction algorithm is efficient in practice for problem sizes of hundreds of qubits. Finally, we provide an implementation of the algorithm, and give the secret vector underlying the "$25 challenge" posted online by the authors of the original paper.
Quantum advantage is a demonstration of a computation by a quantum computer that cannot be performed by the best classical computer in a reasonable time. A well-studied approach to demonstrating this on near-term quantum computers is to use random circuit sampling. It has been suggested that a good candidate for demonstrating quantum advantage with random circuit sampling is to use instantaneous quantum polynomial (IQP) circuits. These are quantum circuits where the unitary it implements is diagonal. In this paper, we introduce improved techniques for exactly classically simulating random IQP circuits. We find a simple algorithm to calculate an amplitude of an nnn-qubit IQP circuit with dense random two-qubit interactions in time O(log2nn2n)O(\frac{{log}^{2}n}{n}{2}^{n})O(nlog2n​2n), which for sparse circuits (where each qubit interacts with O(logn)O(logn)O(logn) other qubits) runs in o(2n/poly(n))o({2}^{n}/\mathrm{poly}(n))o(2n/poly(n)) for any given polynomial. Using a more complicated stabilizer decomposition approach we improve the algorithm for dense circuits to $O(\frac{{(logn)}^{4\ensuremath{-}\ensuremath{\beta}}}{{n}^{2\ensuremath{-}\ensuremath{\beta}}}{2}^{n})$ where $\ensuremath{\beta}\ensuremath{\approx}0.396$. We further discuss how our techniques also lead to improved simulation times for IQP circuits on restricted architectures. We benchmarked our main algorithm and found that we can simulate up to 50-qubit circuits in a couple of minutes on a laptop, with 68-qubit sparse circuits taking a couple of hours. We estimate dense 70-qubit circuits are in range for large computing clusters.
Instantaneous Quantum Polynomial-time (IQP) circuits are a candidate for demonstrating near-term quantum advantage, as their sampling task is believed to be classically hard in the ideal theoretical setting under standard complexity-theoretic assumptions. In noisy implementations, however, this hardness can disappear once circuit depth exceeds a noise-dependent critical threshold. We show that qubit connectivity is a key parameter in this transition, since sparse architectures require additional routing to implement long-range interactions, thereby increasing compiled circuit depth. To make this explicit, we present a connectivity-aware analysis of compiled IQP circuits. For a fixed abstract IQP instance, different hardware connectivity graphs yield different compiled depths and thus different effective positions relative to the noisy-IQP simulatability boundary. We quantify this architecture-dependent shift using the compiled depth overhead and the corresponding simulatability margin. We combine analytic depth estimates for sparse geometries, including the two-dimensional grid, with native-gateset-aware compilation experiments across seven hardware-grounded experimental device models derived from publicly available topologies. To compare these device models under a unified empirical framework, we approximate the effective noise level primarily through reported two-qubit gate error rates. This lets us compare how much effective noise sparse and fully connected architectures can tolerate for the same position relative to the noisy-IQP simulatability boundary. Our results show that sparse connectivity requires a lower effective noise level to sustain the same margin relative to the noisy-IQP simulatability boundary, and they provide a quantitative framework for determining when compiled IQP experiments are likely to remain outside, or instead enter, the classically simulatable regime.