Synopsis

# Mind the Gap

Physics 4, s193
Simulations of a key quantum algorithm reveal the time required for executing a sample computation and point to possible methods for optimization.

Quantum computers promise to accelerate some kinds of calculations in a remarkable manner. But as in present-day classical computing, hardware is only half the story: efficiency requires development of appropriate algorithms, such as the fast Fourier transform.

To apply a quantum computer to a broad class of problems, general-purpose algorithms are needed. One such method is the quantum adiabatic algorithm, in which the problem to be solved is coded into a Hamiltonian $H$. One prepares the quantum computer in the ground state of a reference Hamiltonian $HR$ and then has it evolve under a time-dependent Hamiltonian $H(t)$ that gradually switches from $HR$ to $H$. If the evolution is slow enough (“adiabatic”) the system ends up in the ground state of $H$, which contains information about the desired solution.

In a paper in Physical Review E, Itay Hen and Peter Young of the University of California, Santa Cruz, show that “slow enough” may be very slow indeed. The reason is that the time required for adiabatic evolution depends inversely on the gap in energies between the ground and first excited states of $H(t)$. Using computer simulations, Hen and Young show that for three classes of logic problems, the scaling of the gap is such that the computational time can be expected to grow exponentially with the size of the problem. The authors suggest that it might be possible to optimize the evolution of $H(t)$ to avoid the bottleneck associated with a vanishing gap. – Ron Dickman

## Subject Areas

Quantum Information

## Related Articles

Quantum Physics

### Using Quantum Dots to Simulate Magnetism

Researchers successfully use an array of quantum dots to create and study a Heisenberg spin chain. Read More »

Quantum Physics

### Quantum Leap for Quantum Primacy

Two experimental quantum computers tackle the most complex problems yet, suggesting an end to the debate on whether quantum “primacy”—the point at which a quantum computer outperforms the best possible classical computer—can be reached. Read More »

Quantum Information

### Far Fewer Qubits Required for “Quantum Memory” Quantum Computers

Incorporating storage units for quantum information into quantum computers may allow researchers to build such devices with several orders of magnitude fewer qubits in their processors. Read More »