1Escuela de Matemáticas, Instituto de Investigación en Ciencias Fundamentales (IPM), Teherán, Irán
2Escuela de Ciencias de la Computación, Instituto de Investigación en Ciencias Fundamentales (IPM), Teherán, Irán
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
Lin y Lin [16] han mostrado recientemente cómo a partir de un algoritmo de consulta clásico (árbol de decisión) para una función, podemos encontrar límites superiores en su complejidad de consulta cuántica. Más precisamente, han demostrado que dado un árbol de decisión para una función $ f: {0,1} ^ nto [m] $ cuya entrada se puede acceder a través de consultas a sus bits, y un $ textit {algoritmo de adivinación} $ que predice respuestas a las consultas, hay un algoritmo de consulta cuántica para $ f $ que genera como máximo $ O (sqrt {GT}) $ consultas cuánticas donde $ T $ es la profundidad del árbol de decisión y $ G $ es el número máximo de errores del algoritmo de adivinación. En este artículo damos una prueba simple y generalizamos este resultado para las funciones $ f: [ell] ^ n a [m] $ con alfabetos de entrada y salida no binarios. Nuestra principal herramienta para esta generalización es el programa span no binario que se ha desarrollado recientemente para funciones no binarias y el enlace de adversario dual. Como aplicaciones de nuestro resultado principal, presentamos varios límites superiores de consultas cuánticas, algunos de los cuales son nuevos. En particular, mostramos que la ordenación topológica de los vértices de un grafo dirigido $ mathcal G $ se puede realizar con $ O (n ^ {3/2}) $ consultas cuánticas en el modelo de matriz de adyacencia. Además, mostramos que la complejidad de la consulta cuántica de la máxima coincidencia bipartita está limitada por $ O (n ^ {3/4} sqrt {m + n}) $ en el modelo de lista de adyacencia.
► datos BibTeX
► referencias
[ 1 ] Andris Ambainis, Loïck Magnin, Martin Roetteler y Jérémie Roland. Adversarios asistidos por simetría para la generación de estados cuánticos. En 2011 IEEE 26th Annual Conference on Computational Complexity, páginas 167–177. IEEE, 2011. arXiv: 1012.2112, doi: 10.1109 / CCC.2011.24.
https: / / doi.org/ 10.1109 / CCC.2011.24
arXiv: 1012.2112
[ 2 ] Agnis Āriņš. Algoritmos cuánticos basados en programas de extensión para la conectividad y bipartición de gráficos. En Taller internacional de doctorado sobre métodos matemáticos y de ingeniería en informática, páginas 35–41. Springer, 2015. arXiv: 1510.07825v1, doi: 10.1007 / 978-3-319-29817-7_4.
https://doi.org/10.1007/978-3-319-29817-7_4
arXiv: 1510.07825v1
[ 3 ] Gilles Brassard, Peter Høyer y Alain Tapp. Conteo cuántico. En Kim G. Larsen, Sven Skyum y Glynn Winskel, editores, Automata, Languages and Programming, páginas 820–831, Berlín, Heidelberg. Springer Berlín Heidelberg. arXiv: 9805082, doi: 10.1007 / BFb0055105.
https: / � € ‹/ � €‹ doi.org/� $$$ ‹10.1007 / � €‹ BFb0055105
arXiv: 9805082
[ 4 ] Aleksandrs Belovs y Ben W Reichardt. Programas de extensión y algoritmos cuánticos para conectividad st y detección de garras. En Actas de la 20ª conferencia europea anual sobre algoritmos (ESA 12), páginas 193–204. Springer Berlín Heidelberg. arXiv: 1203.2603, doi: 10.1007 / 978-3-642-33090-2_18.
https://doi.org/10.1007/978-3-642-33090-2_18
arXiv: 1203.2603
[ 5 ] Salman Beigi y Leila Taghavi. Programa de extensión para funciones no binarias. Computación e información cuántica, 19 (9-10): 760–792, 2019. arXiv: 1805.02714, doi: 10.26421 / QIC19.9-10.
https: / / doi.org/ 10.26421 / QIC19.9-10
arXiv: 1805.02714
[ 6 ] Jill Cirasella. Algoritmos clásicos y cuánticos para encontrar ciclos. Tesis de maestría, Universidad de Amsterdam, 2006. URL: http: / / www.illc.uva.nl/ Research / Publications / Reports / MoL-2006-06.text.pdf.
http: / / www.illc.uva.nl/ Research / Publications / Reports / MoL-2006-06.text.pdf
[ 7 ] Andrew M. Childs y Robin Kothari. Complejidad de consultas cuánticas de propiedades de gráficos menores cerrados. Revista SIAM de Computación. arXiv: 1011.1443, doi: 10.4230 / LIPIcs.STACS.2011.661.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2011.661
arXiv: 1011.1443
[ 8 ] Chris Cade, Ashley Montanaro y Aleksandrs Belovs. Algoritmos cuánticos eficientes en el tiempo y el espacio para detectar ciclos y probar la bipartita. oct. arXiv: 1610.00581.
arXiv: 1610.00581
[ 9 ] Christoph Dürr y Peter Høyer. Un algoritmo cuántico para encontrar el mínimo. arXiv: 9607014.
arXiv: quant-ph / 9607014
[ 10 ] Christoph Dürr, Mark Heiligman, Peter Høyer y Mehdi Mhalla. Complejidad de la consulta cuántica de algunos problemas de gráficos. SIAM Journal on Computing, 35 (6): 1310-1328, 2006. arXiv: 0401091, doi: 10.1137 / 050644719.
https: / / doi.org/ 10.1137 / 050644719
arXiv: 0401091
[ 11 ] Bajo K Grover. Un algoritmo rápido de mecánica cuántica para la búsqueda de bases de datos. Actas, 28º Simposio anual de ACM sobre la teoría de la computación (STOC), páginas 212–219. arXiv: 9605043, doi: 10.1145 / 237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: 9605043
[ 12 ] John E Hopcroft y Richard M Karp. Un algoritmo $ O (n ^ {2.5}) $ para la máxima coincidencia en gráficos bipartitos. SIAM Journal On Computing, páginas 122-125, 1970. doi: 10.1137 / 0202019.
https: / / doi.org/ 10.1137 / 0202019
[ 13 ] Peter Høyer, Troy Lee y Robert Špalek. Los pesos negativos fortalecen a los adversarios. En Actas del trigésimo noveno simposio anual de ACM sobre teoría de la computación, páginas 526–535. ACM, 2007. arXiv: 0611054, doi: 10.1145 / 1250790.1250867.
https: / / doi.org/ 10.1145 / 1250790.1250867
arXiv: 0611054
[ 14 ] Tsuyoshi Ito y Stacey Jeffery. Programas de alcance aproximado. En 43 ° Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP 2016), 2015. URL: http: / / arxiv.org/ abs / 1507.00432, arXiv: 1507.00432, doi: 10.4230 / LIPIcs.ICALP.2016.12 .
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2016.12
arXiv: 1507.00432
[ 15 ] Arthur B. Kahn. Clasificación topológica de grandes redes. Communications of the ACM, 5: 558–562, 1962. doi: 10.1145 / 368996.369025.
https: / / doi.org/ 10.1145 / 368996.369025
[ 16 ] Cedric Yen-Yu Lin y Han-Hsuan Lin. Límites superiores en la complejidad de las consultas cuánticas inspirados en el probador de bombas Elitzur-Vaidman. Teoría de la Computación, 12: 1–35, 2016. URL: https: / / theoryofcomputing.org/ articles / v012a018 /, arXiv: 1410.0932, doi: 10.4086 / toc.2016.v012a018.
https: / / doi.org/ 10.4086 / toc.2016.v012a018
arXiv: 1410.0932
https: / / theoryofcomputing.org/ articles / v012a018 /
[ 17 ] Troy Lee, Rajat Mittal, Ben W Reichardt, Robert Špalek y Mario Szegedy. Complejidad de la consulta cuántica de conversión de estado. En 2011, 52º Simposio Anual de IEEE sobre Fundamentos de las Ciencias de la Computación, páginas 344–353. IEEE, 2011. arXiv: 1011.3020, doi: 10.1109 / FOCS.2011.75.
https: / / doi.org/ 10.1109 / FOCS.2011.75
arXiv: 1011.3020
[ 18 ] Troy Lee, Rajat Mittal, Ben W Reichardt y Robert Špalek. Un adversario de los algoritmos. arXiv: 1011.3020.
arXiv: 1011.3020
[ 19 ] Ben W Reichardt. Programas de extensión y complejidad de consultas cuánticas: el límite general del adversario es casi estrecho para cada función booleana. En 2009, quincuagésimo simposio anual del IEEE sobre fundamentos de la informática, páginas 50–544. IEEE, 551. arXiv: 2009, doi: 0904.2759 / FOCS.10.1109.
https: / / doi.org/ 10.1109 / FOCS.2009.55
arXiv: 0904.2759
[ 20 ] Ben W Reichardt y Robert Špalek. Algoritmo cuántico basado en el programa Span para evaluar fórmulas. volumen 8, páginas 291–319. Teoría de la Computación, 2012. URL: http: / / www.theoryofcomputing.org/ articles / v008a013, arXiv: 0710.2630, doi: 10.4086 / toc.2012.v008a013.
https: / / doi.org/ 10.4086 / toc.2012.v008a013
arXiv: 0710.2630
http: / / www.theoryofcomputing.org/ articles / v008a013
[ 21 ] Yaoyun Shi. Límites cuánticos inferiores para la colisión y los problemas de distinción del elemento. En Proceedings 43rd Annual IEEE Symposium on Foundations of Computer Science, páginas 513–519, 2002. arXiv: 0112086, doi: 10.1109 / SFCS.2002.1181975.
https: / / doi.org/ 10.1109 / SFCS.2002.1181975
arXiv: 0112086
[ 22 ] Robert Endre Tarjan. Árboles de expansión disjuntos de bordes y búsqueda en profundidad primero. Acta Informatica, 6 (2): 171-185, 1976. doi: 10.1007 / BF00268499.
https: / / doi.org/ 10.1007 / BF00268499
[ 23 ] Shengyu Zhang. Sobre el poder de los límites inferiores de Ambainis. Ciencias de la Computación Teórica, 339 (2-3): 241-256, 2005. arXiv: 0311060, doi: 10.1016 / j.tcs.2005.01.019.
https: / / doi.org/ 10.1016 / j.tcs.2005.01.019
arXiv: 0311060
Citado por
No se pudo recuperar Crossref citado por datos durante el último intento 2020-03-02 16:26:18: No se pudieron obtener los datos citados por 10.22331 / q-2020-03-02-241 de Crossref. Esto es normal si el DOI se registró recientemente. En ANUNCIOS SAO / NASA no se encontraron datos sobre las obras citadas (último intento 2020-03-02 16:26:19).
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.
Fuente: https://quantum-journal.org/papers/q-2020-03-02-241/
