Tiempos de golpe cuántico de un disparo

13

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| 2p donde | Ψ 0 es el estado inicial, | Ψ f es el estado de destino, y p > 0(T,p)(|Ψ0,|Ψf)|Ψf|UT|Ψ0|2p|Ψ0|Ψfp>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 ).Tp>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 | Ψ fn2n|Ψ0=|0000 , los espectáculos de papel que T = O ( n ) con una probabilidad de error limitado, es decir, p 1 como n|Ψf=|1111T=O(n)p1nse 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.|1111Ω(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 tGv0vfT=O(dist(v0,vf))p1/2Tes 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=(nv0=(0,0)dondea=0,,vf=(n1,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,,n1

texto alternativo

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(v0,vf)=Ω(n)es un límite inferior para la búsqueda, y para las cuadrículas el mejor límite superior esO(Ω(norte). 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 abajoO(norteIniciar sesiónnorte) 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?norteIniciar sesiónnorte

Marcos Villagra
fuente

Respuestas:

10

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 esO(dist(v0 0,vF)) (que en este caso es 1), sino más bien O(norte), entonces su suposición de que T=O(dist(v0 0,vF)) 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 vt) es igual a vFy 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.

Joe Fitzsimons
fuente
Joe, gracias por tu respuesta. Aproximadamente 1, el problema con la medición es que necesita saber qué tan lejos está el objetivo de su punto de partida para poder usarlo. Por ejemplo, para una cuadrícula d-dimensional connortenodos, digamos que comienzas en el centro y el objetivo está en algún lugar en el borde de la cuadrícula y eso lo sabemos. Entonces la distancia desde el centro esΩ(norte1/ /re), y ese también es su tiempo de bateo si la problabilidad de bateo ha limitado el error. ¿Podemos suponer que podemos tener ese tipo de conocimiento? Porque para Grover's, estás haciendo una búsqueda a ciegas completa, y eso parece más real
Marcos Villagra
Claro, pero no necesariamente tiene que considerar las cuadrículas regulares. El algoritmo de Grover correspondería a un nodo central directamente conectado a todos los demás nodos para que la distancia siempre sea fija. Además, hay otro problema, ya que el tiempo de acceso no se definirá para todos los nodos. En algunos casos, la probabilidad simplemente nunca alcanzará el valor umbral. Podría estar equivocado, pero creo que para una cadena lineal, la superposición máxima en cada sitio cae como algo así comov0 0-vF-12para cadenas acopladas XXZ.
Joe Fitzsimons
La decadencia de superposición depende en gran medida de la operación con monedas de su caminata. Si elige el operador de difusión de Grover, cuando golpea el nodo de destino, la superposición es alta y algunos pasos después disminuye a medida queO(t-1)para líneas y gráficos de cuadrícula.
Marcos Villagra
Sí exactamente. La cifra que di es solo para un sistema específico. Simplemente quería destacar que no siempre es posible lograr una probabilidad de golpe constante independientemente del número de vértices.
Joe Fitzsimons
Pero volviendo a la pregunta sobre búsqueda, di el ejemplo de las cuadrículas porque estaba pensando en "búsqueda espacial en cuadrículas" (quant-ph / 0303041). Pero aún así, me parece que para hacer una medición para ver si alcanzas el objetivo, debes hacerlo en el subespacio que contiene el objetivo. Como lo imagino, necesitas un dispositivo en ese subespacio que compruebe constantemente si la caminata llegó o no. Mi problema es que parece que siempre necesitas saber más o menos dónde está tu objetivo. (continuar)
Marcos Villagra
0

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 nortehipercubo tridimensional el número de vértices a distancia re de un origen dado es el coeficiente binomial (nortere). De ahí la mayoría de los vértices (2norteπ2norte) están en norte/ /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.

Antonio Valerio Miceli-Barone
fuente