mod03lec16 - Quantum Algorithms: Bernstein Vazirani Algorithm
Summary
TLDRThis lecture segment delves into the Bernstein-Vazirani algorithm, a quantum computing algorithm that demonstrates the superiority of quantum computers over classical ones in solving certain problems. The algorithm is designed to find a hidden bit string 'a' embedded in a function 'f', which is a dot product of 'a' and the input 'x'. While classical computers require exponential time to solve this with certainty, the quantum algorithm can do it with high probability in polynomial time. The lecture explains the classical and quantum solutions, emphasizing the need for 'n' queries in the classical approach and the efficient quantum method using Hadamard gates and an oracle. The implementation of the algorithm in Qiskit is also discussed, showcasing the practical application of quantum computing principles.
Takeaways
- π The Bernstein-Vazirani algorithm is a quantum algorithm that demonstrates quantum computers can solve certain problems with high probability in polynomial time, whereas classical computers cannot solve them with a probability greater than 1/2 in the same time.
- π§ The algorithm is a follow-up to Deutsch's algorithm, addressing a problem where quantum computers can solve with certainty in polynomial time, while classical computers require exponential time or settle for probabilistic solutions.
- π The problem statement involves an oracle function f that takes an n-bit input and outputs a single bit, either 0 or 1, with the guarantee that there exists a hidden bit string a such that f(x) = a Β· x mod 2.
- π― The goal of the Bernstein-Vazirani algorithm is to determine the hidden bit string a embedded in the function f using quantum computation.
- π Classical solutions require querying the oracle n times, one for each bit of a, which is both necessary and sufficient for classical algorithms to determine a.
- π The quantum solution involves applying Hadamard gates to all qubits, applying the oracle, and then applying Hadamard gates again before measurement, which allows the algorithm to determine a in a single query.
- π οΈ The implementation of the oracle in the algorithm requires an understanding of how to perform a quantum XOR operation, which is essential for the algorithm to function correctly.
- π The Bernstein-Vazirani algorithm highlights the potential of quantum computing to solve problems more efficiently than classical computing, showcasing an oracle separation between BQP and BPP complexity classes.
- π The algorithm's success relies on the ability to apply and invert the Hadamard transform, which is crucial for the quantum state to collapse to the desired solution upon measurement.
- π‘ The lecture concludes with a discussion of the algorithm's implementation in Qiskit, providing a practical example of how theoretical quantum algorithms can be realized in existing quantum computing frameworks.
Q & A
What is the Bernstein-Vazirani algorithm?
-The Bernstein-Vazirani algorithm is a quantum algorithm that demonstrates a problem which quantum computers can solve with high probability in polynomial time, while classical computers cannot solve with a probability greater than 1/2 using the same time.
How does the Bernstein-Vazirani algorithm differ from Deutsch's algorithm?
-While Deutsch's algorithm deals with determining if a function is constant or balanced, the Bernstein-Vazirani algorithm focuses on finding a hidden bit string 'a' embedded in a function f(x) = aΒ·x mod 2, where 'a' is a binary vector and 'x' is the input.
What is the classical solution to the problem addressed by the Bernstein-Vazirani algorithm?
-The classical solution involves querying the oracle with a sequence of inputs designed to isolate each bit of the hidden string 'a'. This requires n queries to the oracle to determine the n-bit string 'a'.
Why is the classical solution to the Bernstein-Vazirani problem limited to n queries?
-The classical solution is limited to n queries because it is an underdetermined system of equations with n variables and n-1 equations, making it impossible to find a unique solution for 'a' with fewer than n queries.
How does the quantum solution to the Bernstein-Vazirani problem work?
-The quantum solution uses a quantum circuit that applies Hadamard gates, the oracle, and another round of Hadamard gates to transform the initial state into the hidden bit string 'a'. This is achieved with fewer than n queries to the oracle.
What is the role of the oracle in the Bernstein-Vazirani algorithm?
-The oracle in the Bernstein-Vazirani algorithm is a black box that takes an input x and outputs x XOR f(x), where f(x) is the function that encodes the hidden bit string 'a' as f(x) = aΒ·x mod 2.
What is the significance of the Hadamard gate in the Bernstein-Vazirani algorithm?
-The Hadamard gate is used to create a superposition of all possible states, which allows the quantum algorithm to query the oracle in a superposed state, enabling the extraction of information about the hidden bit string 'a' with fewer queries than the classical method.
How does the Bernstein-Vazirani algorithm demonstrate the advantage of quantum computing over classical computing?
-The Bernstein-Vazirani algorithm shows that quantum computers can solve certain problems more efficiently than classical computers by leveraging quantum superposition and entanglement, which allows for the extraction of information with fewer queries to the oracle.
What is the output of the Bernstein-Vazirani algorithm?
-The output of the Bernstein-Vazirani algorithm is the hidden n-bit string 'a' that is embedded in the function f(x). This is achieved by measuring the quantum state after applying the quantum circuit.
How is the implementation of the oracle in the Bernstein-Vazirani algorithm described in the script?
-The implementation of the oracle in the Bernstein-Vazirani algorithm is described by showing how to apply a controlled-NOT gate for each bit of the input 'x' where the corresponding bit in the hidden string 'a' is 1. This effectively computes the dot product aΒ·x mod 2.
Outlines
π§ Bernstein Vazirani Algorithm Introduction
The paragraph introduces the Bernstein Vazirani algorithm as a follow-up to the Deutsch's algorithm. It discusses the problem that Bernstein and Vazirani aimed to solve, which is to demonstrate a problem that quantum computers can solve with high probability in polynomial time, while classical computers cannot solve with a probability greater than half in the same time. The classical computers would require exponential time to solve all inputs with certainty. The paragraph explains the motivation behind the algorithm, contrasting it with Deutsch's problem, and setting the stage for the problem statement that involves an oracle function f that outputs a dot x mod 2, where a is an n-bit string embedded in f. The goal is to find this hidden string a using quantum computation.
π Classical Solution to Bernstein Vazirani Problem
This paragraph delves into the classical approach to solving the Bernstein Vazirani problem. It explains that the classical solution involves querying the oracle function f with a sequence of inputs designed to isolate each bit of the hidden string a. The process requires n queries, one for each bit of a, to determine the entire string. The paragraph also discusses why fewer queries are not possible classically by presenting a system of equations that illustrates the underdetermined nature of the problem with n variables and only n-1 equations. It concludes with the assertion that n queries are both necessary and sufficient for the classical solution.
π Quantum Solution and Implementation
The final paragraph outlines the quantum solution to the Bernstein Vazirani problem, emphasizing the efficiency of quantum computation in solving it. It describes the quantum circuit that mirrors the one used in Deutsch's algorithm, involving the application of Hadamard gates, the oracle function, and another application of Hadamard gates. The paragraph explains that after these steps, measuring the quantum state will yield the hidden bit string a. It also touches on the implementation of the oracle function in quantum circuitry, detailing how to apply it based on the value of a. The summary concludes with a brief mention of the next topic, Grover's algorithm, to be discussed in the subsequent lecture.
Mindmap
Keywords
π‘Bernstein Vazirani Algorithm
π‘Quantum Computers
π‘Classical Computers
π‘Oracle
π‘Hadamard Gate
π‘Qubit
π‘Phase Kickback
π‘Measurement
π‘Deutsch's Algorithm
π‘Quantum Supremacy
Highlights
Bernstein-Vazirani algorithm is a quantum algorithm that follows up on Deutsch's algorithm.
Quantum computers can solve certain problems with certainty in polynomial time, unlike classical computers which may require exponential time.
Classical computers can solve the Deutsch's problem probabilistically in polynomial time.
The intuition behind probabilistic algorithms for balanced functions is that they can quickly identify patterns by querying random points.
Bernstein and Vazirani's problem is designed such that quantum computers can solve it with high probability in polynomial time, but classical computers cannot solve it with better than 50% probability in the same time.
The Bernstein-Vazirani problem involves finding a hidden bit string 'a' embedded in a function 'f' using an oracle.
The function 'f' is defined as a dot product between 'a' and the input 'x' modulo 2.
The classical solution to the Bernstein-Vazirani problem requires querying the oracle 'n' times to determine the 'n'-bit string 'a'.
It's proven that classical algorithms cannot do better than 'n' calls to the oracle to determine 'a'.
The quantum solution to the Bernstein-Vazirani problem involves applying Hadamard gates to all qubits, applying the oracle, and then applying the Hadamard gates again.
The quantum algorithm can determine the bit string 'a' with high probability in just one query to the oracle.
The implementation of the oracle in the quantum circuit requires XORing the last qubit with the function 'f(x)' which is the dot product of 'a' and 'x'.
The Bernstein-Vazirani algorithm demonstrates a clear separation between the complexity classes BQP and BPP.
The algorithm showcases the potential of quantum computers to solve certain problems much more efficiently than classical computers.
The quantum solution is intuitively explained through the use of quantum superposition and the oracle's ability to introduce phase shifts.
The implementation of the Bernstein-Vazirani algorithm in Qiskit is straightforward and leverages the built-in functions for Hadamard gates and oracles.
The lecture concludes with a discussion on the practical applications and the transition to Grover's algorithm in the next part.
Transcripts
[Music]
all right
let's get into the final portion of this
part of the lecture
where we'll discuss bernstein vazirani
algorithm
which you can think of it like a
follow-up to deutsches
so why did bernstein and vazirani what
did they start with
we saw that digesa
proves
that the quantum computers can solve a
particular problem with certainty 100
percent
confidence in polynomial time
but the classical computers
have to take exponential time if they
want to solve for all the inputs with
certainty so for some of the inputs with
certainty they need exponential but
probabilistic algorithms are still
practical
right so that in the real world we are
okay with allowing for wrong answers
with very small negligible probability
so if we allow for negligible
probability
the deutsche sub problem can be solved
even by classical computers in
polynomial time
so if you look at it earlier
we mentioned that the deutsch shows up
problem
uh to solve with percent certainty
classical algorithms need to query for
half of the inputs plus one points
so at least one point more than half
then
but if you're okay with allowing for
error with negligible probability
then the classical algorithm is also
quite simple
you just query the function on some
random set of points
okay
so if you do that
even for a balanced function
uh
the classical algorithm can solve uh
within polynomial time
so the intuition behind there is just
like simple for a balanced function we
know that half of the inputs output 0
and half of the inputs output 1.
so it's like 2 buckets bucket of 0s and
like
bucket of inputs which output 0 and
bucket of inputs are output 1.
so the intuitive argument here is that
if we choose inputs randomly if we query
the oracle on random set of points
the probability of inputs coming from
the same bucket like let's say bucket
zero or bucket 1 it reduces
exponentially as we keep querying so the
motivation for bernstein and what's
running is as follows
they came up with a problem which
quantum computers can solve with very
high probability
in some time
but any classical computer cannot solve
with
probability greater than half using the
same time as a one so
extending this this for those who know
this can be thought of as an oracle
separation between the complexity
classes b q b and b q b but again as i
said for deutsche so if you don't know
all right so this is the problem
statement that bernstein and wazirani
came up with
like we had for deutsche
we again
are given an oracle for a function f
which has which takes an n bits as input
and outputs one bin either zero over one
but the change here is
here the function is
of a type
a dot x
so earlier in deutsche we were given the
guarantee that the function is either a
constant function or a
balanced function
but here we are again given a guarantee
but of a different form
we are given a guarantee that there
exists a value a embedded in f
such that for any input x given to f the
output is a dot x mod 2
that is it's just a dot product between
a and x
okay
so the
the goal
for
bernstein vazirani is to
or the goal for this problem is to
output this
uh n which string a that's embedded in f
so given an oracle access to this f
which has a bet in it
the goal is to output this end bit
string here
okay
let's see what's the classical solution
to solve this problem
it's quite straightforward
uh the first solution that you can think
of
so the classical oracle we know that f
of x is a dot x mod 2.
so simply query the oracle with this
sequence of inputs so the first input of
the query is 1 for the all zeros
the second input is 0 1 followed by all
zeros and then third you'll have one at
the third position and then zero to
other positions so similarly you go on
okay so you just have to make end
queries
and for the first query we'll get the
first bit second query will give the
second bit
uh third query will to the third bit and
so on
so after end queries to the classical
article we can obtain
each of the n bits i mean n bits
together
just to give an example to again retrade
what i mentioned earlier let's just
assume that the a that's embedded in it
is one zero one one let's assume that n
is four and then
a is one zero one one so we query the
oracle with four inputs
or yeah to generalize it
we query first with one zero zero zero
zero one zero zero zero zero one zero
and zero zero zero one so one zero zero
zero dot this will give the first bit
one and then zero one zero zero will
give the second bit that's zero zero
zero one zero will be the third bit
that's one and zero zero zero one will
get the fourth bit it's one we can also
prove that we cannot do any better than
these n calls to the r for a classical
article okay so consider
that we have a function with the has an
a embedded in it
and then
just writing the previous what i said in
the previous layer set of equations
uh we have a 1 to a n and let x 1 2
x n minus 1 be the query okay so x 1 can
be written as x 1 1 till x 1 n
and then x n minus 1 can be written as x
n minus 1 1 till x n minus 1 n because
these are all n bit strings okay so
it's like
we have
this system of n minus 1 equations
with
n variables a 1 to a n and we know that
ah this is standard underdetermined
system of equations which means there
are less equations than
ah variables and we cannot find a unique
solution a for this system of equations
so
irrespective of what queries that we do
to this classical article
we have to use n queries to this article
to determine a
and as we saw in the previous slide it's
also an upper point so we know
an algorithm that after end queries will
give the output and here with this slide
with the intuition that we provided here
we also know that we need at least n
queries now let's look at the quantum
solution for it i am just displaying the
end to end quantum solution in a single
picture but here i think you guys
remember this diagram right
the quantum algorithm to solve
the bunching was irani problem it's same
as the algorithm that's same as the set
of steps that's used to solve the sub
problem
given that we have seen these individual
steps i'll just briefly go over these
steps in
somewhat quickly
so the first step it involves applying
hadamard to all the inputs
all right to step back a little bit the
step 0 is the input state which is same
as deutsche
we have uh
n qubits all 0s and n plus 1 qubit as 1
and then step 1
is applying the hadamard on all the
qubits
okay i'm just giving the final
expression that we derived
hadamard applied on a random state a
it's summation over all x minus 1 to the
a dot x x
okay so now if you apply hadamard on
this state all 0
it's just 1 over root 2 to the n
summation over all possible states x
so that's the output of the first step
and then
we apply the article we saw earlier
that
when we apply the oracle it's same as
having this phase that comes out minus 1
to the f x but we know that f of x is a
dot x so
x
when we apply
the state x and minus when you give it
to the article the output will be minus
1 to the a dot x
x and a minus so
again this is focusing on the first n
qubits
so this is
uh when we apply
this is the output of step one and when
we apply
uh when we pass it to the article with
the n plus one qubit
answer the qubit to be minus minus state
we will get this output where
last summation over x minus one to the a
dot xx
okay the third step is applying the
hadamard or to be more precise bernstein
was irani
we have to apply the inverse of hadamard
but inverse of haram had a hadamard
itself
if you look at it
this is the this is the state that we
have got at the end of step 2
i mean summation over x minus 1 to the a
dot x x
and
interestingly
if we apply the hadamard again
or the inverse of hadamard on this state
we'll get back
the value that we want
which is the value a
which is the bit string a that we want
right i mean we have to measure this
the cubic state that we get and then
once we measured it will get the bit
string a
okay so now let's look into the kisket
implementation of bird seamless running
all right so this is the circuit that we
have for diesel so i'll just make a copy
because it's the same circuit
right
so
just call this the pv circuit
all right
so
we know that
the input is 0 0 0 1
we know that the first step is hadamard
applied on all qubits
and then we have to apply the article
let's come back to it a bit later we
know that the third step is applying the
hadamard and finally doing the
measurement
right okay
let's come back to what the article is
okay
just think about it
what do we want to implement
we want to
the oracle
to take in
x
y
and output
x
and y x or f of x
so essentially
we want the oracle to output
the we want this final qubit to be xored
with f of x and we know that f of x is a
dot x
okay so what is the implement of
implementation of how a dot x how do we
implement aerodynamics
so
for how do we
implement aerobics for a particular a
the answer is quite simple
ah
if
a is 1 0 0
then
we just do this
because
what does this do
if we input a y it just outputs y
xr
x
1
okay
or okay here they call it q 0 q 1 q 2 so
which means let's say the inputs are x 0
x 1 x 2 so this just implements y xor x
1
ok which means a is 1 0 0 right it's 1
dot
x 0 plus
0 dot x 1 plus 0 dot x 2
and similarly if you want to implement 1
0 1
it is just this
because this is y x are
x 0
x or x 2
so this essentially says
it's y
x are
1 dot
x 0
plus 0 dot x
1
plus 0 dot oh sorry 1 dot x 2
okay let's see what the output is if it
matches
right so the output says it's 1 0 1
and 1 0 one so yeah as
before we ignored the ancillar qubit uh
the fourth or the last qubit
so that is zero with uh probability
fifty and or fifty percent and one with
probability half
so
right but the first three qubits are one
zero one
or i think we have to read it from here
it's one zero one
let's try to do this so if i put this
here
the output
should be
1 1 0
okay
yes
that's what we got 1 1 0
1 0
okay and if i delete this
it should be 0 1 0
right we got 0 and 0 and 0
so the implementation of oracle is
straightforward uh if
for whichever bits a is one
we have a c naught
with that particular bit as
control and the answer the last qubit
has started
okay
so that's about uh the implementation of
the bernstein vazirani algorithm in
kiskit
i hope you enjoyed this part of the
lecture
in the next part
dheeraj will talk about grover's
algorithm
Browse More Related Video
Quantum Computers, Explained With Quantum Physics
mod01lec09 - Quantum Gates and Circuits - Part 2
The Map of Quantum Computing - Quantum Computing Explained
mod02lec12 - Quantum Computing Concepts: Entanglement and Interferenceβ - Part 2
mod04lec24 - Fixing quantum errors with quantum tricks: A brief introduction to QEC - Part 2
Quantum Computing Expert Explains One Concept in 5 Levels of Difficulty | WIRED
5.0 / 5 (0 votes)