Math
Una pregunta, hecha una sola vez
Una caja negra calcula f de n bits a un bit, y solo se le puede preguntar por entradas. Estar seguro de si f es constante o equilibrada cuesta clásicamente media tabla más una llamada. Hadamard sobre todo, UNA llamada con la respuesta como signo, Hadamard otra vez - y el resultado todo ceros lo decide. La tabla de verdad aquí se puede pulsar, así que la promesa puede romperse a mano: para cualquier tabla la respuesta sale con probabilidad (1 − 2k/N)². Y si la tabla resulta ser f(x) = s·x, esa única llamada devuelve la propia s.
Qué ocurre
Una caja negra calcula alguna función f de n bits a un bit. Se promete que es constante o equilibrada - la misma respuesta en todas partes, o una respuesta en exactamente la mitad de las entradas - y hay que decir cuál. Clásicamente no hay atajo: media tabla puede coincidir y la entrada siguiente estropearlo, así que la certeza cuesta N/2 + 1 llamadas. Nueve con dieciséis entradas, treinta y tres con sesenta y cuatro. Ahora la versión cuántica, y son tres líneas. Hadamard sobre cada cúbit, para preguntar las N entradas a la vez. Llama al oráculo, que no responde con un bit sino con un SIGNO: un menos en cada entrada donde f vale uno. Hadamard otra vez sobre cada cúbit. Mide. Si todos los cúbits leen cero, f era constante; cualquier otra cosa significa equilibrada, y todo costó una llamada. Este módulo pasa de demostración porque la tabla de arriba se pulsa. Rompe la promesa: da la vuelta a una casilla y f no es ni constante ni equilibrada, y el algoritmo no falla - se degrada en una cantidad que se puede escribir. Para CUALQUIER tabla, el resultado todo ceros tiene probabilidad (1 − 2k/N)², donde k cuenta los unos de la tabla. Constante es k = 0 y da uno. Equilibrada es k = N/2 y da exactamente cero. Una casilla volteada con dieciséis entradas da 4/256, una ejecución de cada sesenta y cuatro, y el panel dice el número antes de que cuentes. Eso vale una promesa dentro de un algoritmo, en cifras. Aquí se esconde algo más. Cuando la tabla es lineal - f(x) = s·x mod 2 para una cadena oculta s -, los mismos tres pasos no responden solo sí o no: el resultado ES s, con probabilidad uno, y cualquier otro tiene exactamente cero. Eso es Bernstein-Vazirani, y clásicamente cuesta n llamadas, una por bit. Pregunta una vez, lee la cadena entera. Bajo ambos hechos hay una fórmula: la amplitud del resultado y es la transformada de Walsh-Hadamard de (−1)^f, y el módulo la calcula por segunda vez directamente desde la tabla para poder contrastarlas.
Ecuaciones del módulo
Ecuaciones los tres pasos: H en cada cúbit; una llamada al oráculo como signo, |x> -> (−1)^f(x) |x>; H otra vez en cada cúbit amplitud del resultado y: (1/N) suma sobre x de (−1)^(f(x) + x·y) - la transformada de Walsh-Hadamard de (−1)^f P(todo ceros) = (1 − 2k/N)² donde k es el número de unos que tiene la tabla de verdad - EXACTAMENTE, para cualquier tabla constante (k = 0 o N): 1; equilibrada (k = N/2): 0; una celda de una tabla equilibrada invertida: 4/N² = 1/64 con N = 16 coste clásico para estar SEGURO: N/2 + 1 llamadas (3, 5, 9, 17, 33 para n = 2…6) frente a 1 tabla lineal f(x) = s·x mod 2 (Bernstein-Vazirani): el resultado ES s, probabilidad 1, cualquier otro resultado exactamente 0; coste clásico n llamadas, una por bit f = 1 en todas partes da exactamente las mismas probabilidades que f = 0 en todas partes - la diferencia es un signo global, y un signo global no se puede medir recuento, 2000 ejecuciones con n = 4: constante 2000 de 2000 en solo ceros; oculto s = 11, 2000 de 2000 en 11; equilibrada 0 en solo ceros; una celda invertida 30 (exacto 31.25)
