Quantum algorithm

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or entanglement.

All problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are undecidable using classical computers remain undecidable using quantum computers. The reason that makes quantum algorithms interesting is that they might be able to solve some problems faster than classical algorithms.

The most well known algorithms are Shor's algorithm for factoring, and Grover's algorithm for searching an unstructured database or an unordered list. Shor's algorithms runs exponentially faster than the best known classical algorithm for factoring, the general number field sieve. Grover's algorithm runs quadratically faster than the best possible classical algorithm for the same task.

Overview

Quantum algorithms are usually described, in the commonly-used circuit model of quantum computation, by a quantum circuit which acts on some input qubits and terminates with a measurement. A quantum circuit consists of simple quantum gates which act on at most a fixed number of qubits, usually 2 or 3. Quantum algorithms may also be stated in other models of quantum computation, such as the Hamiltonian oracle model.

Quantum algorithms can be grouped together by the main techniques used by the algorithm. Some commonly used techniques/ideas in quantum algorithms include phase kick-back, phase estimation, the quantum Fourier transform, quantum walks and amplitude amplification. Quantum algorithms may also be grouped by the type of problem solved: algebraic, number-theoretic, combinatorial, etc.

Algorithms based on the quantum Fourier transform

The quantum Fourier transform is the quantum analogue of the discrete Fourier transform, and is used in several quantum algorithms. The Hadamard transform is also an example of a quantum Fourier transform.

Deutsch–Jozsa algorithm

Main article: Deutsch–Jozsa algorithm

The Deutsch–Jozsa algorithm solves a black-box problem which provably requires exponentially many queries to the black box for any deterministic classical computer, but can be done with exactly 1 query with a quantum algorithm.

Simon's algorithm

Main article: Simon's algorithm

Simon's algorithm solves a black-box problem exponentially faster than any such classical algorithm, including probabilistic algorithms.

Shor's algorithm

Main article: Shor's Algorithm

Shor's algorithm solves the discrete logarithm problem and the integer factorization problem in polynomial time, whereas the best known classical algorithms take super-polynomial time.

Hidden subgroup problem

The hidden subgroup problem is a generalization of many problems, such as factoring, graph isomorphism and certain lattice problems. There are efficient quantum algorithms for the Abelian hidden subgroup problem. Efficient quantum algorithms are known for certain non-Abelian groups. However, no efficient algorithms are known for the symmetric group (which would give an efficient algorithm for graph isomorphism) and the dihedral group (which would solve certain lattice problems).

Estimating Gauss sums

A Gauss sum is a type of exponential sum. The best known classical algorithm for estimating these sums takes exponential time. Since the discrete logarithm problem reduces to Gauss sum estimation, an efficient classical algorithm for estimating Gauss sums would imply an efficient classical algorithm for computing discrete logarithms, which is considered unlikely. However, quantum computers can estimate Gauss sums to polynomial precision in polynomial time.

Algorithms based on amplitude amplification

Amplitude amplification is a technique that allows the amplification of a chosen subspace of a quantum state. Applications of amplitude amplification usually lead to quadratic speedups over the corresponding classical algorithms.

Grover's algorithm

Main article: Grover's algorithm

Grover's algorithm searches an unstructured database (or an unordered list) with N entries, for a marked entry, using only $O({\sqrt {N}})$ queries instead of the $\Omega (N)$ queries required classically.

Quantum counting

Quantum counting solves a generalization of the the search problem. It solves the problem of counting the number of marked entries in an unordered list.

Algorithms based on quantum walks

Main article: Quantum walk

Algorithms based on quantum walks can provide an exponential speedup over any classical algorithm for some oracular problems. Quantum walks also give polynomial speedups over classical algorithms for many practical problems, such as the element distinctness problem, the triangle finding problem, and evaluating NAND trees.