1Escuela de Matemáticas, Universidad de Bristol. n.linden@bristol.ac.uk
2QuSoft, CWI y Universidad de Ámsterdam, Países Bajos. rdewolf@cwi.nl
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
La transformada cuántica de Fourier (QFT) es una primitiva clave para la computación cuántica que generalmente se usa como una subrutina dentro de una computación más grande, por ejemplo, para la estimación de fase. Como tal, es posible que tengamos poco control sobre el estado que se ingresa al QFT. Por lo tanto, al implementar un buen QFT, podemos imaginar que debe funcionar bien en estados de entrada arbitrarios. $Verificar$ este comportamiento correcto en el peor de los casos de una implementación de QFT sería exponencialmente difícil (en la cantidad de qubits) en general, lo que genera la preocupación de que esta verificación sería imposible en la práctica en cualquier sistema de tamaño útil. En este artículo mostramos que, de hecho, solo necesitamos tener un buen rendimiento de $promedio$-$caso$ de la QFT para lograr un buen rendimiento de $peor$-$caso$ para tareas clave: estimación de fase, búsqueda de período y estimación de amplitud . Además, proporcionamos un procedimiento muy eficiente para verificar este comportamiento de caso promedio requerido de la QFT.
Resumen popular
► datos BibTeX
► referencias
[ 1 ] Scott Aaronson y Patrick Rall. Conteo aproximado cuántico, simplificado. En Actas del 3er Simposio sobre Simplicidad en Algoritmos (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 y Umesh Vazirani. Fortalezas y debilidades de la computación cuá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 y Alain Tapp. Amplificación y estimación de amplitud cuántica. En Computación cuántica e información cuántica: un volumen del milenio, volumen 305 de la serie AMS Contemporary Mathematics, páginas 53–74. 2002. quant-ph / 0005055.
https: / / doi.org/ 10.1090 / conm / 305/05215
arXiv: quant-ph / 0005055
[ 4 ] Chi-Fang Chen y Fernando GSL Brandão. Concentración por error de Trotter. arXiv:2111.05324, 9 de noviembre de 2021.
https:///doi.org/10.48550/arXiv.2111.05324
arXiv: 2111.05324
[ 5 ] Richard Cleve, Artur Ekert, Chiara Macchiavello y Michele Mosca. Algoritmos cuánticos revisados. En Proceedings of the Royal Society of London, volumen A454, páginas 339–354, 1998. quant-ph/9708016.
https: / / doi.org/ 10.1098 / rspa.1998.0164
arXiv: quant-ph / 9708016
[ 6 ] Don Calderero. Una transformada de Fourier aproximada útil en la factorización cuántica. Informe de investigación de IBM No. RC19642, quant-ph/0201067, 1994.
https://doi.org/10.48550/arXiv.quant-ph/0201067
arXiv: quant-ph / 0201067
[ 7 ] Marcus da Silva, Oliver Landon-Cardenal y David Poulin. Caracterización práctica de dispositivos cuánticos sin tomografía. Cartas de revisión física, 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 y Elham Kashefi. Certificación cuántica y 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 y Yi-Kai Liu. Estimación de fidelidad directa a partir de algunas medidas de Pauli. Cartas de revisión física, 106:230501, 2011. arXiv:1104.4695.
https: / / doi.org/ 10.1103 / PhysRevLett.106.230501
arXiv: 1104.4695
[ 10 ] András Gilyén, Srinivasan Arunachalam y Nathan Wiebe. Optimización de algoritmos de optimización cuántica a través de un cálculo de gradiente cuántico más rápido. En 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 ] Lov K. Grover. Un algoritmo rápido de mecánica cuántica para la búsqueda de bases de datos. En Proceedings of 28th ACM STOC, páginas 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 y Nathan Wiebe. Transformación cuántica de valores singulares y más allá: mejoras exponenciales para la aritmética de matrices cuánticas. En Procedimientos de 51st ACM STOC, páginas 193–204, 2019. arXiv:1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838
[ 13 ] Esteban P. Jordan. Algoritmo cuántico rápido para la estimación numérica de gradientes. 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. Mediciones cuánticas y el problema del estabilizador abeliano. quant-ph/9511026, 12 de noviembre de 1995.
https://doi.org/10.48550/arXiv.quant-ph/9511026
arXiv: quant-ph / 9511026
[ 15 ] Noah Linden y Ronald de Wolf. Detección ligera de un pequeño número de grandes errores en un circuito cuántico. Cuántica, 5(436), 2021. arXiv:2009.08840.
https://doi.org/10.22331/q-2021-04-20-436
arXiv: 2009.08840
[ 16 ] Urmila Mahadev. Verificación clásica de cálculos cuánticos. En 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. Una gran unificación de algoritmos cuá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. Computación Cuántica e Información Cuántica. Prensa de la Universidad de Cambridge, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667
[ 19 ] Patricio Rall. Algoritmos cuánticos coherentes más rápidos para la estimación de fase, energía y amplitud. Cuántica, 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 tiempo polinomial para factorización prima y logaritmos discretos en una computadora cuántica. SIAM Journal on Computing, 26(5):1484–1509, 1997. Versión anterior en 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 y Andrew M. Childs. Simulación hamiltoniana con entradas aleatorias. arXiv:2111.04773, 8 de noviembre 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 y Giacomo Nannicini, “Quantum tomography using state-preparation unitaries”, arXiv: 2207.08800.
Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2022-12-08 04:24:57). La lista puede estar incompleta ya que no todos los editores proporcionan datos de citas adecuados y completos.
On Servicio citado por Crossref no se encontraron datos sobre las obras citadas (último intento 2022-12-08 04:24:56).
Este documento se publica en Quantum bajo el Creative Commons Reconocimiento 4.0 Internacional (CC BY 4.0) licencia. Los derechos de autor permanecen con los titulares de derechos de autor originales, como los autores o sus instituciones.
