Algoritmo de Grover: ¿un ejemplo de la vida real?

13

Estoy bastante confundido acerca de cómo se podría usar el algoritmo de Grover en la práctica y me gustaría pedir ayuda sobre la aclaración a través de un ejemplo.

Supongamos una base de datos de elementos que contiene colores Rojo, Naranja, Amarillo, Verde, Cian, Azul, Indigo y Violeta, y no necesariamente en este orden. Mi objetivo es encontrar Red en la base de datos.N=8

La entrada para el algoritmo de Grover es qubits, donde los 3 qubits codifican los índices del conjunto de datos. Mi confusión viene aquí (podría estar confundido acerca de las premisas, así que más bien decir que la confusión ataca aquí) que, según tengo entendido, el oráculo realmente busca uno de los índices del conjunto de datos (representado por la superposición de los 3 qubits), y además, el oráculo está "codificado" para el índice que debe buscar.n=log2(N=8)=3

Mis preguntas son:

  • ¿Qué me equivoco aquí?
  • Si el oráculo realmente está buscando uno de los índices de la base de datos, eso significaría que ya sabemos qué índice estamos buscando, entonces, ¿por qué buscar?
  • Dadas las condiciones anteriores con los colores, ¿alguien podría señalarlo si es posible con Grover buscar Rojo en un conjunto de datos no estructurado?

Hay implementaciones para el algoritmo de Grover con un oráculo para buscando | 111>, por ejemplo (o vea una implementación R del mismo oráculo a continuación): /quantum//a/2205n=3Oracle para 111

Nuevamente, mi confusión es que, dado que no conozco la posición de elementos en un conjunto de datos, el algoritmo requiere que busque una cadena que codifique la posición de N elementos. ¿Cómo sé qué posición debo buscar cuando el conjunto de datos no está estructurado?Nnorte

Código R:

 #START
 a = TensorProd(TensorProd(Hadamard(I2),Hadamard(I2)),Hadamard(I2))
 # 1st CNOT
 a1= CNOT3_12(a)
 # 2nd composite
 # I x I x T1Gate
 b = TensorProd(TensorProd(I2,I2),T1Gate(I2)) 
 b1 = DotProduct(b,a1)
 c = CNOT3_02(b1)
 # 3rd composite
 # I x I x TGate
 d = TensorProd(TensorProd(I2,I2),TGate(I2))
 d1 = DotProduct(d,c)
 e = CNOT3_12(d1)
 # 4th composite
 # I x I x T1Gate
 f = TensorProd(TensorProd(I2,I2),T1Gate(I2))
 f1 = DotProduct(f,e)
 g = CNOT3_02(f1)
 #5th composite
 # I x T x T
 h = TensorProd(TensorProd(I2,TGate(I2)),TGate(I2))
 h1 = DotProduct(h,g)
 i = CNOT3_01(h1)
 #6th composite
 j = TensorProd(TensorProd(I2,T1Gate(I2)),I2)
 j1 = DotProduct(j,i)
 k = CNOT3_01(j1)
 #7th composite
 l = TensorProd(TensorProd(TGate(I2),I2),I2)
 l1 = DotProduct(l,k)
 #8th composite
 n = TensorProd(TensorProd(Hadamard(I2),Hadamard(I2)),Hadamard(I2))
 n1 = DotProduct(n,l1)
 n2 = TensorProd(TensorProd(PauliX(I2),PauliX(I2)),PauliX(I2))
 a = DotProduct(n2,n1)
 #repeat the same from 2st not gate
 a1= CNOT3_12(a)
 # 2nd composite
 # I x I x T1Gate
 b = TensorProd(TensorProd(I2,I2),T1Gate(I2))
 b1 = DotProduct(b,a1)
 c = CNOT3_02(b1)
 # 3rd composite
 # I x I x TGate
 d = TensorProd(TensorProd(I2,I2),TGate(I2))
 d1 = DotProduct(d,c)
 e = CNOT3_12(d1)
 # 4th composite
 # I x I x T1Gate
 f = TensorProd(TensorProd(I2,I2),T1Gate(I2))
 f1 = DotProduct(f,e)
 g = CNOT3_02(f1)
 #5th composite
 # I x T x T
 h = TensorProd(TensorProd(I2,TGate(I2)),TGate(I2))
 h1 = DotProduct(h,g)
 i = CNOT3_01(h1)
 #6th composite
 j = TensorProd(TensorProd(I2,T1Gate(I2)),I2)
 j1 = DotProduct(j,i)
 k = CNOT3_01(j1)
 #7th composite
 l = TensorProd(TensorProd(TGate(I2),I2),I2)
 l1 = DotProduct(l,k)
 #8th composite
 n = TensorProd(TensorProd(PauliX(I2),PauliX(I2)),PauliX(I2))
 n1 = DotProduct(n,l1)
 n2 = TensorProd(TensorProd(Hadamard(I2),Hadamard(I2)),Hadamard(I2))
 n3 = DotProduct(n2,n1)
 result=measurement(n3)
 plotMeasurement(result)

