Theory Matters Wiki

Summary | Rationale | Powerpoint | JPG Slide | JPG Image | Credits| Comments | All Nuggets

Efficient Computation in the Physical Universe

Quantum computing is revealing remarkable links between the central unsolved problems of theoretical computer science and the laws of physics. These links are already forcing a revision in our understanding of the physical world.

Summary

What is the most powerful kind of computer compatible with the laws of physics? Which problems can computers ever solve within reasonable constraints of time and memory? These questions took on a new character fourteen years ago, with Peter Shor's discovery that a quantum computer could factor integers in polynomial time, and thereby break the cryptographic codes on which most of the world's electronic commerce depends. A quantum computer is a proposed device that would exploit the counterintuitive nature of quantum physics to solve certain problems exponentially faster than we know how to solve them with any computer today.

Rationale

In the wake of Shor's algorithm, one can identify three basic questions:

Theoretical computer scientists have already contributed basic insights about all three of these questions. For example, they played a central role in proving and extending the Fault-Tolerance Theorem, which says that once a quantum computer's noise rate falls below a certain critical point, decoherence can be corrected faster than it occurs, and hence arbitrarily long quantum computations are possible in principle. On the other hand, theoretical computer scientists also discovered evidence that quantum computers would face major limitations in solving NP-complete problems, as well as related tasks such as breaking cryptographic hash functions. Finally, they studied hypothetical models beyond quantum computing, for instance involving topological quantum field theories and closed timelike curves.

Contributors and Credits

Scott Aaronson, Bhaskar DasGupta, Richard Karp, Rocco Servedio, Diane Souvaine

Image Ideas

cosmos/Hubble telescope with graph/matrix/visual representation of a combinatorial problem superimposed or contrasted. (The intended gist is that the entire physical resources of the universe are being harnessed to solve some computational problem.) Something like the title slide of

http://www.scottaaronson.com/talks/npcomplete.ppt

Comments

• to give feedback on this nugget, just add another bullet to this list.
• This [the tagline] sounds cavalier. It is obvious that the fundamental laws of physics, being incomplete and inconsistent, will require revision, regardless of any CS issues. Moreover, quantum computing ideas are based on mathematical formalism used in physics. Elevating extremes of math formalisms to the level of physical laws is a hyperbola. Physical laws have limited domains of applicability and do not claim validity of all formal extrapolations to radically different domains. I would suggest to try a more humble rewording. -Leonid Levin
• There seem to be other exaggerations, too. For instance, my understanding is that the quantum error-corrections can handle only restricted types of noise and there are no reasons to expect that only such types of noise would interfere. I think the nugget would benefit from a more sober assessment of the positive side of the idea. -LL.
• It would be nice to add a forward-looking sentence or two to the end of the summary (I see that the rationale talks about research directions in detail, it'd be nice for the summary to also convey the sense that this is an ongoing subject of research.) - Salil
• Minor comment: "major limitations" -> "major obstacles" (soften since these are only black-box lower bounds, not proofs of impossibility) - Salil
• On the image, it may be helpful to the designer to get a better sense of what you mean by "combinatorial problem". - Salil
• It may help to set the stage by talking about current computers being based on the Turing machine which is basically a logical device that could be implemented using in the physical world using electro-physical devices well above the quantum level of the universe. - Richard L.
• For lay people it may be important to distinguish between an ideal quantum computer which is like a mathematical theory and the implementation of one, which has not really been done yet for some of the reasons discussed. Shor's theorem is a mathematical theorem about ideal quantum computers and not actual ones. - Richard L.
• As a math concept, QC is just another model, like unit cost model (which, too, factors in polynomial time :-). As a physical idea, it is an analog device. In the absence of evidence to the contrary, I would presume analog devices to be exponentially LESS efficient than digital ones. This is an interesting area of research, but making a NUGGET out of it would be feeding a risky hype. Like cold fusion, this may bring temporary benefits at the expense of long-term discredit. -Leonid.
• I think it is important that the ideal Turing machine to a degree drove the design and implementation of real computers. Turing's Universal Machine, is a stored program machine just like all reak computers today. The same thing is happening now with the theory of quantum computers driving the implementors, although the theory is still incomplete as to whether quantum computers can be built in the physical world. - Richard L.
• I am not sure I get the tagline. A quick reading suggests that both current theories are incompatible and one will have to be "fixed." The word "revision" suggests something faulty. If we want to say that either theory will need to be improved then that's fine (but, on the other hand, isn't that true of everything?) Also, why "physical theory" and not "physics"? Is it just for the sake of parallelism with computation theory? - Bernard
• Note from designer Elaine Park: Since this idea will lead to the revision of fundamental theories (in a way rewriting history), this design takes on the feel of a classical text. I thought the image suggestion was great, but if my DIY combinatorial problem is distractingly nonsensical, please let me know!
• In line with Bernard's suggestion above, what do people think about deleting the 2nd sentence of the tagline and just keeping the first one? This seems like it might be punchier and clearer. On a different topic, I like the image. -- Rocco
• The tagline should be shorter and end with a question about what is to solve in the future. -- Richard
• Suggested new second sentence of tagline: "These links are already forcing a revision in our understanding of the physical world." --Scott
• Uploaded ppt with minor change (text box more transparent, font larger and bolder for readability). - Salil
• I would replace "change to" before "currently-accepted laws of physics" with something like "reformulation of". Quantum Computing is not based on known laws of physics (which all have limited domain). They are based on extremes of math formalisms used in formulation of these laws. These extremes are known to contradict other fundamental laws of physics, and so cannot be physical laws themselves. Also, before "decoherence can be corrected": I would add "certain types of". -Leonid Levin.