Üçgensiz Grafiklerde Kuantum Maksimum Kesim için Geliştirilmiş Bir Yaklaşım Algoritması

Üçgensiz Grafiklerde Kuantum Maksimum Kesim için Geliştirilmiş Bir Yaklaşım Algoritması

Zaman Damgası: 9 Kasım 2023 6:44

Robbie Kral

Bilgisayar ve Matematik Bilimleri Bölümü, Caltech

Bu makaleyi ilginç mi buldunuz yoksa tartışmak mı istiyorsunuz? SciRate'e çığlık at veya yorum bırak.

Özet

Quantum Max-Cut için SDP gevşemesini dolaşık kuantum durumuna yuvarlayarak çalışan bir yaklaşım algoritması veriyoruz. SDP, değişken bir kuantum devresinin parametrelerini seçmek için kullanılır. Dolaşmış durum daha sonra bir ürün durumuna uygulanan kuantum devresi olarak temsil edilir. Üçgensiz grafiklerde 0.582'lik bir yaklaşım oranına ulaşır. Anshu, Gosset, Morenz ve Parekh'in önceki en iyi algoritmaları olan Thompson, sırasıyla 0.531 ve 0.533'lük yaklaşım oranlarına ulaştı. Ek olarak, yerel Hamilton problemlerinin bazı önemli kuantum özelliklerini izole eden doğal bir ara problem olduğunu savunduğumuz EPR Hamiltoniyen'i de inceliyoruz. EPR Hamiltonyeni için, tüm grafiklerde $1 / sqrt{2}$ yaklaşım oranına sahip bir yaklaşım algoritması veriyoruz.

Üçgensiz Grafiklerde Kuantum Maksimum Kesim için Geliştirilmiş Bir Yaklaşım Algoritması PlatoBlockchain Veri Zekası. Dikey Arama. Ai.

Öne çıkan görsel: Üçgensiz grafikte kenarın yerel komşuluğu.

[Gömülü içerik]

Popüler özet

Bir SDP gevşemesini dolaşık kuantum durumuna nasıl yuvarlayabiliriz? Peki değişken devre ansatz'ını nasıl optimize etmeliyiz? Bu çalışmada bu iki problemi birleştirerek çözeceğiz: Varyasyonel devrenin parametrelerini seçmek için SDP çözümünü kullanın.

► BibTeX verileri

► Referanslar

[1] Anurag Anshu, David Gosset ve Karen Morenz. Maksimum kesimin kuantum analoğu için ürün durumu yaklaşımlarının ötesinde. 15. Kuantum Hesaplama, İletişim ve Kriptografi Teorisi Konferansında, 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 ve Mehdi Soleimanifar. Sınırlı dereceli yerel Hamiltonlular için geliştirilmiş yaklaşım algoritmaları. Fiziksel İnceleme Mektupları, 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 ve Frank Vallentin. Sıra kısıtlaması olan yarı kesin programlar için Grothendieck eşitsizlikleri. Hesaplama Teorisi, 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 ve Kristan Temme. Kuantum çoklu cisim problemleri için yaklaşım algoritmaları. Matematiksel Fizik Dergisi, 60(3):032203, 2019. https://​/​doi.org/​10.1063/​1.5085428.
https: / / doi.org/ 10.1063 / 1.5085428

[5] Fernando GSL Brandao ve Aram W Harrow. Kuantum durumlarına çarpım durumu yaklaşımları. Matematiksel Fizikte İletişim, 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 ve Ashley Montanaro. Yerel Hamilton problemlerinin karmaşıklık sınıflandırması. SIAM Journal on Computing, 45(2):268–316, 2016. https://​/​doi.org/​10.1137/​140998287.
https: / / doi.org/ 10.1137 / 140998287

[7] Uriel Feige ve Gideon Schechtman. Maksimum kesim için rastgele hiperdüzlem yuvarlama tekniğinin optimalliği üzerine. Rastgele Yapılar ve Algoritmalar, 20(3):403–440, 2002. https://​/​doi.org/​10.1002/​rsa.10036.
https: / / doi.org/ 10.1002 / rsa.10036

[8] Sevag Gharibian ve Julia Kempe. Qma-tam problemler için yaklaşım algoritmaları. SIAM Bilgisayar Dergisi, 41(4):1028–1050, 2012. https://​/​doi.org/​10.1137/​110842272.
https: / / doi.org/ 10.1137 / 110842272

