[ad_1]
Problem Quantum Max Cut (QMC) pojawił się jako problem testowy do projektowania algorytmów aproksymacyjnych dla lokalnych problemów hamiltonianowych. W tym artykule atakujemy ten problem używając algebraicznej struktury QMC, w szczególności związku pomiędzy Hamiltonianem kwantowego maksymalnego cięcia a teorią reprezentacji grupy symetrycznej.
Pierwszym głównym wkładem tego artykułu jest rozszerzenie technik optymalizacji niekomutatywnej sumy kwadratów (ncSoS) w celu uzyskania nowej hierarchii relaksacji dla kwantowego maksymalnego cięcia. Przedstawiona przez nas hierarchia opiera się na optymalizacji wielomianów w operatorach zamiany kubitów. Jest to przeciwieństwo „standardowej” kwantowej hierarchii Lasserre’a, która opiera się na wielomianach wyrażonych w macierzach Pauliego. Aby udowodnić poprawność tej hierarchii, wykorzystujemy skończoną prezentację algebry generowanej przez operatory zamiany kubitów. Prezentacja ta pozwala na wykorzystanie komputerowych technik algebraicznych do manipulowania i upraszczania wielomianów zapisanych w terminach operatorów zamiany i może być przedmiotem niezależnego zainteresowania. Zaskakujące jest to, że poziom 2 tej nowej hierarchii jest numerycznie dokładny (do tolerancji $10^{-7}$) dla wszystkich instancji QMC z jednakowymi wagami krawędzi na grafach o co najwyżej 8 wierzchołkach.
Drugim głównym wkładem tej pracy jest algorytm wielomianowy, który oblicza (w dokładnej arytmetyce) maksymalną wartość własną hamiltonianu QMC dla pewnych grafów, w tym grafów, które można „rozłożyć” jako podpisaną kombinację klików. Szczególnym przypadkiem tych ostatnich są kompletne grafy dwudzielne o jednakowych wagach krawędzi, dla których dokładne rozwiązania są znane z pracy Lieba i Mattisa [33]. Nasze metody, które wykorzystują teorię reprezentacji grupy symetrycznej, mogą być postrzegane jako uogólnienie wyniku Lieba-Mattisa.
[1] Anurag Anshu, David Gosset i Karen Morenz. Beyond Product State Approximations for a Quantum Analogue of Max Cut. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography TQC 2020, tom 158 Leibniz International Proceedings in Informatics (LIPIcs), strony 7:1-7:15, Ryga, Łotwa, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing. OCLC: 1194977622. URL: https://drops.dagstuhl.de/opus/volltexte/2020/12066, doi:10.4230/LIPIcs.TQC.2020.7.
https://doi.org/10.4230/LIPIcs.TQC.2020.7
https://drops.dagstuhl.de/opus/volltexte/2020/12066
[2] Jacob C Bridgeman i Christopher T Chubb. Machanie rękami i taniec interpretacyjny: kurs wprowadzający do sieci tensorowych. Journal of Physics A: Mathematical and Theoretical, 50(22):223001, maj 2017. URL: https://dx.doi.org/10.1088/1751-8121/aa6dc3, doi:10.1088/1751-8121/aa6dc3.
https://doi.org/10.1088/1751-8121/aa6dc3
[3] Wieb Bosma, John Cannon i Catherine Playoust. System algebry Magma. I. The user language. J. Symbolic Comput., 24(3-4):235-265, 1997. Computational algebra and number theory (Londyn, 1993). URL: http://dx.doi.org/10.1006/jsco.1996.0125, doi:10.1006/jsco.1996.0125.
https://doi.org/10.1006/jsco.1996.0125
[4] Magali Bardet, Jean-Charles Faugère i Bruno Salvy. On the complexity of the $F_5$ Gröbner basis algorithm. J. Symb. Comput., 70:49-70, 2015. doi:10.1016/j.jsc.2014.09.025.
https://doi.org/10.1016/j.jsc.2014.09.025
[5] Sergey Bravyi, David Gosset, Robert König i Kristan Temme. Approximation algorithms for quantum many-body problems. Journal of Mathematical Physics, 60(3):032203, marzec 2019. URL: http://aip.scitation.org/doi/10.1063/1.5085428, doi:10.1063/1.5085428.
https://doi.org/10.1063/1.5085428
[6] Fernando G.S.L. Brandao i Aram W. Harrow. Przybliżenia stanu produktu do kwantowych stanów podstawowych. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, strona 871-880, Nowy Jork, NY, USA, 2013. Association for Computing Machinery. doi:10.1145/2488608.2488719.
https://doi.org/10.1145/2488608.2488719
[7] Sabine Burgdorf, Igor Klep, and Janez Povh. Optimization of polynomials in non-commuting variables. SpringerBriefs in Mathematics. Springer, [Cham], 2016. doi:10.1007/978-3-319-33338-0.
https://doi.org/10.1007/978-3-319-33338-0
[8] Calum Buchanan, Christopher Purcell i Puck Rombach. Uzupełnianie podgrafów i minimalna ranga. Electron. J. Combin., 29(1):Paper No. 1.38, 20, 2022. doi:10.37236/10383.
https://doi.org/10.37236/10383
[9] Boaz Barak, Prasad Raghavendra i David Steurer. Rounding semidefinite programming hierarchies via global correlation. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science-FOCS 2011, strony 472-481. IEEE Computer Soc., Los Alamitos, CA, 2011. doi:10.1109/FOCS.2011.95.
https://doi.org/10.1109/FOCS.2011.95
[10] David A. Cox, John Little i Donal O’Shea. Ideały, odmiany i algorytmy. Wprowadzenie do obliczeniowej geometrii algebraicznej i algebry przemiennej. Undergraduate Texts in Mathematics. Springer, Cham, wydanie czwarte, 2015. doi:10.1007/978-3-319-16721-3.
https://doi.org/10.1007/978-3-319-16721-3
[11] Toby S. Cubitt, Ashley Montanaro i Stephen Piddock. Uniwersalne kwantowe hamiltoniany. Proceedings of the National Academy of Sciences, 115(38):9497-9502, wrzesień 2018. URL: https://pnas.org/doi/full/10.1073/pnas.1804949115, doi:10.1073/pnas.1804949115.
https://doi.org/10.1073/pnas.1804949115
[12] J. Ignacio Cirac, David Pérez-García, Norbert Schuch i Frank Verstraete. Stany iloczynu macierzy i rzutowane stany splątanej pary: Koncepcje, symetrie, twierdzenia. Rev. Mod. Phys., 93:045003, grudzień 2021. URL: https://doi.org/10.1103/RevModPhys.93.045003, doi:10.1103/RevModPhys.93.045003.
https://doi.org/10.1103/RevModPhys.93.045003
[13] Etienne de Klerk. Aspects of semidefinite programming, tom 65 Optymalizacji Stosowanej. Kluwer Academic Publishers, Dordrecht, 2002. Interior point algorithms and selected applications. doi:10.1007/b105286.
https://doi.org/10.1007/b105286
[14] Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner i Stephanie Wehner. The quantum moment problem and bounds on entangled multi-prover games. In 2008 23rd Annual IEEE Conference on Computational Complexity, strony 199-210. IEEE, 2008. doi:10.1109/CCC.2008.26.
https://doi.org/10.1109/CCC.2008.26
[15] Pavel Etingof, Oleg Golberg, Sebastian Hensel, Tiankai Liu, Alex Schwendner, Dmitry Vaintrob i Elena Yudovina. Introduction to representation theory, tom 59 Student Mathematical Library. American Mathematical Society, Providence, RI, 2011. With historical interludes by Slava Gerovitch. doi:10.1090/stml/059.
https://doi.org/10.1090/stml/059
[16] Renato M. Fonseca. Groupmath: Pakiet mathematica do obliczeń teorii grup. 2020. arXiv:2011.01764 [hep-th]. arXiv:arXiv:2011.01764, doi:10.1016/j.cpc.2021.108085.
https://doi.org/10.1016/j.cpc.2021.108085
arXiv:arXiv:2011.01764
[17] Sevag Gharibian i Julia Kempe. Approximation algorithms for QMA-complete problems. SIAM Journal on Computing, 41(4):1028-1050, 2012. doi:10.1137/110842272.
https://doi.org/10.1137/110842272
[18] Sevag Gharibian i Ojas Parekh. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. tom 145 Leibniz International Proceedings in Informatics (LIPIcs), strony 31:1-31:17. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Rozmiar grafiki: 17 stron Medium: aplikacja/pdf Wydawca: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Niemcy Numer wersji: 1.0. URL: http://drops.dagstuhl.de/opus/volltexte/2019/11246/, doi:10.4230/LIPICS.APPROX-RANDOM.2019.31.
https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31
http://drops.dagstuhl.de/opus/volltexte/2019/11246/
[19] Edward L. Green. Multiplicative bases, Gröbner bases, and right Gröbner bases. Journal of Symbolic Computation, 29(4-5):601-623, 2000. doi:10.1006/jsco.1999.0324.
https://doi.org/10.1006/jsco.1999.0324
[20] Michel X. Goemans i David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115-1145, listopad 1995. URL: https://dl.acm.org/doi/10.1145/227683.227684, doi:10.1145/227683.227684.
https://doi.org/10.1145/227683.227684
[21] Aram Wettroth Harrow. The church of the symmetric subspace, sierpień 2013. arXiv:1308.6595 [quant-ph]. doi:10.48550/arXiv.1308.6595.
https://doi.org/10.48550/arXiv.1308.6595
arXiv:1308.6595
[22] J. William Helton i Scott McCullough. A Positivstellensatz for noncommutative polynomials. Transactions of the American Mathematical Society, 356(9):3721- 3737, 2004. doi:10.1016/j.aim.2012.04.028.
https://doi.org/10.1016/j.aim.2012.04.028
[23] Aram W. Harrow i Ashley Montanaro. Ekstremalne wartości własne lokalnych hamiltonianów. Quantum, 1:6, kwiecień 2017. doi:10.22331/q-2017-04-25-6.
https://doi.org/10.22331/q-2017-04-25-6
[24] Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson i John Wright. Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell’s inequality, wrzesień 2022. arXiv:2111.01254 [quant-ph]. URL: http://arxiv.org/abs/2111.01254, doi:10.48550/arXiv.2111.01254.
https://doi.org/10.48550/arXiv.2111.01254
arXiv:2111.01254
[25] Matthew B. Hastings i Ryan O’Donnell. Optymalizacja silnie oddziałujących hamiltonianów fermionowych. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, strona 776-789, Nowy Jork, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/3519935.3519960.
https://doi.org/10.1145/3519935.3519960
[26] Gordon Douglas James. The representation theory of the symmetric groups, tom 682. Springer, 2006. doi:10.1007/BFb0067708.
https://doi.org/10.1007/BFb0067708
[27] Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, strony 767-775, 2002. doi:10.1145/509907.510017.
https://doi.org/10.1145/509907.510017
[28] Robbie King. Ulepszony algorytm aproksymacji dla kwantowego maksymalnego cięcia na grafach bez trójkątów. Quantum, 7:1180, listopad 2023. doi:10.22331/q-2023-11-09-1180.
https://doi.org/10.22331/q-2023-11-09-1180
[29] Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local hamiltonian problem. SIAM Journal on Computing, 35(5):1070-1097, 2006. arXiv:https://doi.org/10.1137/S0097539704445226, doi:10.1137/S0097539704445226.
https://doi.org/10.1137/S0097539704445226
arXiv:
[30] Se-Jin Kim, Vern Paulsen i Christopher Schafhauser. Gra synchroniczna dla binarnych systemów ograniczeń. Journal of Mathematical Physics, 59(3):032201, 2018. doi:10.1063/1.4996867.
https://doi.org/10.1063/1.4996867
[31] Alexei Ju Kitaev, Aleksandr Ch Shen i Michail N. Vyalyi. Obliczenia klasyczne i kwantowe. Numer 47 w Graduate studies in mathematics. American Mathematical Society, Providence, RI, 2002. doi:10.1090/gsm/047.
https://doi.org/10.1090/gsm/047
[32] Eunou Lee. Optymalizacja parametrów obwodu kwantowego za pomocą SDP. In 33rd International Symposium on Algorithms and Computation, volume 248 of LIPIcs. Leibniz Int. Proc. Inform., strony Paper No. 48, 16. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022. doi:10.4230/lipics.isaac.2022.48.
https://doi.org/10.4230/lipics.isaac.2022.48
[33] Elliott Lieb i Daniel Mattis. Ordering energy levels of interacting spin systems. Journal of Mathematical Physics, 3(4):749-751, styczeń 1962. doi:10.1063/1.1724276.
https://doi.org/10.1063/1.1724276
[34] Fedor Levkovich-Maslyuk. The Bethe Ansatz. Journal of Physics A: Mathematical and Theoretical, 49(32):323004, 2016. doi:10.1088/1751-8113/49/32/323004.
https://doi.org/10.1088/1751-8113/49/32/323004
[35] Zeph Landau, Umesh Vazirani i Thomas Vidick. A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians. Nature Physics, 11(7):566-569, 2015. doi:10.1038/nphys3345.
https://doi.org/10.1038/nphys3345
[36] Ferdinando Mora. Groebner bases for noncommutative polynomial rings. In Algebraic algorithms and error correcting codes (Grenoble, 1985), tom 229 Lecture Notes in Comput. Sci., strony 353-362. Springer, Berlin, 1986. URL: https://doi.org/10.1007/3-540-16776-5_740, doi:10.1007/3-540-16776-5_740.
https://doi.org/10.1007/3-540-16776-5_740
[37] Miguel Navascués, Stefano Pironio i Antonio Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 10(7):073013, lipiec 2008. URL: https://iopscience.iop.org/article/10.1088/1367-2630/10/7/073013, doi:10.1088/1367-2630/10/7/073013.
https://doi.org/10.1088/1367-2630/10/7/073013
[38] Tobias J. Osborne. Statics and dynamics of quantum ${XY}$ and Heisenberg systems on graphs. Physical Review B, 74:094411, Sep 2006. URL: https://doi.org/10.1103/PhysRevB.74.094411, doi:10.1103/PhysRevB.74.094411.
https://doi.org/10.1103/PhysRevB.74.094411
[39] Maurice Pouzet, Hamza Si Kaddour i Bhalchandra Thatte. O wymiarze boole’owskim grafu i innych powiązanych parametrach. Discrete Mathematics & Theoretical Computer Science, 23(Special issues):2, #5, 2022. doi:10.46298/dmtcs.7437.
https://doi.org/10.46298/dmtcs.7437
[40] Stephen Piddock i Ashley Montanaro. Złożoność oddziaływań antyferromagnetycznych i sieci 2D. Quantum Information & Computation, 17(7&8):636-672, 2017. doi:10.26421/QIC17.7-8-6.
https://doi.org/10.26421/QIC17.7-8-6
[41] Claudio Procesi. Lie groups. Universitext. Springer, New York, 2007. An approach through invariants and representations. doi:10.1007/978-0-387-28929-8.
https://doi.org/10.1007/978-0-387-28929-8
[42] Claudio Procesi. Uwaga na temat funkcji Formanka Weingartena. Note Mat., 41(1):69-109, 2021. doi:10.1285/i15900932v41n1p69.
https://doi.org/10.1285/i15900932v41n1p69
[43] Ojas Parekh i Kevin Thompson. Zastosowanie kwantowej hierarchii Lasserre’a poziomu 2 w kwantowych algorytmach aproksymacji. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), tom 198 Leibniz International Proceedings in Informatics (LIPIcs), strony 102:1-102:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. URL: https://drops.dagstuhl.de/opus/volltexte/2021/14171, doi:10.4230/LIPIcs.ICALP.2021.102.
https://doi.org/10.4230/LIPIcs.ICALP.2021.102
https://drops.dagstuhl.de/opus/volltexte/2021/14171
[44] Ojas Parekh i Kevin Thompson. An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms, czerwiec 2022. arXiv:2206.08342 [quant-ph]. URL: http://arxiv.org/abs/2206.08342, doi:10.48550/arXiv.2206.08342.
https://doi.org/10.48550/arXiv.2206.08342
arXiv:2206.08342
[45] Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the fortieth annual ACM symposium on Theory of computing, strony 245-254, 2008. doi:10.1145/1374376.1374414.
https://doi.org/10.1145/1374376.1374414
[46] Prasad Raghavendra. Approximating NP-hard problems efficient algorithms and their limits. University of Washington, 2009. Praca doktorska.
[47] Richard P. Stanley. Enumerative combinatorics. Vol. 2, tom 62 Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. doi:10.1017/CBO9780511609589.
https://doi.org/10.1017/CBO9780511609589
[48] Jun Takahashi, Chaithanya Rayudu, Cunlu Zhou, Robbie King, Kevin Thompson i Ojas Parekh. An SU(2)-symmetric semidefinite programming hierarchy for Quantum Max Cut. preprint.
[49] Xingqiang Xiu. Niekomutatywne bazy Gröbnera i zastosowania. Praca doktorska, 2012.
[ad_2]