Theory Matters Vision Nuggets

One result of a workshop held in 2008 that "broad research themes within theoretical computer science...that have potential for a major impact in the future, and distill these research directions into compelling "nuggets" that can quickly convey their importance to a layperson" is this set of nuggets. Among the summary of nuggets we find quantum computing and three questions:

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

(1) First, can quantum computers actually be built? Can they cope with realistic rates of decoherence -- that is, unwanted interaction between a quantum computer and its external environment? Alternatively, can we find any plausible change to currently-accepted laws of physics such that quantum computing would *not* be possible?

(2) Second, what would the actual capabilities of quantum computers be? For example, could they efficiently solve NP-complete problems? Though quantum computers would break many of today's cryptographic codes (including RSA), can other practical codes be found that are secure against quantum attacks?

(3) Third, does quantum computing represent the actual limit of what is efficiently computable in the physical world? Or could (for example) quantum gravity lead to yet more powerful kinds of computation?

I would have added (a) are quantum computers useful for physical simulation of chemistry, biology, and physics?, (b) can quantum computing theory overcome roadblocks that have plagued classical computational complexity?, and (c) is quantum computing useful for understanding how to build classical algorithms for simulating physical systems?


More like this

An interesting paper on the arXiv's today, arXiv:0908.2782, "Adiabatic quantum optimization fails for random instances of NP-complete problems" by Boris Altshuler, Hari Krovi, and Jeremie Roland. Trouble for D-wave? Adiabatic quantum algorithms are a set of techniques for designing quantum…
Lately I've been giving a lot of thought to a question that I'm nearly constantly asked: "So...[long pause]...are you a physicist...[long pause]...or are you a computer scientist?" Like many theorists in quantum computing, a field perched between the two proud disciplines of physics and computer…
Over at Emergent Chaos I found an article which throws down the gauntlet over quantum computers. And there isn't anything I cherish more than gauntlets thrown down! Note: I should preface this by saying that I don't consider myself a over the top hyper of quantum computers in the sense attacked…
Shor's algorithm is an algorithm for quantum computers which allows for efficiently factoring of numbers. This in turn allows Shor's algorithm to break the RSA public key cryptosystem. Further variations on Shor's algorithm break a plethora of other public key cryptosystems, including those based…

Are there any serious arguments that quantum computers can't be built? We'll have to see what happens in the next decade, but judging by progress over the last decade, I think scalable systems are coming sooner rather than later.

Cracking lattice-based crypto reduces to non-abelian HSP, and so should be immune to Shor's algorithm.

"Cracking lattice-based crypto reduces to non-abelian HSP, and so should be immune to Shor's algorithm."

Maybe. I'd we willing to wager the opposite...given sufficient odds :)

John Preskill, thank you for that link to the "Report of the Workshop on Quantum Information Science", which I read with great interest.

As it so happens, I earlier this morning read your 1998 article "Quantum Computing: Pro and Con", which also has a list (fourteen items long) that is captioned: "Some possible objections to quantum computation, and some responses."

The two lists are in close accord excellent. This is good very news in terms of the stability of the field. ... but perhaps not-so-good news, in the sense that back in 1999 folks hoped for items to be crossed off much faster than they have been.

Here I have three concrete suggestions to make.


Suggestion 1: The QIS community should stop using the use of the words "skeptical" and "skepticism" in connection with quantum computation.

These phrases have an honorable pedigree in science and engineering, but they can be misused too. Suppose, for example, that 19th century Riemmannian geometers and 20th century general relativists had been called "skeptics of Euclidean geometry" ... would any useful purpose have been served?

As background, I've been drafting (for my own amusement) an "Alice and Bob" dialog decrying the phrase "quantum skeptic*"; this me to search for early uses, of which "Pro and Con" was one of the earliest and most influential ... which gives its author unusual influence regarding its continued use.


Suggestion 2: Broaden the objectives of QIS to include a challenge that Scott Aaronson was (AFAICT) the first to pose: "Carry out any physical experiment whose resulting dataset provably cannot be simulated with PTIME resources (subject to standard assumptions of complexity theory)". This objective includes quantum computation as a special case, but is broader and easier (and IMHO, even more thought-provoking).


Suggestion 3: In documents like the "Report of the Workshop on QIS", it might be good to be explicitly open to the possibility that nature's quantum state-space is *not* a Hilbert space, but rather a (more general) Kählerian state-space. There are two good reasons for this: first, this possibility has a long and distinguished academic pedigree; second, pretty much all of today's practical quantum simulation codes pullback onto Kählerian state-spaces anyway, thus the QIS community would naturally benefit from adding to its charter the study of this difficult (and economically vital) activity.

In my imagination, "Alice and Bob" have been discussing these ideas during a memorial breakfast for Vladimir Arnol'd ... who (IMHO) would have whole-heartedly approved of these ideas ... and simultaneously (perhaps) been hugely skeptical of them.

Which is good! :)

Many thanks for this very insightful post and comments along with link to the NSF report, most helpful.

I'm actually currently conducting a web based survey on Quantum Information Technology aiming at assessing the general public and field experts knowledge and perception of the technology. I would like to invite readers of this site to participate in this study. The questionnaire is available at and takes about 15 minutes to complete. The data collection will be running from March to September 2010 and you can participate at any time. Final results will become available in the spring of 2011.

This effort is being conducted in the context of a Master thesis aiming at better understanding the challenges facing Quantum Information Technology (QIT) in order to successfully integrate into the existing "classic" Information Technology (IT) framework. For further information or if you have any question, visit or contact

Nature seems to be able to do it (quantum computing) so why would we think we can not mimick nature?

"What may prove to be this studyâs most significant revelation is that contrary to the popular scientific notion that entanglement is a fragile and exotic property, difficult to engineer and maintain, the Berkeley researchers have demonstrated that entanglement can exist and persist in the chaotic chemical complexity of a biological system.

âWe present strong evidence for quantum entanglement in noisy non-equilibrium systems at high temperatures by determining the timescales and temperatures for which entanglement is observable in a protein structure that is central to photosynthesis in certain bacteria,â Sarovar says.…

M Morris -- Quantum entanglement is a necessary but not sufficient condition for quantum computation. In the case of photosynthesis, there is certainly evidence for coherence and entanglement, but there is also evidence *against* plants performing some sort of quantum computation. The careful structure and symmetry necessary for quantum computation does not exist in most cases.