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.

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.

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

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

Simon’s algorithm

Simon’s algorithm

3. Measure the second half of the qubits (in the standard basis).

(v) Measure first half of the qubits (in the standard basis)

Analysis: at the board

Quantum subroutine: