What Is a Quantum Algorithm?

Ray Hawk

A quantum algorithm is a set of computer instructions for analyzing problems that is not based on classical mathematical or probabilistic calculations, but instead uses the unique nature of quantum reality where a single bit of data can represent two opposing values, such as both a one and a zero in binary logic. In the strictest sense, a quantum algorithm requires a quantum computer to function, which does not exist in any manufactured form as of 2011. Theoretical computer science, however, has at least created analogues to true quantum algorithm computation as of 2011, with examples such as the Deutsch, Shor, and Grover algorithms.

The Deutsch quantum algorithm was invented in 1985 and named after the Israeli-British physicist David Deutsch who works at Oxford University in the UK. Deutsch's algorithm, like most sets of computer instructions in quantum computing, are valued for their ability to act as a sort of shortcut to processing problems and, therefore, problem solving at the microchip level. In standard probabilistic computing, all possible states for solutions to problems must be given a distribution value and calculations are carried out on all of them to determine which response or value has the highest probability of being correct. In quantum computing using the Deutsch algorithm, every possible solution state is combined into what is known as a unit vector that moves towards a specific type of solution or state transformation. This relies on a principle known as quantum superposition as applied to mathematics, where solutions to problems are expected to exist in all possible states simultaneously, essentially eliminating the need for lengthy probabilistic logic processing.

The Shor and Grover quantum algorithms act in similar fashion, but are designed for specific types of computer processing. The Shor algorithm is used for mathematical factoring, and the Grover algorithm for searching for meaningful data in either computerized lists or databases that lack a definable structure. Though both algorithms are run on classical computer systems that do standard types of processing, their design has been demonstrated to be far superior to classic probability-based algorithms for the same types of tasks. Shor's algorithm is exponentially faster and Grover's is quadratically faster, or of a squared value faster than standard computing methodology. The Shor quantum algorithm is named after Peter Shor, an American professor of mathematics who developed it in 1994, and the Grover quantum algorithm is named after Lov Grover, an Indian-American computer scientist who developed it in 1996.

One of the unique aspects of quantum computing is that calculations are not based on discrete values that can be arbitrarily separated out, but instead exist in a state of quantum entanglement. The standard values in a calculation enter a state of superposition where they are all manipulated exponentially as amplitudes or ranges of value and each bit or qubit of information is said to be entangled with each other. This makes each data point interdependent and not a discrete value as in traditional computing, which is the foundation of how quantum algorithms can be so much faster at processing data than traditional algorithms are.