Simple Quantum Algorithms

Question 1

Define parallel computation.

Answer 1

The circuit computes all f(x) at once, though measurement only reveals one. To get more information out, interference is needed.

Question 2

Describe Deutsch’s algorithm.

Answer 2

Question 3

How does Deutsch’s algorithm extend to the Deutsch-Joza algorithm?

Answer 3

If f(x) = constant, the measurement produces |0>^n 100% of the time. If f(x) is balanced, measuring the query register will give at least one quibit.

Question 4

Explain Grover’s search algorithm

Answer 4

Question 5

How can Grover’s search algorithm be treated as a rotation?

Answer 5

Question 6

What would Grover’s search algorithm look like for n=2 and M=1. Include the upper bound on the number of itterations.

Answer 6

Question 7

What would Grover’s search algorithm look like for n=2 and M=1. Include the upper bound on the number of itterations.

Answer 7

Question 8

How does the quantum Fourier transform act on a state?

Answer 8

Question 9

How would you verify the circuit diagram show is the Fourier transform circuit?

Answer 9