Simulación rápida de circuitos planos de Clifford.

Simulación rápida de circuitos planos de Clifford.

Marca de tiempo: 12 de febrero de 2024 10:28 AM

David Goset1,2,3, Daniel Grier1,4,5, Alex Kerzner1,2y Luke Schaeffer1,2,6

1Instituto de Computación Cuántica, Universidad de Waterloo, Canadá
2Departamento de Combinatoria y Optimización, Universidad de Waterloo, Canadá
3Instituto Perimeter de Física Teórica, Waterloo, Canadá
4Escuela Cheriton de Ciencias de la Computación, Universidad de Waterloo, Canadá
5Departamento de Informática e Ingeniería y Departamento de Matemáticas, Universidad de California, San Diego, EE. UU.
6Centro Conjunto de Información Cuántica y Ciencias de la Computación, College Park, Maryland, EE. UU.

¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.

Resumen

Un circuito cuántico general se puede simular de forma clásica en tiempo exponencial. Si tiene un diseño plano, entonces un algoritmo de contracción de red tensorial debido a Markov y Shi tiene un tiempo de ejecución exponencial en la raíz cuadrada de su tamaño, o más generalmente exponencial en el ancho del árbol del gráfico subyacente. Por separado, Gottesman y Knill demostraron que si todas las puertas están restringidas a ser Clifford, entonces hay una simulación de tiempo polinomial. Combinamos estas dos ideas y mostramos que el ancho del árbol y la planaridad se pueden explotar para mejorar la simulación del circuito Clifford. Nuestro resultado principal es un algoritmo clásico con escalado de tiempo de ejecución asintóticamente como $ n^{omega/2}$ $lt$ $n^{1.19}$ que toma muestras de la distribución de salida obtenida midiendo todos los $n$ qubits de un estado de gráfico plano. en determinadas bases de Pauli. Aquí $ omega $ es el exponente de multiplicación de matrices. También proporcionamos un algoritmo clásico con el mismo tiempo de ejecución asintótico que toma muestras de la distribución de salida de cualquier circuito Clifford de profundidad constante en una geometría plana. Nuestro trabajo mejora algoritmos clásicos conocidos con tiempo de ejecución cúbico.

Un ingrediente clave es un mapeo que, dada una descomposición en árbol de algún gráfico $G$, produce un circuito Clifford con una estructura que refleja la descomposición del árbol y que emula la medición del estado del gráfico correspondiente. Proporcionamos una simulación clásica de este circuito con el tiempo de ejecución indicado anteriormente para gráficos planos y en caso contrario $nt^{omega-1}$ donde $t$ es el ancho de la descomposición del árbol. Nuestro algoritmo incorpora dos subrutinas que pueden ser de interés independiente. La primera es una versión de tiempo de multiplicación de matrices de la simulación de Gottesman-Knill de medición de múltiples qubits en estados estabilizadores. El segundo es un nuevo algoritmo clásico para resolver sistemas lineales simétricos sobre $mathbb{F}_2$ en una geometría plana, ampliando trabajos anteriores que solo se aplicaban a sistemas lineales no singulares en un entorno análogo.

Simulación rápida de circuitos planos Clifford PlatoBlockchain Data Intelligence. Búsqueda vertical. Ai.

Imagen de portada: En el sentido de las agujas del reloj desde la izquierda: un gráfico, una bonita descomposición en árbol y un circuito que prepara el estado del gráfico correspondiente.

[Contenido incrustado]

► datos BibTeX

► referencias

[ 1 ] 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, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[ 2 ] “Documentación cuántica de IBM”. https://​/​docs.quantum.ibm.com/​run.
https://​/​docs.quantum.ibm.com/​run

[ 3 ] Matthew D Reed, Leonardo DiCarlo, Simon E Nigg, Luyan Sun, Luigi Frunzio, Steven M Girvin y Robert J Schoelkopf. “Realización de corrección de errores cuánticos de tres qubits con circuitos superconductores”. Naturaleza 482, 382–385 (2012).
https: / / doi.org/ 10.1038 / nature10786

