Quantum Algorithms for Machine Learning, Optimization, and Simulation
Abstract
Quantum computation has remained a theoretical possibility for many years. Recent advances in hardware suggest that quantum computing devices will soon exist that can carry out small-scale quantum algorithms. It is therefore of central importance to assess the potential impact of near-term quantum computers on real problems of interest. This proposal covers three broad thrust areas with the aim to design and analyze quantum machine learning, optimization, and simulation algorithms with the emphasis on nearterm applications. The first thrust area covers hybrid quantum-classical machine learning algorithms with a quantum enhanced feature space. Such algorithms employ a small quantum computer to estimate a kernel function which is used in the enveloping classical kernel-based classifier. This framework is aimed at avoiding the use of quantum RAM which may be problematic to realize in the near term. It is also proposed to study simple toy problems of learning and testing Boolean functions. This approach aims at developing new mathematical tools for understanding quantum and classical complexity of learning problems as well as developing new quantum algorithms centered around the Clifford hierarchy. Classical optimization algorithms are ubiquitously used in a variety of applications. Understanding the advantages and limitations of quantum algorithms for optimization is therefore of paramount importance. This proposal aims at studying hybrid algorithms for Linear Programming and analyzing the computational cost of obtaining a classical description of the problem solution when QRAM is not available. The secondary goal in this thrust is to revisit QAOA-type optimization algorithms and explore whether their computational power can be enhanced using the technique of correlation rounding and variable elimination described in the proposal. One of the most compelling applications for quantum computers is Richard FeynmanÕs idea of simulating quantum systems with many degrees of freedom. Such systems are found across the physical sciences. It is proposed to investigate VQE-type quantum simulation algorithms tailored to near-term quantum devices and whether their computational power can be enhanced by employing embedding methods and adaptive variational circuits with intermediate measurements. While the worst-case complexity of quantum simulation problems pertaining to the ground state properties is well understood, much less is known about the hardness of finite-temperature simulations. To gain new insights in this area, this proposal aims at studying the problem of approximating partition functions of local quantum Hamiltonians and characterizing its hardness in terms of existing complexity classes.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 03, 2020
- Source ID
- W911NF2010014
Entities
People
- Andrew W. Cross
Organizations
- Army Contracting Command
- International Business Machines Corporation (Armonk, NY)
- National Security Agency