Quanten-Goemans-Williamson-Algorithmus mit dem Hadamard-Test und ungefähren Amplitudenbeschränkungen

Quanten-Goemans-Williamson-Algorithmus mit dem Hadamard-Test und ungefähren Amplitudenbeschränkungen

Zeitstempel: 12. Juli 2023, 8:29 Uhr

Taylor L. Patti1,2, Jean Kossaifi2, Anima Anandkumar3,2, und Susanne F. Yelin1

1Institut für Physik, Harvard University, Cambridge, Massachusetts 02138, USA
2NVIDIA, Santa Clara, Kalifornien 95051, USA
3Department of Computing + Mathematical Sciences (CMS), California Institute of Technology (Caltech), Pasadena, CA 91125 USA

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Semidefinite Programme sind Optimierungsmethoden mit einem breiten Anwendungsspektrum, beispielsweise zur Approximation schwieriger kombinatorischer Probleme. Ein solches semidefinites Programm ist der Goemans-Williamson-Algorithmus, eine beliebte Technik zur Ganzzahlrelaxation. Wir führen einen Variationsquantenalgorithmus für den Goemans-Williamson-Algorithmus ein, der nur $n{+}1$ Qubits, eine konstante Anzahl von Schaltkreisvorbereitungen und $text{poly}(n)$ Erwartungswerte verwendet, um semidefinite Programme näherungsweise zu lösen mit bis zu $N=2^n$ Variablen und $M sim O(N)$ Einschränkungen. Eine effiziente Optimierung wird erreicht, indem die Zielmatrix als ordnungsgemäß parametrisierte Einheit kodiert wird, die auf einem Hilfs-Qubit basiert, eine Technik, die als Hadamard-Test bekannt ist. Der Hadamard-Test ermöglicht es uns, die Zielfunktion zu optimieren, indem wir nur einen einzigen Erwartungswert des Ancilla-Qubits schätzen, anstatt exponentiell viele Erwartungswerte separat zu schätzen. In ähnlicher Weise veranschaulichen wir, dass die semidefiniten Programmierbeschränkungen effektiv durchgesetzt werden können, indem ein zweiter Hadamard-Test implementiert und eine Polynomzahl von Pauli-String-Amplitudenbeschränkungen auferlegt wird. Wir demonstrieren die Wirksamkeit unseres Protokolls, indem wir eine effiziente Quantenimplementierung des Goemans-Williamson-Algorithmus für verschiedene NP-schwere Probleme, einschließlich MaxCut, entwickeln. Unsere Methode übertrifft die Leistung analoger klassischer Methoden bei einer vielfältigen Teilmenge gut untersuchter MaxCut-Probleme aus der GSet-Bibliothek.

Quanten-Goemans-Williamson-Algorithmus mit dem Hadamard-Test und ungefähren Amplitudenbeschränkungen PlatoBlockchain Data Intelligence. Vertikale Suche. Ai.

Ausgewähltes Bild: Diagramm von HTAAC-QSDP für den Goemans-Williamson-Algorithmus mit $n=3$ Nicht-Hilfs-Qubits. a) Ein klassisches Problem von $N$-Variablen (hier ein $N$-Vertex-MaxCut-Problem mit $N=8$). Die Gewichtsmatrix $W$ wird verwendet, um das einheitliche $U_W$ zu generieren. b) Der Hadamard-Test wird verwendet, um die Zielfunktion und die Populationsausgleichsbeschränkungen effizient zu bewerten. Der $n$-Qubit-Zustand $|psirangle = U_V|mathbf{0}rangle$ wird mit einer Variationsquantenschaltung $U_V$ vorbereitet. Das $n+1$-te (Hilfs-)Qubit wird als $(|0rangle -i |1rangle)/sqrt{2}$ initialisiert. Anschließend wird der Hadamard-Test durchgeführt: $U_W$ wird als kontrolliert-unitäres, auf das Hilfs-Qubit konditioniertes Qubit implementiert, das dann gemessen wird, um $langle sigma_{n+1} rangle_{W,t} = text{Im} zu berechnen. [langle psi|U_W|psi rangle]$ oder $langle sigma_{n+1} rangle_{P,t} = text{Im}[langle psi|U_P|psi rangle]$. c) Die $M=2^n$ SDP-Amplitudenbeschränkungen werden näherungsweise nur mit $m sim text{poly}(n)$ Pauli-Stringbeschränkungen erzwungen. Diese werden berechnet, indem $n$-Qubit-Pauli-$z$-Messungen gesammelt und Randstatistiken verwendet werden, um die $m$-Erwartungswerte zu schätzen.

