Sub-rotinas quânticas básicas: encontrar vários elementos marcados e somar números

Sub-rotinas quânticas básicas: encontrar vários elementos marcados e somar números

Carimbo de hora: 14 de março de 2024 9h40
Sub-rotinas quânticas básicas: encontrando vários elementos marcados e somando números PlatoBlockchain Data Intelligence. Pesquisa vertical. Ai.

Joran van Apeldoorn1, Sander Gribling2 e Harold Nieuwboer3

1IViR e QuSoft, Universidade de Amsterdã, Holanda
2Departamento de Econometria e Pesquisa Operacional, Universidade de Tilburg, Tilburg, Holanda
3Instituto Korteweg-de Vries de Matemática e QuSoft, Universidade de Amsterdã, Holanda e Faculdade de Ciência da Computação, Universidade Ruhr Bochum, Alemanha e Departamento de Ciências Matemáticas, Universidade de Copenhague, Dinamarca

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

Sumário

Mostramos como encontrar todos os elementos $k$ marcados em uma lista de tamanho $N$ usando o número ideal $O(sqrt{N k})$ de consultas quânticas e apenas um overhead polilogarítmico na complexidade da porta, na configuração onde um tem uma pequena memória quântica. Algoritmos anteriores incorriam em um fator $k$ de sobrecarga na complexidade da porta ou tinham um fator extra $log(k)$ na complexidade da consulta.
Consideramos então o problema de encontrar uma aproximação $delta$ multiplicativa de $s = sum_{i=1}^N v_i$ onde $v=(v_i) em [0,1]^N$, dado acesso de consulta quântica a uma descrição binária de $v$. Fornecemos um algoritmo que faz isso, com probabilidade de pelo menos $1-rho$, usando consultas quânticas $O(sqrt{N log(1/rho) / delta})$ (sob suposições moderadas em $rho$). Isso melhora quadraticamente a dependência de $1/delta$ e $log(1/rho)$ em comparação com uma aplicação direta de estimativa de amplitude. Para obter a dependência $log(1/rho)$ melhorada, usamos o primeiro resultado.

► dados BibTeX

► Referências

[1] Srinivasan Arunachalam e Ronald de Wolf. Otimizando o número de portas na pesquisa quântica. Informações Quânticas. Comput., 17(3-4):251–261, 2017. doi:10.26421/​qic17.3-4.
https: / / doi.org/ 10.26421 / qic17.3-4

[2] José A. Adell e P. Jodrá. Distâncias exatas de Kolmogorov e de variação total entre algumas distribuições discretas familiares. Jornal de Desigualdades e Aplicações, 2006(1):1–8, 2006. doi:10.1155/​JIA/​2006/​64307.
https://​/​doi.org/​10.1155/​JIA/​2006/​64307

