Content deleted Content added
→Quantum approximate optimization algorithm: removing an article "the" |
|||
Line 87:
In 2020, it was shown that QAOA exhibits a strong dependence on the ratio of a problem's [[Constraint (mathematics)|constraint]] to [[Variable (mathematics)|variables]] (problem density) placing a limiting restriction on the algorithm's capacity to minimize a corresponding [[Loss function|objective function]].<ref name=":0">{{Cite journal|last1=Akshay|first1=V.|last2=Philathong|first2=H.|last3=Morales|first3=M. E. S.|last4=Biamonte|first4=J. D.|date=2020-03-05|title=Reachability Deficits in Quantum Approximate Optimization|journal=Physical Review Letters|volume=124|issue=9|pages=090504|doi=10.1103/PhysRevLett.124.090504|pmid=32202873|arxiv=1906.11259|bibcode=2020PhRvL.124i0504A}}</ref>
It was soon recognized that a generalization of the QAOA process is essentially an alternating application of a continuous-time quantum walk on an underlying graph followed by a quality-dependent phase shift applied to each solution state. This generalized QAOA was termed as QWOA (Quantum Walk Optimisation Algorithm).<ref>{{Cite journal|last1=Marsh|first1=S.|last2=Wang|first2=J. B.|date=2020-06-08|title=Combinatorial optimization via highly efficient quantum walks|journal=Physical Review Research|volume=2|pages=023302|doi=10.1103/PhysRevResearch.2.023302}}</ref>
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?|url=http://arxiv.org/abs/1805.05224|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 sufficient for [[Quantum supremacy|quantum computational supremacy]].
| |||