Populäre Zusammenfassung

Mit semidefiniten Programmen können wir eine Vielzahl schwieriger Probleme approximieren, darunter auch NP-schwere Probleme. Ein solches semidefinites Programm ist der Goemans-Williamson-Algorithmus, der schwierige Probleme wie MaxCut lösen kann. Wir führen einen Variationsquantenalgorithmus für den Goemans-Williamson-Algorithmus ein, der nur $n{+}1$ Qubits, eine konstante Anzahl von Schaltkreisvorbereitungen und eine polynomiale Anzahl von Erwartungswerten verwendet, um semidefinite Programme mit einer exponentiellen Anzahl von näherungsweise zu lösen Variablen und Einschränkungen. Wir kodieren das Problem in einen Quantenschaltkreis (oder Unitary) und lesen es auf einem einzelnen Hilfs-Qubit aus, eine Technik, die als Hadamard-Test bekannt ist. In ähnlicher Weise veranschaulichen wir, dass die Problembeschränkungen durch 1) einen zweiten Hadamard-Test und 2) eine Polynomzahl von Pauli-String-Beschränkungen erzwungen werden können. Wir demonstrieren die Wirksamkeit unseres Protokolls, indem wir eine effiziente Quantenimplementierung des Goemans-Williamson-Algorithmus für verschiedene NP-schwere Probleme, einschließlich MaxCut, entwickeln. Unsere Methode übertrifft die Leistung analoger klassischer Methoden bei einer vielfältigen Teilmenge gut untersuchter MaxCut-Probleme.

► BibTeX-Daten

► Referenzen

[1] Stephen P. Boyd und Lieven Vandenberghe. "Konvexe Optimierung". Cambridge Press. (2004).
https: / / doi.org/ 10.1017 / CBO9780511804441

[2] Michel X. Goemans. „Semidefinite Programmierung in der kombinatorischen Optimierung“. Mathematische Programmierung 79, 143–161 (1997).
https: / / doi.org/ 10.1007 / BF02614315

[3] Lieven Vandenberghe und Stephen Boyd. „Anwendungen der semidefiniten Programmierung“. Angewandte numerische Mathematik 29, 283–299 (1999).
https:/​/​doi.org/​10.1016/​S0168-9274(98)00098-1

[4] Wenjun Li, Yang Ding, Yongjie Yang, R. Simon Sherratt, Jong Hyuk Park und Jin Wang. „Parametrisierte Algorithmen grundlegender NP-schwerer Probleme: eine Umfrage“. Human-centric Computing and Information Sciences 10, 29 (2020).
https: / / doi.org/ 10.1186 / s13673-020-00226-w

[5] Christoph Helmberg. „Semidefinite Programmierung zur kombinatorischen Optimierung“. Konrad-Zuse-Zentrum für Informationstechnik Berlin. (2000).
https: / / doi.org/ 10.1007 / BF02614315

[6] Michel X. Goemans und David P. Williamson. „Verbesserte Approximationsalgorithmen für Maximum Cut- und Erfüllbarkeitsprobleme mithilfe semidefiniter Programmierung“. J. ACM 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684

[7] Florian A. Potra und Stephen J. Wright. „Interior-Point-Methoden“. Journal of Computational and Applied Mathematics 124, 281–302 (2000).
https:/​/​doi.org/​10.1016/​S0377-0427(00)00433-7

[8] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan und Zhao Song. „Eine schnellere Innenpunktmethode für die semidefinite Programmierung“. Im Jahr 2020 findet das 61. jährliche IEEE-Symposium zu Grundlagen der Informatik (FOCS) statt. Seiten 910–918. IEEE (2020).
https://​/​doi.org/​10.1109/​FOCS46700.2020.00089

