Bernstein-Vazirani Algorithm
The Bernstein–Vazirani algorithm was invented by Ethan Bernstein and Umesh Vazirani in 1997. The Bernstein–Vazirani problem is defined as follows:
Problem Definition
Given a function \(f∶\left\{0,1\right\}^n\mapsto\left\{0,1\right\}\), with the oracle function \(f(x)=a\cdot x\), where a is a constant vector of \(\left\{ 0,1 \right\}^n\), and \(a\cdot x\) is a scalar product of a and`x`. The goal of the oracle is to find the hidden bit string a.
A classical solution to this problem requires n steps. We can retrieve the hidden string \(a(a_0 a_1 a_2\ldots a_{n-1} )\) by querying the oracle with a value of x, such that each query returns one of the bits in the hidden string. For example:
After querying all the bits, we can stitch the results and obtain the hidden string \((a_0 a_1 a_2 a_3)\). There are a few ways to solve this problem on a quantum computer, and we can get the answer in one step. The block diagram [16] for the solution to the Bernstein-Vazirani oracle is given below.
We can implement the oracle function as a set of CNOT gates, with the ancilla qubit as the target and the data register qubits corresponding to the bit value of the hidden string a as the control qubits. The following figure [17] illustrates this for a hidden string \(10 =1010b\).
For a detailed step-by-step math of this algorithm, see [11]. The source code for this oracle is outlined in the following sections.
Note
Be sure to use your API token and your account name.
Step 1. Import the required modules and obtain the backend
import QuantumRingsLib
from QuantumRingsLib import QuantumRegister, AncillaRegister, ClassicalRegister, QuantumCircuit
from QuantumRingsLib import QuantumRingsProvider
from QuantumRingsLib import job_monitor
from QuantumRingsLib import JobStatus
from matplotlib import pyplot as plt
import numpy as np
provider = QuantumRingsProvider(token =<YOUR_TOKEN_HERE>, name=<YOUR_ACCOUNT_NAME_HERE>)
backend = provider.get_backend("scarlet_quantum_rings")
shots = 100
provider.active_account()
Step 2. Define the core methods
def bv_func (qc, hiddenstring):
# set the ancilla qubit to state |1>
qc.x(qc.num_qubits-1)
# Set all qubits to a superposition state.
for i in range (qc.num_qubits):
qc.h(i)
qc.barrier()
# implement the hidden string - the oracle function
for i in range (qc.num_qubits - 1):
if ( 0!= ( hiddenstring & (1 << i))):
qc.cx(i, qc.num_qubits-1)
qc.barrier()
# Apply H gates one more time
for i in range (qc.num_qubits-1):
qc.h(i)
qc.barrier()
# finally measure
for i in range(qc.num_qubits - 1):
qc.measure(i,i)
return
def plot_histogram (counts, title=""):
"""
Plots the histogram of the counts
Args:
counts (dict):
The dictionary containing the counts of states
titles (str):
A title for the graph.
Returns:
None
"""
fig, ax = plt.subplots(figsize =(10, 7))
plt.xlabel("States")
plt.ylabel("Counts")
mylist = [key for key, val in counts.items() for _ in range(val)]
unique, inverse = np.unique(mylist, return_inverse=True)
bin_counts = np.bincount(inverse)
plt.bar(unique, bin_counts)
maxFreq = max(counts.values())
plt.ylim(ymax=np.ceil(maxFreq / 10) * 10 if maxFreq % 10 else maxFreq + 10)
# Show plot
plt.title(title)
plt.show()
return
Step 3. Execute the algorithm and plot the results
# obtain the hidden string from the user
hiddenstring = int(input("Enter the hidden string as a binary value: "), 2)
#determine the number of qubits required to represent the hidden string
numberofqubits = hiddenstring.bit_length()
print(hiddenstring, numberofqubits)
# add a qubit for the ancilla register
numberofqubits += 1
q = QuantumRegister(numberofqubits , 'q')
c = ClassicalRegister(numberofqubits , 'c')
qc = QuantumCircuit(q, c)
bv_func(qc, hiddenstring)
job = backend.run(qc, shots)
job_monitor(job)
result = job.result()
counts = result.get_counts()
plot_histogram(counts,"")
An example histogram is shown below for the hidden string \(10101010101\).
Bernstein_Vaziranai algorithm is good teaching example where we create a superposition of \(2^n\) states and use quantum interferance. For the vector \(|a\rangle\), the probability amplitudes interfered constructively. For all other values, the probability amplitudes interfered destructively, and their values are 0. The quantum version of this algorithm gets a linear speed up advantage.