Keunggulan Kuantum Dalam Komputasi Kuantum Berbasis Pengukuran Datar Temporal

Diterbitkan Ulang Oleh Plato

Followers: 0

Michael de Oliveira^1,2,3, Luis S. Barbosa^1,2,3, dan Ernesto F. Galvão^3,4

¹Universitas Minho, Departemen Ilmu Komputer, Braga, Portugal
²INESC TEC, Braga, Portugal
³Laboratorium Nanoteknologi Iberia Internasional (INL) Av. Mestre Jose Veiga, 4715-330, Braga, Portugal
⁴Instituto de Física, Universidade Federal Fluminense Av. Gal. Milton Tavares de Souza s/n, Niterói, RJ, 24210-340, Brasil

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

Abstrak

Beberapa kelas rangkaian kuantum telah terbukti memberikan keunggulan komputasi kuantum berdasarkan asumsi tertentu. Studi tentang kelas sirkuit kuantum yang semakin terbatas yang mampu memberikan keunggulan kuantum dimotivasi oleh kemungkinan penyederhanaan dalam demonstrasi eksperimental. Dalam makalah ini kami mempelajari efisiensi komputasi kuantum berbasis pengukuran dengan urutan pengukuran temporal yang benar-benar datar. Kami mengusulkan konstruksi baru untuk komputasi deterministik fungsi Boolean arbitrer, dengan memanfaatkan korelasi yang ada di status multi-qubit Greenberger, Horne, dan Zeilinger (GHZ). Kami mengkarakterisasi kompleksitas pengukuran yang diperlukan menggunakan hierarki Clifford, dan secara umum juga mengurangi jumlah qubit yang diperlukan dibandingkan dengan konstruksi sebelumnya. Secara khusus, kami mengidentifikasi rangkaian fungsi Boolean yang memungkinkan evaluasi deterministik menggunakan MBQC non-adaptif, yang menampilkan keunggulan kuantum dalam lebar dan jumlah gerbang dibandingkan dengan rangkaian klasik.

Keuntungan kuantum dalam komputasi kuantum berbasis pengukuran datar sementara PlatoBlockchain Data Intelligence. Pencarian Vertikal. Ai.

Gambar unggulan: Model MBQC non-adaptif dapat dijelaskan dengan arsitektur komputasi spesifik yang dibagi menjadi proses persiapan keadaan kuantum, rutinitas pengukuran, dan pemrosesan linier sebelum dan sesudah klasik terkait (kiri atas). Model ini memfasilitasi studi tentang kebutuhan sumber daya untuk mengevaluasi fungsi Boolean simetris dalam hal jumlah qubit asimtotik dan operasi yang diperlukan (kanan atas). Elemen-elemen ini mengungkap hasil utama kami [bawah], yang diartikulasikan untuk himpunan gerbang klasik dan kuantum standar serta deskripsi rangkaian [kiri bawah], yang mengkarakterisasi himpunan fungsi Boolean yang menunjukkan keunggulan kuantum sehubungan dengan jumlah gerbang dan lebar gerbang. sirkuit (kanan bawah).

[Embedded content]

Ringkasan populer

Komputasi kuantum menjanjikan keunggulan komputasi dibandingkan algoritma klasik terbaik untuk banyak tugas. Hasil yang teliti dalam mengukur keunggulan ini jarang terjadi, dan membantu memfokuskan penelitian pada sumber daya kuantum penting yang memberikan kinerja lebih baik daripada kinerja klasik. Keuntungan kuantum ini dapat terjadi sehubungan dengan sumber daya yang berbeda: jumlah gerbang yang diperlukan, kedalaman sirkuit yang dihasilkan, atau ukuran memori yang digunakan (dikenal sebagai lebar sirkuit).

Dalam karya ini kami menganalisis evaluasi fungsi Boolean, sesuatu yang dapat dilakukan komputer kuantum menggunakan hasil pengukuran yang berkorelasi pada status terjerat Greenberger-Horne-Zeilinger (GHZ) pada banyak qubit. Varian komputasi kuantum berbasis pengukuran ini tidak memerlukan adaptasi, sehingga semua qubit dapat diukur secara bersamaan. Struktur temporal datar dari proses komputasi ini, dalam beberapa kasus, menghasilkan sirkuit kuantum yang sangat ekonomis. Kami mengidentifikasi karakteristik fungsi Boolean yang menentukan berapa banyak qubit yang dibutuhkan, dan presisi pengukuran yang diperlukan. Untuk kelompok fungsi Boolean tertentu, kami menunjukkan adanya keunggulan besar dalam lebar dan jumlah gerbang dibandingkan dengan kelompok rangkaian klasik yang bersangkutan. Di masa depan, teknik kami dapat membantu merancang cara yang lebih baik dalam menggunakan sumber daya kuantum juga untuk sirkuit adaptif yang menampilkan lebih banyak ekspresi komputasi.

► data BibTeX

