1QC Ware Corp., Palo Alto, EUA e Paris, França.
2Goldman, Sachs & Co., Nova York, EUA.
3Universidade de Stanford, Palo Alto, EUA.
4CWI Amsterdã, Holanda.
5CNRS, Université Paris, França.
Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.
Sumário
Projetamos e analisamos dois novos algoritmos de baixa profundidade para estimativa de amplitude (AE) alcançando um equilíbrio ideal entre a aceleração quântica e a profundidade do circuito. Para $beta em (0,1]$, nossos algoritmos exigem $N= tilde{O}( frac{1}{ epsilon^{1+beta}})$ chamadas de oráculo e exigem que o oráculo seja chamado sequencialmente $D= O( frac{1}{ epsilon^{1-beta}})$ vezes para realizar a estimativa de amplitude dentro do erro aditivo $epsilon$. Esses algoritmos interpolam entre o algoritmo clássico $(beta=1)$ e o algoritmo quântico padrão ($ beta=0$) e obter uma compensação $ND= O(1/epsilon^{2})$. Esses algoritmos aproximam os aumentos quânticos dos métodos de Monte Carlo, pois podem fornecer aumentos de velocidade com circuitos mais rasos.
O primeiro algoritmo (Lei de potência AE) usa esquemas de lei de potência na estrutura introduzida por Suzuki et al [24]. O algoritmo funciona para $beta em (0,1]$ e tem garantias de correção demonstráveis quando a função log-verossimilhança satisfaz as condições de regularidade exigidas pelo teorema de Bernstein Von-Mises. O segundo algoritmo (QoPrime AE) usa o teorema do resto chinês para combinar estimativas de profundidade mais baixas para obter maior precisão. O algoritmo funciona para $beta =q/k$ discreto onde $k geq 2$ é o número de módulos coprimos distintos usados pelo algoritmo e $1 leq q leq k-1$, e tem um prova de exatidão totalmente rigorosa Analisamos ambos os algoritmos na presença de ruído despolarizante e fornecemos comparações numéricas com os algoritmos de estimativa de amplitude de última geração.
Resumo popular
O algoritmo AE padrão requer consultas $O(1/epsilon)$ a um circuito oracle que é executado sequencialmente $O(1/epsilon)$ vezes para obter uma precisão $O(epsilon)$. Neste trabalho, abordamos a questão dos speedups no cenário de curto prazo, onde o computador quântico é limitado na profundidade das consultas feitas ao oráculo. Fornecemos um algoritmo comprovadamente correto que alcança uma compensação da forma $O(ND) = O(1/epsilon^{2})$ onde $N$ é o número total de consultas do oráculo e $D$ a profundidade máxima da consulta.
Os resultados demonstram a possibilidade de um aumento de velocidade $D$-fold sobre algoritmos clássicos quando o computador quântico é capaz de consultar o oráculo em profundidade $D$. A nova ideia algorítmica é alavancar o teorema do resto chinês para aumentar a precisão das estimativas de EA.
► dados BibTeX
► Referências
[1] 4 S. Aaronson e P. Rall, “Contagem aproximada quântica, simplificada”, em Simpósio sobre Simplicidade em Algoritmos. SIAM, 2020, pp. 24–32. [Conectados]. Disponível: https:///dx.doi.org/10.1137/1.9781611976014.5 0pt.
https: / / doi.org/ 10.1137 / 1.9781611976014.5
[2] DS Abrams e CP Williams, "Algoritmos quânticos rápidos para integrais numéricas e processos estocásticos", arXiv:quant-ph/9908083, 1999.
arXiv: quant-ph / 9908083
[3] 4 A. Ambainis, “Amplificação de amplitude de tempo variável e algoritmos quânticos para problemas de álgebra linear”, em STACS'12 (29º Simpósio sobre Aspectos Teóricos da Ciência da Computação), vol. 14. LIPICS, 2012, pp. 636-647. [Conectados]. Disponível: https://dx.doi.org/10.4230/LIPIcs.STACS.2012.636 0pt.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2012.636
[4] A. Bouland, W. van Dam, H. Joorati, I. Kerenidis e A. Prakash, “Perspectivas e desafios das finanças quânticas”, pré-impressão arXiv arXiv:2011.06492, 2020.
arXiv: 2011.06492
[5] G. Brassard, F. Dupuis, S. Gambs e A. Tapp, “Um algoritmo quântico ótimo para aproximar a média e sua aplicação para aproximar a mediana de um conjunto de pontos em uma distância arbitrária”, arXiv:1106.4267, 2011.
arXiv: 1106.4267
[6] 4 G. Brassard, P. Hoyer, M. Mosca e A. Tapp, “Amplificação e estimativa de amplitude quântica”, Matemática Contemporânea, vol. 305, pp. 53–74, 2002. [Online]. Disponível: https://dx.doi.org/10.1090/conm/305/05215 0pt.
https: / / doi.org/ 10.1090 / conm / 305/05215
[7] 4 G. Brassard, P. Høyer e A. Tapp, “Quantum counting”, no Colóquio Internacional sobre Autômatos, Linguagens e Programação. Springer, 1998, pp. 820-831. [Conectados]. Disponível: https://dx.doi.org/10.1007/BFb0055105 0pt.
https: / / doi.org/ 10.1007 / BFb0055105
[8] P. Burchard, “Limites inferiores para contagem quântica paralela”, pré-impressão arXiv arXiv:1910.04555, 2019.
arXiv: 1910.04555
[9] P. Erdös e JL Selfridge, "Subconjuntos primos completos de números inteiros consecutivos", Anais da Conferência de Manitoba sobre Matemática Numérica, Winnipeg, p. 13, 1971.
[10] 4 C. Ferrie, CE Granade e DG Cory, “Como melhor amostrar uma distribuição de probabilidade periódica, ou sobre a precisão das estratégias de descoberta hamiltonianas”, Quantum Information Processing, vol. 12, não. 1, pp. 611–623, 2013. [Online]. Disponível: https://dx.doi.org/10.1007/s11128-012-0407-6 0pt.
https://doi.org/10.1007/s11128-012-0407-6
[11] 4 D. Grinko, J. Gacon, C. Zoufal e S. Woerner, “Estimativa iterativa de amplitude quântica”, pré-impressão arXiv arXiv:1912.05559, 2019. [Online]. Disponível: https://dx.doi.org/10.1038/s41534-021-00379-1 0pt.
https://doi.org/10.1038/s41534-021-00379-1
arXiv: 1912.05559
[12] 4 LK Grover, “Uma estrutura para algoritmos mecânicos quânticos rápidos”, em Anais do trigésimo simpósio anual de ACM sobre Teoria da Computação, 1998, pp. 53-62. [Conectados]. Disponível: https:///dx.doi.org/10.1145/276698.276712 0pt.
https: / / doi.org/ 10.1145 / 276698.276712
[13] Y. Hamoudi e F. Magniez, “Desigualdade e aplicações de Quantum Chebyshev”, no 46º Colóquio Internacional sobre Autômatos, Linguagens e Programação (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
[14] 4 AW Harrow, A. Hassidim e S. Lloyd, “Algoritmo quântico para sistemas lineares de equações”, Cartas de revisão física, vol. 103, nº. 15, pág. 150502, 2009. [Online]. Disponível: https:///dx.doi.org/10.1007/978-3-642-27848-8_771-1 0pt.
https://doi.org/10.1007/978-3-642-27848-8_771-1
[15] C. Hipp e R. Michel, “Sobre o Bernstein-v. Aproximação de Mises de distribuições posteriores”, The Annals of Statistics, pp. 972-980, 1976.
[16] 4 W. Hoeffding, “Desigualdades de probabilidade para somas de variáveis aleatórias limitadas”, em The Collected Works of Wassily Hoeffding. Springer, 1994, pp. 409-426. [Conectados]. Disponível: https://doi.org/10.2307/2282952 0pt.
https: / / doi.org/ 10.2307 / 2282952
[17] 4 S. Jeffery, F. Magniez e R. De Wolf, "Algoritmos de consulta quântica paralela ideal", Algorithmica, vol. 79, nº. 2, pp. 509–529, 2017. [Online]. Disponível: https://dx.doi.org/10.1007/s00453-016-0206-z 0pt.
https: / / doi.org/ 10.1007 / s00453-016-0206-z
[18] I. Kerenidis, J. Landman, A. Luongo e A. Prakash, “q-means: um algoritmo quântico para aprendizado de máquina não supervisionado”, Proceedings of Neural Information Processing Systems (NeurIPS), 2019.
[19] AY Kitaev, “Medidas quânticas e o problema do estabilizador abeliano”, pré-impressão arXiv quant-ph/9511026, 1995.
arXiv: quant-ph / 9511026
[20] DE Koh, G. Wang, PD Johnson e Y. Cao, “Uma estrutura para engenharia de funções de probabilidade quântica para estimativa de expectativa”, pré-impressão do arXiv arXiv: 2006.09349, 2020.
arXiv: 2006.09349
[21] 4 T. Li e X. Wu, "Complexidade de consulta quântica de estimativa de entropia", Transações IEEE em Teoria da Informação, vol. 65, não. 5, pp. 2899–2921, 2018. [Online]. Disponível: https://dx.doi.org/10.1109/TIT.2018.2883306 0pt.
https: / / doi.org/ 10.1109 / TIT.2018.2883306
[22] 4 A. Montanaro, "Aceleração quântica dos métodos de Monte Carlo", Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 471, nº. 2181, pág. 20150301, 2015. [Online]. Disponível: https://dx.doi.org/10.1098/rspa.2015.0301 0pt.
https: / / doi.org/ 10.1098 / rspa.2015.0301
[23] 4 J. Preskill, "Computação quântica na era NISQ e além", Quantum, vol. 2, pág. 79, 2018. [On-line]. Disponível: https:///dx.doi.org/10.22331/q-2018-08-06-79 0pt.
https://doi.org/10.22331/q-2018-08-06-79
[24] 4 Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera e N. Yamamoto, “estimativa de amplitude sem estimativa de fase”, Quantum Information Processing, vol. 19, não. 2, pág. 75, 2020. [On-line]. Disponível: https://dx.doi.org/10.1007/s11128-019-2565-2 0pt.
https://doi.org/10.1007/s11128-019-2565-2
[25] 4 T. Tanaka, Y. Suzuki, S. Uno, R. Raymond, T. Onodera e N. Yamamoto, “Estimativa de amplitude via máxima verossimilhança em computador quântico barulhento”, pré-impressão arXiv arXiv:2006.16223, 2020. [Online]. Disponível: https://dx.doi.org/10.1007/s11128-021-03215-9 0pt.
https://doi.org/10.1007/s11128-021-03215-9
arXiv: 2006.16223
[26] 4 D. Wang, O. Higgott e S. Brierley, “Accelerated variacional quantum autosolver”, Physical review letter, vol. 122, nº. 14, pág. 140504, 2019. [On-line]. Disponível: https://doi.org/10.1103/PhysRevLett.122.140504 0pt.
https: / / doi.org/ 10.1103 / PhysRevLett.122.140504
[27] 4 N. Wiebe, A. Kapoor e KM Svore, “Algoritmos quânticos para métodos do vizinho mais próximo para aprendizado supervisionado e não supervisionado”, Quantum Information & Computation, vol. 15, não. 3-4, pp. 316–356, 2015. [Online]. Disponível: https://dx.doi.org/10.26421/QIC15.3-4-7 0pt.
https: / / doi.org/ 10.26421 / QIC15.3-4-7
[28] 4 C. Zalka, “o algoritmo de busca quântica de Grover é ótimo”, Physical Review A, vol. 60, não. 4, pág. 2746, 1999. [Online]. Disponível: https://dx.doi.org/10.1103/PhysRevA.60.2746 0pt.
https: / / doi.org/ 10.1103 / PhysRevA.60.2746
Citado por
[1] Adam Callison e Nicholas Chancellor, “Algoritmos quânticos clássicos híbridos na barulhenta era quântica de escala intermediária e além”, Revisão Física A 106 1, 010101 (2022).
[2] Tudor Giurgica-Tiron, Sonika Johri, Iordanis Kerenidis, Jason Nguyen, Neal Pisenti, Anupam Prakash, Ksenia Sosnova, Ken Wright e William Zeng, “Estimativa de amplitude de baixa profundidade em um computador quântico de íons presos”, arXiv: 2109.09685, Pesquisa de Revisão Física 4 3, 033034 (2022).
[3] Bo Yang, Rudy Raymond e Shumpei Uno, “Mitigação eficiente de erros de leitura quântica para resultados de medição esparsos de dispositivos quânticos de curto prazo”, Revisão Física A 106 1, 012423 (2022).
[4] Dylan Herman, Cody Googin, Xiaoyuan Liu, Alexey Galda, Ilya Safro, Yue Sun, Marco Pistoia e Yuri Alexeev, “A Survey of Quantum Computing for Finance”, arXiv: 2201.02773.
[5] Thais de Lima Silva, Márcio M. Taddei, Stefano Carrazza e Leandro Aolita, “Fragmented imaginary-time evolution for early-stage quantum signal processors”, arXiv: 2110.13180.
[6] Prasanth Shyamsundar, “Amplificação de amplitude quântica não booleana e estimativa de média quântica”, arXiv: 2102.04975.
[7] Koichi Miyamoto, Gonzalo Morrás, Takahiro S. Yamamoto, Sachiko Kuroyanagi e Savvas Nesseris, “Gravitational wave matched filtering by quantum Monte Carlo integration and quantum amplitude amplification”, arXiv: 2205.05966.
[8] Shouvanik Chakrabarti, Rajiv Krishnakumar, Guglielmo Mazzola, Nikitas Stamatopoulos, Stefan Woerner e William J. Zeng, "A Threshold for Quantum Advantage in Derivative Pricing", arXiv: 2012.03819.
[9] Kirill Plekhanov, Matthias Rosenkranz, Mattia Fiorentini e Michael Lubasch, "Estimativa de amplitude quântica variacional", arXiv: 2109.03687.
[10] MC Braun, T. Decker, N. Hegemann e SF Kerstan, "Estimativa de amplitude quântica resiliente a erros da estimativa de fase quântica paralela", arXiv: 2204.01337.
[11] Javier Alcazar, Andrea Cadarso, Amara Katabarwa, Marta Mauri, Borja Peropadre, Guoming Wang e Yudong Cao, "algoritmo quântico para ajustes de avaliação de crédito", Novo Jornal de Física 24 2, 023036 (2022).
[12] Jonas Landman, “Algoritmos Quânticos para Aprendizado de Máquina Não Supervisionado e Redes Neurais”, arXiv: 2111.03598.
[13] Amara Katabarwa, Alex Kunitsa, Borja Peropadre e Peter Johnson, “Reduzindo o tempo de execução e o erro em VQE usando circuitos quânticos mais profundos e ruidosos”, arXiv: 2110.10664.
[14] Zhicheng Zhang, Qisheng Wang e Mingsheng Ying, “Algoritmo Quântico Paralelo para Simulação Hamiltoniana”, arXiv: 2105.11889.
[15] Koichi Miyamoto, “Algoritmo quântico para calcular contribuições de risco em uma carteira de crédito”, arXiv: 2201.11394.
[16] Rhea Parekh, Andrea Ricciardi, Ahmed Darwish e Stephen DiAdamo, “Algoritmos Quânticos e Simulação para Computação Quântica Paralela e Distribuída”, arXiv: 2106.06841.
[17] Koichi Miyamoto, “Precificação de opções das Bermudas por estimativa de amplitude quântica e interpolação de Chebyshev”, arXiv: 2108.09014.
[18] Tomoki Tanaka, Shumpei Uno, Tamiya Onodera, Naoki Yamamoto e Yohichi Suzuki, “Estimativa de amplitude quântica ruidosa sem estimativa de ruído”, Revisão Física A 105 1, 012411 (2022).
[19] Alberto Manzano, Daniele Musso, Álvaro Leitão, Andrés Gómez, Carlos Vázquez, Gustavo Ordóñez e María Rodríguez-Nogueiras, “Quantum Arithmetic for Directly Embedded Arrays”, arXiv: 2107.13872.
[20] Amit Saha, Turbasu Chatterjee, Anupam Chattopadhyay e Amlan Chakrabarti, “Operações Aritméticas Quânticas Aprimoradas Baseadas em Qutrit Intermediárias com Aplicação em Precificação de Derivativos Financeiros”, arXiv: 2205.15822.
[21] Koichi Miyamoto, “Algoritmos quânticos para diferenciação numérica de valores esperados em relação a parâmetros”, Processamento de informações quânticas 21 3, 109 (2022).
[22] Joran van Apeldoorn e Tijn de Vos, “A Framework for Distributed Quantum Queries in the CONGEST Model”, arXiv: 2202.10969.
As citações acima são de Serviço citado por Crossref (última atualização com êxito em 2022-07-19 15:37:00) e SAO / NASA ADS (última atualização com êxito 2022-07-19 15:37:01). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.
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.
