Quantum Algo: Bernstein-Vazirani Algorithm
How to find hidden information?
In the previous article Deutsch-Josza Algorithm, we understood Deutsch_Jozsa Algorithm is a simple straight forward generalization of the problem solved by the Deutsch algorithm extending to n-qubits.
In this article we discuss about the Bernstein-Vazirani Algorithm, which uses the same circuit with the same inputs and the same single data register measurement as Deutsch-Josza. However this time, instead of asking whether we see a “0” or a non-“0” at the output, we look at the full output to determine the secret string of the function using qiskit and cirq.
The setup:
The Bernstein–Vazirani algorithm once again considers the analysis of functions with n input bits and a single output bit, but the promise about the nature of the function is different. such that for all input bit strings x, there exists a secret string a, In this case it is promised as shown in below fig 1
where a is an unknown non-negative integer or n-bit integer, labeling the particular function and a · x is a bitwise dot product, calculated by multiplying corresponding bits of a and x and then adding the resulting bits modulo 2 as shown in below fig 2.
Example: Lets us consider x = 100 and secret string a = 101 Then,
x · a = (1)(1) + (0)(0) + (0)(1) (mod 2) = 1
The question is the following:
We are given a reversible circuit implementing an unknown function f, as shown in above fig 1. The problem here is to determine the value of “a” using the smallest number of queries to evaluate particular values of f (x).
what a classical algorithm would do?
Consider the following function f on two bits which obeys the Berstein-Vazirani property f(x) = a · x
Problem:
Given this table of values as shown in fig 3, determine what the secret string a to solve the Berstein-Vazirani problem?
from the fig 4 the code mentioned in orange box is consider as black box or Oracle. With this consideration, there are n classical queries send to Oracle.
In another simpler way not in the context of above mentioned example in fig 4, here, in the classical setting, we send one input string x into our “black box” oracle and learn the value f(x).
Why we do this with n queries?
Consider what happens when we send in the bit string x = 100 · · · 0. (That is, the bit string with one as its first bit and zeros elsewhere.) The query then sends us back f(x) = x · a = a1, where a1 is the first bit of a. Similarly for n inputs as shown in below fig 5
Thus, we have an algorithm for determining a explicitly with n queries.
Can we do better than this?
Classically, the answer is no, simply because each bit of a is independent. It takes at least n bits of information to specify s, and we learn exactly one bit from each query. Thus, n classical queries is a lower bound.
Bernstein-Vazirani Algorithm:
The algorithm uses n qubits and outputs each bit of the secret string s once measurements are made, thereby solving the BV problem in one query — a linear speedup! How does this work?
Same as Deutsch-Jozsa circuit. The circuit mentioned in the fig 6 prepares states that are needed for quantum parallelism and phase kick-back, then sending queries to Oracle and measuring after applying nth order Hadamard gate. Lets quickly revise derivation part
The |0⟩ going into the top register provides the quantum parallelism, which can be represent as shown in below fig 7
The |1⟩ going into the bottom register offers a phase kick-back that transfers information about f from the target output to the data output.
Apply Oracle Uf to the Data and target registers as shown in below fig 9
but we can plug in the exact formula for f(x) as shown in below fig 10
the data register can be expanded as shown in below fig 11
converging expanded form to the n tensor product as shown in below fig 12
We apply the final nth order Hadamard gate, which results the below expression as shown in fig 13
Here, we use the fact that H|+⟩ = |0⟩ and H|−⟩ = |1⟩. Thus, by measuring the jth qubit, we get the value aj exactly. By measuring all the qubits, we get the secret string a exactly, thereby solving the Bernstein-Vazirani problem with exactly one query in the quantum setting!
Conclusion: One thing to note is that, although we used only one query, we used O(n) gates. That is, we used a number of gates that scales linearly in the size of the input (which is the number of bits in the secret string a).
implement:
we will generate an Oracle(Uf) for function f(x) where f(x) = x · a, where x shall be the input bits and a shall be the secret string. After applying Oracle the result shall be |a⟩.
Let us consider a = 101100111, which is a 9 bit string. The expected output for Bernstein-Vazirani problem shall be |101100111⟩.
implement using IBM Qiskit:
As shown in the below qiskit 1, generates initial and measurement conditions for the B-V algorithm.
As shown in the below qiskit 2, generates Oracle for the given function.
As shown in the below qiskit 3, generates B-V circuit for the given function.
As shown in the below qiskit 4, initializes the circuit, number of qubits, generates the B-V circuit and visualize the generated circuit.
circuit generated for the given function as shown in below qiskit5.
As shown in the below qiskit 6, performs measurement using simulator.
After the circuit running over simulator, below is the histogram for the obtained result
The given secret bit-string a = 101100111 matches with the result obtained.
implement using Cirq:
In the following code blocks we walk through over implementation of Oracle for the mentioned function and B-V algorithm
As shown in the below cirq2, generates initial and measurement conditions for the B-V algorithm.
As shown in the below cirq 3, generates Oracle for the given function.
As shown in the below cirq4, generates B-V circuit for the given function.
as shown in cirq5 below, the function performs bits to bit-string
As shown in the below cirq6, initializes the circuit, number of qubits, generates the B-V circuit and visualize the generated circuit.
circuit generated for the given function as shown in below cirq7.
As shown in the below cirq8, performs measurement using simulator.
As shown in the above result the selected bit-string is equal to the circuit generated secret bit-string.
References: Qiskit Textbook, Cirq tutorials, young-physics, Nielsen & Chung textbook, StackExchange, Wikipedia, IEEE papers, open-source materials.
