Skip to content

Bernstein-Vazirani Algorithm

View on GitHub

The Bernstein-Vazirani (BV) algorithm [1], named after Ethan Bernstein and Umesh Vazirani, is a basic quantum algorithm. It gives a linear speed-up with respect to its classical counterpart, in the oracle complexity setting.

The algorithm treats the following problem:

  • Input: A Boolean function \(f: \{0,1\}^n \rightarrow \{0,1\}\) defined as
\[f(x)\equiv (x\cdot a) \,\,\mod 2,\]

where the $ \cdot$ refers to a bitwise dot operation, and \(a\) is some binary string of length \(n\).

  • Output: Returns the secret string \(a\) with the minimal inquries of the function.

Comments: * This problem is a special case of the hidden-shift problem, where the goal is to find a secret string satisfing \(f(x)=f(x\oplus a)\), with \(\oplus\) indicating bitwise addition. * The problem can be considered as a restricted version of the Duetsch-Jozsa algorithm. In particular, the functional quantum circuit is identical for both problems.

Problem Hardness: Classically, the minimal inquiries of the function \(f\) for determining the secret string is \(n\): \(f\) is called with the strings

\[\begin{eqnarray} f(100\dots0) &=& a_0, \\ f(010\dots0) &=& a_1, \\ \vdots\\ f(00\dots01)&=& a_{n-1}, \end{eqnarray}\]

which reveals the secret string, one bit at a time. The BV algorithm finds the secret string using one function call (oracle inquiry); thus, providing a linear speed-up with respect to the classical solution.

Figure 1. The Bernstein-Vazirani algorithm comprises three quantum blocks. The main part of the algorithm is the implementation of the Bernstein-Vazirani predicate $f(x)\equiv (x\cdot a) \mod 2$.

How to Build the Algorithm with Classiq

The BV algorithm contains three function blocks: an oracle for the predicate \(f\), "sandwiched" between two Hadamard transforms. The resulting state corresponds to the secret string. The full mathematical derivation is given at the end of this notebook.

Implementing the BV Predicate

A simple quantum implementation of the binary function \(f(x)\) is by applying a series of controlled-X operations: starting with the state \(|f\rangle=|0\rangle\), we apply an X gate on it, controlled on the \(|x_i\rangle\) state, for all \(i\) such that \(a_i=1\):

\[|x_0\dots x_{n-1}\rangle |0\rangle_f \rightarrow \Pi_{i: a_i=1} {\rm CX}(x_i,f) |x_0\dots x_{n-1}\rangle |0\rangle_f = |x_0\dots x_{n-1}\rangle X^{a\cdot x}|0\rangle_f=|x_0\dots x_{n-1}\rangle |a\cdot x \left(\text{ mod } 2\right)\rangle_f.\]
from classiq import *
from classiq.qmod.symbolic import floor


@qfunc
def bv_predicate(a: CInt, x: QArray, res: QBit):
    repeat(
        x.len,
        lambda i: if_(
            floor(a / 2**i) % 2 == 1, lambda: CX(x[i], res), lambda: IDENTITY(res)
        ),
    )

Figure 1 shows an example for such implementation, for \(a=01101\) and \(n=5\).

Figure 1. The Bernstein Vazirani Predicate $f(x)$ for a secret string $a=01101$, on $n$ qubits. The quantum variable $x$ is stored on the 5 upper qubits and the resulting value of $f$ is on the lower-most qubit.

Implementing the BV Quantum Function

The quantum part of the BV algorithm is essentially identical to the Deutch-Jozsa one, see deutsch_jozsa function in Deutsch-Jozsa notebook. However, in contrast to the latter, the predicate function implementation is fixed, depending solely on the secret string \(a\). Hereafter we refer to the secret string as a secret integer, defined as an integer argument for the bv_function:

@qfunc
def bv_function(a: CInt, x: QArray):
    aux = QBit("aux")
    hadamard_transform(x)
    within_apply(
        lambda: (allocate(1, aux), X(aux), H(aux)), lambda: bv_predicate(a, x, aux)
    )
    hadamard_transform(x)

