Bernstein-Vazirani algorithm

The Bernstein-Vazirani algorithm 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 [math]\displaystyle{ f:\{0,1\}^n\rightarrow \{0,1\} }[/math], It's promised that the function [math]\displaystyle{ f(x) }[/math] is a dot product between [math]\displaystyle{ x }[/math] and a secret string [math]\displaystyle{ s \subset {0,1}^n }[/math] modulo 2. [math]\displaystyle{ f(x) = x \cdot s = x_1s_1 + x_2s_2 + .. + x_ns_n }[/math], find [math]\displaystyle{ s }[/math].

Algorithm

Classically, the most efficient method to find the secret string is by evaluating the function on each input [math]\displaystyle{ x }[/math] of Hamming weight 1.

[math]\displaystyle{ \begin{align} f(1000\cdots0_n) = s_1 \\ f(0100\cdots0_n) = s_2 \\ f(0010\cdots0_n) = s_3 \\ \vdots \\ f(0000\cdots1) = s_n \\ \end{align} }[/math]

In contrast to the classical solution which needs at least [math]\displaystyle{ n }[/math] queries of the function to find [math]\displaystyle{ s }[/math], only one query is needed quantumly. The quantum algorithm is as follows:

Apply a Hadamard transform to the [math]\displaystyle{ n }[/math] qubit state [math]\displaystyle{ |0\rangle^{\otimes n} }[/math] to get

[math]\displaystyle{ \frac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^n} |x\rangle }[/math].

Applying the oracle to the state that was generated by the previous Hadamard transform turns the state into

[math]\displaystyle{ \frac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^n} (-1)^{f(x)} |x\rangle }[/math].

Another Hadamard transform is applied to each qubit which makes it so that for qubits where [math]\displaystyle{ s_i = 1 }[/math], its state is converted from [math]\displaystyle{ |-\rangle }[/math] to [math]\displaystyle{ |1\rangle }[/math] and for qubits where [math]\displaystyle{ s_i = 0 }[/math], its state is converted from [math]\displaystyle{ |+\rangle }[/math] to [math]\displaystyle{ |0\rangle }[/math].

To obtain [math]\displaystyle{ s }[/math], a measurement on the Standard basis ([math]\displaystyle{ \{|0\rangle, |1\rangle\} }[/math]) is performed on the qubits.

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