mod03lec16 - Quantum Algorithms: Bernstein Vazirani Algorithm

Summary

This 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

00:00

🧠 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.

05:01

🔍 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.

10:01

🌌 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.

Keywords

💡Bernstein Vazirani Algorithm

The Bernstein Vazirani Algorithm is a quantum algorithm designed to solve a specific problem with high probability in polynomial time, showcasing the potential of quantum computing over classical computing. In the video, it is presented as a follow-up to the Deutsch's algorithm, emphasizing its role in demonstrating quantum supremacy. The algorithm is used to find a hidden bit string 'a' embedded in a function 'f', which is a dot product between 'a' and the input 'x' mod 2. The script explains that while classical computers require exponential time to solve similar problems, quantum computers can do so efficiently.

💡Quantum Computers

Quantum computers are advanced computational devices that use the principles of quantum mechanics to process information. They are highlighted in the video as being capable of solving certain problems, like the Bernstein Vazirani problem, with a high degree of certainty in polynomial time, which is a significant advantage over classical computers. The script contrasts quantum computing with classical computing to emphasize the potential of quantum algorithms.

💡Classical Computers

Classical computers refer to traditional computing systems that process information based on binary digits (bits). In the context of the video, classical computers are shown to be less efficient than quantum computers for certain problems, requiring exponential time to solve with certainty. The script mentions that classical algorithms can solve problems with a negligible error probability in polynomial time, but not with the same efficiency as quantum algorithms.

💡Oracle

In the script, the term 'oracle' refers to a black-box function that is used in the algorithm to compute the output based on the input. Specifically, in the Bernstein Vazirani algorithm, the oracle is used to compute the function 'f(x) = a dot x mod 2'. The oracle is a crucial component in quantum algorithms, as it allows the algorithm to interact with the function in a way that is not possible with classical computing methods.

💡Hadamard Gate

The Hadamard gate is a quantum gate used in quantum computing to create superpositions of qubits. In the video, it is applied to all qubits at the beginning of the Bernstein Vazirani algorithm to prepare the initial state for computation. The script explains that applying the Hadamard gate to a state of all zeros results in an equal superposition of all possible states, which is a fundamental step in the quantum algorithm.

💡Qubit

A qubit, short for quantum bit, is the basic unit of quantum information in quantum computing. Unlike classical bits, which can be either 0 or 1, qubits can exist in a superposition of states. The script mentions qubits in the context of the initial state of the quantum algorithm and the application of quantum gates, such as the Hadamard gate, to manipulate their states.

💡Phase Kickback

Phase kickback is a phenomenon in quantum computing where the phase of a quantum state is influenced by the application of a quantum gate. In the video, phase kickback is discussed in the context of applying the oracle to the quantum state, which results in a phase shift that depends on the function 'f(x)'. This phase shift is crucial for the algorithm to determine the hidden bit string 'a'.

💡Measurement

Measurement in quantum computing refers to the act of observing a quantum system to obtain classical information. The script explains that after applying the Hadamard gate to the quantum state, the state is measured to obtain the bit string 'a'. Measurement is a critical step in quantum algorithms, as it collapses the superposition of states into a definite outcome.

💡Deutsch's Algorithm

Deutsch's Algorithm is a foundational quantum algorithm that demonstrates the ability of quantum computers to solve certain problems more efficiently than classical computers. In the video, it is mentioned as a precursor to the Bernstein Vazirani Algorithm, setting the stage for understanding the progression of quantum algorithms. The script uses Deutsch's Algorithm to contrast the capabilities of quantum and classical computers.

💡Quantum Supremacy

Quantum supremacy refers to the point at which quantum computers can solve problems that classical computers cannot solve in a reasonable amount of time. The video discusses the Bernstein Vazirani Algorithm as an example of a problem where quantum computers can achieve supremacy by solving it with high probability in polynomial time, while classical computers struggle to do so efficiently.

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