Quantum computing: beyond the limits of conventional computation†

^†This research was supported by the Natural Sciences and Engineering Research Council of Canada.

Abstract

The quantum model of computation not only offers entirely new ways to manipulate information, but also allows information processing tasks to be formulated in unconventional, genuine quantum mechanical terms. We show that the task of distinguishing among entangled quantum states combines entanglement and non-determinism in a way that makes the quantum solution impossible to simulate on any classical machine (even one equipped with the same measurement capabilities as the quantum computational device). A new class of information processing tasks is thus uncovered whose members are readily carried out by a quantum computer, yet are impossible to perform on any classical machine (whether deterministic or probabilistic). In the broad, unconventional context created by quantum mechanics, the computational power of a quantum computer is therefore strictly greater than that of a classical computer.

Keywords:

• Quantum computation
• Classical computation
• Quantum information
• Entanglement
• Distinguishability
• Computational power

Notes

^‡ [email protected]

^†This research was supported by the Natural Sciences and Engineering Research Council of Canada.

^‡Seen as a particular instance of superposition involving multiple qubits.

^¶For the case n = 1 the term entanglement is inappropriate. A single qubit is just in a balanced superposition of 0 and 1. However, we still choose to use entanglement throughout our exposition because for any n>1 the superposition is actually an entangled state.

^§Including those performed in other bases than the standard computational basis.

Additional information

Notes on contributors

Selim G. Akl

‡ ‡ [email protected]