Algoritmo de Bernstein–Vazirani

El Algoritmo de Bernstein–Vazirani es un algoritmo cuántico desarrollado por Ethan Bernstein y Umesh Vazirani en 1992.​ En esencia, permite conocer un string binario, esto es, una cadena de caracteres compuesta de ceros y unos (por ejemplo: s = 0010110101001), que está contenido en una función. Más concretamente, se sabe que dicha función toma la forma , donde es otro string y la multiplicación se entiende como producto binario. Este algoritmo funciona de manera similar al de Deutsch-Jozsa, pero en vez de tratar de distinguir entre clases de funciones, busca el string que caracteriza a la función dada. Supongamos a modo de ejemplo que se participa en un juego consistente en encontrar un número oculto escrito en código binario. Con la versión clásica del algoritmo, la única manera de obtener la solución sería ir haciendo comprobaciones del número oculto bit a bit, lo cual requiere al menos N ejecuciones, siendo N el número de bits de s (esto se denota como O(N) en teoría de la complejidad computacional). En el caso del algoritmo de Bernstein-Vazirani, si se consigue codificar dicho número en el string s, una única ejecución del algoritmo bastaría para encontrar el número completo. La importancia de este algoritmo radica en la superioridad que muestra frente a su equivalente clásico, pudiéndose encontrar el string buscado tras una única ejecución.