Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInteractive Proofs For Quantum Computations
116
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
The widely held belief that BQP strictly contains BPP raises fundamental questions: if we cannot efficiently compute predictions for the behavior of quantum systems, how can we test their behavior? In other words, is quantum mechanics falsifiable? In cryptographic settings, how can a customer of a future untrusted quantum computing company be convinced of the correctness of its quantum computations? To provide answers to 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 only a few qubits. Our main theorem states, roughly: Any language in BQP has a QPIP, which also hides the computation from the prover. We provide two proofs, one based on a quantum authentication scheme (QAS) relying on random Clifford rotations and the other based on a QAS which uses polynomial codes (BOCG+ 06), combined with secure multiparty computation methods. This is the journal version of work reported in 2008 (ABOE08) and presented in ICS 2010; here we have completed the details and made the proofs rigorous. Some of the proofs required major modifications and corrections. Notably, the claim that the polynomial QPIP is fault tolerant was removed. Similar results (with different protocols) were reported independently around the same time of the original version in BFK08. The initial independent works (ABOE08, BFK08) ignited a long line of research of blind verifiable quantum computation, which we survey here, along with connections to various cryptographic problems. Importantly, the problems of making the results fault tolerant as well as removing the need for quantum communication altogether remain open.
We present a protocol that transforms any quantum multi-prover interactive proof into a nonlocal game in which questions consist of logarithmic number of bits and answers of constant number of bits. As a corollary, this proves that the promise problem corresponding to the approximation of the nonlocal value to inverse polynomial accuracy is complete for QMIP*, and therefore NEXP-hard. This establishes that nonlocal games are provably harder than classical games without any complexity theory assumptions. Our result also indicates that gap amplification for nonlocal games may be impossible in general and provides a negative evidence for the possibility of the gap amplification approach to the multi-prover variant of the quantum PCP conjecture.
Multi Prover Interactive Proof systems (MIPs)were first presented in a cryptographic context, but ever since they were used in various fields. Understanding the power of MIPs in the quantum context raises many open problems, as there are several interesting models to consider. For example, one can study the question when the provers share entanglement or not, and the communication between the verifier and the provers is quantum or classical. While there are several partial results on the subject, so far no one presented an efficient scheme for recognizing NEXP (or NP with logarithmic communication), except for [KM03], in the case there is no entanglement (and of course no communication between the provers). We introduce another variant of Quantum MIP, where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case - we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap.
We identify a formal connection between physical problems related to the detection of separable (unentangled) quantum states and complexity classes in theoretical computer science. In particular, we show that to nearly every quantum interactive proof complexity class (including BQP, QMA, QMA(2), and QSZK), there corresponds a natural separability testing problem that is complete for that class. Of particular interest is the fact that the problem of determining whether an isometry can be made to produce a separable state is either QMA-complete or QMA(2)-complete, depending upon whether the distance between quantum states is measured by the one-way LOCC norm or the trace norm. We obtain strong hardness results by proving that for each n-qubit maximally entangled state there exists a fixed one-way LOCC measurement that distinguishes it from any separable state with error probability that decays exponentially in n.
We describe a cohomological framework for measurement based quantum computation, in which symmetry plays a central role. Therein, the essential information about the computational output is contained in topological invariants, namely elements of two cohomology groups. One of those invariants applies to the deterministic case, and the other to the general probabilistic case. The same invariants also witness quantumness in the form of contextuality. In result, they give rise to fundamental algebraic structures underlying quantum computation.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
