New Frameworks for Quantum Algorithms
Abstract
Small quantum devices that will run quantum algorithms are on the near horizon. The development of novel quantum algorithms and the understanding of the power of existing algorithms is more pressing than ever. In the last couple of years we have been involved in the development of novel quantum algorithms and in this we outline our plans for the near future. Most studied quantum algorithms fall into a few classes. These include quantum period finding, quantum algorithms for unstructured search, variants of the quantum adiabatic algorithm as well as quantum simulation. We have been developing algorithms that go beyond these categories. Our ideas fall into two main categories: high-dimensional linear algebra, and restricted models of quantum computing. Linear algebra: One explanation for the power of quantum computers is that they can manipulate exponentially large vectors. However, they are restricted by unitarity and also by the fact that most transformations cannot be done efficiently. Despite this, basic manipulations such as the quantum Fourier transform and solving linear systems of equations are possible. We propose to extend the range of linear-algebraic primitives and improve the accuracy and efficiency with which these can be carried out. Restricted models: The second theme of our proposal is to consider quantum computers that fall short of the ideal large-scale fault-tolerant universal model. For example, we may consider quantum computers that run for a short duration (aka "low-depth circuits") or Hamiltonian-based quantum computers with slowly varying or geometrically local Hamiltonians. These are of great practical interest given that near-term quantum computers may be based on architectures that are in principle universal but in practice are too small to meaningfully run error-correction or compile complicated circuits. On a theoretical level as well, these projects help us better understand the boundary between classical and quantum computing.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 11, 2018
- Source ID
- W911NF1710433
Entities
People
- Aram Harrow
Organizations
- Army Contracting Command
- Massachusetts Institute of Technology
- United States Army