First, a 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. Finally, the simple Hamiltonian is adiabatically evolved to the desired complicated Hamiltonian. 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. 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 of the Hamiltonian. Specifically, if the system is to be kept in the ground state, the energy gap between the ground state and the first excited state of provides an upper bound on the rate at which the Hamiltonian can be evolved at time When the spectral gap is small, the Hamiltonian has to be evolved slowly. The runtime for the entire algorithm can be bounded by: where is the minimum spectral gap for AQC is a possible method to get around the problem of energy relaxation. Since the quantum system is in the ground state, interference with the outside world cannot make it move to a lower state. If the energy of the outside world is kept lower than the energy gap between the ground state and the next higher energy state, the system has a proportionally lower probability of going to a higher energy state. Thus the system can stay in a single system eigenstate as long as needed. Universality results in the adiabatic model are tied to quantum complexity and QMA-hard problems. The k-local Hamiltonian is QMA-complete for k ≥ 2. QMA-hardness results are known for physically realistic lattice models of qubits such as where represent the Pauli matrices 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 or a line of quantum particles with 12 states per particle. If such models were found to be physically realisable, they too could be used to form the building blocks of a universal adiabatic quantum computer. In practice, there are problems during a computation. As the Hamiltonian is gradually changed, the interesting parts occur when multiple qubits are close to a tipping point. It is exactly at this point when the ground state gets very close to a first energy state. Adding a slight amount of energy 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.
Adiabatic quantum computation in satisfiability problems
Adiabatic quantum computation solves satisfiability problems and other combinatorial search problems by the process below. Generally this kind of problem is to seek for a state that satisfies This expression contains the satisfiability of M clauses, each clause has the value True or False, and can involve n bits. Each bit here is a variable so is a Boolean value function of. QAA solves this kind of problem using quantum adiabatic evolution. It starts with an Initial Hamiltonian : where shows the Hamiltonian corresponding to the clause, usually the choice of won't depend on different clauses, so only the total number of times each bit involved in all clauses matters. Then it goes through an adiabatic evolution, ending in the Problem Hamiltonian : where is the satisfying Hamiltonian of clause C. It has eigenvalues: For a simple path of Adiabatic Evolution with running time T, consider: and let, we have: which is the adiabatic evolution Hamiltonian of our algorithm. According to the adiabatic theorem, we start from the ground state of Hamiltonian at beginning, go through an adiabatic process, and at last ending in the ground state of problem Hamiltonian. Then we measure the z-component of each of the n spins in the final state, this will produce a string which is highly likely to be the result of our satisfiability problem. Here the running time T must be sufficiently long to assure the correctness of result, and according to adiabatic theorem, T is about, where is the minimum energy gap between ground state and first excited state.
D-Wave quantum processors
The D-Wave One is a device made by a Canadian company D-Wave Systems which describes it as doing quantum annealing. In 2011, Lockheed-Martin purchased one for about US$10 million; in May 2013, Google purchased a D-Wave Two with 512 qubits. As of now, the question of whether the D-Wave processors offer a speedup over a classical processor is still unanswered. Tests performed by researchers at Quantum Artificial Intelligence Lab, USC, ETH Zurich, and Google show that as of now, there is no evidence of a quantum advantage.
