Slashdot Mirror
Research Team Makes Quantum Computing Progress
Timogen writes to tell us Wired is reporting that a research team is reporting that they have found a way to "controllably couple qubits" bringing us one step closer to quantum computing. "In classical computer science, bits -- or binary digits -- hold data encoded as ones and zeros. In quantum computing, data is measured in qubits, or quantum bits. As such, a qubit can have three possible states -- one, zero or a "superposition" of one and zero. This unique property theoretically makes quantum computing able to solve large-scale calculations that would dwarf today's supercomputers. But qubits in isolation are not very useful. It's only when they can be connected to one another that large-scale processing becomes possible."
Qubits can have an infinite number of states between 0 and 1 (inclusive). "Superposition" does not describe a single state, it just means that it's somewhere in between.
Quantum computers don't turn NP into P. I.e. they don't let you solve NP problems (where recognizing a correct answer is very easy but you have to test all answers to see which is correct) in an amount of time that is a polynomial function of the size of the input.
There are two specific algorithms for quantum computers that have a big impact on encryption:
Shor's algorithm lets a quantum computer factor a number in polynomial time. It requires a number of qubits that is some multiple (greater than 1) of the number of bits in the number. So, once we have quantum computers with a few thousand qubits, all encryption mechanisms based on the difficulty of factoring numbers (which is most mechanisms) are broken.
Grover's algorithm lets a quantum computer look up an entry in an unordered dictionary in N^.5 time, where N is the number of entries in the dictionary.
Grover's algorithm, if I understand it properly, is a Big Deal. When they say "look up an entry in a dictionary", they really mean "give an entry for which an arbitrary algorithm returns a desired value". Essentially, it means you can solve any NP problem in N^.5 time. For example, with a simulation algorithm you could find a satisfactory design out of 100,000,000,000,000 different computer designs in 10,000,000 applications of the simulation algorithm, as opposed to the 100,000,000,000,000 applications it could take on a normal computer.
Another example of applying Grover's algorithm would be cracking a password (regardless of the encryption algorithm used). Let N be the number of possible password combinations. On average cracking a password would take N/2 applications of the encryption algorithm using a normal computer; it would take N^.5 applications using a quantum computer.
Quantum computing doesn't invalidate encryption, but real QC would essentially invalidate encryption algorithms based on the difficulty of factoring large numbers and substantially reduce the difficulty to crack any other algorithmic encryption.
Of course, one time pads are still totally unbreakable if used properly...
You can't access the results individually, and that's the catch. QC does not lead to an exponential speed-up because, even though the "model" says every computation is performed simultaneously, you can only access ONE of the result. As soon as you read one result all the others "collapse" to that result. Imagine a 256 pages book containing the square root of the first 256 integers. Then the only thing you can do is randomly open the book to any page. Say you get sqrt(4)=2. Then every other page of the book holds a 2. You can still use QC to an advantage, but you have to be tricky: waiting as long as possible to read the output and making "interference" operations to increase the probability of the desired answer to show up. That is how a QC can theoretically search an unsorted array in a time proportional to SQRT(n).