[3] Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter e Ronald de Wolf. Algoritmos quânticos para escalonamento e balanceamento de matrizes. Em Anais do 48º Colóquio Internacional sobre Autômatos, Linguagens e Programação (ICALP'21), volume 198, páginas 110:1–110:17, 2021. arXiv:2011.12823, doi:10.4230/​LIPIcs.ICALP.2021.110.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.110
arXiv: 2011.12823

[4] Scott Aaronson e Patrick Rall. Contagem quântica aproximada, simplificada. No Simpósio sobre Simplicidade em Algoritmos, páginas 24–32, 2020. doi:10.1137/​1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5

[5] Michel Boyer, Gilles Brassard, Peter Høyer e Alain Tapp. Limites rígidos na pesquisa quântica. Fortschritte der Physik, 46(4–5):493–505, 1998. Versão anterior em Physcomp'96. arXiv:quant-ph/9605034.
arXiv: quant-ph / 9605034

[6] Harry Buhrman, Richard Cleve, Ronald de Wolf e Christof Zalka. Limites para algoritmos quânticos com erros pequenos e erros zero. No 40º Simpósio Anual sobre Fundamentos da Ciência da Computação (FOCS'99), páginas 358–368. Sociedade de Computação IEEE, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca e Alain Tapp. Amplificação e estimativa de amplitude quântica. Em Computação Quântica e Informação Quântica: Um Volume do Milênio, volume 305 de Matemática Contemporânea, páginas 53–74. Sociedade Matemática Americana, 2002. doi:10.1002/(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P

[8] Richard Brent e Paul Zimmermann. Aritmética de Computador Moderna, volume 18. Cambridge University Press, 2010.

[9] Ran Canetti, Guy Even e Oded Goldreich. Limites inferiores para algoritmos de amostragem para estimar a média. Cartas de Processamento de Informações, 53(1):17–25, janeiro de 1995. doi:10.1016/​0020-0190(94)00171-T.
https:/​/​doi.org/​10.1016/​0020-0190(94)00171-T

[10] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini e Leonard Wossnig. Aprendizado de máquina quântica: uma perspectiva clássica. Anais da Royal Society A: Ciências Matemáticas, Físicas e de Engenharia, 474(2209):20170551, janeiro de 2018. doi:10.1098/​rspa.2017.0551.
https: / / doi.org/ 10.1098 / rspa.2017.0551

[11] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. Introdução aos Algoritmos. MIT Press, 4ª edição, 2022.

[12] P. Diaconis e D. Freedman. Sequências finitas trocáveis. The Annals of Probability, 8(4):745–764, 1980. URL: https:///​/​www.jstor.org/​stable/​2242823.
https: / / www.jstor.org/ stable / 2242823

[13] Christoph Dürr e Peter Høyer. Um algoritmo quântico para encontrar o mínimo, 1996. doi:10.48550/​arXiv.quant-ph/​9607014.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9607014
arXiv: quant-ph / 9607014

[14] Christoph Dürr, Mark Heiligman, Peter Høyer e Mehdi Mhalla. Complexidade de consulta quântica de alguns problemas gráficos. SIAM Journal on Computing, 35(6):1310–1328, janeiro de 2006. doi:10.1137/​050644719.
https: / / doi.org/ 10.1137 / 050644719

[15] Paul Dagum, Richard Karp, Michael Luby e Sheldon Ross. Um algoritmo ótimo para estimativa de Monte Carlo. SIAM Journal on Computing, 29(5):1484–1496, janeiro de 2000. doi:10.1137/​S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

[16] Vittorio Giovannetti, Seth Lloyd e Lorenzo Maccone. Memória quântica de acesso aleatório. Physical Review Letters, 100(16), abril de 2008. doi:10.1103/​physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

[17] Sander Gribling e Harold Nieuwboer. Limites inferior e superior quânticos aprimorados para dimensionamento de matriz. Em Anais do 39º Simpósio Internacional sobre Aspectos Teóricos da Ciência da Computação (STACS'22), volume 219, páginas 35:1–35:23, 2022. arXiv:2109.15282, doi:10.4230/​LIPIcs.STACS.2022.35.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2022.35
arXiv: 2109.15282

[18] Mart de Graaf e Ronald de Wolf. Sobre versões quânticas do princípio Yao. No 19º Simpósio sobre Aspectos Teóricos da Ciência da Computação (STACS'02), volume 2285 de Lecture Notes in Computer Science, páginas 347–358, Berlim, Heidelberg, 2002. Springer. doi:10.1007/​3-540-45841-7_28.
https:/​/​doi.org/​10.1007/​3-540-45841-7_28

[19] Lov K. Grover. Um algoritmo de mecânica quântica rápido para pesquisa em banco de dados. Em Anais do 38º Simpósio Anual ACM sobre Teoria da Computação (STOC'96), páginas 212–219, 1996. arXiv:quant-ph/​9605043, doi:10.1145/​237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: quant-ph / 9605043

[20] Lov K. Grover. Telecomputação quântica, 1997. Memorando Técnico Bell Labs ITD97-31630F. doi:10.48550/​arXiv.quant-ph/​9704012.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9704012
arXiv: quant-ph / 9704012

[21] Lov K. Grover. Uma estrutura para algoritmos de mecânica quântica rápidos. Em Anais do Trigésimo Simpósio Anual ACM sobre Teoria da Computação (STOC'98), páginas 53–62, 1998. arXiv:quant-ph/​9711043, doi:10.1145/​276698.276712.
https: / / doi.org/ 10.1145 / 276698.276712
arXiv: quant-ph / 9711043

[22] Yassine Hamoudi. Estimador Quântico de Média Sub-Gaussiana. No 29º Simpósio Europeu Anual de Algoritmos (ESA 2021), volume 204 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 50:1–50:17, 2021. doi:10.4230/​LIPIcs.ESA.2021.50.
https://​/​doi.org/​10.4230/​LIPIcs.ESA.2021.50

[23] Svante Janson. Limites finais para somas de variáveis ​​geométricas e exponenciais. Cartas de Estatística e Probabilidade, 135:1–6, 2018. doi:10.1016/​j.spl.2017.11.017.
https://​/​doi.org/​10.1016/​j.spl.2017.11.017

[24] Donald Ervin Knuth. A Arte da Programação de Computadores, volume III. Addison-Wesley, 2ª edição, 1998. URL: https://www.worldcat.org/​oclc/​312994415.
https://www.worldcat.org/​oclc/​312994415

[25] Robin Kothari e Ryan O'Donnell. Estimativa média quando você tem o código-fonte; ou métodos quânticos de Monte Carlo. Em Anais do Simpósio Anual ACM-SIAM sobre Algoritmos Discretos de 2023 (SODA'23), páginas 1186–1215, 2023. doi:10.1137/​1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[26] Michael A. Nielsen e Isaac L. Chuang. Computação quântica e informação quântica. Cambridge University Press, 2002.

[27] Ashwin Nayak e Felix Wu. A complexidade da consulta quântica para aproximar a mediana e as estatísticas relacionadas. Em Anais do 31º Simpósio Anual ACM SIGACT sobre Teoria da Computação (STOC'99), páginas 384–393, 1999. arXiv:quant-ph/​9804066, doi:10.1145/​301250.301349.
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: quant-ph / 9804066

[28] B. Roos. Aproximação Binomial à Distribuição Binomial de Poisson: A Expansão de Krawtchouk. Teoria da Probabilidade e Suas Aplicações, 45(2):258–272, 2001. doi:10.1137/​S0040585X9797821X.
https://​/​doi.org/​10.1137/​S0040585X9797821X

[29] Robert M. Jovem. 75.9 Constante de Euler. The Mathematical Gazette, 75(472):187–190, 1991. doi:10.2307/​3620251.
https: / / doi.org/ 10.2307 / 3620251

Citado por

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