Simulasi Cepat Sirkuit Planar Clifford

Diterbitkan Ulang Oleh Plato

Followers: 0

David Gosset^1,2,3, Daniel Grier^1,4,5, Alex Kerzner^1,2, dan Luke Schaeffer^1,2,6

¹Institute for Quantum Computing, University of Waterloo, Kanada
²Departemen Kombinatorik dan Optimasi, Universitas Waterloo, Kanada
³Institut Perimeter untuk Fisika Teoritis, Waterloo, Kanada
⁴Sekolah Ilmu Komputer Cheriton, Universitas Waterloo, Kanada
⁵Departemen Ilmu dan Teknik Komputer dan Departemen Matematika, Universitas California, San Diego, AS
⁶Pusat Gabungan untuk Informasi Kuantum dan Ilmu Komputer, College Park, Maryland, AS

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

Abstrak

Rangkaian kuantum umum dapat disimulasikan secara klasik dalam waktu eksponensial. Jika memiliki tata letak planar, maka algoritme kontraksi jaringan tensor karena Markov dan Shi memiliki eksponensial waktu proses dalam akar kuadrat ukurannya, atau lebih umum lagi eksponensial dalam lebar pohon dari grafik yang mendasarinya. Secara terpisah, Gottesman dan Knill menunjukkan bahwa jika semua gerbang dibatasi menjadi Clifford, maka terdapat simulasi waktu polinomial. Kami menggabungkan dua gagasan ini dan menunjukkan bahwa lebar pohon dan planaritas dapat dimanfaatkan untuk meningkatkan simulasi rangkaian Clifford. Hasil utama kami adalah algoritme klasik dengan penskalaan waktu proses secara asimtotik sebagai $n^{omega/2}$ $lt$ $n^{1.19}$ yang mengambil sampel dari distribusi keluaran yang diperoleh dengan mengukur semua $n$ qubit dalam keadaan grafik planar di pangkalan Pauli tertentu. Di sini $omega$ adalah eksponen perkalian matriks. Kami juga menyediakan algoritme klasik dengan runtime asimtotik yang sama yang mengambil sampel dari distribusi keluaran sirkuit Clifford dengan kedalaman konstan dalam geometri planar. Pekerjaan kami meningkatkan algoritma klasik yang dikenal dengan runtime kubik.

Bahan utamanya adalah pemetaan yang, dengan dekomposisi pohon dari beberapa grafik $G$, menghasilkan sirkuit Clifford dengan struktur yang mencerminkan dekomposisi pohon dan mengemulasi pengukuran keadaan grafik yang sesuai. Kami menyediakan simulasi klasik rangkaian ini dengan runtime yang disebutkan di atas untuk grafik planar dan sebaliknya $nt^{omega-1}$ di mana $t$ adalah lebar dekomposisi pohon. Algoritme kami menggabungkan dua subrutin yang mungkin memiliki kepentingan independen. Yang pertama adalah versi waktu perkalian matriks dari simulasi Gottesman-Knill pengukuran multi-qubit pada keadaan stabilisator. Yang kedua adalah algoritme klasik baru untuk menyelesaikan sistem linier simetris pada $mathbb{F}_2$ dalam geometri planar, memperluas karya sebelumnya yang hanya diterapkan pada sistem linier non-singular dalam pengaturan analog.

Simulasi cepat sirkuit Clifford planar PlatoBlockchain Data Intelligence. Pencarian Vertikal. Ai.

Gambar unggulan: Searah jarum jam dari kiri: Grafik, dekomposisi pohon yang bagus, dan sirkuit yang menyiapkan status grafik yang sesuai.

[Embedded content]

► data BibTeX