[ 4 ] Antonio D Córcoles, Easwar Magesan, Srikanth J Srinivasan, Andrew W Cross, Matthias Steffen, Jay M Gambetta y Jerry M Chow. "Demostración de un código de detección de errores cuánticos utilizando una red cuadrada de cuatro qubits superconductores". Comunicaciones de la naturaleza 6, 1–10 (2015).
https: / / doi.org/ 10.1038 / ncomms7979

[ 5 ] Nissim Ofek, Andrei Petrenko, Reinier Heeres, Philip Reinhold, Zaki Leghtas, Brian Vlastakis, Yehan Liu, Luigi Frunzio, SM Girvin, Liang Jiang, et al. “Ampliación de la vida útil de un bit cuántico con corrección de errores en circuitos superconductores”. Naturaleza 536, 441–445 (2016).
https: / / doi.org/ 10.1038 / nature18949

[ 6 ] Igor L Markov y Yaoyun Shi. “Simulación de computación cuántica mediante la contratación de redes de tensores”. SIAM Journal on Computing 38, 963–981 (2008).
https: / / doi.org/ 10.1137 / 050644756

[ 7 ] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy y Hartmut Neven. “Simulación de circuitos cuánticos de baja profundidad como modelos gráficos complejos no dirigidos” (2017).

[ 8 ] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset y Mark Howard. “Simulación de circuitos cuánticos mediante descomposiciones de estabilizadores de bajo rango”. Cuántico 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[ 9 ] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, Erik W Draeger, Eric T Holland y Robert Wisnieff. “Rompiendo la barrera de los 49 qubits en la simulación de circuitos cuánticos” (2017).

[ 10 ] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh y Robert Wisnieff. “Aprovechando el almacenamiento secundario para simular circuitos Sycamore profundos de 54 qubit” (2019).

[ 11 ] Boaz Barak, Chi-Ning Chou y Xun Gao. “Falsificación de evaluaciones comparativas de entropía cruzada lineal en circuitos cuánticos poco profundos” (2020).

[ 12 ] Barbara M Terhal y David P DiVincenzo. “Computación cuántica adaptativa, circuitos cuánticos de profundidad constante y juegos de Arthur-Merlin” (2002).

[ 13 ] Michael J. Bremner, Richard Jozsa y Dan J. Shepherd. "La simulación clásica de cálculos cuánticos conmutantes implica el colapso de la jerarquía polinómica". Actas de la Royal Society A: Ciencias matemáticas, físicas y de ingeniería 467, 459–472 (2011).
https: / / doi.org/ 10.1098 / rspa.2010.0301

[ 14 ] 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

[ 15 ] Daniel Gottesman. “La representación de Heisenberg de las computadoras cuánticas” (1998).

[ 16 ] Sergey Bravyi y David Gosset. "Simulación clásica mejorada de circuitos cuánticos dominados por puertas de Clifford". Cartas de revisión física 116, 250501 (2016).
https: / / doi.org/ 10.1103 / physrevlett.116.250501

[ 17 ] Scott Aaronson y Daniel Gottesman. “Simulación mejorada de circuitos estabilizadores”. Revisión física A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[ 18 ] Sergey Bravyi, David Gosset y Robert König. “Ventaja cuántica con circuitos poco profundos”. Ciencia 362, 308–311 (2018).
https: / / doi.org/ 10.1126 / science.aar3106

[ 19 ] 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 informática. Páginas 515–526. (2019).
https: / / doi.org/ 10.1145 / 3313276.3316404

[ 20 ] Daniel Grier y Luke Schaeffer. "Circuitos interactivos de Clifford poco profundos: ventaja cuántica frente a $mathsf{NC}^1$ y más". En actas del 52º Simposio anual ACM SIGACT sobre teoría de la informática. Páginas 875–888. (2020).
https: / / doi.org/ 10.1145 / 3357713.3384332

