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

Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games

Finn Holler, Anand Natarajan

quant-phcs.CRSubmitted Sep 29, 2026• Announced Sep 30, 2026• 0 citations
arXivHTMLPDF

Abstract

Computational self-testing gives a classical verifier command over the quantum register of a single computationally bounded prover. We use this framework to construct the first argument system for BQP with quasilinear total resource requirements in the circuit model. Our argument system is based on the learning with errors (LWE) assumption and requires total resources of $O(\mathrm{poly}(λ, \log g)\cdot g)$ for delegating a circuit with $g$ gates, where $λ$ is the LWE security parameter. This is achieved by constructing a new computational self-test for certifying the prover's quantum state and using it to dequantize the efficient verification protocol of Broadbent (ToC 2018). Specifically, this self-test enables the verifiable, random remote state preparation of tensor product states of the single-qubit Clifford observables $σ_X, σ_Y, σ_Z, (σ_Y-σ_X)/\sqrt{2}$ and $(σ_Y+σ_X)/\sqrt{2}$, with constant robustness: the verification error is independent of the number of prepared qubits. This approach was first proposed by Coladangelo et al. (ToC 2024) in the multi-prover setting. We replicate their result in the single-prover setting by applying the compiler proposed by Kalai et al. (STOC 2023)---which turns any nonlocal game into a single-prover argument system---to a modified version of their self-test.

AI Summary

The paper addresses the overhead of classical verification of circuit-model quantum computation with a single computationally bounded prover. It constructs an LWE-based argument for delegating a $g$-gate circuit with total resources $O(g\,\mathrm{poly}(\lambda,\log g))$. This becomes $\widetilde O(g)$ under subexponential LWE hardness against nonuniform quantum adversaries, or $O(g^{1+\varepsilon})$ for every fixed $\varepsilon>0$ under polynomial hardness. Constantly many sequential repetitions give completeness $2/3$ and soundness $1/3$. The construction applies the KLVY nonlocal-game compiler to a modified Clifford rigidity test, then uses the resulting random remote state preparation to replace quantum communication in Broadbent’s verification protocol. The state-preparation guarantee covers tensor products of eigenstates of $X,Y,Z,(Y-X)/\sqrt2,(Y+X)/\sqrt2$, with robustness independent of the number of prepared qubits. The analysis uses approximate representations of an extended Pauli group, an explicitly efficient Gowers–Hatami isometry, and a quantum Fourier transform over that group. A cryptographic dephasing argument makes the prepared state computationally indistinguishable from a classical mixture of the intended state and its complex conjugate, rather than allowing coherent conjugation branches. The guarantee is averaged over random basis assignments, not established separately for every assignment. Security excludes quantum advice, and the protocol is not blind or succinct; its rounds scale with circuit $T$-depth. The unamplified gap is a small, unspecified constant, making the construction impractical as presented. Full certification of entanglement between the simulated provers and extensions to QMA remain open.

No sign of AI-generated textStrong assumptionsPossible error

Error found: The abstract omits that obtaining quasilinear resources in circuit size from its parameterized bound requires sub-exponential quantum hardness of LWE in the paper's instantiation. The verification-theorem remark unjustifiably strengthens adversary-dependent cryptographic security to a single bound and threshold uniform over all efficient provers. Equation eq:bell-twirl is false: a one-sided Pauli twirl depolarizes the acted-on qubit rather than dephasing the two-qubit state in the Bell basis.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
124 pages

Related papers

Verifier-on-a-leash: New schemes for verifiable delegated quantum computation, with quasilinear resources

Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery +1 more

