Editing Quantum computing (section)

== Algorithms ==

<!-- Overview of quantum algorithms, particularly abstract routines with no explicit application -->
Progress in finding [[quantum algorithms]] typically focuses on this quantum circuit model, though exceptions like the [[Adiabatic quantum computation|quantum adiabatic algorithm]] exist. Quantum algorithms can be roughly categorized by the type of speedup achieved over corresponding classical algorithms.<ref name="zoo">{{cite web |author=Jordan |first=Stephen |date=14 October 2022 |title=Quantum Algorithm Zoo |url=http://math.nist.gov/quantum/zoo/ |url-status=live |archive-url=https://web.archive.org/web/20180429014516/https://math.nist.gov/quantum/zoo/ |archive-date=29 April 2018 |orig-year=22 April 2011}}</ref>

Quantum algorithms that offer more than a polynomial speedup over the best-known classical algorithm include Shor's algorithm for factoring and the related quantum algorithms for computing [[discrete logarithm]]s, solving [[Pell's equation]], and more generally solving the [[hidden subgroup problem]] for [[Abelian group|abelian]] finite groups.<ref name="zoo"/> These algorithms depend on the primitive of the [[quantum Fourier transform]]. No mathematical proof has been found that shows that an equally fast classical algorithm cannot be discovered, but evidence suggests that this is unlikely.<ref>{{Cite conference |last1=Aaronson |first1=Scott |last2=Arkhipov |first2=Alex |date=2011-06-06 |title=The computational complexity of linear optics |book-title=Proceedings of the forty-third annual ACM symposium on Theory of computing |language=en |location=[[San Jose, California]] |publisher=[[Association for Computing Machinery]] |pages=333–342 |doi=10.1145/1993636.1993682 |isbn=978-1-4503-0691-1 |author-link=Scott Aaronson |arxiv=1011.3245}}</ref> Certain oracle problems like [[Simon's problem]] and the [[Bernstein–Vazirani algorithm|Bernstein–Vazirani problem]] do give provable speedups, though this is in the [[quantum complexity theory#Quantum query complexity|quantum query model]], which is a restricted model where lower bounds are much easier to prove and doesn't necessarily translate to speedups for practical problems.

Other problems, including the simulation of quantum physical processes from chemistry and solid-state physics, the approximation of certain [[Jones polynomial]]s, and the [[quantum algorithm for linear systems of equations]], have quantum algorithms appearing to give super-polynomial speedups and are [[BQP]]-complete. Because these problems are BQP-complete, an equally fast classical algorithm for them would imply that ''no quantum algorithm'' gives a super-polynomial speedup, which is believed to be unlikely.{{sfn|Nielsen|Chuang|2010|p=42}}

Some quantum algorithms, like [[Grover's algorithm]] and [[amplitude amplification]], give polynomial speedups over corresponding classical algorithms.<ref name="zoo"/> Though these algorithms give comparably modest quadratic speedup, they are widely applicable and thus give speedups for a wide range of problems.{{sfn|Nielsen|Chuang|2010|p=7}}

=== Simulation of quantum systems ===
{{Main|Quantum simulation}}

Since chemistry and nanotechnology rely on understanding quantum systems, and such systems are impossible to simulate in an efficient manner classically, [[Quantum simulator|quantum simulation]] may be an important application of quantum computing.<ref>{{Cite magazine |url=http://archive.wired.com/science/discoveries/news/2007/02/72734 |title=The Father of Quantum Computing |magazine=Wired |first=Quinn |last=Norton |date=15 February 2007 }}</ref> Quantum simulation could also be used to simulate the behavior of atoms and particles at unusual conditions such as the reactions inside a [[collider]].<ref>{{cite web |url=http://www.ias.edu/ias-letter/ambainis-quantum-computing |title=What Can We Do with a Quantum Computer? |first=Andris |last=Ambainis |date=Spring 2014 |publisher=Institute for Advanced Study}}</ref> In June 2023, IBM computer scientists reported that a quantum computer produced better results for a physics problem than a conventional supercomputer.<ref name="NYT-20230614">{{cite news |last=Chang |first=Kenneth |date=14 June 2023 |title=Quantum Computing Advance Begins New Era, IBM Says – A quantum computer came up with better answers to a physics problem than a conventional supercomputer. |work=[[The New York Times]] |url=https://www.nytimes.com/2023/06/14/science/ibm-quantum-computing.html |url-status=live |accessdate=15 June 2023 |archiveurl=https://archive.today/20230614151835/https://www.nytimes.com/2023/06/14/science/ibm-quantum-computing.html |archivedate=14 June 2023}}</ref><ref name="NAT-20230614">{{cite journal |author=Kim, Youngseok |display-authors=et al. |title=Evidence for the utility of quantum computing before fault tolerance |date=14 June 2023 |journal=[[Nature (journal)|Nature]] |volume=618 |issue=7965 |pages=500–505 |doi=10.1038/s41586-023-06096-3 |pmid=37316724 |pmc=10266970 |bibcode=2023Natur.618..500K }}</ref>

About 2% of the annual global energy output is used for [[nitrogen fixation]] to produce [[ammonia]] for the [[Haber process]] in the agricultural fertilizer industry (even though naturally occurring organisms also produce ammonia). Quantum simulations might be used to understand this process and increase the energy efficiency of production.<ref>{{Cite AV media |url=https://www.youtube.com/watch?v=7susESgnDv8 |archive-url=https://web.archive.org/web/20210215140237/https://www.youtube.com/watch?v=7susESgnDv8 |archive-date=15 February 2021 |url-status=bot: unknown |title=Lunch & Learn: Quantum Computing |publisher=[[Sibos (conference)|Sibos TV]] |via=YouTube |date=21 November 2018 |access-date=4 February 2021 |first=Andrea |last=Morello |author-link=Andrea Morello }}</ref> It is expected that an early use of quantum computing will be modeling that improves the efficiency of the Haber–Bosch process<ref>{{Cite news |last1=Ruane |first1=Jonathan |last2=McAfee |first2=Andrew |last3=Oliver |first3=William D. |date=2022-01-01 |title=Quantum Computing for Business Leaders |work=Harvard Business Review |url=https://hbr.org/2022/01/quantum-computing-for-business-leaders |access-date=2023-04-12 |issn=0017-8012}}</ref> by the mid-2020s<ref>{{Cite web |last1=Budde |first1=Florian |last2=Volz |first2=Daniel |date=July 12, 2019 |title=Quantum computing and the chemical industry {{!}} McKinsey |url=https://www.mckinsey.com/industries/chemicals/our-insights/the-next-big-thing-quantum-computings-potential-impact-on-chemicals |access-date=2023-04-12 |website=www.mckinsey.com |publisher=McKinsey and Company}}</ref> although some have predicted it will take longer.<ref>{{Cite web |last=Bourzac |first=Katherine |date=October 30, 2017 |title=Chemistry is quantum computing's killer app |url=https://cen.acs.org/articles/95/i43/Chemistry-quantum-computings-killer-app.html |access-date=2023-04-12 |website=cen.acs.org |publisher=American Chemical Society}}</ref>

=== Post-quantum cryptography ===
{{Main|Post-quantum cryptography}}

A notable application of quantum computation is for [[cryptanalysis|attacks]] on cryptographic systems that are currently in use. [[Integer factorization]], which underpins the security of [[public key cryptography|public key cryptographic]] systems, is believed to be computationally infeasible with an ordinary computer for large integers if they are the product of few [[prime number]]s (e.g., products of two 300-digit primes).<ref>{{cite journal |last=Lenstra |first=Arjen K. |url=http://sage.math.washington.edu/edu/124/misc/arjen_lenstra_factoring.pdf |title=Integer Factoring |journal=Designs, Codes and Cryptography |volume=19 |pages=101–128 |year=2000 |doi=10.1023/A:1008397921377 |issue=2/3 |s2cid=9816153 |url-status=dead |archive-url=https://web.archive.org/web/20150410234239/http://sage.math.washington.edu/edu/124/misc/arjen_lenstra_factoring.pdf |archive-date=10 April 2015 }}</ref> By comparison, a quantum computer could solve this problem exponentially faster using Shor's algorithm to find its factors.{{sfn|Nielsen|Chuang|2010|p=216}} This ability would allow a quantum computer to break many of the [[cryptography|cryptographic]] systems in use today, in the sense that there would be a [[polynomial time]] (in the number of digits of the integer) algorithm for solving the problem. In particular, most of the popular [[Asymmetric Algorithms|public key ciphers]] are based on the difficulty of factoring integers or the [[discrete logarithm]] problem, both of which can be solved by Shor's algorithm. In particular, the [[RSA (algorithm)|RSA]], [[Diffie–Hellman]], and [[elliptic curve Diffie–Hellman]] algorithms could be broken. These are used to protect secure Web pages, encrypted email, and many other types of data. Breaking these would have significant ramifications for electronic privacy and security.

Identifying cryptographic systems that may be secure against quantum algorithms is an actively researched topic under the field of ''post-quantum cryptography''.<ref name="pqcrypto_survey">{{cite book |doi=10.1007/978-3-540-88702-7_1 |chapter=Introduction to post-quantum cryptography |title=Post-Quantum Cryptography |year=2009 |last1=Bernstein |first1=Daniel J. |pages=1–14 |isbn=978-3-540-88701-0 |place=Berlin, Heidelberg |publisher=Springer|s2cid=61401925 }}</ref><ref>See also [http://pqcrypto.org/ pqcrypto.org], a bibliography maintained by Daniel J. Bernstein and [[Tanja Lange]] on cryptography not known to be broken by quantum computing.</ref> Some public-key algorithms are based on problems other than the integer factorization and discrete logarithm problems to which Shor's algorithm applies, like the [[McEliece cryptosystem]] based on a problem in [[coding theory]].<ref name="pqcrypto_survey" /><ref>{{cite journal |last1=McEliece |first1=R. J. |title=A Public-Key Cryptosystem Based On Algebraic Coding Theory |journal=DSNPR |date=January 1978 |volume=44 |pages=114–116 |url=http://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF |bibcode=1978DSNPR..44..114M}}</ref> [[Lattice-based cryptography|Lattice-based cryptosystems]] are also not known to be broken by quantum computers, and finding a polynomial time algorithm for solving the [[dihedral group|dihedral]] [[hidden subgroup problem]], which would break many lattice based cryptosystems, is a well-studied open problem.<ref>{{cite journal |last1=Kobayashi |first1=H. |last2=Gall |first2=F. L. |year=2006 |title=Dihedral Hidden Subgroup Problem: A Survey |journal=Information and Media Technologies |volume=1 |issue=1 |pages=178–185 |doi=10.2197/ipsjdc.1.470 |doi-access=free}}</ref> It has been proven that applying Grover's algorithm to break a [[Symmetric-key algorithm|symmetric (secret key) algorithm]] by brute force requires time equal to roughly 2<sup>''n''/2</sup> invocations of the underlying cryptographic algorithm, compared with roughly 2<sup>''n''</sup> in the classical case,<ref name=bennett_1997>{{cite journal |last1=Bennett |first1=Charles H. |last2=Bernstein |first2=Ethan |last3=Brassard |first3=Gilles |last4=Vazirani |first4=Umesh |title=Strengths and Weaknesses of Quantum Computing |journal=SIAM Journal on Computing |date=October 1997 |volume=26 |issue=5 |pages=1510–1523 |doi=10.1137/s0097539796300933 |arxiv=quant-ph/9701001 |bibcode=1997quant.ph..1001B |s2cid=13403194 }}</ref> meaning that symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover's algorithm that AES-128 has against classical brute-force search (see ''[[Key size#Effect of quantum computing attacks on key strength|Key size]]'').

=== 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>

=== Quantum annealing<span class="anchor" id="Quantum annealing and adiabatic optimization"></span> ===

[[Quantum annealing]] relies on the adiabatic theorem to undertake calculations. A system is placed in the ground state for a simple Hamiltonian, which slowly evolves to a more complicated Hamiltonian whose ground state represents the solution to the problem in question. The adiabatic theorem states that if the evolution is slow enough the system will stay in its ground state at all times through the process. {{anchor|Computational biology}}Adiabatic optimization may be helpful for solving [[computational biology]] problems.<ref>{{cite journal |last1=Outeiral |first1=Carlos| last2=Strahm |first2=Martin |last3=Morris |first3=Garrett |last4=Benjamin |first4=Simon |last5=Deane |first5=Charlotte |last6=Shi |first6=Jiye |title=The prospects of quantum computing in computational molecular biology |journal=WIREs Computational Molecular Science |year=2021|volume=11|doi=10.1002/wcms.1481 |arxiv=2005.12792 |s2cid=218889377 |doi-access=free}}</ref>

=== Machine learning ===
{{Main|Quantum machine learning}}

Since quantum computers can produce outputs that classical computers cannot produce efficiently, and since quantum computation is fundamentally linear algebraic, some express hope in developing quantum algorithms that can speed up [[machine learning]] tasks.<ref name="preskill2018"/><ref>{{Cite journal |last1=Biamonte |first1=Jacob |last2=Wittek |first2=Peter |last3=Pancotti |first3=Nicola |last4=Rebentrost |first4=Patrick |last5=Wiebe |first5=Nathan |last6=Lloyd |first6=Seth |date=September 2017 |title=Quantum machine learning |journal=Nature |language=en |volume=549 |issue=7671 |pages=195–202 |doi=10.1038/nature23474 |pmid=28905917 |arxiv=1611.09347 |bibcode=2017Natur.549..195B |s2cid=64536201 |issn=0028-0836}}</ref>

For example, the [[HHL Algorithm]], named after its discoverers Harrow, Hassidim, and Lloyd, is believed to provide speedup over classical counterparts.<ref name="preskill2018"/><ref name="Quantum algorithm for solving linear systems of equations by Harrow et al.">{{Cite journal |arxiv=0811.3171 |last1=Harrow |first1=Aram |last2=Hassidim |first2=Avinatan |last3=Lloyd |first3=Seth |title=Quantum algorithm for solving linear systems of equations |journal=Physical Review Letters |volume=103 |issue=15 |page=150502 |year=2009 |doi=10.1103/PhysRevLett.103.150502 |pmid=19905613 |bibcode=2009PhRvL.103o0502H |s2cid=5187993}}</ref> Some research groups have recently explored the use of quantum annealing hardware for training [[Boltzmann machine]]s and [[deep neural networks]].<ref>{{Cite journal |last1=Benedetti |first1=Marcello |last2=Realpe-Gómez |first2=John |last3=Biswas |first3=Rupak |last4=Perdomo-Ortiz |first4=Alejandro |date=9 August 2016 |title=Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning |journal=Physical Review A |volume=94 |issue=2 |page=022308 |doi=10.1103/PhysRevA.94.022308 |arxiv=1510.07611 |bibcode=2016PhRvA..94b2308B |doi-access=free}}</ref><ref>{{Cite journal |last1=Ajagekar |first1=Akshay |last2=You |first2=Fengqi |date=5 December 2020 |title=Quantum computing assisted deep learning for fault detection and diagnosis in industrial process systems |journal=Computers & Chemical Engineering |language=en |volume=143 |page=107119 |arxiv=2003.00264 |s2cid=211678230 |doi=10.1016/j.compchemeng.2020.107119 |issn=0098-1354}}</ref><ref>{{Cite journal |last1=Ajagekar |first1=Akshay |last2=You |first2=Fengqi |date=2021-12-01 |title=Quantum computing based hybrid deep learning for fault diagnosis in electrical power systems |journal=Applied Energy |language=en |volume=303 |pages=117628 |doi=10.1016/j.apenergy.2021.117628 |issn=0306-2619 |doi-access=free|bibcode=2021ApEn..30317628A }}</ref>

{{anchor|Computer-aided drug design and generative chemistry}}
Deep generative chemistry models emerge as powerful tools to expedite [[drug discovery]]. However, the immense size and complexity of the structural space of all possible drug-like molecules pose significant obstacles, which could be overcome in the future by quantum computers. Quantum computers are naturally good for solving complex quantum many-body problems<ref name="273.5278.1073"/> and thus may be instrumental in applications involving quantum chemistry. Therefore, one can expect that quantum-enhanced generative models<ref>{{cite journal |last1=Gao |first1=Xun |last2=Anschuetz |first2=Eric R. |last3=Wang |first3=Sheng-Tao |last4=Cirac |first4=J. Ignacio |last5=Lukin |first5=Mikhail D. |title=Enhancing Generative Models via Quantum Correlations |journal=Physical Review X |year=2022 |volume=12 |issue=2 |page=021037 |doi=10.1103/PhysRevX.12.021037 |arxiv=2101.08354 |bibcode=2022PhRvX..12b1037G |s2cid=231662294}}</ref> including quantum GANs<ref>{{cite arXiv |last1=Li |first1=Junde |last2=Topaloglu |first2=Rasit |last3=Ghosh |first3=Swaroop |title=Quantum Generative Models for Small Molecule Drug Discovery |date=9 January 2021 |class=cs.ET |eprint=2101.03438}}</ref> may eventually be developed into ultimate generative chemistry algorithms.