1Departamento de Física, ETH Zürich, Suíça
2Instituto de Estudos Teóricos, ETH Zürich, Suíça
Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.
Sumário
Uma prova de quantum é um tipo de protocolo de desafio-resposta no qual um verificador clássico pode certificar eficientemente a $textit{vantagem quântica}$ de um provador não confiável. Ou seja, um provador quântico pode responder corretamente aos desafios do verificador e ser aceito, enquanto qualquer provador clássico de tempo polinomial será rejeitado com alta probabilidade, com base em suposições computacionais plausíveis. Para responder aos desafios do verificador, as provas existentes de quantum geralmente exigem que o provador quântico execute uma combinação de circuitos e medições quânticas de tamanho polinomial.
Neste artigo, fornecemos duas provas de construções quânticas nas quais o provador precisa apenas executar $textit{circuitos quânticos de profundidade constante}$ (e medições) juntamente com a computação clássica de profundidade logarítmica. Nossa primeira construção é um compilador genérico que nos permite traduzir todas as provas existentes de quantumidade em versões de profundidade quântica constante. Nossa segunda construção é baseada no problema $textit{aprendizagem com arredondamento}$, e produz circuitos com menor profundidade e requerendo menos qubits do que a construção genérica. Além disso, a segunda construção também possui alguma robustez contra ruídos.
► dados BibTeX
► Referências
[1] Scott Aaronson e Alex Arkhipov. A complexidade computacional da óptica linear. Em Proceedings of the quadragésimo terceiro simpósio anual da ACM sobre teoria da computação, páginas 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. Supremacia quântica usando um processador supercondutor programável. Nature, 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: Uma estrutura de código aberto para computação quântica, 2021.
[4] Sanjeev Arora e Boaz Barak. Complexidade computacional: uma abordagem moderna. Cambridge University Press, 2009.
[5] Scott Aaronson e Lijie Chen. Fundamentos teóricos da complexidade de experimentos de supremacia quântica. Em Proceedings of the 32nd Computational Complexity Conference, CCC '17, páginas 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
[6] Scott Aaronson e Sam Gunn. Sobre a dureza clássica da falsificação Benchmarking de entropia cruzada linear. Theory of Computing, 16(11):1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[7] B. Applebaum, Y. Ishai e E. Kushilevitz. Criptografia em ${NC}^0$. No 45º Simpósio Anual do IEEE sobre Fundamentos da Ciência da Computação, páginas 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak e Daniel Wichs. Aprendendo com Arredondamento, Revisitado. Em Advances in Cryptology – CRYPTO 2013, páginas 57–74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] David A. Barrington. Os programas de ramificação de tamanho polinomial de largura limitada reconhecem exatamente esses idiomas em ${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 e Thomas Vidick. Um teste criptográfico de quantum e aleatoriedade certificável de um único dispositivo quântico. Em 2018 IEEE 59º Simpósio Anual sobre Fundamentos da Ciência da Computação (FOCS), páginas 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell e Jeremy M. Sage. Computação quântica de íons presos: progresso e desafios. Revisões de Física Aplicada, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] Adam Bouland, Bill Fefferman, Chinmay Nirkhe e Umesh Vazirani. Sobre a complexidade e verificação da amostragem de circuito aleatório quântico. Nature Physics, 15(2):159–163, fevereiro de 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 e Hartmut Neven. Caracterizando a supremacia quântica em dispositivos de curto prazo. Nature Physics, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani e Thomas Vidick. Provas mais simples de Quantumness. Na 15ª Conferência sobre a Teoria da Computação Quântica, Comunicação e Criptografia (TQC 2020), volume 158 do Leibniz International Proceedings in Informatics (LIPIcs), páginas 8:1–8:14, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz- Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Abhishek Banerjee, Chris Peikert e Alon Rosen. Funções pseudoaleatórias e reticulados. Em Advances in Cryptology – EUROCRYPT 2012, páginas 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 e Richard A Holt. Experimento proposto para testar teorias de variáveis ocultas locais. Physical Review Letters, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[17] Matthew Coudron, Jalex Stark e Thomas Vidick. Trocando localidade por tempo: aleatoriedade certificável de circuitos de baixa profundidade. Communications in Mathematical Physics, 382(1):49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] Richard Cleve e John Watrous. Circuitos paralelos rápidos para a transformada quântica de Fourier. Em Anais do 41º Simpósio Anual sobre Fundamentos da Ciência da Computação, páginas 526–536. IEEE, 2000.
https: / / doi.org/ 10.1109 / SFCS.2000.892140
[19] Pierre Dusart. Automático da função que calcula o número de nomes principais. Tese de doutorado, Université de Limoges, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Austin G Fowler, Matteo Mariantoni, John M Martinis e Andrew N Cleland. Códigos de superfície: rumo à computação quântica prática em grande escala. Physical Review A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] François Le Gall. Correspondência privada, 2022.
[22] Craig Gidney e Martin Ekerå. Como fatorar inteiros RSA de 2048 bits em 8 horas usando 20 milhões de qubits ruidosos. Quantum, 5:433, 2021. See More
https://doi.org/10.22331/q-2021-04-15-433
[23] Alexandru Gheorghiu e Matty J Hoban. Estimar a entropia de saídas de circuitos rasos é difícil. arXiv preprint arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Shuichi Hirahara e François Le Gall. Teste de Quantumidade com Circuitos Quânticos de Pequena Profundidade. No 46º Simpósio Internacional de Fundamentos Matemáticos da Ciência da Computação (MFCS 2021), volume 202 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 59:1–59:15, Dagstuhl, Alemanha, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[25] Aram W Harrow e Ashley Montanaro. Supremacia computacional quântica. Nature, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] Peter Høyer e Robert Špalek. Fan-out quântico é poderoso. Theory of Computing, 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 e Jianxin Chen. Simulação Clássica de Circuitos de Supremacia Quântica. arXiv preprint arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Gregory D Kahanamoku-Meyer. Forjando dados quânticos: derrotando classicamente um teste quântico baseado em 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 e Norman Y. Yao. Vantagem quântica classicamente verificável de um teste de Bell computacional. Nature Physics, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Vadim Lyubashevsky, Chris Peikert e Oded Regev. Sobre redes ideais e aprendizado com erros sobre anéis. Na Conferência Internacional Anual sobre Teoria e Aplicações de Técnicas Criptográficas, páginas 1–23. Springer, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Urmila Mahadev. Verificação clássica de cálculos quânticos. Em 2018 IEEE 59º Simpósio Anual sobre Fundamentos da Ciência da Computação (FOCS), páginas 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[32] Michael A. Nielsen e Isaac Chuang. Computação quântica e informação quântica, 2002.
[33] AS Popova e AN Rubtsov. Quebrando o Limite de Vantagem Quântica para Amostragem de Bósons Gaussianos. Na Conferência e Exposição Quantum 2.0, página QW2A.15. Grupo Ótica Editora, 2022. See More
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] John Preskill. Computação Quântica na era NISQ e além. Quantum, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Michael O Rabin. Algoritmo probabilístico para testar a primalidade. Journal of Number Theory, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Oded Regev. Em redes, aprendendo com erros, códigos lineares aleatórios e criptografia. Journal of the ACM (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[37] Dan Shepherd e Michael J. Bremner. Computação quântica não estruturada temporalmente. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465(2105):1413–1439, 2009.
https: / / doi.org/ 10.1098 / rspa.2008.0443
[38] Peter W Shor. Algoritmos para computação quântica: logaritmos discretos e fatoração. Em Proceedings 35º simpósio anual sobre fundamentos da ciência da computação, páginas 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 e Jian-Wei Pan. Forte vantagem computacional quântica usando um processador quântico supercondutor. Física 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. Benchmarking de um computador quântico de 11 qubits. Comunicações da natureza, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] G Wendin. Processamento de informação quântica com circuitos supercondutores: uma revisão. Reports on Progress in Physics, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] Adam Bene Watts, Robin Kothari, Luke Schaeffer e Avishay Tal. Separação exponencial entre circuitos quânticos rasos e circuitos clássicos rasos fan-in ilimitados. Em Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, páginas 515–526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
[43] Andrew Chi-Chih Yao. Como gerar e trocar segredos. No 27º Simpósio Anual sobre Fundamentos da Ciência da Computação (sfcs 1986), páginas 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 e Jian-Wei Pan. Vantagem computacional quântica via amostragem de circuito aleatório de 60 ciclos de 24 qubits. Boletim de Ciências, 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 e Christopher Monroe. Protocolos interativos para vantagem quântica classicamente verificável. 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 e Jian-Wei Pan. Vantagem computacional quântica usando fótons. Ciência, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Citado por
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath e Ruben Verresen, “Uma hierarquia de ordem topológica de unitários de profundidade finita, medição e feedforward”, arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch e Robert Koenig, “Circuitos adaptativos de profundidade constante para manipulação de anyons não abelianos”, 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, "Protocolos interativos para vantagem quântica classicamente verificável", arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo e Dmitriy Vassilyev, “PRFs chave homomórficas específicas da estrela a partir da regressão linear e da teoria dos conjuntos extremos”, arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani e Norman Y. Yao, “Vantagem quântica classicamente verificável de um teste de Bell computacional”, Natureza Física 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn e Avishay Tal, “On Certified Randomness from Quantum Advantage Experiments”, arXiv: 2111.14846.
[7] Nai-Hui Chia e Shih-Han Hung, “Verificação clássica da profundidade quântica”, arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa e Seiichiro Tani, “Autoteste computacional para estados mágicos emaranhados”, Revisão Física A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde e Eneet Kaur, “Estimativa de traço multivariada em profundidade quântica constante”, arXiv: 2206.15405.
As citações acima são de SAO / NASA ADS (última atualização com êxito 2022-09-21 12:16:02). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.
On Serviço citado por Crossref nenhum dado sobre a citação de trabalhos foi encontrado (última tentativa 2022-09-21 12:16:00).
Este artigo é publicado na Quantum sob o Atribuição 4.0 do Creative Commons Internacional (CC BY 4.0) licença. Os direitos autorais permanecem com os detentores originais, como os autores ou suas instituições.
