Adiabatic Quantum Computers have the potential to be faster than classical computers and circuit model quantum computers

Optimal Annealing Paths for Adiabatic Quantum Computation (AQC). 80 pages, 2011 by Navid Yousefabadi

The generic form of the gap functions for all the factorization problems allow an iterative process for finding the optimal parameters. AQC has the potential to be not only faster than the classical computers, but also the circuit model quantum computer.

The computational power of AQCs is not determined yet. It is mainly because the Hamiltonian of the AQC model is intractable, and consequently there is no rigid formulation that can relate the AQC’s computation time with the problem size. However, we know that entanglement is the key ingredient to the quantum computation power, and AQC directly uses the entangled qubits to anneal the system. There are some arguments about the power of this machine in literature. In a paper by Vazirani, it is stated that AQC can be used to gain quadratic speedup over classical search algorithms, and later the Grover bound was recovered for AQC. There
is even hope that AQCs has the potential to solve NP-complete problems polynomially,
where people solve random instances of NP-complete problems in polynomial time. In these works the AQC was simulated on a traditional computer, and the NP-complete problems that were solved with the simulated AQC, were limited to small sizes. Later, in several other similar works, it was shown that conventional AQC fails to provide an exponential speedup for solving NP-complete problems.

In this dissertation, we similarly simulate AQC (the spin glass Ising model AQC), with which we solve integer factorization instances (noting that instead of using the adiabatic approximation, we evolve the Hamiltonian in time and find the exact state of the system). Although we are limited in the problem size, we show that even if the conventional AQC fails to provide an exponential speedup, one can find optimal annealing paths that can exponentially improve the computation time. The Hamiltonian we use is the one implemented by D-Wave. This Hamiltonian is known to not be universal. However, a very large class of problems can be solved with Hamiltonian, including the important problem of integer factorization, and this is the problem on which we will focus.

The factoring problems could be encoded in an Ising Hamiltonian. For this task some carry qubits are needed. It was shown that to factor a 6 bit number, 17 bits are needed in total: 6 bits represent the factors (either a 3-bit and a 3-bit number or a 4-bit and a 2-bit number) and 11-bits for the carry bits.

However, for an algorithm that factorizes integer numbers on an Adiabatic quantum computer, which operates without using quantum logic gates, there is still no way to show how the computational time will scale with respect to the problem size. It is not clear whether an adiabatic quantum computer could be exponentially more efficient than a classical computer. The main issue seems to be that in the case of AQC, there is no explicit expression that can express the relationship between the annealing time needed to find the answer, and the size of the system. Having such an expression requires solving the time dependant Schrodinger equation for any large size Ising Hamiltonian.

The computational power of circuit model quantum computers is dramatically illusrated via Shor’s algorithm for integer factorization, where this quantum algorithm is exponentially more efficient than any known classical algorithm. On the other hand, there is no mathematical formulation for adiabatic quantum computers, such that one can assert any scaling between the problem size and computation time. However, through a limited number of factorization problems that could be solved numerically, we demonstrated such scaling. We showed that naive AQC is incapable of providing an exponential speedup over classical computers, but its unleashed power lies in the evolution path. Intuitive from the adiabatic theorem, the main ingredients of the AQC’s speed are larger gaps and slower speeds. We brought conclusive evidence that there exist evolution paths that provide such ingredients. We provided one-parameter and two-parameter evolution schemes. Utilizing heuristically-derived parametrised functions, it was shown how these functions could find larger gaps, and could adjust their speed with the gap value to result in a faster computation. Not only could AQC factorize integers in polynomial time, but also the degree of the polynomial can be reduced by optimising the evolution path.

We have preliminary evidence that there exist even more optimal paths in higher dimensions, although only results for one-dimensional and two-dimensional landscapes were shown. We have developed a scheme to penetrate higher dimensions, in order to find short paths with larger gaps. The generic form of the gap functions for all the factorization problems allow an iterative process for finding the optimal parameters. Therefore, AQC has the potential to be not only faster than the classical computers, but also the circuit model quantum computer. These issues are the subject of ongoing work.

The Limits of Adiabatic Quantum Computation is a thesis paper written in 2009 by Alper Sarikaya of the University of Wisconson (21 pages) This paper has an opposing view that adiabatic computers only provide polynomial speedup. It runs a few simulations and has no mathematical proof. The first paper seems more thorough by using different algorithms and methods to tune the process to get more speed.

Initial results indicate that as the number of qubits in the system increases, the eigenvalue gap of the ground state of the combined Hamiltonian H decreases polynomially. While this supports the hypothesis described in Chapter 2 that adiabatic quantum computation only off er a polynomial increase in efficiency over the exponential time reclaimed by standard quantum computation, this result is only preliminary.

We have brought up that this is simply a numerical simulation of several runs of the
Hamiltonian. Since we are trying to deal with all cases of the input wave function it would seem that a mathematical proof would yield a more conclusive result for our hypothesis. Instead, we opted for a numerical simulation by randomly feeding input wavefunctions and function parameters to the computational Hamiltonian as a mathematical proof would be infeasible.

An adiabatic quantum computer has the advantage of circumventing the problem of quantum decoherence { as the quantum computer is always kept in the ground state throughout the computation, the surrounding environment cannot force the lower-energy state that would disrupt the computation. As long as the temperature of the environment is kept below the ground state of the quantum computer, the qubits in the computation can be kept coherent. However, from the preliminary results here in this paper, it seems to give up some of its efficiency gains by remaining in the ground state throughout the quantum evolution.

A patent for the Physical Realizations of a Universal Adiabatic Quantum Computer describes adiabatic quantum computers versus quantum computers versus classical computers.

A Turing machine is a theoretical computing system, described in 1936 by Alan Turing. A Turing machine that can efficiently simulate any other Turing machine is called a Universal Turing Machine (UTM). The Church-Turing thesis states that any practical computing model has either the equivalent or a subset of the capabilities of a UTM.

A quantum computer is any physical system that harnesses one or more quantum effects to perform a computation. A quantum computer that can efficiently simulate any other quantum computer is called a Universal Quantum Computer (UQC).

In 1981 Richard P. Feynman proposed that quantum computers could be used to solve certain computational problems more efficiently than a UTM and therefore invalidate the Church-Turing thesis. See e.g., Feynman R. P., “Simulating Physics with Computers”, International Journal of Theoretical Physics, Vol. 21 (1982) pp. 467-488. For example, Feynman noted that a quantum computer could be used to simulate certain other quantum systems, allowing exponentially faster calculation of certain properties of the simulated quantum system than is possible using a UTM.

Approaches to Quantum Computation

There are several general approaches to the design and operation of quantum computers. One such approach is the “circuit model” of quantum computation. In this approach, qubits are acted upon by sequences of logical gates that are the compiled representation of an algorithm. Circuit model quantum computers have several serious barriers to practical implementation. In the circuit model, it is required that qubits remain coherent over time periods much longer than the single-gate time. This requirement arises because circuit model quantum computers require operations that are collectively called quantum error correction in order to operate. Quantum error correction cannot be performed without the circuit model quantum computer’s qubits being capable of maintaining quantum coherence over time periods on the order of 1,000 times the single-gate time. Much research has been focused on developing qubits with coherence sufficient to form the basic information units of circuit model quantum computers. See e.g., Shor, P. W. “Introduction to Quantum Algorithms”, (2001), pp. 1-27. The art is still hampered by an inability to increase the coherence of qubits to acceptable levels for designing and operating practical circuit model quantum computers.

Another approach to quantum computation involves using the natural physical evolution of a system of coupled quantum systems as a computational system. This approach does not make critical use of quantum gates and circuits. Instead, starting from a known initial Hamiltonian, it relies upon the guided physical evolution of a system of coupled quantum systems wherein the problem to be solved has been encoded in the terms of the system’s Hamiltonian, so that the final state of the system of coupled quantum systems contains information relating to the answer to the problem to be solved. This approach does not require long qubit coherence times. Examples of this type of approach include adiabatic quantum computation, cluster-state quantum computation, one-way quantum computation, quantum annealing and classical annealing, and are described, for example, in Farhi, E. et al., “Quantum Adiabatic Evolution Algorithms versus Simulated Annealing” (2002), pp 1-16.

Complexity and Computability

Wikipedia on Computational complexity theory

Wikipedia on BQP

In computational complexity theory BQP (bounded error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most one third for all instances. It is the quantum analogue of the complexity class BPP.

In other words, there is an algorithm for a quantum computer (a quantum algorithm) that solves the decision problem with high probability and is guaranteed to run in polynomial time. On any given run of the algorithm, it has a probability of at most one third that it will give the wrong answer.

Quantum computers have gained widespread interest because some problems of practical interest are known to be in BQP, but suspected to be outside P. Some prominent examples are:

* Integer factorization (see Shor’s algorithm)
* Discrete logarithm
* Simulation of quantum systems (see universal quantum simulator)
* Computing the Jones polynomial at certain roots of unity

Quantum annealing can be millions of times faster than classical computing

If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks