PhD Proposal: Classical proofs for quantum computation

Quantum computers are believed to efficiently solve a range of computational tasks infeasible to classical computers. Recent advances in quantum technology demand practical solutions to the following question: how do we verify a quantum device with only classical interaction? Existing results have shown that based on robust self-testing for quantum correlations or lattice assumptions, a classical machine can certify any polynomial-time bounded quantum computation. Furthermore, the constructions enable tests of quantumness and randomness expansion.In this proposal, I aim to construct practical protocols for device-independent quantum cryptography. In particular, my goals are to improve over the current constructions with respect to round complexity, verifiability and reliability, and to construct new cryptographic schemes for robust outsourcing quantum computation.As a first step, I showed classical verification for any quantum computation can be performed non-interactively and in zero-knowledge. The protocol results from a sequence of significant improvements to the first classical verification protocol of Mahadev. First, I showed that the sampling of randomness can be made instance-independent, and thus can be performed in an offline setup phase. Next, I established a parallel repetition theorem to reduce the soundness error at an optimal rate. Finally, the round complexity can be reduced by Fiat-Shamir transform in the quantum-accessible random oracle model. As a consequence, I gave the first classical non-interactive zero-knowledge for QMA.In the next step, I plan to integrate the aforementioned verification procedure to construct schemes for robust outsourcing quantum computation, including (i) a non-interactive randomness expansion protocol for extracting uniformly random bits of arbitrarily polynomial size, and (ii) a classically verifiable fully homomorphic encryption for quantum circuits. Furthermore, I will study efficient protocols for near-term devices.Examining Committee:

Chair: Dr. Andrew Childs Dept rep: Dr. Michael Hicks Members: Dr. Gorjan Alagic