What are the prospects for quantum computation? In this section we discuss the search for other algorithms and describe the largest difficulty in building a quantum computer.
In this paper we discussed a single algorithm yielding an exponential speed-up over conventional methods: Effectively the calculation of the period of a long sequence. To date this is the only algorithm displaying such a speed-up. This algorithm was applied to a traditional computer-science problem, factoring, only by recognizing a deeper structure within that problem. This requirement appears to be a general one: Quantum parallelism will only yield an exponential speedup in problems whose structure avoids the need to try exponentially many solutions [28,29,30,31]. Thus, a brute force approach to some of the hardest computational questions, known as NP-complete problems, will not succeed with the aid of quantum parallelism. Any progress for such problems will require finding a deeper structure within them. Instead, quantum computers are likely to be most useful for simulating or manipulating small quantum systems [6].
How difficult will it be to build a quantum computer? Even within apparently small atomic-scale systems, quantum computation runs on the enormous size of Hilbert space. Quantum computation involves building a trajectory from a standard initial state to a complex final state. The main difficulty is keeping to this trajectory. To fail is to be lost in Hilbert space. The largest problem is hypersensitivity to perturbations, shifting the computational trajectory randomly from its path. Such perturbations come from an unintentional coupling to external noise [32]. It is too soon to predict the gravity of this problem. It appears, though, that there is no fundamental limit to how well we can isolate a quantum system. Currently, several implementations are being considered by theoreticians and experimentalists worldwide [17,18,33,34,35,36,37]. One promising scheme involves ion-traps [34,35]---the next generation of atomic-clock standards. Over the next two decades conventional computers will approach the atomic scale, perhaps quantum computers will get there first.