[9] Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao und Ruizhe Zhang. „SDP schneller lösen: Ein robustes IPM-Framework und eine effiziente Implementierung“. Im Jahr 2022 findet das 63. jährliche IEEE-Symposium zu Grundlagen der Informatik (FOCS) statt. Seiten 233–244. IEEE (2022).
https://​/​doi.org/​10.1109/​FOCS54457.2022.00029

[10] David P. Williamson und David B. Shmoys. „Das Design von Approximationsalgorithmen“. Cambridge University Press. (2011).
https: / / doi.org/ 10.1017 / CBO9780511921735

[11] Nikolaj Moll, Panagiotis Barkoutsos, Lev S. Bishop, Jerry M. Chow, Andrew Cross, Daniel J. Egger, Stefan Filipp, Andreas Fuhrer, Jay M. Gambetta, Marc Ganzhorn, et al. „Quantenoptimierung mithilfe von Variationsalgorithmen auf kurzfristigen Quantengeräten“. Quantenwissenschaft und -technologie 3, 030503 (2018).
https: / / doi.org/ 10.1088 / 2058-9565 / aab822

[12] Edward Farhi, Jeffrey Goldstone, Sam Gutmann und Michael Sipser. „Quantenberechnung durch adiabatische Evolution“ (2000). arXiv:quant-ph/​0001106.
arXiv: quant-ph / 0001106

[13] Tameem Albash und Daniel A. Lidar. „Adiabatisches Quantenrechnen“. Rev. Mod. Phys. 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002

[14] Sepehr Ebadi, Alexander Keesling, Madelyn Cain, Tout T Wang, Harry Levine, Dolev Bluvstein, Giulia Semeghini, Ahmed Omran, JG Liu, Rhine Samajdar, et al. „Quantenoptimierung der maximalen unabhängigen Menge unter Verwendung von Rydberg-Atom-Arrays“. Science 376, 1209–1215 (2022).
https://​/​doi.org/​10.1126/​science.abo6587

[15] Tadashi Kadowaki und Hidetoshi Nishimori. „Quantenglühen im Transversalisierungsmodell“. Phys. Rev. E 58, 5355–5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355

[16] Elizabeth Gibney. „D-Wellen-Upgrade: Wie Wissenschaftler den umstrittensten Quantencomputer der Welt nutzen“. Natur 541 (2017).
https://​/​doi.org/​10.1038/​541447b

[17] Edward Farhi, Jeffrey Goldstone und Sam Gutmann. „Ein Quantennäherungsoptimierungsalgorithmus“. arXiv (2014). arXiv:1411.4028.
https://​/​doi.org/​10.48550/​arXiv.1411.4028
arXiv: 1411.4028

[18] Juan M. Arrazola, Ville Bergholm, Kamil Brádler, Thomas R. Bromley, Matt J. Collins, Ish Dhand, Alberto Fumagalli, Thomas Gerrits, Andrey Goussev, Lukas G. Helt, et al. „Quantenschaltungen mit vielen Photonen auf einem programmierbaren nanophotonischen Chip“. Natur 591, 54–60 (2021).
https:/​/​doi.org/​10.1038/​s41586-021-03202-1

[19] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore und Xiaodi Wu. „Quanten-SDP-Löser: Große Beschleunigungen, Optimalität und Anwendungen für das Quantenlernen“. 46. ​​Internationales Kolloquium über Automaten, Sprachen und Programmierung (ICALP 2019) 132, 27:1–27:14 (2019).
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.27

[20] Joran Van Apeldoorn und András Gilyén. „Verbesserungen bei der Quanten-SDP-Lösung mit Anwendungen“. In Proceedings des 46. Internationalen Kolloquiums über Automaten, Sprachen und Programmierung (2019).
https: // doi.org/ 10.4230 / LIPICS.ICALP.2019.99

[21] Joran van Apeldoorn, Andràs Gilyèn, Sander Gribling und Ronald de Wolf. „Quanten-SDP-Löser: Bessere Ober- und Untergrenzen“. Quantum 4, 230 (2020).
https:/​/​doi.org/​10.22331/​q-2020-02-14-230

[22] Fernando GSL Brandão und Krysta M. Svore. „Quantenbeschleunigungen zur Lösung semidefiniter Programme“. Im Jahr 2017 fand das 58. IEEE-Jahressymposium zu Grundlagen der Informatik (FOCS) statt. Seiten 415–426. (2017).
https: / / doi.org/ 10.1109 / FOCS.2017.45

