[2][3][4][5] First, a (potentially complicated) Hamiltonian is found whose ground state describes the solution to the problem of interest.
Next, a system with a simple Hamiltonian is prepared and initialized to the ground state.
By the adiabatic theorem, the system remains in the ground state, so at the end, the state of the system describes the solution to the problem.
Adiabatic quantum computing has been shown to be polynomially equivalent to conventional quantum computing in the circuit model.
[6] The time complexity for an adiabatic algorithm is the time taken to complete the adiabatic evolution which is dependent on the gap in the energy eigenvalues (spectral gap) of the Hamiltonian.
provides an upper bound on the rate at which the Hamiltonian can be evolved at time
[7] When the spectral gap is small, the Hamiltonian has to be evolved slowly.
AQC is a possible method to get around the problem of energy relaxation.
Universality results in the adiabatic model are tied to quantum complexity and QMA-hard problems.
[8] QMA-hardness results are known for physically realistic lattice models of qubits such as[9]
Such models are used for universal adiabatic quantum computation.
The Hamiltonians for the QMA-complete problem can also be restricted to act on a two dimensional grid of qubits[10] or a line of quantum particles with 12 states per particle.
[11] If such models were found to be physically realizable, they too could be used to form the building blocks of a universal adiabatic quantum computer.
As the Hamiltonian is gradually changed, the interesting parts (quantum behavior as opposed to classical) occur when multiple qubits are close to a tipping point.
It is exactly at this point when the ground state (one set of qubit orientations) gets very close to a first energy state (a different arrangement of orientations).
Adding a slight amount of energy (from the external bath, or as a result of slowly changing the Hamiltonian) could take the system out of the ground state, and ruin the calculation.
Trying to perform the calculation more quickly increases the external energy; scaling the number of qubits makes the energy gap at the tipping points smaller.
Specifically, these kind of problems seek a state that satisfies
QAA solves this kind of problem using quantum adiabatic evolution.
won't depend on different clauses, so only the total number of times each bit is involved in all clauses matters.
Next, it goes through an adiabatic evolution, ending in the Problem Hamiltonian
For a simple path of adiabatic evolution with run time T, consider:
In accordance with the adiabatic theorem, start from the ground state of Hamiltonian
at the beginning, proceed through an adiabatic process, and end in the ground state of problem Hamiltonian
Then measure the z-component of each of the n spins in the final state.
The run time T must be sufficiently long to assure correctness of the result.
[12] Adiabatic quantum computing is equivalent in power to standard gate-based quantum computing that implements arbitrary unitary operations.
However, the mapping challenge on gate-based quantum devices differs substantially from quantum annealers as logical variables are mapped only to single qubits and not to chains.
[13] The D-Wave One is a device made by Canadian company D-Wave Systems, which claims that it uses quantum annealing to solve optimization problems.
Tests performed by researchers at Quantum Artificial Intelligence Lab (NASA), USC, ETH Zurich, and Google show that as of 2015, there is no evidence of a quantum advantage.