$ $ The problem of reliably certifying the outcome of a computation performed by a quantum device is rapidly gaining relevance. We present two protocols for a classical verifier to verifiably delegate a quantum computation to two non-communicating but entangled quantum provers, with statistical soundness. Our protocols have near-optimal complexity in terms of the total resources employed by the verifier and the honest provers, with the total number of operations of each party, including the number of entangled pairs of qubits required of the honest provers, scaling as $O(g\log g)$ for delegating a circuit of size $g$. This is in contrast to previous protocols, whose overhead in terms of resources employed, while polynomial, is far beyond what is feasible in practice. Our first protocol requires a number of rounds that is linear in the depth of the circuit being delegated, and is blind, meaning neither prover can learn the circuit or its input. The second protocol is not blind, but requires only a constant number of rounds of interaction. Our main technical innovation is an efficient rigidity theorem that allows a verifier to test that two entangled provers perform measurements specified by an arbitrary $m$-qubit tensor product of single-qubit Clifford observables on their respective halves of $m$ shared EPR pairs, with a robustness that is independent of $m$. Our two-prover classical-verifier delegation protocols are obtained by combining this rigidity theorem with a single-prover quantum-verifier protocol for the verifiable delegation of a quantum computation, introduced by Broadbent (Theory of Computing, 2018). ------------------- A conference version of this paper appeared in the Proceedings of the 48th Ann. Internat. Conf. on Theory and Appl. of Cryptographic Techniques (EUROCRYPT 2019).

Theory of Computing•Jan 1, 2024•6 citations

Bounding the Quantum Value of Compiled Nonlocal Games: From CHSH to BQP Verification

Anand Natarajan, Tina Zhang

We present a step towards the goal of producing a general cryptographic ’compilation’ procedure which can translate any entangled nonlocal game into a single-prover interactive protocol while preserving quantum completeness and soundness, using cryptography to simulate the separation between the provers. A candidate for such a procedure was introduced by Kalai et al. (STOC ’23), who defined a black-box cryptographic compilation procedure that applies to any nonlocal game and showed that it preserves classical value. In this work, we make progress towards a full understanding of the quantum value of the single-prover protocols that result from applying the Kalai et al. compilation procedure to entangled games. For the special case of CHSH, we prove that the Tsirelson bound holds under the compilation procedure introduced by Kalai et al., and we also recover a strong version of the ’rigidity’ property that makes CHSH so useful. As an application, we give a single-prover cryptographically sound classical verification protocol for BQP, and we prove its soundness using our CHSH rigidity analysis. Our protocol replicates the functionality of Mahadev’s protocol (FOCS ’18) but with two advantages: (1) the protocol is conceptually intuitive and requires fewer bespoke ingredients, and the soundness analysis is simpler and directly follows the analysis of the nonlocal case, and (2) the soundness analysis does not explicitly use the assumption of a TCF or an adaptive hardcore bit, and only requires QFHE as a black box (though currently the only known constructions of QFHE use TCFs).

arXiv:2303.01545•Annual Symposium on Foundations of Computer Science•Nov 6, 2023•34 citations

Classical verification of quantum depth

Nai-Hui Chia, Hung, Shih-Han

We present two protocols for classical verification of quantum depth. Our protocols allow a purely classical verifier to distinguish devices with different quantum circuit depths even in the presence of classical computation. We show that a device with quantum circuit depth at most d will be rejected by the verifier even if the prover applies additional polynomial-time classical computation to cheat. On the other hand, the verifier accepts a device which has quantum circuit depth d' for some d'>d. In our first protocol, we introduce an additional untrusted quantum machine which shares entanglements with the target machine. Applying a robust self-test, our first protocol certifies the depth of the target machine with information theoretic security and nearly optimal separation. The protocol relies on the oracle separation problem for quantum depth by Chia, Chung and Lai [STOC 2020] and a transformation from an oracle separation problem to a two-player non-local game. Our second protocol certifies the quantum depth of a single device based on quantum hardness of learning with errors. The protocol relies on the noisy trapdoor claw-free function family and the idea of pointer chasing to force the prover to keep quantum coherence until all preceding message exchanges are completed. To our knowledge, we give the first constructions for distinguishing hybrid quantum-classical computers with different circuit depths in unrelativized models.

arXiv:2205.04656•May 10, 2022•13 citations

Robust verification of quantum computation

Alexandru Gheorghiu