[23] Fernando GS L. Brandão, Richard Kueng und Daniel Stilck França. „Schnellere Quanten- und klassische SDP-Näherungen für die quadratische binäre Optimierung“. Quantum 6, 625 (2022).
https:/​/​doi.org/​10.22331/​q-2022-01-20-625

[24] Dhrumil Patel, Patrick J. Coles und Mark M. Wilde. „Variative Quantenalgorithmen für semidefinite Programmierung“ (2021). arXiv:2112.08859.
arXiv: 2112.08859

[25] Anirban N. Chowdhury, Guang Hao Low und Nathan Wiebe. „Ein Variationsquantenalgorithmus zur Vorbereitung von Quanten-Gibbs-Zuständen“ (2020). arXiv:2002.00055.
arXiv: 2002.00055

[26] Taylor L. Patti, Omar Shehab, Khadijeh Najafi und Susanne F. Yelin. „Markov Chain Monte Carlo verbesserte Variationsquantenalgorithmen“. Quantenwissenschaft und -technologie 8, 015019 (2022).
https://​/​doi.org/​10.1088/​2058-9565/​aca821

[27] Youle Wang, Guangxi Li und Xin Wang. „Variative Quanten-Gibbs-Zustandsvorbereitung mit einer verkürzten Taylor-Reihe“. Physical Review Applied 16, 054035 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054035

[28] Sanjeev Arora, Elad Hazan und Satyen Kale. „Die multiplikative Gewichtungsaktualisierungsmethode: Ein Metaalgorithmus und Anwendungen“. Theory of Computing 8, 121–164 (2012).
https: / / doi.org/ 10.4086 / toc.2012.v008a006

[29] Iordanis Kerenidis und Anupam Prakash. „Eine Quanten-Innere-Punkt-Methode für LPS und SDPS“. ACM-Transaktionen zum Quantencomputing 1 (2020).
https: / / doi.org/ 10.1145 / 3406306

[30] Brandon Augustino, Giacomo Nannicini, Tamás Terlaky und Luis F. Zuluaga. „Quantum Interior Point-Methoden zur semidefiniten Optimierung“ (2022). arXiv:2112.06025.
arXiv: 2112.06025

[31] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio und Patrick J. Coles. „Variative Quantenalgorithmen“. Nature Reviews Physics 3, 625–644 (2021).
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[32] Kishor Bharti, Tobias Haug, Vlatko Vedral und Leong-Chuan Kwek. „Verrauschter Quantenalgorithmus mittlerer Skala für semidefinite Programmierung“. Physik. Rev. A 105, 052445 (2022).
https: / / doi.org/ 10.1103 / PhysRevA.105.052445

[33] Lennart Bittel und Martin Kliesch. „Das Training von Variationsquantenalgorithmen ist np-schwer.“ Physik. Rev. Lett. 127, 120502 (2021).
https://doi.org/ 10.1103/PhysRevLett.127.120502

[34] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush und Hartmut Neven. „Karge Plateaus in Trainingslandschaften für quantenneuronale Netze“. Nature Communications 9, 4812 (2018).
https:/​/​doi.org/​10.1038/​s41467-018-07090-4

[35] Carlos Ortiz Marrero, Mária Kieferová und Nathan Wiebe. „Verschränkungsbedingte karge Plateaus“. PRX Quantum 2, 040316 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.040316

[36] Taylor L. Patti, Khadijeh Najafi, Xun Gao und Susanne F. Yelin. „Verschränkung ersann die Abmilderung des kargen Plateaus“. Physik. Rev. Res. 3, 033090 (2021).
https: / / doi.org/ 10.1103 / PhysRevResearch.3.033090

[37] Arthur Pesah, M. Cerezo, Samson Wang, Tyler Volkoff, Andrew T. Sornborger und Patrick J. Coles. „Fehlen unfruchtbarer Plateaus in Quantenfaltungs-Neuronalen Netzen“. Physik. Rev. X 11, 041011 (2021).
https://doi.org/ 10.1103/PhysRevX.11.041011

