On Tue, Mar 19, 2013 at 7:53 PM, Mike Archbold <[email protected]> wrote: > I thought if we took 2 qubits we could have it in states of either, > some, all, whatever combo: > 00, 01, 10, 11 > > eg: 01 and 11 might be a state at one point in time, 10 and 11 at the > next... etc, which is more than the simple choice of the above four in > ordinary binary. > > But reading elsewhere I have seen the claim that the information in > the qubit is the same amount as the ordinary bit (I was browsing > through a paper that Gentian Kasa posted here; he refers to Holevo's > theorem).
That's right. What quantum computing does is speed up some algorithms by computing a superposition of outputs from a superposition of inputs. If you have n qubits, then you effectively do 2^n computations in parallel. But there are some severe limitations. The operations have to be time reversible. Logic operations have to have the same number of inputs as outputs. Effectively, this means that they only do rotations in a complex vector space. The assignment statement is not computable. Neither is error correction, which is important because practical computation has a high error rate. When you have computed the result, you can only read the result probabilistically. The qubit values you observe depend on the amplitude of the computed result. A quantum computer does not speed up NP-complete problems. We do know of a couple of useful algorithms. Shor's algorithm will solve the discrete logarithm problem, and thus the factoring problem in O(n^3) time, thus breaking most forms of public key cryptography. Grover's algorithm will invert a function in O(2^(n/2)) time, which effectively speeds up brute force key search over symmetric key encryption as if the key were half its size. However, practical implementations have yet to be built. D-Wave has quantum computers with 128 and 512 qubit sizes, but they have the wrong architecture to execute Shor's or Grover's algorithm. Instead, they solve the discrete optimization problem of maximizing Ax + b where A is a partially programmable matrix (with a lot of fixed 0 elements), b is a partially programmable vector, and x = (-1,1)^n is the vector to be found. So far, it has only been used to compute small Ramsay numbers, but nothing that couldn't be computed with pencil and paper. Also, the machines cost millions of dollars (with liquid helium cooling) and in a typical application half of the qubits don't work due to noise and the extreme difficulty of manufacturing reliable components. -- -- Matt Mahoney, [email protected] ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-f452e424 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-58d57657 Powered by Listbox: http://www.listbox.com
