Slashdot Mirror
The Limits of Quantum Computing
The Narrative Fallacy writes "Scott Aaronson has posted a draft of his article from this month's Scientific American on the limitations of quantum computers (PDF) discussing the question: Will quantum computers let us transcend the human condition and become as powerful as gods, or are they a physical absurdity destined to be exposed as the twenty-first century's perpetual-motion machine? Aaronson says that while a quantum computer could quickly factor large numbers, and thereby break most of the cryptographic codes used on the Internet today, there's reason to think that not even a quantum computer could solve the crucial class of NP-complete problems efficiently. Aaronson contends that any method for solving NP-complete problems in polynomial time may violate the laws of physics and that this may be a fundamental limitation on technology no different than the second law of thermodynamics or the impossibility of faster-than-light communication."
I think you need a new quantum computer - you seem to have been beaten to that first post you claim.
The truth is a superposition of this two, so thruth is quantum. So could quantum computer uncover the truth? A: Maybe.
Extreme Programming - Redundant Array of Inexpensive Developers
We don't need Quantum computing for a Star Trek futre.
We need a way to disregard or at least completely reinterpret the laws of physics, and do without money, and all get on, and find entire worlds whose populations all conform to some stereotype.
And are green.
What does it matter if it is perfect or not? Seems to me that it is much better than what we're working with now.
If we want to start talking in that tone, well our "micro" processors and new fangled technologies didn't solve the mysteries of the universe, so we should have stuck with computers the size of buildings that have trouble doing more than adding, subtracting, and multiplying. Hell - they were good enough to design the atomic bomb and our space program, and that's good enough for me!
Besides, does anyone seriously think that we'll gain God-Like-Powers from quantum computing? The only God Mode I expect from the computer starts with the phrase 'iddqd'.
Just -1, Troll talking to another.
This really have touched me deeply, specially the ending. Somewhat related to the article and perhaps one day it actually happens.
:
Following by Isaac Asimov
The last question was asked for the first time, half in jest, on May 21, 2061, at a time when humanity first stepped into the light. The question came about as a result of a five dollar bet over highballs, and it happened this way:
Alexander Adell and Bertram Lupov were two of the faithful attendants of Multivac. As well as any human beings could, they knew what lay behind the cold, clicking, flashing face -- miles and miles of face -- of that giant computer. They had at least a vague notion of the general plan of relays and circuits that had long since grown past the point where any single human could possibly have a firm grasp of the whole.
Multivac was self-adjusting and self-correcting. It had to be, for nothing human could adjust and correct it quickly enough or even adequately enough -- so Adell and Lupov attended the monstrous giant only lightly and superficially, yet as well as any men could. They fed it data, adjusted questions to its needs and translated the answers that were issued. Certainly they, and all others like them, were fully entitled to share In the glory that was Multivac's.
For decades, Multivac had helped design the ships and plot the trajectories that enabled man to reach the Moon, Mars, and Venus, but past that, Earth's poor resources could not support the ships. Too much energy was needed for the long trips. Earth exploited its coal and uranium with increasing efficiency, but there was only so much of both.
But slowly Multivac learned enough to answer deeper questions more fundamentally, and on May 14, 2061, what had been theory, became fact.
The energy of the sun was stored, converted, and utilized directly on a planet-wide scale. All Earth turned off its burning coal, its fissioning uranium, and flipped the switch that connected all of it to a small station, one mile in diameter, circling the Earth at half the distance of the Moon. All Earth ran by invisible beams of sunpower.
Seven days had not sufficed to dim the glory of it and Adell and Lupov finally managed to escape from the public function, and to meet in quiet where no one would think of looking for them, in the deserted underground chambers, where portions of the mighty buried body of Multivac showed. Unattended, idling, sorting data with contented lazy clickings, Multivac, too, had earned its vacation and the boys appreciated that. They had no intention, originally, of disturbing it.
They had brought a bottle with them, and their only concern at the moment was to relax in the company of each other and the bottle.
"It's amazing when you think of it," said Adell. His broad face had lines of weariness in it, and he stirred his drink slowly with a glass rod, watching the cubes of ice slur clumsily about. "All the energy we can possibly ever use for free. Enough energy, if we wanted to draw on it, to melt all Earth into a big drop of impure liquid iron, and still never miss the energy so used. All the energy we could ever use, forever and forever and forever."
Lupov cocked his head sideways. He had a trick of doing that when he wanted to be contrary, and he wanted to be contrary now, partly because he had had to carry the ice and glassware. "Not forever," he said.
"Oh, hell, just about forever. Till the sun runs down, Bert."
"That's not forever."
"All right, then. Billions and billions of years. Twenty billion, maybe. Are you satisfied?"
Lupov put his fingers through his thinning hair as though to reassure himself that some was still left and sipped gently at his own drink. "Twenty billion years isn't forever."
"Will, it will last our time, won't it?"
"So would the coal and uranium."
"All right, but now we can hook up each individual spaceship to the Solar Station, and it can go to Pluto and back a million times without ever worrying about fuel. You can't do
Will quantum computers let us transcend the human condition and become as powerful as gods, or are they a physical absurdity destined to be exposed as the twenty-first century's perpetual-motion machine?
No, they won't let us defy physical laws and become omnipotent. No, quantum mechanics, being a whole class of physical laws, isn't going to have absolutely no practical use. How about something in between that doesn't come from the over-used plot of a bad sci-fi show?
These posts express my own personal views, not those of my employer
Afair Protein folding is an NP-complete problem.
They solve the problem in real time (way better than Polynomial), by actually folding.
Therefore either
It is possible to solve NP-complete problems in better than polynomial time. We just have to figure out how. Quantum may be a solution
OR
Protein folding is not NP-complete problem.
http://davesboat.blogspot.com/
Just those pesky relativisic effects.
No no no. Factoring is not NP-complete. Sure, its in NP since you can verify a factoring in polynomial time. But the complete part is kind of important, here! Go read a book on complexity theory :)
Luckily, though, tight spandex is a reality today!
http://en.wikipedia.org/wiki/Quantum_computer
and lay off the trolling.
How we know is more important than what we know.
A good list of NP-complete problems can be found here.
____
~ |rip/\/\aster /\/\onkey
The (fundamental) difference is that the bits in the DRAM cells are in a well-defined state of either 0 or 1, but you just haven't measured them yet. In the quantum computer, the qubits are in a superposition of 0 and 1 at the same time.
To be more precise, the 'state space' of a classical bit is, well, 1 bit. Either 0 or 1. In the scenario that you describe, you don't know what the bits are until you measure them, but that is nothing special (imagine another example: tossing a coin with your eyes closed. You don't know the outcome until you open your eyes, but that doesn't mean that anything quantum-mechanical is going on!).
The 'state space' of a qubit, on the other hand, is an angle. Put the '0' result along the x axis and the '1' result along the y axis. Angle 0 corresponds to '0', 90 degrees corresponds to '1', and so on. But the possible physical state is anywhere on the unit circle, not just '0' and '1'. If the physical state of the system is 45 degrees then it really is a mixture of '0' and '1', and you can do interesting things with this state. For example, you can add it to some other state (at a different angle) and get wave-like interference effects.
When you see an electrical arc, you are seeing Nature taking the path of least resistance between two points. Interestingly, if you build a "maze" which requires the arc to pass around a corner, it does just that. In fact, the arc, given sufficient power, can find its way through a maze. Not only can it solve a maze, it can solve it for the shortest path essentially instantly.
NP completeness is only a problem for us because we don't understand the mechanics of the solution. It is not an unsolvable problem, just one that we don't know how to solve yet.
The first generation of computers had low storage / computation space. They grew as engineering progressed. It's the same deal with quantum computers. Five to seven qbits today may turn into 32, 64.. and larger. A quantum computer with "only" 512 qbits could be solving a problem that would normally require 2^512 = 10^154 work (which is more atoms in the universe) is amazing.
What the fuck?! I would outraged when this was at +4, but +5?!
This is misleading. NP-completeness relates to how other problems can be reduced to it. Currently we can't say much about how NP-completeness and complexity relate. We know that if a problem is NP-complete, it must take at least polynomial time and at most exponential time (on a classical computer), but beyond that, we know nothing.
This is factually incorrect. So far we have not found a quantum algorithm to solve any NP-complete problem in less than exponential time.
Ha!
This is factually incorrect. Perhaps you're getting confused by the fact that quantum algorithms are often described in circuit notation. Classical algorithms are also sometimes described in circuit notation, but this is much less common. In any case, quantum algorithms do not bound the size of the input any more than classical computers do.
For instance, quicksort on a classical computer might be "bounded" in that you cannot sort an array of 50 billion petabytes. This is not inherent in the algorithm; it's inherent in our inability to construct a computer with 50 billion petabytes of memory. Similarly, we have not been able to use quantum computers to date to factor integers larger than 15. This limit is not inherent in the algorithm; it's inherent in the fact that engineers have not been able to construct a viable quantum computer to date with more than 5 (if I remember correctly) qubits.
Again, quantum algorithms to not bound the size of their input.
This is factually incorrect. Almost all of the research into quantum computation in the past 10 years has been in the area of quantum complexity. Perhaps you have heard of the BQP complexity class, which was mentioned in the article you were supposed to have read. By the way, BQP can in some way be thought of as quantum computers' "P"; i.e., the class of problems which can viably be computed on a quantum computer in polynomial time.
Quantum complexity very much uses big-O notation (as well as big- notation and any other complexity notation used in classical complexity theory).
Non sequitur. It's not clear at this point. If you could answer that question, you'd probably be drowning in money right now.
I wondered the same thing. I've talked to several experts and have been told that, indeed, a quantum computer can break elliptic curve encryption efficiently. This paper, for example, seems to cover adapting Shor's algorithm to breaking elliptic codes.
"You call it a new way of thinking; I call it regression to ignorance!" -- Operation Ivy
Besides, I thought that "NP-complete" was a pure math term. Since when has pure math had anything to do with physics? I can understand that solving an NP-complete problem in polynomial time could be mathematically/logically impossible, but calling it "violating the laws of physics" should be a misnomer. Would a number that's greater than 2 and less than 1 violate the laws of physics? How about a triangle with 4 sides?
Author here. I thought those who accuse me of drawing a false dichotomy -- between quantum computers as "godlike" on the one hand or a hoax on the other -- might be interested in the following quotes from the actual published article. "although we should not accept the usual hype, in my view it is equally misguided to dismiss quantum computing as science fiction. Instead we should find out what the limits of quantum computers are and what we could really do if we had them." (p. 63) "According to our current understanding, [quantum computers] would provide dramatic speedups for a few problems -- such as breaking the cryptographic codes that are widely used for monetary transactions on the Internet. For other problems, however -- such as playing chess, scheduling airline flights and proving theorems -- evidence now strongly suggests that quantum computers would suffer from many of the same algorithmic limitations as today's classical computers." (p. 63) "If a large, ideal quantum computer would face most of the same limitations as our present-day classical computers do, should the physicists working on the extraordinarily hard task of building even rudimentary quantum computers pack up and go home? I believe the answer is no, for four reasons..." (p. 65) "To some, the apparent limitations of quantum computers might come as a letdown. One can, however, give those same limitations a more optimistic spin. They mean that although certain cryptographic codes could be broken in a world with quantum computers, other codes would probably remain secure..." (p. 69) In short, the precise misconception that I wrote my article to try to combat, is the one I then get accused of! Reading an article can, indeed, provide useful clues about its contents.
From a mathematic point of view, solving an NP-complete problem in polynomial time is not a problem at all. The class NP is defined as the set of problems that a non-deterministic Turing machine can solve in polynomial time.
It seems as if most of the readers of Slashdot think quantum computers are the same as nondeterministic computers. Well, they are not. Nondeterministic Turing Machines (NTMs) are those that follow every computational path simultaneously and accepts if any path accepts. Quantum computers are more like Probabilistic TMs, which take a random branch at every step. The problems solvable in polynomial time by NTMs define NP, and RTMs define RP. The classes x-complete are the "hardest" of the problems in the class x. It is believed to be highly unlikely that any NP-complete problems are polytime on QCs.
These are very informal definitions. Look at
http://en.wikipedia.org/wiki/Nondeterministic_Turing_machine
http://en.wikipedia.org/wiki/Probabilistic_Turing_machine
http://en.wikipedia.org/wiki/Quantum_computer#Quantum_computing_in_computational_complexity_theory
for more details.
And yes, I am a mathematician.
Forty two.
My amazing wife - Artist, Author, Philosopher - Laurie M
Untill he posts a reply, the cat both exists and doesn't exist at the same time.
What if Tetris was invented by Nazis?
Unless the post was from a computer, which may or may not exist, or may both exist and not exist at the same time, of which he would be an AI construct inside that brings up a whole new level of abstractness that... Oh dear, I've gone cross-eyed.
Your ad here.
Shor's paper -- the one that showed how quantum computers can factor efficiently -- also showed how they can solve the discrete log problem efficiently (and thereby break Diffie-Hellman among other cryptosystems). Shortly afterward, Boneh and Lipton gave a simple extension to break elliptic curve cryptography (the key fact that makes this possible is that elliptic curve groups are abelian). Basically, the one class of public-key cryptosystems that's *not* known to be breakable with quantum computers, is the class for which the encryption function consists of applying a linear transformation and then adding random noise. This class includes, e.g., the McEliece and Ajtai-Dwork cryptosystems, as well as more recent lattice-based cryptosystems due to Regev and Peikert-Waters. Breaking this class of cryptosystems with a quantum computer reduces to solving the "hidden subgroup problem over the dihedral group," which (in contrast to the HSP over abelian groups) we don't yet know how to do. I should mention that, if you're content with private-key cryptography, then we have *plenty* of examples not known to be efficiently breakable with a quantum computer (even DES, suitably generalized to n-bit keys, would probably suffice).
It looks to me as if Grover's Algorithm should allow solving every NP problem in time proportional to the square root of the minimum number of operations a classical computer would require.
This moves a huge class of problems from not solvable in less than millions of years to solvable in about one year, which seems like a pretty big impact to me...
I understand that as a complexity scientist, reduction that only halves the exponent of the number of operations is of merely practical importance and therefore barely worthy of notice, but to the rest of the world it could be a Big Deal.
In brief, the answer is yes, you can use a variation of fuzzy logic to emulate a quantum computer. Unfortunately no complexity gains can be made as the emulation cannot exploit a superposition to calculate in parallel.
While both a fuzzy bit and a qubit could have a state like 0(75%) 1(25%), having a computer perform a fuzzy operation requires two computations (one for each possible state) whereas a quantum computer can apply a single operation to the qubit and have it affect both states.
One difference however, is that for qubits the weights on each state are complex (as opposed to real-valued). This means that interference can occur when, for example, the weights on two qubits being combined have the same magnitude but opposite phase. The true awesome magic of Shor's algorithm is how the computation expands into a massive superposition (parallel computation) and then manages to exploit the interference to return to just a single possible answer before it comes time to measure.