Quantum computers promise to offer a considerable speed-up in solving certain problems, compared to the best classical algorithms. In many instances, the gap between quantum and classical running times is conjectured to be exponential. While this is great news for those applications where quantum computers would provide such an advantage, it also raises a significant challenge: how can classical computers verify the correctness of quantum computations? In attempting to answer this question, a number of protocols have been developed in which a classical client (referred to as verifier) can interact with one or more quantum servers (referred to as provers) in order to certify the correctness of a quantum computation performed by the server(s). These protocols are of one of two types: either there are multiple non-communicating provers, sharing entanglement, and the verifier is completely classical; or, there is a single prover and the classical verifier has a device for preparing or measuring quantum states. The latter type of protocols are, arguably, more relevant to near term quantum computers, since having multiple quantum computers that share a large amount of entanglement is, from a technological standpoint, extremely challenging. Before the realisation of practical single-prover protocols, a number of challenges need to be addressed: how robust are these protocols to noise on the verifier's device? Can the protocols be made fault-tolerant without significantly increasing the requirements of the verifier? How do we know that the verifier's device is operating correctly? Could this device be eliminated completely, thus having a protocol with a fully classical verifier and a single quantum prover? Our work attempts to provide answers to these questions. First, we consider a single-prover verification protocol developed by Fitzsimons and Kashefi and show that this protocol is indeed robust with respect to deviations on the quantum state prepared by the verifier. We show that this is true even if those deviations are the result of a correlation with the prover's system. We then use this result to give a verification protocol which is device- independent. The protocol consists of a verifier with a measurement device and a single prover. Device-independence means that the verifier need not trust the measurement device (nor the prover) which can be assumed to be fully malicious (though not communicating with the prover). A key element in realising this protocol is a robust technique of Reichardt, Unger and Vazirani for testing, using non-local correlations, that two untrusted devices share a large number of entangled states. This technique is referred to as rigidity of non-local correlations. Our second result is to prove a rigidity result for a type of quantum correlations known as steering correlations. To do this, we first show that steering correlations can be used in order to certify maximally entangled states, in a setting in which each test is independent of the previous one. We also show that the fidelity with which we characterise the state, in this specific test, is optimal. We then improve the previous result by removing the independence assumption. This then leads to our desired rigidity result. We make use of it, in a similar fashion to the device-independent case, in order to give a verification protocol that is one-sided device-independent. The importance of this application is to show how different trust assumptions affect the efficiency of the protocol. Next, we describe a protocol for fault-tolerantly verifying quantum computations, with minimal "quantum requirements" for the verifier. Specifically, the verifier only requires a device for measuring single-qubit states. Both this device, and the prover's operations are assumed to be prone to errors. We show that under standard assumptions about the error model, it is possible to achieve verification of quantum computation using fault-tolerant principles. As a proof of principle, and to better illustrate the inner workings of the protocol, we describe a toy implementation of the protocol in a quantum simulator, and present the results we obtained, when running it for a small computation. Finally, we explore the possibility of having a verification protocol, with a classical verifier and a single prover, such that the prover is blind with respect to the verifier's computation. We give evidence that this is not possible. In fact, our result is only concerned with blind quantum computation with a classical client, and uses complexity theoretic results to argue why it is improbable for such a protocol to exist. We then use these complexity theoretic techniques to show that a client, with the ability to prepare and send quantum states to a quantum server, would not be able to delegate arbitrary NP problems to that server. In other words, even a client with quantum capabilities cannot exploit those capabilities to delegate the computation of NP problems, while keeping the input, to that computation, private. This is again true, provided certain complexity theoretic conjectures are true.

•Nov 29, 2018•0 citations

Classical Verifier Position Verification from Non-Local Games

Wen Yu Kon, Fatih Kaleoglu, Kaushik Chakraborty

Secure position verification certifies that a remote prover occupies a claimed location, a task that is provably impossible with classical resources alone against colluding adversaries. Most existing quantum position verification schemes require transmitting quantum states between verifiers and provers, and the resulting photon loss makes long-distance verification impractical. Classical verifier position verification (CVPV) schemes with classical verifier-prover communication exist, but rely on complex quantum processes that generate certifiable randomness, placing them outside the reach of near-term hardware. Here we introduce a general compiler that maps any complete-support non-local game with the required quantum advantage into a multi-prover CVPV protocol. This addresses both limitations, with entirely classical verifier-prover communication and all quantum resources confined to shared entanglement and local measurements on the prover devices. Instantiating with the CHSH game enables near-term implementation on existing experimental platforms. We prove finite-size security in the quantum random oracle model for both simultaneous verification of multiple provers and verification of a single prover with multiple prover devices. Notably, security in the multi-prover setting is governed not by the certified randomness of the joint provers' outputs, but by certified blind local randomness that depends critically on the spatial arrangement of provers and verifiers.

