# 9

# QUANTUM ALGORITHMS

An *algorithm* is a set of instructions used to perform some well-defined task on a computer. A large part of the desire to develop a quantum computer has come from the discovery that some algorithms work dramatically better on a quantum computer than they could ever work on a classical computer. This is because the nature of quantum systems—captured in superposition and interference of qubits—often allows a quantum system to compute in a parallel way that is not possible even, in principle, with a classical computer.

It was discovered that given a function *f* (*x*), a quantum algorithm is capable of evaluating the function at multiple values of *x* simultaneously. As we will see below, a quantum algorithm highlights one of the central tugs-of-war that exist in quantum theory. A qubit can exist in a superposition of states, giving a quantum computer a hidden realm where exponential computations are possible. In other words, the fact that a quantum system can exist in a superposition or linear combination of states allows us to do simultaneous parallel computations that cannot be done even, in principle, on any classical computer. This feature allows a quantum computer to do parallel computations using a single circuit-providing a dramatic speedup in many cases. However, since measurement finds a qubit in one state *or* the other—frustratingly we find that if we give a quantum computer *n* inputs we only get *n* outputs.

Nature allows us to get around this to a certain extent ...

Get *Quantum Computing Explained* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.