Editing Quantum computing (section)

=== Search problems<span class="anchor" id="Quantum search"></span> ===
{{Main|Grover's algorithm}}

The most well-known example of a problem that allows for a polynomial quantum speedup is ''unstructured search'', which involves finding a marked item out of a list of <math>n</math> items in a database. This can be solved by Grover's algorithm using <math>O(\sqrt{n})</math> queries to the database, quadratically fewer than the <math>\Omega(n)</math> queries required for classical algorithms. In this case, the advantage is not only provable but also optimal: it has been shown that Grover's algorithm gives the maximal possible probability of finding the desired element for any number of oracle lookups. Many examples of provable quantum speedups for query problems are based on Grover's algorithm, including [[BHT algorithm|Brassard, Høyer, and Tapp's algorithm]] for finding collisions in two-to-one functions,<ref>{{cite encyclopedia |year=2016 |title=Quantum Algorithm for the Collision Problem |encyclopedia=Encyclopedia of Algorithms |publisher=Springer |place=New York, New York |editor-last=Kao |editor-first=Ming-Yang |pages=1662–1664 |language=en |arxiv=quant-ph/9705002 |doi=10.1007/978-1-4939-2864-4_304 |isbn=978-1-4939-2864-4 |last2=Høyer |first2=Peter |last3=Tapp |first3=Alain |last1=Brassard |first1=Gilles |s2cid=3116149}}</ref> and Farhi, Goldstone, and Gutmann's algorithm for evaluating NAND trees.<ref>{{Cite journal |last1=Farhi |first1=Edward |last2=Goldstone |first2=Jeffrey |last3=Gutmann |first3=Sam |date=23 December 2008 |title=A Quantum Algorithm for the Hamiltonian NAND Tree |journal=Theory of Computing |language=EN |volume=4 |issue=1 |pages=169–190 |doi=10.4086/toc.2008.v004a008 |s2cid=8258191 |issn=1557-2862 |doi-access=free}}</ref>

Problems that can be efficiently addressed with Grover's algorithm have the following properties:<ref>{{cite book |author=Williams |first=Colin P. |title=Explorations in Quantum Computing |publisher=[[Springer Science+Business Media|Springer]] |year=2011 |isbn=978-1-84628-887-6 |pages=242–244}}</ref><ref>{{cite arXiv |last=Grover| first=Lov| author-link=Lov Grover |title=A fast quantum mechanical algorithm for database search |date=29 May 1996| eprint=quant-ph/9605043}}</ref>
#There is no searchable structure in the collection of possible answers,
#The number of possible answers to check is the same as the number of inputs to the algorithm, and
#There exists a Boolean function that evaluates each input and determines whether it is the correct answer.

For problems with all these properties, the running time of Grover's algorithm on a quantum computer scales as the square root of the number of inputs (or elements in the database), as opposed to the linear scaling of classical algorithms. A general class of problems to which Grover's algorithm can be applied<ref>{{cite journal |last1=Ambainis |first1=Ambainis |title=Quantum search algorithms |journal=ACM SIGACT News |date=June 2004 |volume=35 |issue=2 |pages=22–35 |doi=10.1145/992287.992296 |arxiv=quant-ph/0504012 |bibcode=2005quant.ph..4012A |s2cid=11326499 }}</ref> is a [[Boolean satisfiability problem]], where the ''database'' through which the algorithm iterates is that of all possible answers. An example and possible application of this is a [[Password cracking|password cracker]] that attempts to guess a password. Breaking [[Symmetric-key algorithm|symmetric ciphers]] with this algorithm is of interest to government agencies.<ref>{{cite news |url=https://www.washingtonpost.com/world/national-security/nsa-seeks-to-build-quantum-computer-that-could-crack-most-types-of-encryption/2014/01/02/8fff297e-7195-11e3-8def-a33011492df2_story.html |title=NSA seeks to build quantum computer that could crack most types of encryption |first1=Steven |last1=Rich |first2=Barton |last2=Gellman |date=1 February 2014 |newspaper=The Washington Post}}</ref>