Thanks. In a kind of pure form quantum computation seems kind of problematic now, but it seems like it could be hybridized in the not to distant future. Example: suppose you wanted to capture all the properties for some object in 8 bit registers, one register to describe each property of the object. Instead of being limited to a single property per register, now you can cram 2^8 -- 256 --properties in a single register. A simply program could be crammed in another register, so you could run the whole shebang out of just two registers. The only time I tried parallel programming was on a Tandem computer, and I never developed the hang of it really. Simpler just to think serially. So some means of converting a program to parallel from serial would be nice. doubtless people have tried that. Mike A
On 3/19/13, Matt Mahoney <[email protected]> wrote: > 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/11943661-d9279dae > Modify Your Subscription: > https://www.listbox.com/member/?&; > Powered by Listbox: http://www.listbox.com > ------------------------------------------- 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
