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

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

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

Analysis: at the whiteboard

Quantum subroutine: