1Universidad de Minho, Departamento de Ciencias de la Computación, Braga, Portugal
2INESC TEC, Braga, Portugal
3Laboratorio Ibérico Internacional de Nanotecnología (INL) Av. Mestre José Veiga, 4715-330, Braga, Portugal
4Instituto de Física, Universidad Federal Fluminense Av. Galón. Milton Tavares de Souza s/n, Niterói, RJ, 24210-340, Brasil
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
Se ha demostrado que varias clases de circuitos cuánticos proporcionan una ventaja computacional cuántica bajo ciertos supuestos. El estudio de clases cada vez más restringidas de circuitos cuánticos capaces de obtener ventajas cuánticas está motivado por posibles simplificaciones en las demostraciones experimentales. En este artículo estudiamos la eficiencia de la computación cuántica basada en mediciones con un ordenamiento temporal de mediciones completamente plano. Proponemos nuevas construcciones para el cálculo determinista de funciones booleanas arbitrarias, basándose en correlaciones presentes en estados multiqubit de Greenberger, Horne y Zeilinger (GHZ). Caracterizamos la complejidad de medición necesaria utilizando la jerarquía de Clifford y, en general, también reducimos el número de qubits necesarios con respecto a construcciones anteriores. En particular, identificamos una familia de funciones booleanas para las cuales es posible una evaluación determinista utilizando MBQC no adaptativo, presentando ventajas cuánticas en ancho y número de puertas con respecto a los circuitos clásicos.
Imagen de portada: El modelo MBQC no adaptativo puede describirse mediante una arquitectura computacional específica que se divide en el proceso de preparación del estado cuántico, la rutina de medición y el procesamiento lineal pre y posclásico asociado (arriba a la izquierda). Este modelo facilita el estudio de los requisitos de recursos para evaluar funciones booleanas simétricas en términos del número asintótico de qubits y operaciones requeridas (arriba a la derecha). Estos elementos revelan nuestros resultados principales [abajo], que se articulan para conjuntos de puertas y descripciones de circuitos clásicos y cuánticos estándar [abajo a la izquierda], que caracterizan el conjunto de funciones booleanas que demuestran la ventaja cuántica con respecto al número de puertas y el ancho de la circuitos (abajo a la derecha).
[Contenido incrustado]
Resumen popular
En este trabajo analizamos la evaluación de funciones booleanas, algo que las computadoras cuánticas pueden hacer utilizando los resultados correlacionados de mediciones en estados entrelazados de Greenberger-Horne-Zeilinger (GHZ) de muchos qubits. Esta variante de computación cuántica basada en mediciones no requiere adaptabilidad, por lo que todos los qubits se pueden medir simultáneamente. Esta estructura temporal plana del proceso computacional da como resultado, en algunos casos, circuitos cuánticos muy económicos. Identificamos las características de una función booleana que determinan cuántos qubits se necesitan y la precisión de medición requerida. Para una familia particular de funciones booleanas mostramos que existe una ventaja rigurosa en ancho y número de compuertas con respecto a la familia correspondiente de circuitos clásicos. En el futuro, nuestras técnicas pueden ayudar a idear mejores formas de utilizar recursos cuánticos también para circuitos adaptativos que muestren una mayor expresividad computacional.
► datos BibTeX
► referencias
[ 1 ] Scott Aaronson, DeVon Ingram y William Kretschmer. “Las Acrobacias del BQP”. En Shachar Lovett, editor, 37ª Conferencia sobre Complejidad Computacional (CCC 2022). Volumen 234 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 20:1–20:17. Dagstuhl, Alemania (2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2022.20
[ 2 ] Richard Jozsa y Noah Linden. “Sobre el papel del entrelazamiento en la aceleración computacional cuántica”. Actas de la Royal Society de Londres. Serie A: Ciencias Matemáticas, Físicas y de Ingeniería 459, 2011–2032 (2003).
https: / / doi.org/ 10.1098 / rspa.2002.1097
[ 3 ] Mark Howard, Joel Wallman, Victor Veitch y Joseph Emerson. "La contextualidad proporciona la 'magia' para la computación cuántica". Naturaleza 510, 351–355 (2014).
https: / / doi.org/ 10.1038 / nature13460
[ 4 ] Juan Bermejo-Vega, Nicolas Delfosse, Dan E. Browne, Cihan Okay y Robert Raussendorf. “La contextualidad como recurso para modelos de computación cuántica con qubits”. Física. Rev. Lett. 119, 120505 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.120505
[ 5 ] Ernesto F. Galvão. "Funciones de Wigner discretas y aceleración computacional cuántica". Física. Rev. A 71, 042302 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.042302
[ 6 ] A. Mari y J. Eisert. "Las funciones de Wigner positivas hacen eficiente la simulación clásica de la computación cuántica". Física. Rev. Lett. 109, 230503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.230503
[ 7 ] Lov K. Grover. “Las ventajas de la superposición”. Ciencia 280, 228–228 (1998).
https: / / doi.org/ 10.1126 / science.280.5361.228
[ 8 ] Robert Raussendorf y Hans J. Briegel. “Una computadora cuántica unidireccional”. física Rev. Lett. 86, 5188–5191 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188
[ 9 ] Maarten Van den Nest, Akimasa Miyake, Wolfgang Dür y Hans J. Briegel. "Recursos universales para la computación cuántica basada en mediciones". Física. Rev. Lett. 97, 150504 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.150504
[ 10 ] Janet Anders y Dan E. Browne. “Poder computacional de las correlaciones”. Física. Rev. Lett. 102, 050502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.050502
[ 11 ] Vincent Danos y Elham Kashefi. “Determinismo en el modelo unidireccional”. Física. Rev. A 74, 052310 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052310
[ 12 ] Daniel E Browne, Elham Kashefi, Mehdi Mhalla y Simon Perdrix. “Flujo generalizado y determinismo en la computación cuántica basada en mediciones”. Nueva Revista de Física 9, 250 (2007).
https://doi.org/10.1088/1367-2630/9/8/250
[ 13 ] Michael J. Bremner, Ashley Montanaro y Dan J. Shepherd. "Complejidad de caso promedio versus simulación aproximada de cálculos cuánticos de conmutación". Física. Rev. Lett. 117, 080501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501
[ 14 ] Matty J. Hoban, Joel J. Wallman, Hussain Anwar, Naïri Usher, Robert Raussendorf y Dan E. Browne. “Computación clásica basada en medidas”. Física. Rev. Lett. 112, 140505 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.112.140505
[ 15 ] Michael J. Bremner, Ashley Montanaro y Dan J. Shepherd. "Lograr la supremacía cuántica con cálculos cuánticos de conmutación escasos y ruidosos". Cuántico 1, 8 (2017).
https://doi.org/10.22331/q-2017-04-25-8
[ 16 ] Leonardo Novo, Juani Bermejo Vega y Raúl García Patrón. "Ventaja cuántica de las mediciones de energía de sistemas cuánticos de muchos cuerpos". Cuántico 5, 465 (2021).
https://doi.org/10.22331/q-2021-06-02-465
[ 17 ] Masahito Hayashi y Yuki Takeuchi. "Verificación de cálculos cuánticos de conmutación mediante estimación de fidelidad de estados de gráficos ponderados". Nueva Revista de Física 21, 93060 (2019).
https://doi.org/10.1088/1367-2630/ab3d88
[ 18 ] Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf y Jens Eisert. "Arquitecturas para simulación cuántica que muestran una aceleración cuántica". Física. Rev. X 8, 021010 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.021010
[ 19 ] Jacob Miller, Stephen Sanders y Akimasa Miyake. "Supremacía cuántica en la computación basada en mediciones en tiempo constante: una arquitectura unificada para muestreo y verificación". Física. Rev. A 96, 062320 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062320
[ 20 ] Matty J Hoban, Earl T Campbell, Klearchos Loukopoulos y Dan E Browne. "Computación cuántica basada en mediciones no adaptativas y desigualdades de Bell multipartitas". Nueva Revista de Física 13, 23014 (2011).
https://doi.org/10.1088/1367-2630/13/2/023014
[ 21 ] Ryuhei Mori. “Representación periódica de Fourier de funciones booleanas”. Información cuántica. Computadora. 19, 392–412 (2019). URL: https:///dl.acm.org/doi/abs/10.5555/3370251.3370253.
https: / / dl.acm.org/ doi / abs / 10.5555 / 3370251.3370253
[ 22 ] Markus Frembs, Sam Roberts, Earl T Campbell y Stephen D Bartlett. “Jerarquías de recursos para la computación cuántica basada en mediciones”. Nueva Revista de Física 25, 013002 (2023).
https://doi.org/10.1088/1367-2630/acaee2
[ 23 ] Jelena Mackeprang, Daniel Bhatti, Matty J Hoban y Stefanie Barz. "El poder de los qutrits para la computación cuántica basada en mediciones no adaptativas". Nueva Revista de Física 25, 073007 (2023).
https://doi.org/10.1088/1367-2630/acdf77
[ 24 ] Daniel Collins, Nicolas Gisin, Sandu Popescu, David Roberts y Valerio Scarani. "Desigualdades tipo campana para detectar la verdadera no separabilidad del cuerpo $mathit{n}$". Física. Rev. Lett. 88, 170405 (2002).
https: / / doi.org/ 10.1103 / PhysRevLett.88.170405
[ 25 ] Nicolás Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani y Stephanie Wehner. “Bell no localidad”. Rev.Mod. física 86, 419–478 (2014).
https: / / doi.org/ 10.1103 / RevModPhys.86.419
[ 26 ] Dmitrijs Kravčenko. “Juegos Cuánticos, Estados Cuánticos, Sus Propiedades y Aplicaciones”. Tesis doctoral. Universidad de Latvijas. (2013).
[ 27 ] William Slofstra. "Límites inferiores del entrelazamiento necesarios para jugar juegos XOR no locales". Revista de Física Matemática 52, 102202 (2011).
https: / / doi.org/ 10.1063 / 1.3652924
[ 28 ] Andris Ambainis, Jānis Iraids, Dmitry Kravchenko y Madars Virza. “Ventaja de las estrategias cuánticas en juegos xor simétricos aleatorios”. En Antonín Kučera, Thomas A. Henzinger, Jaroslav Nešetřil, Tomáš Vojnar y David Antoš, editores, Métodos matemáticos y de ingeniería en informática. Páginas 57–68. Berlín, Heidelberg (2013). Springer Berlín Heidelberg.
https://doi.org/10.1007/978-3-642-36046-6_7
[ 29 ] Andris Ambainis y Janis Iraids. "Ventaja demostrable para estrategias cuánticas en juegos XOR simétricos aleatorios". En Simone Severini y Fernando Brandao, editores, 8ª Conferencia sobre Teoría de la Computación, Comunicación y Criptografía Cuántica (TQC 2013). Volumen 22 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 146-156. Dagstuhl, Alemania (2013). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2013.146
[ 30 ] Samuel Marcovitch y Benni Reznik. “Implicaciones de la complejidad de la comunicación en sistemas multipartitos”. Física. Rev. A 77, 032120 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.032120
[ 31 ] Marcin Pawłowski, Tomasz Paterek, Dagomir Kaszlikowski, Valerio Scarani, Andreas Winter y Marek Żukowski. “La causalidad de la información como principio físico”. Naturaleza 461, 1101–1104 (2009).
https: / / doi.org/ 10.1038 / nature08400
[ 32 ] Sandu Popescu y Daniel Rohrlich. “La no localidad cuántica como axioma”. Fundamentos de Física 24, 379–385 (1994).
https: / / doi.org/ 10.1007 / BF02058098
[ 33 ] Jonathan Barrett, Noah Linden, Serge Massar, Stefano Pironio, Sandu Popescu y David Roberts. “Las correlaciones no locales como recurso teórico de la información”. Física. Rev. A 71, 022101 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.022101
[ 34 ] AA Razborov. “Complejidad de la comunicación cuántica de predicados simétricos”. Izvestiya: Matemáticas 67, 145 (2003).
https://doi.org/10.1070/IM2003v067n01ABEH000422
[ 35 ] Zhiqiang Zhang y Yaoyun Shi. "Complejidades de comunicación de funciones XOR simétricas". Información y computación cuántica 9, 255–263 (2009). URL: https:///dl.acm.org/doi/abs/10.5555/2011781.2011786.
https: / / dl.acm.org/ doi / abs / 10.5555 / 2011781.2011786
[ 36 ] Pierre Botteron. “Cajas no locales y complejidad de la comunicación”. Tesis de maestría. Universidad Paul Sabatier Toulouse III. (2022). URL: https:///pierre-botteron.github.io/Articles/2022-06-MSc-Thesis.pdf.
https://pierre-botteron.github.io/Articles/2022-06-MSc-Thesis.pdf
[ 37 ] Kwangil Bae y Wonmin Son. “Criterios generalizados de no localidad bajo la simetría de correlación”. Física. Rev. A 98, 022116 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.022116
[ 38 ] Markus Frembs, Sam Roberts y Stephen D. Bartlett. "La contextualidad como recurso para la computación cuántica basada en mediciones más allá de los qubits". Nueva Revista de Física 20, 103011 (2018).
https: / / doi.org/ 10.1088 / 1367-2630 / aae3ad
[ 39 ] 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
[ 40 ] Daniel Grier y Luke Schaeffer. "Circuitos interactivos de Clifford poco profundos: ventaja cuántica frente a NC¹ y más allá". En actas del 52º Simposio anual ACM SIGACT sobre teoría de la informática. Páginas 875–888. STOC 2020Nueva York, NY, EE.UU. (2020). Asociación para Maquinaria de Computación.
https: / / doi.org/ 10.1145 / 3357713.3384332
[ 41 ] Libor Caha, Xavier Coiteux-Roy y Robert Koenig. “La teletransportación de puerta de un solo qubit proporciona una ventaja cuántica” (2022). arXiv:2209.14158.
arXiv: 2209.14158
[ 42 ] François Le Gall. "Ventaja cuántica del caso medio con circuitos poco profundos". En Amir Shpilka, editor, 34ª Conferencia sobre Complejidad Computacional (CCC 2019). Volumen 137 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 21:1—-21:20. Dagstuhl, Alemania (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2019.21
[ 43 ] Matthew Coudron, Jalex Stark y Thomas Vidick. “Cambio de localidad por tiempo: aleatoriedad certificable a partir de circuitos de baja profundidad”. Comunicaciones en física matemática 382, 49–86 (2021).
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[ 44 ] Sergey Bravyi, David Gosset, Robert König y Marco Tomamichel. "Ventaja cuántica con circuitos poco profundos y ruidosos". Física de la naturaleza 16, 1040–1045 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z
[ 45 ] Atsuya Hasegawa y François Le Gall. "Ventaja cuántica con circuitos poco profundos bajo corrupción arbitraria". En Hee-Kap Ahn y Kunihiko Sadakane, editores, 32º Simposio Internacional sobre Algoritmos y Computación (ISAAC 2021). Volumen 212 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 74:1–74:16. Dagstuhl, Alemania (2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.ISAAC.2021.74
[ 46 ] 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 de entrada ilimitada". En actas del 51º Simposio anual ACM SIGACT sobre teoría de la informática. Páginas 515–526. STOC 2019Nueva York, NY, EE.UU. (2019). Asociación para Maquinaria de Computación.
https: / / doi.org/ 10.1145 / 3313276.3316404
[ 47 ] Natalia Parham. "Sobre el poder y las limitaciones de los circuitos cuánticos poco profundos". Tesis de maestría. Universidad de Waterloo. (2022). URL: https:///uwspace.uwaterloo.ca/handle/10012/18702.
https: / / uwspace.uwaterloo.ca/ handle / 10012/18702
[ 48 ] Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J. Yoder y Sarah Sheldon. “Ventaja cuántica para cálculos con espacio limitado”. Física de la naturaleza 17, 894–897 (2021).
https://doi.org/10.1038/s41567-021-01271-7
[ 49 ] Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore y Christopher Pollett. “Sobre el poder computacional del programa de ramificación cuántica y probabilística”. Información y Computación 203, 145–162 (2005).
https: / / doi.org/ 10.1016 / j.ic.2005.04.003
[ 50 ] D Shepherd y MJ Bremner. “Computación cuántica temporalmente desestructurada”. Actas de la Royal Society of London Serie A 465, 1413-1439 (2009).
https: / / doi.org/ 10.1098 / rspa.2008.0443
[ 51 ] Daniel M. Greenberger, Michael A. Horne y Anton Zeilinger. "Más allá del teorema de Bell". En Menas Kafatos, editor, Teorema de Bell, Teoría cuántica y Concepciones del Universo. Páginas 69–72. Dordrecht (1989). Springer Países Bajos.
https://doi.org/10.1007/978-94-017-0849-4_10
[ 52 ] Diogo Cruz, Romain Fournier, Fabien Gremion, Alix Jeannerot, Kenichi Komagata, Tara Tosic, Jarla Thiesbrummel, Chun Lam Chan, Nicolas Macris, Marc-André Dupertuis y Clément Javerzac-Galy. "Algoritmos cuánticos eficientes para los estados GHZ y W, e implementación en la computadora cuántica IBM". Tecnologías cuánticas avanzadas 2, 1900015 (2019).
https: / / doi.org/ 10.1002 / qute.201900015
[ 53 ] RF Werner y MM Wolf. "Desigualdades de correlación de campana multipartitas para dos observables dicotómicos por sitio". física Rev. A 64, 032112 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.032112
[ 54 ] Ryan O'Donnell. “Análisis de funciones booleanas”. Prensa de la Universidad de Cambridge. (2014). URL: http://www.cs.cmu.edu/ ./odonnell/papers/Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf.
http://www.cs.cmu.edu/~./odonnell/papers/Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf
[ 55 ] Anastasiya Chistopolskaya y Vladimir V. Podolskii. “La complejidad del árbol de decisión de paridad es mayor que la granularidad” (2018). arXiv:1810.08668.
arXiv: 1810.08668
[ 56 ] A Canteaut y M Videau. “Funciones booleanas simétricas”. Transacciones IEEE sobre teoría de la información 51, 2791–2811 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.851743
[ 57 ] Larry J. Stockmeyer. "Sobre la complejidad combinacional de determinadas funciones booleanas simétricas". Teoría de sistemas matemáticos 10, 323–336 (1976).
https: / / doi.org/ 10.1007 / BF01683282
[ 58 ] RF Arnold y MA Harrison. “Propiedades algebraicas de funciones booleanas simétricas y parcialmente simétricas”. Transacciones IEEE en computadoras electrónicas EC-12, 244–251 (1963).
https:///doi.org/10.1109/PGEC.1963.263535
[ 59 ] An Braeken y Bart Preneel. "Sobre la inmunidad algebraica de funciones booleanas simétricas". En Subhamoy Maitra, CE Veni Madhavan y Ramarathnam Venkatesan, editores, Progress in Cryptology - INDOCRYPT 2005. Volumen 3797 de Lecture Notes in Computer Science, páginas 35–48. Berlín, Heidelberg (2005). Springer Berlín Heidelberg.
https: / / doi.org/ 10.1007 / 11596219_4
[ 60 ] Harry Buhrman y Ronald de Wolf. “Medidas de complejidad y complejidad del árbol de decisión: una encuesta”. Informática teórica 288, 21–43 (2002).
https://doi.org/10.1016/S0304-3975(01)00144-X
[ 61 ] Matthew Amy, Dmitri Maslov, Michele Mosca y Martin Roetteler. "Un algoritmo de encuentro intermedio para la síntesis rápida de circuitos cuánticos de profundidad óptima". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados 32, 818–830 (2013).
https: / / doi.org/ 10.1109 / TCAD.2013.2244643
[ 62 ] VV Shende, SS Bullock e IL Markov. “Síntesis de circuitos de lógica cuántica”. Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados 25, 1000–1010 (2006).
https: / / doi.org/ 10.1109 / TCAD.2005.855930
[ 63 ] Juha J Vartiainen, Mikko Möttönen y Martti M Salomaa. “Descomposición eficiente de puertas cuánticas”. Física. Rev. Lett. 92, 177902 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.92.177902
[ 64 ] Bei Zeng, Xie Chen e Isaac L Chuang. "Operaciones Semi-Clifford, estructura de la jerarquía $mathcal{C}_{k}$ y complejidad de la puerta para la computación cuántica tolerante a fallas". Física. Rev. A 77, 042313 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.042313
[ 65 ] Gary J Mooney, Charles D Hill y Lloyd CL Hollenberg. "Síntesis de puerta de qubit único con costo óptimo en la jerarquía de Clifford". Cuántico 5, 396 (2021).
https://doi.org/10.22331/q-2021-02-15-396
[ 66 ] Nadish de Silva. "Teletransportación eficiente de puertas cuánticas en dimensiones superiores". Actas de la Royal Society A 477, 20200865 (2021).
https: / / doi.org/ 10.1098 / rspa.2020.0865
[ 67 ] Daniel Gottesman e Isaac L Chuang. "Demostrar la viabilidad de la computación cuántica universal mediante teletransportación y operaciones de un solo qubit". Naturaleza 402, 390–393 (1999).
https: / / doi.org/ 10.1038 / 46503
[ 68 ] Daniel Gottesman. “La representación de Heisenberg de las computadoras cuánticas” (1998). arXiv:quant-ph/9807006.
arXiv: quant-ph / 9807006
[ 69 ] Vadym Kliuchnikov, Dmitri Maslov y Michele Mosca. "Síntesis exacta, rápida y eficiente de unidades unitarias de un solo qubit generadas por las puertas Clifford y T". Información cuántica. Computadora. 13, 607–630 (2013). URL: https:///dl.acm.org/doi/abs/10.5555/2535649.2535653.
https: / / dl.acm.org/ doi / abs / 10.5555 / 2535649.2535653
[ 70 ] Nicolas Brunner, James Sharam y Tamás Vértesi. "Prueba de la estructura del entrelazamiento multipartito con desigualdades de campana". Física. Rev. Lett. 108, 110501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.108.110501
[ 71 ] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner y Thomas Vidick. "Los juegos entrelazados son difíciles de aproximar". Revista SIAM de Computación 40, 848–877 (2011).
https: / / doi.org/ 10.1137 / 090751293
[ 72 ] Yihui Quek, Eneet Kaur y Mark M. Wilde. “Estimación de trazas multivariada en profundidad cuántica constante”. Cuántico 8, 1220 (2024).
https://doi.org/10.22331/q-2024-01-10-1220
[ 73 ] Pedro Selinger. "Aproximación eficiente de Clifford + T de operadores de un solo qubit". Información cuántica. Computadora. 15, 159–180 (2015).
[ 74 ] Vadym Kliuchnikov, Dmitri Maslov y Michele Mosca. “Aproximación práctica de unitarios de un solo qubit mediante circuitos T y Quantum Quantum de un solo qubit”. Transacciones IEEE en computadoras 65, 161–172 (2016).
https: / / doi.org/ 10.1109 / TC.2015.2409842
[ 75 ] Neil J Ross. “Aproximación óptima de rotaciones Z CLIFFORD+V sin Ancilla”. Información cuántica. Computadora. 15, 932–950 (2015). URL: https:///dl.acm.org/doi/abs/10.5555/2871350.2871354.
https: / / dl.acm.org/ doi / abs / 10.5555 / 2871350.2871354
[ 76 ] Ethan Bernstein y Umesh Vazirani. “Teoría de la Complejidad Cuántica”. En actas del vigésimo quinto simposio anual de ACM sobre teoría de la informática. Páginas 11 a 20. STOC '93 Nueva York, NY, Estados Unidos (1993). Asociación para Maquinaria de Computación.
https: / / doi.org/ 10.1145 / 167088.167097
[ 77 ] Alex Bocharov, Martin Roetteler y Krysta M Svore. “Síntesis eficiente de circuitos cuánticos probabilísticos con respaldo”. Física. Rev. A 91, 052317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.052317
[ 78 ] Alex Bocharov, Martin Roetteler y Krysta M Svore. “Síntesis eficiente de circuitos cuánticos universales de repetición hasta el éxito”. Física. Rev. Lett. 114, 080502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.080502
[ 79 ] Ingo Wegener. "La complejidad de las funciones booleanas". John Wiley $&$ Sons, Inc. Estados Unidos (1987).
[ 80 ] Heribert Vollmer. "Introducción a la complejidad de los circuitos: un enfoque uniforme". Compañía editorial Springer, incorporada. (2010). 1ª edición. URL: https:///link.springer.com/book/10.1007/978-3-662-03927-4.
https://link.springer.com/book/10.1007/978-3-662-03927-4
[ 81 ] R. Smolensky. "Métodos algebraicos en la teoría de límites inferiores para la complejidad de circuitos booleanos". En actas del decimonoveno simposio anual de la ACM sobre teoría de la informática. Páginas 77–82. STOC '87Nueva York, NY, Estados Unidos (1987). Asociación para Maquinaria de Computación.
https: / / doi.org/ 10.1145 / 28395.28404
[ 82 ] Jaikumar Radhakrishnan. "Mejores límites para fórmulas de umbral". En [1991] Actas del 32º Simposio Anual sobre Fundamentos de la Informática. Páginas 314–323. Sociedad de Computación IEEE (1991).
https: / / doi.org/ 10.1109 / SFCS.1991.185384
[ 83 ] Michael J. Fischer, Albert R. Meyer y Michael S. Paterson. “$Omega(Nlog n)$ Límites inferiores de longitud de fórmulas booleanas”. SIAM J. Computación. 11, 416–427 (1982).
https: / / doi.org/ 10.1137 / 0211033
[ 84 ] Sanjeev Arora y Boaz Barak. "Complejidad computacional: un enfoque moderno". Prensa de la Universidad de Cambridge. Estados Unidos (2009). 1ª edición. URL: https:///dl.acm.org/doi/abs/10.5555/1540612.
https: / / dl.acm.org/ doi / abs / 10.5555 / 1540612
[ 85 ] Scott Aaronson. "¿Cuánta estructura se necesita para enormes aceleraciones cuánticas?" (2022). arXiv:2209.06930.
arXiv: 2209.06930
[ 86 ] David A Barrington. "Los programas de ramificación de tamaño polinomial de ancho acotado reconocen exactamente esos idiomas en NC1". Revista de Ciencias de la Computación y Sistemas 38, 150–164 (1989).
https://doi.org/10.1016/0022-0000(89)90037-8
[ 87 ] 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. STOC '11 Nueva York, NY, EE. UU. (2011). Asociación para Maquinaria de Computación.
https: / / doi.org/ 10.1145 / 1993636.1993682
[ 88 ] Peter W. Shor. "Algoritmos de tiempo polinomial para factorización prima y logaritmos discretos en una computadora cuántica". Revisión SIAM 41, 303–332 (1999).
https: / / doi.org/ 10.1137 / S0036144598347011
[ 89 ] Daniel R Simón. "Sobre el poder de la computación cuántica". Revista SIAM de Computación 26, 1474–1483 (1997).
https: / / doi.org/ 10.1137 / S0097539796298637
[ 90 ] Gilles Brassard, Harry Buhrman, Noah Linden, André Allan Méthot, Alain Tapp y Unger Falk. "Límite a la no localidad en cualquier mundo en el que la complejidad de la comunicación no sea trivial". Física. Rev. Lett. 96, 250401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.96.250401
[ 91 ] Wim van Dam. "Consecuencias inverosímiles de la no localidad superfuerte". Computación natural 12, 9–12 (2013).
https://doi.org/10.1007/s11047-012-9353-6
[ 92 ] Matthew Amy y Michele Mosca. "Optimización del recuento T y códigos Reed-Muller". Transacciones IEEE sobre teoría de la información 65, 4771–4784 (2019).
https: / / doi.org/ 10.1109 / TIT.2019.2906374
[ 93 ] Peter Bürgisser, Michael Clausen y Mohammad A Shokrollahi. “Teoría de la complejidad algebraica”. Volumen 315. Springer Science & Business Media. (2013). URL: https:///dl.acm.org/doi/abs/10.5555/1965416.
https: / / dl.acm.org/ doi / abs / 10.5555 / 1965416
[ 94 ] Guang Hao Low e Isaac L. Chuang. “Simulación hamiltoniana óptima mediante procesamiento cuántico de señales”. física Rev. Lett. 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501
[ 95 ] Jeongwan Haah. “Descomposición del producto de funciones periódicas en el procesamiento de señales cuánticas”. Cuántico 3, 190 (2019).
https://doi.org/10.22331/q-2019-10-07-190
[ 96 ] Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao y Avishay Tal. "Grado versus grado aproximado e implicaciones cuánticas del teorema de sensibilidad de Huang". En actas del 53º Simposio anual ACM SIGACT sobre teoría de la informática. Páginas 1330–1342. STOC 2021Nueva York, NY, EE.UU. (2021). Asociación para Maquinaria de Computación.
https: / / doi.org/ 10.1145 / 3406325.3451047
[ 97 ] Hao Huang. “Subgrafos inducidos de hipercubos y una prueba de la conjetura de la sensibilidad”. Anales de Matemáticas 190, 949–955 (2019).
https: / / doi.org/ 10.4007 / annals.2019.190.3.6
[ 98 ] Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha y Juris Smotrovs. "Separaciones en la complejidad de consultas basadas en funciones de puntero". J. ACM 64 (2017).
https: / / doi.org/ 10.1145 / 3106234
[ 99 ] Peter Høyer y Robert Špalek. “Circuitos cuánticos con despliegue ilimitado”. En Helmut Alt y Michel Habib, editores, STACS 2003. Páginas 234–246. Berlín, Heidelberg (2003). Springer Berlín Heidelberg.
https://doi.org/10.1007/3-540-36494-3_22
[ 100 ] Austin K Daniel, Yingyue Zhu, C Huerta Alderete, Vikas Buchemmavari, Alaina M Green, Nhung H Nguyen, Tyler G Thurtell, Andrew Zhao, Norbert M Linke y Akimasa Miyake. "Ventaja computacional cuántica atestiguada por juegos no locales con el estado de clúster cíclico". Física. Rev. Investigación 4, 033068 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033068
[ 101 ] Paul Herringer y Robert Raussendorf. “Clasificación de cables cuánticos basados en mediciones en PEPS estabilizadores”. Cuántico 7, 1041 (2023).
https://doi.org/10.22331/q-2023-06-12-1041
[ 102 ] Abhishek Anand. “Sobre el poder de los circuitos clásicos y cuánticos de baja profundidad entrelazados”. Tesis de maestría. Universidad de Waterloo. (2022). URL: https://uwspace.uwaterloo.ca/handle/10012/18805.
https: / / uwspace.uwaterloo.ca/ handle / 10012/18805
[ 103 ] Juan Preskill. “Computación cuántica en la era NISQ y más allá”. Cuántica 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79
[ 104 ] Bülent Demirel, Weikai Weng, Christopher Thalacker, Matty Hoban y Stefanie Barz. “Correlaciones para cálculo y cálculo para correlaciones”. npj Información cuántica 7, 1–8 (2021).
https://doi.org/10.1038/s41534-020-00354-2
[ 105 ] Manoranjan Swain, Amit Rai, Bikash K Behera y Prasanta K Panigrahi. “Demostración experimental de las violaciones de las desigualdades de Mermin y Svetlichny para los estados W y GHZ”. Procesamiento de información cuántica 18, 218 (2019).
https://doi.org/10.1007/s11128-019-2331-5
[ 106 ] Bo Yang, Rudy Raymond, Hiroshi Imai, Hyungseok Chang y Hidefumi Hiraishi. "Prueba de desigualdades de campana escalables para estados de gráficos cuánticos en dispositivos cuánticos de IBM". Revista IEEE sobre temas emergentes y seleccionados en circuitos y sistemas 12, 638–647 (2022).
https:///doi.org/10.1109/JETCAS.2022.3201730
[ 107 ] F. Baccari, R. Augusiak, I. Šupić, J. Tura y A. Acín. "Desigualdades de campana escalables para estados de gráficos de qubit y autopruebas sólidas". Física. Rev. Lett. 124, 020402 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.124.020402
[ 108 ] Ken X Wei, Isaac Lauer, Srikanth Srinivasan, Neereja Sundaresan, Douglas T McClure, David Toyli, David C McKay, Jay M Gambetta y Sarah Sheldon. "Verificación de estados multipartitos entrelazados de Greenberger-Horne-Zeilinger a través de múltiples coherencias cuánticas". Física. Rev. A 101, 032343 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.032343
[ 109 ] Wei-Jia Huang, Wei-Chen Chien, Chien-Hung Cho, Che-Chun Huang, Tsung-Wei Huang y Ching-Ray Chang. "Desigualdades de Mermin de múltiples qubits con medidas ortogonales en el sistema IBM Q de 53 qubits". Ingeniería cuántica 2, e45 (2020).
https:///doi.org/10.1002/que2.45
[ 110 ] Meron Sheffer, Daniel Azses y Emanuele G Dalla Torre. "Jugar juegos cuánticos no locales con seis Qubits ruidosos en la nube". Tecnologías cuánticas avanzadas 5, 2100081 (2022).
https: / / doi.org/ 10.1002 / qute.202100081
[ 111 ] Vedran Dunjko, Theodoros Kapourniotis y Elham Kashefi. “Computación clásica delegada segura mejorada cuánticamente”. Información cuántica. Computadora. 16, 61–86 (2016).
[ 112 ] Stefanie Barz, Vedran Dunjko, Florian Schlederer, Merritt Moore, Elham Kashefi e Ian A. Walmsley. “Computación delegada mejorada mediante coherencia”. Física. Rev. A 93, 032339 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.032339
[ 113 ] Marco Clementi, Anna Pappa, Andreas Eckstein, Ian A Walmsley, Elham Kashefi y Stefanie Barz. “Computación clásica multipartita utilizando recursos cuánticos”. Revisión física A 96, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062317
[ 114 ] Nasir Ahmed y Kamisetty Ramamohan Rao. “Transformación de Walsh-Hadamard”. En transformadas ortogonales para procesamiento de señales digitales. Páginas 99–152. Saltador (1975).
[ 115 ] Michael A Nielsen e Isaac L Chuang. “Computación cuántica e información cuántica: edición del décimo aniversario”. Prensa de la Universidad de Cambridge. (10).
https: / / doi.org/ 10.1017 / CBO9780511976667
[ 116 ] Philip Feinsilver y Jerzy Kocik. “Polinomios de Krawtchouk y matrices de krawtchouk”. Páginas 115–141. Avances recientes en probabilidad aplicada. Springer Estados Unidos. Boston, MA (2005).
https://doi.org/10.1007/0-387-23394-6_5
[ 117 ] Philip Feinsilver y René Schott. “Krawtchouk transforma y convoluciones”. Boletín de Ciencias Matemáticas Páginas 1 a 19 (2018).
https://doi.org/10.1007/s13373-018-0132-2
[ 118 ] M. Stobińska, A. Buraczewski, M. Moore, WR Clements, JJ Renema, SW Nam, T. Gerrits, A. Lita, WS Kolthammer, A. Eckstein e IA Walmsley. "La interferencia cuántica permite el procesamiento de información cuántica en tiempo constante". Avances científicos 5, eau9674 (2019).
https: / / doi.org/ 10.1126 / sciadv.aau9674
[ 119 ] Ravindran Kannan y Achim Bachem. "Algoritmos polinómicos para calcular las formas normales de Smith y Hermite de una matriz entera". Revista SIAM de Computación 8, 499–507 (1979).
https: / / doi.org/ 10.1137 / 0208040
[ 120 ] Josh Alman y Virginia Vassilevska Williams. “Un método láser refinado y una multiplicación de matrices más rápida”. En actas del trigésimo segundo simposio anual ACM-SIAM sobre algoritmos discretos. Páginas 522–539. SODA '21EE.UU. (2021). Sociedad de Matemática Industrial y Aplicada.
https: / / doi.org/ 10.1137 / 1.9781611976465.32
Citado por
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.
- Distribución de relaciones públicas y contenido potenciado por SEO. Consiga amplificado hoy.
- PlatoData.Network Vertical Generativo Ai. Empodérate. Accede Aquí.
- PlatoAiStream. Inteligencia Web3. Conocimiento amplificado. Accede Aquí.
- PlatoESG. Carbón, tecnología limpia, Energía, Ambiente, Solar, Gestión de residuos. Accede Aquí.
- PlatoSalud. Inteligencia en Biotecnología y Ensayos Clínicos. Accede Aquí.
- Fuente: https://quantum-journal.org/papers/q-2024-04-09-1312/
