1 of 19

Deutsch’s algorithm

2 of 19

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

3 of 19

The problem

Determine if a given function

 

is constant or balanced.

constant:

 

balanced:

 

 

 

 

 

0

1

0

1

0

1

0

1

or

0

1

0

1

0

1

0

1

or

4 of 19

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!

5 of 19

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?

 

 

 

 

 

 

6 of 19

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:

 

 

 

 

7 of 19

What does quantum computation buy us?

?

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

8 of 19

What does quantum computation buy us?

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

How do we “extract” it though?

 

9 of 19

What does quantum computation buy us?

 

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

 

 

 

 

 

 

?

 

 

 

 

 

10 of 19

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

 

11 of 19

What does quantum computation buy us?

 

 

 

1. First qubit in superposition:

In summary:

2. Second qubit in superposition:

 

 

 

 

 

 

 

 

 

..any other ideas??

12 of 19

What does quantum computation buy us?

 

 

 

1. First qubit in superposition:

In summary:

2. Second qubit in superposition:

 

 

 

 

 

 

 

 

 

Put both qubits in superposition!

13 of 19

What does quantum computation buy us?

 

 

 

1. First qubit in superposition:

In summary:

2. Second qubit in superposition:

 

 

 

 

 

 

 

 

 

3. Both qubits in superposition:

 

 

?

14 of 19

What does quantum computation buy us?

 

 

 

1. First qubit in superposition:

In summary:

2. Second qubit in superposition:

 

 

 

 

 

 

 

 

 

3. Both qubits in superposition:

 

 

 

 

 

 

15 of 19

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

16 of 19

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

17 of 19

What does quantum computation buy us?

 

 

 

1. First qubit in superposition:

In summary:

2. Second qubit in superposition:

 

 

 

 

 

 

 

 

 

3. Both qubits in superposition:

 

 

 

 

 

 

 

 

 

 

 

?

 

18 of 19

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!!

19 of 19

Deutsch’s algorithm

 

 

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