[38] Dorit Aharonov, Vaughan Jones und Zeph Landau. „Ein polynomialer Quantenalgorithmus zur Approximation des Jones-Polynoms“. Algorithmica 55, 395–421 (2009).
https:/​/​doi.org/​10.1007/​s00453-008-9168-0

[39] Clayton W. Kommandant. „Maximales Schnittproblem, maximaler Schnitt, maximales Schnittproblem, maximaler Schnitt“. Seiten 1991–1999. Springer USA. Boston, MA (2009).
https:/​/​doi.org/​10.1007/​978-0-387-74759-0_358

[40] Steven J. Benson, Yinyu Yeb und Xiong Zhang. „Gemischte lineare und semidefinite Programmierung zur kombinatorischen und quadratischen Optimierung“. Optimierungsmethoden und Software 11, 515–544 (1999).
https: / / doi.org/ 10.1080 / 10556789908805761

[41] Changhui Choi und Yinyu Ye. „Lösen spärlicher semidefiniter Programme unter Verwendung des dualen Skalierungsalgorithmus mit einem iterativen Löser“. Manuskript, Department of Management Sciences, University of Iowa, Iowa City, IA 52242 (2000). URL: web.stanford.edu/​ yyye/​yyye/​cgsdp1.pdf.
https://​/​web.stanford.edu/​~yyye/​yyye/​cgsdp1.pdf

[42] Angelika Wiegele. „Biq-Mac-Bibliothek – eine Sammlung von Max-Cut- und quadratischen 0-1-Programmierinstanzen mittlerer Größe“. Alpen-Adria-Universität Klagenfurt (2007). URL: biqmac.aau.at/​biqmaclib.pdf.
https://​/​biqmac.aau.at/​biqmaclib.pdf

[43] Stefan H. Schmieta. „Die Dimacs-Bibliothek gemischter semidefinit-quadratisch-linearer Programme“. 7. DIMACS-Implementierungsherausforderung (2007). URL: http://archive.dimacs.rutgers.edu.
http://archive.dimacs.rutgers.edu

[44] Yoshiki Matsuda. „Benchmarking des Max-Cut-Problems auf der simulierten Bifurkationsmaschine“. Mittel (2019). URL: medium.com/​toshiba-sbm/​benchmarking-the-max-cut-problem-on-the-simulated-bifurcation-machine-e26e1127c0b0.
https://​/​medium.com/​toshiba-sbm/​benchmarking-the-max-cut-problem-on-the-simulated-bifurcation-machine-e26e1127c0b0

[45] RM Karp. „Reduzierbarkeit bei kombinatorischen Problemen“. Springer USA. Boston, MA (1972).

[46] Dimitri P Bertsekas. „Eingeschränkte Optimierung und Lagrange-Multiplikatormethoden“. Akademische Presse. (1982).
https:/​/​doi.org/​10.1016/​C2013-0-10366-2

[47] G Mauro D'Ariano, Matteo GA Paris und Massimiliano F Sacchi. „Quantentomographie“. Fortschritte in der Bildgebung und Elektronenphysik 128, 206–309 (2003).
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​0302028
arXiv: quant-ph / 0302028

[48] Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D'Ariano, Stefano Facchini und Paolo Perinotti. „Optimale Quantentomographie“. IEEE Journal of Selected Topics in Quantum Electronics 15, 1646–1660 (2009).
https: / / doi.org/ 10.1109 / JSTQE.2009.2029243

[49] Max S. Kaznady und Daniel FV James. „Numerische Strategien für die Quantentomographie: Alternativen zur vollständigen Optimierung“. Physik. Rev. A 79, 022109 (2009).
https: / / doi.org/ 10.1103 / PhysRevA.79.022109

[50] Javier Peña. „Konvergenz von Methoden erster Ordnung über das konvexe Konjugat“. Operations Research Letters 45, 561–564 (2017).
https://​/​doi.org/​10.1016/​j.orl.2017.08.013

[51] Alan Frieze und Mark Jerrum. „Verbesserte Approximationsalgorithmen für Maxk-Cut und Max Bisection“. Algorithmica 18, 67–81 (1997).
https: / / doi.org/ 10.1007 / BF02523688

