1Fizik Bölümü, ETH Zürih, İsviçre
2Teorik Araştırmalar Enstitüsü, ETH Zürih, İsviçre
Bu makaleyi ilginç mi buldunuz yoksa tartışmak mı istiyorsunuz? SciRate'e çığlık at veya yorum bırak.
Özet
Bir kuantumluk kanıtı, klasik bir doğrulayıcının güvenilmeyen bir kanıtlayıcının $textit{kuantum avantajını}$ verimli bir şekilde onaylayabildiği bir tür sorgulama-yanıt protokolüdür. Yani, bir kuantum ispatlayıcı, doğrulayıcının zorluklarını doğru bir şekilde yanıtlayabilir ve kabul edilebilirken, herhangi bir polinom zamanlı klasik ispatlayıcı, makul hesaplama varsayımlarına dayalı olarak yüksek olasılıkla reddedilecektir. Doğrulayıcının zorluklarını yanıtlamak için, mevcut kuantum kanıtları tipik olarak kuantum kanıtlayıcının polinom boyutlu kuantum devreleri ve ölçümlerinin bir kombinasyonunu gerçekleştirmesini gerektirir.
Bu yazıda, ispatlayıcının log-derinlikli klasik hesaplama ile birlikte sadece $textit{sabit-derinlikli kuantum devreleri}$ (ve ölçümleri) gerçekleştirmesi gereken iki kuantumluk yapısının ispatını veriyoruz. İlk yapımız, mevcut tüm kuantum kanıtlarını sabit kuantum derinliği sürümlerine çevirmemize izin veren genel bir derleyicidir. İkinci yapımız $textit{yuvarlayarak öğrenme}$ problemine dayanıyor ve genel yapıya göre daha kısa derinlikte ve daha az kübit gerektiren devreler veriyor. Ek olarak, ikinci konstrüksiyon da gürültüye karşı bir miktar sağlamlığa sahiptir.
► BibTeX verileri
► Referanslar
[1] Scott Aaronson ve Alex Arkhipov. Doğrusal optiğin hesaplama karmaşıklığı. Bilgisayar Teorisi üzerine kırk üçüncü yıllık ACM sempozyumunun Bildirilerinde, sayfa 333-342, 2011.
https: / / doi.org/ 10.1145 / 1993636.1993682
[2] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Programlanabilir bir süper iletken işlemci kullanarak kuantum üstünlüğü. Doğa, 574(7779):505–510, 2019.
https://doi.org/10.1038/s41586-019-1666-5
[3] MD SAJID ANIS, Abby-Mitchell, Héctor Abraham, AduOffei, et al. Qiskit: Kuantum hesaplama için açık kaynaklı bir çerçeve, 2021.
[4] Sanjeev Arora ve Boaz Barak. Hesaplamalı karmaşıklık: modern bir yaklaşım. Cambridge Üniversitesi Yayınları, 2009.
[5] Scott Aaronson ve Lijie Chen. Kuantum Üstünlük Deneylerinin Karmaşıklık-Teorik Temelleri. Proceedings of the 32nd Computational Complexity Conference, CCC '17, sayfa 1-67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https://doi.org/10.48550/arXiv.1612.05903
[6] Scott Aaronson ve Sam Gunn. Yanıltıcı Doğrusal Çapraz Entropi Kıyaslamanın Klasik Sertliği Üzerine. Hesaplama Teorisi, 16(11)::1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[7] B. Applebaum, Y. Ishai ve E. Kushilevitz. ${NC}^0$ cinsinden şifreleme. Bilgisayar Biliminin Temelleri üzerine 45. Yıllık IEEE Sempozyumu, sayfa 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak ve Daniel Wichs. Yuvarlama ile Öğrenme, Tekrar Ziyaret Edildi. Advances in Cryptology – CRYPTO 2013, sayfa 57–74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] David A Barrington. Sınırlı genişlikte polinom boyutlu dallara ayırma programları tam olarak ${NC}^1$ içindeki bu dilleri tanır. Bilgisayar ve Sistem Bilimleri Dergisi, 38(1):150-164, 1989.
https://doi.org/10.1016/0022-0000(89)90037-8
[10] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani ve Thomas Vidick. Tek bir kuantum cihazından bir kriptografik kuantum ve onaylanabilir rastgelelik testi. 2018'de IEEE 59. Yıllık Bilgisayar Bilimi Temelleri Sempozyumu (FOCS), sayfa 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell ve Jeremy M. Sage. Kapana kısılmış iyon kuantum hesaplama: İlerleme ve zorluklar. Uygulamalı Fizik İncelemeleri, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe ve Umesh Vazirani. Kuantum rastgele devre örneklemesinin karmaşıklığı ve doğrulanması üzerine. Doğa Fiziği, 15(2):159-163, Şubat 2019.
https://doi.org/10.1038/s41567-018-0318-2
[13] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis ve Hartmut Neven. Yakın vadeli cihazlarda kuantum üstünlüğünü karakterize etmek. Doğa Fiziği, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani ve Thomas Vidick. Kuantumun Daha Basit Kanıtları. Kuantum Hesaplama, İletişim ve Kriptografi Teorisi üzerine 15. Konferansta (TQC 2020), Leibniz International Proceedings in Informatics (LIPIcs), sayfa 158:8–1:8, Dagstuhl, Almanya, 14. Schloss Dagstuhl–Leibniz- Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert ve Alon Rosen. Sözde Rastgele Fonksiyonlar ve Kafesler. Advances in Cryptology – EUROCRYPT 2012, sayfa 719-737. Springer Berlin Heidelberg, 2012.
https://doi.org/10.1007/978-3-642-29011-4_42
[16] John F Clauser, Michael A Horne, Abner Shimony ve Richard A Holt. Yerel gizli değişken teorilerini test etmek için önerilen deney. Fiziksel İnceleme Mektupları, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark ve Thomas Vidick. Zaman için ticaret yeri: düşük derinlikli devrelerden onaylanabilir rastgelelik. Matematiksel Fizikte İletişim, 382(1):49–86, 2021.
HTTPS: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] Richard Cleve ve John Watrous. Kuantum Fourier dönüşümü için hızlı paralel devreler. Proceedings 41. Yıllık Bilgisayar Biliminin Temelleri Sempozyumu'nda, sayfa 526-536. IEEE, 2000.
https: / / doi.org/ 10.1109 / SFCS.2000.892140
[19] Pierre Dusart. En iyi seçimler. Doktora tezi, Université de Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Austin G Fowler, Matteo Mariantoni, John M Martinis ve Andrew N Cleland. Yüzey kodları: Pratik büyük ölçekli kuantum hesaplamaya doğru. Fiziksel İnceleme A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] François Le Gall. Özel yazışmalar, 2022.
[22] Craig Gidney ve Martin Ekerå. 2048 milyon gürültülü kübit kullanarak 8 bit RSA tamsayılarını 20 saatte çarpanlarına ayırma. Kuantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu ve Matty J Hoban. Sığ devre çıkışlarının entropisini tahmin etmek zordur. arXiv ön baskı arXiv:2002.12814, 2020.
https://doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara ve François Le Gall. Küçük Derinlikli Kuantum Devreleri ile Kuantum Testi. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), Leibniz International Proceedings in Informatics (LIPIcs) cilt 202, sayfa 59:1–59:15, Dagstuhl, Almanya, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] Aram W Harrow ve Ashley Montanaro. Kuantum hesaplama üstünlüğü. Doğa, 549(7671):203-209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] Peter Höyer ve Robert Špalek. Kuantum Yayılımı Güçlüdür. Hesaplama Teorisi, 1(5):81–103, 2005.
https: / / doi.org/ 10.4086 / toc.2005.v001a005
[27] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi ve Jianxin Chen. Kuantum Üstünlük Devrelerinin Klasik Simülasyonu. arXiv ön baskı arXiv:2005.06787, 2020.
https://doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Kuantum verilerini biçimlendirme: Klasik olarak IQP tabanlı bir kuantum testini yenmek. arXiv ön baskı arXiv:1912.05547, 2019.
https://doi.org/10.48550/arXiv.1912.05547
arXiv: 1912.05547
[29] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani ve Norman Y. Yao. Hesaplamalı bir Bell testinden klasik olarak doğrulanabilir kuantum avantajı. Doğa Fiziği, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Lyubashevsky, Chris Peikert ve Oded Regev. İdeal kafesler ve halkalar üzerinde hatalarla öğrenme. Yıllık Uluslararası Konferansta, Kriptografik Tekniklerin Teorisi ve Uygulamaları, sayfa 1-23. Springer, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Urmila Mahadev. Kuantum hesaplamalarının klasik doğrulaması. 2018'de IEEE 59. Yıllık Bilgisayar Bilimi Temelleri Sempozyumu (FOCS), sayfa 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[32] Michael A Nielsen ve Isaac Chuang. Kuantum hesaplama ve kuantum bilgisi, 2002.
[33] AS Popova ve AN Rubtsov. Gauss Bozonu Örneklemesi için Kuantum Avantaj Eşiğini Kırmak. Quantum 2.0 Konferans ve Sergisinde, sayfa QW2A.15. Optica Yayın Grubu, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] John Preskill. NISQ çağında ve ötesinde Kuantum Hesaplama. Kuantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Asallığı test etmek için olasılıksal algoritma. Sayı Teorisi Dergisi, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. Kafesler, hatalarla öğrenme, rastgele doğrusal kodlar ve kriptografi. ACM Dergisi (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[37] Dan Shepherd ve Michael J Bremner. Geçici olarak yapılandırılmamış kuantum hesaplama. Proceedings of the Royal Society A: Matematik, Fizik ve Mühendislik Bilimleri, 465(2105):1413–1439, 2009.
https: / / doi.org/ 10.1098 / rspa.2008.0443
[38] Peter W Shor. Kuantum hesaplama için algoritmalar: ayrık logaritmalar ve çarpanlara ayırma. Bildiriler kitabında bilgisayar biliminin temelleri üzerine 35. yıllık sempozyum, sayfa 124-134. IEEE, 1994.
https: / / doi.org/ 10.1109 / SFCS.1994.365700
[39] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han , Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao , Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu ve Jian-Wei Pan. Süper İletken Kuantum İşlemci Kullanan Güçlü Kuantum Hesaplama Avantajı. Fizik Rev. Lett., 127:180501, 2021.
https: / / doi.org/ 10.1103 / PhysRevLett.127.180501
[40] K Wright, KM Beck, Sea Debnath, JM Amini, Y Nam, N Grzesiak, JS Chen, NC Pisenti, M Chmielewski, C Collins, et al. 11 kübitlik bir kuantum bilgisayarı kıyaslama. Doğa iletişimi, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Süper iletken devrelerle kuantum bilgi işleme: bir inceleme. Fizikte İlerleme Raporları, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] Adam Bene Watts, Robin Kothari, Luke Schaeffer ve Avishay Tal. Sığ kuantum devreleri ve sınırsız fanlı sığ klasik devreler arasında üstel ayrım. Hesaplama Teorisi üzerine 51. Yıllık ACM SIGACT Sempozyumu Bildiriler Kitabında, sayfa 515-526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
[43] Andrew Chi Chih Yao. Sırlar nasıl oluşturulur ve değiştirilir. 27. Yıllık Bilgisayar Biliminin Temelleri Sempozyumu'nda (sfcs 1986), sayfa 162–167. IEEE, 1986.
https: / / doi.org/ 10.1109 / SFCS.1986.25
[44] Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He -Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang , Dachao Wu, Yulin Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu ve Jian-Wei Pan. 60-qubit 24 döngülü rastgele devre örneklemesi yoluyla kuantum hesaplama avantajı. Bilim Bülteni, 67(3):240–245, 2022.
https: / / doi.org/ 10.1016 / j.scib.2021.10.017
[45] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidick, Umesh Vazirani, Norman Y. Yao, Marko Cetina ve Christopher Monroe. Klasik Olarak Doğrulanabilir Kuantum Avantajı için Etkileşimli Protokoller. arXiv ön baskı arXiv:2112.05156, 2021.
https://doi.org/10.48550/arXiv.2112.05156
arXiv: 2112.05156
[46] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei- Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu ve Jian-Wei Pan. Fotonları kullanarak kuantum hesaplama avantajı. Bilim, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Alıntılama
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath ve Ruben Verresen, “Sonlu derinlikli ünitelerden topolojik düzen hiyerarşisi, ölçüm ve ileri besleme”, arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch ve Robert Koenig, “Abelyan olmayan herkesi manipüle etmek için uyarlanabilir sabit derinlikli devreler”, arXiv: 2205.01933.
[3] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidick, Umesh Vazirani, Norman Y. Yao, Marko Cetina ve Christopher Monroe, “Klasik olarak Doğrulanabilir Kuantum Avantajı için Etkileşimli Protokoller”, arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo ve Dmitriy Vassilyev, “Linear Regresyon ve Aşırı Küme Teorisinden Yıldıza Özgü Anahtar Homomorfik PRF'ler”, arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani ve Norman Y. Yao, “Hesaplamalı Bell testinden klasik olarak doğrulanabilir kuantum avantajı”, Doğa Fiziği 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn ve Avishay Tal, “On Certified Randomness from Quantum Advantage Experiments”, arXiv: 2111.14846.
[7] Nai-Hui Chia ve Shih-Han Hung, “Kuantum derinliğinin klasik doğrulaması”, arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa ve Seiichiro Tani, “Dolaşık sihirli durumlar için hesaplamalı kendi kendini test etme”, Fiziksel İnceleme A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde ve Eneet Kaur, “Sabit kuantum derinliğinde çok değişkenli iz tahmini”, arXiv: 2206.15405.
Yukarıdaki alıntılar SAO / NASA REKLAMLARI (son başarıyla 2022-09-21 12:16:02) güncellendi. Tüm yayıncılar uygun ve eksiksiz alıntı verisi sağlamadığından liste eksik olabilir.
On Crossref'in alıntı yaptığı hizmet alıntı yapma çalışmaları ile ilgili veri bulunamadı (son deneme 2022-09-21 12:16:00).
Bu Makale, Quantum'da Creative Commons Atıf 4.0 Uluslararası (CC BY 4.0) lisans. Telif hakkı, yazarlar veya kurumları gibi orijinal telif hakkı sahiplerine aittir.
