Departamento de Ciencias de la Computación, Universidad de Texas en Austin, Austin, TX 78712, EE. UU.
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
Una propuesta líder para verificar experimentos de supremacía cuántica a corto plazo en circuitos cuánticos aleatorios ruidosos es la evaluación comparativa lineal de entropía cruzada. Para un circuito cuántico $ C $ en $ n $ qubits y una muestra $ z en {0,1} ^ n $, el punto de referencia implica calcular $ | langle z | C | 0 ^ n rangle | ^ 2 $, es decir, la probabilidad de medir $ z $ a partir de la distribución de salida de $ C $ en la entrada de todos ceros. Bajo una fuerte conjetura sobre la dureza clásica de estimar las probabilidades de salida de los circuitos cuánticos, ningún algoritmo clásico de tiempo polinomial dado $ C $ puede generar una cadena $ z $ tal que $ | langle z | C | 0 ^ nrangle | ^ 2 $ es sustancialmente mayor que $ frac {1} {2 ^ n} $ (Aaronson y Gunn, 2019). Por otro lado, para un circuito cuántico aleatorio $ C $, el muestreo de $ z $ de la distribución de salida de $ C $ logra $ | langle z | C | 0 ^ nrangle | ^ 2 approx frac {2} {2 ^ n} $ en promedio (Arute et al., 2019).
En analogía con la desigualdad de Tsirelson de las correlaciones cuánticas no locales, preguntamos: ¿puede un algoritmo cuántico de tiempo polinomial funcionar sustancialmente mejor que $ frac {2} {2 ^ n} $? Estudiamos esta pregunta en el modelo de consulta (o caja negra), donde el algoritmo cuántico tiene acceso de Oracle a $ C $. Mostramos que, para cualquier $ varepsilon ge frac {1} {mathrm {poly} (n)} $, se genera una muestra $ z $ tal que $ | langle z | C | 0 ^ nrangle | ^ 2 ge frac {2 + varepsilon} {2 ^ n} $ en promedio requiere al menos $ Omegaleft (frac {2 ^ {n / 4}} {mathrm {poly} (n)} right) $ consultas a $ C $, pero no más de $ Oleft (2 ^ {n / 3} derecha) $ consultas a $ C $, si $ C $ es un unitario de $ n $ -qubit aleatorio de Haar, o un oráculo de preparación de estado canónico para un $ n $ -qubit aleatorio de Haar estado. También mostramos que cuando $ C $ toma muestras de la distribución de Fourier de una función booleana aleatoria, el algoritmo ingenuo que toma muestras de $ C $ es el algoritmo óptimo de 1 consulta para maximizar $ | langle z | C | 0 ^ nrangle | ^ 2 $ en promedio.
Resumen popular
Argumentamos que este límite superior en el poder de los algoritmos clásicos para el XEB lineal es análogo a la desigualdad de Bell en las correlaciones no locales: ambos capturan límites inherentes al poder de la información clásica y el cálculo que pueden violarse en la configuración cuántica. Motivados por esta conexión, preguntamos: ¿cuál es el análogo de supremacía cuántica de la desigualdad de Tsirelson? Es decir, ¿cuál es la puntuación XEB lineal más alta que se puede lograr mediante un algoritmo cuántico eficiente? Damos evidencia de que el algoritmo cuántico ingenuo para pasar el punto de referencia es esencialmente óptimo en este sentido.
► datos BibTeX
► referencias
[ 1 ] Scott Aaronson. Muestreo de circuitos aleatorios: pensamientos y problemas abiertos. The Quantum Wave in Computing, 2020. URL https: / / simons.berkeley.edu/ starts / tbd-124.
https: / / simons.berkeley.edu/conversaciones / tbd-124
[ 2 ] Scott Aaronson y Lijie Chen. Fundamentos teóricos de la complejidad de los experimentos de supremacía cuántica. En Ryan O'Donnell, editor, 32nd Computational Complexity Conference (CCC 2017), volumen 79 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 22: 1–22: 67, Dagstuhl, Alemania, 2017. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-040-8. 10.4230 / LIPIcs.CCC.2017.22. URL http: / / drops.dagstuhl.de/ opus / volltexte / 2017/7527.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.22
http: / / drops.dagstuhl.de/ opus / volltexte / 2017/7527
[ 3 ] Scott Aaronson y Sam Gunn. Sobre la dureza clásica de la suplantación de la evaluación comparativa lineal de entropía cruzada. Teoría de la Computación, 16 (11): 1–8, 2020. 10.4086 / toc.2020.v016a011. URL http: / / www.theoryofcomputing.org/ articles / v016a011.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
http: / / www.theoryofcomputing.org/ articles / v016a011
[ 4 ] Scott Aaronson, Robin Kothari, William Kretschmer y Justin Thaler. Límites inferiores cuánticos para el recuento aproximado mediante polinomios de Laurent. En Shubhangi Saraf, editor, 35th Computational Complexity Conference (CCC 2020), volumen 169 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 7: 1–7: 47, Dagstuhl, Alemania, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik . ISBN 978-3-95977-156-6. 10.4230 / LIPIcs.CCC.2020.7. URL https: / / drops.dagstuhl.de/ opus / volltexte / 2020/12559.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2020.7
https: / / drops.dagstuhl.de/ opus / volltexte / 2020/12559
[ 5 ] Dorit Aharonov, Alexei Kitaev y Noam Nisan. Circuitos cuánticos con estados mixtos. En Actas del Trigésimo Simposio Anual de ACM sobre Teoría de la Computación, STOC '98, páginas 20–30, Nueva York, NY, EE. UU., 1998. Association for Computing Machinery. ISBN 0897919629. 10.1145 / 276698.276708. URL https: / / doi.org/ 10.1145 / 276698.276708.
https: / / doi.org/ 10.1145 / 276698.276708
[ 6 ] Andris Ambainis. Comprender los algoritmos cuánticos a través de la complejidad de las consultas. En Actas del Congreso Internacional de Matemáticos de 2018, volumen 3, páginas 3249–3270, 2018. 10.1142 / 9789813272880_0181.
https: / / doi.org/ 10.1142 / 9789813272880_0181
[ 7 ] Andris Ambainis, Loïck Magnin, Martin Roetteler y Jeremie Roland. Adversarios asistidos por simetría para la generación de estados cuánticos. En Actas de la 2011ª Conferencia Anual de IEEE 26 sobre Complejidad Computacional, CCC '11, páginas 167–177, EE. UU., 2011. IEEE Computer Society. ISBN 9780769544113. 10.1109 / CCC.2011.24. URL https: / / doi.org/ 10.1109 / CCC.2011.24.
https: / / doi.org/ 10.1109 / CCC.2011.24
[ 8 ] Andris Ambainis, Ansis Rosmanis y Dominique Unruh. Ataques cuánticos en sistemas de prueba clásicos: la dureza del rebobinado cuántico. En Actas del 2014º Simposio Anual de IEEE 55 sobre los fundamentos de la informática, FOCS '14, páginas 474–483, EE. UU., 2014. IEEE Computer Society. ISBN 9781479965175. 10.1109 / FOCS.2014.57. URL https: / / doi.org/ 10.1109 / FOCS.2014.57.
https: / / doi.org/ 10.1109 / FOCS.2014.57
[ 9 ] Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis y Ronald de Wolf. Colector de cupones cuánticos. En Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volumen 158 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 10: 1–10: 17, Dagstuhl, Alemania, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-146-7. 10.4230 / LIPIcs.TQC.2020.10. URL https: / / drops.dagstuhl.de/ opus / volltexte / 2020/12069.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.10
https: / / drops.dagstuhl.de/ opus / volltexte / 2020/12069
[ 10 ] Frank Arute, Kunal Arya, Ryan Babbush, et al. Supremacía cuántica utilizando un procesador superconductor programable. Nature, 574 (7779): 505–510, 2019. 10.1038 / s41586-019-1666-5. URL https: / / doi.org/ 10.1038 / s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5
[ 11 ] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca y Ronald de Wolf. Límites inferiores cuánticos por polinomios. J. ACM, 48 (4): 778–797, julio de 2001. ISSN 0004-5411. 10.1145 / 502090.502097. URL https: / / doi.org/ 10.1145 / 502090.502097.
https: / / doi.org/ 10.1145 / 502090.502097
[ 12 ] John Bell. Sobre la paradoja de Einstein-Podolsky-Rosen. Physics, 1: 195-200, noviembre de 1964. 10.1103 / PhysicsPhysiqueFizika.1.195. URL https: / / link.aps.org/ doi / 10.1103 / PhysicsPhysiqueFizika.1.195.
https: / / doi.org/ 10.1103 / PhysicsPhysiqueFizika.1.195
[ 13 ] Aleksandrs Belovs. Variaciones sobre el adversario cuántico, 2015.
arXiv: 1504.06943
[ 14 ] Aleksandrs Belovs y Ansis Rosmanis. Límite inferior cuántico estrecho para el recuento aproximado con estados cuánticos, 2020.
arXiv: 2002.06879
[ 15 ] Fernando GSL Brandão, Aram W. Harrow y Michał Horodecki. Los circuitos cuánticos aleatorios locales son diseños polinomiales aproximados. Communications in Mathematical Physics, 346 (2): 397–434, 2016. 10.1007 / s00220-016-2706-8. URL https: / / doi.org/ 10.1007 / s00220-016-2706-8.
https://doi.org/10.1007/s00220-016-2706-8
[ 16 ] Gilles Brassard, Peter Høyer y Alain Tapp. Criptoanálisis cuántico de funciones hash y sin garras. SIGACT News, 28 (2): 14-19, junio de 1997. ISSN 0163-5700. 10.1145 / 261342.261346. URL https: / / doi.org/ 10.1145 / 261342.261346.
https: / / doi.org/ 10.1145 / 261342.261346
[ 17 ] 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, volumen 305 de Matemáticas contemporáneas, páginas 53–74. Sociedad Americana de Matemáticas, 2002. ISBN 9780821821404. 10.1090 / conm / 305.
https: / / doi.org/ 10.1090 / conm / 305
[ 18 ] Mark Bun y Justin Thaler. Límites inferiores dobles para grados aproximados y desigualdades de Markov-Bernstein. Inf. Comput., 243 (C): 2–25, agosto de 2015. ISSN 0890-5401. 10.1016 / j.ic.2014.12.003. URL https: / / doi.org/ 10.1016 / j.ic.2014.12.003.
https: / / doi.org/ 10.1016 / j.ic.2014.12.003
[ 19 ] Boris Cirel'son (Tsirelson). Generalizaciones cuánticas de la desigualdad de Bell. Letters in Mathematical Physics, 4 (2): 93-100, 1980. 10.1007 / BF00417500. URL https: / / doi.org/ 10.1007 / BF00417500.
https: / / doi.org/ 10.1007 / BF00417500
[ 20 ] John F. Clauser, Michael A. Horne, Abner Shimony y Richard A. Holt. Experimento propuesto para probar las teorías locales de variables ocultas. Phys. Rev. Lett., 23: 880–884, octubre de 1969. 10.1103 / PhysRevLett.23.880. URL https: / / link.aps.org/ doi / 10.1103 / PhysRevLett.23.880.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[ 21 ] Richard Cleve, Peter Høyer, Benjamin Toner y John Watrous. Consecuencias y límites de las estrategias no locales. En Actas de la 19ª Conferencia Anual de IEEE sobre Complejidad Computacional, CCC '04, páginas 236–249, EE.UU., 2004. IEEE Computer Society. ISBN 0769521207. 10.1109 / CCC.2004.1313847.
https: / / doi.org/ 10.1109 / CCC.2004.1313847
[ 22 ] Aram Harrow y Saeed Mehraban. Diseños t unitarios aproximados por circuitos cuánticos aleatorios cortos utilizando puertas de largo alcance y vecino más cercano, 2018.
arXiv: 1809.06957
[ 23 ] Norman L. Johnson y Samuel Kotz. Modelos de urnas y su aplicación: una aproximación a la teoría de probabilidad discreta moderna. Wiley, 1977. ISBN 9780471446309.
[ 24 ] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols y Theodore J. Yoder. Simulación hamiltoniana con una complejidad de muestra óptima. npj Quantum Information, 3 (1): 13, 2017. 10.1038 / s41534-017-0013-7. URL https: / / doi.org/ 10.1038 / s41534-017-0013-7.
https://doi.org/10.1038/s41534-017-0013-7
[ 25 ] William Kretschmer. La desigualdad de Tsirelson de la supremacía cuántica. En James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volumen 185 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 13: 1–13: 13, Dagstuhl, Alemania, 2021. Schloss Dagstuhl– Leibniz-Zentrum für Informatik. ISBN 978-3-95977-177-1. 10.4230 / LIPIcs.ITCS.2021.13. URL https: / / drops.dagstuhl.de/ opus / volltexte / 2021/13552.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2021.13
https: / / drops.dagstuhl.de/ opus / volltexte / 2021/13552
[ 26 ] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek y Mario Szegedy. Complejidad de la consulta cuántica de conversión de estado. En Actas del 2011º Simposio Anual de IEEE 52 sobre los fundamentos de la informática, FOCS '11, páginas 344–353, EE.UU., 2011. IEEE Computer Society. ISBN 9780769545714. 10.1109 / FOCS.2011.75. URL https: / / doi.org/ 10.1109 / FOCS.2011.75.
https: / / doi.org/ 10.1109 / FOCS.2011.75
[ 27 ] Nathan Lindzey y Ansis Rosmanis. Un límite inferior ajustado para el borrado de índice no coherente. En Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volumen 151 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 59: 1–59: 37, Dagstuhl, Alemania, 2020. Schloss Dagstuhl – Leibniz- Zentrum fuer Informatik. ISBN 978-3-95977-134-4. 10.4230 / LIPIcs.ITCS.2020.59. URL https: / / drops.dagstuhl.de/ opus / volltexte / 2020/11744.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2020.59
https: / / drops.dagstuhl.de/ opus / volltexte / 2020/11744
[ 28 ] Frederic Magniez, Ashwin Nayak, Jeremie Roland y Miklos Santha. Búsqueda a través de la caminata cuántica. En Actas del Trigésimo Noveno Simposio Anual de ACM sobre Teoría de la Computación, STOC '07, páginas 575–584, Nueva York, NY, EE. UU., 2007. Association for Computing Machinery. ISBN 9781595936318. 10.1145 / 1250790.1250874. URL https: / / doi.org/ 10.1145 / 1250790.1250874.
https: / / doi.org/ 10.1145 / 1250790.1250874
[ 29 ] Ryan O'Donnell. Análisis de funciones booleanas. Cambridge University Press, EE. UU., 2014. ISBN 1107038324. 10.1017 / CBO9781139814782.
https: / / doi.org/ 10.1017 / CBO9781139814782
[ 30 ] Martin Raab y Angelika Steger. "Bolas en contenedores": un análisis simple y estricto. En Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM '98, páginas 159-170, Berlín, Heidelberg, 1998. Springer-Verlag. ISBN 354065142X. 10.1007 / 3-540-49543-6_13.
https://doi.org/10.1007/3-540-49543-6_13
[ 31 ] Ben W. Reichardt. Reflexiones para algoritmos de consulta cuántica. En Actas del Vigésimo Segundo Simposio Anual ACM-SIAM sobre Algoritmos Discretos, SODA '11, páginas 560–569, EE.UU., 2011. Sociedad de Matemáticas Industriales y Aplicadas. 10.1137 / 1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44
[ 32 ] Alfréd Rényi. Sobre la teoría de la estadística de orden. Acta Mathematica Academiae Scientiarum Hungarica, 4 (3): 191-231, 1953. 10.1007 / BF02127580. URL https: / / doi.org/ 10.1007 / BF02127580.
https: / / doi.org/ 10.1007 / BF02127580
Citado por
[1] Daniel Stilck França y Raul García-Patrón, "Un juego de ventaja cuántica: vincular verificación y simulación", arXiv: 2011.12173.
[2] Nicholas LaRacuente, "Separaciones de Oracle cuántico de estados complejos pero fácilmente especificados", arXiv: 2104.07247.
[3] Scott Aaronson, "Problemas abiertos relacionados con la complejidad de las consultas cuánticas", arXiv: 2109.06917.
Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2021-10-07 11:15:15). La lista puede estar incompleta ya que no todos los editores proporcionan datos de citas adecuados y completos.
No se pudo recuperar Crossref citado por datos durante el último intento 2021-10-07 11:15:13: No se pudieron obtener los datos citados por 10.22331 / q-2021-10-07-560 de Crossref. Esto es normal si el DOI se registró recientemente.
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.
PlatoAi. Web3 reinventado. Inteligencia de datos ampliada.
Haga clic aquí para acceder.
Fuente: https://quantum-journal.org/papers/q-2021-10-07-560/
