Forjando dados quânticos: derrotando classicamente um teste quântico baseado em IQP

Forjando dados quânticos: derrotando classicamente um teste quântico baseado em IQP

Carimbo de data / hora: 11 de setembro de 2023 8:46

Gregory D. Kahanamoku-Meyer

Departamento de Física, Universidade da Califórnia em Berkeley, Berkeley, CA 94720

Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.

Sumário

Recentemente, experimentos de computação quântica excederam pela primeira vez a capacidade dos computadores clássicos de realizar certos cálculos – um marco denominado “vantagem computacional quântica”. No entanto, verificar a saída do dispositivo quântico nesses experimentos exigiu cálculos clássicos extremamente grandes. Um próximo passo emocionante para demonstrar a capacidade quântica seria implementar testes de vantagem computacional quântica com verificação clássica eficiente, de modo que sistemas maiores possam ser testados e verificados. Uma das primeiras propostas para um teste de quântica eficientemente verificável consiste em esconder uma bitstring clássica secreta dentro de um circuito da classe IQP, de tal forma que amostras da distribuição de saída do circuito sejam correlacionadas com o segredo. A dureza clássica deste protocolo foi apoiada por evidências de que simular diretamente circuitos IQP é difícil, mas a segurança do protocolo contra outros ataques clássicos (não simulados) permaneceu uma questão em aberto. Neste trabalho demonstramos que o protocolo não é seguro contra a falsificação clássica. Descrevemos um algoritmo clássico que pode não apenas convencer o verificador de que o provador (clássico) é quântico, mas também pode de fato extrair a chave secreta subjacente a uma determinada instância de protocolo. Além disso, mostramos que o algoritmo de extração de chaves é eficiente na prática para problemas com tamanhos de centenas de qubits. Finalmente, fornecemos uma implementação do algoritmo e fornecemos o vetor secreto subjacente ao “desafio de $ 25” postado online pelos autores do artigo original.

Forjando dados quânticos: derrotando classicamente um teste quântico baseado em IQP PlatoBlockchain Data Intelligence. Pesquisa vertical. Ai.

Imagem em destaque: Neste trabalho, mostramos como um computador clássico trapaceiro (à esquerda) pode se disfarçar de computador quântico em suas interações com um computador “verificador” clássico (à direita), no contexto de um protocolo específico de prova de quântica.

Resumo popular

Experimentos recentes de amostragem quântica demonstraram vantagem computacional quântica ao realizar cálculos que são inviáveis ​​de reproduzir classicamente. No entanto, a verificação clássica dos resultados é pelo menos igualmente difícil, tornando a verificação direta inviável para experimentos maiores. Um candidato para superar esse desafio foi um protocolo de amostragem proposto em 2008, que prometia verificação clássica eficiente, mantendo a dureza clássica de reproduzir o comportamento do dispositivo quântico. Neste trabalho, fornecemos um algoritmo clássico eficiente que passa nas verificações extraindo a chave secreta subjacente, que deveria estar oculta mesmo em um dispositivo quântico real. Nosso algoritmo invalida a afirmação de que apenas um dispositivo quântico poderia passar nas verificações, anulando a utilidade do teste como demonstração da capacidade quântica.

► dados BibTeX

► Referências

[1] Frank Arute e cols. “Supremacia quântica usando um processador supercondutor programável”. Nature 574, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[2] Han-Sen Zhong et al. “Vantagem computacional quântica usando fótons”. Ciência 370, 1460–1463 (2020).
https: / / doi.org/ 10.1126 / science.abe8770

[3] 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”. Cartas de Revisão Física 127, 180501 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.180501

[4] 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, Ele -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 por meio de amostragem de circuito aleatório de 60 qubits e 24 ciclos”. Boletim Científico 67, 240–245 (2022).
https: / / doi.org/ 10.1016 / j.scib.2021.10.017

