A verificação do caso médio da transformada quântica de Fourier permite a estimativa da fase do pior caso PlatoBlockchain Data Intelligence. Pesquisa vertical. Ai.

A verificação de caso médio da transformada quântica de Fourier permite a estimativa da fase de pior caso

Carimbo de data / hora: 7 de dezembro de 2022 11h15

Noah Linden1 e Ronald de Wolf2

1Escola de Matemática, Universidade de Bristol. n.linden@bristol.ac.uk
2QuSoft, CWI e Universidade de Amsterdã, Holanda. rdewolf@cwi.nl

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

Sumário

A transformada quântica de Fourier (QFT) é uma chave primitiva para a computação quântica que é normalmente usada como uma sub-rotina dentro de uma computação maior, por exemplo, para estimativa de fase. Como tal, podemos ter pouco controle sobre o estado que é inserido no QFT. Assim, ao implementar um bom QFT, podemos imaginar que ele precisa ter um bom desempenho em estados de entrada arbitrários. $Verificar$ esse comportamento correto de pior caso de uma implementação de QFT seria exponencialmente difícil (no número de qubits) em geral, levantando a preocupação de que essa verificação seria impossível na prática em qualquer sistema de tamanho útil. Neste artigo, mostramos que, de fato, precisamos apenas ter um bom desempenho $average$-$case$ do QFT para obter um bom desempenho $worst$-$case$ para tarefas-chave – estimativa de fase, localização de período e estimativa de amplitude . Além disso, fornecemos um procedimento muito eficiente para verificar esse comportamento de caso médio exigido da QFT.

Resumo popular

A transformada quântica de Fourier (QFT) é uma chave primitiva que normalmente é usada como uma sub-rotina dentro de uma computação quântica maior. Como tal, podemos ter pouco controle sobre o estado que é inserido no QFT. Mostramos que o bom desempenho do QFT em um estado de entrada $average$ (1) é testável com eficiência e (2) é suficiente para alcançar um bom desempenho de $worst$-$case$ para tarefas baseadas em QFT, como estimativa de fase, localização de período e estimativa de amplitude.

► dados BibTeX

► Referências

[1] Scott Aaronson e Patrick Rall. Contagem quântica aproximada, simplificada. In Proceedings of 3rd Symposium on Simplicity in Algorithms (SOSA), páginas 24–32, 2020. arXiv:1908.10846.
https: / / doi.org/ 10.1137 / 1.9781611976014.5
arXiv: 1908.10846

[2] Charles H. Bennett, Ethan Bernstein, Gilles Brassard e Umesh Vazirani. Pontos fortes e fracos da computação quântica. SIAM Journal on Computing, 26(5):1510–1523, 1997. quant-ph/9701001.
https: / / doi.org/ 10.1137 / S0097539796300933
arXiv: quant-ph / 9701001

[3] 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 da AMS Contemporary Mathematics Series, páginas 53–74. 2002. quant-ph/​0005055.
https: / / doi.org/ 10.1090 / conm / 305/05215
arXiv: quant-ph / 0005055

[4] Chi-Fang Chen e Fernando GSL Brandão. Concentração para erro Trotter. arXiv:2111.05324, 9 de novembro de 2021.
https://​/​doi.org/​10.48550/​arXiv.2111.05324
arXiv: 2111.05324

[5] Richard Cleve, Artur Ekert, Chiara Macchiavello e Michele Mosca. Algoritmos quânticos revisitados. Em Proceedings of the Royal Society of London, volume A454, páginas 339–354, 1998. quant-ph/9708016.
https: / / doi.org/ 10.1098 / rspa.1998.0164
arXiv: quant-ph / 9708016

[6] Dom Coppersmith. Uma transformada aproximada de Fourier útil na fatoração quântica. Relatório de pesquisa IBM nº RC19642, quant-ph/0201067, 1994.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​0201067
arXiv: quant-ph / 0201067

[7] Marcus da Silva, Oliver Landon-Cardinal e David Poulin. Caracterização prática de dispositivos quânticos sem tomografia. Physical Review Letters, 107:210404, 2011. arXiv:1104.3835.
https: / / doi.org/ 10.1103 / PhysRevLett.107.210404
arXiv: 1104.3835

