This week:

• Deutsch’s algorithm, Simon’s algorithm

​

• Programming quantum algorithms!

Deutsch’s algorithm

Deutsch’s algorithm

• One of the very first algorithms to provide evidence of the power of quantum algorithms over classical.

​

• We will understand the algorithm.

​

• You will be asked to code this as part of the next homework.

The problem

Determine if a given function

is constant or balanced.

constant:

balanced:

The problem

Determine if a given function

is constant or balanced.

How is the function given to you?

“Black-box” access

Q: How many queries to the black-box does it take to solve the problem (with certainty) classically?

A: 2 queries are necessary and sufficient.

Deutsch’s algorithm does it�in one query!

Querying a function quantumly

In the quantum setting: what does it mean to query a function as a black-box?

This is not a unitary transformation in general!

Why?

Querying a function quantumly

This is looking kind of different from what a classical algorithm had access to…

Is this more powerful..?

Remark: It’s easy to see that a classical algorithm requires 2 queries even if it has access to:

What does quantum computation buy us?

?

1. Let’s try putting the first qubit in superposition:

What does quantum computation buy us?

1. Let’s try putting the first qubit in superposition:

How do we “extract” it though?

What does quantum computation buy us?

2. Let’s try putting the second qubit in superposition:

?

What does quantum computation buy us?

2. Let’s try putting the second qubit in superposition:

Interesting that the global phase �depends on f(x)!�Still just a global phase though..

What does quantum computation buy us?

1. First qubit in superposition:

In summary:

2. Second qubit in superposition:

..any other ideas??

What does quantum computation buy us?

1. First qubit in superposition:

In summary:

2. Second qubit in superposition:

Put both qubits in superposition!

What does quantum computation buy us?

1. First qubit in superposition:

In summary:

2. Second qubit in superposition:

3. Both qubits in superposition:

?

What does quantum computation buy us?

1. First qubit in superposition:

In summary:

2. Second qubit in superposition:

3. Both qubits in superposition:

What does quantum computation buy us?

1. First qubit in superposition:

In summary:

2. Second qubit in superposition:

3. Both qubits in superposition:

Let’s focus on the first qubit

and ignore the second

What does quantum computation buy us?

1. First qubit in superposition:

In summary:

2. Second qubit in superposition:

3. Both qubits in superposition:

Let’s focus on the first qubit

and ignore the second

What does quantum computation buy us?

1. First qubit in superposition:

In summary:

2. Second qubit in superposition:

3. Both qubits in superposition:

?

What does quantum computation buy us?

1. First qubit in superposition:

In summary:

2. Second qubit in superposition:

3. Both qubits in superposition:

up to a global phase

these two states can be

distinguished perfectly!!

Deutsch’s algorithm

(iii) Measure the first qubit in the Hadamard basis.

Simon’s algorithm

Simon’s algorithm

• First example of a quantum algorithm solving a problem exponentially faster than the best classical randomized algorithm.

​

• Like Deutsch, the speedup is in terms of queries to an oracle.

​

• You will be asked to code this as part of the next homework.

The problem

You are given black-box access to a function

with the promise that there exists an

such that

if and only if

or

Find

The problem

You are given black-box access to a function

with the promise that there exists an

such that

if and only if

or

Find

Q: How many queries to the black-box does it take to solve the problem (with certainty) classically?

The problem

You are given oracle access to a function

with the promise that there exists an

such that

if and only if

or

Find

Q: How many queries does a classical randomized algorithm need to succeed “with high probability”?

Can be achieved by a “birthday paradox” style algorithm

The problem

You are given oracle access to a function

with the promise that there exists an

such that

if and only if

or

Find

Q: What about quantum queries?

Quantum queries

We model the black-box as a

acting as

Simon’s algorithm

Consists of:

(i) A quantum sub-routine to sample from a useful distribution many times.�(ii) Classical post-processing on the samples to recover the secrets.

Q: How many times do you need to sample to be able to recover s?

Simon’s algorithm

Consists of:

(i) A quantum sub-routine to sample from a useful distribution many times.�(ii) Classical post-processing of the samples to recover the secrets.

Simon’s algorithm

3. Measure the second qubit (in the standard basis).

(v) Measure first qubit (in the standard basis)

Analysis: at the whiteboard

Quantum subroutine: