Quantum Algorithms for Algebra and Discrete Optimization
Abstract
Quantum computation has made tremendous progress since the discovery of Shor s algorithm, both as a field of scientific research and as a rapidly developing area of technology. However, we still have only a limited understanding of the class of computational problems for which quantum computers dramatically outperform classical ones. In this proposal, we outline a research project to advance our knowledge in this important field, primarily through the development ofnew quantum algorithms. We propose high-risk, high-reward research with the primary goal of discovering new exponential quantum speedups for computational problems of practical relevance. We will assume a large-scale, fault-tolerant platform, and primarily concern ourselves with the asymptotic regime. Our project will consist of three main topic areas: 1.) Polynomial systems. Systems of polynomial equations arise in numerous theoretical and practical applications. Solving such systems is a computational problem which is provably hard in the worst case, and appears quite challenging in practically relevant instance distributions. We propose to develop new quantum algorithms for characterizing the solution space of such systems, and producing solutions. 2.) Hidden Shifts and lattice problems. The Hidden Shift and Hidden Subgroup problems are part of an important quantum-algorithmic framework generalizing Shor s algorithm. We propose to significantly expand this framework by developing new Quantum Fourier Transforms and new Hidden Shift algorithms, with applications to lattice problems. In parallel, we will develop new quantum algorithms for hard lattice problems with improved asymptotic parameters, both in general and for special classes of lattices. 3.) Dynamic programming and recursion. Dynamic programming and recursion are widely used in classical algorithms, for tasks such as computing the longest common subsequence, and finding approximate solutions to the NP-hard knapsack problem. We will develop quantum algorithms using these ideas, building on the Bernstein-Vazirani algorithm for recursive Fourier sampling. We will also explore (with the goal of proving new complexity results) an analogy between dynamic programming and the behavior of Hamiltonian systems. Our team consists of top experts in quantum algorithms, and quantum computation and information more generally. We have extensive expertise in a wide range of subfields of computer science, mathematics, and physics. The project will support three PhD students and will run for three years. The place of performance is the Joint Center for Quantum Information and Computer Science (Qui CS), a world-renowned research center at the University of Maryland.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 03, 2020
- Source ID
- W911NF2010015
Entities
People
- Gorjan Alagic
Organizations
- Army Contracting Command
- National Security Agency
- University of Maryland