Batas Konsentrasi Untuk Keadaan Kuantum Dan Batasan Pada QAOA Dari Perkiraan Polinomial

Diterbitkan Ulang Oleh Plato

Followers: 0

Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Anurag Anshu¹ dan Tony Metger²

¹Sekolah Teknik dan Ilmu Terapan, Universitas Harvard
²Institut Fisika Teoretis, ETH Zurich

Apakah makalah ini menarik atau ingin dibahas? Scite atau tinggalkan komentar di SciRate.

Abstrak

Kami membuktikan batas konsentrasi untuk kelas status kuantum berikut: (i) status keluaran sirkuit kuantum dangkal, menjawab pertanyaan terbuka dari [16]; (ii) status produk matriks injektif; (iii) keadaan keluaran evolusi Hamiltonian padat, yaitu keadaan dalam bentuk $e^{iota H^{(p)}} cdots e^{iota H^{(1)}} |psi_0rangle$ untuk $n$- status produk qubit $|psi_0rangle$, di mana masing-masing $H^{(i)}$ dapat berupa komuter lokal Hamiltonian yang memenuhi batasan norma, termasuk Hamiltonian padat dengan interaksi antara qubit apa pun. Bukti kami menggunakan pendekatan polinomial untuk menunjukkan bahwa negara bagian ini dekat dengan operator lokal. Ini menyiratkan bahwa distribusi bobot Hamming dari pengukuran dasar komputasi (dan yang dapat diamati terkait lainnya) terkonsentrasi.
Contoh dari (iii) adalah keadaan yang dihasilkan oleh algoritma optimisasi perkiraan kuantum (QAOA). Dengan menggunakan hasil konsentrasi kami untuk keadaan ini, kami menunjukkan bahwa untuk model putaran acak, QAOA hanya dapat berhasil dengan probabilitas yang dapat diabaikan bahkan pada tingkat super-konstan $p = o(log log n)$, dengan asumsi versi yang diperkuat dari keadaan- disebut tumpang tindih kesenjangan properti. Ini memberikan batasan pertama pada QAOA pada contoh padat pada tingkat super-konstan, meningkatkan hasil terbaru [BGMZ22].

[Embedded content]

► data BibTeX

@artikel{Anshu2023concentrationbounds, doi = {10.22331/q-2023-05-11-999}, url = {https://doi.org/10.22331/q-2023-05-11-999}, title = {Concentration bounds untuk keadaan kuantum dan batasan pada {QAOA} dari perkiraan polinomial}, penulis = {Anshu, Anurag dan Metger, Tony}, jurnal = {{Quantum}}, issn = {2521-327X}, penerbit = {{Verein zur F {“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, halaman = {999}, bulan = Mei, tahun = {2023} }

► Referensi

[1] Anurag Anshu, Itai Arad, and David Gosset. Hukum area untuk sistem putaran bebas frustrasi 2d. Dalam Prosiding Simposium ACM SIGACT Tahunan ke-54 tentang Teori Komputasi, STOC 2022, halaman 12–18, New York, NY, AS, 2022. Asosiasi Mesin Komputasi. doi:10.1145/3519935.3519962.
https: / / doi.org/ 10.1145 / 3519935.3519962

[2] Anurag Anshu dan Nikolas P. Breuckmann. Konstruksi NLTS kombinatorial. Jurnal Fisika Matematika, 63(12), 12 2022. doi:10.1063/5.0113731.
https: / / doi.org/ 10.1063 / 5.0113731

[3] Anurag Anshu, Nikolas Breuckmann, dan Chinmay Nirkhe. NLTS hamiltonian dari kode kuantum yang bagus. pracetak arXiv arXiv:2206.13228, 2022. URL: https:///arxiv.org/abs/2206.13228.
arXiv: 2206.13228

[4] Nilin Abrahamsen. Bukti singkat dari chernoff spektral yang terikat untuk hamiltonian lokal. pracetak arXiv arXiv:2009.04993, 2020. URL: https:///arxiv.org/abs/2009.04993.
arXiv: 2009.04993

[5] Alvaro M Alhambra. Sistem banyak benda kuantum dalam kesetimbangan termal. pracetak arXiv arXiv:2204.08349, 2022. URL: https:///arxiv.org/abs/2204.08349.
arXiv: 2204.08349

[6] Anurag Anshu dan Chinmay Nirkhe. Batas Bawah Sirkuit untuk Keadaan Energi Rendah Hamiltonian Kode Kuantum. Dalam Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), halaman 6:1–6:22, Dagstuhl, Jerman, 2022. Schloss Dagstuhl – Leibniz- Zentrum untuk Informatik. doi:10.4230/LIPIcs.ITCS.2022.6.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2022.6

[7] Anurag Anshu. Batas konsentrasi untuk keadaan kuantum dengan panjang korelasi terbatas pada sistem kisi spin kuantum. New Journal of Physics, 18(8):083011, agustus 2016. doi:10.1088/1367-2630/18/8/083011.
https://doi.org/10.1088/1367-2630/18/8/083011

[8] Fernando GSL Brandao dan Marcus Cramer. Kesetaraan ansambel mekanik statistik untuk sistem kuantum non-kritis. pracetak arXiv arXiv:1502.03263, 2015. URL: https:///arxiv.org/abs/1502.03263.
arXiv: 1502.03263

[9] H. Buhrman, R. Cleve, R. De Wolf, and C. Zalka. Batasan untuk algoritme kuantum kesalahan kecil dan kesalahan nol. Dalam Proceedings of the 40th Annual Symposium on Foundations of Computer Science, halaman 358–368, 1999. doi:10.1109/SFCCS.1999.814607.
https: / / doi.org/ 10.1109 / SFFCS.1999.814607

[10] FGSL Brandao, Marcus Cramer, dan Madalin Guta. Teorema berry-esseen untuk sistem kisi kuantum dan kesetaraan ansambel mekanis statistik. QIP2015 Talk, 2015. URL: http:///www.quantum-lab.org/qip2015/talks/125-Brandao.pdf.
http:///www.quantum-lab.org/qip2015/talks/125-Brandao.pdf

[11] Joao Basso, David Gamarnik, Song Mei, and Leo Zhou. Performa dan batasan qaoa pada level konstan pada hypergraph besar dan model spin glass. Pada 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2022. doi:10.1109/FOCS54457.2022.00039.
https:///doi.org/10.1109/FOCS54457.2022.00039

[12] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Hambatan untuk optimasi kuantum variasional dari perlindungan simetri. Fisika. Pdt. Lett., 125:260505, Des. doi:10.1103/PhysRevLett.125.260505.
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[13] Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman. Suboptimalitas algoritme lokal untuk kelas masalah pemotongan maksimal. The Annals of Probability, 47(3):1587 – 1618, 2019. doi:10.1214/18-AOP1291.
https:///doi.org/10.1214/18-AOP1291

[14] Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi. Keterbatasan Algoritma Kuantum Lokal pada MAX-k-XOR Acak dan Selanjutnya. Dalam Kolokium Internasional ke-49 tentang Automata, Bahasa, dan Pemrograman (ICALP 2022), volume 229 dari Leibniz International Proceedings in Informatics (LIPIcs), halaman 41:1–41:20, Dagstuhl, Jerman, 2022. Schloss Dagstuhl – Leibniz-Zentrum fur Informatik. doi:10.4230/LIPIcs.ICALP.2022.41.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2022.41

[15] J Ignacio Cirac, David Perez-Garcia, Norbert Schuch, and Frank Verstraete. Status produk matriks dan status pasangan terjerat yang diproyeksikan: Konsep, simetri, teorema. Ulasan Fisika Modern, 93(4):045003, 2021. doi:10.1103/RevModPhys.93.045003.
https: / / doi.org/ 10.1103 / RevModPhys.93.045003

[16] Giacomo De Palma, Milad Marvian, Cambyse Rouzé, and Daniel Stilck Franca. Keterbatasan algoritma kuantum variasional: Pendekatan transpor optimal kuantum. PRX Quantum, 4:010309, Jan 2023. doi:10.1103/PRXQuantum.4.010309.
https: / / doi.org/ 10.1103 / PRXQuantum.4.010309

[17] Giacomo De Palma dan Cambyse Rouze. Ketidaksetaraan konsentrasi kuantum. Annales Henri Poincaré, Apr 2022. doi:10.1007/s00023-022-01181-1.
https://doi.org/10.1007/s00023-022-01181-1

[18] L. Eldar dan AW Harrow. hamiltonian lokal yang keadaan dasarnya sulit diperkirakan. Pada 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), halaman 427–438, 2017. doi:10.1109/FOCS.2017.46.
https: / / doi.org/ 10.1109 / FOCS.2017.46

[19] Edward Farhi, Jeffrey Goldstone, dan Sam Gutmann. Algoritma pengoptimalan perkiraan kuantum. pracetak arXiv arXiv:1411.4028, 2014. URL: https:///arxiv.org/abs/1411.4028.
arXiv: 1411.4028

[20] Edward Farhi, David Gamarnik, dan Sam Gutmann. Algoritme pengoptimalan perkiraan kuantum perlu melihat keseluruhan grafik: Kasus tipikal. pracetak arXiv arXiv:2004.09002, 2020. URL: https:///arxiv.org/abs/2004.09002.
arXiv: 2004.09002

