Question of the week, 29.12.2010
Quantum computing is a fascinating field. That’s the world (quantum mechanical), where “some of impossible is possible”. For example efficient factoring of integers (Shor’s algorithm). But what’s the source of quantum computers’ power?
People believed that it’s entanglement – a quantum mechanical quality describing the interdependence of measurements made between parts of a quantum system. Entanglement plays a key role e.g. in quantum teleportation, superdense coding, quantum pseudotelepathy and many many others. In fact, it has been shown that without enough entanglement existing at some point in the process of a computation, quantum computer cannot outperform a classical one.
It’s quite surprising that as was shown recently (see references in [2]), also opposite is bad. Too much of entanglement in case of so called quantum one-way computing (one of analogs of a circuit model) causes that this computational model cannot outperform classical computers. So let me cite Dave Bacon [2]: “Entanglement, like most good things in life, must be consumed in moderation.”
References:
[1] Nielsen and Chuang; Quantum Computation and Quantum Information; Cambridge University Press, 2000
[2] http://physics.aps.org/articles/v2/38
Libor Veis