Google DeepMind
CQIF, DAMTP, Universitas Cambridge, Inggris
Apakah makalah ini menarik atau ingin dibahas? Scite atau tinggalkan komentar di SciRate.
Abstrak
Persiapan keadaan kuantum merupakan unsur penting untuk algoritma kuantum tingkat tinggi lainnya, seperti simulasi Hamiltonian, atau untuk memuat distribusi ke dalam perangkat kuantum yang akan digunakan misalnya dalam konteks tugas optimasi seperti pembelajaran mesin. Dimulai dengan metode "kotak hitam" generik yang dirancang oleh Grover pada tahun 2000, yang menggunakan amplifikasi amplitudo untuk memuat koefisien yang dihitung oleh oracle, ada serangkaian hasil dan peningkatan yang panjang dengan berbagai kondisi tambahan pada amplitudo yang akan dimuat, yang berpuncak pada Karya Sanders et al. yang menghindari hampir semua aritmatika selama tahap persiapan.
Dalam pekerjaan ini, kami membangun skema pemuatan status kotak hitam yang dioptimalkan yang dengannya berbagai set koefisien penting dapat dimuat secara signifikan lebih cepat daripada di $O(sqrt N)$ putaran amplifikasi amplitudo, hingga hanya $O(1)$ banyak. Kami mencapai ini dengan dua varian algoritma kami. Yang pertama menggunakan modifikasi oracle dari Sanders et al., yang membutuhkan lebih sedikit ancillas ($log_2 g$ vs $g+2$ dalam presisi bit $g$), dan lebih sedikit operasi non-Clifford per putaran amplifikasi amplitudo dalam konteks algoritma kami. Yang kedua menggunakan oracle yang sama, tetapi dengan biaya yang sedikit meningkat dalam hal ancillas ($g+log_2g$) dan operasi non-Clifford per putaran amplifikasi. Karena jumlah putaran amplifikasi amplitudo masuk sebagai faktor perkalian, skema pemuatan status kotak hitam kami menghasilkan percepatan hingga eksponensial dibandingkan dengan metode sebelumnya. Percepatan ini diterjemahkan di luar kotak kotak hitam.
Ringkasan populer
Dalam pekerjaan ini, kami meningkatkan rutin host, dengan secara signifikan mengurangi jumlah kueri yang diperlukan ke kotak hitam, menghasilkan percepatan hingga eksponensial – tentu saja tergantung pada data yang akan dimuat, tetapi hasilnya berlaku untuk berbagai kumpulan data atau distribusi yang menarik. Kami selanjutnya merancang subrutin kotak hitam tertentu, yang disesuaikan untuk bekerja dengan sangat baik dengan skema pemuatan data host kami yang selanjutnya mengurangi qubit dan overhead gerbang yang diperlukan.
► data BibTeX
► Referensi
[1] Lov K. Grover "Sintesis Superposisi Kuantum dengan Komputasi Kuantum" Surat Tinjauan Fisik 85, 1334-1337 (2000).
https: / / doi.org/ 10.1103 / PhysRevLett.85.1334
[2] Yuval R. Sanders, Guang Hao Low, Artur Scherer, dan Dominic W. Berry, “Persiapan Keadaan Kuantum Kotak Hitam tanpa Aritmatika” Surat Tinjauan Fisik 122, 020502 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.020502
[3] Aram W. Harrow, Avinatan Hassidim, dan Seth Lloyd, "Algoritma Quantum untuk Sistem Persamaan Linear" Surat Tinjauan Fisik 103, 150502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
arXiv: 0811.3171
[4] Julia Kempe “Jalan acak kuantum – tinjauan pengantar” Fisika Kontemporer 44, 307–327 (2003).
https: / / doi.org/ 10.1080 / 00107151031000110776
arXiv: 0303081
[5] Miklos Santha “Algoritma Pencarian Berbasis Quantum Walk” Teori dan Aplikasi Model Komputasi 31–46 (2008).
https://doi.org/10.1007/978-3-540-79228-4_3
http://link.springer.com/10.1007/978-3-540-79228-4%7B%5C_%7D3
[6] Dominic W. Berryand Andrew M. Childs “Simulasi kotak hitam Hamiltonian dan implementasi kesatuan” (2009).
https: / / doi.org/ 10.26421 / QIC12.1-2
arXiv: 0910.4157
[7] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, dan Xiaodi Wu, “Quantum SDP Solvers: Large Speed-up, Optimality, and Applications to Quantum Learning” ICALP 2019 (2017).
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.27
arXiv: 1710.02581
[8] Sergey Bravyi, Alexander Kliesch, Robert Koenig, dan Eugene Tang, “Hambatan untuk Persiapan Negara dan Optimalisasi Variasi dari Perlindungan Simetri” (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
arXiv: 1910.08980
[9] Dominic W. Berry, Andrew M. Childs, dan Robin Kothari, “simulasi Hamilton dengan ketergantungan yang hampir optimal pada semua parameter” (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.54
arXiv: 1501.01715
[10] N Cody Jones, James D. Whitfield, Peter L. McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik, dan Yoshihisa Yamamoto, “Simulasi kimia kuantum lebih cepat pada komputer kuantum yang toleran terhadap kesalahan” Jurnal Fisika Baru 14, 115023 (2012).
https://doi.org/10.1088/1367-2630/14/11/115023
arXiv: 1204.0567
[11] Andrei N. Soklakovand Rüdiger Schack "Persiapan keadaan yang efisien untuk register bit kuantum" Tinjauan Fisik A 73, 012307 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.012307
[12] Martin Pleschand aslav Brukner “Persiapan keadaan kuantum dengan dekomposisi gerbang universal” Tinjauan Fisik A 83, 032302 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.032302
arXiv: 1003.5760
[13] Mikko Mottonen, Juha J. Vartiainen, Ville Bergholm, dan Martti M. Salomaa, "Transformasi keadaan kuantum menggunakan rotasi terkontrol seragam" Quant. Inf. Komp. 5, 467 (2004).
https:///doi.org/10.48550/arXiv.quant-ph/0407010
arXiv: 0407010
[14] Israel F. Araujo, Daniel K. Park, Francesco Petruccione, dan Adenilton J. da Silva, “Algoritme bagi-dan-taklukkan untuk persiapan keadaan kuantum” (2020).
https://doi.org/10.1038/s41598-021-85474-1
arXiv: 2008.01511
[15] Lov Groverand Terry Rudolph “Menciptakan superposisi yang sesuai dengan distribusi probabilitas yang dapat diintegrasikan secara efisien” (2002).
https:///doi.org/10.48550/arXiv.quant-ph/0208112
arXiv: 0208112
[16] Andrew M. Childs "Pada Hubungan Antara Terus-menerus dan Diskrit-Waktu Quantum Walk" Komunikasi dalam Fisika Matematika 294, 581-603 (2009).
https://doi.org/10.1007/s00220-009-0930-1
[17] Christa Zoufal, Aurélien Lucchi, dan Stefan Woerner, “Quantum Generative Adversarial Networks for learning and loading random distributions” npj Quantum Information (2019).
https://doi.org/10.1038/s41534-019-0223-2
arXiv: 1904.00043
[18] Michael A. Nielsen dan Isaac L. Chuang “Komputasi Kuantum dan Informasi Kuantum” Cambridge University Press (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667
http://books.google.com/books?id=-s4DEy7o-a0C%7B%5C&%7Dpgis=1%20http://ebooks.cambridge.org/ref/id/CBO9780511976667
[19] Theodore J. Yoder, Guang Hao Low, dan Isaac L. Chuang, “Pencarian Kuantum Titik Tetap dengan Jumlah Kueri Optimal” Surat Tinjauan Fisik 113, 210501 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.210501
[20] Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, dan David Petrie Moulton, “Sirkuit penambahan pembawa riak kuantum baru” (2004).
https:///doi.org/10.48550/arXiv.quant-ph/0410184
arXiv: 0410184
[21] Craig Gidney “Mengurangi separuh biaya penambahan kuantum” Quantum 2, 74 (2018).
https://doi.org/10.22331/q-2018-06-18-74
arXiv: 1709.06648
[22] Yong He, Ming-Xing Luo, E. Zhang, Hong-Ke Wang, dan Xiao-Feng Wang, “Penguraian Gerbang Toffoli n-qubit dengan Kompleksitas Sirkuit Linier” Jurnal Internasional Fisika Teoritis 56, 2350–2361 (2017).
https://doi.org/10.1007/s10773-017-3389-4
[23] John A. Smolinand David P. DiVincenzo “Lima gerbang kuantum dua bit cukup untuk mengimplementasikan gerbang kuantum Fredkin” Tinjauan Fisik A 53, 2855–2856 (1996).
https: / / doi.org/ 10.1103 / PhysRevA.53.2855
[24] Quantum AI Lab Google, Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann , Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandr, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, NicholasC. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalmman, Hartmut Neven, John M Martinis, Quantum AI Lab Google, Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho , Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandr, Jarrod R. McClean, Matthew McEwen, Anthony Megran t, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalmman, Hartmut Neven, dan John M. Martinis, “Supremasi kuantum menggunakan prosesor superkonduktor yang dapat diprogram” Nature 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5
http://www.nature.com/articles/s41586-019-1666-5
[25] Ashley Montanaro “Pencarian kuantum dengan saran” 1–14 (2009).
arXiv: 0908.3066
Dikutip oleh
[1] Kouhei Nakaji, Shumpei Uno, Yohichi Suzuki, Rudy Raymond, Tamiya Onodera, Tomoki Tanaka, Hiroyuki Tezuka, Naoki Mitsuda, dan Naoki Yamamoto, “Perkiraan encoding amplitudo dalam sirkuit kuantum berparameter dangkal dan penerapannya pada indikator pasar keuangan”, Penelitian Tinjauan Fisik 4 2, 023136 (2022).
[2] Weiwen Jiang, Jinjun Xiong, dan Yiyu Shi, "Kerangka kerja desain bersama jaringan saraf dan sirkuit kuantum menuju keuntungan kuantum", Komunikasi Alam 12, 579 (2021).
[3] Vladimir Vargas-Calderón, Fabio A. González, dan Herbert Vinck-Posada, “Klasifikasi bebas optimasi dan Estimasi Densitas dengan Sirkuit Quantum”, arXiv: 2203.14452.
[4] Gabriel Marin-Sanchez, Javier Gonzalez-Conde, dan Mikel Sanz, “Algoritma kuantum untuk perkiraan fungsi pemuatan”, arXiv: 2111.07933.
[5] Shengbin Wang, Zhimin Wang, Guolong Cui, Lixin Fan, Shangshang Shi, Ruimin Shang, Wendong Li, Zhiqiang Wei, dan Yongjian Gu, “Aritmatika Amplitudo Kuantum”, arXiv: 2012.11056.
[6] B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, dan William J. Zeng, "Sumber Daya Kuantum yang Diperlukan untuk Blok-Encode Matriks Data Klasik", arXiv: 2206.03505.
[7] M. Yu Kirillin, AV Priezzhev, J. Hast, dan Risto Myllylä, "APLIKASI LASER DAN TOPIK LAIN DALAM ELEKTRONIK QUANTUM: Simulasi Monte Carlo pembersihan optik kertas dalam tomografi koherensi optik", Elektronik Kuantum 36 2, 174 (2006).
[8] Shengbin Wang, Zhimin Wang, Guolong Cui, Shangshang Shi, Ruimin Shang, Lixin Fan, Wendong Li, Zhiqiang Wei, dan Yongjian Gu, "Persiapan status kuantum kotak hitam cepat berdasarkan kombinasi linier unitari", Pemrosesan Informasi Quantum 20 8, 270 (2021).
[9] Raoul Heese, Patricia Bickert, dan Astrid Elisa Niederle, "Representasi pohon klasifikasi biner dengan fitur biner oleh sirkuit kuantum", arXiv: 2108.13207.
[10] Weiwen Jiang, Jinjun Xiong, dan Yiyu Shi, “Ketika Pembelajaran Mesin Bertemu Komputer Kuantum: Studi Kasus”, arXiv: 2012.10360.
[11] Tiago ML de Veras, Leon D. da Silva, dan Adenilton J. da Silva, “Persiapan keadaan kuantum jarang ganda”, Pemrosesan Informasi Quantum 21 6, 204 (2022).
[12] DA Zimnyakov, LV Kuznetsova, OV Ushakova, dan Risto Myllylä, “Masalah khusus yang ditujukan untuk hamburan radiasi multipel dalam media acak: Pada perkiraan parameter optik efektif dari media fibrillar padat”, Elektronik Kuantum 37 1, 9 (2007).
[13] Shengbin Wang, Zhimin Wang, Runhong He, Guolong Cui, Shangshang Shi, Ruimin Shang, Jiayun Li, Yanan Li, Wendong Li, Zhiqiang Wei, dan Yongjian Gu, “Persiapan Keadaan Kuantum Kotak Hitam dengan Koefisien Terbalik”, arXiv: 2112.05937.
Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2022-08-04 12:34:11). 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 2022-08-04 12:34:09: Tidak dapat mengambil data yang dikutip oleh untuk 10.22331 / q-2022-08-04-773 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.
