Slashdot Mirror
IBM Touts Quantum Computing Breakthrough
Lucas123 writes "IBM today claimed to have been able to reduce error rates and retain the integrity of quantum mechanical properties in quantum bits or qubits long enough to perform a gate operation, opening the door to new microfabrication techniques that allow engineers to begin designing a quantum computer. While still a long ways off, the creation of a quantum computer would mean data processing power would be exponentially increased over what is possible with today's silicon-based computing."
And people keep telling me IBM isn't innovative and cutting edge anymore. [/Sarcasm]
1) Repeated news about being able to perform some operation with a tiny number of qubits do not suggest that it is probably true that a useful quantum computer of practical size can be built;
2) It wouldn't mean data processing power would be "exponentially increased", but that certain algorithms could be executed asymptotically faster.
QC remains a second rate branch of mathematics for computer science types who don't want to apply themselves to less glamorous problems in the more mature and challenging fields of classical computing. For engineers, it's still in the nuclear fusion stage: kinda just possible in the right conditions, but under no conditions shown useful.
The Economist had an interesting article a couple days ago.. at least it's interesting if you don't really know the details of quantum computing:
Quantum computing: An uncertain future
Each extra qubit in a quantum machine doubles the number of simultaneous operations it can perform. It is this which gives quantum computing its power. Two entangled qubits permit four operations; three permit eight; and so on. A 300-qubit computer could perform more concurrent operations than there are atoms in the visible universe.
Actually, this is a correct use. Some algorithms on quantum computers are exponentially faster than the best known classical algorithms. For example, estimating a Gauss sum http://en.wikipedia.org/wiki/Gauss_sum scales exponentially in time, but the most efficient quantum algorithms are bounded by a polynomial. So exponential speed up is a valid use of the term here.
The whole discussion is fubar
First of all, the derivative of e to the x ("exponential function") is e to the x. Yeah thats true the D is the same as the function itself. Welcome to 1st semester calculus, kids. Not a constant, not even sure what "constantly increasing" means mathematically, although if AC meant its linear thats a bucket of fail too.
The next fubar is quantum computing doesn't provide a magic exponential speedup. There is a page length summary on the wikipedia but it should come as No Surprise Whatsoever to anyone in CS that different algorithm designs inherently have different big O notation and magically sprinkling quantum pixie dust doesn't change that, some algos are linear, some poly, some constant, some exponential, all quantum computing does is swap about where some belong. Solve for X where X+1=2 is not gonna change much, factoring into primes is going to change quite a bit. Some of the most interesting problems are polynomial time not exponential in quantum computing. http://en.wikipedia.org/wiki/Quantum_computer#Potential
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
I find that to be a terrible explanation. What he said: "For each qubit you double the number of states you can be in at the same time." is also true for normal bits. Huh? Here is a better explanation: http://en.wikipedia.org/wiki/Qubit
For conventional computers, as soon as you have "and" and "not" in gate-form, you can do everything, as you can just connect them together. For quantum computers that is not true, as all elements performing the complete computation need to be entangled the whole time.
IMO, there is now reason to believe that the real-world scalability of quantum computers is so bad that it negates any speed advantage. It seems the complexity of building a quantum computer that can do computations on inputs of size n is at least high-order polynomial or maybe exponential in n. That would explain why no significant advances have been made in keeping larger quantum computing elements entangled in the last 10 years or so and no meaningful sizes have been reached.
Keep in mind that, for example, to break RSA 2048, you have to keep > 2048 bits entangled while doing computations on them. And you cannot take smaller elements and combine them, the whole > 2048 bits need to represent the input all must be entangled with each other or the computation does not work.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
has any1 else hear hurd of it????!?
FTFY.
Apparently wizard is not a legitimate career path, so I chose programmer instead.
I took a class on Quantum computing, and studied many specific QC algorithms, so I know a little bit about them.
Quantum Computers are not super-computers. On a bit-for-bit (or qubit-for-qubit) scale, they're not necessarily faster than regular computers, they just process info differently. Since information is stored in a quantum "superposition" of states, as opposed to a deterministic state like regular computers, the qubits exhibit quantum interference when mixed with other qubits. Typically, your qubit starts in 50% '0' and 50% '1', and thus when you measure it, you get a 50% chance of it being one or the other (and then it assumes that state). But if you don't measure, and push it through quantum circuits allowing them to interact with other qubits, you get the quantum phases to interfere and cancel out. If you are damned smart (as I realized you have to be, to design QC algorithms), you can figure out creative ways to encode your problem into qubits, and use the interference to cancel out the information you don't want, and leave the information you do want.
For instance, some calculations will start with the 50/50 qubit above, and end with 99% '0' and 1% '1' at the end of the calculation, or vice versa, depending on the answer. Then you've got a 99% chance of getting the right answer. If you run the calculation twice, you have a 99.99% chance of measuring the correct answer. However, the details of these circuits which perform quantum algorithms are extremely non-intuitive to most people, even those who study it. I found it to require an amazing degree of creativity, to figure out how leverage quantum interference constructively.
But what does this get us? Well it turns out that quantum computers can run anything a classical computer can do, and such algorithms can be written identically if you really wanted to, but doing so gets the same results as the classical computer (i.e. same order of growth). But, the smart people who have been publishing papers about this for the past 20 years have been finding new ways to combine qubits, to take advantage of nature of certain problems (usually deep, pure-math concepts), to achieve better orders of growth than possible on a classical computer. For instance, factoring large numbers is difficult on classical computers, which is why RSA/PGP/GPG/PKI/SSL is secure. It's order of growth is e^( n^(1/3) ). It's not quite exponential, but it's still prohibitive. It turns out that Shor figured out how to get it to n^2 on a quantum computer (which is the same order of growth as decrypting with the private key on a classical computer!). Strangely, trying to guess someone's encryption key, normally O(n) on classical computers (where n is the number of possible keys encryption keys) it's only O(sqrt(n)) on QCs using Grover's algorithm. Weird (but sqrt(n) is still usually too big).
There's a vast number of other problems for which efficient quantum algorithms have been found. Unfortunately, a lot of these problems aren't particularly useful in real life (besides to the curious pure-mathematician). A lot of them are better, but not phenomenal. Like verifying that two sparse matrices were mulitplied correctly has order of growth n^(7/3) on a classical computer, n^(5/3) on a quantum computer. You can find a pretty extensive list by googling "quantum algorithm zoo." But the reality is that "most" problems we face in computer science do not benefit from quantum computers. In these cases, they are no better than a classical computer. But for problems like integer factorization, bringing the compute requirements down to polynomial time isn't just faster: it makes a problem solvable that wasn't before.
Unfortunately [for humanity], there is no evidence yet that quantum computers will solve NP-complete problems efficiently. Most likely, they won't. So don't get your hopes up about solving the traveling salesmen problem any time soon. But there is still a lot of cool stuff we can do with them. In fact, the theory is so far ahead of the technology, that we're anxiously waiting for breakthroughs like this, so we can start plugging problems through known algorithms.
Wouldn't this be a game-changer for encryption, though (if they can actually make it work, that is)? I mean, brute-force decryption seems like exactly the kind of computational task that a quantum computer could easily handle. So a brute-force attack on a key that may take hundreds of years on a current supercomputer could be done in a few minutes. No password would be safe from any organization with access to that kind of computing power. Or am I understanding the potential?
"Somebody has to do something. It's just incredibly pathetic it has to be us."
--- Jerry Garcia
Wouldn't this be a game-changer for encryption, though (if they can actually make it work, that is)? I mean, brute-force decryption seems like exactly the kind of computational task that a quantum computer could easily handle. So a brute-force attack on a key that may take hundreds of years on a current supercomputer could be done in a few minutes. No password would be safe from any organization with access to that kind of computing power. Or am I understanding the potential?
Not necessarily, no. For any crypto app you can come up with some formula where you chunk in the number of bits and it spits out how long it takes to crack it. It exclusively has to do with scalability in design. Double a linear algo and that number takes twice as long. Most (good) crypto is exponential so triple the number of bits it goes up by 3^3 or 27 times longer or whatever. The deal is quantum computing for some crypto increases by poly instead of exponential.
What no one wants to talk about is what if the quantum solution for a given sample takes 100 years ... thats a bucket of fail even if it only increases poly. That is completely freaking useless because it scales nicely if you double the number of bits its just great that it only increases to 200 years, but no one can wait 100 years anyway, so...
This is also the strongly minority belief I hold about P=NP where I'm willing to accept there might be a poly solution to a supposedly exponential problem, but the constant factor for a trivial problem might be like a factorial number of universe-lifetimes so theoretically it exists which is why it hasn't been disproven yet and also it has no real world effect.
Much like the physics analogy of time dilatation at highway speeds, it exists, but its irrelevant in scale.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger