Tiempos de golpe cuántico de un disparo

En el artículo Quantum Random Walks Hit Exponencialmente más rápido ( arXiv: quant-ph / 0205083 ) Kempe da una noción del tiempo de golpeo para caminatas cuánticas (en el hipercubo) que no es muy popular en la literatura de la caminata cuántica. Se define de la siguiente manera:

One-Shot Quantum Golpear Tiempo: Un paseo de tiempo discreto cuántica tiene una de una sola vez ( | Psi 0 ⟩ , | Psi f ⟩ ) tiempo -hitting si | ⟨ Psi f | U T | Ψ 0 ⟩ | 2 ≥ p donde | Ψ 0 ⟩ es el estado inicial, | Ψ f ⟩ es el estado de destino, y p > $(T,p)$$(|\Psi_0\rangle,|\Psi^f\rangle)$$|\langle\Psi^f|U^T|\Psi_0\rangle|^2 \geq p$$|\Psi_0\rangle$$|\Psi^f\rangle$$p>0$ es la probabilidad de golpear

Normalmente le gustaría saber el mínimo tal que p > 0 . No es posible (corríjame si me equivoco) definir una noción de tiempo promedio de golpe porque necesitará realizar mediciones durante la caminata, y eso la colapsaría en una caminata clásica. Por eso tenemos la noción de una sola vez. En el mismo trabajo, hay una aplicación para el enrutamiento cuántico (véase la sección 5 ).$T$$p>0$

Para saber que la caminata llegó al vértice objetivo, debe realizar una medición solo en ese nodo. Por ejemplo, en el hipercubo dimensional con 2 n nodos si comienza en el nodo | Ψ 0 ⟩ = | 00 ... 00 ⟩ y tienen como nodo de destino | Ψ f$n$$2^n$$|\Psi_0\rangle=|00\dots00\rangle$ , los espectáculos de papel que T = O ( n ) con una probabilidad de error limitado, es decir, p → 1 como$|\Psi^f\rangle=|11\dots11\rangle$$T=O(n)$$p\to 1$$n$se vuelve muy grande. Entonces, para detectar que la caminata llegó a que hacer una medición después de Ohmio ( n ) pasos. Esta es una aceleración exponencial.$|11\dots11\rangle$$\Omega(n)$

Preguntas:

1. Para usar esta noción de tiempo de búsqueda para la búsqueda, necesita saber al menos la distancia del vértice objetivo desde el origen, porque así es como sabe cuándo aplicar su medición. Supongamos que tiene un gráfico y lo establece como vértice inicial v 0 y desea alcanzar v f . Supongamos también que T = O ( d i s t ( v 0 , v f ) ) y p ≥ 1 / 2 . Bueno $G$$v_0$$v^f$$T=O(dist(v_0,v^f))$$p\geq 1/2$$T$es obvio porque necesitas al menos tantos pasos para alcanzarlo. ¿Tiene sentido usar este tiempo de búsqueda para la búsqueda? Si sabes dónde está el nodo, no tiene sentido buscar, pero tener una información como "distancia desde el vértice inicial" pero no saber exactamente dónde está el objetivo, ¿esta noción de tiempo de golpeo da algo interesante (vale la pena estudiar? ) algoritmo de búsqueda?

2. ¿Tiene sentido la aplicación al enrutamiento cuántico? En el documento dice que puede usarse para enrutar paquetes, pero me parece que solo puede enviar 1 bit, por ejemplo, ¿llegó al destino o no? ¿Se puede realmente enviar un estado cuántico en este marco? En el documento, este problema no se está abordando.

3. Esta es quizás una pregunta tonta, pero aquí va. ¿Puedes usar esta noción de tiempo de golpe para construir un "interferómetro generalizado Mach-Zender"?

