Acelerando Algoritmos Quânticos com Pré-computação

Acelerando Algoritmos Quânticos com Pré-computação

Acelerando Algoritmos Quânticos com Pré-computação PlatoBlockchain Data Intelligence. Pesquisa vertical. Ai.

William J. Huggins e Jarrod R. McClean

Google Quantum AI, Veneza, CA, EUA

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

Sumário

As aplicações de computação do mundo real podem ser extremamente sensíveis ao tempo. Seria valioso se pudéssemos acelerar essas tarefas realizando parte do trabalho com antecedência. Motivados por isso, propomos um modelo de custo para algoritmos quânticos que permite a pré-computação quântica; isto é, para uma quantidade polinomial de computação “livre” antes que a entrada de um algoritmo seja totalmente especificada e métodos para tirar vantagem dela. Analisamos duas famílias de unitários que são assintoticamente mais eficientes de implementar neste modelo de custos do que no padrão. O primeiro exemplo de pré-computação quântica, baseado na exponenciação da matriz de densidade, poderia oferecer uma vantagem exponencial sob certas condições. O segundo exemplo usa uma variante de teletransporte de portão para obter uma vantagem quadrática quando comparado com a implementação direta dos unitários. Esses exemplos sugerem que a pré-computação quântica pode oferecer uma nova arena para buscar vantagens quânticas.

► dados BibTeX

► Referências

[1] S Aaronson. Limitações do aconselhamento quântico e da comunicação unidirecional. Em Processo. 19ª Conferência Anual do IEEE sobre Complexidade Computacional, 2004, páginas 320–332. IEEE, 2004. ISBN 9780769521206/​ccc.10.1109.
https: / / doi.org/ 10.1109 / ccc.2004.1313854

[2] Scott Aaronson e Andris Ambainis. Forrelação. Em Anais do quadragésimo sétimo simpósio anual da ACM sobre Teoria da Computação, STOC '15, páginas 307–316, Nova York, NY, EUA, 14 de junho de 2015. ACM. ISBN 9781450335362/​10.1145.
https: / / doi.org/ 10.1145 / 2746539.2746547

[3] Scott Aaronson e Guy N Rothblum. Medição suave de estados quânticos e privacidade diferencial. 18 de abril de 2019. URL http://​/​arxiv.org/​abs/​1904.08747.
arXiv: 1904.08747

[4] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo e Hartmut Neven. Concentre-se além das acelerações quadráticas para obter vantagem quântica com correção de erros. PRX quantum, 2 (1): 010103, 29 de março de 2021. ISSN 2691-3399. 10.1103/​prxquantum.2.010103.
https: / / doi.org/ 10.1103 / prxquantum.2.010103

[5] Daniel J Bernstein e Tanja Lange. Fissuras não uniformes no concreto: O poder da pré-computação livre. Em Advances in Cryptology – ASIACRYPT 2013, Notas de aula em ciência da computação, páginas 321–340. Springer Berlin Heidelberg, Berlim, Heidelberg, 2013. ISBN 9783642420443,9783642420450. 10.1007/​978-3-642-42045-0_17.
https:/​/​doi.org/​10.1007/​978-3-642-42045-0_17

[6] Dominic W Berry, Craig Gidney, Mario Motta, Jarrod R McClean e Ryan Babbush. Qubitização da química quântica de base arbitrária aproveitando a dispersão e a fatoração de baixa classificação. 6 de fevereiro de 2019. URL https://​/​doi.org/​10.22331/​q-2019-12-02-208.
https:/​/​doi.org/​10.22331/​q-2019-12-02-208

[7] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe e Seth Lloyd. Aprendizado de máquina quântica. Natureza, 549 (7671): 195–202, setembro de 2017. ISSN 0028-0836,1476-4687. 10.1038/nature23474.
https: / / doi.org/ 10.1038 / nature23474

[8] Sergey Bravyi e Alexei Kitaev. Computação quântica universal com portas de Clifford ideais e ancillas ruidosas. Física. Rev. 71/​physreva.2.
https: / / doi.org/ 10.1103 / physreva.71.022316

[9] Sergey Bravyi e Dmitri Maslov. Os circuitos livres de Hadamard expõem a estrutura do grupo clifford. IEEE Trans. Inf. Teoria, 67 (7): 4546–4563, julho de 2021. ISSN 0018-9448,1557-9654. 10.1109/​tit.2021.3081415.
https: / / doi.org/ 10.1109 / tit.2021.3081415

[10] Earl T Campbell e Joe O'Gorman. Uma abordagem eficiente de estado mágico para rotações de pequenos ângulos. 14 de março de 2016. URL https://​/​doi.org/​10.1088/​2058-9565/​1/​1/​015007.
https:/​/​doi.org/​10.1088/​2058-9565/​1/​1/​015007

