Bernstein–Vazirani algorithm

The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1992. It's a restricted version of the Deutsch–Jozsa algorithm where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function. The Bernstein–Vazirani algorithm was designed to prove an oracle separation between complexity classes BQP and BPP.

Problem statement

Given an oracle that implements some function $f:\{0,1\}^{n}\rightarrow \{0,1\}$, It is promised that the function $f(x)$ is a dot product between $x$ and a secret string $s\in \{0,1\}^{n}$ modulo 2. $f(x)=x\cdot s=x_{1}s_{1}+x_{2}s_{2}+\cdots +x_{n}s_{n}$, find $s$.

Algorithm

Classically, the most efficient method to find the secret string is by evaluating the function $n$ times where $x=2^{i}$, $i\in \{0,1,...,n-1\}$

${\begin{aligned}f(1000\cdots 0_{n})&=s_{1}\\f(0100\cdots 0_{n})&=s_{2}\\f(0010\cdots 0_{n})&=s_{3}\\&\,\,\,\vdots \\f(0000\cdots 1)&=s_{n}\\\end{aligned}}$

In contrast to the classical solution which needs at least $n$ queries of the function to find $s$, only one query is needed using quantum computing. The quantum algorithm is as follows:

Apply a Hadamard transform to the $n$ qubit state $|0\rangle ^{\otimes n}$ to get

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n-1}}|x\rangle .$

Perform a controlled negation of every state in the superposition generated by the previous Hadamard transformation for which the oracle when applied to this state returns 1. This transforms the superposition into

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n-1}}(-1)^{f(x)}|x\rangle .$

Another Hadamard transform is applied to each qubit which makes it so that for qubits where $s_{i}=1$, its state is converted from $|-\rangle$ to $|1\rangle$ and for qubits where $s_{i}=0$, its state is converted from $|+\rangle$ to $|0\rangle$.

To obtain $s$, a measurement on the Standard basis ($\{|0\rangle ,|1\rangle \}$) is performed on the qubits. Graphically algorithm may be represented by the following diagram:

Scheme of the algorithm

Where $H^{\otimes n}$ is the Hadamard transform.

Implementation

An implementation of the Bernstein–Vazirani algorithm in Cirq.

"""Demonstrates the Bernstein–Vazirani algorithm.

The (non-recursive) Bernstein–Vazirani algorithm takes a black-box oracle
implementing a function f(a) = a·factors + bias (mod 2), where 'bias' is 0 or 1,
'a' and 'factors' are vectors with all elements equal to 0 or 1, and the
algorithm solves for 'factors' in a single query to the oracle.
=== EXAMPLE OUTPUT ===
Secret function:
f(a) = a·<0, 0, 1, 0, 0, 1, 1, 1> + 0 (mod 2)
Sampled results:
Counter({'00100111': 3})
Most common matches secret factors:
True
"""
import random
import cirq


def main(qubit_count=8):
    circuit_sample_count = 3

    # Choose qubits to use.
    input_qubits = [cirq.GridQubit(i, 0) for i in range(qubit_count)]
    output_qubit = cirq.GridQubit(qubit_count, 0)

    # Pick coefficients for the oracle and create a circuit to query it.
    secret_bias_bit = random.randint(0, 1)
    secret_factor_bits = [random.randint(0, 1) for _ in range(qubit_count)]
    oracle = make_oracle(
        input_qubits, output_qubit, secret_factor_bits, secret_bias_bit
    )
    print(
        "Secret function:\nf(a) = a·<{}> + {} (mod 2)".format(
            ", ".join(str(e) for e in secret_factor_bits), secret_bias_bit
        )
    )

    # Embed the oracle into a special quantum circuit querying it exactly once.
    circuit = make_bernstein_vazirani_circuit(input_qubits, output_qubit, oracle)

    # Sample from the circuit a couple times.
    simulator = cirq.Simulator()
    result = simulator.run(circuit, repetitions=circuit_sample_count)
    frequencies = result.histogram(key="result", fold_func=bitstring)
    print("Sampled results:\n{}".format(frequencies))

    # Check if we actually found the secret value.
    most_common_bitstring = frequencies.most_common(1)[0][0]
    print(
        "Most common matches secret factors:\n{}".format(
            most_common_bitstring == bitstring(secret_factor_bits)
        )
    )


def make_oracle(input_qubits, output_qubit, secret_factor_bits, secret_bias_bit):
    """Gates implementing the function f(a) = a·factors + bias (mod 2)."""

    if secret_bias_bit:
        yield cirq.X(output_qubit)

    for qubit, bit in zip(input_qubits, secret_factor_bits):
        if bit:
            yield cirq.CNOT(qubit, output_qubit)


def make_bernstein_vazirani_circuit(input_qubits, output_qubit, oracle):
    """Solves for factors in f(a) = a·factors + bias (mod 2) with one query."""

    c = cirq.Circuit()

    # Initialize qubits.
    c.append(
        [cirq.X(output_qubit), cirq.H(output_qubit), cirq.H.on_each(*input_qubits),]
    )

    # Query oracle.
    c.append(oracle)

    # Measure in X basis.
    c.append([cirq.H.on_each(*input_qubits), cirq.measure(*input_qubits, key="result")])

    return c


def bitstring(bits):
    return "".join(str(int(b)) for b in bits)


if __name__ == "__main__":
    main()

See also

• Hidden linear function problem