quant-pharXiv:2609.38441•Oct 1, 2026•0 citations

Self-testing of a single quantum device under computational assumptions

Tony Metger, Thomas Vidick

Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.

•Jan 1, 2021•11 citations
Computational self-testing gives a classical verifier command over the quantum register of a single computationally bounded prover. We use this framework to construct the first argument system for BQP with quasilinear total resource requirements in the circuit model. Our argument system is based on the learning with errors (LWE) assumption and requires total resources of O(poly(λ,log⁡g)⋅g)O(\mathrm{poly}(λ, \log g)\cdot g)O(poly(λ,logg)⋅g) for delegating a circuit with ggg gates, where λλλ is the LWE security parameter. This is achieved by constructing a new computational self-test for certifying the prover's quantum state and using it to dequantize the efficient verification protocol of Broadbent (ToC 2018). Specifically, this self-test enables the verifiable, random remote state preparation of tensor product states of the single-qubit Clifford observables σX,σY,σZ,(σY−σX)/2σ_X, σ_Y, σ_Z, (σ_Y-σ_X)/\sqrt{2}σX​,σY​,σZ​,(σY​−σX​)/2​ and (σY+σX)/2(σ_Y+σ_X)/\sqrt{2}(σY​+σX​)/2​, with constant robustness: the verification error is independent of the number of prepared qubits. This approach was first proposed by Coladangelo et al. (ToC 2024) in the multi-prover setting. We replicate their result in the single-prover setting by applying the compiler proposed by Kalai et al. (STOC 2023)---which turns any nonlocal game into a single-prover argument system---to a modified version of their self-test.
The paper addresses the overhead of classical verification of circuit-model quantum computation with a single computationally bounded prover. It constructs an LWE-based argument for delegating a ggg-gate circuit with total resources O(g poly(λ,log⁡g))O(g\,\mathrm{poly}(\lambda,\log g))O(gpoly(λ,logg)). This becomes O~(g)\widetilde O(g)O(g) under subexponential LWE hardness against nonuniform quantum adversaries, or O(g1+ε)O(g^{1+\varepsilon})O(g1+ε) for every fixed ε>0\varepsilon>0ε>0 under polynomial hardness. Constantly many sequential repetitions give completeness 2/32/32/3 and soundness 1/31/31/3.
The construction applies the KLVY nonlocal-game compiler to a modified Clifford rigidity test, then uses the resulting random remote state preparation to replace quantum communication in Broadbent’s verification protocol. The state-preparation guarantee covers tensor products of eigenstates of X,Y,Z,(Y−X)/2,(Y+X)/2X,Y,Z,(Y-X)/\sqrt2,(Y+X)/\sqrt2X,Y,Z,(Y−X)/2​,(Y+X)/2​, with robustness independent of the number of prepared qubits. The analysis uses approximate representations of an extended Pauli group, an explicitly efficient Gowers–Hatami isometry, and a quantum Fourier transform over that group. A cryptographic dephasing argument makes the prepared state computationally indistinguishable from a classical mixture of the intended state and its complex conjugate, rather than allowing coherent conjugation branches.
The guarantee is averaged over random basis assignments, not established separately for every assignment. Security excludes quantum advice, and the protocol is not blind or succinct; its rounds scale with circuit TTT-depth. The unamplified gap is a small, unspecified constant, making the construction impractical as presented. Full certification of entanglement between the simulated provers and extensions to QMA remain open.
$ $ The problem of reliably certifying the outcome of a computation performed by a quantum device is rapidly gaining relevance. We present two protocols for a classical verifier to verifiably delegate a quantum computation to two non-communicating but entangled quantum provers, with statistical soundness. Our protocols have near-optimal complexity in terms of the total resources employed by the verifier and the honest provers, with the total number of operations of each party, including the number of entangled pairs of qubits required of the honest provers, scaling as O(glog⁡g)O(g\log g)O(glogg) for delegating a circuit of size ggg. This is in contrast to previous protocols, whose overhead in terms of resources employed, while polynomial, is far beyond what is feasible in practice. Our first protocol requires a number of rounds that is linear in the depth of the circuit being delegated, and is blind, meaning neither prover can learn the circuit or its input. The second protocol is not blind, but requires only a constant number of rounds of interaction. Our main technical innovation is an efficient rigidity theorem that allows a verifier to test that two entangled provers perform measurements specified by an arbitrary mmm-qubit tensor product of single-qubit Clifford observables on their respective halves of mmm shared EPR pairs, with a robustness that is independent of mmm. Our two-prover classical-verifier delegation protocols are obtained by combining this rigidity theorem with a single-prover quantum-verifier protocol for the verifiable delegation of a quantum computation, introduced by Broadbent (Theory of Computing, 2018). ------------------- A conference version of this paper appeared in the Proceedings of the 48th Ann. Internat. Conf. on Theory and Appl. of Cryptographic Techniques (EUROCRYPT 2019).
We present a step towards the goal of producing a general cryptographic ’compilation’ procedure which can translate any entangled nonlocal game into a single-prover interactive protocol while preserving quantum completeness and soundness, using cryptography to simulate the separation between the provers. A candidate for such a procedure was introduced by Kalai et al. (STOC ’23), who defined a black-box cryptographic compilation procedure that applies to any nonlocal game and showed that it preserves classical value. In this work, we make progress towards a full understanding of the quantum value of the single-prover protocols that result from applying the Kalai et al. compilation procedure to entangled games. For the special case of CHSH, we prove that the Tsirelson bound holds under the compilation procedure introduced by Kalai et al., and we also recover a strong version of the ’rigidity’ property that makes CHSH so useful. As an application, we give a single-prover cryptographically sound classical verification protocol for BQP, and we prove its soundness using our CHSH rigidity analysis. Our protocol replicates the functionality of Mahadev’s protocol (FOCS ’18) but with two advantages: (1) the protocol is conceptually intuitive and requires fewer bespoke ingredients, and the soundness analysis is simpler and directly follows the analysis of the nonlocal case, and (2) the soundness analysis does not explicitly use the assumption of a TCF or an adaptive hardcore bit, and only requires QFHE as a black box (though currently the only known constructions of QFHE use TCFs).
We present two protocols for classical verification of quantum depth. Our protocols allow a purely classical verifier to distinguish devices with different quantum circuit depths even in the presence of classical computation. We show that a device with quantum circuit depth at most d will be rejected by the verifier even if the prover applies additional polynomial-time classical computation to cheat. On the other hand, the verifier accepts a device which has quantum circuit depth d' for some d'>d. In our first protocol, we introduce an additional untrusted quantum machine which shares entanglements with the target machine. Applying a robust self-test, our first protocol certifies the depth of the target machine with information theoretic security and nearly optimal separation. The protocol relies on the oracle separation problem for quantum depth by Chia, Chung and Lai [STOC 2020] and a transformation from an oracle separation problem to a two-player non-local game. Our second protocol certifies the quantum depth of a single device based on quantum hardness of learning with errors. The protocol relies on the noisy trapdoor claw-free function family and the idea of pointer chasing to force the prover to keep quantum coherence until all preceding message exchanges are completed. To our knowledge, we give the first constructions for distinguishing hybrid quantum-classical computers with different circuit depths in unrelativized models.
Quantum computers promise to offer a considerable speed-up in solving certain problems, compared to the best classical algorithms. In many instances, the gap between quantum and classical running times is conjectured to be exponential. While this is great news for those applications where quantum computers would provide such an advantage, it also raises a significant challenge: how can classical computers verify the correctness of quantum computations? In attempting to answer this question, a number of protocols have been developed in which a classical client (referred to as verifier) can interact with one or more quantum servers (referred to as provers) in order to certify the correctness of a quantum computation performed by the server(s). These protocols are of one of two types: either there are multiple non-communicating provers, sharing entanglement, and the verifier is completely classical; or, there is a single prover and the classical verifier has a device for preparing or measuring quantum states. The latter type of protocols are, arguably, more relevant to near term quantum computers, since having multiple quantum computers that share a large amount of entanglement is, from a technological standpoint, extremely challenging. Before the realisation of practical single-prover protocols, a number of challenges need to be addressed: how robust are these protocols to noise on the verifier's device? Can the protocols be made fault-tolerant without significantly increasing the requirements of the verifier? How do we know that the verifier's device is operating correctly? Could this device be eliminated completely, thus having a protocol with a fully classical verifier and a single quantum prover? Our work attempts to provide answers to these questions. First, we consider a single-prover verification protocol developed by Fitzsimons and Kashefi and show that this protocol is indeed robust with respect to deviations on the quantum state prepared by the verifier. We show that this is true even if those deviations are the result of a correlation with the prover's system. We then use this result to give a verification protocol which is device- independent. The protocol consists of a verifier with a measurement device and a single prover. Device-independence means that the verifier need not trust the measurement device (nor the prover) which can be assumed to be fully malicious (though not communicating with the prover). A key element in realising this protocol is a robust technique of Reichardt, Unger and Vazirani for testing, using non-local correlations, that two untrusted devices share a large number of entangled states. This technique is referred to as rigidity of non-local correlations. Our second result is to prove a rigidity result for a type of quantum correlations known as steering correlations. To do this, we first show that steering correlations can be used in order to certify maximally entangled states, in a setting in which each test is independent of the previous one. We also show that the fidelity with which we characterise the state, in this specific test, is optimal. We then improve the previous result by removing the independence assumption. This then leads to our desired rigidity result. We make use of it, in a similar fashion to the device-independent case, in order to give a verification protocol that is one-sided device-independent. The importance of this application is to show how different trust assumptions affect the efficiency of the protocol. Next, we describe a protocol for fault-tolerantly verifying quantum computations, with minimal "quantum requirements" for the verifier. Specifically, the verifier only requires a device for measuring single-qubit states. Both this device, and the prover's operations are assumed to be prone to errors. We show that under standard assumptions about the error model, it is possible to achieve verification of quantum computation using fault-tolerant principles. As a proof of principle, and to better illustrate the inner workings of the protocol, we describe a toy implementation of the protocol in a quantum simulator, and present the results we obtained, when running it for a small computation. Finally, we explore the possibility of having a verification protocol, with a classical verifier and a single prover, such that the prover is blind with respect to the verifier's computation. We give evidence that this is not possible. In fact, our result is only concerned with blind quantum computation with a classical client, and uses complexity theoretic results to argue why it is improbable for such a protocol to exist. We then use these complexity theoretic techniques to show that a client, with the ability to prepare and send quantum states to a quantum server, would not be able to delegate arbitrary NP problems to that server. In other words, even a client with quantum capabilities cannot exploit those capabilities to delegate the computation of NP problems, while keeping the input, to that computation, private. This is again true, provided certain complexity theoretic conjectures are true.
Secure position verification certifies that a remote prover occupies a claimed location, a task that is provably impossible with classical resources alone against colluding adversaries. Most existing quantum position verification schemes require transmitting quantum states between verifiers and provers, and the resulting photon loss makes long-distance verification impractical. Classical verifier position verification (CVPV) schemes with classical verifier-prover communication exist, but rely on complex quantum processes that generate certifiable randomness, placing them outside the reach of near-term hardware. Here we introduce a general compiler that maps any complete-support non-local game with the required quantum advantage into a multi-prover CVPV protocol. This addresses both limitations, with entirely classical verifier-prover communication and all quantum resources confined to shared entanglement and local measurements on the prover devices. Instantiating with the CHSH game enables near-term implementation on existing experimental platforms. We prove finite-size security in the quantum random oracle model for both simultaneous verification of multiple provers and verification of a single prover with multiple prover devices. Notably, security in the multi-prover setting is governed not by the certified randomness of the joint provers' outputs, but by certified blind local randomness that depends critically on the spatial arrangement of provers and verifiers.
Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.