For questions about quantum algorithms, that is, sequences of quantum gates, operations, and measurements, whose purpose which achieve some goal. Standard examples are Shor's and Grover's algorithms.
A quantum algorithm is a procedure or set of instructions that can be performed on a theoretical model of a quantum computer.
Generally, a quantum algorithm solves some problem and utilises the properties of quantum physics, such as entanglement, to do so. Often, a quantum algorithm will have a better time/query complexity than a classical algorithm solving the same problem.
An algorithm can be written as a program in a quantum programming language, which can then be implemented on a large enough quantum computer.
Some famous algorithms include:
Deutsch-Josza algorithm: The first algorithm to exponentially fast than the classical equivalent, showing the potential of quantum computing. Given an oracle that implements a function that takes an n-bit input and returns a single-bit output and is known to be either balanced (returning '1' as often as '0' over all inputs) or constant (the output is the same regardless of input), the Deutsch-Josza algorithm can deterministically find if the function is constant or balanced in a single step.
Simon's algorithm: Given an oracle that implements a function (returning the same number of output bits as input bits) with the property that $f\left(x\right)=f\left(x\oplus s\right)\forall x\in\left\lbrace0, 1\right\rbrace^n$, for some unknown $s$, Simon's algorithm finds $s$ in $\mathcal O\left(n\right)$ queries, in comparison with the best possible algorithm requiring $\Omega\left(2^{n/2}\right)$ queries.
Shor's algorithm: Solves the problem of integer factorisation sub-exponentially faster than the current best known classical algorithm (the general number field sieve). As current classical encryption methods rely on the computational difficulty in performing integer factorisation, a large enough fault tolerant universal quantum computer would break current encryption methods.
Grover's algorithm: This finds the input value to an oracle returning a particular output for that input in a time quadratically faster than a classical computer.
A list of all the currently discovered quantum algorithms can be found at the quantum complexity zoo, which also contains links to several reviews on algorithms. Aside from Nielsen and Chuang's Quantum Computation and Quantum Information textbook, these are lecture notes by:
- Andrew Child
- John Preskill
- Michael Loceff's *A Course in Quantum Computing (for the Community College) - pdf link
as well as review articles by:
