Quantum algorithm: Difference between revisions

Revision as of 22:26, 29 May 2020

Revision as of 19:33, 28 July 2020

Line 5:

Problems which 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|pages=|author-link=Michael A. Nielsen|author-link2=Isaac Chuang|url=https://books.google.com/books?id=-s4DEy7o-a0C&printsec=frontcover#v=onepage&q=undecidable%20OR%20undecidability&f=false}}</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 probably can't be efficiently simulated on classical computers (see [[Quantum supremacy]]).

The most well 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]].{{citation needed|date=February 2018}} Grover's algorithm runs quadratically faster than the best possible classical algorithm for the same task,{{citation needed|date=February 2018}} a [[linear search]].

==Overview==