Verifikasi Kasus Rata-Rata dari Transformasi Quantum Fourier Memungkinkan Estimasi Fase Kasus Terburuk Kecerdasan Data PlatoBlockchain. Pencarian Vertikal. Ai.

Verifikasi Kasus Rata-Rata dari Quantum Fourier Transform Memungkinkan Estimasi Fase Kasus Terburuk

Stempel Waktu: 7 Desember 2022 11:15

Nuh Linden1 dan Ronald de Wolf2

1Sekolah Matematika, Universitas Bristol. n.linden@bristol.ac.uk
2QuSoft, CWI dan University of Amsterdam, Belanda. rdewolf@cwi.nl

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

Abstrak

Transformasi Fourier kuantum (QFT) adalah kunci primitif untuk komputasi kuantum yang biasanya digunakan sebagai subrutin dalam komputasi yang lebih besar, misalnya untuk estimasi fase. Dengan demikian, kita mungkin memiliki sedikit kendali atas keadaan yang dimasukkan ke QFT. Jadi, dalam mengimplementasikan QFT yang baik, kita dapat membayangkan bahwa QFT perlu bekerja dengan baik pada status input arbitrer. $Memverifikasi$ perilaku terburuk implementasi QFT ini akan sulit secara eksponensial (dalam jumlah qubit) secara umum, meningkatkan kekhawatiran bahwa verifikasi ini tidak mungkin dilakukan dalam praktik pada sistem berukuran berguna apa pun. Dalam makalah ini kami menunjukkan bahwa, pada kenyataannya, kami hanya perlu memiliki kinerja QFT $rata-rata$-$kasus$ yang baik untuk mencapai kinerja $terburuk$-$kasus$ yang baik untuk tugas-tugas utama – estimasi fase, penemuan periode, dan estimasi amplitudo . Selanjutnya kami memberikan prosedur yang sangat efisien untuk memverifikasi perilaku kasus rata-rata yang diperlukan dari QFT ini.

Ringkasan populer

Transformasi Fourier kuantum (QFT) adalah kunci primitif yang biasanya digunakan sebagai subrutin dalam komputasi kuantum yang lebih besar. Dengan demikian, kita mungkin memiliki sedikit kendali atas keadaan yang dimasukkan ke QFT. Kami menunjukkan bahwa kinerja QFT yang baik pada status input $rata-rata$ (1) dapat diuji secara efisien, dan (2) cukup untuk mencapai kinerja $terburuk$-$kasus$ yang baik untuk tugas berbasis QFT seperti estimasi fase, penemuan periode dan estimasi amplitudo.

► data BibTeX

► Referensi

[1] Scott Aaronson dan Patrick Rall. Penghitungan perkiraan kuantum, disederhanakan. Dalam Prosiding Simposium ke-3 tentang Kesederhanaan dalam Algoritma (SOSA), halaman 24–32, 2020. arXiv:1908.10846.
https: / / doi.org/ 10.1137 / 1.9781611976014.5
arXiv: 1908.10846

[2] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, dan Umesh Vazirani. Kekuatan dan kelemahan komputasi kuantum. SIAM Journal on Computing, 26 (5): 1510-1523, 1997. quant-ph / 9701001.
https: / / doi.org/ 10.1137 / S0097539796300933
arXiv: quant-ph / 9701001

[3] Gilles Brassard, Peter Høyer, Michele Mosca, dan Alain Tapp. Amplifikasi dan estimasi amplitudo kuantum. Dalam Komputasi Kuantum dan Informasi Kuantum: Volume Milenium, volume 305 dari Seri Matematika Kontemporer AMS, halaman 53–74. 2002. quant-ph / 0005055.
https: / / doi.org/ 10.1090 / conm / 305/05215
arXiv: quant-ph / 0005055

[4] Chi-Fang Chen dan Fernando GSL Brandão. Konsentrasi untuk kesalahan Trotter. arXiv:2111.05324, 9 Nov 2021.
https://​/​doi.org/​10.48550/​arXiv.2111.05324
arXiv: 2111.05324

[5] Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Algoritma kuantum ditinjau kembali. Dalam Proceedings of the Royal Society of London, volume A454, halaman 339–354, 1998. quant-ph/​9708016.
https: / / doi.org/ 10.1098 / rspa.1998.0164
arXiv: quant-ph / 9708016

[6] Dan Tukang Tembaga. Perkiraan Transformasi Fourier berguna dalam pemfaktoran kuantum. Laporan Riset IBM No. RC19642, quant-ph/​0201067, 1994.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​0201067
arXiv: quant-ph / 0201067