Imagen2

01000001
fuente
3
Posible duplicado del algoritmo
DaftWullie
también relacionado con: quantumcomputing.stackexchange.com/q/175/55
glS

Respuestas:

5

|xaddress|0value|xaddress|load(x)0value=|xaddress|load(x)value.

Haddressn|0address|0value=12n/2x=02n1|xaddress|0value
apply load12n/2x=02n1|xaddress|load(x)value
O(N)x
|xaddress|load(x)value.

Quizás el principal problema que tiene es comprender la base de datos, no el algoritmo de Grover. Puede ver una explicación más detallada en el capítulo 6.5 Nielsen & Chuang para esto.

También creo que la aplicación más útil del algoritmo de Grover no es la aplicación de la base de datos, sino sus generalizaciones como amplificación de amplitud (consulte https://arxiv.org/abs/quant-ph/0005055 ) en cualquier algoritmo cuántico.

Alex Go
fuente
k|k|skksk=+1sk.
glS
4

Esto ya se discutió parcialmente en esta pregunta relacionada , pero trataré aquí para abordar más específicamente algunos de los problemas que plantea.

En términos generales, el algoritmo de Grover se basa en el supuesto de que uno puede realizar una operación de consulta del formulario

El |yo(-1)F(Xyo)El |yo,
dónde yo es el índice en la base de datos y Xyo cualquier información que la base de datos adjunte a yo.

Tu puedes pensar en F(Xyo)como " hacer una pregunta sobreXyo". Por ejemplo," esXyoun numero primo? "o" haceXyo tener propiedad PAG?", dónde PAG podría significar "ser rojo".

Es importante observar que F podría estar haciendo una pregunta que no caracteriza completamente Xyo. Esto significa que después de ejecutar el algoritmo y recuperaryo, y por lo tanto Xyo con él, también obtengo conocimiento que no se usó para construir el oráculo.

Sin embargo, en muchas implementaciones de prueba de principio del algoritmo de Grover, como la que muestra, este no es el caso. De hecho, en estas demostraciones la pregunta que se hace es "trivial", en el sentido de queXyo=yo, y la pregunta es de la forma " esXyoigual a 3 ?

En tal caso, el algoritmo no es particularmente útil ya que la respuesta tiene que estar codificada en el oráculo, pero este no tiene que ser el caso en general.

glS
fuente
¡Gracias por su respuesta! ¿Quizás sería posible proporcionar un ejemplo de la vida real donde el Grover's sea "útil" aplicado en algunos datos reales dado el oráculo presentado? Por ejemplo, ¿cómo funcionaría con una base de datos de 8 elementos con primos y no primos?
01000001
1
@01000001 I believe this answer on a related question on cstheory.SE could qualify. It is a nice example of Grover being used for a nontrivial f. In his case, f codifies whether a given boolean formula is satisfied by the input. The output of the algorithm is thus an x satisfying a boolean formula
glS