Keep that argument in mind as you read the following paragraph from David Bacon.
If today someone was to prove that P does not equal NP for a classical computer, would we be satisfied? Well certainly we would be very excited and this would be the breakthrough of the century in computation, but because the universe is fundamentally quantum mechanical, would we really be satisfied that the intractability of NP-complete problems had been shown? Quantum computers open up an entire bag of worrying about the foundations of computational complexity. It is dangerous to say this, of course: if this view is correct, then the hard work of classical computational theory might have been in vain. But if this is the correct view, then we need to begin weaning ourselves off of the classical model of computation.Dangerous indeed. Bacon is not the first one to make such statements, Gilles Brassard made much stronger pronouncements as far back as 1990.
Did the theory of relativity mean the hard work of classical mechanics was in vain? Of course not. When we drive a car we don't need to worry about relativistic effects, they simply don't amount to much at that level.
We don't know how quantum mechanics will actually play out in a computer that would require the entanglement and manipulation of tens of thousands of quantum bits. Maybe we can harness the full power of quantum computation, maybe we can't. At this point we simply don't know.
I support research in quantum complexity, as long as quantum computing remains a possibility we should try and understand its computational power. But not until we all have fast quantum computers on our desks should we even think of abandoning classical complexity. And in our current state of affairs, where creating a quantum computer that factors faster than my daughter is a pipe dream, classical computational complexity serves us very well indeed.
But the question is this: would you advise grad students wanting to start research in complexity theory to focus on quantum complexity ?
ReplyDeleteOne answer is: "depends on what they are interested in". But for a "blank slate" student who is interested in all aspects of complexity, might their career not be furthered better by focusing on quantum complexity, if there is a chance 10-15 years down the road that quantum complexity will define the basic language of computation?
Suresh: I would suggest a student pick as their subfield the area in which the *incremental* results excite and interest them.
ReplyDeleteI think it would be pretty easy for someone to be interested in all of the big results, but research is not about big results all the time. I think we would all be interested in the big results of quantum complexity, but that doesn't mean we'd all be interested in the smaller results that would need to come first.
Career-wise it would be just as good to focus on randomness or cryptography.
Wait a second. No one has shown that any NP-complete problem has an efficient quantum algorithm right? While factoring would be easy, there is no reason to believe that every NP problem is efficiently solvable. Until someone shows even that I think that this pronouncement is a bit off.
ReplyDeleteMy intuition is that though Factoring and "intermediate" problems may be quantum polytime, not all of NP is. Does anyone know of any results that would suggest this? I.e. something like SAT in solvable in quantum polynomial time implies PH collapses?
Macneil,
ReplyDeleteI'd have to nitpick on the "we'd all be interested in the smaller results that would need to come first". The problem with many subfields of theory now is that you can't poach: i.e you can't easily wait around for the smaller results and then pounce to prove the big one, because you have to invest a significant amount of brain space in understanding the field. Hence, in order to prove (attempt to prove) big results in quantum computing, one would need a lot of training in it, and I don't think that (say) doing a course or two is sufficient; one would need to invest some time doing research.
I am reminded of the situation in physics, where it is now popular to lament the fact that an entire generation of phyicists was dispatched off into string theory because that was the hottest theory of everything. My question about quantum computing should be viewed in that light.
I love the analogy with the flying cars!
ReplyDeleteAs you point out the way to argue against what I said, is to argue that the model of quantum computing will never be realized. Of course my view will be shared by those who are confident that large scale quantum comptuers will be built, and will not be shared by those who believe large quantum computers will never be built. This is a very pragmatic point of view, and there seems to me nothing wrong with it.
However, I would also like to point out that there is a very good reason for studying quantum complexity theory even if we cannot build quantum computers. This is that studying quantum complexity classes may lead to proofs relevant to classical computational complexity. We already have (some) evidence that quantum complexity classes can lead to simple proofs of classical results, for example in Scott Aaronsons PP closed under intersection result (OK, I'll admit I'm not a great judge of this because I don't understand the classical results well enough to judge Scott's proof "simpler" Simple is in the eye of the beholder, eh?) I believe we should study quantum complexity theory for the same reason we study all sorts of crazy complexity classes: because they might yield new insights into our fundamental problems. Further there is always the possibility that it might be much easier to prove BQP<>NP than to show that P<>NP?
Along these lines, I would also point out that as mathematicians and physicists have learned over the years, mathematicians ignorning physics and physicists ignoring mathematics is usually not a wise course. The "miraculous" connection between these two disciplines serves to me as a very strong warning to computer science: ignore physics at your own peril! (am I reaching Brassard's level yet?) In light of the strong connections between math and physics, we must ask ourselves, why are there no such similar connections between computer science and physics?
Following Scott Aaronson's usual arguments, Dave's reasoning already has a classical analog using randomized computation:
ReplyDeleteShowing P not equal to NP so far does not rule the possibility that NP is contained in BPP.
Few would argue about the ability to build randomized computing machines. Of course it seems more likely that P=BPP than P=BQP but the above possibility does not change the importance of resolving P versus NP.
Paul Beame
Paul, again "difference" is in the eyes of the beholder, but I'd argue that understanding randomization is not something so fundamentally different as understanding quantum operators. Maybe I'm just dating myself here :)...
ReplyDeleteAnd then there are the complexity theorists trying to prove lower bounds for AC_0 thinking "Flying cars? I'm still riding a tricycle to work!"
ReplyDeleteThe argument that studying quantum computation is good because it might lead to results in classical complexity is a little bogus; there has to be some additional motivation (e.g. some evidence that studying BQP is better than studying WXP where WXP is some arbitrary computational model).
I think one can make a case for BQP because (1) it seems to have more power than P and (2) it probably does not capture all of NP. On the other hand, I think the cases where quantum studies lead to classical theorems (kerenidis-dewolf, aaronson, aharonov-regev) just offer evidence that _it helps complexity theorists to know more mathematics_.
Scott, if you're so upset about crappy papers that "put Q in various places," why not do something about it? Prove a theorem that gives us conditions under which we can take a classical result and "quantum"-ize it.
ReplyDeleteIf you're lucky, all these "crappy" papers and more will follow from the theorem. If you're not, then you won't be able to find a fully general theorem. Then the results that don't follow may tell us something interesting about the relationship between classical and quantum computation, rendering those "crappy" papers maybe not so crappy after all.
Quantum models of computing? No, why settle for just a piddling exponential speed-up for some NP-intermediate problems, when there are much bigger gains to be made? For example, here's the concluding paragraph from "Turing's Ideas and Models", by E. Eberbach, D. Goldin, and P. Wegner (in Alan Turing: Life and Legacy of a Great Thinker):
ReplyDelete"We expect super-Turing computation to become a central paradigm of computer science. However, we cannot claim that the super-Turing models, as described in this chapter, are definitive and complete. Most likely, they will be superseded in the future by models that are even better and more complete for problem solving, in the never ending quest for a better description of reality."
Hmmmmm, on second thought, I don't think the classicists have anything to worry about.
One pro of classic complexity is that it seems to describe formal processes of proof, reasoning and some types of communication. When we humans communicate formally, be it about mathematical proofs or just about the latest football game, we use "classic" mechanisms. I'm not aware ('though I have no idea) of anyone verifying proofs quantumly, and despite some claims, I find it hard to believe that quantum effects have much to do with what happens in the human brain from a computational point of view. Theory is great when it helps hardware / software engineering directly, but that's not its only goal.
ReplyDeleteGilad.
Another thought/opinion: I think large scale quantum computers are only slightly more likely to be built than a Blum-Shub-Smale Turing machine.
ReplyDeleteKurt has a good point.
ReplyDeleteI also read some of the book he mentions. A witty paper by Martin Davis in this book citicizes harshly the "Hyper-computation" community (i.e., super-Turing computations).
The analogy doesn't fly. Traffic rules are prescriptive laws while the rules describing the behavior of the most powerful realizable computer are descriptive laws (we set the former but discover the latter).
ReplyDeleteRonald de Wolf
To come at this from a different angle, see the ACM's 2004 G�del Prize citation, and the report that was ultimately published as the first of the cited papers.
ReplyDeleteI attended a lecture this past summer in which Michael Nielsen suggested (if I understood him correctly) that quantum computation was to classical computation what analytic functions were to real functions. That is, a powerful extension of a classical idea that makes, e.g., doing integrals much easier.
ReplyDeleteIn particular, he suggested that proving P ne NP might be much easier in the quantum domain, essentially because the behavior of a quantum computer is analytic rather than binary.
So, for example, if it could be shown that noisy quantum computers can solve problems in P, but cannot not solve problems in NP, in consequence of an inadequate total volume of quantum phase space computational trajectories, it would follow that P ne NP. Just like evaluating a real integral by analytic continuation, such a proof would have no easily disentangled classical version.
From this point of view, even if it should happen quantum computers never prove technologically viable, and even if the set of P-time quantum algorithms is limited, quantum computation still represent a very powerful mathematical abstraction.
In fact, extending the above thread, a contrarian line of research would be to inject so much noise into a quantum computer that it became algorithmically weaker than a classical computer.
ReplyDeleteThen we ask, what can't these "wimpy" quantum computers do?
If the answer is, wimpy quantum computers can do P but can't do NP, then P ne NP.
Why would there be any conceptual advantage is studying wimpy quantum computers, relative to classical computers?
Hmmmm it is well known that noise is equivalent to covert measurement, so a wimpy quantum computer is equivalent to a "secret sharer" of information.
So the question is, how much information can a "secret sharer" covertly steal from an operating quantum computer, and still have it successfully complete P-time algorithms?