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."
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 depressing thing is that you will never see anything like this out of Apple. Billions of dollars in reserves and no "Jobs Labs".
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.
THIS, like times a million. NYTimes this weekend had an excellent article on the history of Bell Labs (the laser, the transistor, communications satellites, etc). HP, whatever else you may think of them, supported the pure research lab which brought forth the memristor. IBM can point to things such as this, its various efforts to simulate a brain, and Watson. Google, bless their souls, is pushing for automated driving (this may not sound in the same league, until you realize the consequences for everybody who drives or rides in an auto.)
Where is the pure research at Apple? Do they think they can get by on just making better UIs, for the rest of forever? Are they at all part of a larger community?
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.
Apple doesn't do technological research. Instead, they pour all of that money into usage research, so that they can design an improved user experience.
It's not necessarily a bad thing. There's a place for both the technological side, and the usability side. Most tech companies focus on the technology side while neglecting the usability, which is why so much technology ends up unusable by laymen.
Microsoft actually does a lot of usability research too. But the difference between Microsoft and Apple is that Apple has (or had) someone steering the ship. They're a top-down dictatorship-style management house. Microsoft is more about internal competition to see who wins out. They're more of a survival-of-the-fittest, cream-of-the-crop-rises-to-the-top type of management house.
"If a nation expects to be ignorant and free in a state of civilization, it expects what never was and never will be."