1Dipartimento di Fisica, ETH Zurigo, Svizzera
2Istituto di studi teorici, ETH Zurigo, Svizzera
Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.
Astratto
Una prova di quanticità è un tipo di protocollo sfida-risposta in cui un verificatore classico può certificare in modo efficiente il $textit{vantaggio quantistico}$ di un dimostratore non affidabile. Cioè, un dimostratore quantistico può rispondere correttamente alle sfide del verificatore ed essere accettato, mentre qualsiasi dimostratore classico in tempo polinomiale verrà rifiutato con alta probabilità, sulla base di ipotesi computazionali plausibili. Per rispondere alle sfide del verificatore, le prove esistenti della quantistica richiedono in genere che il dimostratore quantistico esegua una combinazione di circuiti quantistici e misurazioni di dimensioni polinomiali.
In questo articolo, forniamo due dimostrazioni di costruzioni quantistiche in cui il dimostratore deve solo eseguire $textit{circuiti quantistici a profondità costante}$ (e misurazioni) insieme al calcolo classico a profondità logaritmica. La nostra prima costruzione è un compilatore generico che ci consente di tradurre tutte le prove esistenti della quantistica in versioni a profondità quantistica costante. La nostra seconda costruzione si basa sul problema $textit{learning with rounding}$ e produce circuiti con profondità minore e che richiedono meno qubit rispetto alla costruzione generica. Inoltre, anche la seconda costruzione presenta una certa robustezza contro il rumore.
► dati BibTeX
► Riferimenti
, Scott Aaronson e Alex Arkhipov. La complessità computazionale dell'ottica lineare. In Atti del quarantatreesimo simposio annuale ACM sulla teoria dell'informatica, pagine 333–342, 2011.
https: / / doi.org/ 10.1145 / 1993636.1993682 mila
, 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. Supremazia quantistica utilizzando un processore superconduttore programmabile. Natura, 574(7779):505–510, 2019.
https://doi.org/10.1038/s41586-019-1666-5
, MD SAJID ANIS, Abby-Mitchell, Héctor Abraham, AduOffei, et al. Qiskit: un framework open source per l'informatica quantistica, 2021.
, Sanjeev Arora e Boaz Barak. Complessità computazionale: un approccio moderno. Cambridge University Press, 2009.
, Scott Aaronson e Lijie Chen. Fondamenti teorici della complessità degli esperimenti di supremazia quantistica. In Atti della 32a conferenza sulla complessità computazionale, CCC ’17, pagine 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
, Scott Aaronson e Sam Gunn. Sulla classica durezza dello spoofing Benchmarking lineare incrociato di entropia. Teoria dell'informatica, 16(11):1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
, B. Applebaum, Y. Ishai e E. Kushilevitz. Crittografia in ${NC}^0$. Nel 45esimo Simposio annuale dell'IEEE sui fondamenti dell'informatica, pagine 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
, Joël Alwen, Stephan Krenn, Krzysztof Pietrzak e Daniel Wichs. Imparare con arrotondamento, rivisitato. In Advances in Cryptology – CRYPTO 2013, pagine 57–74, Berlino, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
, David A Barrington. I programmi di ramificazione di dimensione polinomiale a larghezza limitata riconoscono esattamente quelle lingue in ${NC}^1$. Giornale di scienze informatiche e di sistema, 38(1):150–164, 1989.
https://doi.org/10.1016/0022-0000(89)90037-8
, Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani e Thomas Vidick. Un test crittografico di quanticità e casualità certificabile da un singolo dispositivo quantistico. Nel 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pagine 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309 mila
, Colin D. Bruzewicz, John Chiaverini, Robert McConnell e Jeremy M. Sage. Calcolo quantistico a ioni intrappolati: progressi e sfide. Recensioni di fisica applicata, 2019.
https: / / doi.org/ 10.1063 / 1.5088164 mila
, Adam Bouland, Bill Fefferman, Chinmay Nirkhe e Umesh Vazirani. Sulla complessità e verifica del campionamento circuitale casuale quantistico. Nature Physics, 15(2):159–163, febbraio 2019.
https://doi.org/10.1038/s41567-018-0318-2
, Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis e Hartmut Neven. Caratterizzazione della supremazia quantistica nei dispositivi a breve termine. Fisica della natura, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
, Zvika Brakerski, Venkata Koppula, Umesh Vazirani e Thomas Vidick. Dimostrazioni più semplici della quantistica. Nella 15a conferenza sulla teoria del calcolo quantistico, della comunicazione e della crittografia (TQC 2020), volume 158 di Leibniz International Proceedings in Informatics (LIPIcs), pagine 8:1–8:14, Dagstuhl, Germania, 2020. Schloss Dagstuhl–Leibniz- Centro informatico.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
, Abhishek Banerjee, Chris Peikert e Alon Rosen. Funzioni e reticoli pseudocasuali. In Advances in Cryptology – EUROCRYPT 2012, pagine 719–737. Springer Berlino Heidelberg, 2012.
https://doi.org/10.1007/978-3-642-29011-4_42
, John F Clauser, Michael A Horne, Abner Shimony e Richard A Holt. Esperimento proposto per testare le teorie locali delle variabili nascoste. Lettere di revisione fisica, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
, Matthew Coudron, Jalex Stark e Thomas Vidick. Località di scambio per tempo: casualità certificabile da circuiti a bassa profondità. Comunicazioni in fisica matematica, 382(1):49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
, Richard Cleve e John Watrous. Circuiti paralleli veloci per la trasformata quantistica di Fourier. Negli Atti del 41° Simposio annuale sui fondamenti dell'informatica, pagine 526–536. IEEE, 2000.
https: / / doi.org/ 10.1109 / SFCS.2000.892140
, Pierre Dusart. Autour de la fonction qui compte le nombre de nombres premiers. Tesi di dottorato, Université de Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
, Austin G Fowler, Matteo Mariantoni, John M Martinis e Andrew N Cleland. Codici di superficie: verso il calcolo quantistico pratico su larga scala. Revisione fisica A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
, François Le Gall. Corrispondenza privata, 2022.
, Craig Gidney e Martin Ekerå. Come fattorizzare interi RSA a 2048 bit in 8 ore utilizzando 20 milioni di qubit rumorosi. Quantistici, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
, Alexandru Gheorghiu e Matty J Hoban. Stimare l'entropia delle uscite di circuiti poco profondi è difficile. prestampa di arXiv arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
, Shuichi Hirahara e François Le Gall. Test della quanticità con circuiti quantistici di piccola profondità. Nel 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 di Leibniz International Proceedings in Informatics (LIPIcs), pagine 59:1–59:15, Dagstuhl, Germania, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
, Aram W Harrow e Ashley Montanaro. Supremazia computazionale quantistica. Natura, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
, Peter Høyer e Robert Špalek. Il fan-out quantistico è potente. Teoria dell'informatica, 1(5):81–103, 2005.
https: / / doi.org/ 10.4086 / toc.2005.v001a005
, Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi e Jianxin Chen. Simulazione classica dei circuiti di supremazia quantistica. prestampa di arXiv arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
, Gregory D Kahanamoku-Meyer. Forgiare dati quantistici: sconfiggere in modo classico un test quantistico basato su IQP. prestampa di arXiv arXiv:1912.05547, 2019.
https:///doi.org/10.48550/arXiv.1912.05547
arXiv: 1912.05547
, Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani e Norman Y. Yao. Vantaggio quantistico classicamente verificabile da un test computazionale di Bell. Fisica della natura, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
, Vadim Lyubashevskij, Chris Peikert e Oded Regev. Su reticoli ideali e apprendimento con errori su anelli. Nella conferenza internazionale annuale sulla teoria e le applicazioni delle tecniche crittografiche, pagine 1–23. Springer, 2010.
https: / / doi.org/ 10.1145 / 2535925 mila
, Urmila Mahadev. Verifica classica dei calcoli quantistici. Nel 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pagine 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
, Michael A Nielsen e Isaac Chuang. Calcolo quantistico e informazione quantistica, 2002.
, A. S. Popova e A.N. Rubcov. Superare la soglia del vantaggio quantistico per il campionamento dei bosoni gaussiani. In Conferenza ed esposizione Quantum 2.0, pagina QW2A.15. Gruppo Editoriale Ottica, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
, Giovanni Preskill. L'informatica quantistica nell'era NISQ e oltre. Quantistici, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
, Michael O'Rabin. Algoritmo probabilistico per testare la primalità. Giornale della teoria dei numeri, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
, Oded Regev. Su reticoli, apprendimento con errori, codici lineari casuali e crittografia. Giornale dell'ACM (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324 mila
, Dan Shepherd e Michael J Bremner. Calcolo quantistico temporalmente non strutturato. Atti della Royal Society A: Scienze matematiche, fisiche e ingegneristiche, 465(2105):1413–1439, 2009.
https: / / doi.org/ 10.1098 / rspa.2008.0443
, Peter W. Shor. Algoritmi per il calcolo quantistico: logaritmi discreti e fattorizzazione. In Atti del 35esimo simposio annuale sui fondamenti dell'informatica, pagine 124–134. IEEE, 1994.
https: / / doi.org/ 10.1109 / SFCS.1994.365700
, 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 e Jian-Wei Pan. Forte vantaggio computazionale quantistico utilizzando un processore quantistico superconduttore. Fis. Rev. Lett., 127:180501, 2021.
https: / / doi.org/ 10.1103 / PhysRevLett.127.180501
, K Wright, KM Beck, Sea Debnath, JM Amini, Y Nam, N Grzesiak, J-S Chen, NC Pisenti, M Chmielewski, C Collins, et al. Benchmarking di un computer quantistico a 11 qubit. Comunicazioni sulla natura, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
, G Wendin. Elaborazione dell'informazione quantistica con circuiti superconduttori: una revisione. Rapporti sui progressi in fisica, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
, Adam Bene Watts, Robin Kothari, Luke Schaeffer e Avishay Tal. Separazione esponenziale tra circuiti quantistici superficiali e circuiti classici superficiali a ventaglio illimitato. In Atti del 51° Simposio annuale ACM SIGACT sulla teoria dell'informatica, pagine 515–526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404 mila
, Andrew Chi-Chih Yao. Come generare e scambiare segreti. Nel 27esimo Simposio annuale sui fondamenti dell'informatica (sfcs 1986), pagine 162–167. IEEE, 1986.
https: / / doi.org/ 10.1109 / SFCS.1986.25
, 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 e Jian-Wei Pan. Vantaggio computazionale quantistico tramite campionamento di circuiti casuali a 60 cicli da 24 qubit. Bollettino scientifico, 67(3):240–245, 2022.
https: / / doi.org/ 10.1016 / j.scib.2021.10.017
, 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 e Christopher Monroe. Protocolli interattivi per un vantaggio quantistico classicamente verificabile. prestampa di arXiv arXiv:2112.05156, 2021.
https:///doi.org/10.48550/arXiv.2112.05156
arXiv: 2112.05156
, 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 e Jian-Wei Pan. Vantaggio computazionale quantistico utilizzando i fotoni. Scienza, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Citato da
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath e Ruben Verresen, "Una gerarchia di ordine topologico da unitari a profondità finita, misurazione e feedforward", arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch e Robert Koenig, "Circuiti adattivi a profondità costante per manipolare anioni non abeliani", 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 e Christopher Monroe, "Protocolli interattivi per un vantaggio quantistico classicamente verificabile", arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo e Dmitriy Vassilyev, "PRF chiave-omomorfi specifici per le stelle dalla regressione lineare e dalla teoria degli insiemi estremi", arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani e Norman Y. Yao, "Vantaggio quantistico classicamente verificabile da un test computazionale di Bell", Fisica della natura 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn e Avishay Tal, "Sulla casualità certificata dagli esperimenti Quantum Advantage", arXiv: 2111.14846.
[7] Nai-Hui Chia e Shih-Han Hung, “Verifica classica della profondità quantistica”, arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa e Seiichiro Tani, "Autotest computazionale per stati magici intrecciati", Revisione fisica A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde e Eneet Kaur, "Stima della traccia multivariata a profondità quantistica costante", arXiv: 2206.15405.
Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2022-09-21 12:16:02). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.
On Il servizio citato da Crossref non sono stati trovati dati su citazioni (ultimo tentativo 2022-09-21 12:16:00).
Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.
