1Boston University
2Cuántica de Microsoft
3La Universidad de Georgetown
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
Proporcionamos nuevos algoritmos cuánticos para evaluar funciones compuestas cuyas entradas pueden compartirse entre puertas de nivel inferior. Sea $ f $ una función booleana de $ m $ -bit y considere una función $ n $ -bit $ F $ obtenida aplicando $ f $ a conjunciones de subconjuntos posiblemente superpuestos de $ n $ variables. Si $ f $ tiene una complejidad de consulta cuántica $ Q (f) $, damos un algoritmo para evaluar $ F $ usando $ tilde {O} (sqrt {Q (f) cdot n}) $ consultas cuánticas. Esto mejora el límite de $ O (Q (f) cdot sqrt {n}) $ que sigue al tratar cada conjunción de forma independiente, y nuestro límite es estrecho para las opciones del peor caso de $ f $. Usando técnicas completamente diferentes, probamos un teorema de composición ajustada similar para el grado aproximado de $ f $.
Al aplicar de forma recursiva nuestros teoremas de composición, obtenemos un límite superior de $ tilde {O} (n ^ {1-2 ^ {- d}}) $ casi óptimo en la complejidad de la consulta cuántica y el grado aproximado de profundidad de tamaño lineal - $ d $ AC $ ^ 0 $ circuitos. Como consecuencia, dichos circuitos pueden aprenderse con PAC en un tiempo subexponencial, incluso en un entorno agnóstico desafiante. Antes de nuestro trabajo, no se conocía un algoritmo de tiempo subexponencial ni siquiera para circuitos de tamaño lineal de profundidad 3 AC $ ^ 0 $.
Como consecuencia adicional, mostramos que AC $ ^ 0 circ oplus $ circuitos de profundidad $ d + 1 $ requieren tamaño $ tilde {Omega} (n ^ {1 / (1-2 ^ {- d})}) geq omega (n ^ {1+ 2 ^ {- d}}) $ para calcular la función del producto interno incluso en promedio. El límite inferior del mejor tamaño anterior era $ Omega (n ^ {1 + 4 ^ {- (d + 1)}}) $ y solo se mantuvo en el peor de los casos (Cheraghchi et al., JCSS 2018).
► datos BibTeX
► referencias
[ 1 ] Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath y Alon Rosen. Funciones pseudoaleatorias débiles candidatas en AC $ ^ 0 circ mathsf {MOD} _2 $. En Actas de la 5ª conferencia sobre innovaciones en informática teórica, ITCS '14, páginas 251–260, 2014.
https: / / doi.org/ 10.1145 / 2554797.2554821
[ 2 ] Miklos Ajtai y Michael Ben-Or. Un teorema sobre cálculos probabilísticos de profundidad constante. En Actas del 16º Simposio Anual de ACM sobre Teoría de la Computación, STOC '84, páginas 471–474, 1984.
https: / / doi.org/ 10.1145 / 800057.808715
[ 3 ] Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek y Shengyu Zhang. Cualquier fórmula Y-O de tamaño $ N $ puede evaluarse en el tiempo $ N ^ {1/2 + o (1)} $ en una computadora cuántica. SIAM Journal on Computing, 39 (6): 2513-2530, 2010.
https: / / doi.org/ 10.1137 / 080712167
[ 4 ] Charles H. Bennett, Ethan Bernstein, Gilles Brassard y Umesh Vazirani. Fortalezas y debilidades de la computación cuántica. SIAM Journal on Computing, 26 (5): 1510-1523, 1997.
https: / / doi.org/ 10.1137 / S0097539796300933
[ 5 ] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca y Ronald de Wolf. Límites inferiores cuánticos por polinomios. Revista de la ACM, 48 (4): 778–797, 2001.
https: / / doi.org/ 10.1145 / 502090.502097
[ 6 ] Michel Boyer, Gilles Brassard, Peter Høyer y Alain Tapp. Límites estrictos en la búsqueda cuántica. Fortschritte der Physik, 46 (4-5): 493–505, 1998.
[ 7 ] Harry Buhrman, Richard Cleve, Ronald de Wolf y Christof Zalka. Límites para algoritmos cuánticos de error pequeño y error cero. En el 40º Simposio anual sobre los fundamentos de la informática, páginas 358–368, 1999.
https: / / doi.org/ 10.1109 / sffcs.1999.814607
[ 8 ] Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler y Prashant Nalini Vasudevan. Sobre el poder del conocimiento estadístico cero. En el 58 ° Simposio anual sobre fundamentos de la informática (FOCS 2017), páginas 708–719, 2017.
https: / / doi.org/ 10.1109 / focs.2017.71
[ 9 ] Harry Buhrman y Ronald de Wolf. Medidas de complejidad y complejidad del árbol de decisiones: una encuesta. Informática teórica, 288 (1): 21–43, 2002.
https://doi.org/10.1016/S0304-3975(01)00144-X
[ 10 ] Mark Bun, Robin Kothari y Justin Thaler. El método polinomial contraataca: estrechos límites de consulta cuántica a través de polinomios duales. En Actas del 50 ° Simposio anual de ACM SIGACT sobre teoría de la computación, STOC 2018, páginas 297–310, 2018.
https: / / doi.org/ 10.1145 / 3188745.3188784
[ 11 ] Mark Bun, Robin Kothari y Justin Thaler. Algoritmos cuánticos y polinomios aproximados para funciones compuestas con entradas compartidas. En Actas del Simposio anual ACM-SIAM sobre algoritmos discretos (SODA) de 2019, páginas 662–678, 2019.
https: / / doi.org/ 10.1137 / 1.9781611975482.42
[ 12 ] Paul Beame y Widad Machmouchi. La complejidad de la consulta cuántica de AC $ ^ 0 $. Computación e información cuántica, 12 (7-8): 670–676, 2012.
[ 13 ] Harry Buhrman, Ilan Newman, Hein Röhrig y Ronald de Wolf. Polinomios robustos y algoritmos cuánticos. Teoría de los sistemas informáticos, 40 (4): 379–395, 2007.
https: / / doi.org/ 10.1007 / s00224-006-1313-z
[ 14 ] Jehoshua Bruck y Roman Smolensky. Funciones de umbral polinomial, funciones AC $ ^ 0 $ y normas espectrales. SIAM Journal on Computing, 21 (1): 33–42, 1992.
https: / / doi.org/ 10.1137 / 0221003
[ 15 ] Mark Bun y Justin Thaler. Un límite inferior casi óptimo en el grado aproximado de AC $ ^ 0 $. En IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS 2017), páginas 1 a 12, 2017.
https: / / doi.org/ 10.1109 / FOCS.2017.10
[ 16 ] Mark Bun y Justin Thaler. Columna invitada: Grado aproximado en computación clásica y cuántica. SIGACT News, 51 (4): 48–72, enero de 2021.
https: / / doi.org/ 10.1145 / 3444815.3444825
[ 17 ] Andrew M. Childs, Richard Cleve, Stephen P. Jordan y David Yonge-Mallo. Algoritmo cuántico de consulta discreta para árboles NAND. Teoría de la Computación, 5: 119-123, 2009.
https: / / doi.org/ 10.4086 / toc.2009.v005a005
[ 18 ] Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer y Ning Xie. AC0 $ circ $ MOD2 límites inferiores para el producto interno booleano. En LIPIcs-Leibniz International Proceedings in Informatics, volumen 55. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2016.35
[ 19 ] Chris Calabro, Russell Impagliazzo y Ramamohan Paturi. La complejidad de la satisfacibilidad de los circuitos de pequeña profundidad. En Taller internacional sobre computación exacta y parametrizada, páginas 75–85, 2009.
https://doi.org/10.1007/978-3-642-11269-0_6
[ 20 ] Andrew M. Childs, Shelby Kimmel y Robin Kothari. La complejidad de la consulta cuántica de fórmulas de lectura múltiple. En el 20º Simposio Europeo Anual de Algoritmos (ESA 2012), páginas 337–348, 2012.
https://doi.org/10.1007/978-3-642-33090-2_30
[ 21 ] Shiva Chaudhuri y Jaikumar Radhakrishnan. Restricciones deterministas en la complejidad del circuito. En Actas del vigésimo octavo simposio anual de ACM sobre teoría de la computación, STOC '96, páginas 30–36, 1996.
https: / / doi.org/ 10.1145 / 237814.237824
[ 22 ] Gil Cohen e Igor Shinkar. La complejidad de DNF de paridades. En Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, páginas 47–58, 2016.
https: / / doi.org/ 10.1145 / 2840728.2840734
[ 23 ] Ning Ding, Yanli Ren y Dawu Gu. PAC aprendizaje profundidad-3 AC $ ^ 0 $ circuitos de ventilador superior acotado. En Proceedings of the 28th International Conference on Algorithmic Learning Theory, volumen 76 de Proceedings of Machine Learning Research, páginas 667–680, 2017. URL: http: / / procedure.mlr.press/ v76 / ding17a.html.
http: / / procedure.mlr.press/ v76 / ding17a.html
[ 24 ] Michael Ezra y Ron D. Rothblum. Los circuitos pequeños implican protocolos Arthur-Merlin eficientes. Informe técnico TR21-127, Coloquio electrónico sobre complejidad computacional (ECCC), 2021. URL: https: / / eccc.weizmann.ac.il/ report / 2021/127 /.
https: / / eccc.weizmann.ac.il/ report / 2021/127 /
[ 25 ] Edward Farhi, Jeffrey Goldstone y Sam Gutmann. Un algoritmo cuántico para el árbol NAND de Hamilton. Teoría de la Computación, 4 (1): 169-190, 2008.
https: / / doi.org/ 10.4086 / toc.2008.v004a008
[ 26 ] Yuval Filmus, Hamed Hatami, Steven Heilman, Elchanan Mossel, Ryan O'Donnell, Sushant Sachdeva, Andrew Wan y Karl Wimmer. Análisis real en informática: colección de problemas abiertos, 2014. URL: https: // simons.berkeley.edu/ sites / default / files / openprobsmerged.pdf.
https: / / simons.berkeley.edu/ sites / default / files / openprobsmerged.pdf
[ 27 ] Lov K. Grover. Un algoritmo rápido de mecánica cuántica para la búsqueda de bases de datos. En Actas del vigésimo octavo simposio anual de ACM sobre teoría de la computación, STOC '96, páginas 212–219, 1996.
https: / / doi.org/ 10.1145 / 237814.237866
[ 28 ] Peter Høyer, Troy Lee y Robert Špalek. Los pesos negativos fortalecen a los adversarios. En Actas del 39º Simposio sobre Teoría de la Computación (STOC 2007), páginas 526–535, 2007.
https: / / doi.org/ 10.1145 / 1250790.1250867
[ 29 ] Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour y Rocco A. Servedio. Aprendizaje agnóstico de medios espacios. SIAM Journal on Computing, 37 (6): 1777–1805, 2008.
https: / / doi.org/ 10.1137 / 060649057
[ 30 ] Adam Klivans, Pravesh Kothari e Igor C. Oliveira. Construir funciones duras usando algoritmos de aprendizaje. En IEEE Conference on Computational Complexity (CCC 2013), páginas 86–97, 2013.
https: / / doi.org/ 10.1109 / CCC.2013.18
[ 31 ] Michal Koucký, Clemens Lautemann, Sebastian Poloczek y Denis Therien. Límites inferiores del circuito a través de juegos Ehrenfeucht-Fraisse. En la 21ª Conferencia Anual de IEEE sobre Complejidad Computacional (CCC 2006), páginas 190–201, 07 de 2006.
https: / / doi.org/ 10.1109 / CCC.2006.12
[ 32 ] Swastik Kopparty. AC0 límites inferiores y pseudoaleatoriedad. Notas de la conferencia de "Temas en la teoría de la complejidad y la pseudoaleatoriedad (primavera de 2013)" en la Universidad de Rutgers. http: / / sites.math.rutgers.edu/ sk1233 /ourses / topics-S13 / lec4.pdf (Consultado el 12 de julio de 2018), 2013.
http: / / sites.math.rutgers.edu/ ~ sk1233 /ourses / topics-S13 / lec4.pdf
[ 33 ] Michal Koucký. Complejidad del circuito de lenguajes regulares. Teoría de los sistemas informáticos, 45 (4): 865–879, 2009.
https: / / doi.org/ 10.1007 / s00224-009-9180-z
[ 34 ] Adam R. Klivans y Rocco A. Servedio. Aprendiendo DNF a tiempo $ 2 ^ {{tilde O} (n ^ {1/3})} $. Revista de Ciencias de la Computación y Sistemas, 68 (2): 303–318, 2004.
https: / / doi.org/ 10.1016 / j.jcss.2003.07.007
[ 35 ] Michael J. Kearns, Robert E. Schapire y Linda M. Sellie. Hacia un aprendizaje agnóstico eficiente. Aprendizaje automático, 17 (2-3): 115-141, 1994.
https: / / doi.org/ 10.1007 / bf00993468
[ 36 ] Wee Sun Lee, Peter L. Bartlett y Robert C. Williamson. Sobre el aprendizaje agnóstico eficiente de combinaciones lineales de funciones básicas. En Actas de la octava conferencia anual sobre teoría del aprendizaje computacional, páginas 369–376, 1995.
https: / / doi.org/ 10.1145 / 225298.225343
[ 37 ] Troy Lee. Diapositivas para el artículo "algoritmos de consulta cuántica mejorados para la búsqueda de triángulos y pruebas de asociatividad" por T. Lee, F. Magniez, M. Santha. Disponible en http: / / research.cs.rutgers.edu/ troyjlee / troy_triangle.pdf (Consultado el 11 de julio de 2018), 2012.
http: / / research.cs.rutgers.edu/ ~ troyjlee / troy_triangle.pdf
[ 38 ] Troy Lee y Adi Shraibman. Límites inferiores en la complejidad de la comunicación. Fundamentos y tendencias en informática teórica, 3 (4): 263–399, 2009.
https: / / doi.org/ 10.1561 / 0400000040
[ 39 ] Noam Nisan. Fórmula más corta para un CNF monótono de $ n $ a plazo. Theoretical Computer Science Stack Exchange, 2011. https: / / cstheory.stackexchange.com/ q / 7087 (versión: 2011-06-23).
https: / / cstheory.stackexchange.com/ q / 7087
[ 40 ] Noam Nisan y Mario Szegedy. Sobre el grado de funciones booleanas como polinomios reales. Complejidad computacional, 4: 301–313, 1994.
https: / / doi.org/ 10.1007 / BF01263419
[ 41 ] Igor C. Carboni Oliveira y Rahul Santhanam. Conspiraciones entre algoritmos de aprendizaje, límites inferiores de circuito y pseudoaleatoriedad. En 32nd Computational Complexity Conference (CCC 2017), volumen 79 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 18: 1–18: 49, 2017.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.18
[ 42 ] Alexander A Razborov. Límites inferiores en el tamaño de los circuitos de profundidad limitada sobre una base completa con adición lógica. Notas matemáticas de la Academia de Ciencias de la URSS, 41 (4): 333–338, 1987.
[ 43 ] Ben Reichardt. Reflexiones para algoritmos de consulta cuántica. En SODA '11: Actas del 22º Simposio ACM-SIAM sobre algoritmos discretos, páginas 560–569, 2011.
https: / / doi.org/ 10.1137 / 1.9781611973082.44
[ 44 ] Alexander A. Razborov y Alexander A. Sherstov. El rango de signo de AC $ ^ 0 $. SIAM Journal on Computing, 39 (5): 1833–1855, 2010.
https: / / doi.org/ 10.1137 / 080744037
[ 45 ] Prabhakar Ragde y Avi Wigderson. Circuitos de umbral polilog de profundidad constante de tamaño lineal. Cartas de procesamiento de información, 39 (3): 143-146, 1991.
https://doi.org/10.1016/0020-0190(91)90110-4
[ 46 ] Alexander A. Sherstov. El método de matriz de patrones. SIAM Journal on Computing, 40 (6): 1969–2000, 2011.
https: / / doi.org/ 10.1137 / 080733644
[ 47 ] Alexander A. Sherstov. Fuertes teoremas de productos directos para la comunicación cuántica y la complejidad de las consultas. En Actas del 43º simposio anual de ACM sobre teoría de la computación (STOC 2011), páginas 41–50, 2011.
https: / / doi.org/ 10.1145 / 1993636.1993643
[ 48 ] Alexander A. Sherstov. La intersección de dos medios espacios tiene un grado de umbral alto. SIAM Journal on Computing, 42 (6): 2329-2374, 2013.
https: / / doi.org/ 10.1137 / 100785260
[ 49 ] Alexander A. Sherstov. Hacer polinomios robustos al ruido. Teoría de la Computación, 9: 593–615, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a018
[ 50 ] Alexander A. Sherstov. El poder de la asimetría en circuitos de profundidad constante. En IEEE 56th Annual Symposium on Foundations of Computer Science, páginas 431–450, 2015.
https: / / doi.org/ 10.1109 / FOCS.2015.34
[ 51 ] Alexander A. Sherstov. Polinomios algorítmicos. En Actas del 50 ° Simposio Anual ACM SIGACT sobre Teoría de la Computación (STOC 2018), 2018.
https: / / doi.org/ 10.1145 / 3188745.3188958
[ 52 ] Rahul Santhanam y Srikanth Srinivasan. Sobre los límites de la dispersión. En Coloquio internacional sobre autómatas, lenguajes y programación, páginas 774–785. Springer, 2012.
https://doi.org/10.1007/978-3-642-31594-7_65
[ 53 ] Rocco A. Servedio y Li-Yang Tan. ¿Qué clases de circuitos se pueden aprender con ahorros no triviales? En 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volumen 67 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 30: 1–30: 21, 2017.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2017.30
[ 54 ] Rocco A Servedio y Emanuele Viola. En un caso especial de rigidez. Informe técnico TR12-144, Coloquio electrónico sobre complejidad computacional (ECCC), 2012. URL: https: / / eccc.weizmann.ac.il/ report / 2012/144 /.
https: / / eccc.weizmann.ac.il/ report / 2012/144 /
[ 55 ] Avishay Tal. La complejidad de la fórmula bipartita del producto interno es cuadrática. Informe técnico TR16-181, Coloquio electrónico sobre complejidad computacional (ECCC), 2016. URL: https: / / eccc.weizmann.ac.il/ report / 2016/181 /.
https: / / eccc.weizmann.ac.il/ report / 2016/181 /
[ 56 ] Avishay Tal. Fórmula de límites inferiores mediante el método cuántico. En Actas del 49º Simposio Anual ACM SIGACT sobre Teoría de la Computación (STOC 2017), páginas 1256–1268, 2017.
https: / / doi.org/ 10.1145 / 3055399.3055472
[ 57 ] Avishay Tal. Comunicación personal, 2018.
[ 58 ] Leslie G. Valiente. Una teoria de lo aprendible. Communications of the ACM, 27 (11): 1134-1142, noviembre de 1984.
https: / / doi.org/ 10.1145 / 1968.1972
Citado por
[1] Scott Aaronson, Daniel Grier y Luke Schaeffer, "Una tricotomía de complejidad de consulta cuántica para lenguajes regulares", arXiv: 1812.04219.
[2] Kamil Khadiev y Liliya Safina, “Algoritmo cuántico para el enfoque de programación dinámica para DAG. Aplicaciones para la evaluación del polinomio de Zhegalkin y algunos problemas en los DAG ”, arXiv: 1804.09950.
Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2021-09-16 14:44:06). 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-16 14:44:04: No se pudieron obtener los datos citados por 10.22331 / q-2021-09-16-543 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-16-543/
