Quantum algorithm: Difference between revisions

Content deleted Content added
corrected a page number
fixed URL-wikilink conflict
Line 16:
}}</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&pg=PA23&lpg=PA23&dq=quantum%2520computer%2520equivalent%2520classical%2520computer&source=bl&ots=a4GtRJVB3c&sig=TwUadwnVELCCwY6EXkKne-2GZVw&hl=en&sa=X&ved=0ahUKEwi54efO39PJAhUG7WMKHSg6BkIQ6AEIRDAH#v=onepage&q=quantum%2520computer%2520equivalent%2520classical%2520computer&f=false|publisher = Morgan & Claypool Publishers|date = 2009-01-01|isbn = 9781598297324|first = Marco|last = Lanzagorta|first2 = Jeffrey K.|last2 = Uhlmann}}</ref>{{rp|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 problem|undecidable]] using classical computers remain undecidable using quantum computers.<ref name=nielchuan>{{cite book|title=[[Quantum Computation and Quantum Information (book)|Quantum Computation and Quantum Information]]|last1=Nielsen|first1=Michael A.|last2=Chuang|first2=Isaac L.|last3=|date=|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{{why|date=February 2018}}.
 
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]]{{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}}{{which|date=February 2018}}.