Editing Quantum algorithm (section)

{{Short description|Algorithm to be run on quantum computers}}
{{Use American English|date=January 2019}}
{{Use dmy dates|date=December 2020}}
In [[quantum computing]], a '''quantum algorithm''' is an [[algorithm]] that runs on a realistic model of [[quantum computation]], the most commonly used model being the [[quantum circuit]] model of computation.<ref>{{cite book|title=Quantum Computation and Quantum Information|last1=Nielsen|first1=Michael A.|last2=Chuang|first2=Isaac L.|publisher=[[Cambridge University Press]]|year=2000|isbn=978-0-521-63503-5|author-link=Michael Nielsen|author-link2=Isaac Chuang|title-link=Quantum Computation and Quantum Information}}</ref><ref>{{cite arXiv|eprint=0808.0369|class=quant-ph|first=M.|last=Mosca|author-link=Michele Mosca|title=Quantum Algorithms|date=2008}}</ref> 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,<ref>{{Cite book|title = Quantum Computer Science|url = https://books.google.com/books?id=-wkJIuw0YRsC&q=quantum%2520computer%2520equivalent%2520classical%2520computer&pg=PA23|publisher = Morgan & Claypool Publishers|date = 2009-01-01|isbn = 9781598297324|first1 = Marco|last1 = Lanzagorta|first2 = Jeffrey K.|last2 = Uhlmann}}</ref>{{rp|126}}  the term quantum algorithm is generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such as [[quantum superposition]] or [[quantum entanglement]].

Problems that are [[Undecidable problem|undecidable]] using classical computers remain undecidable using quantum computers.<ref name=nielchuan>{{cite book|title=Quantum Computation and Quantum Information|last1=Nielsen|first1=Michael A.|last2=Chuang|first2=Isaac L.|publisher=Cambridge University Press|year=2010|isbn=978-1-107-00217-3|edition=2nd|location=Cambridge|author-link=Michael A. Nielsen|author-link2=Isaac Chuang|url=https://books.google.com/books?id=-s4DEy7o-a0C}}</ref>{{rp|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 generally 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 algorithm runs much (almost exponentially) faster than the most efficient known classical algorithm for factoring, the [[general number field sieve]].<ref>{{Cite web|url=https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm|title = Shor's algorithm}}</ref> Grover's algorithm runs quadratically faster than the best possible classical algorithm for the same task,<ref>{{cite web |url=https://quantum-computing.ibm.com/composer/docs/iqx/guide/grovers-algorithm |title=IBM quantum composer user guide: Grover's algorithm |access-date=7 June 2022 |website=quantum-computing.ibm.com}}</ref> a [[linear search]].