|
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. |