Quantum Algorithms and Applications

(Shor, Farhi, Harrow, Brown, Chong)

EPiQC will study the algorithms and applications which demonstrate the most promise in the five year horizon. Among these are quantum simulation, a natural task for a quantum computer, and the Quantum Adiabatic Algorithm which could yield efficient solutions to optimization problems.

Quantum Supremacy

An important milestone for quantum computers is to perform a task which cannot be simulated by classical computers–a condition has been recently described as “quantum supremacy”. Our research will address three key challenges in the current research on quantum supremacy: overheads, verification, and noise. Our strategy will be to consider three plausible near-term architectures: random circuits on an ion chain, random circuits on a planar architecture, and sequential circuits (suitable for our multimode cavity QED superconducting systems as shown below).

Quantum Simulation

One of the most important quantum algorithms is likely to be to simulate quantum systems. Indeed enormous amounts of (classical) supercomputer resources are already devoted to this task, and there would be tremendous utility in extending the range of simulations that are possible. As shown in the figure below, the Department of Energy spent large portions of 1.7 Billion CPU hours in 2011 simulating quantum processes. One key difference between quantum and classical simulations is that for a classical simulator, both dynamic problems (i.e. simulating time evolution) and static problems (such as finding properties of ground states and thermal states) are hard and tend to scale exponentially with the size of the system. On quantum computers, time evolution can be simulated much more efficiently, but in the worst case finding the ground state or a thermal state can still take exponential time. We will seek to improve quantum algorithms for these static problems both by simulating natural thermalization processes and by developing new faster synthetic processes. We expect that our proposals will in some cases be able to provably run in polynomial time, but ultimately will need to be tested on actual hardware. Thus we will also develop proposals for testing our state-preparation methods on near-term quantum computing devices.

Quantum Adiabatic Algorithm (QADI)

Among the many known quantum algorithms, QADI, introduced by Farhi et al. in 2000 as an alternative to classical heuristics for hard optimization problems, is an especially good match for our target systems. QADI involves building a system that can slowly evolve from an instance-independent Hamiltonian H(0) to a final H(T) whose lowest energy state encodes the solution to an optimization problem. The time needed to reach the optimum depends on the separation between an extremal eigenvalue and the next one in line, and in most cases this separation is impossible to compute, except in a few cases. It is not known whether QADI provides a significant advantage over classical heuristics or not, as the problem quickly becomes intractable in classical computers as the problem size increases. With systems in the 100- to 1000-qubit range, we will be able to investigate the performance QADI algorithm on problem sizes that are untouchable by classical numerical calculations.