@article{Gosset2024fastsimulationof, doi = {10.22331/q-2024-02-12-1251}, url = {https://doi.org/10.22331/q-2024-02-12-1251}, title = {Simulasi cepat dari planar {C}lifford sirkuit}, penulis = {Gosset, David dan Grier, Daniel dan Kerzner, Alex dan Schaeffer, Luke}, jurnal = {{Quantum}}, issn = {2521-327X}, penerbit = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, halaman = {1251}, bulan = feb, tahun = {2024} }

► Referensi

[1] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, dkk. "Supremasi kuantum menggunakan prosesor superkonduktor yang dapat diprogram". Alam 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5

[2] “Dokumentasi kuantum IBM”. https:///docs.quantum.ibm.com/run.
https:///docs.quantum.ibm.com/run

[3] Matthew D Reed, Leonardo DiCarlo, Simon E Nigg, Luyan Sun, Luigi Frunzio, Steven M Girvin, dan Robert J Schoelkopf. “Realisasi koreksi kesalahan kuantum tiga qubit dengan sirkuit superkonduktor”. Alam 482, 382–385 (2012).
https: / / doi.org/ 10.1038 / nature10786

[4] Antonio D Córcoles, Easwar Magesan, Srikanth J Srinivasan, Andrew W Cross, Matthias Steffen, Jay M Gambetta, dan Jerry M Chow. “Demonstrasi kode deteksi kesalahan kuantum menggunakan kisi persegi empat qubit superkonduktor”. Komunikasi alam 6, 1–10 (2015).
https:///doi.org/10.1038/ncomms7979

[5] Nissim Ofek, Andrei Petrenko, Reinier Heeres, Philip Reinhold, Zaki Leghtas, Brian Vlastakis, Yehan Liu, Luigi Frunzio, SM Girvin, Liang Jiang, dkk. “Memperpanjang masa pakai bit kuantum dengan koreksi kesalahan di sirkuit superkonduktor”. Alam 536, 441–445 (2016).
https: / / doi.org/ 10.1038 / nature18949

[6] Igor L Markov dan Yaoyun Shi. “Mensimulasikan komputasi kuantum dengan mengontrak jaringan tensor”. Jurnal SIAM tentang Komputasi 38, 963–981 (2008).
https: / / doi.org/ 10.1137 / 050644756

[7] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, dan Hartmut Neven. “Simulasi rangkaian kuantum kedalaman rendah sebagai model grafis kompleks tak terarah” (2017).

[8] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, dan Mark Howard. “Simulasi rangkaian kuantum dengan dekomposisi stabilizer tingkat rendah”. Kuantum 3, 181 (2019).
https://doi.org/10.22331/q-2019-09-02-181

[9] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, Erik W Draeger, Eric T Holland, dan Robert Wisnieff. “Mendobrak penghalang 49-qubit dalam simulasi sirkuit kuantum” (2017).

[10] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, dan Robert Wisnieff. “Memanfaatkan penyimpanan sekunder untuk mensimulasikan sirkuit Sycamore 54-qubit yang dalam” (2019).

[11] Boaz Barak, Chi-Ning Chou, dan Xun Gao. “Memalsukan pembandingan entropi silang linier di sirkuit kuantum dangkal” (2020).

[12] Barbara M Terhal dan David P DiVincenzo. “Komputasi kuantum adaptif, sirkuit kuantum kedalaman konstan, dan permainan Arthur-Merlin” (2002).

[13] Michael J Bremner, Richard Jozsa, dan Dan J Shepherd. “Simulasi klasik dari komputasi kuantum komutasi menyiratkan runtuhnya hierarki polinomial”. Prosiding Royal Society A: Ilmu Matematika, Fisika dan Teknik 467, 459–472 (2011).
https: / / doi.org/ 10.1098 / rspa.2010.0301

[14] Scott Aaronson dan Alex Arkhipov. “Kompleksitas komputasi optik linier”. Dalam Prosiding simposium ACM tahunan keempat puluh tiga tentang Teori komputasi. Halaman 333–342. (2011).
https: / / doi.org/ 10.1145 / 1993636.1993682

[15] Daniel Gottesman. “Representasi Heisenberg dari komputer kuantum” (1998).

[16] Sergey Bravyi dan David Gosset. “Peningkatan simulasi klasik sirkuit kuantum yang didominasi oleh gerbang Clifford”. Surat review fisik 116, 250501 (2016).
https: / / doi.org/ 10.1103 / physrevlett.116.250501

[17] Scott Aaronson dan Daniel Gottesman. "Peningkatan simulasi sirkuit stabilizer". Tinjauan Fisik A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[18] Sergey Bravyi, David Gosset, dan Robert König. “Keuntungan kuantum dengan sirkuit dangkal”. Sains 362, 308–311 (2018).
https: / / doi.org/ 10.1126 / science.aar3106

[19] Adam Bene Watts, Robin Kothari, Luke Schaeffer, dan Avishay Tal. “Pemisahan eksponensial antara sirkuit kuantum dangkal dan sirkuit klasik dangkal kipas tak terbatas”. Dalam Prosiding Simposium ACM SIGACT Tahunan ke-51 tentang Teori Komputasi. Halaman 515–526. (2019).
https: / / doi.org/ 10.1145 / 3313276.3316404

[20] Daniel Grier dan Luke Schaeffer. “Sirkuit Clifford dangkal interaktif: keunggulan kuantum terhadap $mathsf{NC}^1$ dan seterusnya”. Dalam Prosiding Simposium ACM SIGACT Tahunan ke-52 tentang Teori Komputasi. Halaman 875–888. (2020).
https: / / doi.org/ 10.1145 / 3357713.3384332

[21] Sergey Bravyi, David Gosset, Robert Koenig, dan Marco Tomamichel. “Keuntungan kuantum dengan sirkuit dangkal yang bising”. Fisika AlamHalaman 1–6 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

[22] Robert Raussendorf dan Hans J Briegel. “Komputer kuantum satu arah”. Tinjauan Fisik Surat 86, 5188 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[23] Josh Alman dan Virginia Vassilevska Williams. “Metode laser yang disempurnakan dan penggandaan matriks yang lebih cepat” (2020).

[24] Chaowen Guan dan Kenneth W Regan. “Sirkuit penstabil, bentuk kuadrat, dan peringkat matriks komputasi” (2019).

[25] Daniel Grier dan Luke Schaeffer. “gridCHP++, lisensi Apache versi 2.0”. https://github.com/danielgrier/gridCHPpp/tree/v1.0.0.
https://github.com/danielgrier/gridCHPpp/tree/v1.0.0

[26] Alan George. “Diseksi bersarang dari jaring elemen hingga beraturan”. Jurnal SIAM tentang Analisis Numerik 10, 345–363 (1973).
https: / / doi.org/ 10.1137 / 0710032

[27] Richard J Lipton, Donald J Rose, dan Robert Endre Tarjan. “Diseksi bersarang umum”. Jurnal SIAM tentang analisis numerik 16, 346–358 (1979).
https: / / doi.org/ 10.1137 / 0716027

[28] Noga Alon dan Raphael Yuster. “Memecahkan sistem linier melalui diseksi bersarang”. Pada Simposium Tahunan ke-2010 IEEE 51 tentang Fondasi Ilmu Komputer. Halaman 225–234. IEEE (2010).
https: / / doi.org/ 10.1109 / FOCS.2010.28

[29] Richard J. Lipton dan Robert Endre Tarjan. “Teorema pemisah grafik planar”. Jurnal SIAM Matematika Terapan 36, 177–189 (1979).
https: / / doi.org/ 10.1137 / 0136016

[30] Scott Aaronson dan Lijie Chen. “Dasar teori kompleksitas dari eksperimen supremasi kuantum”. Dalam Konferensi Kompleksitas Komputasi ke-32 (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum untuk Informatik (2017).

[31] Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman, dan Yaoyun Shi. “Simulasi klasik sirkuit kuantum ukuran menengah” (2018).

[32] Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S Humble, Rupak Biswas, Eleanor G Rieffel, Alan Ho, dan Salvatore Mandrà. “Menetapkan batas supremasi kuantum dengan simulasi 281 pflop/s”. Sains dan Teknologi Kuantum 5, 034003 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab7eeb

[33] Stefan Arnborg, Derek G Corneil, dan Andrzej Proskurowski. “Kompleksitas menemukan penyematan di pohon $k$”. Jurnal SIAM tentang Metode Diskrit Aljabar 8, 277–284 (1987).
https: / / doi.org/ 10.1137 / 0608024

[34] HL Bodlaender. “Pemandu wisata melintasi pepohonan”. Acta Cybernetica 11, 1–21 (1993).

[35] Hans L. Bodlaender, Pål Grøonås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, dan Michał Pilipczuk. “Algoritme perkiraan $c^kn$ 5 untuk lebar pohon”. Jurnal SIAM tentang Komputasi 45, 317–378 (2016).
https: / / doi.org/ 10.1137 / 130947374

[36] Sergey Bravyi, Graeme Smith, dan John A Smolin. “Perdagangan sumber daya komputasi klasik dan kuantum”. Tinjauan Fisik X 6, 021043 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021043

[37] M Van den Sarang. “Simulasi klasik komputasi kuantum, teorema Gottesman-Knill, dan lebih jauh lagi” (2008).

[38] Alex Kerzner. “Simulasi Clifford: Teknik dan aplikasi”. tesis master. Universitas Waterloo. (2021).

[39] Carsten sial. “Masalah selesai untuk $oplus{L}$”. Dalam Jürgen Dassow dan Jozef Kelemen, editor, Aspek dan Prospek Ilmu Komputer Teoritis. Halaman 130–137. Berlin, Heidelberg (1990). Pegas Berlin Heidelberg.
https://doi.org/10.1016/0020-0190(90)90150-V

[40] David Eppstein (2007). commons.wikimedia.org/wiki/File:Tree_decomposition.svg, diakses 08/31/2020.

[41] Hans L Bodlaender dan Ton Kloks. “Algoritme yang lebih baik untuk lebar jalur dan lebar pohon grafik”. Dalam Automata, Bahasa dan Pemrograman: Kolokium Internasional ke-18 Madrid, Spanyol, 8–12 Juli 1991 Prosiding 18. Halaman 544–555. Pegas (1991).
https://doi.org/10.1007/3-540-54233-7_162

[42] Oscar H Ibarra, Shlomo Moran, dan Roger Hui. “Generalisasi algoritma dan aplikasi dekomposisi matriks LUP cepat”. Jurnal Algoritma 3, 45–56 (1982).
https://doi.org/10.1016/0196-6774(82)90007-4

[43] Adi Ben-Israel dan Thomas NE Greville. "Pembalikan umum: teori dan aplikasi". Volume 15. Sains & Media Bisnis Springer. (2003).
https: / / doi.org/ 10.1007 / b97366

[44] Michael T Goodrich. “Pemisah planar dan triangulasi poligon paralel”. Jurnal Ilmu Komputer dan Sistem 51, 374–389 (1995).
https: / / doi.org/ 10.1006 / jcss.1995.1076

[45] Jeroen Dehaene dan Bart De Moor. “Grup Clifford, status penstabil, dan operasi linier dan kuadrat pada $mathrm{GF}$(2)”. Tinjauan Fisik A 68, 042318 (2003).
https: / / doi.org/ 10.1103 / PhysRevA.68.042318

[46] Simon Anders dan Hans J Briegel. “Simulasi cepat rangkaian stabilizer menggunakan representasi keadaan grafik”. Tinjauan Fisik A 73, 022334 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022334

[47] Sergey Bravyi. Komunikasi pribadi, 2017 (2017).

[48] Maarten Van den Nest, Jeroen Dehaene, dan Bart De Moor. “Deskripsi grafis dari tindakan transformasi Clifford lokal pada keadaan grafik”. Tinjauan Fisik A 69, 022316 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.69.022316

Dikutip oleh

[1] Travis L. Scholten, Carl J. Williams, Dustin Moody, Michele Mosca, William Hurley, William J. Zeng, Matthias Troyer, dan Jay M. Gambetta, “Menilai Manfaat dan Risiko Komputer Kuantum”, arXiv: 2401.16317, (2024).

[2] Lorenzo Leone, Salvatore FE Oliviero, Seth Lloyd, dan Alioscia Hamma, “Mempelajari dekoder yang efisien untuk pengacak kuantum semu”, arXiv: 2212.11338, (2022).

[3] Ryan L. Mann, “Mensimulasikan komputasi kuantum dengan polinomial Tutte”, npj Informasi Quantum 7, 141 (2021).

[4] Sahar Atallah, Michael Garn, Sania Jevtic, Yukuan Tao, dan Shashank Virmani, “Simulasi klasik yang efisien dari rangkaian kuantum keadaan cluster dengan input alternatif”, arXiv: 2201.07655, (2022).

[5] Shihao Zhang, Jiacheng Bao, Yifan Sun, Lvzhou Li, Houjun Sun, dan Xiangdong Zhang, “Skema klasik paralel berkinerja tinggi untuk simulasi sirkuit kuantum dangkal”, arXiv: 2103.00693, (2021).

Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2024-02-13 03:31:05). 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 2024-02-13 03:31:02).

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.
PlatoData.Jaringan Vertikal Generatif Ai. Berdayakan Diri Anda. Akses Di Sini.
PlatoAiStream. Intelijen Web3. Pengetahuan Diperkuat. Akses Di Sini.
PlatoESG. Karbon, teknologi bersih, energi, Lingkungan Hidup, Tenaga surya, Penanganan limbah. Akses Di Sini.
PlatoHealth. Kecerdasan Uji Coba Biotek dan Klinis. Akses Di Sini.
Sumber: https://quantum-journal.org/papers/q-2024-02-12-1251/

Stempel Waktu: Februari 12, 2024

Lebih dari Jurnal Kuantum

Saluran Pauli dapat diperkirakan dari pengukuran sindrom dalam koreksi kesalahan kuantum

Jurnal Kuantum

Node Sumber: 1911866

Stempel Waktu: November 7, 2023

Tanda tangan kuantum dalam gelombang gravitasi nonlinier

Kluster Sumber:

Jurnal Kuantum

Node Sumber: 1774792

Stempel Waktu: Desember 19, 2022

Simulasi cepat sirkuit Clifford planar

Diterbitkan Ulang Oleh Plato

Abstrak

► data BibTeX

► Referensi

Dikutip oleh

Lebih dari Jurnal Kuantum

Saluran Pauli dapat diperkirakan dari pengukuran sindrom dalam koreksi kesalahan kuantum

Apakah dinamika kausal menyiratkan interaksi lokal?

Pendekatan kuantum cepat untuk optimasi kombinatorial yang terinspirasi oleh transfer keadaan optimal

Simetri meningkatkan pemecah eigen spin kuantum variasional

Formula multi-produk yang terkondisi dengan baik untuk simulasi Hamiltonian yang ramah perangkat keras

Pembuatan dan pelestarian status cat dan grid berbasis pengukuran dalam status cluster variabel kontinu

Abstrak: Analisis Rangkaian Kuantum melalui Simulasi Penstabil Abstrak

Entropi penstabil dan monoton nonstabilisasi

Persiapan qubit fisik berkualitas tinggi tanpa seleksi

Mempersiapkan kondisi bekas luka banyak tubuh kuantum pada komputer kuantum

Tanda tangan kuantum dalam gelombang gravitasi nonlinier

Tentang Kami

Pencarian Vertikal & Ai

Platform

Tetap Berhubung

Akun