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

Fault-Tolerant Quantum Error Correction without Measurements
Quantum Physics

Fault-Tolerant Quantum Error Correction without Measurements

A proposed recipe for quantum error correction removes the need for time-consuming measurements of qubits, replacing them with copying and feedback steps instead. Read More »

Cooper-Pair Splitting on Demand
Quantum Information

Cooper-Pair Splitting on Demand

A proposed device can repeatedly grab pairs of electrons from a superconductor and separate them while preserving their entangled state. Read More »

Superconducting Qubit Breaks Low-Frequency Record
Quantum Physics

Superconducting Qubit Breaks Low-Frequency Record

Researchers have demonstrated an unprecedentedly low-frequency superconducting “fluxonium” qubit, which could facilitate experiments that probe macroscopic quantum phenomena. Read More »

More Articles