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

Qubits Could Act as Sensitive Dark Matter Detectors
Quantum Physics

Qubits Could Act as Sensitive Dark Matter Detectors

A detector made from superconducting qubits could allow researchers to search for dark matter particles 1000 times faster than other techniques can. Read More »

A Chiral Magnet Induces Vortex Currents in Superconductors
Condensed Matter Physics

A Chiral Magnet Induces Vortex Currents in Superconductors

Control over vortices that arise in magnet-superconductor heterostructures could lead to qubits that are immune to the effects of their environment. Read More »

Measuring Higher Dimensional “Qudits” for Computation
Quantum Information

Measuring Higher Dimensional “Qudits” for Computation

With a technique called self-guided tomography, researchers accurately measure the states of qudits—quantum systems like qubits but with more than two dimensions.  Read More »

More Articles