Content deleted Content added
m clean up |
Citation bot (talk | contribs) Alter: template type. Add: eprint, class, year, s2cid, authors 1-1. Removed access-date with no URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 34/49 |
||
Line 33:
\end{pmatrix}</math>
The quantum least-squares fitting algorithm<ref>{{cite journal|last1=Wiebe|first1=Nathan|last2=Braun|first2=Daniel|last3=Lloyd|first3=Seth|title=Quantum Algorithm for Data Fitting|journal=Physical Review Letters|date=2 August 2012|volume=109|issue=5|pages=050505|arxiv=1204.5242|doi=10.1103/PhysRevLett.109.050505|pmid=23006156|bibcode=2012PhRvL.109e0505W|s2cid=118439810 }}</ref> makes use of a version of Harrow, Hassidim, and Lloyd's [[quantum algorithm for linear systems of equations]] (HHL), and outputs the coefficients <math> \lambda_j </math> and the fit quality estimation <math> E </math>. It consists of three subroutines: an algorithm for performing a pseudo-[[matrix inversion|inverse]] operation, one routine for the fit quality estimation, and an algorithm for learning the fit parameters.
Because the quantum algorithm is mainly based on the HHL algorithm, it suggests an exponential improvement<ref>{{cite journal|last1=Montanaro|first1=Ashley|title=Quantum algorithms: an overview|journal=[[Npj Quantum Information]] |date=12 January 2016|volume=2|pages=15023|arxiv=1511.04206|doi=10.1038/npjqi.2015.23|bibcode=2016npjQI...215023M|s2cid=2992738}}</ref> in the case where <math> F</math> is [[sparse matrix|sparse]] and the [[condition number]] (namely, the ratio between the largest and the smallest [[eigenvalues]]) of both <math> F F^\dagger </math> and <math> F^\dagger F </math> is small.
Line 92:
In the paper ''How many qubits are needed for quantum computational supremacy'' submitted to arXiv,<ref>{{Cite journal|last1=Dalzell|first1=Alexander M.|last2=Harrow|first2=Aram W.|last3=Koh|first3=Dax Enshan|last4=La Placa|first4=Rolando L.|date=2020-05-11|title=How many qubits are needed for quantum computational supremacy?|journal=Quantum|volume=4|pages=264|doi=10.22331/q-2020-05-11-264|arxiv=1805.05224|issn=2521-327X|doi-access=free}}</ref> the authors conclude that a QAOA circuit with 420 [[qubits]] and 500 [[Constraint (mathematics)|constraints]] would require at least one century to be simulated using a classical simulation algorithm running on [[State of the art|state-of-the-art]] [[supercomputers]] so that would be [[Necessity and sufficiency#Sufficiency|sufficient]] for [[Quantum supremacy|quantum computational supremacy]].
A rigorous comparison of QAOA with classical algorithms can give estimates on depth <math> p </math> and number of qubits required for quantum advantage. A study of QAOA and [[Maximum cut|MaxCut]] algorithm shows that <math>p>11</math> is required for scalable advantage.<ref name="Lykov Wurtz Poole Saffman p. ">{{cite
== See also ==
| |||