1Wydział Fizyki, ETH Zurych, Szwajcaria
2Instytut Studiów Teoretycznych, ETH Zurych, Szwajcaria
Czy ten artykuł jest interesujący czy chcesz dyskutować? Napisz lub zostaw komentarz do SciRate.
Abstrakcyjny
Dowód kwantowości to rodzaj protokołu wyzwanie-odpowiedź, w którym klasyczny weryfikator może skutecznie poświadczyć $textit{kwantową przewagę}$ niezaufanego dowodzącego. Oznacza to, że dowód kwantowy może poprawnie odpowiedzieć na wyzwania weryfikatora i zostać zaakceptowany, podczas gdy każdy klasyczny dowód wielomianowy zostanie odrzucony z dużym prawdopodobieństwem, w oparciu o wiarygodne założenia obliczeniowe. Aby odpowiedzieć na wyzwania weryfikatora, istniejące dowody kwantowości zwykle wymagają od dowodzenia kwantowego wykonania kombinacji obwodów kwantowych o wielkości wielomianu i pomiarów.
W tym artykule podajemy dwie konstrukcje dowodzące kwantowości, w których dowodzący musi wykonać tylko $textit{obwody kwantowe o stałej głębokości}$ (i pomiary) wraz z klasycznymi obliczeniami log-głębokości. Naszą pierwszą konstrukcją jest ogólny kompilator, który pozwala nam przetłumaczyć wszystkie istniejące dowody kwantowości na wersje o stałej głębokości kwantowej. Nasza druga konstrukcja opiera się na problemie $textit{uczenie się z zaokrąglaniem}$ i daje obwody o mniejszej głębokości i wymagające mniejszej liczby kubitów niż ogólna konstrukcja. Ponadto druga konstrukcja ma również pewną odporność na hałas.
► Dane BibTeX
► Referencje
[1] Scotta Aaronsona i Alexa Arkhipova. Złożoność obliczeniowa optyki liniowej. W Proceedings of the czterdziestego trzeciego dorocznego sympozjum ACM na temat teorii obliczeń, strony 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 i in. Supremacja kwantowa przy użyciu programowalnego procesora nadprzewodzącego. Przyroda, 574(7779):505–510, 2019.
https://doi.org/10.1038/s41586-019-1666-5
[3] MD SAJID ANIS, Abby-Mitchell, Héctor Abraham, AduOffei i in. Qiskit: platforma open-source do obliczeń kwantowych, 2021 r.
[4] Sanjeev Arora i Boaz Barak. Złożoność obliczeniowa: nowoczesne podejście. Wydawnictwo Uniwersytetu Cambridge, 2009.
[5] Scotta Aaronsona i Lijie Chen. Teoretyczne podstawy złożoności eksperymentów supremacji kwantowej . W Proceedings of the 32nd Computational Complexity Conference, CCC '17, strony 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
[6] Scotta Aaronsona i Sama Gunna. O klasycznej twardości fałszowania testów porównawczych z liniową krzyżową entropią. Teoria informatyki, 16(11):1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[7] B. Applebaum, Y. Ishai i E. Kushilevitz. Kryptografia w ${NC}^0$. W 45. dorocznym sympozjum IEEE na temat podstaw informatyki, strony 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak i Daniel Wichs. Nauka z zaokrąglaniem, powtórka. W Advances in Cryptology – CRYPTO 2013, strony 57–74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] Davida Barringtona. Programy rozgałęziające o wielkości wielomianu o ograniczonej szerokości rozpoznają dokładnie te języki w ${NC}^1$. Journal of Computer and System Sciences, 38 (1): 150–164, 1989.
https://doi.org/10.1016/0022-0000(89)90037-8
[10] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani i Thomas Vidick. Kryptograficzny test kwantowości i certyfikowanej losowości z jednego urządzenia kwantowego. W 2018 r. IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), strony 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell i Jeremy M. Sage. Obliczenia kwantowe z uwięzionymi jonami: postęp i wyzwania. Recenzje fizyki stosowanej, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe i Umesh Vazirani. O złożoności i weryfikacji kwantowego próbkowania obwodów losowych. Nature Physics, 15(2):159–163, luty 2019 r.
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 i Hartmut Neven. Charakterystyka supremacji kwantowej w urządzeniach krótkoterminowych. Fizyka przyrody, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani i Thomas Vidick. Prostsze dowody kwantowości. W 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), tom 158 Leibniz International Proceedings in Informatics (LIPIcs), strony 8:1–8:14, Dagstuhl, Niemcy, 2020. Schloss Dagstuhl–Leibniz- Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert i Alon Rosen. Funkcje pseudolosowe i kraty. W Advances in Cryptology – EUROCRYPT 2012, strony 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 i Richard A Holt. Proponowany eksperyment mający na celu przetestowanie lokalnych teorii zmiennych ukrytych. Listy przeglądu fizycznego, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark i Thomas Vidick. Lokalizacja handlu na czas: certyfikowana losowość z obwodów o małej głębokości. Komunikacja w fizyce matematycznej, 382 (1): 49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] Richarda Cleve'a i Johna Watrousa. Szybkie obwody równoległe dla kwantowej transformaty Fouriera. W Proceedings 41. doroczne sympozjum na temat podstaw informatyki, strony 526–536. IEEE, 2000.
https: / / doi.org/ 10.1109 / SFCS.2000.892140
[19] Pierre'a Dusarta. Autour de la fonction qui compte le nombre de nombres premiers. Praca doktorska, Université de Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Austin G. Fowler, Matteo Mariantoni, John M. Martinis i Andrew N. Cleland. Kody powierzchni: w kierunku praktycznych obliczeń kwantowych na dużą skalę. Przegląd fizyczny A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] Franciszka Le Galla. Prywatna korespondencja, 2022.
[22] Craiga Gidneya i Martina Ekerå. Jak rozłożyć 2048-bitowe liczby całkowite RSA w ciągu 8 godzin przy użyciu 20 milionów hałaśliwych kubitów. Quantum, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu i Matty'ego J. Hobana. Oszacowanie entropii wyjść płytkich obwodów jest trudne. arXiv preprint arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara i Francois Le Gall. Test kwantowości za pomocą obwodów kwantowych o małej głębokości. W 46. Międzynarodowym Sympozjum na temat matematycznych podstaw informatyki (MFCS 2021), tom 202 Leibniz International Proceedings in Informatics (LIPIcs), strony 59:1–59:15, Dagstuhl, Niemcy, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] Arama W. Harrowa i Ashleya Montanaro. Kwantowa dominacja obliczeniowa. Przyroda, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] Petera Høyera i Roberta Špalka. Quantum Fan-out jest potężny. Teoria informatyki, 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 i Jianxin Chen. Klasyczna symulacja obwodów supremacji kwantowej. arXiv preprint arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D. Kahanamoku-Meyer. Fałszowanie danych kwantowych: klasyczne pokonanie testu kwantowego opartego na IQP. arXiv preprint 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 i Norman Y. Yao. Klasycznie weryfikowalna przewaga kwantowa z obliczeniowego testu Bella. Fizyka przyrody, 18 (8): 918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Lyubashevsky, Chris Peikert i Oded Regev. O sieciach idealnych i uczeniu się z błędami na pierścieniach. W dorocznej międzynarodowej konferencji na temat teorii i zastosowań technik kryptograficznych, strony 1–23. Springera, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Urmiła Mahadewa. Klasyczna weryfikacja obliczeń kwantowych. W 2018 r. IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), strony 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[32] Michael A Nielsen i Izaak Chuang. Obliczenia kwantowe i informacja kwantowa, 2002.
[33] AS Popowa i AN Rubcow. Złamanie progu przewagi kwantowej dla próbkowania bozonu gaussowskiego. W Konferencja i wystawa Quantum 2.0, strona QW2A.15. Grupa Wydawnicza Optica, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] Johna Preskilla. Obliczenia kwantowe w erze NISQ i później. Kwant, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michał O Rabin. Algorytm probabilistyczny do testowania pierwszości. Journal of Number Theory, 12 (1): 128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. O kratach, uczeniu się z błędami, losowych kodach liniowych i kryptografii. Dziennik ACM (JACM), 56 (6): 1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[37] Dana Shepherda i Michaela J. Bremnera. Czasowo nieustrukturyzowane obliczenia kwantowe. Proceedings of Royal Society A: Nauki matematyczne, fizyczne i inżynierskie, 465 (2105): 1413–1439, 2009.
https: / / doi.org/ 10.1098 / rspa.2008.0443
[38] Piotr W Szor. Algorytmy obliczeń kwantowych: logarytmy dyskretne i faktoring. W Proceedings 35. doroczne sympozjum poświęcone podstawom informatyki, strony 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 i Jian-Wei Pan. Silna przewaga obliczeń kwantowych przy użyciu nadprzewodzącego procesora kwantowego. fizyka Wielebny 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 i in. Test porównawczy 11-kubitowego komputera kwantowego. Komunikaty przyrodnicze, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Kwantowe przetwarzanie informacji za pomocą obwodów nadprzewodzących: przegląd. Raporty o postępach w fizyce, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] Adam Bene Watts, Robin Kothari, Luke Schaeffer i Avishay Tal. Separacja wykładnicza między płytkimi obwodami kwantowymi a nieograniczonymi płytkimi obwodami klasycznymi. W Proceedings of 51. Annual ACM SIGACT Symposium on Theory of Computing, strony 515–526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
[43] Andrew Chi-Chih Yao. Jak generować i wymieniać sekrety. W 27. dorocznym sympozjum na temat podstaw informatyki (sfcs 1986), strony 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, On -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 i Jian-Wei Pan. Kwantowa przewaga obliczeniowa dzięki losowemu próbkowaniu obwodu 60 kubitów w 24 cyklach. Biuletyn Naukowy, 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 i Christopher Monroe. Interaktywne protokoły dla klasycznie weryfikowalnej przewagi kwantowej. arXiv preprint 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 i Jian-Wei Pan. Kwantowa przewaga obliczeniowa przy użyciu fotonów. Nauka, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Cytowany przez
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath i Ruben Verresen, „Hierarchia porządku topologicznego od jednostek o skończonej głębokości, pomiar i sprzężenie zwrotne”, arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch i Robert Koenig, „Adaptacyjne obwody o stałej głębokości do manipulowania nieabelowymi anyonami”, 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 i Christopher Monroe, „Interaktywne protokoły dla klasycznie weryfikowalnej przewagi kwantowej”, arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo i Dmitriy Vassilyev, „Specyficzne dla gwiazd kluczowe homomorficzne PRF z regresji liniowej i teorii zbiorów ekstremalnych”, arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani i Norman Y. Yao, „Klasycznie weryfikowalna przewaga kwantowa z obliczeniowego testu Bella”, Fizyka natury 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn i Avishay Tal, „On Certified Randomness from Quantum Advantage Experiments”, arXiv: 2111.14846.
[7] Nai-Hui Chia i Shih-Han Hung, „Klasyczna weryfikacja głębi kwantowej”, arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa i Seiichiro Tani, „Obliczeniowe samotestowanie splątanych stanów magicznych”, Przegląd fizyczny A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde i Eneet Kaur, „Wielowymiarowa estymacja śladu w stałej głębokości kwantowej”, arXiv: 2206.15405.
Powyższe cytaty pochodzą z Reklamy SAO / NASA (ostatnia aktualizacja pomyślnie 2022-09-21 12:16:02). Lista może być niekompletna, ponieważ nie wszyscy wydawcy podają odpowiednie i pełne dane cytowania.
On Serwis cytowany przez Crossref nie znaleziono danych na temat cytowania prac (ostatnia próba 2022-09-21 12:16:00).
Niniejszy artykuł opublikowano w Quantum pod Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0) licencja. Prawa autorskie należą do pierwotnych właścicieli praw autorskich, takich jak autorzy lub ich instytucje.
