Quantum Computing Explained

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 ...