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:1309.5675 · Theory of Computing

Interactive proofs for BQP via self-tested graph states

Matthew McKague

Published Jan 1, 2016• 120 citations
arXivHTMLPDF

Abstract

$ \newcommand{\cclass}[1]{\mathsf{#1}} $ Using the measurement-based quantum computation model, we construct interactive proofs with non-communicating quantum provers and a classical verifier. Our construction gives interactive proofs for all languages in $\cclass{BQP}$ with a polynomial number of quantum provers, each of which, in the honest case, performs only a single measurement. In this paper we introduce two main improvements over previous work in self-testing for graph states. Specifically, we derive new error bounds which scale polynomially with the size of the graph compared with exponential dependence on the size of the graph in previous work. We also extend the self-testing error bounds on measurements to a very general set which includes the adaptive measurements used for measurement-based quantum computation as a special case. These improvements allow us to apply graph state self-testing and measurement based quantum computation to build interactive proofs for all languages in $\cclass{BQP}$.

DOI
10.4086/toc.2016.v012a003

Related papers

Interactive proofs for BQP via self-tested graph states (extended abstract)

Matthew McKague

Using the measurement-based quantum computation model, we construct interactive proofs with non-communicating quantum provers and a classical verifier. Our construction gives interactive proofs for all languages in BQP with a polynomial number of quantum provers, each of which, in the honest case, performs only a single measurement. Our techniques use self-tested graph states which allow us to test the provers for honesty, establishing that they hold onto a particular graph state and measure it in specified bases. In this extended abstract we give an overview of the construction and proofs.

arXiv:1311.1534•Nov 6, 2013•2 citations

Interactive Proofs For Quantum Computations

Dorit Aharonov, Michael Ben-Or, Elad Eban +1 more

The widely held belief that BQP strictly contains BPP raises fundamental questions: Upcoming generations of quantum computers might already be too large to be simulated classically. Is it possible to experimentally test that these systems perform as they should, if we cannot efficiently compute predictions for their behavior? Vazirani has asked: If predicting Quantum Mechanical systems requires exponential resources, is QM a falsifiable theory? In cryptographic settings, an untrusted future company wants to sell a quantum computer or perform a delegated quantum computation. Can the customer be convinced of correctness without the ability to compare results to predictions? To answer these questions, we define Quantum Prover Interactive Proofs (QPIP). Whereas in standard Interactive Proofs the prover is computationally unbounded, here our prover is in BQP, representing a quantum computer. The verifier models our current computational capabilities: it is a BPP machine, with access to few qubits. Our main theorem can be roughly stated as: "Any language in BQP has a QPIP, and moreover, a fault tolerant one". We provide two proofs. The simpler one uses a new (possibly of independent interest) quantum authentication scheme (QAS) based on random Clifford elements. This QPIP however, is not fault tolerant. Our second protocol uses polynomial codes QAS due to BCGHS, combined with quantum fault tolerance and multiparty quantum computation techniques. A slight modification of our constructions makes the protocol "blind": the quantum computation and input are unknown to the prover. After we have derived the results, we have learned that Broadbent at al. have independently derived "universal blind quantum computation" using completely different methods. Their construction implicitly implies similar implications.

arXiv:0810.5375•International Conference on Supercomputing•Oct 30, 2008•243 citations

How to Verify a Quantum Computation

Anne Broadbent

We give a new theoretical solution to a leading-edge experimental challenge, namely to the verification of quantum computations in the regime of high computational complexity. Our results are given in the language of quantum interactive proof systems. Specifically, we show that any language in $\mathsf{BQP}$ has a quantum interactive proof system with a polynomial-time classical verifier (who can also prepare random single-qubit pure states), and a quantum polynomial-time prover. Here, soundness is unconditional—i.e., it holds even for computationally unbounded provers. Compared to prior work achieving similar results, our technique does not require the encoding of the input or of the computation; instead, we rely on encryption of the input (together with a method to perform computations on encrypted inputs), and show that the random choice between three types of input (defining a computational run, versus two types of test runs) suffices. Because the overhead is very low for each run (it is linear in the size of the circuit), this shows that verification could be achieved at minimal cost compared to performing the computation. As a proof technique, we use a reduction to an entanglement-based protocol; to the best of our knowledge, this is the first time this technique has been used in the context of verification of quantum computations, and it enables a relatively straightforward analysis.

arXiv:1509.09180•Theory of Computing•Jan 1, 2018•95 citations

Interactive Proofs for Synthesizing Quantum States and Unitaries

Gregory Rosenthal, Henry Yuen

Whereas quantum complexity theory has traditionally been concerned with problems arising from classical complexity theory (such as computing boolean functions), it also makes sense to study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations. With this motivation, we define models of interactive proofs for synthesizing quantum states and unitaries, where a polynomial-time quantum verifier interacts with an untrusted quantum prover, and a verifier who accepts also outputs an approximation of the target state (for the state synthesis problem) or the result of the target unitary applied to the input state (for the unitary synthesis problem); furthermore there should exist an "honest" prover which the verifier accepts with probability 1. Our main result is a "state synthesis" analogue of the inclusion $\mathsf{PSPACE} \subseteq \mathsf{IP}$: any sequence of states computable by a polynomial-space quantum algorithm (which may run for exponential time) admits an interactive protocol of the form described above. Leveraging this state synthesis protocol, we also give a unitary synthesis protocol for polynomial space-computable unitaries that act nontrivially on only a polynomial-dimensional subspace. We obtain analogous results in the setting with multiple entangled provers as well.

arXiv:2108.07192•Leibniz international proceedings in informatics•Aug 16, 2021•22 citations

Non-Interactive Quantum Statistical and Perfect Zero-Knowledge

Hirotada Kobayashi

This paper introduces quantum analogues of non-interactive perfect and statistical zero-knowledge proof systems. Similar to the classical cases, it is shown that sharing randomness or entanglement is necessary for non-trivial protocols of non-interactive quantum perfect and statistical zero-knowledge. It is also shown that, with sharing EPR pairs a priori, the class of languages having one-sided bounded error non-interactive quantum perfect zero-knowledge proof systems has a natural complete problem. Non-triviality of such a proof system is based on the fact proved in this paper that the Graph Non-Automorphism problem, which is not known in BQP, can be reduced to our complete problem. Our results may be the first non-trivial quantum zero-knowledge proofs secure even against dishonest quantum verifiers, since our protocols are non-interactive, and thus the zero-knowledge property does not depend on whether the verifier in the protocol is honest or not. A restricted version of our complete problem derives a natural complete problem for BQP.

arXiv:quant-ph/0207158•Jul 29, 2002•3 citations

Post hoc Verification of Quantum Computation

Joseph F. Fitzsimons, Michal Hajdušek, Tomoyuki Morimae

We propose a set of protocols for verifying quantum computing at any time after the computation itself has been performed. We provide two constructions: one requires five entangled provers and a completely classical verifier; the other requires a single prover, a verifier, who is restricted to measuring qubits in the X or Z basis, and one-way quantum communication from the prover to the verifier. These results demonstrate that the verification can be achieved independently from the blindness. We also show that a constant round protocol with a single prover and a completely classical verifier is not possible, unless bounded error quantum polynomial time (BQP) is contained in the third level of the polynomial hierarchy.

arXiv:1512.04375•Physical Review Letters•Jan 22, 2018•121 citations
\newcommand{\cclass}[1]{\mathsf{#1}} Using the measurement-based quantum computation model, we construct interactive proofs with non-communicating quantum provers and a classical verifier. Our construction gives interactive proofs for all languages in \cclassBQP\cclass{BQP}\cclassBQP with a polynomial number of quantum provers, each of which, in the honest case, performs only a single measurement. In this paper we introduce two main improvements over previous work in self-testing for graph states. Specifically, we derive new error bounds which scale polynomially with the size of the graph compared with exponential dependence on the size of the graph in previous work. We also extend the self-testing error bounds on measurements to a very general set which includes the adaptive measurements used for measurement-based quantum computation as a special case. These improvements allow us to apply graph state self-testing and measurement based quantum computation to build interactive proofs for all languages in \cclassBQP\cclass{BQP}\cclassBQP.
Using the measurement-based quantum computation model, we construct interactive proofs with non-communicating quantum provers and a classical verifier. Our construction gives interactive proofs for all languages in BQP with a polynomial number of quantum provers, each of which, in the honest case, performs only a single measurement. Our techniques use self-tested graph states which allow us to test the provers for honesty, establishing that they hold onto a particular graph state and measure it in specified bases. In this extended abstract we give an overview of the construction and proofs.
The widely held belief that BQP strictly contains BPP raises fundamental questions: Upcoming generations of quantum computers might already be too large to be simulated classically. Is it possible to experimentally test that these systems perform as they should, if we cannot efficiently compute predictions for their behavior? Vazirani has asked: If predicting Quantum Mechanical systems requires exponential resources, is QM a falsifiable theory? In cryptographic settings, an untrusted future company wants to sell a quantum computer or perform a delegated quantum computation. Can the customer be convinced of correctness without the ability to compare results to predictions? To answer these questions, we define Quantum Prover Interactive Proofs (QPIP). Whereas in standard Interactive Proofs the prover is computationally unbounded, here our prover is in BQP, representing a quantum computer. The verifier models our current computational capabilities: it is a BPP machine, with access to few qubits. Our main theorem can be roughly stated as: "Any language in BQP has a QPIP, and moreover, a fault tolerant one". We provide two proofs. The simpler one uses a new (possibly of independent interest) quantum authentication scheme (QAS) based on random Clifford elements. This QPIP however, is not fault tolerant. Our second protocol uses polynomial codes QAS due to BCGHS, combined with quantum fault tolerance and multiparty quantum computation techniques. A slight modification of our constructions makes the protocol "blind": the quantum computation and input are unknown to the prover. After we have derived the results, we have learned that Broadbent at al. have independently derived "universal blind quantum computation" using completely different methods. Their construction implicitly implies similar implications.
We give a new theoretical solution to a leading-edge experimental challenge, namely to the verification of quantum computations in the regime of high computational complexity. Our results are given in the language of quantum interactive proof systems. Specifically, we show that any language in BQP\mathsf{BQP}BQP has a quantum interactive proof system with a polynomial-time classical verifier (who can also prepare random single-qubit pure states), and a quantum polynomial-time prover. Here, soundness is unconditional—i.e., it holds even for computationally unbounded provers. Compared to prior work achieving similar results, our technique does not require the encoding of the input or of the computation; instead, we rely on encryption of the input (together with a method to perform computations on encrypted inputs), and show that the random choice between three types of input (defining a computational run, versus two types of test runs) suffices. Because the overhead is very low for each run (it is linear in the size of the circuit), this shows that verification could be achieved at minimal cost compared to performing the computation. As a proof technique, we use a reduction to an entanglement-based protocol; to the best of our knowledge, this is the first time this technique has been used in the context of verification of quantum computations, and it enables a relatively straightforward analysis.
Whereas quantum complexity theory has traditionally been concerned with problems arising from classical complexity theory (such as computing boolean functions), it also makes sense to study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations. With this motivation, we define models of interactive proofs for synthesizing quantum states and unitaries, where a polynomial-time quantum verifier interacts with an untrusted quantum prover, and a verifier who accepts also outputs an approximation of the target state (for the state synthesis problem) or the result of the target unitary applied to the input state (for the unitary synthesis problem); furthermore there should exist an "honest" prover which the verifier accepts with probability 1. Our main result is a "state synthesis" analogue of the inclusion PSPACE⊆IP\mathsf{PSPACE} \subseteq \mathsf{IP}PSPACE⊆IP: any sequence of states computable by a polynomial-space quantum algorithm (which may run for exponential time) admits an interactive protocol of the form described above. Leveraging this state synthesis protocol, we also give a unitary synthesis protocol for polynomial space-computable unitaries that act nontrivially on only a polynomial-dimensional subspace. We obtain analogous results in the setting with multiple entangled provers as well.
This paper introduces quantum analogues of non-interactive perfect and statistical zero-knowledge proof systems. Similar to the classical cases, it is shown that sharing randomness or entanglement is necessary for non-trivial protocols of non-interactive quantum perfect and statistical zero-knowledge. It is also shown that, with sharing EPR pairs a priori, the class of languages having one-sided bounded error non-interactive quantum perfect zero-knowledge proof systems has a natural complete problem. Non-triviality of such a proof system is based on the fact proved in this paper that the Graph Non-Automorphism problem, which is not known in BQP, can be reduced to our complete problem. Our results may be the first non-trivial quantum zero-knowledge proofs secure even against dishonest quantum verifiers, since our protocols are non-interactive, and thus the zero-knowledge property does not depend on whether the verifier in the protocol is honest or not. A restricted version of our complete problem derives a natural complete problem for BQP.
We propose a set of protocols for verifying quantum computing at any time after the computation itself has been performed. We provide two constructions: one requires five entangled provers and a completely classical verifier; the other requires a single prover, a verifier, who is restricted to measuring qubits in the X or Z basis, and one-way quantum communication from the prover to the verifier. These results demonstrate that the verification can be achieved independently from the blindness. We also show that a constant round protocol with a single prover and a completely classical verifier is not possible, unless bounded error quantum polynomial time (BQP) is contained in the third level of the polynomial hierarchy.