We propose an implementation of a quantum computer to solve Deutsch's problem, which requires exponential time on a classical computer but only linear time with quantum parallelism. By using a dual-rail quantum-bit representation as a simple form of error correction, our machine can tolerate some amount of decoherence and still give the correct result with high probability. The design that we employ also demonstrates a signature for quantum parallelism which unambiguously distinguishes the desired quantum behavior from the merely classical. The experimental demonstration of our proposal using quantum optical components calls for the development of several key technologies common to single photonics.
Chuang et al. (1995) studied this question.