[7] Marcus da Silva, Oliver Landon-Kardinal, dan David Poulin. Karakterisasi praktis perangkat kuantum tanpa tomografi. Surat Tinjauan Fisik, 107:210404, 2011. arXiv:1104.3835.
https: / / doi.org/ 10.1103 / PhysRevLett.107.210404
arXiv: 1104.3835

[8] Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi. Sertifikasi dan pembandingan kuantum. Ulasan Alam Fisika, 2:382–390, 2020. arXiv:1910.06343.
https:/​/​doi.org/​10.1038/​s42254-020-0186-4
arXiv: 1910.06343

[9] Steven T. Flammia dan Yi-Kai Liu. Estimasi ketepatan langsung dari beberapa pengukuran Pauli. Surat Tinjauan Fisik, 106:230501, 2011. arXiv:1104.4695.
https: / / doi.org/ 10.1103 / PhysRevLett.106.230501
arXiv: 1104.4695

[10] András Gilyén, Srinivasan Arunachalam, dan Nathan Wiebe. Mengoptimalkan algoritme pengoptimalan kuantum melalui perhitungan gradien kuantum yang lebih cepat. Dalam Prosiding SODA ACM-SIAM ke-30, halaman 1425–1444, 2019. arXiv:1711.00465.
https: / / doi.org/ 10.1137 / 1.9781611975482.87
arXiv: 1711.00465

[11] Lov K. Grover. Algoritma mekanika kuantum cepat untuk pencarian basis data. Dalam Prosiding 28th ACM STOC, halaman 212–219, 1996. quant-ph/​9605043.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: quant-ph / 9605043

[12] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Transformasi nilai singular kuantum dan seterusnya: peningkatan eksponensial untuk aritmatika matriks kuantum. Dalam Prosiding 51st ACM STOC, halaman 193–204, 2019. arXiv:1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838

[13] Stephen P.Jordan. Algoritma kuantum cepat untuk estimasi gradien numerik. Surat Tinjauan Fisik, 95:050501, 2005. quant-ph/​0405146.
https: / / doi.org/ 10.1103 / PhysRevLett.95.050501
arXiv: quant-ph / 0405146

[14] Alexei Yu. Kitaev. Pengukuran kuantum dan masalah stabilizer Abelian. quant-ph/​9511026, 12 Nov 1995.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9511026
arXiv: quant-ph / 9511026

[15] Noah Linden dan Ronald de Wolf. Deteksi ringan dari sejumlah kecil kesalahan besar di sirkuit kuantum. Quantum, 5(436), 2021.arXiv:2009.08840.
https:/​/​doi.org/​10.22331/​q-2021-04-20-436
arXiv: 2009.08840

[16] Urmila Mahadev. Verifikasi klasik perhitungan kuantum. Dalam Prosiding IEEE FOCS ke-59, halaman 259–267, 2018. arXiv:1804.01082.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
arXiv: 1804.01082

[17] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. Penyatuan besar algoritma kuantum. PRX Quantum, 2:040203, 2021.arXiv.2105.02859.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203

[18] Michael A. Nielsen dan Isaac L. Chuang. Komputasi Kuantum dan Informasi Kuantum. Pers Universitas Cambridge, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667

[19] Patrick Ral. Algoritme kuantum koheren yang lebih cepat untuk estimasi fase, energi, dan amplitudo. Quantum, 5(566), 2021. arXiv:2103.09717.
https:/​/​doi.org/​10.22331/​q-2021-10-19-566
arXiv: 2103.09717

[20] Peter W. Shor. Algoritme waktu polinomial untuk faktorisasi prima dan logaritma diskrit pada komputer kuantum. SIAM Journal on Computing, 26(5):1484–1509, 1997. Versi sebelumnya di FOCS'94. quant-ph/​9508027.
https: / / doi.org/ 10.1137 / S0097539795293172
arXiv: quant-ph / 9508027

[21] Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs. Simulasi Hamiltonian dengan input acak. arXiv:2111.04773, 8 Nov 2021.
https://​/​doi.org/​10.48550/​arXiv.2111.04773
arXiv: 2111.04773

Dikutip oleh

[1] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, dan Giacomo Nannicini, “Tomografi kuantum menggunakan kesatuan persiapan negara”, arXiv: 2207.08800.

Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2022-12-08 04:24:57). 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-12-08 04:24:56).

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.

Stempel Waktu:

Lebih dari Jurnal Kuantum