PerspectiveComputer Science

Randomness in Quantum Computation

See allHide authors and affiliations

Science  19 Dec 2003:
Vol. 302, Issue 5653, pp. 2076-2077
DOI: 10.1126/science.1092977

You are currently viewing the summary.

View Full Text

Log in to view the full text

Log in through your institution

Log in through your institution

Summary

Introducing randomness by computationally flipping a coin can increase the efficiency of classical computer algorithms. Quantum computing may also benefit from the introduction of randomness, but doing so is less straightforward because at any step, a quantum computer can follow a continuous set of possible paths. In his Perspective, Paz explains that a good approximation of randomness can be introduced more easily than was anticipated. He highlights the report by Emerson et al., who have devised a two-step procedure that allows the efficient implementation of quantum coin-tosses in an approximate but useful way.