Bernstein–Vazirani Algorithm

In this demonstration, we simulate the Bernstein-Vazirani algorithm to discover the secret parameter of a bitwise dot product.

Introduction #

Let $f(x)$ be a function which accepts an $n$-bit integer $0 \le x < 2^n$ and returns its bit-wise dot product with a secret integer $s$ in the same domain
$$ f(x) = x \cdot s \;\; \equiv \;\; \sum\limits_i^n \; \text{bit}_i(x) \; \text{bit}_i(s) \;\;\; \text{modulo 2} $$ We seek to find $s$ among the $2^n$ possible values by querying $f(x)$. Classically, we could query $f(2^j)$ for each integer $0 \le j < n$ to learn the corresponding $j$-th bit of $s$. This requires precisely $n$ total queries of $f(x)$.

But assume we have an $(n+1)$-qubit error-free quantum computer, and a unitary oracle $U_f$ which performs $$ U_f |x\rangle \; = \; (-1)^{f(x)} \; |x\rangle$$ Armed with these utilities, we can discover $s$ in a single invocation of $U_f$, using the Bernstein-Vazirani algorithm. The algorithm proceeds as follows.

1. Initialise the quantum register into the $|0\rangle$ state
2. Nominate the least significant qubit as the ancilla
3. Apply Pauli $X$ to the ancilla
4. Apply a Hadamard gate to every qubit (including the ancilla)
5. Apply the oracle $U_f$
6. Apply a Hadamard gate to every qubit (including the ancilla)
7. Measure the non-ancilla qubits, whose outcomes inform the bits of $s$

Implementation #

Let’s simulate it!

We first prepare the QuEST environment and our simulation parameters.

#include "QuEST.h"

int main() {
    
    // prepare the hardware-agnostic QuEST environment
    QuESTEnv env = createQuESTEnv();

    // choose the register size
    int numQubits = 15;

    // randomly choose the secret parameter
    srand(time(NULL));
    int secret = rand() % (int) pow(2, numQubits - 1);

    // prepare our register in the |0> state
    Qureg qureg = createQureg(numQubits, env);

    // search for s using BV's algorithm
    applyBernsteinVazirani(qureg, numQubits, secret);

    // tidy up
    destroyQureg(qureg, env);
    destroyQuESTEnv(env);
    return 0;
}

Algorithm #

The Bernstein-Vazirani algorithm is simply effected by $X$, $H$ and the oracle $U_f$.

void applyBernsteinVazirani(Qureg qureg, int numQubits, int secret) {

    // start in |0>
    initZeroState(qureg);

    // NOT the ancilla
    pauliX(qureg, 0);

    // H all qubits, including the ancilla
    for (int q=0; q<numQubits; q++)
        hadamard(qureg, q);

    applyOracle(qureg, numQubits, secret);

    for (int q=0; q<numQubits; q++)
        hadamard(qureg, q);

    // infer the output basis state
    measureResult(qureg, secret);
}

Oracle #

Our next task is to implement the oracle operator, which effects $$ U_f |x\rangle \; = \; (-1)^{f(x)} \; |x\rangle$$ This is simply done with $O(n)$ controlled-NOT gates.

void applyOracle(Qureg qureg, int numQubits, int secret) {

    int bits = secret;

    for (int q=1; q<numQubits; q++) {

        // extract the (q-1)-th bit of secret
        int bit = bits % 2;
        bits /= 2;
        
        // NOT the ancilla, controlling on the q-th qubit
        if (bit)
            controlledNot(qureg, q, 0);
    }
}

Measurement #

The above steps will leave the quantum register precisely in a single computational basis state, chiefly $|s\rangle|1\rangle$, with our ancilla on the right. An experimentalist would infer this state by performing a final measurement on every non-ancilla qubit to infer the bits of $s$.

void measureResult(...) {

    int secret = 0;

    for (int q=1; q<numQubits; q++) {

        int bit = measure(qureg, q);
        secret += bit * (int) pow(2, q-1);
    }
}

However, since $|s\rangle|1\rangle$ is a known computational basis state in our simulation, we can instead directly measure its probability in the final quantum state.

void measureResult(Qureg qureg, int secret) {

    // |ind> = |s>|1>
    int ind = 2*secret + 1;

    qreal prob = getProbAmp(qureg, ind);

    printf("success probability: %g \n", prob);
}

If we did everything right, the printed probability should be precisely $1$. The Bernstein-Vazirani algorithm works!

Run #

View the full code demonstration here.

Run the demonstration, from within the root QuEST directory, by running in terminal

cp examples/bernstein_vazirani_circuit.c .
make SOURCES=bernstein_vazirani_circuit
./demo