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.
I believe this was done by Japanese researchers. RTFA.
You can't access them individually.
You can measure your system and observe the value sqrt(k) for some random k between 1 and 2^n. This doesn't buy you anything as it is trivial clasically to choose a random k and compute its sqrt.
Or you can take "glurg" and apply some funky quantum gates to it and *then* measure your system and get n strange bits out of it. This can buy you something if you take a quantum computing class to learn how to design a useful quantum post-operation and analyze exactly what the output would be.
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...
I can (kinda) understand how n qubits can store every number between 1 and 2^n, and I can (very vaguely) imagine how that allows one to perform calculations on all those numbers simultaneously. Assuming all of that is true and good, what would one do with the output? For example, let's say I take sqrt(1 to 2^n) and get glurg as a result. Does glurg really hold the sqrt of all those numbers, and if so, how do I access them individually?
Those aren't the sorts of problem you ask to a quantum computer. Even if you could do that it would take you ages to read out all 2^n answers, so why bother, just use a classical computer.
Where quantum computers shine is when you know the answer lies between 1 and 2^n but you have no idea which number.
So you set up your QC with all the numbers between 1 and sqrt(N) and then ask the computer - what is a factor of N. It can test them all in parallel and give you the one result you want.
Tim.
God said, "div D = rho, div B = 0, curl E = -@B/@t, curl H = J + @D/@t," and there was light.
Simply put, for SOME calculations you MIGHT be able to get ONE answer, the shiny part is that it is sometimes possible to make the computer give you the interesting answer and none of the ones you don't care about. I.e if you try to factorize a large integer you can set up a QC to calculate the result of dividing it by every other integer, and if you do things right you can make it output only those integers which yield a result of 0. I'm not completely sure, but I think this is possible for only certain problems with certain properties, but given that integer factorization is of central importance to mathematics, and an exponential time problem for a classical computer, that problem alone is worth the effort of making one. It would among other things allow you to brute force an RSA key in the same time it takes to generate one. This is not to say that all encryption would be broken. Only those schemes where a QC can brute force the key in short time would be affected. It would not allow you to read a one time pad as an example. It would however drastically reduce the number of secure encryption algorithms as a large number of calculations that are "slow" for a classical computer are "quick" in a QC. The main problem with building a quantum computer is that you have to keep the quantum states separate from the environment or they collapse. So if there is a 90% chance that any one of your qubits will be successfully isolated for the duration of the calculation, the chance that all of your 333 qubits will be ok is less than 10^-15. What is worse, because each of the qubits is entangled with the other ones, any single one of them interacting with the environment will destroy not just that bit but ALL the qubits. Imagine trying to build a computer where an error in a single bit will reset all your RAM to random values. Now try to do that for a 2048 bit RSA key. To have just a 10% chance of success each of your qubits would need a probability of success greater than 99.9%. This may not seem difficult since classical computers manage it fine, but they don't have to deal with a practically 0 error tolerance. For the serial port anything between -3V and -12V is good enough to represent a 1. For a corresponding quantum system it needs to 1 , not 1.5 or 1.1 or even 1.001 It needs to be 1, no more, no less. This is why quantum computers typically involve cooling the whole thing close to absolute zero. If you don't the thermal noise of the system will be enough to nuke your memory. Remember, it is not required that you try to measure the value for the system to cause a collapse, it is sufficient that any reaction takes place which means that you could theoretically have measured the value if you were monitoring every single particle that wasn't part of your computer. If a single helium atom in your super cooled vacuum chamber accidentally strikes one of the 2048 beryllium ions that is held in your magnetic trap that could be it. If the laser you use to read/write to your system is off by a fraction of its wavelength you might be fucked too. What you need to do is ensure that the quantum state you create is in a form which has a very low probability of interacting with anything at all, yet retain a manner in which you can cause it to react with the other qubits so that you can entangle them. After that you need to find a way to set up a circuit of them which allows you to recover just those results you are interested in. I'm amazed they have managed to do this for even a few bits. This is sci-fi which makes a light-saber look like a trivial device.
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).