1Departamento de Física, ETH Zürich, Suiza
2Instituto de Estudios Teóricos, ETH Zürich, Suiza
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
Una prueba de cuántica es un tipo de protocolo de desafío-respuesta en el que un verificador clásico puede certificar de manera eficiente la $textit{ventaja cuántica}$ de un probador que no es de confianza. Es decir, un probador cuántico puede responder correctamente a los desafíos del verificador y ser aceptado, mientras que cualquier probador clásico en tiempo polinomial será rechazado con alta probabilidad, basándose en supuestos computacionales plausibles. Para responder a los desafíos del verificador, las pruebas existentes de cuántica generalmente requieren que el probador cuántico realice una combinación de circuitos y mediciones cuánticos de tamaño polinomial.
En este artículo, damos dos pruebas de construcciones cuánticas en las que el probador solo necesita realizar $textit{circuitos cuánticos de profundidad constante}$ (y mediciones) junto con el cálculo clásico de profundidad logarítmica. Nuestra primera construcción es un compilador genérico que nos permite traducir todas las pruebas existentes de cuántica en versiones de profundidad cuántica constante. Nuestra segunda construcción se basa en el problema de $textit{aprendizaje con redondeo}$ y produce circuitos con una profundidad más corta y que requieren menos qubits que la construcción genérica. Además, la segunda construcción también presenta cierta robustez frente al ruido.
► datos BibTeX
► referencias
[ 1 ] Scott Aaronson y Alex Arkhipov. La complejidad computacional de la óptica lineal. En Actas del cuadragésimo tercer simposio anual de ACM sobre teoría de la informática, páginas 333–342, 2011.
https: / / doi.org/ 10.1145 / 1993636.1993682
[ 2 ] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Supremacía cuántica utilizando un procesador superconductor programable. Naturaleza, 574(7779):505–510, 2019.
https://doi.org/10.1038/s41586-019-1666-5
[ 3 ] MD SAJID ANIS, Abby-Mitchell, Héctor Abraham, AduOffei, et al. Qiskit: un marco de código abierto para la computación cuántica, 2021.
[ 4 ] Sanjeev Arora y Boaz Barak. Complejidad computacional: un enfoque moderno. Prensa de la Universidad de Cambridge, 2009.
[ 5 ] Scott Aaronson y Lijie Chen. Fundamentos teóricos de la complejidad de los experimentos de supremacía cuántica. En Actas de la 32ª Conferencia sobre Complejidad Computacional, CCC '17, páginas 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
[ 6 ] Scott Aaronson y Sam Gunn. Sobre la dureza clásica de la falsificación de la evaluación comparativa de entropía cruzada lineal. Teoría de la Computación, 16(11):1–8, 2020.
https: / / doi.org/ 10.4086 / toc.2020.v016a011
[ 7 ] B. Applebaum, Y. Ishai y E. Kushilevitz. Criptografía en ${NC}^0$. En 45º Simposio anual del IEEE sobre fundamentos de la informática, páginas 166–175, 2004.
https: / / doi.org/ 10.1109 / FOCS.2004.20
[ 8 ] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak y Daniel Wichs. Aprender con redondeo, revisado. En Advances in Cryptology – CRYPTO 2013, páginas 57–74, Berlín, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[ 9 ] David A. Barrington. Los programas de ramificación de tamaño polinomial de ancho limitado reconocen exactamente esos idiomas en ${NC}^1$. Revista de Ciencias de la Computación y Sistemas, 38(1):150–164, 1989.
https://doi.org/10.1016/0022-0000(89)90037-8
[ 10 ] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani y Thomas Vidick. Una prueba criptográfica de cuántica y aleatoriedad certificable desde un único dispositivo cuántico. En 2018, 59.º Simposio anual del IEEE sobre fundamentos de la informática (FOCS), páginas 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[ 11 ] Colin D. Bruzewicz, John Chiaverini, Robert McConnell y Jeremy M. Sage. Computación cuántica de iones atrapados: avances y desafíos. Reseñas de Física Aplicada, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[ 12 ] Adam Bouland, Bill Fefferman, Chinmay Nirkhe y Umesh Vazirani. Sobre la complejidad y verificación del muestreo de circuitos aleatorios cuánticos. Física de la naturaleza, 15(2):159–163, febrero de 2019.
https://doi.org/10.1038/s41567-018-0318-2
[ 13 ] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis y Hartmut Neven. Caracterizando la supremacía cuántica en dispositivos a corto plazo. Física de la naturaleza, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[ 14 ] Zvika Brakerski, Venkata Koppula, Umesh Vazirani y Thomas Vidick. Pruebas más simples de cuántica. En la 15ª Conferencia sobre la Teoría de la Computación, la Comunicación y la Criptografía Cuánticas (TQC 2020), volumen 158 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 8:1–8:14, Dagstuhl, Alemania, 2020. Schloss Dagstuhl–Leibniz- Centro de informática.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[ 15 ] Abhishek Banerjee, Chris Peikert y Alon Rosen. Funciones pseudoaleatorias y celosías. En Avances en criptología - EUROCRYPT 2012, páginas 719–737. Springer Berlín Heidelberg, 2012.
https://doi.org/10.1007/978-3-642-29011-4_42
[ 16 ] John F Clauser, Michael A Horne, Abner Shimony y Richard A Holt. Experimento propuesto para probar teorías locales de variables ocultas. Cartas de revisión física, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[ 17 ] Matthew Coudron, Jalex Stark y Thomas Vidick. Cambiando localidad por tiempo: aleatoriedad certificable a partir de circuitos de baja profundidad. Comunicaciones en Física Matemática, 382(1):49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[ 18 ] Richard Cleve y John Watrous. Circuitos paralelos rápidos para la transformada cuántica de Fourier. En Actas del 41º Simposio Anual sobre Fundamentos de la Informática, páginas 526–536. IEEE, 2000.
https: / / doi.org/ 10.1109 / SFCS.2000.892140
[ 19 ] Pierre Dusart. Autour de la función que cuenta el nombre de nombres premiers. Tesis doctoral, Universidad de Limoges, 1998.
https://www.unilim.fr/laco/theses/1998/T1998_01.pdf
[ 20 ] Austin G Fowler, Matteo Mariantoni, John M Martinis y Andrew N Cleland. Códigos de superficie: hacia la computación cuántica práctica a gran escala. Revisión física A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[ 21 ] François Le Gall. Correspondencia privada, 2022.
[ 22 ] Craig Gidney y Martin Ekerå. Cómo factorizar enteros RSA de 2048 bits en 8 horas utilizando 20 millones de qubits ruidosos. Cuántico, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[ 23 ] Alexandru Gheorghiu y Matty J. Hoban. Es difícil estimar la entropía de las salidas de circuitos poco profundos. Preimpresión de arXiv arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[ 24 ] Shuichi Hirahara y François Le Gall. Prueba de cuántica con circuitos cuánticos de pequeña profundidad. En el 46.º Simposio internacional sobre fundamentos matemáticos de la informática (MFCS 2021), volumen 202 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 59:1–59:15, Dagstuhl, Alemania, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2021.59
[ 25 ] Aram W Harrow y Ashley Montanaro. Supremacía computacional cuántica. Naturaleza, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[ 26 ] Peter Høyer y Robert Špalek. La distribución cuántica es poderosa. Teoría de la Computación, 1(5):81–103, 2005.
https: / / doi.org/ 10.4086 / toc.2005.v001a005
[ 27 ] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi y Jianxin Chen. Simulación clásica de circuitos de supremacía cuántica. Preimpresión de arXiv arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[ 28 ] Gregory D. Kahanamoku-Meyer. Forjar datos cuánticos: derrotar clásicamente una prueba cuántica basada en IQP. Preimpresión de arXiv arXiv:1912.05547, 2019.
https:///doi.org/10.48550/arXiv.1912.05547
arXiv: 1912.05547
[ 29 ] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani y Norman Y. Yao. Ventaja cuántica clásicamente verificable a partir de una prueba de Bell computacional. Física de la naturaleza, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[ 30 ] Vadim Lyubashevsky, Chris Peikert y Oded Regev. Sobre redes ideales y aprendizaje con errores sobre anillos. En Conferencia internacional anual sobre teoría y aplicaciones de técnicas criptográficas, páginas 1–23. Springer, 2010.
https: / / doi.org/ 10.1145 / 2535925
[ 31 ] Urmila Mahadev. Verificación clásica de cálculos cuánticos. En 2018, 59.º Simposio anual del IEEE sobre fundamentos de la informática (FOCS), páginas 259–267. IEEE, 2018.
https: / / doi.org/ 10.1109 / FOCS.2018.00033
[ 32 ] Michael A Nielsen e Isaac Chuang. Computación cuántica e información cuántica, 2002.
[ 33 ] A. S. Popova y A.N. Rubtsov. Rompiendo el umbral de ventaja cuántica para el muestreo de bosones gaussianos. En Conferencia y exposición Quantum 2.0, página QW2A.15. Grupo Editorial Óptica, 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[ 34 ] John Preskill. Computación cuántica en la era NISQ y más allá. Cuántico, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[ 35 ] Michael O. Rabin. Algoritmo probabilístico para probar la primalidad. Revista de teoría de números, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[ 36 ] Oded Regev. Sobre celosías, aprendizaje con errores, códigos lineales aleatorios y criptografía. Revista de la ACM (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[ 37 ] Dan Shepherd y Michael J. Bremner. Computación cuántica temporalmente desestructurada. Actas de la Royal Society A: Ciencias matemáticas, físicas y de ingeniería, 465(2105):1413–1439, 2009.
https: / / doi.org/ 10.1098 / rspa.2008.0443
[ 38 ] Peter W. Shor. Algoritmos para computación cuántica: logaritmos discretos y factorización. En Actas del 35º simposio anual sobre fundamentos de la informática, páginas 124-134. IEEE, 1994.
https: / / doi.org/ 10.1109 / SFCS.1994.365700
[ 39 ] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han , Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao , Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu y Jian-Wei Pan. Fuerte ventaja computacional cuántica utilizando un procesador cuántico superconductor. Física. Rev. Lett., 127:180501, 2021.
https: / / doi.org/ 10.1103 / PhysRevLett.127.180501
[ 40 ] K Wright, KM Beck, Sea Debnath, JM Amini, Y Nam, N Grzesiak, J-S Chen, NC Pisenti, M Chmielewski, C Collins, et al. Evaluación comparativa de una computadora cuántica de 11 qubits. Comunicaciones de la naturaleza, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[ 41 ] G Wendin. Procesamiento de información cuántica con circuitos superconductores: una revisión. Informes sobre el progreso en física, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[ 42 ] Adam Bene Watts, Robin Kothari, Luke Schaeffer y Avishay Tal. Separación exponencial entre circuitos cuánticos poco profundos y circuitos clásicos poco profundos en abanico ilimitados. En Actas del 51º Simposio Anual ACM SIGACT sobre Teoría de la Computación, páginas 515–526, 2019.
https: / / doi.org/ 10.1145 / 3313276.3316404
[ 43 ] Andrew Chi-Chih Yao. Cómo generar e intercambiar secretos. En 27º Simposio anual sobre fundamentos de la informática (sfcs 1986), páginas 162–167. IEEE, 1986.
https: / / doi.org/ 10.1109 / SFCS.1986.25
[ 44 ] Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He -Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang , Dachao Wu, Yulin Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu y Jian-Wei Pan. Ventaja computacional cuántica a través del muestreo de circuitos aleatorios de 60 ciclos y 24 qubits. Boletín científico, 67(3):240–245, 2022.
https: / / doi.org/ 10.1016 / j.scib.2021.10.017
[ 45 ] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidick, Umesh Vazirani, Norman Y. Yao, Marko Cetina y Christopher Monroe. Protocolos interactivos para una ventaja cuántica clásicamente verificable. Preimpresión de arXiv arXiv:2112.05156, 2021.
https:///doi.org/10.48550/arXiv.2112.05156
arXiv: 2112.05156
[ 46 ] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei- Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu y Jian-Wei Pan. Ventaja computacional cuántica utilizando fotones. Ciencia, 370(6523):1460–1463, 2020.
https: / / doi.org/ 10.1126 / science.abe8770
Citado por
[1] Nathanan Tantivasadakarn, Ashvin Vishwanath y Ruben Verresen, “Una jerarquía de orden topológico a partir de unidades unitarias de profundidad finita, medición y avance”, arXiv: 2209.06202.
[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch y Robert Koenig, "Circuitos adaptativos de profundidad constante para manipular electrones no abelianos", arXiv: 2205.01933.
[3] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidick, Umesh Vazirani, Norman Y. Yao, Marko Cetina y Christopher Monroe, "Protocolos interactivos para una ventaja cuántica clásicamente verificable", arXiv: 2112.05156.
[4] Vipin Singh Sehrawat, Foo Yee Yeo y Dmitriy Vassilyev, "PRF clave homomórficas específicas de estrellas de la regresión lineal y la teoría de conjuntos extremos", arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani y Norman Y. Yao, “Ventaja cuántica clásicamente verificable de una prueba computacional de Bell”, Naturaleza Física 18 8, 918 (2022).
[6] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn y Avishay Tal, "Sobre la aleatoriedad certificada de los experimentos con ventajas cuánticas", arXiv: 2111.14846.
[7] Nai-Hui Chia y Shih-Han Hung, “Verificación clásica de la profundidad cuántica”, arXiv: 2205.04656.
[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa y Seiichiro Tani, “Autoprueba computacional para estados mágicos entrelazados”, Revisión física A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde y Eneet Kaur, “Estimación de trazas multivariadas en profundidad cuántica constante”, arXiv: 2206.15405.
Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2022-09-21 12:16:02). 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-09-21 12:16:00).
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.
