log in  |  register  |  feedback?  |  help  |  web accessibility
PhD Proposal: Classical proofs for quantum computation
Shih-Han Hung
Virtual: https://umd.zoom.us/j/108285777
Monday, April 13, 2020, 3:00-5:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
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

Shih-Han Hung is a graduate student in the Department of Computer Science at the University of Maryland. His research aims to understand the power of quantum computation. He is interested in quantum cryptography, verification of quantum computation and quantum algorithms.

This talk is organized by Tom Hurst