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 practica