[21] David Gamarnik. Properti overlap gap: Penghalang topologi untuk mengoptimalkan struktur acak. Prosiding National Academy of Sciences, 118(41):e2108492118, 2021. doi:10.1073/pnas.2108492118.
https: / / doi.org/ 10.1073 / pnas.2108492118

[22] Ronald L Graham, Martin Grötschel, dan László Lovász. Buku Pegangan Kombinatorik, volume 1. Elsevier, 1995.

[23] David Gamarnik dan Aukosh Jagannath. Properti overlap gap dan perkiraan algoritma pengiriman pesan untuk model $p$-spin. The Annals of Probability, 49(1):180–205, 2021. URL: https:///hdl.handle.net/1721.1/145311.
https: / / hdl.handle.net/ 1721.1/145311

[24] David Gamarnik, Aukosh Jagannath, dan Alexander S Wein. Kekerasan tingkat rendah dari masalah optimasi acak. Pada Simposium Tahunan ke-2020 IEEE 61 tentang Yayasan Ilmu Komputer (FOCS), halaman 131–140. IEEE, 2020. doi:10.1109/FOCS46700.2020.00021.
https:///doi.org/10.1109/FOCS46700.2020.00021

[25] David Gamarnik dan Quan Li. Menemukan submatriks besar dari matriks acak gaussian. The Annals of Statistics, 46(6A):2511–2561, 2018. URL: http:///hdl.handle.net/1721.1/120593.
http: / / hdl.handle.net/ 1721.1/120593

[26] Francesco Guerra dan Fabio Lucio Toninelli. Batas termodinamika dalam model kaca spin bidang rata-rata. Komunikasi dalam Fisika Matematika, 230(1):71–79, 2002. doi:10.1007/s00220-002-0699-y.
https: / / doi.org/ 10.1007 / s00220-002-0699-y

[27] D. Goderis dan P.Vets. Teorema limit sentral untuk mencampur sistem kuantum dan aljabar fluktuasi CCR. Komunikasi dalam Fisika Matematika, 122:249–265, 1989. doi:10.1007/BF01257415.
https: / / doi.org/ 10.1007 / BF01257415

[28] MB Hastings. Lieb-schultz-mattis dalam dimensi yang lebih tinggi. Fisika. Rev.B, 69:104431, Mar 2004. doi:10.1103/PhysRevB.69.104431.
https:///doi.org/10.1103/PhysRevB.69.104431

[29] Michael Hartmann, Günter Mahler, dan Ortwin Hess. Keberadaan Temperatur pada Skala Nano. Fisika. Rev Lett., 93:080402, Agustus 2004. doi:10.1103/PhysRevLett.93.080402.
https: / / doi.org/ 10.1103 / PhysRevLett.93.080402

[30] Tomotaka Kuwahara, Itai Arad, Luigi Amico, and Vlatko Vedral. Reversibilitas lokal dan struktur keterikatan dari keadaan dasar banyak benda. Sains dan Teknologi Kuantum, 2(1):015005, 2017. doi:10.1088/2058-9565/aa523d.
https: / / doi.org/ 10.1088 / 2058-9565 / aa523d

[31] Jeff Kahn, Nathan Linial, and Alex Samorodnitsky. Inklusi-eksklusi: Tepat dan perkiraan. Combinatorica, 16(4):465–477, Des 1996. doi:10.1007/BF01271266.
https: / / doi.org/ 10.1007 / BF01271266

[32] Tomotaka Kuwahara dan Keiji Saito. Termalisasi eigenstate dari properti pengelompokan korelasi. Fisika. Lett., 124:200604, Mei 2020. doi:10.1103/PhysRevLett.124.200604.
https: / / doi.org/ 10.1103 / PhysRevLett.124.200604

[33] Tomotaka Kuwahara dan Keiji Saito. Ikatan konsentrasi Gaussian dan kesetaraan ansambel dalam sistem banyak benda kuantum generik termasuk interaksi jarak jauh. Sejarah Fisika, 421:168278, 2020. doi:10.1016/j.aop.2020.168278.
https:///doi.org/10.1016/j.aop.2020.168278

[34] Tomotaka Kuwahara. Menghubungkan distribusi probabilitas dari berbagai operator dan generalisasi ketidaksetaraan chernoff-hoeffding. Journal of Statistical Mechanics: Theory and Experiment, 2016(11):113103, nov 2016. doi:10.1088/1742-5468/2016/11/113103.
https://doi.org/10.1088/1742-5468/2016/11/113103

[35] Elliott Lieb, Theodore Schultz, dan Daniel Mattis. Dua model larut rantai antiferomagnetik. Annals of Physics, 16(3):407–466, 1961. doi:10.1016/0003-4916(61)90115-4.
https://doi.org/10.1016/0003-4916(61)90115-4

