Afdeling informatica, Instituut voor geavanceerde computerstudies en gezamenlijk centrum voor kwantuminformatie en informatica, Universiteit van Maryland
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
Hoewel recent onderzoek suggereert dat kwantumcomputers de oplossing van semidefinite-programma's kunnen versnellen, is er weinig bekend over de kwantumcomplexiteit van meer algemene convexe optimalisatie. We presenteren een kwantumalgoritme dat een convexe functie kan optimaliseren over een $ n $ -dimensionale convexe body met behulp van $ tilde {O} (n) $ queries naar orakels die de objectieve functie evalueren en het lidmaatschap van de convexe body bepalen. Dit vertegenwoordigt een kwadratische verbetering ten opzichte van het bekendste klassieke algoritme. We bestuderen ook beperkingen op de kracht van kwantumcomputers voor algemene convexe optimalisatie, waaruit blijkt dat het $ tilde {Omega} (sqrt n) $ evaluatiequery's en $ Omega (sqrt {n}) $ lidmaatschapsvragen vereist.
Populaire samenvatting
► BibTeX-gegevens
► Referenties
[1] Andris Ambainis en Ashley Montanaro, Quantum-algoritmen voor zoeken met jokertekens en combinatorische groepstesten, Quantum Information and Computation 14 (2014), nr. 5 & 6, 439-453.
https: / / doi.org/ 10.26421 / QIC14.5-6
arXiv: arXiv: 1210.1148
[2] Joran van Apeldoorn en András Gilyén, verbeteringen in kwantum SDP-oplossingen met applicaties, Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 99: 1-99: 15, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.99
arXiv: arXiv: 1804.05058
[3] Joran van Apeldoorn, András Gilyén, Sander Gribling en Ronald de Wolf, Quantum SDP-solvers: Betere boven- en ondergrenzen, Proceedings of the 58th Annual Symposium on Foundations of Computer Science, 2017.
https: / / doi.org/ 10.1109 / FOCS.2017.44
arXiv: arXiv: 1705.01843
[4] Joran van Apeldoorn, András Gilyén, Sander Gribling en Ronald de Wolf, convexe optimalisatie met kwantumorakels, Quantum, 2019.
arXiv: arXiv: 1809.00643
[5] Stephen Boyd en Lieven Vandenberghe, Convex-optimalisatie, Cambridge University Press, 2004.
[6] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore en Xiaodi Wu, Quantum SDP-oplossers: grote versnellingen, optimaliteit en toepassingen voor kwantumleer, Proceedings of the 46th International Colloquium on Automata , Talen en programmering, Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 27: 1-27: 14, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.27
arXiv: arXiv: 1710.02581v2
[7] Fernando GSL Brandão en Krysta Svore, Quantum-versnellingen voor het oplossen van semidefinite-programma's, Proceedings of the 58th Annual Symposium on Foundations of Computer Science, pp. 415-426, 2017.
https: / / doi.org/ 10.1109 / FOCS.2017.45
arXiv: arXiv: 1609.05537
[8] Gilles Brassard, Peter Høyer, Michele Mosca en Alain Tapp, Quantum-amplitude-amplificatie en schatting, Contemporary Mathematics 305 (2002), 53-74.
arXiv: arXiv: quant-ph / 0005055
[9] Andrew M. Childs, Robin Kothari en Rolando D. Somma, Quantum-algoritme voor systemen van lineaire vergelijkingen met exponentieel verbeterde afhankelijkheid van precisie, SIAM Journal on Computing 46 (2017), nr. 6, 1920-1950.
https: / / doi.org/ 10.1137 / 16M1087072
arXiv: arXiv: 1511.02306
[10] George B. Dantzig en Mukund N. Thapa, Lineaire programmering 2: Theorie en uitbreidingen, Springer, 2006.
[11] András Gilyén, Srinivasan Arunachalam en Nathan Wiebe, Optimalisatie van kwantumoptimalisatie-algoritmen via snellere kwantumgradiëntberekening, Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1425-1444, Society for Industrial and Applied Mathematics, 2019.
https: / / doi.org/ 10.1137 / 1.9781611975482.87
arXiv: arXiv: 1711.00465
[12] Martin Grötschel, László Lovász en Alexander Schrijver, Geometrische algoritmen en combinatorische optimalisatie, Algorithms and Combinatorics, vol. 2, Springer, 2012.
[13] Aram W. Harrow, Avinatan Hassidim en Seth Lloyd, Quantum-algoritme voor lineaire vergelijkingssystemen, Physical Review Letters 103 (2009), nr. 15, 150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
arXiv: arXiv: 0811.3171
[14] Lars Hörmander, De analyse van lineaire partiële differentiaaloperatoren: distributietheorie en Fourier-analyse, Springer-Verlag, 1990.
[15] Stephen P. Jordan, snel kwantumalgoritme voor numerieke gradiëntschatting, Physical Review Letters 95 (2005), nr. 5, 050501.
https: / / doi.org/ 10.1103 / PhysRevLett.95.050501
arXiv: arXiv: quant-ph / 0405146
[16] Adam T. Kalai en Santosh Vempala, gesimuleerd gloeien voor convexe optimalisatie, Mathematics of Operations Research 31 (2006), nr. 2, 253-266.
https: / / doi.org/ 10.1287 / moor.1060.0194
[17] Narendra Karmarkar, een nieuw polynoomtijd-algoritme voor lineair programmeren, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pp. 302-311, 1984.
https: / / doi.org/ 10.1145 / 800057.808695
[18] James E. Kelley, Jr., De snijvlakmethode voor het oplossen van convexe programma's, Journal of the Society for Industrial and Applied Mathematics 8 (1960), nr. 4, 703-712.
https: / / doi.org/ 10.1137 / 0108053
[19] Iordanis Kerenidis en Anupam Prakash, Quantumgradiëntafdaling voor lineaire systemen en kleinste kwadraten, 2017.
arXiv: arXiv: 1704.04992
[20] Yin Tat Lee, persoonlijke communicatie, 2018.
[21] Yin Tat Lee, Aaron Sidford en Santosh S. Vempala, Efficiënte convexe optimalisatie met lidmaatschapsorakels, Proceedings of the 31st Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 75, pp. 1292-1294, 2018.
arXiv: arXiv: 1706.07357
[22] Yin Tat Lee, Aaron Sidford en Sam Chiu-wai Wong, een snellere snijmesmethode en de implicaties voor combinatorische en convexe optimalisatie, Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pp. 1049-1065, 2015.
https: / / doi.org/ 10.1109 / FOCS.2015.68
arXiv: arXiv: 1508.04874
[23] László Lovász en Santosh Vempala, Snelle algoritmen voor logconcave functies: bemonstering, afronding, integratie
en optimalisatie, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 57-68, 2006.
https: / / doi.org/ 10.1109 / FOCS.2006.28
[24] Arkadi S. Nemirovski, op informatie gebaseerde complexiteit van convex programmeren, dictaten, 1995.
[25] Arkadi S. Nemirovski en David B. Yudin, Probleemcomplexiteit en methode-efficiëntie bij optimalisatie, Wiley, 1983.
[26] Yurii Nesterov, inleidende lezingen over convexe optimalisatie: een basiscursus, toegepaste optimalisatie, vol. 87, Springer, 2013.
[27] Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione en Seth Lloyd, Quantum gradiëntafdaling en Newton's methode voor beperkte polynoomoptimalisatie, New Journal of Physics 21 (2019), nr. 7, 073023, IOP Publishing.
https://doi.org/10.1088/1367-2630/ab2a9e
arXiv: arXiv: 1612.01789
[28] Pravin M. Vaidya, een nieuw algoritme voor het minimaliseren van convexe functies via convexe sets, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pp. 338-343, 1989.
https: / / doi.org/ 10.1109 / SFCS.1989.63500
Geciteerd door
[1] Patrick Rebentrost en Seth Lloyd, "Quantum computational finance: quantum algoritme voor portefeuilleoptimalisatie", arXiv: 1811.03975.
[2] Joran van Apeldoorn, András Gilyén, Sander Gribling en Ronald de Wolf, "Quantum SDP-Solvers: betere boven- en ondergrenzen", arXiv: 1705.01843.
[3] Joran van Apeldoorn, András Gilyén, Sander Gribling en Ronald de Wolf, "Convexe optimalisatie met behulp van kwantumorakels", arXiv: 1809.00643.
[4] PAM Casares en MA Martin-Delgado, "A Quantum Interior-Point Predictor-Corrector Algorithm for Linear Programming", arXiv: 1902.06749.
[5] Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis en Miklos Santha, "Quantum and Classical Algorithms for approximate Submodular Function Minimalization", arXiv: 1907.05378.
[6] Hsin-Yuan Huang, Kishor Bharti en Patrick Rebentrost, "Quantumalgoritmen op korte termijn voor lineaire stelsels van vergelijkingen", arXiv: 1909.07344.
[7] Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang en Xiaodi Wu, "Quantum-algoritme voor het schatten van volumes van convexe lichamen", arXiv: 1908.03903.
Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2020-01-22 14:30:25). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.
On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2020-01-22 14:30:24).
Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.
