Mind the Gap
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 . One prepares the quantum computer in the ground state of a reference Hamiltonian and then has it evolve under a time-dependent Hamiltonian that gradually switches from to . If the evolution is slow enough (“adiabatic”) the system ends up in the ground state of , 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 . 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 to avoid the bottleneck associated with a vanishing gap. – Ron Dickman