1Centro de AWS para Computación Cuántica, EE. UU.
2IQIM, Instituto de Tecnología de California, EE. UU.
3Departamento de Ciencias de la Computación, Universidad Carnegie Mellon, EE. UU.
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
Motivados por la estimación de modelos de ruido cuántico, estudiamos el problema de aprender un canal de Pauli, o más generalmente las tasas de error de Pauli de un canal arbitrario. Al emplear una reducción novedosa del problema de "Recuperación de población", proporcionamos un algoritmo extremadamente simple que aprende las tasas de error de Pauli de un canal de $ n $ -qubit con precisión $ epsilon $ en $ ell_infty $ usando solo $ O (1 / epsilon ^ 2) log (n / epsilon) $ aplicaciones del canal. Esto es óptimo hasta los factores logarítmicos. Nuestro algoritmo utiliza solo medidas y preparación de estados desenredadas, y el tiempo de ejecución clásico posterior a la medición es solo un factor $ O (1 / épsilon) $ mayor que el tamaño de los datos de medición. También es impermeable a un modelo limitado de ruido de medición donde los fallos de medición anunciados ocurren de forma independiente con una probabilidad de $ le 1/4 $.
Luego consideramos el caso en el que el canal de ruido está cerca de la identidad, lo que significa que el resultado sin error ocurre con probabilidad $ 1-eta $. En el régimen de $ eta $ pequeños, ampliamos nuestro algoritmo para lograr precisión multiplicativa $ 1 pm épsilon $ (es decir, precisión aditiva $ épsilon eta $) usando solo $ Obigl (frac {1} {épsilon ^ 2 eta} bigr) log (n / epsilon) $ aplicaciones del canal.
Resumen popular
En este trabajo, consideramos el problema de aprender una distribución de probabilidad sobre operadores de Pauli; es decir, deseamos aprender un canal Pauli. Además, deseamos hacerlo utilizando solo preparaciones (estado del producto) y mediciones de base muy simples. Aprender los canales Pauli con recursos mínimos es importante para conocer los errores en una computadora cuántica ruidosa y encontrar mejores formas de corregir o mitigar esos errores.
Nuestro trabajo muestra que este problema se reduce al problema clásico de recuperación de la población con un cierto tipo de ruido asimétrico. A continuación, mostramos que los algoritmos estándar conocidos en la literatura para la recuperación de la población se aplican sin cambios a este tipo de ruido. Esto nos proporciona algoritmos muy eficientes en cuanto a muestras para aprender los canales Pauli que utilizan preparaciones y medidas de estado muy simples.
También mostramos algunos otros datos interesantes. Primero, el algoritmo es naturalmente robusto a ciertos tipos de ruido de medición adicional. También podemos extender el algoritmo para manejar el caso en el que la mayoría de las veces solo ocurre un único Pauli (digamos, la identidad Pauli), y deseamos recuperar la población restante con una precisión relativa a la frecuencia de la población restante ( una tarea más exigente). Mostramos una conexión interesante con el análisis de Fourier sobre variables booleanas. Finalmente, damos una implementación de código abierto en Julia de uno de los algoritmos.
► datos BibTeX
► referencias
[ 1 ] F. Ban, X. Chen, A. Freilich, R. Servedio y S. Sinha. Más allá de la reconstrucción de trazas: recuperación de la población del canal de eliminación. En Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science, páginas 745–768, 2019, arXiv: 1904.05532.
https: / / doi.org/ 10.1109 / FOCS.2019.00050
arXiv: 1904.05532
[ 2 ] F. Ban, X. Chen, RA Servedio y S. Sinha. Recuperación eficiente de la población de casos promedio en presencia de inserciones y deleciones. En D. Achlioptas y LA Végh, editores, Aproximación, Aleatorización y Optimización Combinatoria. Algorithms and Techniques (APPROX / RANDOM 2019), volumen 145 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 44: 1–44: 18, Dagstuhl, Alemania, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, arXiv: 1907.05964 .
https: / / doi.org/ 10.4230 / LIPIcs.APPROX-RANDOM.2019.44
arXiv: 1907.05964
[ 3 ] L. Batman, R. Impagliazzo, C. Murray y R. Paturi. Encontrar pesos pesados a partir de datos ruidosos o con pérdidas. En Actas de la 16ª Conferencia Internacional Anual sobre Algoritmos de Aproximación para Problemas de Optimización Combinatoria, páginas 347–362, 2013.
https://doi.org/10.1007/978-3-642-40328-6_25
[ 4 ] CH Bennett y SJ Wiesner. Comunicación a través de operadores de una y dos partículas en los estados de Einstein-Podolsky-Rosen. Phys. Rev. Lett., 69: 2881–2884, noviembre de 1992.
https: / / doi.org/ 10.1103 / PhysRevLett.69.2881
[ 5 ] CL Canonne. Una breve nota sobre el aprendizaje de distribuciones discretas, 2020, arXiv: 2002.11457.
arXiv: 2002.11457
[ 6 ] C. Dankert. Simulación eficiente de operadores y estados cuánticos aleatorios. Tesis de doctorado, Universidad de Waterloo, 2015, arXiv: quant-ph / 0512217.
arXiv: quant-ph / 0512217
[ 7 ] A. De, R. O'Donnell y R. Servedio. Límites marcados para la recuperación de la población. Teoría de la Computación, 16 (6): 1–20, 2020, arXiv: 1703.01474.
https: / / doi.org/ 10.4086 / toc.2020.v016a006
arXiv: 1703.01474
[ 8 ] A. De, M. Saks y S. Tang. Recuperación poblacional ruidosa en tiempo polinomial. En Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, páginas 675–684, 2016, arXiv: 1602.07616.
https: / / doi.org/ 10.1109 / FOCS.2016.77
arXiv: 1602.07616
[ 9 ] Z. Dvir, A. Rao, A. Wigderson y A. Yehudayoff. Restricción de acceso. En Proceedings of the 3nd Annual Innovations in Theoretical Computer Science, páginas 19–33, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090239
[ 10 ] S. Flammia y J. Wallman. Estimación eficiente de canales Pauli. Transacciones ACM en Computación Cuántica, 1 (1): 1–32, 2020, arXiv: 1907.12976.
https: / / doi.org/ 10.1145 / 3408039
arXiv: 1907.12976
[ 11 ] ST Flammia. PauliPopRec, repositorio de Github, 2021.
https: / / doi.org/ 10.5281 / ZENODO.5327656
[ 12 ] A. Fujiwara y H. Imai. Estimación de parámetros cuánticos de un canal de Pauli generalizado. Journal of Physics A: Mathematical and General, 36 (29): 8093–8103, julio de 2003.
https://doi.org/10.1088/0305-4470/36/29/314
[ 13 ] O. Goldreich y L. Levin. Un predicado fundamental para todas las funciones unidireccionales. En Proceedings of the 21st Annual ACM Symposium on Theory of Computing, páginas 25–32, 1989.
https: / / doi.org/ 10.1145 / 73007.73010
[ 14 ] R. Harper, ST Flammia y JJ Wallman. Aprendizaje eficiente del ruido cuántico. Nature Physics, 16 (12): 1184-1188, agosto de 2020, arXiv: 1907.13022.
https://doi.org/10.1038/s41567-020-0992-8
arXiv: 1907.13022
[ 15 ] R. Harper, W. Yu y ST Flammia. Estimación rápida de ruido cuántico escaso. PRX Quantum, 2 (1): 010322, febrero de 2021, arXiv: 2007.07901.
https: / / doi.org/ 10.1103 / PRXQuantum.2.010322
arXiv: 2007.07901
[ 16 ] M. Hayashi. Teoría de la información cuántica. Springer Berlin Heidelberg, 2a edición, 2017.
https://doi.org/10.1007/978-3-662-49725-8
[ 17 ] J. Helsen, X. Xue, LMK Vandersypen y S. Wehner. Una nueva clase de protocolos de evaluación comparativa aleatorios eficientes. npj Quantum Information, 5 (1): 71, agosto de 2019, arXiv: 1806.02048.
https://doi.org/10.1038/s41534-019-0182-7
arXiv: 1806.02048
[ 18 ] E. Knill. Computación cuántica con dispositivos realmente ruidosos. Nature, 434 (7029): 39–44, marzo de 2005, arXiv: quant-ph / 0410199.
https: / / doi.org/ 10.1038 / nature03350
arXiv: quant-ph / 0410199
[ 19 ] S. Lovett y J. Zhang. Mejora de la recuperación de la población ruidosa y revierte la desigualdad Bonami-Beckner para funciones dispersas. En Proceedings of the 47th Annual ACM Symposium on Theory of Computing, páginas 137-142, 2015.
https: / / doi.org/ 10.1145 / 2746539.2746540
[ 20 ] S. Lovett y J. Zhang. Recuperación de población ruidosa de ruido desconocido. En Conferencia sobre teoría del aprendizaje, páginas 1417–1431, 2017.
[ 21 ] A. Moitra y M. Saks. Un algoritmo de tiempo polinomial para la recuperación de poblaciones con pérdidas. En Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, páginas 110-116, 2013, arXiv: 1302.1515.
https: / / doi.org/ 10.1109 / FOCS.2013.20
arXiv: 1302.1515
[ 22 ] A. Montanaro y TJ Osborne. Funciones booleanas cuánticas. Chicago Journal of Theoretical Computer Science, 2010 (1): 1–45, enero de 2010, arXiv: 0810.2435.
https: / / doi.org/ 10.4086 / cjtcs.2010.001
arXiv: 0810.2435
[ 23 ] S. Narayanan. Algoritmos mejorados para la recuperación de la población del canal de eliminación. En Actas del Simposio ACM-SIAM de 2021 sobre algoritmos discretos (SODA), páginas 1259–1278. Society for Industrial and Applied Mathematics, enero de 2021, arXiv: 2004.06828.
https: / / doi.org/ 10.1137 / 1.9781611976465.77
arXiv: 2004.06828
[ 24 ] R. O'Donnell. Análisis de funciones booleanas. Cambridge University Press, 2014, arXiv: 2105.10386.
https: / / doi.org/ 10.1017 / CBO9781139814782
arXiv: 2105.10386
[ 25 ] Y. Polyanskiy, AT Suresh e Y. Wu. Muestra de la complejidad de la recuperación de la población. En S. Kale y O. Shamir, editores, Proceedings of the 2017 Conference on Learning Theory, volumen 65 de Proceedings of Machine Learning Research, páginas 1589–1618, Ámsterdam, Países Bajos, 07–10 de julio de 2017. PMLR, arXiv: 1702.05574.
arXiv: 1702.05574
[ 26 ] B. Terhal. Corrección de errores cuánticos para memorias cuánticas. Reseñas de la física moderna, 87 (2): 307, 2015, arXiv: 1302.3428.
https: / / doi.org/ 10.1103 / RevModPhys.87.307
arXiv: 1302.3428
[ 27 ] J. ur Rehman y H. Shin. Estimación de parámetros sin enredos de canales de Pauli generalizados. Quantum, 5: 490, julio de 2021, arXiv: 2102.00740.
https://doi.org/10.22331/q-2021-07-01-490
arXiv: 2102.00740
[ 28 ] M. Wainwright. Estadísticas de alta dimensión: un punto de vista no asintótico. Cambridge University Press, 2019.
https: / / doi.org/ 10.1017 / 9781108627771
[ 29 ] J. Wallman y J. Emerson. Adaptación de ruido para computación cuántica escalable mediante compilación aleatoria. Revisión física A, 94 (5): 052325, 2016, arXiv: 1512.01098.
https: / / doi.org/ 10.1103 / PhysRevA.94.052325
arXiv: 1512.01098
[ 30 ] A. Wigderson y A. Yehudayoff. Recuperación poblacional e identificación parcial. Aprendizaje automático, 102 (1): 29–56, 2016.
https://doi.org/10.1007/s10994-015-5489-9
Citado por
[1] Yunchao Liu, Matthew Otten, Roozbeh Bassirianjahromi, Liang Jiang y Bill Fefferman, "Evaluación comparativa de computadoras cuánticas a corto plazo mediante muestreo de circuito aleatorio", arXiv: 2105.05232.
[2] Thomas Wagner, Hermann Kampermann, Dagmar Bruß y Martin Kliesch, "Los canales de Pauli se pueden estimar a partir de mediciones de síndrome en la corrección de errores cuánticos", arXiv: 2107.14252.
[3] Senrui Chen, Sisi Zhou, Alireza Seif y Liang Jiang, "Ventajas cuánticas para la estimación del canal Pauli", arXiv: 2108.08488.
[4] Steven T. Flammia, “Muestreo de valores propios de circuito promediado”, arXiv: 2108.05803.
Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2021-09-23 14:17:36). 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-09-23 14:17:34: No se pudieron obtener los datos citados por 10.22331 / q-2021-09-23-549 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-09-23-549/