@artikel{Oliveira2024quantumadvantagein, doi = {10.22331/q-2024-04-09-1312}, url = {https://doi.org/10.22331/q-2024-04-09-1312}, title = {Keunggulan kuantum dalam komputasi kuantum berbasis pengukuran datar sementara}, penulis = {Oliveira, Michael de dan Barbosa, Lu{'{i}}s S. dan Galv{~{a}}o, Ernesto F.}, jurnal = {{Quantum}}, issn = {2521-327X}, penerbit = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, halaman = {1312}, bulan = April, tahun = {2024} }

► Referensi

[1] Scott Aaronson, DeVon Ingram, dan William Kretschmer. “Akrobatik BQP”. Di Shachar Lovett, editor, Konferensi Kompleksitas Komputasi ke-37 (CCC 2022). Volume 234 dari Leibniz International Proceedings in Informatics (LIPIcs), halaman 20:1–20:17. Dagstuhl, Jerman (2022). Schloss Dagstuhl – Leibniz-Zentrum untuk Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2022.20

[2] Richard Jozsa dan Noah Linden. "Tentang peran keterikatan dalam percepatan komputasi kuantum". Prosiding Royal Society of London. Seri A: Ilmu Matematika, Fisika, dan Teknik 459, 2011–2032 (2003).
https: / / doi.org/ 10.1098 / rspa.2002.1097

[3] Mark Howard, Joel Wallman, Victor Veitch, dan Joseph Emerson. “Kontekstualitas memberikan 'keajaiban' untuk komputasi kuantum”. Alam 510, 351–355 (2014).
https: / / doi.org/ 10.1038 / nature13460

[4] Juan Bermejo-Vega, Nicolas Delfosse, Dan E. Browne, Cihan Okay, dan Robert Raussendorf. “Kontekstualitas sebagai sumber daya untuk model komputasi kuantum dengan qubit”. Fis. Pendeta Lett. 119, 120505 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.120505

[5] Ernesto F. Galvão. “Fungsi wigner diskrit dan percepatan komputasi kuantum”. Fis. Pdt.A 71, 042302 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.042302

[6] A. Mari dan J. Eisert. “Fungsi wigner positif membuat simulasi klasik komputasi kuantum menjadi efisien”. Fis. Pendeta Lett. 109, 230503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.230503

[7] Lov K. Grover. “Kelebihan superposisi”. Sains 280, 228–228 (1998).
https:///doi.org/10.1126/science.280.5361.228

[8] Robert Raussendorf dan Hans J. Briegel. “Komputer kuantum satu arah”. fisik. Pdt. Lett. 86, 5188–5191 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[9] Maarten Van den Nest, Akimasa Miyake, Wolfgang Dür, dan Hans J. Briegel. “Sumber daya universal untuk komputasi kuantum berbasis pengukuran”. Fis. Pendeta Lett. 97, 150504 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.150504

[10] Janet Anders dan Dan E. Browne. “Kekuatan komputasi korelasi”. Fis. Pendeta Lett. 102, 050502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.050502

[11] Vincent Danos dan Elham Kashefi. “Determinisme dalam model satu arah”. Fis. Pdt.A 74, 052310 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052310

[12] Daniel E Browne, Elham Kashefi, Mehdi Mhalla, dan Simon Perdrix. “Aliran umum dan determinisme dalam komputasi kuantum berbasis pengukuran”. Jurnal Fisika Baru 9, 250 (2007).
https://doi.org/10.1088/1367-2630/9/8/250

[13] Michael J Bremner, Ashley Montanaro, dan Dan J Shepherd. “Kompleksitas Kasus Rata-Rata Versus Perkiraan Simulasi Komputasi Kuantum Komuter”. Fis. Pendeta Lett. 117, 080501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501

[14] Matty J. Hoban, Joel J. Wallman, Hussain Anwar, Naïri Usher, Robert Raussendorf, dan Dan E. Browne. “Perhitungan klasik berbasis pengukuran”. Fis. Pendeta Lett. 112, 140505 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.112.140505

[15] Michael J. Bremner, Ashley Montanaro, dan Dan J. Shepherd. “Mencapai supremasi kuantum dengan komputasi kuantum perjalanan yang jarang dan berisik”. Kuantum 1, 8 (2017).
https://doi.org/10.22331/q-2017-04-25-8

[16] Leonardo Novo, Juani Bermejo-Vega, dan Raúl García-Patrón. “Keuntungan kuantum dari pengukuran energi sistem kuantum banyak benda”. Kuantum 5, 465 (2021).
https://doi.org/10.22331/q-2021-06-02-465

[17] Masahito Hayashi dan Yuki Takeuchi. “Memverifikasi komputasi kuantum perjalanan melalui estimasi fidelitas status grafik berbobot”. Jurnal Fisika Baru 21, 93060 (2019).
https://doi.org/10.1088/1367-2630/ab3d88

[18] Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, dan Jens Eisert. “Arsitektur untuk Simulasi Kuantum Menampilkan Percepatan Kuantum”. Fis. Pdt. X 8, 021010 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.021010

[19] Jacob Miller, Stephen Sanders, dan Akimasa Miyake. “Supremasi kuantum dalam komputasi berbasis pengukuran waktu konstan: Arsitektur terpadu untuk pengambilan sampel dan verifikasi”. Fis. Pdt.A 96, 062320 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062320

[20] Matty J Hoban, Earl T Campbell, Klearchos Loukopoulos, dan Dan E Browne. “Perhitungan kuantum berbasis pengukuran non-adaptif dan ketidaksetaraan Bell multi-pihak”. Jurnal Fisika Baru 13, 23014 (2011).
https://doi.org/10.1088/1367-2630/13/2/023014

[21] Ryuhei Mori. “Representasi Fourier periodik dari fungsi Boolean”. Info Kuantum. Hitung. 19, 392–412 (2019). url: https:///dl.acm.org/doi/abs/10.5555/3370251.3370253.
https: / / dl.acm.org/ doi / abs / 10.5555 / 3370251.3370253

[22] Markus Frembs, Sam Roberts, Earl T Campbell, dan Stephen D Bartlett. “Hierarki sumber daya untuk komputasi kuantum berbasis pengukuran”. Jurnal Fisika Baru 25, 013002 (2023).
https://doi.org/10.1088/1367-2630/acaee2

[23] Jelena Mackeprang, Daniel Bhatti, Matty J Hoban, dan Stefanie Barz. “Kekuatan qutrit untuk komputasi kuantum berbasis pengukuran non-adaptif”. Jurnal Fisika Baru 25, 073007 (2023).
https://doi.org/10.1088/1367-2630/acdf77

[24] Daniel Collins, Nicolas Gisin, Sandu Popescu, David Roberts, dan Valerio Scarani. “Ketidaksetaraan Tipe Lonceng untuk Mendeteksi $mathit{n}$-Body Nonseparability yang Sebenarnya”. Fis. Pendeta Lett. 88, 170405 (2002).
https: / / doi.org/ 10.1103 / PhysRevLett.88.170405

[25] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner. "Bell nonlocality". Pendeta Mod. Fisika. 86, 419–478 (2014).
https: / / doi.org/ 10.1103 / RevModPhys.86.419

[26] Dmitrijs Kravčenko. “Permainan Kuantum, Keadaan Kuantum, Sifat dan Penerapannya”. Tesis PhD. Universitas Latvijas. (2013).

[27] William Slofstra. “Batas bawah keterjeratan diperlukan untuk memainkan game XOR non-lokal”. Jurnal Fisika Matematika 52, 102202 (2011).
https: / / doi.org/ 10.1063 / 1.3652924

[28] Andris Ambainis, Jānis Iraids, Dmitry Kravchenko, dan Madars Virza. “Keuntungan strategi kuantum dalam permainan xor simetris acak”. Dalam Antonín Kučera, Thomas A. Henzinger, Jaroslav Nešetřil, Tomáš Vojnar, dan David Antoš, editor, Metode Matematika dan Teknik dalam Ilmu Komputer. Halaman 57–68. Berlin, Heidelberg (2013). Pegas Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-36046-6_7

[29] Andris Ambainis dan Janis Iraids. “Keuntungan yang Dapat Dibuktikan untuk Strategi Kuantum dalam Game XOR Simetris Acak”. Dalam Simone Severini dan Fernando Brandao, editor, Konferensi ke-8 Teori Komputasi Kuantum, Komunikasi dan Kriptografi (TQC 2013). Volume 22 dari Leibniz International Proceedings in Informatics (LIPIcs), halaman 146–156. Dagstuhl, Jerman (2013). Schloss Dagstuhl – Leibniz-Zentrum untuk Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2013.146

[30] Samuel Marcovitch dan Benni Reznik. “Implikasi kompleksitas komunikasi dalam sistem multipartit”. Fis. Pdt.A 77, 032120 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.032120

[31] Marcin Pawłowski, Tomasz Paterek, Dagomir Kaszlikowski, Valerio Scarani, Andreas Winter, and Marek Żukowski. "Kausalitas informasi sebagai prinsip fisik". Alam 461, 1101–1104 (2009).
https: / / doi.org/ 10.1038 / nature08400

[32] Sandu Popescu dan Daniel Rohrlich. "Nonlokalitas kuantum sebagai aksioma". Dasar Fisika 24, 379–385 (1994).
https: / / doi.org/ 10.1007 / BF02058098

[33] Jonathan Barrett, Noah Linden, Serge Massar, Stefano Pironio, Sandu Popescu, dan David Roberts. “Korelasi nonlokal sebagai sumber teori informasi”. Fis. Pdt.A 71, 022101 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.022101

[34] AA Razborov. “Kompleksitas komunikasi kuantum dari predikat simetris”. Izvestiya: Matematika 67, 145 (2003).
https://doi.org/10.1070/IM2003v067n01ABEH000422

[35] Zhiqiang Zhang dan Yaoyun Shi. “Kompleksitas komunikasi fungsi XOR simetris”. Informasi dan Komputasi Kuantum 9, 255–263 (2009). url: https:///dl.acm.org/doi/abs/10.5555/2011781.2011786.
https: / / dl.acm.org/ doi / abs / 10.5555 / 2011781.2011786

[36] Pierre Botteron. “Kotak NonLokal dan Kompleksitas Komunikasi”. tesis master. Universitas Paul Sabatier Toulouse III. (2022). url: https:///pierre-botteron.github.io/Articles/2022-06-MSc-Thesis.pdf.
https://pierre-botteron.github.io/Articles/2022-06-MSc-Thesis.pdf

[37] Kwangil Bae dan Wonmin Son. “Kriteria nonlokalitas umum di bawah simetri korelasi”. Fis. Pdt.A 98, 022116 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.022116

[38] Markus Frembs, Sam Roberts, dan Stephen D Bartlett. “Kontekstualitas sebagai sumber daya untuk komputasi kuantum berbasis pengukuran di luar qubit”. Jurnal Fisika Baru 20, 103011 (2018).
https: / / doi.org/ 10.1088 / 1367-2630 / aae3ad

[39] 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

[40] Daniel Grier dan Luke Schaeffer. “Sirkuit Clifford Dangkal Interaktif: Keuntungan Kuantum melawan NC¹ dan Selanjutnya”. Dalam Prosiding Simposium ACM SIGACT Tahunan ke-52 tentang Teori Komputasi. Halaman 875–888. STOC 2020New York, NY, AS (2020). Asosiasi Mesin Komputasi.
https: / / doi.org/ 10.1145 / 3357713.3384332

[41] Libor Caha, Xavier Coiteux-Roy, dan Robert Koenig. “Teleportasi gerbang qubit tunggal memberikan keuntungan kuantum” (2022). arXiv:2209.14158.
arXiv: 2209.14158

[42] Francois Le Gall. “Keunggulan Kuantum Kasus Rata-Rata dengan Sirkuit Dangkal”. Di Amir Shpilka, editor, Konferensi Kompleksitas Komputasi ke-34 (CCC 2019). Volume 137 Leibniz International Proceedings in Informatics (LIPIcs), halaman 21:1—-21:20. Dagstuhl, Jerman (2019). Schloss Dagstuhl–Leibniz-Zentrum Fuer Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2019.21

[43] Matthew Coudron, Jalex Stark, dan Thomas Vidick. “Perdagangan lokalitas dengan waktu: keacakan yang dapat disertifikasi dari sirkuit kedalaman rendah”. Komunikasi dalam fisika matematika 382, 49–86 (2021).
https: / / doi.org/ 10.1007 / s00220-021-03963-w

[44] Sergey Bravyi, David Gosset, Robert König, dan Marco Tomamichel. “Keuntungan kuantum dengan sirkuit dangkal yang bising”. Fisika Alam 16, 1040–1045 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

[45] Atsuya Hasegawa dan Francois Le Gall. “Keuntungan Kuantum dengan Sirkuit Dangkal di Bawah Korupsi Sewenang-wenang”. Dalam Hee-Kap Ahn dan Kunihiko Sadakane, editor, Simposium Internasional ke-32 tentang Algoritma dan Komputasi (ISAAC 2021). Volume 212 dari Leibniz International Proceedings in Informatics (LIPIcs), halaman 74:1–74:16. Dagstuhl, Jerman (2021). Schloss Dagstuhl – Leibniz-Zentrum untuk Informatik.
https:///doi.org/10.4230/LIPICs.ISAAC.2021.74

[46] Adam Bene Watts, Robin Kothari, Luke Schaeffer, dan Avishay Tal. “Pemisahan Eksponensial antara Sirkuit Kuantum Dangkal dan Sirkuit Klasik Dangkal Fan-in Tanpa Batas”. Dalam Prosiding Simposium ACM SIGACT Tahunan ke-51 tentang Teori Komputasi. Halaman 515–526. STOC 2019New York, NY, AS (2019). Asosiasi Mesin Komputasi.
https: / / doi.org/ 10.1145 / 3313276.3316404

[47] Natalie Parham. “Tentang Kekuatan dan Keterbatasan Sirkuit Kuantum Dangkal”. tesis master. Universitas Waterloo. (2022). url: https:///uwspace.uwaterloo.ca/handle/10012/18702.
https:///uwspace.uwaterloo.ca/handle/10012/18702

[48] Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J Yoder, dan Sarah Sheldon. “Keunggulan kuantum untuk komputasi dengan ruang terbatas”. Fisika Alam 17, 894–897 (2021).
https://doi.org/10.1038/s41567-021-01271-7

[49] Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore, dan Christopher Pollett. “Tentang kekuatan komputasi program percabangan probabilistik dan kuantum”. Informasi dan Komputasi 203, 145–162 (2005).
https: / / doi.org/ 10.1016 / j.ic.2005.04.003

[50] D Shepherd dan MJ Bremner. “Perhitungan kuantum yang tidak terstruktur untuk sementara”. Prosiding Royal Society of London Seri A 465, 1413–1439 (2009).
https: / / doi.org/ 10.1098 / rspa.2008.0443

[51] Daniel M Greenberger, Michael A Horne, dan Anton Zeilinger. “Melampaui Teorema Bell”. Dalam Menas Kafatos, editor, Teorema Bell, Teori Kuantum dan Konsepsi Alam Semesta. Halaman 69–72. Dordrecht (1989). Pegas Belanda.
https://doi.org/10.1007/978-94-017-0849-4_10

[52] Diogo Cruz, Romain Fournier, Fabien Gremion, Alix Jeannerot, Kenichi Komagata, Tara Tosic, Jarla Thiesbrummel, Chun Lam Chan, Nicolas Macris, Marc-André Dupertuis, dan Clément Javerzac-Galy. “Algoritma Kuantum yang Efisien untuk Status GHZ dan W, dan Implementasinya pada Komputer Kuantum IBM”. Teknologi Kuantum Tingkat Lanjut 2, 1900015 (2019).
https: / / doi.org/ 10.1002 / qute.201900015

[53] RF Werner dan MM Wolf. "Ketidaksetaraan korelasi lonceng semua multipartit untuk dua pengamatan dikotomis per situs". Fisika. Pdt. A 64, 032112 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.032112

[54] Ryan O'Donnell. “Analisis Fungsi Boolean”. Pers Universitas Cambridge. (2014). url: http://www.cs.cmu.edu/ ./odonnell/papers/Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf.
http://www.cs.cmu.edu/~./odonnell/papers/Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf

[55] Anastasiya Chistopolskaya dan Vladimir V. Podolskii. “Kompleksitas Pohon Keputusan Paritas Lebih Besar Dari Granularitas” (2018). arXiv:1810.08668.
arXiv: 1810.08668

[56] A Canteau dan M Videau. “Fungsi Boolean Simetris”. Transaksi IEEE pada Teori Informasi 51, 2791–2811 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.851743

[57] Larry J Stockmeyer. “Tentang kompleksitas kombinasi fungsi Boolean simetris tertentu”. Teori sistem matematika 10, 323–336 (1976).
https: / / doi.org/ 10.1007 / BF01683282

[58] RF Arnold dan MA Harrison. “Sifat Aljabar Fungsi Boolean Simetris dan Simetris Sebagian”. Transaksi IEEE pada Komputer Elektronik EC-12, 244–251 (1963).
https:///doi.org/10.1109/PGEC.1963.263535

[59] Braeken dan Bart Preneel. “Tentang kekebalan aljabar fungsi boolean simetris”. Dalam Subhamoy Maitra, CE Veni Madhavan, dan Ramarathnam Venkatesan, editor, Progress in Cryptology – INDOCRYPT 2005. Volume 3797 of Lecture Notes in Computer Science, halaman 35–48. Berlin, Heidelberg (2005). Pegas Berlin Heidelberg.
https: / / doi.org/ 10.1007 / 11596219_4

[60] Harry Buhrman dan Ronald de Wolf. “Ukuran kompleksitas dan kompleksitas pohon keputusan: survei”. Ilmu Komputer Teoritis 288, 21–43 (2002).
https://doi.org/10.1016/S0304-3975(01)00144-X

[61] Matthew Amy, Dmitri Maslov, Michele Mosca, dan Martin Roetteler. “Algoritma Pertemuan di Tengah untuk Sintesis Cepat Sirkuit Kuantum Kedalaman-Optimal”. Transaksi IEEE pada Desain Sirkuit dan Sistem Terpadu Berbantuan Komputer 32, 818–830 (2013).
https: / / doi.org/ 10.1109 / TCAD.2013.2244643

[62] VV Shende, SS Bullock, dan IL Markov. “Sintesis rangkaian logika kuantum”. Transaksi IEEE pada Desain Sirkuit dan Sistem Terpadu Berbantuan Komputer 25, 1000–1010 (2006).
https: / / doi.org/ 10.1109 / TCAD.2005.855930

[63] Juha J Vartiainen, Mikko Möttönen, dan Martti M Salomaa. “Dekomposisi Gerbang Kuantum yang Efisien”. Fis. Pendeta Lett. 92, 177902 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.92.177902

[64] Bei Zeng, Xie Chen, dan Isaac L Chuang. “Operasi semi-Clifford, struktur hierarki $mathcal{C}_{k}$, dan kompleksitas gerbang untuk komputasi kuantum yang toleran terhadap kesalahan”. Fis. Pdt.A 77, 042313 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.042313

[65] Gary J Mooney, Charles D Hill, dan Lloyd CL Hollenberg. “Sintesis gerbang qubit tunggal dengan biaya optimal dalam hierarki Clifford”. Kuantum 5, 396 (2021).
https://doi.org/10.22331/q-2021-02-15-396

[66] Nadish de Silva. “Teleportasi gerbang kuantum yang efisien dalam dimensi yang lebih tinggi”. Prosiding Royal Society A 477, 20200865 (2021).
https: / / doi.org/ 10.1098 / rspa.2020.0865

[67] Daniel Gottesman dan Isaac L Chuang. “Menunjukkan kelayakan komputasi kuantum universal menggunakan teleportasi dan operasi qubit tunggal”. Alam 402, 390–393 (1999).
https: / / doi.org/ 10.1038 / 46503

[68] Daniel Gottesman. “Representasi Komputer Kuantum Heisenberg” (1998). arXiv:quant-ph/9807006.
arXiv: quant-ph / 9807006

[69] Vadym Kliuchnikov, Dmitri Maslov, dan Michele Mosca. “Sintesis tepat yang cepat dan efisien dari kesatuan qubit tunggal yang dihasilkan oleh gerbang clifford dan t”. Info Kuantum. Hitung. 13, 607–630 (2013). url: https:///dl.acm.org/doi/abs/10.5555/2535649.2535653.
https: / / dl.acm.org/ doi / abs / 10.5555 / 2535649.2535653

[70] Nicolas Brunner, James Sharam, dan Tamás Vértesi. “Menguji struktur keterikatan multipartit dengan ketidaksetaraan lonceng”. Fis. Pendeta Lett. 108, 110501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.108.110501

[71] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, dan Thomas Vidick. “Permainan yang Menjerat Sulit untuk Didekati”. Jurnal SIAM tentang Komputasi 40, 848–877 (2011).
https: / / doi.org/ 10.1137 / 090751293

[72] Yihui Quek, Eneet Kaur, dan Mark M. Wilde. “Estimasi jejak multivariat dalam kedalaman kuantum konstan”. Kuantum 8, 1220 (2024).
https://doi.org/10.22331/q-2024-01-10-1220

[73] Peter Selinger. “Pendekatan Clifford+T yang Efisien untuk Operator Qubit Tunggal”. Info Kuantum. Hitung. 15, 159–180 (2015).

[74] Vadym Kliuchnikov, Dmitri Maslov, dan Michele Mosca. “Pendekatan Praktis Kesatuan Qubit Tunggal dengan Sirkuit Clifford dan T Quantum Qubit Tunggal”. Transaksi IEEE di Komputer 65, 161–172 (2016).
https: / / doi.org/ 10.1109 / TC.2015.2409842

[75] Neil J Ross. “Perkiraan Rotasi Z Bebas Ancilla-Gratis Ancilla yang Optimal”. Info Kuantum. Hitung. 15, 932–950 (2015). url: https:///dl.acm.org/doi/abs/10.5555/2871350.2871354.
https: / / dl.acm.org/ doi / abs / 10.5555 / 2871350.2871354

[76] Ethan Bernstein dan Umesh Vazirani. “Teori Kompleksitas Kuantum”. Dalam Prosiding Simposium ACM Tahunan Kedua Puluh Lima tentang Teori Komputasi. Halaman 11–20. STOC '93New York, NY, AS (1993). Asosiasi Mesin Komputasi.
https: / / doi.org/ 10.1145 / 167088.167097

[77] Alex Bocharov, Martin Roetteler, dan Krysta M Svore. “Sintesis sirkuit kuantum probabilistik yang efisien dengan fallback”. Fis. Pdt.A 91, 052317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.052317

[78] Alex Bocharov, Martin Roetteler, dan Krysta M Svore. “Sintesis Efisien dari Sirkuit Kuantum Berulang-Sampai-Sukses Universal”. Fis. Pendeta Lett. 114, 080502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.080502

[79] Ingo Wegener. “Kompleksitas Fungsi Boolean”. John Wiley $&$ Sons, Inc.Amerika Serikat (1987).

[80] Heribert Vollmer. “Pengantar Kompleksitas Sirkuit: Pendekatan Seragam”. Perusahaan Penerbitan Springer, Tergabung. (2010). edisi pertama. url: https:///link.springer.com/book/1/10.1007-978-3-662-03927.
https://link.springer.com/book/10.1007/978-3-662-03927-4

[81] R.Smolensk. “Metode Aljabar dalam Teori Batas Bawah Kompleksitas Rangkaian Boolean”. Dalam Prosiding Simposium ACM Tahunan Kesembilan Belas tentang Teori Komputasi. Halaman 77–82. STOC '87New York, NY, AS (1987). Asosiasi Mesin Komputasi.
https: / / doi.org/ 10.1145 / 28395.28404

[82] Jaikumar Radhakrishnan. “Batas yang lebih baik untuk rumus ambang batas”. Dalam [1991] Prosiding Simposium Tahunan ke-32 Yayasan Ilmu Komputer. Halaman 314–323. Masyarakat Komputer IEEE (1991).
https: / / doi.org/ 10.1109 / SFCS.1991.185384

[83] Michael J Fischer, Albert R Meyer, dan Michael S Paterson. “$Omega(Nlog n)$ Batas Bawah Panjang Rumus Boolean”. SIAM J. Komputasi. 11, 416–427 (1982).
https: / / doi.org/ 10.1137 / 0211033

[84] Sanjeev Arora dan Boaz Barak. “Kompleksitas Komputasi: Pendekatan Modern”. Pers Universitas Cambridge. Amerika Serikat (2009). edisi pertama. url: https:///dl.acm.org/doi/abs/1/10.5555.
https: / / dl.acm.org/ doi / abs / 10.5555 / 1540612

[85] Scott Aaronson. “Berapa Banyak Struktur yang Dibutuhkan untuk Percepatan Kuantum Besar?” (2022). arXiv:2209.06930.
arXiv: 2209.06930

[86] David A.Barrington. "Program percabangan ukuran polinomial dengan lebar terbatas mengenali dengan tepat bahasa-bahasa itu di NC1". Jurnal Ilmu Komputer dan Sistem 38, 150–164 (1989).
https://doi.org/10.1016/0022-0000(89)90037-8

[87] Scott Aaronson dan Alex Arkhipov. “Kompleksitas Komputasi Optik Linier”. Dalam Prosiding Simposium ACM Tahunan Keempat Puluh Ketiga tentang Teori Komputasi. Halaman 333–342. STOC '11New York, NY, AS (2011). Asosiasi Mesin Komputasi.
https: / / doi.org/ 10.1145 / 1993636.1993682

[88] Peter W Shor. “Algoritma Waktu Polinomial untuk Faktorisasi Prima dan Logaritma Diskrit pada Komputer Kuantum”. Kajian SIAM 41, 303–332 (1999).
https: / / doi.org/ 10.1137 / S0036144598347011

[89] Daniel R Simon. “Tentang Kekuatan Komputasi Kuantum”. Jurnal SIAM tentang Komputasi 26, 1474–1483 (1997).
https: / / doi.org/ 10.1137 / S0097539796298637

[90] Gilles Brassard, Harry Buhrman, Noah Linden, André Allan Méthot, Alain Tapp, dan Unger Falk. “Batasan Nonlokalitas di Dunia Mana Pun yang Kompleksitas Komunikasinya Tidak Sepele”. Fis. Pendeta Lett. 96, 250401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.96.250401

[91] Wim van Dam. “Konsekuensi yang tidak masuk akal dari nonlokalitas yang sangat kuat”. Komputasi Alami 12, 9–12 (2013).
https://doi.org/10.1007/s11047-012-9353-6

[92] Matthew Amy dan Michele Mosca. “Optimasi T-Count dan Kode Reed–Muller”. Transaksi IEEE pada Teori Informasi 65, 4771–4784 (2019).
https: / / doi.org/ 10.1109 / TIT.2019.2906374

[93] Peter Bürgisser, Michael Clausen, dan Mohammad A Shokrollahi. “Teori kompleksitas aljabar”. Volume 315. Sains & Media Bisnis Springer. (2013). url: https:///dl.acm.org/doi/abs/10.5555/1965416.
https: / / dl.acm.org/ doi / abs / 10.5555 / 1965416

[94] Guang Hao Low dan Isaac L. Chuang. "Simulasi hamiltonian optimal dengan pemrosesan sinyal kuantum". Fisika. Pendeta Lett. 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[95] Jeongwan Haah. “Dekomposisi Produk Fungsi Periodik dalam Pemrosesan Sinyal Kuantum”. Kuantum 3, 190 (2019).
https://doi.org/10.22331/q-2019-10-07-190

[96] Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, dan Avishay Tal. "Gelar vs. Derajat Perkiraan dan Implikasi Kuantum Teorema Sensitivitas Huang". Dalam Prosiding Simposium ACM SIGACT Tahunan ke-53 tentang Teori Komputasi. Halaman 1330–1342. STOC 2021New York, NY, AS (2021). Asosiasi Mesin Komputasi.
https: / / doi.org/ 10.1145 / 3406325.3451047

[97] Hao Huang. “Subgraf hiperkubus yang diinduksi dan bukti Dugaan Sensitivitas”. Sejarah Matematika 190, 949–955 (2019).
https: / / doi.org/ 10.4007 / annals.2019.190.3.6

[98] Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, dan Juris Smotrovs. “Pemisahan Kompleksitas Query Berdasarkan Fungsi Pointer”. J.ACM 64 (2017).
https: / / doi.org/ 10.1145 / 3106234

[99] Peter Høyer dan Robert Špalek. “Sirkuit kuantum dengan penyebaran tanpa batas”. Dalam Helmut Alt dan Michel Habib, editor, STACS 2003. Halaman 234–246. Berlin, Heidelberg (2003). Pegas Berlin Heidelberg.
https://doi.org/10.1007/3-540-36494-3_22

[100] Austin K Daniel, Yingyue Zhu, C Huerta Alderete, Vikas Buchemmavari, Alaina M Green, Nhung H Nguyen, Tyler G Thurtell, Andrew Zhao, Norbert M Linke, dan Akimasa Miyake. “Keunggulan komputasi kuantum dibuktikan oleh permainan nonlokal dengan status cluster siklik”. Fis. Penelitian Pdt 4, 033068 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033068

[101] Paul Herringer dan Robert Raussendorf. “Klasifikasi kawat kuantum berbasis pengukuran pada stabilizer PEPS”. Kuantum 7, 1041 (2023).
https://doi.org/10.22331/q-2023-06-12-1041

[102] Abhishek Anand. “Tentang kekuatan sirkuit kuantum dan klasik kedalaman rendah yang disisipkan”. tesis master. Universitas Waterloo. (2022). url: https:///uwspace.uwaterloo.ca/handle/10012/18805.
https:///uwspace.uwaterloo.ca/handle/10012/18805

[103] John Preskill. “Komputasi Kuantum di era NISQ dan seterusnya”. Kuantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[104] Bulent Demirel, Weikai Weng, Christopher Thalacker, Matty Hoban, dan Stefanie Barz. “Korelasi untuk komputasi dan komputasi untuk korelasi”. npj Informasi Kuantum 7, 1–8 (2021).
https://doi.org/10.1038/s41534-020-00354-2

[105] Manoranjan Swain, Amit Rai, Bikash K Behera, dan Prasanta K Panigrahi. “Demonstrasi eksperimental pelanggaran ketidaksetaraan Mermin dan Svetlichny di negara bagian W dan GHZ”. Pemrosesan Informasi Kuantum 18, 218 (2019).
https://doi.org/10.1007/s11128-019-2331-5

[106] Bo Yang, Rudy Raymond, Hiroshi Imai, Hyungseok Chang, dan Hidefumi Hiraishi. “Menguji ketidaksetaraan lonceng yang dapat diskalakan untuk status grafik kuantum pada perangkat kuantum ibm”. Jurnal IEEE tentang Topik yang Muncul dan Terpilih di Sirkuit dan Sistem 12, 638–647 (2022).
https:///doi.org/10.1109/JETCAS.2022.3201730

[107] F. Baccari, R. Augusiak, I. Šupić, J. Tura, dan A. Acín. “Ketidaksetaraan lonceng yang dapat diskalakan untuk status grafik qubit dan pengujian mandiri yang kuat”. Fis. Pendeta Lett. 124, 020402 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.124.020402

[108] Ken X Wei, Isaac Lauer, Srikanth Srinivasan, Neereja Sundaresan, Douglas T McClure, David Toyli, David C McKay, Jay M Gambetta, dan Sarah Sheldon. “Memverifikasi keadaan multipartit yang melibatkan Greenberger-Horne-Zeilinger melalui beberapa koherensi kuantum”. Fis. Pdt.A 101, 032343 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.032343

[109] Wei-Jia Huang, Wei-Chen Chien, Chien-Hung Cho, Che-Chun Huang, Tsung-Wei Huang, dan Ching-Ray Chang. “Ketidaksetaraan Mermin pada beberapa qubit dengan pengukuran ortogonal pada sistem IBM Q 53-qubit”. Rekayasa Kuantum 2, e45 (2020).
https:///doi.org/10.1002/que2.45

[110] Meron Sheffer, Daniel Azses, dan Emanuele G Dalla Torre. “Memainkan Game Quantum Nonlokal dengan Enam Qubit Bising di Cloud”. Teknologi Kuantum Tingkat Lanjut 5, 2100081 (2022).
https: / / doi.org/ 10.1002 / qute.202100081

[111] Vedran Dunjko, Theodoros Kapourniotis, dan Elham Kashefi. “Komputasi Klasik Terdelegasi Aman yang Ditingkatkan Kuantum”. Info Kuantum. Hitung. 16, 61–86 (2016).

[112] Stefanie Barz, Vedran Dunjko, Florian Schlederer, Merritt Moore, Elham Kashefi, dan Ian A. Walmsley. “Komputasi terdelegasi yang ditingkatkan menggunakan koherensi”. Fis. Pdt.A 93, 032339 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.032339

[113] Marco Clementi, Anna Pappa, Andreas Eckstein, Ian A Walmsley, Elham Kashefi, dan Stefanie Barz. “Komputasi multipartai klasik menggunakan sumber daya kuantum”. Tinjauan Fisik A 96, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062317

[114] Nasir Ahmed dan Kamisetty Ramamohan Rao. “Transformasi Walsh-hadamard”. Dalam transformasi Ortogonal untuk pemrosesan sinyal digital. Halaman 99–152. Pegas (1975).

[115] Michael A Nielsen dan Isaac L Chuang. “Komputasi Kuantum dan Informasi Kuantum: Edisi Hari Jadi ke-10”. Pers Universitas Cambridge. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

[116] Philip Feinsilver dan Jerzy Kocik. “Polinomial Krawtchouk dan matriks krawtchouk”. Halaman 115–141. Kemajuan Terkini dalam Probabilitas Terapan. Pegas AS. Boston, MA (2005).
https://doi.org/10.1007/0-387-23394-6_5

[117] Philip Feinsilver dan Rene Schott. “Krawtchouk bertransformasi dan berkonvolusi”. Buletin Ilmu MatematikaHalaman 1–19 (2018).
https://doi.org/10.1007/s13373-018-0132-2

[118] M. Stobińska, A. Buraczewski, M. Moore, WR Clements, JJ Renema, SW Nam, T. Gerrits, A. Lita, WS Kolthammer, A. Eckstein, dan IA Walmsley. “Interferensi kuantum memungkinkan pemrosesan informasi kuantum dalam waktu yang konstan”. Kemajuan Sains 5, eaau9674 (2019).
https:///doi.org/10.1126/sciadv.aau9674

[119] Ravindran Kannan dan Achim Bachem. “Algoritma Polinomial untuk Menghitung Bentuk Normal Smith dan Hermite dari Matriks Integer”. Jurnal SIAM tentang Komputasi 8, 499–507 (1979).
https: / / doi.org/ 10.1137 / 0208040

[120] Josh Alman dan Virginia Vassilevska Williams. “Metode laser yang disempurnakan dan penggandaan matriks yang lebih cepat”. Dalam Prosiding Simposium ACM-SIAM Tahunan Ketiga Puluh Kedua tentang Algoritma Diskrit. Halaman 522–539. SODA '21AS (2021). Masyarakat Matematika Industri dan Terapan.
https: / / doi.org/ 10.1137 / 1.9781611976465.32

Dikutip oleh

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.