[5] Scott Aaronson e Alex Arkhipov. “A complexidade computacional da óptica linear”. Nos Anais do quadragésimo terceiro simpósio anual da ACM sobre Teoria da Computação. Páginas 333–342. STOC '11Nova York, NY, EUA (2011). Associação de Máquinas de Computação.
https: / / doi.org/ 10.1145 / 1993636.1993682

[6] Edward Farhi e Aram W. Harrow. “Supremacia Quântica através do Algoritmo de Otimização Aproximada Quântica” (2019). arXiv:1602.07674.
arXiv: 1602.07674

[7] AP Lund, Michael J. Bremner e TC Ralph. “Problemas de amostragem quântica, BosonSampling e supremacia quântica”. npj Informação Quântica 3, 1–8 (2017).
https:/​/​doi.org/​10.1038/​s41534-017-0018-2

[8] Aram W. Harrow e Ashley Montanaro. “Supremacia computacional quântica”. Natureza 549, 203–209 (2017).
https: / / doi.org/ 10.1038 / nature23458

[9] 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, 595-600 (2018).
https: / / doi.org/ 10.1038 / s41567-018-0124-x

[10] Bárbara M. Terhal. “Supremacia quântica, aí vamos nós”. Física da Natureza 14, 530–531 (2018).
https: / / doi.org/ 10.1038 / s41567-018-0131-y

[11] C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, SV Isakov, V. Smelyanskiy, A. Megrant, B. Chiaro, A. Dunsworth, K. Arya, R. Barends, B. Burkett, Y. Chen , Z. Chen, et al. “Um projeto para demonstrar a supremacia quântica com qubits supercondutores”. Ciência 360, 195–199 (2018).
https: / / doi.org/ 10.1126 / science.aao4309

[12] Sergey Bravyi, David Gosset e Robert Konig. “Vantagem quântica com circuitos rasos”. Ciência 362, 308–311 (2018).
https: / / doi.org/ 10.1126 / science.aar3106

[13] Sergey Bravyi, David Gosset, Robert König e Marco Tomamichel. “Vantagem quântica com circuitos rasos barulhentos”. Física da Natureza 16, 1040–1045 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

[14] 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, 159–163 (2019).
https:/​/​doi.org/​10.1038/​s41567-018-0318-2

[15] Scott Aaronson e Sam Gunn. “Sobre a dureza clássica da falsificação de benchmarking de entropia cruzada linear”. Teoria da Computação 16, 1–8 (2020).
https: / / doi.org/ 10.4086 / toc.2020.v016a011

[16] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani e Thomas Vidick. “Um teste criptográfico de quântica e aleatoriedade certificável a partir de um único dispositivo quântico”. Jornal da ACM (JACM) (2021).
https: / / doi.org/ 10.1145 / 3441309

[17] Zvika Brakerski, Venkata Koppula, Umesh Vazirani e Thomas Vidick. “Provas mais simples de quântica”. Em Steven T. Flammia, editor, 15ª Conferência sobre Teoria da Computação, Comunicação e Criptografia Quântica (TQC 2020). Volume 158 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 8:1–8:14. Dagstuhl, Alemanha (2020). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8

[18] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani e Norman Y. Yao. “Vantagem quântica classicamente verificável a partir de um teste computacional de Bell”. Física da Natureza 18, 918–924 (2022).
https:/​/​doi.org/​10.1038/​s41567-022-01643-7

[19] Dan Shepherd e Michael J. Bremner. “Computação quântica temporalmente não estruturada”. Procedimentos da Royal Society A: Ciências Matemáticas, Físicas e de Engenharia 465, 1413–1439 (2009).
https: / / doi.org/ 10.1098 / rspa.2008.0443

[20] Michael J. Bremner et al. “A simulação clássica de cálculos quânticos comutados implica o colapso da hierarquia polinomial”. Procedimentos da Royal Society A: Ciências Matemáticas, Físicas e de Engenharia 467, 459–472 (2011).
https: / / doi.org/ 10.1098 / rspa.2010.0301

[21] Michael J. Bremner et al. “Complexidade de caso médio versus simulação aproximada de computações quânticas comutadas”. Cartas de Revisão Física 117, 080501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501