[8] Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud e Elham Kashefi. Certificação quântica e benchmarking. Nature Reviews Physics, 2:382–390, 2020. arXiv:1910.06343.
https:/​/​doi.org/​10.1038/​s42254-020-0186-4
arXiv: 1910.06343

[9] Steven T. Flammia e Yi-Kai Liu. Estimativa de fidelidade direta a partir de poucas medições de Pauli. Physical Review Letters, 106:230501, 2011. arXiv:1104.4695.
https: / / doi.org/ 10.1103 / PhysRevLett.106.230501
arXiv: 1104.4695

[10] András Gilyén, Srinivasan Arunachalam e Nathan Wiebe. Otimizando algoritmos de otimização quântica por meio de computação de gradiente quântico mais rápida. Em Proceedings of 30th ACM-SIAM SODA, páginas 1425–1444, 2019. arXiv:1711.00465.
https: / / doi.org/ 10.1137 / 1.9781611975482.87
arXiv: 1711.00465

[11] Amor K. Grover. Um algoritmo mecânico quântico rápido para pesquisa de banco de dados. In Proceedings of 28th ACM STOC, pages 212–219, 1996. quant-ph/​9605043.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: quant-ph / 9605043

[12] András Gilyén, Yuan Su, Guang Hao Low e Nathan Wiebe. Transformação de valor singular quântico e além: melhorias exponenciais para aritmética de matriz quântica. In Proceedings of 51st ACM STOC, páginas 193–204, 2019. arXiv:1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838

[13] Stephen P. Jordan. Algoritmo quântico rápido para estimativa de gradiente numérico. Physical Review Letters, 95:050501, 2005. quant-ph/​0405146.
https: / / doi.org/ 10.1103 / PhysRevLett.95.050501
arXiv: quant-ph / 0405146

[14] Alexei Yu. Kitaev. Medições quânticas e o problema do estabilizador abeliano. quant-ph/​9511026, 12 de novembro de 1995.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9511026
arXiv: quant-ph / 9511026

[15] Noah Linden e Ronald de Wolf. Detecção leve de um pequeno número de grandes erros em um circuito quântico. Quantum, 5(436), 2021. arXiv:2009.08840.
https:/​/​doi.org/​10.22331/​q-2021-04-20-436
arXiv: 2009.08840

[16] Urmila Mahadev. Verificação clássica de cálculos quânticos. Em Proceedings of 59th IEEE FOCS, páginas 259–267, 2018. arXiv:1804.01082.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
arXiv: 1804.01082

[17] John M. Martyn, Zane M. Rossi, Andrew K. Tan e Isaac L. Chuang. Uma grande unificação de algoritmos quânticos. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203

[18] Michael A. Nielsen e Isaac L. Chuang. Computação Quântica e Informação Quântica. Cambridge University Press, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667

[19] Patrick Rall. Algoritmos quânticos coerentes mais rápidos para estimativa de fase, energia e amplitude. Quantum, 5(566), 2021. arXiv:2103.09717.
https:/​/​doi.org/​10.22331/​q-2021-10-19-566
arXiv: 2103.09717

[20] Peter W. Shor. Algoritmos de tempo polinomial para fatoração primária e logaritmos discretos em um computador quântico. SIAM Journal on Computing, 26(5):1484–1509, 1997. Versão anterior em FOCS'94. quant-ph/​9508027.
https: / / doi.org/ 10.1137 / S0097539795293172
arXiv: quant-ph / 9508027

[21] Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li e Andrew M. Childs. Simulação hamiltoniana com entradas aleatórias. arXiv:2111.04773, 8 de novembro de 2021.
https://​/​doi.org/​10.48550/​arXiv.2111.04773
arXiv: 2111.04773

Citado por

[1] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén e Giacomo Nannicini, “Tomografia quântica usando unidades de preparação de estado”, arXiv: 2207.08800.

As citações acima são de SAO / NASA ADS (última atualização com êxito 2022-12-08 04:24:57). 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-12-08 04:24:56).

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