1Institut für Informatik, Princeton University, Princeton, NJ 08540, USA.
2Argonne National Laboratory, 9700 S. Cass Ave., Lemont, IL 60439, USA.
Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.
Abstrakt
Wir stellen einen neuen hybriden, lokalen Suchalgorithmus für die Quantennäherungsoptimierung von eingeschränkten kombinatorischen Optimierungsproblemen vor. Wir konzentrieren uns auf das Maximum Independent Set-Problem und demonstrieren die Fähigkeit der lokalen Quantensuche, große Probleminstanzen auf Quantengeräten mit wenigen Qubits zu lösen. Dieser hybride Algorithmus findet iterativ unabhängige Mengen über sorgfältig konstruierte Nachbarschaften und kombiniert diese Lösungen, um eine globale Lösung zu erhalten. Wir untersuchen die Leistung dieses Algorithmus auf 3-regulären, Community- und Erdős-Rényi-Graphen mit bis zu 100 Knoten.
Ausgewähltes Bild: Ein anschauliches Beispiel für den lokalen Quantensuchalgorithmus, der eine lokale Nachbarschaft innerhalb eines größeren Graphen konstruiert.
Populäre Zusammenfassung
► BibTeX-Daten
► Referenzen
[1] Edward Farhi, Jeffrey Goldstone und Sam Gutmann. Ein quantenungefährer Optimierungsalgorithmus. arXiv-Vorabdruck arXiv:1411.4028, 2014.
arXiv: 1411.4028
[2] Stuart Andrew Hadfield. Quantenalgorithmen für wissenschaftliches Rechnen und approximative Optimierung. arXiv-Vordruck arXiv:1805.03265, 2018.
arXiv: 1805.03265
[3] Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G. Rieffel, Davide Venturelli und Rupak Biswas. Vom Quantum Approximate Optimization Algorithmus zum Quantum Alternating Operator Ansatz. Algorithmen, 12(2):34, 2019. https://doi.org/10.3390/a12020034.
https: // doi.org/ 10.3390 / a12020034
[4] Emile Aarts und Jan K. Lenstra. Lokale Suche in der kombinatorischen Optimierung. Princeton University Press, 2003. https:///doi.org/10.2307/j.ctv346t9c.
https:///doi.org/10.2307/j.ctv346t9c
[5] Ruslan Shaydulin, Hayato Ushijima-Mwesigwa, Ilya Safro, Susan Mniszewski und Yuri Alexeev. Erkennung von Netzwerkgemeinschaften auf kleinen Quantencomputern. Advanced Quantum Technologies, 2(9):1900029, 2019. https://doi.org/10.1002/qute.201900029.
https: / / doi.org/ 10.1002 / qute.201900029
[6] Edward Farhi und Aram W Harrow. Quantenüberlegenheit durch den Quantum Approximate Optimization Algorithm. arXiv-Vorabdruck arXiv:1602.07674, 2016.
arXiv: 1602.07674
[7] Richard M Karp. Reduzierbarkeit unter kombinatorischen Problemen. In Komplexität von Computerberechnungen, Seiten 85–103. Springer, 1972. https:///doi.org/10.1007/978-1-4684-2001-2_9.
https://doi.org/10.1007/978-1-4684-2001-2_9
[8] Teague Tomesh. quantenlokale Suche. https://github.com/teaguetomesh/quantum-local-search, 2021.
https:///github.com/teaguetomesh/quantum-local-search
[9] Edward Farhi, David Gamarnik und Sam Gutmann. Der Quantum Approximate Optimization Algorithmus muss den gesamten Graphen sehen: Worst-Case-Beispiele. arXiv-Vordruck arXiv:2005.08747, 2020.
arXiv: 2005.08747
[10] Edward Farhi, David Gamarnik und Sam Gutmann. Der Quanten-Approximations-Optimierungsalgorithmus muss den gesamten Graphen sehen: Ein typischer Fall. arXiv-Vordruck arXiv:2004.09002, 2020.
arXiv: 2004.09002
[11] Zain Hamid Saleem. Max-unabhängige Menge und der quantenalternierende Operatoransatz. International Journal of Quantum Information, 18(04):2050011, 2020. https://doi.org/10.1142/S0219749920500112.
https: / / doi.org/ 10.1142 / S0219749920500112
[12] Daniel J. Egger, Jakub Mareček und Stefan Woerner. Warmstart-Quantenoptimierung. Quantum, 5:479, 2021. https:///doi.org/10.22331/q-2021-06-17-479.
https://doi.org/10.22331/q-2021-06-17-479
[13] Zain H. Saleem, Teague Tomesh, Bilal Tariq und Martin Suchara. Ansätze zur eingeschränkten ungefähren Quantenoptimierung. arXiv-Vordruck arXiv:2010.06660, 2020.
arXiv: 2010.06660
[14] Rebekah Herrman, Phillip C. Lotshaw, James Ostrowski, Travis S. Humble und George Siopsis. Mehrwinkel-Quantennäherungs-Optimierungsalgorithmus. Wissenschaftliche Berichte, 12(6781), 2022. https://doi.org/10.1038/s41598-022-10555-8.
https://doi.org/10.1038/s41598-022-10555-8
[15] Santo Fortunato. Community-Erkennung in Diagrammen. Physics Reports, 486(3-5):75–174, 2010. https://doi.org/10.1016/j.physrep.2009.11.002.
https://doi.org/ 10.1016/j.physrep.2009.11.002
[16] Aric Hagberg, Pieter Swart und Daniel S. Chult. Untersuchen von Netzwerkstruktur, -dynamik und -funktion mit networkx. Technischer Bericht, Los Alamos National Lab. (LANL), Los Alamos, NM, Vereinigte Staaten, 2008. https://www.osti.gov/biblio/960616.
https:///www.osti.gov/biblio/960616
[17] Fakultät für Informatik der Universität Princeton. CS-Cluster-Computing. https://csguide.cs.princeton.edu/resources/clusters, 2022.
https:///csguide.cs.princeton.edu/resources/clusters
[18] Ravi Boppana und Magnús M. Halldórsson. Annäherung an maximale unabhängige Mengen durch Ausschluss von Teilgraphen. BIT Numerical Mathematics, 32:180–196, 1992. https://doi.org/10.1007/BF01994876.
https: / / doi.org/ 10.1007 / BF01994876
[19] Andreas Kreuz. Das IBM Q-Erlebnis und die Open-Source-Quantencomputing-Software QISKit. In APS March Meeting Abstracts, Band 2018, Seiten L58–003, 2018.
[20] Diogo V. Andrade, Mauricio GC Resende und Renato F. Werneck. Schnelle lokale Suche nach dem Problem der maximalen unabhängigen Menge. Journal of Heuristics, 18:525–547, 2012. https://doi.org/10.1007/s10732-012-9196-4.
https://doi.org/10.1007/s10732-012-9196-4
[21] Michael Krivelevich, Tamás Mészáros, Peleg Michaeli und Clara Shikhelman. Greedy Maximal Independent Sets über Local Limits. arXiv-Vordruck arXiv:1907.07216, 2019.
arXiv: 1907.07216
[22] Qinghua Wu und Jin-Kao Hao. Eine Übersicht über Algorithmen für Maximum-Clique-Probleme. European Journal of Operational Research, 242(3):693–709, 2015. https://doi.org/10.1016/j.ejor.2014.09.064.
https:///doi.org/10.1016/j.ejor.2014.09.064
[23] Vivek V. Shende und Igor L. Markov. Zu den CNOT-Kosten von TOFFOLI Gates. Quanteninfo. Comput., 9(5):461–486, Mai 2009.
[24] Yong He, Ming-Xing Luo, E Zhang, Hong-Ke Wang und Xiao-Feng Wang. Zerlegung von n-Qubit-Toffoli-Gattern mit linearer Schaltungskomplexität. International Journal of Theoretical Physics, 56(7):2350–2361, 2017. https://doi.org/10.1007/s10773-017-3389-4.
https://doi.org/10.1007/s10773-017-3389-4
[25] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin und Harald Weinfurter. Elementare Gatter für die Quantenberechnung. Physical Review A, 52(5):3457, 1995. https://doi.org/10.1103/PhysRevA.52.3457.
https: / / doi.org/ 10.1103 / PhysRevA.52.3457
[26] Markus Saffmann. Quantencomputing mit neutralen Atomen. National Science Review, 6(1):24–25, 2019. https://doi.org/10.1093/nsr/nwy088.
https: / / doi.org/ 10.1093 / nsr / nwy088
[27] Thomas Bækkegaard, LB Kristensen, Niels JS Loft, Christian Kraglund Andersen, David Petrosyan und Nikolaj T Zinner. Realisierung effizienter Quantengatter mit einer supraleitenden Qubit-Qutrit-Schaltung. Wissenschaftliche Berichte, 9:13389, 2019. https://doi.org/10.1038/s41598-019-49657-1.
https://doi.org/10.1038/s41598-019-49657-1
[28] Oder Katz, Marko Cetina und Christopher Monroe. $N$-Körper-Wechselwirkungen zwischen eingeschlossenen Ionen-Qubits durch spinabhängiges Quetschen. Phys. Rev. Lett., 129:063603, August 2022. https://doi.org/10.1103/PhysRevLett.129.063603.
https://doi.org/ 10.1103/PhysRevLett.129.063603
[29] Pranav Gokhale, Jonathan M. Baker, Casey Duckering, Natalie C. Brown, Kenneth R. Brown und Frederic T. Chong. Asymptotische Verbesserungen an Quantenschaltkreisen über Qutrits. In Proceedings of the 46th International Symposium on Computer Architecture, Seiten 554–566, 2019. https://doi.org/10.1145/3307650.3322253.
https: / / doi.org/ 10.1145 / 3307650.3322253
Zitiert von
[1] Zain H. Saleem, Teague Tomesh, Michael A. Perlin, Pranav Gokhale und Martin Suchara, „Divide and Conquer for Combinatorial Optimization and Distributed Quantum Computation“, arXiv: 2107.07532.
Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2022, 08:22:12 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.
Konnte nicht abrufen Crossref zitiert von Daten während des letzten Versuchs 2022-08-22 12:17:16: Von Crossref konnten keine zitierten Daten für 10.22331 / q-2022-08-22-781 abgerufen werden. Dies ist normal, wenn der DOI kürzlich registriert wurde.
Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.