[ 21 ] Sergey Bravyi, David Gosset, Robert Koenig y Marco Tomamichel. "Ventaja cuántica con circuitos poco profundos y ruidosos". Física de la naturaleza Páginas 1 a 6 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

[ 22 ] Robert Raussendorf y Hans J. Briegel. “Una computadora cuántica unidireccional”. Cartas de revisión física 86, 5188 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[ 23 ] Josh Alman y Virginia Vassilevska Williams. “Un método láser refinado y una multiplicación de matrices más rápida” (2020).

[ 24 ] Chaowen Guan y Kenneth W. Regan. “Circuitos estabilizadores, formas cuadráticas y rango de matriz informática” (2019).

[ 25 ] Daniel Grier y Luke Schaeffer. “gridCHP++, licencia Apache versión 2.0”. https:/​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0.
https:/​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0

[ 26 ] Alan Jorge. “Disección anidada de una malla regular de elementos finitos”. Revista SIAM de análisis numérico 10, 345–363 (1973).
https: / / doi.org/ 10.1137 / 0710032

[ 27 ] Richard J. Lipton, Donald J. Rose y Robert Endre Tarjan. “Disección anidada generalizada”. Revista SIAM sobre análisis numérico 16, 346–358 (1979).
https: / / doi.org/ 10.1137 / 0716027

[ 28 ] Noga Alon y Raphael Yuster. “Resolución de sistemas lineales mediante disección anidada”. En 2010, 51º Simposio Anual del IEEE sobre Fundamentos de la Informática. Páginas 225–234. IEEE (2010).
https: / / doi.org/ 10.1109 / FOCS.2010.28

[ 29 ] Richard J. Lipton y Robert Endre Tarjan. "Un teorema del separador para gráficos planos". Revista SIAM de Matemáticas Aplicadas 36, 177–189 (1979).
https: / / doi.org/ 10.1137 / 0136016

[ 30 ] Scott Aaronson y Lijie Chen. "Fundamentos teóricos de la complejidad de los experimentos de supremacía cuántica". En la 32ª Conferencia sobre Complejidad Computacional (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2017).

[ 31 ] Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman y Yaoyun Shi. “Simulación clásica de circuitos cuánticos de tamaño intermedio” (2018).

[ 32 ] Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S Humble, Rupak Biswas, Eleanor G Rieffel, Alan Ho y Salvatore Mandrà. “Estableciendo la frontera de la supremacía cuántica con una simulación de 281 pflop/s”. Ciencia y Tecnología Cuánticas 5, 034003 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab7eeb

[ 33 ] Stefan Arnborg, Derek G Corneil y Andrzej Proskurowski. “Complejidad de encontrar incrustaciones en un árbol $k$”. Revista SIAM sobre métodos algebraicos discretos 8, 277–284 (1987).
https: / / doi.org/ 10.1137 / 0608024

[ 34 ] HL Bodlaender. “Una guía turística a través de la anchura de los árboles”. Acta Cybernetica 11, 1–21 (1993).

[ 35 ] Hans L. Bodlaender, Pål Grøonås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov y Michał Pilipczuk. "Un algoritmo de aproximación $c^kn$ 5 para el ancho del árbol". Revista SIAM de Computación 45, 317–378 (2016).
https: / / doi.org/ 10.1137 / 130947374

[ 36 ] Sergey Bravyi, Graeme Smith y John A. Smolin. “Comercio de recursos computacionales clásicos y cuánticos”. Revisión física X 6, 021043 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021043

[ 37 ] Sr. Van den Nest. “Simulación clásica de la computación cuántica, el teorema de Gottesman-Knill y un poco más allá” (2008).

[ 38 ] Álex Kerzner. “Simulación Clifford: Técnicas y aplicaciones”. Tesis de maestría. Universidad de Waterloo. (2021).

