CRII: AF: Theoretical Problems in Quantum Computation

University Of Maryland, College Park, College Park MD

Investigators

Abstract

In anticipation of quantum computers being utilized in the near future, this project seeks to find quantum advantages in machine-learning-like tasks that are ubiquitous in our daily life. Future quantum computers will take advantage of entanglement, a quantum property, that digital computers do not use. It is important to understand the essential role of entanglement in the computational power of quantum computers to be able to use it efficiently. This project consists of two sets of questions that touch upon central topics in quantum information (e.g., entanglement and its impact on complexity theory) and novel topics such as property testing. The first part of the project investigates the possibility of designing fast quantum algorithms for property testing of unknown classical distributions and quantum states, a well-motivated topic related to statistics, data analysis, and machine learning. The project aims to integrate techniques from classical property testing, quantum tomography, quantum walks, and so on. The second part of the project investigates the computational power of the absence of entanglement in the context of quantum Merlin-Arthur protocols with two provers (QMA(2)). It is a well-motivated problem due to its connection to the separability problem within quantum information as well as the Unique Games Conjecture in the field of approximation algorithm. Specific objectives include the study of (1) the k-extendible states and de Finetti theorems for the separability problem and (2) non-trivial error reduction schemes of QMA(2). The techniques used are primarily inspired by ideas from the sum-of-squares techniques in optimization, weak measurements and approximation theory. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.