Lab QuOne, Pusat Penelitian dan Inovasi Phanous, Teheran, Iran
Apakah makalah ini menarik atau ingin dibahas? Scite atau tinggalkan komentar di SciRate.
Abstrak
Evolusi Hamiltonian lokal dalam waktu singkat diharapkan tetap lokal dan dengan demikian terbatas. Dalam makalah ini, kami memvalidasi intuisi ini dengan membuktikan beberapa keterbatasan pada evolusi waktu singkat dari Hamiltonian yang bergantung pada waktu lokal. Kami menunjukkan bahwa distribusi keluaran pengukuran dari evolusi waktu pendek (paling banyak logaritmik) dari Hamiltonian lokal adalah $konsentrasi$ dan memenuhi $textit{ketidaksamaan isoperimetri}$. Untuk menampilkan aplikasi eksplisit dari hasil kami, kami mempelajari masalah $M$$small{AX}$$C$$small{UT}$ dan menyimpulkan bahwa kuantum annealing membutuhkan setidaknya run-time yang diskalakan secara logaritmik dalam ukuran masalah untuk kalahkan algoritme klasik di $M$$small{AX}$$C$$small{UT}$. Untuk menetapkan hasil kami, kami juga membuktikan ikatan Lieb-Robinson yang bekerja untuk Hamiltonian bergantung waktu yang mungkin memiliki kepentingan independen.
Ringkasan populer
โบ data BibTeX
โบ Referensi
[1] T. Kadowaki dan H. Nishimori. Anil kuantum dalam model Ising melintang. Tinjauan Fisik E 58, 5355โ5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355
[2] E. Farhi, J. Goldstone, S. Gutmann dan M. Sipser. Komputasi Kuantum oleh Evolusi Adiabatik. arXiv:0001106 [quant-ph] (2000).
https://โ/โdoi.org/โ10.48550/โarXiv.quant-ph/โ0001106
arXiv: 0001106
[3] T. Kato. Pada teorema adiabatik mekanika kuantum. Jurnal Masyarakat Fisik Jepang 5, 435โ439 (1950).
https: / / doi.org/ 10.1143 / JPSJ.5.435
[4] M. Lahir dan V. Fock. Beweis des adiabatensatzes. Zeitschrift fรผr Physik 51, 165โ180 (1928).
https: / / doi.org/ 10.1007 / BF01343193
[5] T. Albash dan DA Lidar. Perhitungan kuantum adiabatik. Ulasan Fisika Modern 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002
[6] I. Hen dan FM Spedalieri. Quantum Annealing untuk Optimalisasi Terbatas. Tinjauan Fisik Diterapkan 5, 034007 (2016).
https: / / doi.org/ 10.1103 / PhysRevApplied.5.034007
[7] S. Puri, CK Andersen, AL Grimsmo, dan A. Blais. Anil kuantum dengan osilator nonlinier yang terhubung semua ke semua. Komunikasi Alam 8, 15785 (2017).
https://โ/โdoi.org/โ10.1038/โncomms15785
[8] W. Lechner, P. Hauke, dan P. Zoller. Arsitektur anil kuantum dengan konektivitas menyeluruh dari interaksi lokal. Kemajuan Sains 1, e1500838 (2015).
https: / / doi.org/ 10.1126 / sciadv.1500838
[9] S. Jiang, KA Britt, AJ McCaskey, TS Humble, dan S. Kais. Quantum Annealing untuk Faktorisasi Prima. Laporan Ilmiah 8, 17667 (2018).
https: / / doi.org/ 10.1038 / s41598-018-36058-z
[10] RY Li, R. Di Felice, R. Rohs, dan DA Lidar. Anil kuantum versus pembelajaran mesin klasik yang diterapkan pada masalah biologi komputasi yang disederhanakan. Informasi kuantum NPJ 4, 1โ10 (2018).
https:/โ/โdoi.org/โ10.1038/โs41534-018-0060-8
[11] L. Stella, GE Santoro, dan E. Tosatti. Optimalisasi dengan anil kuantum: Pelajaran dari kasus sederhana. Tinjauan Fisik B 72, 014303 (2005).
https://โ/โdoi.org/โ10.1103/โPhysRevB.72.014303
[12] O. Titiloye dan A. Crispin. Anil kuantum dari masalah pewarnaan graf. Pengoptimalan Diskrit 8, 376โ384 (2011).
https://โ/โdoi.org/โ10.1016/โj.disopt.2010.12.001
[13] A. Mott, J. Job, J.-R. Vlimant, D. Lidar, dan M. Spiropulu. Memecahkan masalah pengoptimalan Higgs dengan anil kuantum untuk pembelajaran mesin. Alam 550, 375โ379 (2017).
https: / / doi.org/ 10.1038 / nature24047
[14] KL Pudenz, T. Albash, dan D. A Lidar. Koreksi anil kuantum untuk masalah Ising acak. Tinjauan Fisik A 91, 042302 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.042302
[15] A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, dan A. Aspuru-Guzik. Menemukan konformasi berenergi rendah dari model protein kisi dengan anil kuantum. Laporan ilmiah 2, 571 (2012).
https: / / doi.org/ 10.1038 / srep00571
[16] KL Pudenz, T. Albash, dan D. A Lidar. Anil kuantum yang dikoreksi kesalahan dengan ratusan qubit. Komunikasi alam 5, 1โ10 (2014).
https://โ/โdoi.org/โ10.1038/โncomms4243
[17] R. Martoลรกk, GE Santoro, dan E. Tosatti. Anil kuantum dari masalah penjual keliling. Tinjauan Fisik E 70, 057701 (2004).
https: / / doi.org/ 10.1103 / PhysRevE.70.057701
[18] SH Adachi dan MP Henderson. Penerapan anil kuantum untuk pelatihan jaringan saraf dalam. arXiv:1510.06356 [quant-ph] (2015).
https://โ/โdoi.org/โ10.48550/โarXiv.1510.06356
arXiv: 1510.06356
[19] M.W Johnson, dkk. Anil kuantum dengan putaran buatan. Alam 473, 194โ198 (2011).
https: / / doi.org/ 10.1038 / nature10012
[20] S. Boixo, T. Albash, FM Spedalieri, N. Rektor, dan DA Lidar. Tanda tangan eksperimental anil kuantum yang dapat diprogram. Komunikasi alam 4, 1โ8 (2013).
https://โ/โdoi.org/โ10.1038/โncomms3067
[21] Raja AD, dkk. Anil kuantum koheren dalam rantai Ising 2000-qubit yang dapat diprogram. arXiv:2202.05847 [quant-ph] (2022).
https://โ/โdoi.org/โ10.48550/โarXiv.2202.05847
arXiv: 2202.05847
[22] B. Foxen, dkk. Mendemonstrasikan Serangkaian Gerbang Dua-qubit Berkelanjutan untuk Algoritma Kuantum Jangka Dekat. Surat Tinjauan Fisik 125, 120504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.120504
[23] K.Wright, dkk. Membandingkan komputer kuantum 11-qubit. Komunikasi alam 10, 1โ6 (2019).
https:/โ/โdoi.org/โ10.1038/โs41467-019-13534-2
[24] EJ Crosson dan DA Lidar. Prospek untuk peningkatan kuantum dengan anil kuantum diabatik. Ulasan Alam Fisika 3, 466โ489 (2021).
https:/โ/โdoi.org/โ10.1038/โs42254-021-00313-6
[25] E. Farhi, J. Goldstone, dan S. Gutmann. Algoritma Optimasi Perkiraan Kuantum. arXiv:1411.4028 [quant-ph] (2014).
https://โ/โdoi.org/โ10.48550/โarXiv.1411.4028
arXiv: 1411.4028
[26] E. Farhi, D. Gamarnik, dan S. Gutmann. Algoritma Quantum Approximate Optimization Perlu Melihat Seluruh Grafik: Contoh Kasus Terburuk. arXiv:2005.08747 [quant-ph] (2020).
https://โ/โdoi.org/โ10.48550/โarXiv.2005.08747
arXiv: 2005.08747
[27] E. Farhi, D. Gamarnik, dan S. Gutmann. Algoritma Quantum Approximate Optimization Perlu Melihat Seluruh Grafik: Kasus Khas. arXiv: 2004.09002 [quant-ph] (2020).
https://โ/โdoi.org/โ10.48550/โarXiv.2004.09002
arXiv: 2004.09002
[28] S. Bravyi, A. Kliesch, R. Koenig, dan E. Tang. Hambatan untuk Optimasi Quantum Variasi dari Perlindungan Simetri. Surat Tinjauan Fisik 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
[29] S. Bravyi, D. Gosset, dan R. Movassagh. Algoritma klasik untuk nilai mean kuantum. Fisika Alam 17, 337โ341 (2021).
https:/โ/โdoi.org/โ10.1038/โs41567-020-01109-8
[30] S. Bravyi, A. Kliesch, R. Koenig, dan E. Tang. Algoritma klasik kuantum hibrida untuk pewarnaan grafik perkiraan. Kuantum 6, 678 (2022).
https:/โ/โdoi.org/โ10.22331/โq-2022-03-30-678
[31] L. Eldar dan AW Harrow. Hamiltonian Lokal Yang Keadaan Dasarnya Sulit Ditaksir. Pada Simposium Tahunan IEEE ke-2017 tahun 58 tentang Yayasan Ilmu Komputer (FOCS), 427โ438 (2017).
https: / / doi.org/ 10.1109 / FOCS.2017.46
[32] LT Brady, CL Baldwin, A. Bapat, Y. Kharkov, dan AV Gorshkov. Protokol Optimal dalam Masalah Algoritma Quantum Annealing dan Quantum Approximate Optimization. Surat Tinjauan Fisik 126, 070505 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.070505
[33] LT Brady, L. Kocia, P. Bienias, A. Bapat, Y. Kharkov, dan AV Gorshkov. Perilaku Algoritma Quantum Analog. arXiv:2107.01218 [quant-ph] (2021).
https://โ/โdoi.org/โ10.48550/โarXiv.2107.01218
arXiv: 2107.01218
[34] LC Venuti, D. D'Alessandro, dan DA Lidar. Kontrol Optimal untuk Optimasi Quantum Sistem Tertutup dan Terbuka. Tinjauan Fisik Diterapkan 16, 054023 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054023
[35] AM Childs, Y. Su, MC Tran, N. Wiebe, dan S. Zhu. Teori Kesalahan Trotter dengan Penskalaan Komutator. Tinjauan Fisik X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020
[36] B. Nachtergaele, Y. Ogata, dan R. Sims. Propagasi korelasi dalam sistem kisi kuantum. Jurnal Fisika Statistik 124, 1โ13 (2006).
https:/โ/โdoi.org/โ10.1007/โs10955-006-9143-6
[37] B. Nachtergaele dan R. Sims. Lieb-Robinson terikat dalam fisika banyak benda kuantum. Matematika Kontemporer 529, 141-176 (2010).
https: / / doi.org/ 10.1090 / conm / 529/10429
[38] S. Bravyi, MB Hastings, dan F. Verstraete. Batas Lieb-robinson dan generasi korelasi dan urutan kuantum topologi. Surat Tinjauan Fisik 97, 050401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.050401
[39] C.-F. Chen dan A.Lucas. Batas pertumbuhan operator dari teori graf. Komunikasi dalam Fisika Matematika 385, halaman1273โ1323 (2021).
https:/โ/โdoi.org/โ10.1007/โs00220-021-04151-6
[40] EH Lieb dan DW Robinson. Kecepatan grup hingga sistem spin kuantum. Komunikasi dalam Fisika Matematika 28, 251โ257 (1972).
https: / / doi.org/ 10.1007 / BF01645779
[41] J. Haah, MB Hastings, R. Kothari, dan GH Low. Algoritma kuantum untuk mensimulasikan evolusi waktu nyata dari kisi Hamiltonian. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 350โ360 (2018).
https: / / doi.org/ 10.1109 / FOCS.2018.00041
[42] A. Lubotzky, R. Phillips, dan P. Sarnak. grafik Ramanujan. Combinatorica 8, 261โ277 (1988).
https: / / doi.org/ 10.1007 / BF02126799
[43] B.Mohar. Bilangan isoperimetri dari graf. Jurnal Teori Kombinatorial, Seri B 47, 274โ291 (1989).
https:/โ/โdoi.org/โ10.1016/โ0095-8956(89)90029-4
[44] AW Marcus, DA Spielman, dan N. Srivastava. Jalinan Famili IV: Grafik Ramanujan Bipartit dari Semua Ukuran. Pada tahun 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), 1358โ1377 (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.87
[45] AW Marcus, DA Spielman, dan N. Srivastava. Jalinan Famili IV: Grafik Ramanujan Bipartit dari Semua Ukuran. Jurnal SIAM tentang Komputasi 47, 2488โ2509 (2018).
https://โ/โdoi.org/โ10.1137/โ16M106176X
[46] C. Hall, D. Puder, dan WF Sawin. Penutup Ramanujan dari grafik. Kemajuan dalam Matematika 323, 367โ410 (2018).
https://โ/โdoi.org/โ10.1016/โj.aim.2017.10.042
[47] MX Goemans dan DP Williamson. Algoritma aproksimasi yang ditingkatkan untuk masalah pemotongan dan kepuasan maksimum menggunakan pemrograman semidefinite. Jurnal ACM 42, 1115-1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684
[48] RD Somma, D. Nagaj, dan M. Kieferovรก. Quantum Speedup oleh Quantum Annealing. Surat Tinjauan Fisik 109, 050501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.050501
[49] MB Hasting. Kekuatan Komputasi Kuantum Adiabatik dengan Masalah Tanpa Tanda. Kuantum 5, 597 (2021).
https:/โ/โdoi.org/โ10.22331/โq-2021-12-06-597
[50] A. Gilyen, MB Hastings, dan U. Vazirani. (Sub)Keuntungan eksponensial dari komputasi kuantum adiabatik tanpa masalah tanda. Dalam Prosiding Simposium ACM Tahunan tentang Teori Komputasi (STOC), 1357โ1369 (2021).
https: / / doi.org/ 10.1145 / 3406325.3451060
[51] R.Bhati. Analisis matriks. Teks Pascasarjana dalam Matematika. Springer New York (1996).
https:/โ/โdoi.org/โ10.1007/โ978-1-4612-0653-8
[52] R.Bhati. Matriks pasti positif. Pers Universitas Princeton, (2007).
https: / / doi.org/ 10.1515 / 9781400827787
[53] BD McKay, NC Wormald, dan B. Wysocka. Siklus Pendek dalam Grafik Reguler Acak. The Electronic Journal of Combinatorics 11, 1โ12 (2004).
https: / / doi.org/ 10.37236 / 1819
[54] F. Kardoลก, D. Krรกl, dan J. Volec. Pemotongan tepi maksimum dalam grafik kubik dengan ketebalan besar dan dalam grafik kubik acak. Struktur & Algoritma Acak 41, 506โ520 (2012).
https: / / doi.org/ 10.1002 / rsa.20471
[55] D. Coppersmith, D. Gamarnik, MT Hajiaghayi, dan GB Sorkin. MAX SAT acak, MAX CUT acak, dan transisi fasenya. Struktur dan Algoritma Acak 24, 502โ545 (2004).
https: / / doi.org/ 10.1002 / rsa.20015
[56] A. Dembo, A. Montanari, dan S. Sen. Pemotongan ekstrim dari grafik acak jarang. Sejarah Probabilitas 45, 1190โ1217 (2017).
https://โ/โdoi.org/โ10.1214/โ15-AOP1084
Dikutip oleh
[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzรฉ, dan Daniel Stilck Franรงa, โKeterbatasan algoritma kuantum variasional: pendekatan transportasi optimal kuantumโ, arXiv: 2204.03455.
Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2022-07-19 03:10:09). Daftar ini mungkin tidak lengkap karena tidak semua penerbit menyediakan data kutipan yang cocok dan lengkap.
On Layanan dikutip-oleh Crossref tidak ada data tentang karya mengutip ditemukan (upaya terakhir 2022-07-19 03:10:07).
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.