[9] Sevag Gharibian ve Ojas Parekh. Maksimum kesimin kuantum genellemesi için neredeyse optimal klasik yaklaşım algoritmaları. Yaklaşım, Rastgeleleştirme ve Kombinatoryal Optimizasyonda. Algoritmalar ve Teknikler (YAKLAŞIK/​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 ve David Williamson. Yarı kesin programlama kullanılarak maksimum kesme ve karşılanabilirlik sorunları için geliştirilmiş yaklaşım algoritmaları. ACM Dergisi (JACM), 42(6):1115–1145, 1995. https://​/​doi.org/​10.1145/​227683.227684.
https: / / doi.org/ 10.1145 / 227683.227684

[11] Johan Håstad. Bazı optimal yaklaşılamazlık sonuçları. ACM Dergisi (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 ve John Wright. Kuantum maksimum kesmenin benzersiz oyun sertliği ve varsayılan vektör değerli borell eşitsizliği. Ayrık Algoritmalar (SODA) üzerine 2023 Yıllık ACM-SIAM Sempozyumu Bildirileri, sayfa 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 ve Ryan O'Donnell. Maksimum kesim ve diğer 2 değişkenli csps için optimum yaklaşılamazlık sonuçları? SIAM Journal on Computing, 37(1):319–357, 2007. https://​/​doi.org/​10.1137/​S0097539705447372.
https: / / doi.org/ 10.1137 / S0097539705447372

[14] Eunou Lee. Kuantum devre parametrelerini sdp aracılığıyla optimize etme. 33. Uluslararası Algoritmalar ve Hesaplama Sempozyumunda (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 ve Ashley Montanaro. Antiferromanyetik etkileşimlerin ve 2 boyutlu kafeslerin karmaşıklığı. Kuantum Bilgisi ve Hesaplama, 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 ve Kevin Thompson. Seviye-2 kuantum lasserre hiyerarşisinin kuantum yaklaşım algoritmalarında uygulanması. 48. Uluslararası Otomata, Diller ve Programlama Toplantısı'nda (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 ve Kevin Thompson. Kuantum 2-yerel Hamilton problemlerine yaklaşmak için rastgele atamayı yenmek. 29. Yıllık Avrupa Algoritmalar Sempozyumunda (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 ve Kevin Thompson. Pozitif terimlerle 2 yerel kuantum hamiltoniyen için optimal ürün durumu yaklaşımı. arXiv ön baskı arXiv:2206.08342, 2022. https://​/​doi.org/​10.48550/​arXiv.2206.08342.
https:/​/​doi.org/10.48550/​arXiv.2206.08342
arXiv: 2206.08342

Alıntılama

[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 ve Daan Camps, "HamLib: Kuantum algoritmalarını ve donanımını kıyaslamak için Hamiltonyalılardan oluşan bir kütüphane", arXiv: 2306.13126, (2023).

[2] Dmitry Grinko ve Maris Ozols, “Üniter-eşdeğer kısıtlamalı doğrusal programlama”, arXiv: 2207.05713, (2022).

[3] Charlie Carlson, Zackary Jorquera, Alexandra Kolla, Steven Kordonowy ve Stuart Wayland, “Quantum Max-$d$-Cut için Approximation Algorithms”, arXiv: 2309.10957, (2023).

[4] Adam Bene Watts, Anirban Chowdhury, Aidan Epperly, J. William Helton ve Igor Klep, "Swap Operatörlerinin Cebirsel Yapısı aracılığıyla Quantum Max Cut'a Gevşemeler ve Kesin Çözümler", arXiv: 2307.15661, (2023).

[5] Andrew Zhao ve Nicholas C. Rubin, "Fermiyonik yerleştirmelerle kuantum optimizasyonunun kapsamını genişletmek", arXiv: 2301.01778, (2023).

[6] Steven Heilman, “Küre Değerli Gürültü Kararlılığı ve Kuantum MAX-CUT Sertliği”, arXiv: 2306.03912, (2023).

Yukarıdaki alıntılar SAO / NASA REKLAMLARI (son başarıyla 2023-11-09 11:49:09) güncellendi. Tüm yayıncılar uygun ve eksiksiz alıntı verisi sağlamadığından liste eksik olabilir.

Getirilemedi Alıntılanan veriler son girişim sırasında 2023-11-09 11:49:08: Crossref'ten 10.22331 / q-2023-11-09-1180 için belirtilen veriler getirilemedi. DOI yakın zamanda kaydedildiyse bu normaldir.

Bu Makale, Quantum'da Creative Commons Atıf 4.0 Uluslararası (CC BY 4.0) lisans. Telif hakkı, yazarlar veya kurumları gibi orijinal telif hakkı sahiplerine aittir.

Zaman Damgası:

Den fazla Kuantum Günlüğü