Ulepszony algorytm aproksymacji dla kwantowego maksymalnego cięcia na wykresach bez trójkątów

Ulepszony algorytm aproksymacji dla kwantowego maksymalnego cięcia na wykresach bez trójkątów

Znacznik czasu: 9 listopada 2023 6:44

Robbi King

Wydział Informatyki i Nauk Matematycznych, Caltech

Czy ten artykuł jest interesujący czy chcesz dyskutować? Napisz lub zostaw komentarz do SciRate.

Abstrakcyjny

Podajemy algorytm aproksymacji dla Quantum Max-Cut, który działa poprzez zaokrąglanie relaksacji SDP do splątanego stanu kwantowego. SDP służy do wyboru parametrów wariacyjnego obwodu kwantowego. Stan splątany jest następnie reprezentowany jako obwód kwantowy zastosowany do stanu produktu. Osiąga współczynnik aproksymacji 0.582 na wykresach pozbawionych trójkątów. Poprzednie najlepsze algorytmy Anshu, Gosseta, Morenza i Parekha, Thompsona osiągnęły współczynniki aproksymacji odpowiednio 0.531 i 0.533. Ponadto badamy hamiltonian EPR, który naszym zdaniem jest naturalnym problemem pośrednim, który izoluje niektóre kluczowe cechy kwantowe lokalnych problemów hamiltonowskich. Dla hamiltonianu EPR podajemy algorytm aproksymacji ze współczynnikiem aproksymacji $1 / sqrt{2}$ na wszystkich wykresach.

Ulepszony algorytm aproksymacji dla Quantum Max-Cut na wykresach bez trójkątów Inteligencja danych PlatoBlockchain. Wyszukiwanie pionowe. AI.

Wyróżniony obraz: Lokalne sąsiedztwo krawędzi na wykresie bez trójkątów.

[Osadzone treści]

Popularne podsumowanie

Jak możemy zaokrąglić relaksację SDP do splątanego stanu kwantowego? A jak powinniśmy zoptymalizować ansatz obwodu wariacyjnego? W tej pracy rozwiązujemy te dwa problemy, łącząc je: Użyj rozwiązania SDP, aby wybrać parametry obwodu wariacyjnego.

► Dane BibTeX

► Referencje

[1] Anurag Anshu, David Gosset i Karen Morenz. Poza przybliżeniami stanu produktu dla kwantowego analogu maksymalnego cięcia. W 15. Konferencji na temat teorii obliczeń kwantowych, komunikacji i kryptografii, 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. Ulepszone algorytmy aproksymacji dla hamiltonianów lokalnych o ograniczonym stopniu. 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. Nierówności Grothendiecka dla programów półokreślonych z ograniczeniem rangowym. 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. Algorytmy aproksymacyjne dla kwantowych problemów wielu ciał. 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. Przybliżenia stanu produktu do stanów kwantowych. 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’ego Cubitta i Ashley Montanaro. Klasyfikacja złożoności lokalnych problemów Hamiltona. SIAM Journal on Computing, 45(2):268–316, 2016. https://​/​doi.org/​10.1137/​140998287.
https: / / doi.org/ 10.1137 / 140998287

[7] Uriela Feige i Gideona Schechtmana. O optymalności techniki losowego zaokrąglania hiperpłaszczyznowego dla maksymalnego cięcia. Random Structures & Algorithms, 20(3):403–440, 2002. https://​/​doi.org/​10.1002/​rsa.10036.
https: // doi.org/ 10.1002 / rsa.10036

[8] Sevaga Gharibiana i Julii Kempe. Algorytmy aproksymacyjne dla problemów qma-zupełnych. 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. Prawie optymalne klasyczne algorytmy aproksymacyjne dla kwantowego uogólnienia maksymalnego cięcia. W przybliżeniu, randomizacji i optymalizacji kombinatorycznej. Algorytmy i techniki (APPROX/​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] Michela Goemansa i Davida Williamsona. Ulepszone algorytmy aproksymacji dla problemów maksymalnego cięcia i spełnialności przy użyciu programowania półokreślonego. 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] Johana Håstada. Niektóre optymalne wyniki nieprzybliżenia. 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. Unikalna twardość gier kwantowego maksymalnego cięcia i przypuszczalna nierówność Borella o wartościach wektorowych. W materiałach z dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych (SODA) w 2023 r., strony 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. Optymalne wyniki niedokładności dla maksymalnego cięcia i innych 2-zmiennych csps? SIAM Journal on Computing, 37(1):319–357, 2007. https://​/​doi.org/​10.1137/​S0097539705447372.
https: / / doi.org/ 10.1137 / S0097539705447372

[14] Eunou Lee. Optymalizacja parametrów obwodu kwantowego poprzez sdp. Podczas 33. Międzynarodowego Sympozjum Algorytmów i Obliczeń (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] Stephena Piddocka i Ashley Montanaro. Złożoność oddziaływań antyferromagnetycznych i sieci 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. Zastosowanie hierarchii lassera kwantowego drugiego poziomu w algorytmach aproksymacji kwantowej. Podczas 2. Międzynarodowego Kolokwium na temat automatów, języków i programowania (ICALP 48). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. https://​/​doi.org/​2021/​LIPIcs.ICALP.10.4230.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.102

[17] Ojas Parekh i Kevin Thompson. Przypisanie losowe Beaty do aproksymacji kwantowych 2-lokalnych problemów Hamiltona. Podczas 29. dorocznego europejskiego sympozjum na temat algorytmów (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. Optymalne przybliżenie stanu produktu dla 2-lokalnych hamiltonianów kwantowych z wyrazami dodatnimi. Przedruk arXiv arXiv:2206.08342, 2022. https://​/​doi.org/​10.48550/​arXiv.2206.08342.
https://​/​doi.org/​10.48550/​arXiv.2206.08342
arXiv: 2206.08342

Cytowany przez

[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: biblioteka hamiltonianów do porównywania algorytmów kwantowych i sprzętu”, arXiv: 2306.13126, (2023).

[2] Dmitry Grinko i Maris Ozols, „Programowanie liniowe z ograniczeniami unitary-equivariant”, arXiv: 2207.05713, (2022).

[3] Charlie Carlson, Zackary Jorquera, Alexandra Kolla, Steven Kordonowy i Stuart Wayland, „Algorithms aproximation for 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 algebraic Structure of Swap Operators”, arXiv: 2307.15661, (2023).

[5] Andrew Zhao i Nicholas C. Rubin, „Rozszerzanie zasięgu optymalizacji kwantowej za pomocą osadzania fermionowego”, arXiv: 2301.01778, (2023).

[6] Steven Heilman, „Stabilność hałasu o wartości kulistej i twardość Quantum MAX-CUT”, arXiv: 2306.03912, (2023).

Powyższe cytaty pochodzą z Reklamy SAO / NASA (ostatnia aktualizacja pomyślnie 2023-11-09 11:49:09). Lista może być niekompletna, ponieważ nie wszyscy wydawcy podają odpowiednie i pełne dane cytowania.

Nie można pobrać Przywołane przez Crossref dane podczas ostatniej próby 2023-11-09 11:49:08: Nie można pobrać cytowanych danych dla 10.22331 / q-2023-11-09-1180 z Crossref. Jest to normalne, jeśli DOI zostało niedawno zarejestrowane.

Niniejszy artykuł opublikowano w Quantum pod Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0) licencja. Prawa autorskie należą do pierwotnych właścicieli praw autorskich, takich jak autorzy lub ich instytucje.

Znak czasu:

Więcej z Dziennik kwantowy