Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userClassical Verification of Quantum Computations with Efficient Verifier
346
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, we extend the protocol of classical verification of quantum computations (CVQC) recently proposed by Mahadev to make the verification efficient. Our result is obtained in the following three steps: $bullet$ We show that parallel repetition of Mahadevs protocol has negligible soundness error. This gives the first constant round CVQC protocol with negligible soundness error. In this part, we only assume the quantum hardness of the learning with error (LWE) problem similar to the Mahadevs work. $bullet$ We construct a two-round CVQC protocol in the quantum random oracle model (QROM) where a cryptographic hash function is idealized to be a random function. This is obtained by applying the Fiat-Shamir transform to the parallel repetition version of the Mahadevs protocol. $bullet$ We construct a two-round CVQC protocol with the efficient verifier in the CRS+QRO model where both prover and verifier can access to a (classical) common reference string generated by a trusted third party in addition to quantum access to QRO. Specifically, the verifier can verify a $QTIME(T)$ computation in time $poly(n,log T)$ where $n$ is the security parameter. For proving soundness, we assume that a standard model instantiation of our two-round protocol with a concrete hash function (say, SHA-3) is sound and the existence of post-quantum indistinguishability obfuscation and post-quantum fully homomorphic encryption in addition to the quantum hardness of the LWE problem.
rate research
Read More
In a recent breakthrough, Mahadev constructed a classical verification of quantum computation (CVQC) protocol for a classical client to delegate decision problems in BQP to an untrusted quantum prover under computational assumptions. In this work, we explore further the feasibility of CVQC with the more general sampling problems in BQP and with the desirable blindness property. We contribute affirmative solutions to both as follows. (1) Motivated by the sampling nature of many quantum applications (e.g., quantum algorithms for machine learning and quantum supremacy tasks), we initiate the study of CVQC for quantum sampling problems (denoted by SampBQP). More precisely, in a CVQC protocol for a SampBQP problem, the prover and the verifier are given an input $xin {0,1}^n$ and a quantum circuit $C$, and the goal of the classical client is to learn a sample from the output $z leftarrow C(x)$ up to a small error, from its interaction with an untrusted prover. We demonstrate its feasibility by constructing a four-message CVQC protocol for SampBQP based on the quantum Learning With Error assumption. (2) The blindness of CVQC protocols refers to a property of the protocol where the prover learns nothing, and hence is blind, about the clients input. It is a highly desirable property that has been intensively studied for the delegation of quantum computation. We provide a simple yet powerful generic compiler that transforms any CVQC protocol to a blind one while preserving its completeness and soundness errors as well as the number of rounds. Applying our compiler to (a parallel repetition of) Mahadevs CVQC protocol for BQP and our CVQC protocol for SampBQP yields the first constant-round blind CVQC protocol for BQP and SampBQP respectively, with negligible completeness and soundness errors.
We present a classical interactive protocol that verifies the validity of a quantum witness state for the local Hamiltonian problem. It follows from this protocol that approximating the non-local value of a multi-player one-round game to inverse polynomial precision is QMA-hard. Our work makes an interesting connection between the theory of QMA-completeness and Hamiltonian complexity on one hand and the study of non-local games and Bell inequalities on the other.
Verifying the correct functioning of quantum gates is a crucial step towards reliable quantum information processing, but it becomes an overwhelming challenge as the system size grows due to the dimensionality curse. Recent theoretical breakthroughs show that it is possible to verify various important quantum gates with the optimal sample complexity of $O(1/epsilon)$ using local operations only, where $epsilon$ is the estimation precision. In this work, we propose a variant of quantum gate verification (QGV) which is robust to practical gate imperfections, and experimentally realize efficient QGV on a two-qubit controlled-not gate and a three-qubit Toffoli gate using only local state preparations and measurements. The experimental results show that, by using only 1600 and 2600 measurements on average, we can verify with 95% confidence level that the implemented controlled-not gate and Toffoli gate have fidelities at least 99% and 97%, respectively. Demonstrating the superior low sample complexity and experimental feasibility of QGV, our work promises a solution to the dimensionality curse in verifying large quantum devices in the quantum era.
Quantum state verification provides an efficient approach to characterize the reliability of quantum devices for generating certain target states. The figure of merit of a specific strategy is the estimated infidelity $epsilon$ of the tested state to the target state, given a certain number of performed measurements n. Entangled measurements constitute the globally optimal strategy and achieve the scaling that epsilon is inversely proportional to n. Recent advances show that it is possible to achieve the same scaling simply with non-adaptive local measurements, however, the performance is still worse than the globally optimal bound up to a constant factor. In this work, by introducing classical communication, we experimentally implement an adaptive quantum state verification. The constant-factor is minimized from ~2.5 to 1.5 in this experiment, which means that only 60% measurements are required to achieve a certain value of epsilon compared to optimal non-adaptive local strategy. Our results indicate that classical communication significantly enhances the performance of quantum state verification, and leads to an efficiency that further approaches the globally optimal bound.
This paper is devoted to such a fundamental problem of quantum computing as quantum parallelism. It is well known that quantum parallelism is the basis of the ability of quantum computer to perform in polynomial time computations performed by classical computers for exponential time. Therefore better understanding of quantum parallelism is important both for theoretical and applied research, cf. e.g. David Deutsch cite{DD}. We present a realistic interpretation based on recently developed prequantum classical statistical field theory (PCSFT). In the PCSFT-approach to QM quantum states (mixed as well as pure) are labels of special ensembles of classical fields. Thus e.g. a single (!) ``electron in the pure state $psi$ can be identified with a special `` electron random field, say $Phi_psi(phi).$ Quantum computer operates with such random fields. By one computational step for e.g. a Boolean function $f(x_1,...,x_n)$ the initial random field $Phi_{psi_0}(phi)$ is transformed into the final random field $Phi_{psi_f}(phi)$ ``containing all values of $f.$ This is the objective of quantum computers ability to operate quickly with huge amounts of information -- in fact, with classical random fields.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
