QuICS - Dissertation Defense

Tue, Jun 1, 2021 10:00 am - 12:00 pm


Title: Applications and verification of quantum computers 
Speaker: Shih-Han Hung (QuICS)
Time: Tuesday, June 1, 2021 - 10:00am
Location: Virtual Via Zoom: https://umd.zoom.us/j/95958136789?pwd=dy83YzZOeVova0NvL3pHeWVDNkVxQT09

Quantum computing devices can solve problems that are infeasible for classical computers. While rigorously proving speedups over existing classical algorithms demonstrates the usefulness of quantum computers, analyzing the limits on efficient processes for computational tasks allows us to better understand the power of quantum computation. Indeed, hard problems for quantum computers also enable useful cryptographic applications. In this dissertation, we aim to understand the limits on efficient quantum computation and base applications on hard problems for quantum computers. We consider models in which a classical machine can leverage the power of a quantum device, which may be affected by noise or behave adversarially. We present protocols and tools for detecting errors in a quantum machine and estimate how serious the deviation is. We construct a non-interactive protocol that enables a purely classical party to delegate any quantum computation to an untrusted quantum prover. In the setting of error-prone quantum hardware, we employ formal methods to construct a logic system for reasoning about the robustness of a quantum algorithm design. We also study the limits of ideal quantum computers for computational tasks and give asymptotically optimal algorithms. In particular, we give quantum algorithms which provide speedups for the polynomial interpolation problem and show their optimality. Finally, we study the performance of quantum algorithms that learn properties of a matrix using queries that return its action on an input vector, and show that for various linear algebra problems, there is no quantum speedup, while for some problems, exponential speedups can be achieved.

Upcoming Events

24 Jun
Physics and Public Policy: Victor Yakovenko
Date Thu, Jun 24, 2021 9:00 am - 10:00 am
7 Sep
Physics Colloquium
Tue, Sep 7, 2021 4:00 pm - 5:00 pm
14 Sep
Physics Colloquium
Tue, Sep 14, 2021 4:00 pm - 5:00 pm
21 Sep
Physics Colloquium
Tue, Sep 21, 2021 4:00 pm - 5:00 pm
28 Sep
Physics Colloquium
Tue, Sep 28, 2021 4:00 pm - 5:00 pm