In this tutorial, we introduce the Bernstein-Vazirani algorithm, which is one of the earliest algorithms demonstrating the power of quantum computing. Despite its simplicity, it is often used and is the inspiration for many other quantum algorithms even today; it is the basis of the power of the short-depth quantum circuits, as in Bravyi et al. that uses its non-oracular version, or in Linke et al. that uses it to test the performance of the quantum processors (see also the talk by Ken Brown at the ThinkQ 2017 conference). Here, we show the implementation of the Bernstein-Vazirani algorithm without using entanglement based on Du et al. on Qiskit and test it on IBM Q systems.
The latest version of this notebook is available on https://github.com/qiskit/qiskit-tutorial.
Rudy Raymond
The Bernstein-Vazirani algorithm deals with finding a hidden integer $a \in \{0,1\}^n$ from an oracle $f_a$ that returns a bit $a \cdot x \equiv \sum_i a_i x_i \mod 2$ upon receiving an input $x \in \{0,1\}^n$. A classical oracle returns $f_a(x) = a \cdot x \mod 2$ given an input $x$. Meanwhile, a quantum oracle behaves similarly but can be queried with superposition of input $x$'s.
Classically, the hidden integer $a$ can be revealed by querying the oracle with $x = 1, 2, \ldots, 2^i, \ldots, 2^{n-1}$, where each query reveals the $i$-th bit of $a$ (or, $a_i$). For example, with $x=1$ one can obtain the least significant bit of $a$, and so on. This turns out to be an optimal strategy; any classical algorithm that finds the hidden integer with high probability must query the oracle $\Omega(n)$ times. However, given a corresponding quantum oracle, the hidden integer can be found with only $1$ query using the Bernstein-Vazirani algorithm.
The Bernstein-Vazirani algorithm to find the hidden integer is very simple: start from a $|0\rangle$ state, apply Hadamard gates, query the oracle, apply Hadamard gates, and measure. The correctness of the algorithm is best explained by looking at the transformation of a quantum register $|a \rangle$ by $n$ Hadamard gates, each applied to the qubit of the register. It can be shown that
$$ |a\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x\in \{0,1\}^n} (-1)^{a\cdot x}|x\rangle. $$In particular, when we start with a quantum register $|0\rangle$ and apply $n$ Hadamard gates to it, we have the familiar quantum superposition as below
$$ |0\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x\in \{0,1\}^n} |x\rangle, $$which is slightly different from the Hadamard transform of the reqister $|a \rangle$ by the phase $(-1)^{a\cdot x}$.
Now, the quantum oracle $f_a$ returns $1$ on input $x$ such that $a \cdot x \equiv 1 \mod 2$, and returns $0$ otherwise. This means we have the following transformation:
$$ |x \rangle \left(|0\rangle - |1\rangle \right) \xrightarrow{f_a} | x \rangle \left(|0 \oplus f_a(x) \rangle - |1 \oplus f_a(x) \rangle \right) = (-1)^{a\cdot x} |x \rangle \left(|0\rangle - |1\rangle \right). $$Notice that the second register $|0\rangle - |1\rangle$ in the above does not change and can be omitted for simplicity. In short, the oracle can be used to create $(-1)^{a\cdot x}|x\rangle$ from the input $|x \rangle$. In this tutorial, we follow Du et al. to generate a circuit for a quantum oracle without the need of an ancilla qubit (often used in the standard quantum oracle).
The algorithm to reveal the hidden integer follows naturally by querying the quantum oracle $f_a$ with the quantum superposition obtained from the Hadamard transformation of $|0\rangle$. Namely,
$$ |0\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x\in \{0,1\}^n} |x\rangle \xrightarrow{f_a} \frac{1}{\sqrt{2^n}} \sum_{x\in \{0,1\}^n} (-1)^{a\cdot x}|x\rangle. $$Because the inverse of the $n$ Hadamard gates is again the $n$ Hadamard gates, we can obtain $a$ by
$$ \frac{1}{\sqrt{2^n}} \sum_{x\in \{0,1\}^n} (-1)^{a\cdot x}|x\rangle \xrightarrow{H^{\otimes n}} |a\rangle. $$Here, we describe how to build the oracle used in the Bernstein-Vazirani algorithm. The oracle is also referred to as the inner-product oracle (while the oracle of the Grover search is known as the Equivalence, or EQ, oracle). Notice that it transforms $|x\rangle$ into $(-1)^{a\cdot x} |x\rangle$. Clearly, we can observe that
$$ (-1)^{a\cdot x} = (-1)^{a_1 x_1} \ldots (-1)^{a_ix_i} \ldots (-1)^{a_nx_n} = \prod_{i: a_i = 1} (-1)^{x_i}. $$Therefore, the inner-product oracle can be realized by the following unitary transformation, which is decomposable as single-qubit unitaries:
$$ O_{f_a} = O^1 \otimes O^2 \otimes \ldots \otimes O^i \otimes \ldots \otimes O^n, $$where $O^i = (1 - a_i)I + a_i Z$, where $Z$ is the Pauli $Z$ matrix and $I$ is the identity matrix for $a_i \in \{0,1\}$.
Notice that we start from a separable quantum state $|0\rangle$ and apply a series of transformations that are separable (i.e., can be described by unitaries acting on a single qubit): Hadamard gates to each qubit, followed by the call to the decomposable quantum oracle as Du et al., and another Hadamard gate. Hence, there is no entanglement created during the computation. This is in contrast with the circuit at Linke et al. that used CNOT gates to realize the oracle and an ancilla qubit to store the answer of the oracle.
In [1]:
#initialization
import matplotlib.pyplot as plt
%matplotlib inline
import numpy as np
# importing Qiskit
from qiskit import IBMQ, Aer
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister
from qiskit import available_backends, execute, register, get_backend
from qiskit.wrapper.jupyter import *
# import basic plot tools
from qiskit.tools.visualization import circuit_drawer, plot_histogram
In [2]:
# Load our saved IBMQ accounts.
IBMQ.load_accounts()
We first set the number of qubits used in the experiment, and the hidden integer $a$ to be found by the Bernstein-Vazirani algorithm. The hidden integer $a$ determines the circuit for the quantum oracle.
In [11]:
nQubits = 14 # number of physical qubits
a = 101 # the hidden integer whose bitstring is 1100101
# make sure that a can be represented with nQubits
a = a % 2**(nQubits)
We then use Qiskit to program the Bernstein-Vazirani algorithm.
In [12]:
# Creating registers
# qubits for querying the oracle and finding the hidden integer
qr = QuantumRegister(nQubits)
# for recording the measurement on qr
cr = ClassicalRegister(nQubits)
circuitName = "BernsteinVazirani"
bvCircuit = QuantumCircuit(qr, cr)
# Apply Hadamard gates before querying the oracle
for i in range(nQubits):
bvCircuit.h(qr[i])
# Apply barrier so that it is not optimized by the compiler
bvCircuit.barrier()
# Apply the inner-product oracle
for i in range(nQubits):
if (a & (1 << i)):
bvCircuit.z(qr[i])
else:
bvCircuit.iden(qr[i])
# Apply barrier
bvCircuit.barrier()
#Apply Hadamard gates after querying the oracle
for i in range(nQubits):
bvCircuit.h(qr[i])
# Measurement
bvCircuit.barrier(qr)
bvCircuit.measure(qr, cr)
Out[12]:
In [13]:
circuit_drawer(bvCircuit)
Out[13]:
In [14]:
# use local simulator
backend = Aer.get_backend('qasm_simulator')
shots = 1000
results = execute(bvCircuit, backend=backend, shots=shots).result()
answer = results.get_counts()
plot_histogram(answer)
In [15]:
%%qiskit_job_status
backend = IBMQ.get_backend('ibmq_16_melbourne')
shots = 1000
job_exp = execute(bvCircuit, backend=backend, shots=shots)
In [16]:
results = job_exp.result()
answer = results.get_counts(bvCircuit)
threshold = int(0.03 * shots) #the threshold of plotting significant measurements
filteredAnswer = {k: v for k,v in answer.items() if v >= threshold} #filter the answer for better view of plots
removedCounts = np.sum([ v for k,v in answer.items() if v < threshold ]) #number of counts removed
filteredAnswer['other_bitstring'] = removedCounts #the removed counts is assigned to a new index
plot_histogram(filteredAnswer)
print(filteredAnswer)
We indeed see that the outcome is the binary representation of the hidden integer $a$ with high probability.