[52] Clark David Thompson. „Eine Komplexitätstheorie für vlsi“. Doktorarbeit. Carnegie Mellon Universität. (1980). URL: dl.acm.org/​doi/​10.5555/​909758.
https: / / dl.acm.org/ doi / 10.5555 / 909758

[53] Chu Min Li und Felip Manya. „Maxsat, harte und weiche Beschränkungen“. Im Handbuch der Erfüllbarkeit. Seiten 903–927. IOS Press (2021).
https:/​/​doi.org/​10.3233/​978-1-58603-929-5-613

[54] Nicholas J. Higham. „Berechnung der nächstgelegenen Korrelationsmatrix – ein Problem aus der Finanzwelt“. IMA Journal of Numerical Analysis 22, 329–343 (2002).
https://​/​doi.org/​10.1093/​imanum/​22.3.329

[55] Tadayoshi Fushiki. „Schätzung positiver semidefiniter Korrelationsmatrizen unter Verwendung konvexer quadratischer semidefiniter Programmierung“. Neural Computation 21, 2028–2048 (2009).
https://​/​doi.org/​10.1162/​neco.2009.04-08-765

[56] Todd MJ. „Eine Untersuchung der Suchrichtungen in primal-dualen Innenpunktmethoden für semidefinite Programmierung“. Optimierungsmethoden und Software 11, 1–46 (1999).
https: / / doi.org/ 10.1080 / 10556789908805745

[57] Roger Fletcher. „Straffunktionen“. Mathematische Programmierung: Stand der Technik: Bonn 1982, Seiten 87–114 (1983).
https:/​/​doi.org/​10.1007/​978-3-642-68874-4_5

[58] Robert M. Freund. „Straf- und Barrierenmethoden für eingeschränkte Optimierung“. Vorlesungsunterlagen, Massachusetts Institute of Technology (2004). URL: ocw.mit.edu/​courses/​15-084j-nonlinear-programming-spring-2004.
https://​/​ocw.mit.edu/​courses/​15-084j-nonlinear-programming-spring-2004

[59] Eric Ricardo Anschütz. „Kritische Punkte in quantengenerativen Modellen“. In der Internationalen Konferenz über Lernrepräsentationen. (2022). URL: openreview.net/​forum?id=2f1z55GVQN.
https://​/​openreview.net/​forum?id=2f1z55GVQN

[60] Amir Beck. „Methoden erster Ordnung in der Optimierung“. SIAM. (2017).
https: / / doi.org/ 10.1137 / 1.9781611974997

[61] Sanjeev Arora und Satyen Kale. „Ein kombinatorischer, primär-dualer Ansatz für semidefinite Programme“. J. ACM 63 (2016).
https: / / doi.org/ 10.1145 / 2837020

[62] Taylor L. Patti, Jean Kossaifi, Susanne F. Yelin und Anima Anandkumar. „Tensorly-Quantum: Quantenmaschinelles Lernen mit Tensormethoden“ (2021). arXiv:2112.10239.
arXiv: 2112.10239

[63] Jean Kossaifi, Yannis Panagakis, Anima Anandkumar und Maja Pantic. „Tensorly: Tensor-Lernen in Python“. Journal of Machine Learning Research 20, 1–6 (2019). URL: http://​/​jmlr.org/​papers/​v20/​18-277.html.
http: // jmlr.org/ papers / v20 ​​/ 18-277.html

[64] cuQuantum-Team. „Nvidia/​cuquantum: cuquantum v22.11“ (2022).

[65] Diederik P. Kingma und Jimmy Ba. „Adam: Eine Methode zur stochastischen Optimierung“ (2017). arXiv:1412.6980.
arXiv: 1412.6980

[66] Brahim Chaourar. „Ein linearer Zeitalgorithmus für eine Variante des Max-Cut-Problems in seriell parallelen Graphen“. Fortschritte in der Operationsforschung (2017).
https: / / doi.org/ 10.1155 / 2017/1267108

[67] Juri Makarytschew. „Ein kurzer Beweis für Kuratowskis Graphplanaritätskriterium“. Journal of Graph Theory 25, 129–131 (1997).
<a href="https://doi.org/10.1002/(SICI)1097-0118(199706)25:23.0.CO;2-O”>https:/​/​doi.org/​10.1002/​(SICI)1097-0118(199706)25:2<129::AID-JGT4>3.0.CO;2-O