[11] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang e Jerry Li. Separações exponenciais entre aprendizagem com e sem memória quântica. Em 2021, 62º Simpósio Anual IEEE sobre Fundamentos da Ciência da Computação (FOCS). IEEE, fevereiro de 2022. 10.1109/​focs52979.2021.00063.
https://​/​doi.org/​10.1109/​focs52979.2021.00063

[12] Andrew M Childs, Robin Kothari e Rolando D Somma. Algoritmo quântico para sistemas de equações lineares com dependência de precisão exponencialmente melhorada. SIAM J. Comput., 46 (6): 1920–1950, 1º de janeiro de 2017. ISSN 0097-5397. 10.1137/​16M1087072.
https: / / doi.org/ 10.1137 / 16M1087072

[13] N Cody Jones, James D Whitfield, Peter L McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik e Yoshihisa Yamamoto. Simulação de química quântica mais rápida em computadores quânticos tolerantes a falhas. Novo J. Phys., 14 (11): 115023, 27 de novembro de 2012. ISSN 1367-2630. 10.1088/​1367-2630/​14/​11/​115023.
https:/​/​doi.org/​10.1088/​1367-2630/​14/​11/​115023

[14] Pedro CS Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush e Dominic W Berry. Solucionador de sistemas lineares quânticos de escala ideal via teorema adiabático discreto. PRX quantum, 3 (4): 040303, 7 de outubro de 2022. ISSN 2691-3399. 10.1103/​prxquantum.3.040303.
https: / / doi.org/ 10.1103 / prxquantum.3.040303

[15] Jordan Cotler, Hsin-Yuan Huang e Jarrod R McClean. Revisitando a desquantização e a vantagem quântica em tarefas de aprendizagem. 1º de dezembro de 2021. URL http://​/​arxiv.org/​abs/​2112.00811.
arXiv: 2112.00811

[16] Shawn X Cui, Daniel Gottesman e Anirudh Krishna. Portões diagonais na hierarquia de Clifford. Física. Rev. A, 95 (1), 26 de janeiro de 2017. ISSN 2469-9926,2469-9934. 10.1103/​physreva.95.012329.
https: / / doi.org/ 10.1103 / physreva.95.012329

[17] Edward Farhi, Jeffrey Goldstone e Sam Gutmann. Um algoritmo de otimização quântica aproximada. 14 de novembro de 2014. URL http://​/​arxiv.org/​abs/​1411.4028.
arXiv: 1411.4028

[18] Austin G Fowler. Computação quântica com ótimo tempo. 17 de outubro de 2012. URL http://​/​arxiv.org/​abs/​1210.4626.
arXiv: 1210.4626

[19] Sevag Gharibian e François Le Gall. Desquantizando a transformação quântica de valor singular: dureza e aplicações à química quântica e à conjectura quântica PCP. Em Anais do 54º Simpósio Anual ACM SIGACT sobre Teoria da Computação, STOC 2022, páginas 19–32, Nova York, NY, EUA, 9 de junho de 2022. ACM. ISBN 9781450392648/​10.1145.
https: / / doi.org/ 10.1145 / 3519935.3519991

[20] Craig Gidney e Martin Ekerå. Como fatorar números inteiros RSA de 2048 bits em 8 horas usando 20 milhões de qubits barulhentos. Quantum, 5 (433): 433, 15 de abril de 2021. ISSN 2521-327X. 10.22331/​q-2021-04-15-433.
https:/​/​doi.org/​10.22331/​q-2021-04-15-433

[21] Craig Gidney e Austin G Fowler. Layout flexível de cálculos de código de superfície usando estados AutoCCZ. 21 de maio de 2019. URL http://​/​arxiv.org/​abs/​1905.08916.
arXiv: 1905.08916

[22] András Gilyén e Alexander Poremba. Algoritmos quânticos aprimorados para estimativa de fidelidade. 29 de março de 2022. URL http://​/​arxiv.org/​abs/​2203.15993.
arXiv: 2203.15993

[23] Daniel Gottesman e Isaac L. Chuang. O teletransporte quântico é uma primitiva computacional universal. 2 de agosto de 1999. URL https:///​/​doi.org/​10.1038/​46503.
https: / / doi.org/ 10.1038 / 46503

[24] Leo Grady e Ali Kemal Sinop. Segmentação rápida e aproximada de caminhantes aleatórios usando pré-computação de autovetores. Na Conferência IEEE de 2008 sobre Visão Computacional e Reconhecimento de Padrões, páginas 1–8. IEEE, junho de 2008. ISBN 9781424422425. 10.1109/​cvpr.2008.4587487.
https://​/​doi.org/​10.1109/​cvpr.2008.4587487

