Hacker News Reader

Comment by r2 | Hacker News Reader

Some USC scientists recently analyzed the performance of a D-wave system and found that "quantum annealing is indeed being performed by D-Wave One": http://www.pppl.gov/events/adiabatic-quantum-computing-d-wav...

So their computer does behave quantum mechanically. But I can't find any evidence that they have shown entanglement, which is necessary to realize the full promise of quantum computing, see e.g. http://www.scottaaronson.com/blog/?p=954#comment-40364

View on HN

I think they only do adiabatic quantum computing, which is not what most of the people mean when speaking about quantum computing (it does not involve entanglement, only quantum annealing). Edit: Wikipedia article: http://en.wikipedia.org/wiki/Quantum_annealing

this is correct. for those with a hazy understanding of quantum mechanics- or to lazy to read link- the adiabatic process basically adds an extraneous (kinetic) part to the Hamiltonian and then the commutation of these properties allows for a superior process than thermal annealing. D-Wave folks would like us to believe that this imitates the vast majority of computation improvements expected in QC, and it may yet create some performance improvements.

However, in 'true' QC, there is something very physically different happening; we expect to see universal superposition of Hamiltonian states (entangled vector bases), which allows for some remarkable parallelism in a gate architecture that mirrors programmable (classic) computers. Specifically, we would be able to perform an operation on 2^N different numbers with just one calculation, while in classical computing such a computation would actually require 2^N separate (sequential) iterations. DWave systems, although it has produced some evidence of engtanglement, could not achieve anything on this magnitude of computational efficiency/parallelism. Footnote: as promising as the big picture of recombining said superpositions and 'hacking the multiverse' (a la Deutsche) is, fragility & decoherence of said states is an extraordinary barrier to overcome in order to achieve a 'true' QC in the near term or even medium term (as some critics as Wolfram would argue)...

Your explanation of 'true' QC seems misleading as well. We can (and have) constructed the quantum gates necessary to build a computer with the classical gate structure. It is true that in doing so, if we make the input a superposition of states, then the output will be a superposition of the states that would result from passing in each individual state into a classical computer. However, this is not sufficient for us to actually take advantage of the massive parralelization. Lets assume you have a N quibit input, which is a perfect superposition of all 2^N possible states, and as many internal quibits as you want. You have some boolean function, f(n), that is true for exactly 1 number (and that number fits in N bits). If you tried applying programming your QC to apply f(n) to the superposition, then after you do that, you will have a superposistion of 2^N-1 0s, and one 1, all with an equal probability. When you go to measure it, you will read either 0, or 1. Not very usefull.

You can fix this problem using N+1 quibits, and returning the input number along with the answer. Now, you have 1 state where the 'answer' quibit is true. When you go to measure the system, you have a 1/(2^N-1) probability of seeing that state. If you see another state, then you have collapsed the superposition and need to redo the computation. This is equivalent to just randomly picking an input in the first place. Quantom mechanics does not allow a way of taking a system and making one state more probable based on its value (IE. guaranteeing that the one you measure is the one marked 'true'). However, their are some quantum mechanical mechanisms that can provide provable improvement.

One such algorithm is Shors, which allows efficient factorization of prime numbers.

In my opinion, their is a far more interesting result I have seen, which is a general algorithm that can take any problem with a solution space of 2^N, and solve it in 2^(N/2).

Sadly, it has been a while since I dabbled in quantom computing so I do not recall the details of that, and I very well might have gotten stuff wrong to.

I am however becoming convinced that P/=NP is a physical law of the universe.

EDIT: I just read farther down the thread. I think the algorithm I was referring to is Grovers search algorithm which was mentioned by zaptheimpaler.

Reply on news.ycombinator.com