The Power of Quantum Computers and Entanglement

In the Section 4.2, entitled Quantum Algorithms of [1], R. Jozsa argues that the property of entanglement is the key property for the power of quantum computers. In quantum theory it is possible to represent a superposition of 2^n states using n 2-level systems, because of the phenomenon of entanglement. A general superposition of this kind requires only a linear amount of physical resources to represent it, since at most each of the n systems needs to be separately excited. Hence, although superposition occurs in classical systems, the phenomenon of quantum entanglement leads to an exponential saving of physical resources needed to represent large superpositions.

“Natural quantum physical evolution may be thought as a processing of quantum information. Thus the viewpoint of computational complexity reveals a new bizarre distinction between classical and quantum physics: to perform natural quantum physical evolution Nature must process vasts amounts of information at a rate tha cannot be matched in real time by any classical means, yet at the same time, most of this processed information is kept hidden from us. However, it is important to point out that the inherent inaccessibility of quantum information does not cancel out the possibility of exploiting this massive information capability for useful computational purposes. Indeed, small amounts of information may be extracted about the overall identity of the final state which would still require an exponential effort to obtain by classical means.’’

[1] Dirk Bouwmeester, Artur Ekert and Anton Zeilinger (Eds.) The Physics of Quantum Information, Springer, 2001.