Soy consciente de las otras nociones de tiempos de bateo para caminatas cuánticas (como las de Szegedy's o Ambainis ). Estoy particularmente interesado en este tiempo de golpe específico.

Actualización (9/24/2010): Gracias a Joe Fitzsimons las preguntas 2 y 3 fueron respondidas por completo. Aunque la pregunta número 1 aún permanece. Primero, volveré a plantear la pregunta 2 en términos más específicos ahora que terminé de leer el documento que Joe me recomendó a mí y a un par más (por ejemplo, consulte arXiv: 0802.1224 ), y luego daré un ejemplo concreto de lo que tengo en mente para la pregunta 1.

2 '. Si está enviando un mensaje concreto (como una secuencia de bits clásicos), puede usar un unitario más complicado que copiará esta información durante los pasos de la caminata. Para enviar estados cuánticos necesitas algo más. El canal de cadenas giratorias utiliza una matriz lineal de qubits con un acoplamiento fijo. Puede poner el estado (estado puro, no sé si funciona para estados mixtos) que desea transmitir en un extremo y va al otro extremo con alta fidelidad según los resultados numéricos. Todavía tengo que pensarlo más, pero tengo dos ideas: i) poner una cadena en cada enlace del gráfico, o ii) hacer la caminata, encontrar el estado objetivo, luego hacer el canal entre el estado inicial y el objetivo y luego enviar el estado. ¿Alguno de estos enfoques es posible? ¿Funciona con estados mixtos?

1 '. Considere una caminata en una cuadrícula bidimensional centrada en el origen con nodos con cada lado con longitud $n$ . Establezca el estado inicial env0=(0,0)y el estado objetivo envf=($\sqrt{n}$$v_0=(0,0)$dondea=0,…,$v^f=(\sqrt{n}-1,a)$. Debido a que la caminata es simétrica, tenemos el mismo tiempo de golpe y las mismas probabilidades de golpe para cualquier objetivo en algún lugar en el borde de la cuadrícula como se muestra a continuación.$a=0,\dots,\sqrt{n}-1$

Por lo tanto, la información que tenemos es que . Podemos usar esto para saber cuándo hacer la medición. ¿Se puede usar el tiempo de golpe único para buscar en esta cuadrícula? Aquí necesitas esa información. Un problema abierto al buscar una cuadrícula es que sabemos queΩ($dist(v_0,v^f)=\Omega(\sqrt{n})$es un límite inferior para la búsqueda, y para las cuadrículas el mejor límite superior esO($\Omega(\sqrt{n})$. O no estamos siendo capaces de encontrar un algoritmo mejor, o las técnicas para probar los límites inferiores cuando los usas en cuadrículas están dando un límite inferior débil. ¿Puedes demostrar que la única forma de ir abajo$O(\sqrt{n\log n})$ es tener "una información" como la de la pregunta? Esto implicaría una forma de probar un límite inferior para las cuadrículas. ¿Tiene algún sentido?$\sqrt{n\log n}$

No estoy tan familiarizado con este documento, pero trataré de dar una respuesta aproximada a cada una de sus preguntas después de una lectura superficial.

1. El algoritmo de Grover puede verse con esta noción de tiempo de golpe. Debe decidir cuándo medir el sistema, y ​​aunque T es constante para todos los resultados, aún es importante calcularlo. Aquí T ciertamente no es$O(\mbox{dist}(v_0, v^f))$ (que en este caso es 1), sino más bien $O(\sqrt{n})$, entonces su suposición de que $T=O(\mbox{dist}(v_0, v^f))$ No es válido aquí.
2. Supongo que el autor está tomando un paquete completo para hacer la caminata aleatoria. Obviamente, esto requiere un unitario algo más complicado, pero realmente no veo un problema. Alternativamente, Burgarth y Bose tienen un esquema muy bueno para codificar información en gráficos idénticos que también funcionaría si simplemente reemplaza sus cadenas 1d con la red de elección ( quant-ph / 0406112 ).
3. Bueno, no necesitas esta noción de golpear el tiempo. Los hipercubos tienen una transferencia de estado perfecta (ver, por ejemplo, quant-ph / 0309131 y quant-ph / 0411020 ), por lo que puede ver el transporte en un hipercubo como un interferómetro con el interferómetro Mach-Zender correspondiente al caso 2d.

ACTUALIZACIÓN: (Para responder la pregunta actualizada sobre caminatas aleatorias en una cuadrícula u otra red)

Un enfoque para el problema de medición que resalta con el problema de búsqueda espacial es simplemente hacer una medición en cada paso de tiempo de manera que devuelva 1 si el vértice en el que se encuentra el caminante (digamos $v_t$) es igual a $v^f$y el paso de tiempo actual t es el tiempo de golpe para ese vértice. Esto debería evitar el problema de colapsar la función de onda, ya que la medición solo se realiza para cada vértice una vez que se alcanza el tiempo de golpeo, y solo registra colapsos en una ubicación si esa ubicación es el resultado correcto.

Con respecto a la pregunta 1, conocer la distancia entre el vértice objetivo desconocido y algún vértice de origen conocido en el hipercubo puede ayudar al proceso de búsqueda. Sin embargo, el valor de la distancia en sí determina qué tan útil es esta información.

Los algoritmos típicos de caminata cuántica suelen ser variaciones / aproximaciones de la búsqueda de Grover: implican una rotación aproximada del vector de estado en un subespacio 2-d del espacio total de Hilbert.

Puede usar estos algoritmos para preparar de manera eficiente una superposición aproximadamente uniforme de todos los vértices a una distancia dada del origen. Luego puede buscar su vértice objetivo dentro de esta superposición utilizando la búsqueda cuántica o clásica (Monte Carlo): para la búsqueda clásica, simplemente prepare la superposición y mida en la base del vértice y repita hasta encontrar el objetivo. Para la búsqueda cuántica, el procedimiento de preparación de superposición (y su inverso) se convierte en una subrutina que reemplaza la transformación de Hadamard en la iteración de Grover.

La utilidad de esto depende del valor de la distancia: en el $n$hipercubo tridimensional el número de vértices a distancia $d$ de un origen dado es el coeficiente binomial $\binom{n}{d}$. De ahí la mayoría de los vértices ($\approx \frac{2^n}{\sqrt{\frac{\pi}{2}n}}$) están en $\approx n/2$ distancia: si bien puede preparar eficientemente la superposición de estos vértices, la búsqueda del objetivo dentro de él todavía requiere un tiempo exponencial.