[25] Amo K Grover. Um algoritmo de mecânica quântica rápido para pesquisa em banco de dados. Em Anais do vigésimo oitavo simpósio anual da ACM sobre Teoria da Computação – STOC '96, STOC '96, páginas 212–219, Nova York, Nova York, EUA, 1996. ACM Press. ISBN 9780897917858/​10.1145.
https: / / doi.org/ 10.1145 / 237814.237866

[26] Aram W Harrow, Avinatan Hassidim e Seth Lloyd. Algoritmo quântico para sistemas lineares de equações. Física. Rev. Lett., 103 (15): 150502, 9 de outubro de 2009. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

[27] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill e Jarrod R McClean. Vantagem quântica em aprender com experimentos. Ciência, 376 (6598): 1182–1186, 10 de junho de 2022. ISSN 0036-8075,1095-9203. 10.1126/​science.abn7293.
https://​/​doi.org/​10.1126/​science.abn7293

[28] Cody Jones. Protocolos de destilação para estados de Fourier em computação quântica. 12 de março de 2013. URL http://​/​arxiv.org/​abs/​1303.3066.
arXiv: 1303.3066

[29] John Kallaugher. Uma vantagem quântica para um problema de streaming natural. Em 2021, 62º Simpósio Anual IEEE sobre Fundamentos da Ciência da Computação (FOCS), páginas 897–908. IEEE, fevereiro de 2022. 10.1109/​focs52979.2021.00091.
https://​/​doi.org/​10.1109/​focs52979.2021.00091

[30] Richard M Karp e Richard J Lipton. Algumas conexões entre classes de complexidade não uniformes e uniformes. Em Anais do décimo segundo simpósio anual ACM sobre Teoria da Computação – STOC '80, STOC '80, páginas 302–309, Nova York, Nova York, EUA, 28 de abril de 1980. ACM Press. ISBN 9780897910170/​10.1145.
https: / / doi.org/ 10.1145 / 800141.804678

[31] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols e Theodore J Yoder. Simulação hamiltoniana com complexidade de amostra ideal. Npj Quantum Inf., 3 (1): 1–7, 30 de março de 2017. ISSN 2056-6387,2056-6387. 10.1038/​s41534-017-0013-7.
https:/​/​doi.org/​10.1038/​s41534-017-0013-7

[32] François Le Gall. Separação exponencial da complexidade do espaço online quântico e clássico. Em Anais do décimo oitavo simpósio anual ACM sobre Paralelismo em algoritmos e arquiteturas, SPAA '06, páginas 67–73, Nova York, NY, EUA, 30 de julho de 2006. ACM. ISBN 9781595934529/​10.1145.
https: / / doi.org/ 10.1145 / 1148109.1148119

[33] Lin Lin e Yu Tong. Filtragem de estado próprio quântico baseada em polinômios ideal com aplicação na resolução de sistemas lineares quânticos. Quantum, 4 (361): 361, 11 de novembro de 2020. ISSN 2521-327X. 10.22331/​q-2020-11-11-361.
https:/​/​doi.org/​10.22331/​q-2020-11-11-361

[34] Daniel Litinski. Destilação em estado mágico: Não é tão caro quanto você pensa. Quantum, 3 (205): 205, 2 de dezembro de 2019a. ISSN2521-327X. 10.22331/​q-2019-12-02-205.
https:/​/​doi.org/​10.22331/​q-2019-12-02-205

[35] Daniel Litinski. Um jogo de códigos de superfície: computação quântica em grande escala com cirurgia de rede. Quantum, 3 (128): 128, 5 de março de 2019b. ISSN2521-327X. 10.22331/​q-2019-03-05-128.
https:/​/​doi.org/​10.22331/​q-2019-03-05-128

[36] Seth Lloyd, Masoud Mohseni e Patrick Rebentrost. Análise quântica de componentes principais. Nat. Phys., 10 (9): 631–633, 27 de setembro de 2014. ISSN 1745-2473,1745-2481. 10.1038/nphys3029.
https: / / doi.org/ 10.1038 / nphys3029

[37] John M Martyn, Zane M Rossi, Andrew K Tan e Isaac L Chuang. Grande unificação de algoritmos quânticos. PRX quantum, 2 (4): 040203, 3 de dezembro de 2021. ISSN 2691-3399. 10.1103/​prxquantum.2.040203.
https: / / doi.org/ 10.1103 / prxquantum.2.040203

[38] Iman Marvian e Seth Lloyd. Emulador quântico universal. 8 de junho de 2016. URL http://​/​arxiv.org/​abs/​1606.02734.
arXiv: 1606.02734

