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:1912.05547 · Quantum

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

Gregory D. Kahanamoku–Meyer

Published Sep 11, 2023• 7 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2023-09-11-1107

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

Achieving quantum supremacy with sparse and noisy commuting quantum computations

Michael J. Bremner, Ashley Montanaro, Dan J. Shepherd

The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(sqrt(n) log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is sufficiently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.

arXiv:1610.01808•Quantum•Apr 25, 2017•191 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•0 citations

Anti-Forging Quantum Data: Cryptographic Verification of Quantum Computational Power

Man‐Hong Yung, Bin Cheng

Quantum cloud computing is emerging as a popular model for users to experience the power of quantum computing through the internet, enabling quantum computing as a service. The question is, when the scale of the computational problems becomes out of reach of classical computers, how can users be sure that the output strings sent by the server are really from a quantum hardware? In 2008, Shepherd and Bremner proposed a cryptographic verification protocol based on a simplified circuit model called IQP (instantaneous quantum polynomial-time), which can potentially be applied to most existing quantum cloud platforms. However, the Shepherd-Bremner protocol has recently been shown to be insecure by Kahanamoku-Meyer. Here we present an extended model of IQP-based cryptographic verification protocol, where the Shepherd-Bremner construction can be regarded as a special case. This protocol not only can avoid the attack by Kahanamoku-Meyer but also provide several additional security measures for anti-forging quantum data. In particular, our protocol admits a simultaneous encoding of multiple secret strings, strengthening significantly the hardness for classical hacking. Furthermore, we provide methods for estimating the correlation functions associated with the secret strings, which are the key elements in our verification protocol.

arXiv:2005.01510•May 4, 2020•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

Anti-Forging Quantum Data: Cryptographic Verification of Quantum Cloud Computing

Man‐Hong Yung, Bin Cheng

Quantum cloud computing is emerging as a popular model for users to experience the power of quantum computing through the internet, enabling quantum computing as a service (QCaaS). The question is, when the scale of the computational problems becomes out of reach of classical computers, how can users be sure that the output strings sent by the server are really from a quantum hardware? In 2008, Shepherd and Bremner proposed a cryptographic verification protocol based on a simplified circuit model called IQP (instantaneous quantum polynomial-time), which can potentially be applied to most existing quantum cloud platforms. However, the Shepherd-Bremner protocol has recently been shown to be insecure by Kahanamoku-Meyer. Here we present a generalized model of cryptographic verification protocol, where the Shepherd-Bremner model can be regarded as a special case. This protocol not only can avoid the attack by Kahanamoku-Meyer but also provide several additional security measures for anti-forging quantum data. In particular, our protocol admits a simultaneous encoding of multiple secret strings, strengthening significantly the hardness for classical hacking. Furthermore, we provide methods for estimating the correlation functions associated with the secret strings, which are the key elements in our verification protocol.

•May 4, 2020•2 citations
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 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.
The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(sqrt(n) log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is sufficiently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.
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.
Quantum cloud computing is emerging as a popular model for users to experience the power of quantum computing through the internet, enabling quantum computing as a service. The question is, when the scale of the computational problems becomes out of reach of classical computers, how can users be sure that the output strings sent by the server are really from a quantum hardware? In 2008, Shepherd and Bremner proposed a cryptographic verification protocol based on a simplified circuit model called IQP (instantaneous quantum polynomial-time), which can potentially be applied to most existing quantum cloud platforms. However, the Shepherd-Bremner protocol has recently been shown to be insecure by Kahanamoku-Meyer. Here we present an extended model of IQP-based cryptographic verification protocol, where the Shepherd-Bremner construction can be regarded as a special case. This protocol not only can avoid the attack by Kahanamoku-Meyer but also provide several additional security measures for anti-forging quantum data. In particular, our protocol admits a simultaneous encoding of multiple secret strings, strengthening significantly the hardness for classical hacking. Furthermore, we provide methods for estimating the correlation functions associated with the secret strings, which are the key elements in our verification protocol.
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.
Quantum cloud computing is emerging as a popular model for users to experience the power of quantum computing through the internet, enabling quantum computing as a service (QCaaS). The question is, when the scale of the computational problems becomes out of reach of classical computers, how can users be sure that the output strings sent by the server are really from a quantum hardware? In 2008, Shepherd and Bremner proposed a cryptographic verification protocol based on a simplified circuit model called IQP (instantaneous quantum polynomial-time), which can potentially be applied to most existing quantum cloud platforms. However, the Shepherd-Bremner protocol has recently been shown to be insecure by Kahanamoku-Meyer. Here we present a generalized model of cryptographic verification protocol, where the Shepherd-Bremner model can be regarded as a special case. This protocol not only can avoid the attack by Kahanamoku-Meyer but also provide several additional security measures for anti-forging quantum data. In particular, our protocol admits a simultaneous encoding of multiple secret strings, strengthening significantly the hardness for classical hacking. Furthermore, we provide methods for estimating the correlation functions associated with the secret strings, which are the key elements in our verification protocol.