---
title: Bernstein–Vazirani Algorithm
description: "In this demonstration, we simulate the [Bernstein-Vazirani algorithm](https://epubs.siam.org/doi/10.1137/S0097539796300921) 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…"
url: "https://quest.qtechtheory.org/docs/bernstein-vazirani-algorithm/"
updated: "2021-10-24"
category: Examples
---

# Bernstein–Vazirani Algorithm

In this demonstration, we simulate the [Bernstein-Vazirani algorithm](https://epubs.siam.org/doi/10.1137/S0097539796300921) 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Oracle_machine) $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](https://quest-kit.github.io/QuEST/group__type.html#ga8ba2c3388dd64d9348c3b091852d36d4) and our simulation parameters.

```c
#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$.

```c
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](https://quest-kit.github.io/QuEST/group__unitary.html#gaa5a138473a4433c853c6e66e7aabc237) gates.

```c
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](https://quest-kit.github.io/QuEST/group__normgate.html#ga2a3794103125f1e3cfa103f8b1963656) on every non-ancilla qubit to infer the bits of $s$.

```c
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](https://quest-kit.github.io/QuEST/group__calc.html#ga4a14d22379d399760b0cfc5c8053589b) in the final quantum state.

```c
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](https://github.com/QuEST-Kit/QuEST/blob/develop/examples/bernstein_vazirani_circuit.c).

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

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

![Written by Tyson Jones](https://quest.qtechtheory.org/wp-content/uploads/2021/10/me-150x150.jpg)