[ 39 ] Carsten Damm. “Problemas completos para $oplus{L}$”. En Jürgen Dassow y Jozef Kelemen, editores, Aspectos y perspectivas de la informática teórica. Páginas 130–137. Berlín, Heidelberg (1990). Springer Berlín Heidelberg.
https:/​/​doi.org/​10.1016/​0020-0190(90)90150-V

[ 40 ] David Eppstein (2007). commons.wikimedia.org/​wiki/​File:Tree_decomposition.svg, consultado el 08/31/​2020.

[ 41 ] Hans L. Bodlaender y Ton Kloks. "Mejores algoritmos para el ancho de ruta y el ancho de árbol de gráficos". En Autómatas, Lenguajes y Programación: XVIII Coloquio Internacional Madrid, España, 18 al 8 de julio de 12 Actas 1991. Páginas 18–544. Saltador (555).
https:/​/​doi.org/​10.1007/​3-540-54233-7_162

[ 42 ] Oscar H Ibarra, Shlomo Moran y Roger Hui. “Una generalización del algoritmo y sus aplicaciones de descomposición rápida de matrices LUP”. Revista de algoritmos 3, 45–56 (1982).
https:/​/​doi.org/​10.1016/​0196-6774(82)90007-4

[ 43 ] Adi Ben-Israel y Thomas NE Greville. “Inversas generalizadas: teoría y aplicaciones”. Volumen 15. Springer Science & Business Media. (2003).
https: / / doi.org/ 10.1007 / b97366

[ 44 ] Michael T. Goodrich. “Separadores planos y triangulación de polígonos paralelos”. Revista de Ciencias de la Computación y Sistemas 51, 374–389 (1995).
https: / / doi.org/ 10.1006 / jcss.1995.1076

[ 45 ] Jeroen Dehaene y Bart De Moor. “Grupo Clifford, estados estabilizadores y operaciones lineales y cuadráticas sobre $mathrm{GF}$(2)”. Revisión física A 68, 042318 (2003).
https: / / doi.org/ 10.1103 / PhysRevA.68.042318

[ 46 ] Simon Anders y Hans J. Briegel. "Simulación rápida de circuitos estabilizadores utilizando una representación gráfica del estado". Revisión física A 73, 022334 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022334

[ 47 ] Serguéi Bravyi. Comunicación personal, 2017 (2017).

[ 48 ] Maarten Van den Nest, Jeroen Dehaene y Bart De Moor. “Descripción gráfica de la acción de las transformaciones locales de Clifford sobre los estados del grafo”. Revisión física A 69, 022316 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.69.022316

Citado por

[1] Travis L. Scholten, Carl J. Williams, Dustin Moody, Michele Mosca, William Hurley, William J. Zeng, Matthias Troyer y Jay M. Gambetta, "Evaluación de los beneficios y riesgos de las computadoras cuánticas", arXiv: 2401.16317, (2024).

[2] Lorenzo Leone, Salvatore FE Oliviero, Seth Lloyd y Alioscia Hamma, “Aprender decodificadores eficientes para modificadores cuánticos cuasi-caóticos”, arXiv: 2212.11338, (2022).

[3] Ryan L. Mann, "Simulación de cálculos cuánticos con polinomios de Tutte", npj Información cuántica 7, 141 (2021).

[4] Sahar Atallah, Michael Garn, Sania Jevtic, Yukuan Tao y Shashank Virmani, “Simulación clásica eficiente de circuitos cuánticos de estado de cúmulo con entradas alternativas”, arXiv: 2201.07655, (2022).

[5] Shihao Zhang, Jiacheng Bao, Yifan Sun, Lvzhou Li, Houjun Sun y Xiangdong Zhang, "Esquema clásico paralelo de alto rendimiento para simular circuitos cuánticos poco profundos", arXiv: 2103.00693, (2021).

Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2024-02-13 03:31:05). 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 2024-02-13 03:31:02).

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.

Sello de tiempo:

Mas de Diario cuántico