Adiabatic quantum computing
   HOME

TheInfoList



OR:

Adiabatic quantum computation (AQC) is a form of
quantum computing Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
which relies on the adiabatic theorem to do calculations and is closely related to
quantum annealing Quantum annealing (QA) is an optimization process for finding the global minimum of a given objective function over a given set of candidate solutions (candidate states), by a process using quantum fluctuations. Quantum annealing is used mainl ...
.


Description

First, a (potentially complicated)
Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified 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 (spectral gap) 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 H(t) 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: T = O\left(\frac\right) where g_ 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 (that is, the "temperature of the bath") 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 H = \sum_h_i Z_i + \sum_J^Z_iZ_j + \sum_K^X_iX_j where Z, X 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 (quantum behaviour 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.


Adiabatic quantum computation in satisfiability problems

Adiabatic quantum computation solves satisfiability problems and other combinatorial search problems. Specifically, these kind of problems seek a state that satisfies C_1 \wedge C_2 \wedge \cdots \wedge C_M . This expression contains the satisfiability of M clauses, for which clause C_i has the value True or False, and can involve n bits. Each bit is a variable x_j\in \ such that C_i is a Boolean value function of x_1, x_2, \dots , x_n. QAA solves this kind of problem using quantum adiabatic evolution. It starts with an Initial Hamiltonian H_B: H_B=H_+H_+\dots+H_ where H_ shows the Hamiltonian corresponding to the clause C_i. Usually, the choice of H_ 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 H_P: H_P=\sum\limits_^ H_ where H_ is the satisfying Hamiltonian of clause C. It has eigenvalues: h_C(z_,z_\dots z_)= \begin 0 & \mbox C \mbox \\ 1 & \mbox C \mbox \end For a simple path of adiabatic evolution with run time T, consider: H(t)=(1-t/T)H_+(t/T)H_ and let s=t/T. We then have \tilde(s)=(1-s)H_+sH_ , which is the adiabatic evolution Hamiltonian of our algorithm. According to the adiabatic theorem, we start from the ground state of Hamiltonian H_B at the beginning, proceed through an adiabatic process, and end in the ground state of problem Hamiltonian H_P. We then measure the z-component of each of the n spins in the final state. This will produce a string z_1,z_2,\dots,z_n which is highly likely to be the result of our satisfiability problem. The run time T must be sufficiently long to assure correctness of the result. According to adiabatic theorem, T is about \varepsilon/g_\mathrm^, where g_\mathrm=\min_(E_1(s)-E_0(s)) is the minimum energy gap between ground state and first excited state.


Comparison to gate-based quantum computing

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.


D-Wave quantum processors

The
D-Wave One D-Wave Systems Inc. is a Canadian quantum computing company, based in Burnaby, British Columbia, Canada. D-Wave was the world's first company to sell computers to exploit quantum effects in their operation. D-Wave's early customers include L ...
is a device made by Canadian company D-Wave Systems, which claims that it uses
quantum annealing Quantum annealing (QA) is an optimization process for finding the global minimum of a given objective function over a given set of candidate solutions (candidate states), by a process using quantum fluctuations. Quantum annealing is used mainl ...
to solve optimization problems. On 25 May 2011, Lockheed-Martin purchased a D-Wave One for about US$10 million. In May 2013,
Google Google LLC () is an American multinational technology company focusing on search engine technology, online advertising, cloud computing, computer software, quantum computing, e-commerce, artificial intelligence, and consumer electronics. ...
purchased a 512 qubit
D-Wave Two D-Wave Two (project code name Vesuvius) is the second commercially available quantum computer, and the successor to the first commercially available quantum computer, D-Wave One. Both computers were developed by Canadian company D-Wave Systems. T ...
. 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 The Quantum Artificial Intelligence Lab (also called the Quantum AI Lab or QuAIL) is a joint initiative of NASA, Universities Space Research Association, and Google (specifically, Google Research) whose goal is to pioneer research on how quantum ...
(
NASA The National Aeronautics and Space Administration (NASA ) is an independent agency of the US federal government responsible for the civil space program, aeronautics research, and space research. NASA was established in 1958, succeeding t ...
),
USC USC most often refers to: * University of South Carolina, a public research university ** University of South Carolina System, the main university and its satellite campuses **South Carolina Gamecocks, the school athletic program * University of ...
,
ETH Zurich (colloquially) , former_name = eidgenössische polytechnische Schule , image = ETHZ.JPG , image_size = , established = , type = Public , budget = CHF 1.896 billion (2021) , rector = Günther Dissertori , president = Joël Mesot , ac ...
, and
Google Google LLC () is an American multinational technology company focusing on search engine technology, online advertising, cloud computing, computer software, quantum computing, e-commerce, artificial intelligence, and consumer electronics. ...
show that as of 2015, there is no evidence of a quantum advantage.


Notes

{{Quantum computing Quantum mechanics