[22] Gregory D. Kahanamoku-Meyer (2023). código: https://​/​doi.org/​10.5281/​zenodo.7545881.
https: / / doi.org/ 10.5281 / zenodo.7545881

[23] Yusuf Alnawakhtha, Atul Mantri, Carl A. Miller e Daochen Wang. “Vantagem quântica baseada em rede de medições rotacionadas” (2022). arXiv:2210.10143.
arXiv: 2210.10143

[24] Takashi Yamakawa e Mark Zhandry. “Vantagem Quântica Verificável sem Estrutura”. Em 2022, 63º Simpósio Anual IEEE sobre Fundamentos da Ciência da Computação (FOCS). Páginas 69–74. (2022).
https: / / doi.org/ 10.1109 / FOCS54457.2022.00014

[25] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan e Lisa Yang. “Vantagem quântica de qualquer jogo não local”. Nos Anais do 55º Simpósio Anual ACM sobre Teoria da Computação. Páginas 1617–1628. STOC 2023Nova York, NY, EUA (2023). Associação de Máquinas de Computação.
https: / / doi.org/ 10.1145 / 3564246.3585164

[26] Alexandru Gheorghiu e Thomas Vidick. “Preparação de estado remoto computacionalmente seguro e combinável”. Em 2019, 60º Simpósio Anual IEEE sobre Fundamentos da Ciência da Computação (FOCS). Páginas 1024–1033. (2019).
https: / / doi.org/ 10.1109 / FOCS.2019.00066

[27] Urmila Mahadev. “Verificação Clássica de Computações Quânticas”. Em 2018, 59º Simpósio Anual IEEE sobre Fundamentos da Ciência da Computação (FOCS). Páginas 259–267. (2018).
https: / / doi.org/ 10.1109 / FOCS.2018.00033

Citado por

[1] Sergey Bravyi, David Gosset, Robert König e Marco Tomamichel, “Vantagem quântica com circuitos rasos barulhentos”, Natureza Física 16 10, 1040 (2020).

[2] Dominik Hangleiter e Jens Eisert, “Vantagem computacional da amostragem aleatória quântica”, Comentários de Modern Physics 95 3, 035001 (2023).

[3] Zhenning Liu e Alexandru Gheorghiu, “Provas de quantumidade com eficiência em profundidade”, Quântico 6, 807 (2022).

[4] Martin Kliesch e Ingo Roth, “Teoria da certificação de sistema quântico: um tutorial”, arXiv: 2010.05925, (2020).

[5] Ulysse Chabaud, Frédéric Grosshans, Elham Kashefi e Damian Markham, “Verificação eficiente da amostragem de bósons”, Quântico 5, 578 (2021).

[6] Michael J. Bremner, Bin Cheng e Zhengfeng Ji, “Amostragem IQP e vantagem quântica verificável: esquema de estabilizador e segurança clássica”, arXiv: 2308.07152, (2023).

[7] Sergey Bravyi, David Gosset, Daniel Grier e Luke Schaeffer, “Algoritmos clássicos para relacionamento”, arXiv: 2102.06963, (2021).

[8] Dominik Hangleiter, “Amostragem e a complexidade da natureza”, arXiv: 2012.07905, (2020).

[9] Xi Chen, Bin Cheng, Zhaokai Li, Xinfang Nie, Nengkun Yu, Man-Hong Yung e Xinhua Peng, “Verificação criptográfica experimental para computação quântica em nuvem de curto prazo”, Boletim Científico 66 1, 23 (2021).

[10] Sritam Kumar Satpathy, Vallabh Vibhu, Sudev Pradhan, Bikash K. Behera e Prasanta K. Panigrahi, “Verificação eficiente da amostragem de bósons usando um computador quântico”, arXiv: 2108.03954, (2021).

As citações acima são de SAO / NASA ADS (última atualização com êxito 2023-09-12 13:11:52). 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 2023-09-12 13:11:50).

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.

Carimbo de hora:

Mais de Diário Quântico