An Example on 5 Qbits

We construct a model for a specific example, setting the secret integer to \(a=13\) and \(n=5\).

We can essentially set the number of shots to 1. This is because that under the assumption of noiseless execution, the resulting state is just the secret integer (see last equation Eq. (1) below). In particular, the idea of using solely 1 shot was used to demonstrate algorithmic speedup in Ref. [2], where the authors considered a modified version of the BV algorithm in which the secret integer changes after every inquiry.

In our example, we take num_shots=1000 to highlight the fact that the resulting state is purely the secret string.

import numpy as np

from classiq.execution import ExecutionPreferences

SECRET_INT = 13
STRING_LENGTH = 5
NUM_SHOTS = 1000
assert (
    np.floor(np.log2(SECRET_INT) + 1) <= STRING_LENGTH
), "The STRING_LENGTH cannot be smaller than secret string length"


@qfunc
def main(x: Output[QNum]):
    allocate(STRING_LENGTH, x)
    bv_function(SECRET_INT, x)


qmod = create_model(
    main,
    execution_preferences=ExecutionPreferences(num_shots=NUM_SHOTS),
    out_file="bernstein_vazirani_example",
)
qprog = synthesize(qmod)

We can now visualize the circuit

show(qprog)

We execute and extract the result:

result = execute(qprog).result_value()

secret_integer_q = result.parsed_counts[0].state["x"]

print("The secret integer is:", secret_integer_q)
print(
    "The probability for measuring the secret integer is:",
    result.parsed_counts[0].shots / NUM_SHOTS,
)

assert int(secret_integer_q) == SECRET_INT

The secret integer is: 13.0
The probability for measuring the secret integer is: 1.0

Technical Notes

A brief summary of the linear algebra behind the Bernstein-Vazirani algorithm. The first Hadamard transformation generates an equal super-position over all the standard basis elements:

\[|0\rangle_n \xrightarrow[H^{\otimes n}]{} \frac{1}{2^{n/2}}\sum^{2^n-1}_{j=0}|j\rangle_n.\]

The oracle gets the boolean Bernstein-Vazirani predicate and adds an \(e^{\pi i}=-1\) phase to all states for which the function returns True:

\[\frac{1}{2^{n/2}}\sum^{2^n-1}_{j=0}|j\rangle_n \xrightarrow[\text{Oracle}(f(j))]{}\frac{1}{2^{n/2}}\sum^{2^n-1}_{j=0}(-1)^{a\cdot j}|j\rangle_n.\]

Finally, application of the Hadamard transform, which can be written as $H^{\otimes n}\equiv \frac{1}{2^{n/2}}\sum^{2^n-1}_{k,l=0}(-1)^{k\cdot l} |k\rangle \langle l| $, gives

\[\frac{1}{2^{n/2}}\sum^{2^n-1}_{j=0}(-1)^{a\cdot j}|j\rangle \xrightarrow[H^{\otimes n}]{} \sum^{2^n-1}_{k=0} \left(\frac{1}{2^{n}}\sum^{2^n-1}_{j=0}(-1)^{j\cdot \left(k\oplus a \right)} \right) |k\rangle.\]

The final expression represents a super-position over all basis states \(|k\rangle\); however, one can verify that the amplitude of the state \(|k\rangle=|a\rangle\) is simply 1, as \(a\oplus a =0\):

\[\begin{equation*} \left(\frac{1}{2^{n}}\sum^{2^n-1}_{j=0}1 \right) |a\rangle + \sum^{2^n-1}_{k\neq a} 0 |k\rangle = |a\rangle. \tag{1} \end{equation*}\]

Therefore, the final state is simply the secret string.

References

[1]: Bernstein–Vazirani (Wikipedia)

[2]: Pokharel B., and Daniel A. L. "Demonstration of algorithmic quantum speedup." Physical Review Letters 130, 210602 (2023)