I have been interested Adiabatic Quantum Computing (AQC) for quite some time and have spoken with D-Wave's founder and have a few thoughts to post.
D-wave says they are using techniques in AQC to help solve np-complete problems via energy minimization of a quantum state that has been mapped to problems in mathematics. I believe they have also described their technique in the past as quantum annealing, related to classic simulated annealing frequently used in mathematical optimization of "np-hard" variants of np-complete problems.
An np-complete problem is a yes/no type of computer decision problem defined on a simple abstract model of a computer called a "Deterministic Turing Machine". Without getting into too much detail, the np-complete problems
appear to be "exponentially difficult" in the size of the problem "N". These problems come up frequently in problems like the famous TSP (Traveling Salesperson Problem) and other routing, scheduling, and assignment problems of interest to industry and the government.
Genuine AQC has been shown to be equivalent to standard "gate-based" quantum computing, and both can be shown to be "Turing Complete", and polynomially equivalent to each other (i.e., basically AQC = regular QC).
http://arxiv.org/abs/quant-ph/0405098http://arxiv.org/pdf...h/0405098v2.pdfFrom the abstract:
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev
(Submitted on 18 May 2004 (v1), last revised 26 Mar 2005 (this version, v2))
Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient adiabatic simulation of any given quantum algorithm, which implies that the adiabatic computation model and the conventional quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models provides a new vantage point from which to tackle the central issues in quantum computation, namely designing new quantum algorithms and constructing fault tolerant quantum computers. In particular, by translating the main open questions in the area of quantum algorithms to the language of spectral gaps of sparse matrices, the result makes these questions accessible to a wider scientific audience, acquainted with mathematical physics, expander theory and rapidly mixing Markov chains.
So the debate (and controversy) is not about the Turing universality of AQC, but is really centered on whether D-Wave is truly performing AQC in a Turing universal manner. That debate continues, but I do believe they can come up with good answers to very difficult problems, even if they are not being performed by a Turing universal QC.
For the class NP (and np-complete) problems mentioned in their literature in the past, it needs to be pointed out that at best, theoretically, they can only get about square root speedup of the important subclass np-complete (and np-hard) which includes a huge array of problems of interest to industry and defense in scheduling, optimization, etc. The np-complete problems are "realistically viewed" as being exponentially difficult in size of the problem N, although it is still unknown whether a polynomial time algorithm can solve NP (the famous unsolved question: is P equal to NP?).
http://en.wikipedia....alesman_problemLet's look at a famous problem like the Traveling Salesperson Problem (TSP) with N=25. In this problem we ask a salesperson to visit 25 cities once and only once on his/her tour of cities, and choose the shortest possible route/path. That would require (N-1)! = 24! = 24*23*22*...*2*1 paths to be investigated (! refers to the factorial function, so 5! = 5 * 4 * 3 * 2 * 1).
Below I use Srinivasa Ramanujan to estimate (n-1)! where n = 25 cities:
http://en.wikipedia....ons_for_large_nln(n!) != n * ln(n) - n + 1/6 * log(n(1 + 4n(1+2n))) + 1/2 * log(pi) = 54.7847
where pi = 3.1415926... and e = 2.718281828... = base of natural log
==>
n! = 6.20408 e+23
An interesting point to remember: Avogadro's number (a mole of particles) is about 6.02e+23, so the number of possible paths for a 25 city TSP problem is about Avogadro's number, which gives you an idea of the size of the problem for n=25. The value of Avogadro's is defined as the number of atoms in 12 grams of pure carbon-12. It is also important to note that N=25 is a very small problem compared to NP-Hard optimization typically found in industrial and military applications.
One of the claims in the past was that the computer could help address problems in np-hard optimization like the TSP and other problems in scheduling, assignment, and other tasks. This would be true in the sense that it would help, since the NP class does admit a solution via an algorithm called Grover's quantum computing algorithm for unstructured search. Grover does produce a square root speedup in NP, but the square root of exponential growth is still exponential (using best guess, P != NP). An np-complete problem growing like exp(n) will grow like exp(n/2) via Grover on a Turing universal QC.
Given the foundational nature of Bennett’s paper, here is the abstract in its entirety:
http://arxiv.org/pdf...-ph/9701001.pdfhttp://epubs.siam.or...rnalCode=smjcatStrengths and Weaknesses of Quantum Computing, Charles H. Bennett, et al.
Abstract. Recently a great deal of attention has been focused on quantum computation following a sequence of results [Bernstein and Vazirani, in Proc. 25th Annual ACM Symposium Theory Comput., 1993, pp. 11-20, SIAM J. Comput., 26 (1997), pp. 1411-1473], [Simon, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 116-123, SIAM J. Comput., 26 (1997), pp. 1474-1483], [Shor, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 124-134] suggesting that quantum computers are more powerful than classical probabilistic computers. Following Shor's result that factoring and the extraction of discrete logarithms are both solvable in quantum polynomial time, it is natural to ask whether all of NP can be efficiently solved in quantum polynomial time. In this paper, we address this question by proving that relative to an oracle chosen uniformly at random with probability 1 the class NP cannot be solved on a quantum Turing machine (QTM) in time o(2n/2). We also show that relative to a permutation oracle chosen uniformly at random with probability 1 the class NP ∩ co-NP cannot be solved on a QTM in time o(2n/3). The former bound is tight since recent work of Grover [in Proc. 28th Annual ACM Symposium Theory Comput., 1996] shows how to accept the class NP relative to any oracle on a quantum computer in time O(2n/2)
A few comments are in order here. The paper states that the class NP (which includes the NP-Complete subclass) cannot be solved in o(2n/2) time, using the “little o notation”, which means that the result is asymptotically bounded by 2n/2 , with the difference between the function and the asymptote being negligible for large n. The Grover result returns an answer in O(2n/2) time, where the “big O notation” means that the difference between the function and the asymptote is finite (perhaps not negligible) for large n. When the authors state that the bound on NP is tight, they mean that the solution time for problems in the class is between o(2n/2) and O(2n/2), i.e. the solution time is asymptotically bounded between asymptotic negligence and asymptotic finite difference. And very basically, in short approximate terms, we have square root speedup in np-complete. Good, but still requires exponential search time in size of the problem "N", or number of cities, or other defining characteristic of class NP.
If the D-Wave system is really doing a QC solution in a Turing universal way, regardless of whether it is adiabatic or traditional gate based QC, then we might have some really embarrassing moments wrt security and "stored encrypted messages"... i.e., messages that were stolen from secure facilities in an encrypted public key format years earlier could now be subject to Shor's algorithm for RSA and elliptic curve cryptosystems, and similar encryption techniques.
While the Shor algorithm could attack PK cryptography, some np-complete based encryption systems could be attacked via Grover, and while 1.0 e25 may seem like a lot of combinations to search for an exact search, in some cases a search, while expensive via a QC, might be worthwhile in a space of 1.0 e12 (e.g. national security applications).
I have posted before about the problems remaining "hard" with QC in class NP unless the standard assumption of linearity in quantum mechanics is dropped. A nonlinear quantum theory yields polynomial time solution of NP-Complete and #P-Complete. (#P could still be hard in classic computation even if in the future it is shown that P = NP). Given that most research assumes linear field theories, then the class NP will likely be viewed as hard in the near future, even on a QC.
http://arxiv.org/abs/quant-ph/9801041http://arxiv.org/pdf...h/9801041v1.pdfNonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
Daniel S. Abrams (1), Seth Lloyd (2) ( (1) Dept. of Physics, MIT, (2) Dept. of Mechanical Engineering, MIT)
If quantum states exhibit small nonlinearities during time evolution, then quantum computers can be used to solve NP-complete problems in polynomial time. We provide algorithms that solve NP-complete and #P oracle problems by exploiting nonlinear quantum logic gates. It is argued that virtually any deterministic nonlinear quantum theory will include such gates, and the method is explicitly demonstrated using the Weinberg model of nonlinear quantum mechanics.
There are other classes like #P-Complete that may be hard even if P=NP (making np-complete "easy", not currently believed, but unknown). Problems in the #P-complete class include problems in network reliability and survivability.
The take away from this post is that
IF D-Wave's system is Turing universal, then we might have an "oh sh*t" moment in national security. My guess is that they are doing a non-Turing universal variant of quantum annealing that may provide *good* solutions in NP, but not an exact solution.
This relates to longevity since there are a number of problems in protein folding, gene sequencing, and other areas that are np-complete.
Edited by npcomplete, 28 March 2013 - 06:31 PM.
LongeCity
