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?
“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 🙂
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.
Hi Dave. We made a list of important open questions in QIS for the Report of the Workshop on Quantum Information Science last spring. Some are nearly in “nugget” form, though some are a bit more technical, and they span physics and experiment as well as computer science. The list starts on page 21 of the report.