Un importante artículo de 2003 de Childs et al.introdujo el "problema de los árboles combinados": un problema que admite una aceleración cuántica exponencial que es diferente a casi cualquier otro problema que conozcamos. En este problema, se nos da un gráfico exponencialmente grande como el que se muestra a continuación, que consta de dos árboles binarios completos de profundidad n, cuyas hojas están conectadas entre sí por un ciclo aleatorio. Se nos proporciona la etiqueta del vértice de ENTRADA. También se nos proporciona un oráculo que, dado como entrada, la etiqueta de cualquier vértice, nos dice las etiquetas de sus vecinos. Nuestro objetivo es encontrar el vértice EXIT (que puede reconocerse fácilmente, como el único vértice de grado 2 en el gráfico que no sea el vértice ENTRADA). Podemos suponer que las etiquetas son largas cadenas aleatorias, de modo que con una probabilidad abrumadora,El oráculo le dará el vértice que no sea el vértice de ENTRADA.
Childs y cols. demostró que un algoritmo de caminata cuántica es capaz de atravesar este gráfico y encontrar el vértice EXIT después de los pasos poli (n). Por el contrario, también mostraron que cualquier algoritmo aleatorio clásico requiere pasos exp (n) para encontrar el vértice EXIT con alta probabilidad. Declararon su límite inferior como Ω (2 n / 6 ), pero creo que un examen más detallado de su prueba produce Ω (2 n / 2 ). Intuitivamente, esto se debe a que con una probabilidad abrumadora, una caminata aleatoria en el gráfico (incluso una caminata que se evita a sí mismo, etc.) se quedará atascada en la vasta región media por una cantidad de tiempo exponencial: cada vez que un caminante comienza a dirigirse hacia la SALIDA , el número mucho mayor de bordes que apuntan lejos de la SALIDA actuará como una "fuerza repulsiva" que lo empuja hacia el centro.
La forma en que formalizaron el argumento fue mostrar que, hasta que se visita ~ 2 n / 2 vértices, un algoritmo aleatorio ni siquiera ha encontrado ningún ciclo en el gráfico: el subgrafo inducido que se ha visto hasta ahora es solo un árbol, sin proporcionar información sobre dónde podría estar el vértice EXIT.
Estoy interesado en precisar la complejidad de la consulta aleatoria de este problema con mayor precisión. Mi pregunta es esta:
¿Alguien puede encontrar un algoritmo clásico que encuentre el vértice EXIT en menos de ~ 2 n pasos --- digamos, en O (2 n / 2 ) u O (2 2n / 3 )? Alternativamente, ¿alguien puede dar un límite inferior mejor que Ω (2 n / 2 )?
(Tenga en cuenta que, por la paradoja del cumpleaños, no es difícil encontrar ciclos en el gráfico después de O (2 n / 2 ) pasos. La pregunta es si uno puede usar los ciclos para obtener pistas sobre dónde está el vértice EXIT).
Si alguien puede mejorar el pasado límite inferior Ω (2 n / 2 ), entonces, que yo sepa, esto proporcionaría el primer ejemplo comprobable de un problema de caja negra con una aceleración cuántica exponencial, cuya complejidad de consulta aleatoria es mayor que √N . (Donde N ~ 2 n es el tamaño del problema).
Actualización: He aprendido de Andrew Childs que, en esta nota , Fenner y Zhang mejoran explícitamente el límite inferior aleatorio para árboles unidos a Ω (2 n / 3 ). Si estuvieran dispuestos a aceptar una probabilidad de éxito constante (en lugar de exponencialmente pequeña), creo que podrían mejorar aún más el límite, a Ω (2 n / 2 ).
