Un algoritm de aproximare îmbunătățit pentru Quantum Max-Cut pe grafice fără triunghi

Un algoritm de aproximare îmbunătățit pentru Quantum Max-Cut pe grafice fără triunghi

Marca temporală: 9 noiembrie 2023, ora 6:44

Robbie King

Departamentul de calcul și științe matematice, Caltech

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

Oferim un algoritm de aproximare pentru Quantum Max-Cut care funcționează prin rotunjirea unei relaxări SDP la o stare cuantică încurcată. SDP este utilizat pentru a alege parametrii unui circuit cuantic variațional. Starea încâlcită este apoi reprezentată ca circuitul cuantic aplicat unei stări de produs. Se realizează un raport de aproximare de 0.582 pe grafice fără triunghi. Cei mai buni algoritmi anteriori ai lui Anshu, Gosset, Morenz și Parekh, Thompson au obținut rapoarte de aproximare de 0.531 și, respectiv, 0.533. În plus, studiem Hamiltonianul EPR, despre care considerăm că este o problemă intermediară naturală care izolează unele caracteristici cuantice cheie ale problemelor Hamiltoniene locale. Pentru Hamiltonianul EPR, oferim un algoritm de aproximare cu raport de aproximare $1 / sqrt{2}$ pe toate graficele.

Un algoritm de aproximare îmbunătățit pentru Quantum Max-Cut pe grafice fără triunghi PlatoBlockchain Data Intelligence. Căutare verticală. Ai.

Imagine prezentată: vecinătatea locală a muchiei într-un grafic fără triunghi.

[Conținutul încorporat]

Rezumat popular

Cum putem rotunji o relaxare SDP la o stare cuantică încurcată? Și cum ar trebui să optimizăm un circuit variațional ansatz? În această lucrare, rezolvăm aceste două probleme combinându-le: Utilizați soluția SDP pentru a alege parametrii circuitului variațional.

► Date BibTeX

► Referințe

[1] Anurag Anshu, David Gosset și Karen Morenz. Dincolo de aproximările stării produsului pentru un analog cuantic al tăieturii maxime. În cea de-a 15-a conferință privind teoria calculului cuantic, comunicării și criptografiei, 2020. https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2020.7.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.7

[2] Anurag Anshu, David Gosset, Karen Morenz și Mehdi Soleimanifar. Algoritmi de aproximare îmbunătățiți pentru hamiltonieni locali cu grad mărginit. Physical Review Letters, 127(25):250502, 2021. https:/​/​doi.org/​10.1103/​PhysRevLett.127.250502.
https: / / doi.org/ 10.1103 / PhysRevLett.127.250502

[3] Jop Briët, Fernando Mário de Oliveira Filho și Frank Vallentin. Inegalități Grothendieck pentru programe semidefinite cu constrângere de rang. Theory OF Computing, 10(4):77–105, 2014. https://​/​doi.org/​10.4086/​toc.2014.v010a004.
https: / / doi.org/ 10.4086 / toc.2014.v010a004

[4] Sergey Bravyi, David Gosset, Robert König și Kristan Temme. Algoritmi de aproximare pentru probleme cuantice cu mai multe corpuri. Journal of Mathematical Physics, 60(3):032203, 2019. https:/​/​doi.org/​10.1063/​1.5085428.
https: / / doi.org/ 10.1063 / 1.5085428

[5] Fernando GSL Brandao și Aram W Harrow. Aproximații de stare de produs la stările cuantice. Communications in Mathematical Physics, 342:47–80, 2016. https://​/​doi.org/​10.1007/​s00220-016-2575-1.
https:/​/​doi.org/​10.1007/​s00220-016-2575-1

[6] Toby Cubitt și Ashley Montanaro. Clasificarea complexității problemelor hamiltoniene locale. SIAM Journal on Computing, 45(2):268–316, 2016. https://​/​doi.org/​10.1137/​140998287.
https: / / doi.org/ 10.1137 / 140998287

[7] Uriel Feige și Gideon Schechtman. Despre optimitatea tehnicii de rotunjire aleatoare a hiperplanului pentru tăierea maximă. Random Structures & Algorithms, 20(3):403–440, 2002. https://​/​doi.org/​10.1002/​rsa.10036.
https://​/​doi.org/​10.1002/​rsa.10036

[8] Sevag Gharibian și Julia Kempe. Algoritmi de aproximare pentru probleme qma-complete. SIAM Journal on Computing, 41(4):1028–1050, 2012. https://​/​doi.org/​10.1137/​110842272.
https: / / doi.org/ 10.1137 / 110842272

