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

Real-Time Error Correction for Quantum Computing
Quantum Information

Real-Time Error Correction for Quantum Computing

An experiment shows that errors in quantum computation can be repeatedly corrected on the fly. Read More »

Pushing the Limits of Quantum Sensing with Variational Quantum Circuits
Quantum Information

Pushing the Limits of Quantum Sensing with Variational Quantum Circuits

Variational quantum algorithms could help researchers improve the performance of optical atomic clocks and of other quantum-metrology schemes. Read More »

Using Quantum Dots to Simulate Magnetism
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 »

More Articles