[68] Béla Bollobás. „Die Entwicklung zufälliger Graphen – die riesige Komponente“. Seite 130–159. Cambridge-Studien in fortgeschrittener Mathematik. Cambridge University Press. (2001). 2. Auflage.
https: / / doi.org/ 10.1017 / CBO9780511814068.008

[69] Sanjeev Arora, David Karger und Marek Karpinski. „Polynomiale Zeitnäherungsschemata für dichte Instanzen von NP-schweren Problemen“. Journal of Computer and System Sciences 58, 193–210 (1999).
https: / / doi.org/ 10.1006 / jcss.1998.1605

[70] Rick Durrett. „Erdös-rényi-Zufallsgraphen“. Seite 27–69. Cambridge-Reihe in statistischer und probabilistischer Mathematik. Cambridge University Press. (2006).
https: / / doi.org/ 10.1017 / CBO9780511546594.003

[71] Gary Chartrand und Ping Zhang. „Chromatische Graphentheorie“. Taylor und Francis. (2008).
https: / / doi.org/ 10.1201 / 9781584888017

[72] John van de Wetering. „Zx-Kalkül für den arbeitenden Quanteninformatiker“ (2020). arXiv:2012.13966.
arXiv: 2012.13966

[73] Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons und Seyon Sivarajah. „Phasen-Gadget-Synthese für flache Schaltkreise“. Electronic Proceedings in Theoretical Computer Science 318, 213–228 (2020).
https: / / doi.org/ 10.4204 / eptcs.318.13

[74] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe und Shuchen Zhu. „Theorie des Traberfehlers mit Kommutator-Skalierung“. Phys. Rev. X 11, 011020 (2021).
https://doi.org/ 10.1103/PhysRevX.11.011020

[75] Joseph W. Britton, Brian C. Sawyer, Adam C. Keith, CC Joseph Wang, James K. Freericks, Hermann Uys, Michael J. Biercuk und John J. Bollinger. „Entwickelte zweidimensionale Ising-Wechselwirkungen in einem Quantensimulator für gefangene Ionen mit Hunderten von Spins.“ Natur 484, 489–492 (2012).
https: / / doi.org/ 10.1038 / nature10981

[76] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, Soonwon Choi, Alexander S. Zibrov, Manuel Endres, Markus Greiner, et al. "Untersuchung der Vielteilchendynamik an einem 51-Atom-Quantensimulator". Natur 551, 579–584 (2017).
https: / / doi.org/ 10.1038 / nature24622

[77] Gheorghe-Sorin Paraoanu. „Neueste Fortschritte in der Quantensimulation mit supraleitenden Schaltkreisen“. Journal of Low Temperature Physics 175, 633–654 (2014).
https:/​/​doi.org/​10.1007/​s10909-014-1175-8

[78] Katsuki Fujisawa, Hitoshi Sato, Satoshi Matsuoka, Toshio Endo, Makoto Yamashita und Maho Nakata. „Hochleistungsfähiger allgemeiner Löser für extrem große semidefinite Programmierprobleme“. In SC '12: Tagungsband der International Conference on High Performance Computing, Networking, Storage and Analysis. Seiten 1–11. (2012).
https://​/​doi.org/​10.1109/​SC.2012.67

[79] Adrian S. Lewis und Michael L. Overton. „Eigenwertoptimierung“. Acta Numerica 5, 149–190 (1996).
https: / / doi.org/ 10.1017 / S0962492900002646

[80] Xiaosi Xu, Jinzhao Sun, Suguru Endo, Ying Li, Simon C. Benjamin und Xiao Yuan. „Variationsalgorithmen für die lineare Algebra“. Science Bulletin 66, 2181–2188 (2021).
https: / / doi.org/ 10.1016 / j.scib.2021.06.023

Zitiert von

Konnte nicht abrufen Crossref zitiert von Daten während des letzten Versuchs 2023-07-12 14:07:40: Von Crossref konnten keine zitierten Daten für 10.22331 / q-2023-07-12-1057 abgerufen werden. Dies ist normal, wenn der DOI kürzlich registriert wurde. Auf SAO / NASA ADS Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2023-07-12 14:07:40).

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.

Zeitstempel:

Mehr von Quantenjournal