[9] Sevag Gharibian și Ojas Parekh. Algoritmi de aproximare clasici aproape optimi pentru o generalizare cuantică a max-cut. În aproximare, randomizare și optimizare combinatorie. Algoritmi și tehnici (APROX/​RANDOM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. https:/​/​doi.org/​10.4230/​LIPIcs.APPROX-RANDOM.2019.31.
https://​/​doi.org/​10.4230/​LIPIcs.APPROX-RANDOM.2019.31

[10] Michel Goemans și David Williamson. Algoritmi de aproximare îmbunătățiți pentru probleme maxime de tăiere și satisfacție folosind programare semidefinită. Journal of the ACM (JACM), 42(6):1115–1145, 1995. https://​/​doi.org/​10.1145/​227683.227684.
https: / / doi.org/ 10.1145 / 227683.227684

[11] Johan Håstad. Câteva rezultate optime de inaproximabilitate. Journal of the ACM (JACM), 48(4):798–859, 2001. https://​/​doi.org/​10.1145/​502090.502098.
https: / / doi.org/ 10.1145 / 502090.502098

[12] Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson și John Wright. Duritatea unică a jocurilor cuantice max-cut și o inegalitate presupusă a lui Borell cu valoare vectorială. În Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), paginile 1319–1384. SIAM, 2023. https:/​/​doi.org/​10.1137/​1.9781611977554.ch48.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch48

[13] Subhash Khot, Guy Kindler, Elchanan Mossel și Ryan O'Donnell. Rezultate optime de inaproximabilitate pentru max-cut și alte csps cu 2 variabile? SIAM Journal on Computing, 37(1):319–357, 2007. https://​/​doi.org/​10.1137/​S0097539705447372.
https: / / doi.org/ 10.1137 / S0097539705447372

[14] Eunou Lee. Optimizarea parametrilor circuitului cuantic prin sdp. În cel de-al 33-lea Simpozion Internațional de Algoritmi și Calcul (ISAAC 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. https:/​/​doi.org/​10.4230/​LIPIcs.ISAAC.2022.48.
https://​/​doi.org/​10.4230/​LIPIcs.ISAAC.2022.48

[15] Stephen Piddock și Ashley Montanaro. Complexitatea interacțiunilor antiferomagnetice și a rețelelor 2d. Quantum Information & Computation, 17(7-8):636–672, 2017. https:/​/​dl.acm.org/​doi/​abs/​10.5555/​3179553.3179559.
https: / / dl.acm.org/ doi / ABS / 10.5555 / 3179553.3179559

[16] Ojas Parekh și Kevin Thompson. Aplicarea ierarhiei cuantice lasserre de nivel 2 în algoritmi de aproximare cuantică. În cel de-al 48-lea Colocviu internațional despre automate, limbaje și programare (ICALP 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2021.102.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.102

[17] Ojas Parekh și Kevin Thompson. Depășirea atribuirii aleatoare pentru aproximarea problemelor hamiltoniene cuantice 2-locale. În cel de-al 29-lea Simpozion european anual privind algoritmi (ESA 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. https:/​/​doi.org/​10.4230/​LIPIcs.ESA.2021.74.
https://​/​doi.org/​10.4230/​LIPIcs.ESA.2021.74

[18] Ojas Parekh și Kevin Thompson. O aproximare optimă a stării produsului pentru hamiltonienii cuantici 2-locali cu termeni pozitivi. arXiv preprint arXiv:2206.08342, 2022. https://​/​doi.org/​10.48550/​arXiv.2206.08342.
https://​/​doi.org/​10.48550/​arXiv.2206.08342
arXiv: 2206.08342

Citat de

[1] Nicolas PD Sawaya, Daniel Marti-Dafcik, Yang Ho, Daniel P Tabor, David Bernal, Alicia B Magann, Shavindra Premaratne, Pradeep Dubey, Anne Matsuura, Nathan Bishop, Wibe A de Jong, Simon Benjamin, Ojas D Parekh, Norm Tubman, Katherine Klymko și Daan Camps, „HamLib: A library of Hamiltonians for benchmarking cuantic algoritms and hardware”, arXiv: 2306.13126, (2023).

[2] Dmitry Grinko și Maris Ozols, „Programare liniară cu constrângeri unitare-echivariante”, arXiv: 2207.05713, (2022).

[3] Charlie Carlson, Zackary Jorquera, Alexandra Kolla, Steven Kordonowy și Stuart Wayland, „Algoritmi de aproximare pentru Quantum Max-$d$-Cut”, arXiv: 2309.10957, (2023).

[4] Adam Bene Watts, Anirban Chowdhury, Aidan Epperly, J. William Helton și Igor Klep, „Relaxations and Exact Solutions to Quantum Max Cut via the Algebric Structure of Swap Operators”, arXiv: 2307.15661, (2023).

[5] Andrew Zhao și Nicholas C. Rubin, „Extinderea amplitudinii optimizării cuantice cu înglobări fermionice”, arXiv: 2301.01778, (2023).

[6] Steven Heilman, „Sphere Valued Noise Stability and Quantum MAX-CUT Hardness”, arXiv: 2306.03912, (2023).

Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2023-11-09 11:49:09). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.

Nu a putut să aducă Date citate încrucișate în ultima încercare 2023-11-09 11:49:08: Nu s-au putut prelua date citate pentru 10.22331 / q-2023-11-09-1180 de la Crossref. Acest lucru este normal dacă DOI a fost înregistrat recent.

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.

Timestamp-ul:

Mai mult de la Jurnalul cuantic