Quantum adiabatic and quantum circuit algorithms are equivalent, say physicists

20 Nov 2018 Hamish Johnston

Exactly equivalent: Quantum adiabatic and quantum circuit algorithms should take the same time to run (Courtesy: iStock/Devrimb)

Practical quantum computers could be one step closer thanks to physicists in China, who have published a rigorous proof that “quantum circuit” algorithms can be transformed into algorithms that can be executed at the same running time on adiabatic quantum computers .

A quantum circuit algorithm runs on a quantum computer made up of a sequence of quantum-logic gates. This set-up resembles a conventional computer, which runs algorithms on sequences of classical logic gates. However, fundamental differences between quantum and classical computation mean that certain problems can be solved much more quickly on a quantum computer.

A big challenge for researchers trying to create practical quantum computers is decoherence – the degradation of quantum information caused by interactions with the surrounding environment. This makes it very hard to maintain the quantum nature of information as it is being processed, which is why only very basic quantum computations have been possible so far.

Ground-state solution

Adiabatic quantum computers take a different approach by using a network of quantum nodes (such as superconducting circuits) that can be configured to represent a complicated computational problem. The solution to the problem is given by the lowest energy – or ground – state of the system, which can be very complicated to determine.

The trick is to first configure the system so that it has a much simpler ground state and then transform it into the much more complicated system representing the solution. If the transformation is done adiabatically, which means there is minimal transfer of energy into or out of the system, then the system will remain in its ground state during the transformation – thus revealing the solution to the problem. Because the system is in its ground state throughout the process, decoherence may not be as much of a problem as it is in systems running quantum circuit algorithms.

Algorithms for adiabatic quantum computers were first proposed in 2000 and since then, researchers have shown that quantum adiabatic algorithms and quantum circuit algorithms are “polynomially equivalent”. This means that if one type of algorithm takes time t to solve a problem, then the other will take a polynomial value of t to the nth power to complete the task.

Rigorous proof

Now, Biao Wu and colleagues at Peking University have shown that the two types of algorithm are even more similar by publishing a “rigorous proof that quantum circuit algorithm can be transformed into quantum adiabatic algorithm”. This means that if one type of algorithm takes time t to solve a problem, then the other will take t multiplied by a constant.

Wu told Physics World that the result is good news for people trying to build adiabatic quantum computers: “In principle, any quantum-computing problem can be solved using a quantum adiabatic algorithm as efficiently as using quantum circuit algorithm.

The proof is described in Chinese Physics Letters.

20/11/2018 FROM PHYSICSWORLD.COM