glances at advert for Quantum Disk Drives
It’s not quite that simple. If that were all there is to it, a quantum computer could efficiently solve any problem in NP (and people would be much more interested). The problem with this method is that you can’t efficiently read out the result you want.
As Mathochist explained, actual quantum algorithms rely more on being able to detect long periods efficiently and, in some problems like factoring, using knowledge of the period to determine something useful.
Most of the hype was probably surrounding the Shor and Grover algorithms; there haven’t been any other such interesting algorithmic results. The hardware development doesn’t seem to lend itself to such sexy headlines (“Four Qubits!” … “Five Qubits!” …), at least until the numbers get up into the hundreds where they can start to solve actual hard factoring problems.
It depends on what you mean by “possible.” Quantum computation doesn’t enlarge the class of “computable functions” (for example, the halting problem is still unsolvable); but it does make some computations feasible (e.g., finishing in less than the age of the universe) for which the current classical algorithms are practically infeasible.
Speaking as someone who doesn’t know his ass from a quantum hole-in-the-ground about this stuff, are there not two other major pluses with quantum computing?
-
Modeling quantum systems themselves
-
The ability to break any code (as well as the ability to know if your own coded message has been “listened to”)
First of all, some crypto systems are provably unbreakable period. The most famous of which are One-Time-Pad type systems.
Secondly, several theoretically breakable (but hopefully unbreakable “in practice”) systems are related to more difficult problems than factoring. None of these have been proven efficiently solvable using quantum computing.
It is a widespread misunderstanding that all problems in NP are known to be solvable in polynomial time using a quantum computer.
My take on the whole thing:
In Theoretical Computer Science, there are “trendy” topics that pop up from time to time and flood the major conferences like STOC and FOCS for a year or two. QC was just another one of these.
Given the lack of “interesting” positive results and the few (quite underpublicized) negative results, people are getting quite discouraged.
So they are just waiting for the next “hot topic” to come along so they can get their next grants and pad their vitas.
Don’t confuse quantum computing with quantum cryptogrphy. The latter is eminently feasible and the hardware has actually been built. The only thing is that it relies on photons and the unknowability of their quantum state until you actually measure it. You cannot amplify them so it is limited to the distance you can send a photon without losing it. Quantum cryptography is also theoretically uncrackable and also uninterceptible (without leaving unerasable traces), all from the magic of quantum mechanics.
I would also like to correct a statement above that the ONLY way to factor a number is to try division by all primes less than its square root. There are a number of quite significantly faster methods. One of them is called the elliptic curve method. I have not come close to understanding it, but it is much faster than trial division, while definitely not polynomial time. There is a web site that will allow to you enter numbers in excess of 100 digits and it factors them quite quickly using the ECM, definitely not by trial division by all 50 digit or smaller primes. IIRC, the person who runs it is named Dario Alpern (he’s an Argentine) and you can find it by googling him. It carries out various other number theoretic computations, for example, writing any integer it can factor as a sum of four squares.
Quantum computation has the ability for “Massively parallel” computation. As others have mentioned, you can manipulate large amounts of data simultaneously because you can deal with these superpositions of 0 and 1 states simultaneously. Not only that, but QC’s have more inherent operations than the classical computer (the standard logic operations). For example, the QC also has a natural {square root(-1)} operation.
The requirements for QC are as folows:
- Design algorithms/problems that the QC can solve. Otherwise, what’s the point?
-Mathematics - Determine what physical device will be the basis of the QC and how you can manipulate the data.
-Theoretical physics - Build this device.
- Experimental physics and in the future engineering.
Quantum error correction is an area where much research is taking place. It’s not something I have much knowledge of, but they are trying to use the mechanism of quantum entanglement (quantum teleportation) to be able to correct for various noises.
AFAIK the only experimental quantum computers that have been built so far are based on nuclear magnetic resonance (the basis for MRI machines), using nuclear spin states as the qbits. I can’t remember how many qbits they’re up to, somewhere around 5 I think.
Spintronics (electronics deals with electron charges, spintronics deals with electron spins) has possible future applications with QC. That the qbits of a QC could be the electron spin states (or a superposition of electron spin states) in a quantum dot. A quantum dot is essentially an energy well that can capture individual electrons. There is much research right now in trying to build these qbits and be able to read and manipulate the data. This should also involve quantum entanglement.
Mathochist is correct, the big problem with any practical QC device is the scalability. Nobody really knows if they’ll ever be able to build a QC with more than a handfull of qbits. There are various types of signal degradation such as dephasing times (timescale when the spin-states become randomized and we lose all information). I have read that in order to have practical QC, the dephasing time must be longer than around 1 nano second. Apparently semiconductor spintronics has this possibility and I think they’ve built devices that are currently at around 0.1ns.
Nitpick: I was at a talk recently and the speaker said that those in this area of research have downgraded it from quantum cryptography to “quantum key exchange”. Because they realised that they somehow had to send the deciphering key to the receiver, which wouldn’t be quantumly secure. Once the receiver has this quantum key then you are correct, it is theoretically uncrackable because the key is essentially a long string of random qbits.
So wait – would it be correct to interpret this statement as saying a quantum computer can actually implement a non-deterministic algorithm?
I’m a grad student in computer science, but have little knowledge about quantum computing. Some of the people in my department are involved in this, however; from what I’ve gathered (which, again, is not much), they’re looking at using quantum cells to implement something that appeared to me to be akin to classical computing machinery. In particular, the cells can be placed next to one another to form something akin to a wire; this has a many benefits, among which are better size, heat, and speed capacities. Another nifty thing about this is that these “wires” can be laid over one another, which does wonders for circuit layout (not to mention a very real possibility of 3-D circuits).
I should probably talk to the people in my department, but does anyone have any knowledge about this? Is my understanding correct? If so, does this increase anyone’s opinion of the possible usefulness of quantum computing?
I suppose I should have included some links (although I’m not sure which are the most relevant, knowing as little as I do):
Quantum Dots, from Lawrence Livermore
Quantum Cellular Automata, from University of Waterloo
Quantum Dot Cellular Automata, from Notre Dame
News article about quantum dot fabrication, from Purdue
Quantum Dots, from Wikipedia
Doesn’t Quantum, Quantized, ect mean only set values? For example, as I recall, electron spin is something like + or - 1/2. How do you take something with two binary values and get an infinite set of possibilities?
Really? Do you have more information on that? Is there a more official name for this type of system?
Not what I was thinking it was, and to answer my own question, sometimes called the Vernam cipher.
I have an online account where there is a randomly generated pad where numbers and letters are assigned, and you enter the number you know with letters on the pad. It is different each time, but from what I can tell, this is not the same system as a ‘one time pad.’
Well, not exactly. Reading out the result is technically non-deterministic, but with probabilities for the various possible results of observation being set by a deterministic process. In practice, one sets up a “quantum register” of qubits and performs some operation, which will make the “right” answer almost certain to be observed. You can then repeat the experiment to bump up the lower bound on error.
There are only two possible values from an observation of an electron’s spin, but the electron’s state before the observation (and during a quantum computation) is a linear combination of those two values.
Think of a point on the unit circle. Say when you look at it, you’ll either see it at (1,0) or (0,1), but the probability of each is the square of the point’s component along each direction. That is, (3/5,4/5) would be seen as (1,0) 9/25 of the time, and as (0,1) 16/25 of the time. There are two possible outcomes of an observation, but there are infinitely many points around the circle.
Basically it replaces the group of integers modulo n (for some very large n) with another group, which happens to be derived from a thing in algebraic geometry called an elliptic curve. The Wikipedia article has a good coverage of the group law.
Yes, it’s more analogous to a protocol like Diffie-Hellman than to a cryptosystem like RSA or Rijndael. I wasn’t aware that they had changed what they called it, but that’s really public relations as much as anything else.
http://www.alpertron.com.ar/ECM.HTM
(and if you want an idea of the complexity, look at the source code. oy.)
Not exactly: QC would, should it provide an efficient solution to the factoring problem, allow you to decode any RSA-encrypted message, since the strength of RSA rests on the intractability of factoring large numbers. Given the marketshare of RSA, this has led to the headline that QC would be the ultimate decryption machine. Which might be essentially true today, but there are numerous other cryptographic methods which would not be compromised by a successful factoring implementation. So while it’s true that one could wreak havoc with such a system at the moment, as other crypto methods see wider usage, this will gradually become less of a threat.
For that matter, by the time useful quantum computers are available, it will likely be possible to use quantum key exchange to move around one time pads - that would be an unbreakable/uninterceptable method of encryption.
As others have said, it’s not that you could break any code, but rather a particularly popular encryption algorithm.
My impression is that most physicsts would be a lot more excited about the quantum simulation aspects than the code breaking aspects. If we can learn how to make scalable quantum computers, we’d probably start learning a lot more physics very quickly. The main value of the code breaking applications, to most physicists, is as a means of extracting funding from govenment agencies. 