[39] F Motzoi, MP Kaicher e FK Wilhelm. Composições temporais lineares e logarítmicas de operadores quânticos de muitos corpos. Física. Rev. 119/PhysRevLett.16.
https: / / doi.org/ 10.1103 / PhysRevLett.119.160503

[40] Michael A Nielsen. Computação quântica óptica usando estados de cluster. Física. Rev. 93/​PhysRevLett.4.
https: / / doi.org/ 10.1103 / PhysRevLett.93.040503

[41] Bryan O'Gorman, William J Huggins, Eleanor G Rieffel e K Birgitta Whaley. Redes de troca generalizadas para computação quântica de curto prazo. 13 de maio de 2019. URL http://​/​arxiv.org/​abs/​1905.05118.
arXiv: 1905.05118

[42] Paul Pham e Krysta M Svore. Uma arquitetura quântica 2D de vizinho mais próximo para fatoração em profundidade polilogarítmica. 27 de julho de 2012. URL http://​/​arxiv.org/​abs/​1207.6655.
arXiv: 1207.6655

[43] R Raussendorf e HJ Briegel. Um computador quântico unilateral. Física. Rev. 86/​PhysRevLett.22.
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[44] Yuval R Sanders, Dominic W Berry, Pedro CS Costa, Louis W Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven e Ryan Babbush. Compilação de heurísticas quânticas tolerantes a falhas para otimização combinatória. PRX quantum, 1 (2): 020312, 9 de novembro de 2020. ISSN 2691-3399. 10.1103/​prxquantum.1.020312.
https: / / doi.org/ 10.1103 / prxquantum.1.020312

[45] Dan Shepherd e Michael J Bremner. Computação quântica temporariamente não estruturada. Processo. Matemática. Física. Eng. Sci., 465 (2105): 1413–1439, 8 de maio de 2009. ISSN 1364-5021,1471-2946. 10.1098/​rspa.2008.0443.
https: / / doi.org/ 10.1098 / rspa.2008.0443

[46] Peter-Pike Sloan, Jan Kautz e John Snyder. Transferência de brilho pré-computada para renderização em tempo real em ambientes de iluminação dinâmica e de baixa frequência. Em Anais da 29ª conferência anual sobre computação gráfica e técnicas interativas, SIGGRAPH '02, páginas 527–536, Nova York, NY, EUA, 1 de julho de 2002. ACM. ISBN 9781581135213/​10.1145.
https: / / doi.org/ 10.1145 / 566570.566612

[47] James E Smith. Um estudo de estratégias de previsão de ramificação. Em 25 anos de simpósios internacionais sobre arquitetura de computadores (artigos selecionados), ISCA '98, páginas 202–215, Nova York, NY, EUA, 1 de agosto de 1998. ACM. ISBN 9781581130584/​10.1145.
https: / / doi.org/ 10.1145 / 285930.285980

[48] Rolando D Somma e Yiğit Subaşı. Complexidade da verificação do estado quântico no problema de sistemas lineares quânticos. PRX quantum, 2 (1): 010315, 27 de janeiro de 2021. ISSN 2691-3399. 10.1103/​prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

[49] Bárbara M Terhal. Correção quântica de erros para memórias quânticas. Rev. Mod. Phys., 87 (2): 307–346, 7 de abril de 2015. ISSN 0034-6861,1539-0756. 10.1103/​revmodphys.87.307.
https: / / doi.org/ 10.1103 / revmodphys.87.307

[50] Xinlan Zhou, Debbie W Leung e Isaac L Chuang. Metodologia para construção de portas lógicas quânticas. Física. Rev. A, 62 (5), 18 de outubro de 2000. ISSN 1050-2947,1094-1622. 10.1103/​physreva.62.052316.
https: / / doi.org/ 10.1103 / physreva.62.052316

Citado por

[1] Dar Gilboa e Jarrod R. McClean, “Vantagem da comunicação quântica exponencial na aprendizagem distribuída”, arXiv: 2310.07136, (2023).

[2] Pablo Rodriguez-Grasa, Ruben Ibarrondo, Javier Gonzalez-Conde, Yue Ban, Patrick Rebentrost e Mikel Sanz, “Exponenciação de matriz de densidade assistida por clonagem aproximada quântica”, arXiv: 2311.11751, (2023).

As citações acima são de SAO / NASA ADS (última atualização com êxito 2024-02-22 13:13:08). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.

Não foi possível buscar Dados citados por referência cruzada durante a última tentativa 2024-02-22 13:13:06: Não foi possível buscar os dados citados por 10.22331 / q-2024-02-22-1264 do Crossref. Isso é normal se o DOI foi registrado recentemente.

Carimbo de hora:

Mais de Diário Quântico