# 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 (or non-quantum) 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,: 126  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 quantum entanglement.

Problems which are undecidable using classical computers remain undecidable using quantum computers.: 127  What makes quantum algorithms interesting is that they might be able to solve some problems faster than classical algorithms because the quantum superposition and quantum entanglement that quantum algorithms exploit probably cannot be efficiently simulated on classical computers (see Quantum supremacy).

The best-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 much (almost 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, a linear search.

1. ^ Nielsen, Michael A.; Chuang, Isaac L. (2000). Quantum Computation and Quantum Information. Cambridge University Press. ISBN 978-0-521-63503-5.
2. ^ Mosca, M. (2008). "Quantum Algorithms". arXiv:0808.0369 [quant-ph].
3. ^ Lanzagorta, Marco; Uhlmann, Jeffrey K. (1 January 2009). Quantum Computer Science. Morgan & Claypool Publishers. ISBN 9781598297324.
4. ^ Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (2nd ed.). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3.
5. ^
6. ^ "IBM quantum composer user guide: Grover's algorithm". quantum-computing.ibm.com. Retrieved 7 June 2022.