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 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 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 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 does a classical randomized algorithm need to succeed “with high probability”?

Can be achieved by picking uniformly random inputs to query�(a “birthday paradox” style analysis)

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

Analysis: at the whiteboard

Quantum subroutine: