Bernstein-Vazirani Algorithm using Qiskit
Bernstein-Vazirani Algorithm can be seen as an extension to the Deutsch-Josza Algorithm where a black box is given and we need to determine weather the function is balanced or constant,Whereas in Bernstein Vazirani algorithm we need to determine the function (f) of a a black box which takes input as string of bits(x) and returns either 0 or 1. Function f can be represented as :
f ({ x0,x1,x2,…})→0 or 1 where xn is 0 or 1
Here the function is guaranteed to return the bitwise product of the input with some string s .
For a given input x
f(x) = s . x (mod 2) , we have to find s .
This problem can be easily solved by Quantum computer with just one query to th function f(x) or black box . Algorithm for implementation on Qiskit to find s are below :
1. Initialize the quantum register |0> for n series of x and |-> for output bit
2. Apply Hadamard gates to input register .
3. Query the function
4. Apply Hadamard gate to the input qubits ,
5. Measure
Let’s do Qiskit implementation :
- Importing qiskit library :
import matplotlib.pyplot as plt
import numpy as np
from qiskit import IBMQ, BasicAer
from qiskit.providers.ibmq import least_busy
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, execute
from qiskit.visualization import plot_histogram2. Choose number of qubits for operation , also we need one extra ancilla qubit .
n = 3 # Qubits for s
s = '101' # the binary string3. Create the quantum circuit. Apply hadamard gates on all n qubit except the ancilla bit . We need to set ancilla bit to |-> by applying hadamard gate and pauli Z gate .
Remember to reverse the s (binary string) as order in qubit in qiskit will be represented as q0q1q2 while out binary string is q2q1q0.
Apply inner product oracle by applying identity for Qubit in 0 state and CNOT for qubit in state 1. Apply Hadamard opeations again on all qubits except ancilla bit.
4. Do the measurement.
bv_circuit = QuantumCircuit(n+1, n)# put ancilla in state |->
bv_circuit.h(n)
bv_circuit.z(n)# Apply Hadamard gates before querying the oracle
for i in range(n):
bv_circuit.h(i)# Apply barrier
bv_circuit.barrier()# Apply the inner-product oracle
s = s[::-1] # reverse s to fit qiskit's qubit orderingfor q in range(n):
if s[q] == '0':
bv_circuit.i(q)
else:
bv_circuit.cx(q, n)# Apply barrierbv_circuit.barrier()#Apply Hadamard gates after querying the oraclefor i in range(n):
bv_circuit.h(i)# Measurementfor i in range(n):
bv_circuit.measure(i, i)
bv_circuit.draw('mpl')
Simulation :
Using Qasm simulator to obtain ideal output (error free result)for 1024 shots . Visualize it on histogram.
# use local simulatorbackend = BasicAer.get_backend('qasm_simulator')
results = execute(bv_circuit, backend=backend, shots=1024).result()
answer = results.get_counts()
plot_histogram(answer)
Running on Real IBM Quantum Computer :
IBMQ.save_account('6540e36d3f9476d104af16f52ef0ca6eb678b9936b7e43c48570ac609a034a052e86ddf374a7ee046d4f108244b3a71916c057585b15bcd3923f8560c6a24a13')
IBMQ.load_account()
provider = IBMQ.get_provider(hub='ibm-q')
provider.backends()
backend = least_busy(provider.backends(filters=lambda x: x.configuration().n_qubits <= 5 and
x.configuration().n_qubits >= 2 and
not x.configuration().simulator and x.status().operational==True))
#print("least busy backend: ", backend)#from qiskit.tools.monitor import job_monitor
job = execute(bv_circuit, backend=backend, shots=1024)
#job_monitor(job, interval = 2)# Get the results from the computationresults = job.result()
answer = results.get_counts()
plot_histogram(answer)
We can see there are results apart from our ideal result ,this is due to errors present in the gates that we applied.
Git Hub link:
Thanks for reading. Please reach out to me at vbhvtiwari32@gmail.com for any queries.