[36] Anthony Leverrier dan Gilles Zemor. Kode penyamak kuantum. Pada 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2022. doi:10.1109/FOCS54457.2022.00117.
https:///doi.org/10.1109/FOCS54457.2022.00117

[37] D. Perez-Garcia, F. Verstraete, MM Wolf, dan JI Cirac. Representasi status produk matriks. Informasi Kuantum. Comput., 7(5):401–430, Juli 2007. URL: https:///dl.acm.org/doi/10.5555/2011832.2011833.
https: / / dl.acm.org/ doi / 10.5555 / 2011832.2011833

[38] Pavel Panteleev dan Gleb Kalachev. Kode ldpc klasik kuantum yang asimtotik dan dapat diuji secara lokal. Dalam Prosiding Simposium ACM SIGACT Tahunan ke-54 tentang Teori Komputasi, halaman 375–388, 2022. doi:10.1145/3519935.3520017.
https: / / doi.org/ 10.1145 / 3519935.3520017

[39] Sushant Sachdeva dan Nisheeth K. Vishnoi. Algoritme lebih cepat melalui teori pendekatan. Foundations and Trends® in Theoretical Computer Science, 9(2):125–210, 2014. doi:10.1561/0400000065.
https: / / doi.org/ 10.1561 / 0400000065

[40] Hal Tasaki. Tentang kesetaraan lokal antara ansambel kanonik dan mikrokanonik untuk sistem putaran kuantum. Journal of Statistical Physics, 172(4):905–926, Agustus 2018. doi:10.1007/s10955-018-2077-y.
https: / / doi.org/ 10.1007 / s10955-018-2077-y

Dikutip oleh

[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzé, dan Daniel Stilck França, “Keterbatasan Algoritma Kuantum Variasi: Pendekatan Transportasi Kuantum Optimal”, PRX Kuantum 4 1, 010309 (2023).

[2] Ojas Parekh, “Sinergi Antara Riset Operasi dan Ilmu Informasi Kuantum”, arXiv: 2301.05554, (2023).

[3] Dominik S. Wild dan Álvaro M. Alhambra, “Simulasi klasik dinamika kuantum waktu singkat”, arXiv: 2210.11490, (2022).

[4] Lennart Bittel, Sevag Gharibian, dan Martin Kliesch, "Mengoptimalkan kedalaman algoritme kuantum variasional sangat sulit untuk diperkirakan oleh QCMA", arXiv: 2211.12519, (2022).

Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2023-05-11 10:33:33). Daftar ini mungkin tidak lengkap karena tidak semua penerbit menyediakan data kutipan yang cocok dan lengkap.

Tidak dapat mengambil Crossref dikutip oleh data selama upaya terakhir 2023-05-11 10:33:31: Tidak dapat mengambil data yang dikutip oleh untuk 10.22331 / q-2023-05-11-999 dari Crossref. Ini normal jika DOI terdaftar baru-baru ini.

Makalah ini diterbitkan dalam Quantum di bawah Creative Commons Attribution 4.0 Internasional (CC BY 4.0) lisensi. Hak cipta tetap berada pada pemegang hak cipta asli seperti penulis atau lembaganya.

Konten Bertenaga SEO & Distribusi PR. Dapatkan Amplifikasi Hari Ini.
PlatoAiStream. Kecerdasan Data Web3. Pengetahuan Diperkuat. Akses Di Sini.
Mencetak Masa Depan bersama Adryenn Ashley. Akses Di Sini.
Beli dan Jual Saham di Perusahaan PRE-IPO dengan PREIPO®. Akses Di Sini.
Sumber: https://quantum-journal.org/papers/q-2023-05-11-999/

Stempel Waktu: 11 Mei 2023

Diterbitkan Ulang Oleh Plato

Abstrak

► data BibTeX

► Referensi

Dikutip oleh

Transformasi dalam jaringan kuantum melalui operasi lokal dibantu oleh banyak putaran komunikasi klasik

Model Tautan Topologi dari Keterikatan Multipartit

Enkripsi independen perangkat yang aman secara komposisi dengan penghapusan bersertifikat

LIMDD: Diagram Keputusan untuk Simulasi Komputasi Kuantum Termasuk Status Penstabil

Algoritme kuantum umum untuk simulasi Hamiltonian dengan aplikasi pada teori pengukur kisi non-Abelian

Peran teori koherensi dalam jaringan saraf kuantum penarik

Pengukuran sindrom adaptif untuk koreksi kesalahan gaya pendek

Sepasang Kode Permukaan Pengukuran pada Pentagon

Algoritma yang efisien untuk kemacetan informasi kuantum

Ketidaksetaraan konsentrasi matriks dan efisiensi set universal acak gerbang kuantum

Peta pelestarian pesanan pada pengukuran kuantum

Tentang Kami

Pencarian Vertikal & Ai

Platform

Tetap Berhubung

Akun