Next:
Contents
Contents
Quantum Computing and Grover's Algorithm
Matthew Hayward
Contents
Motivation for Study of Quantum Computing
A ``Killer App'' for Quantum Computing
The Quantum Computer
The Qubit
The Quantum Register
A Formal Description of a Quantum Register
Performing Computations
Grover's Algorithm
An Illustration of Grover's Algorithm
Outline of Proof of Correctness of Grover's Algorithm
Operator to Create Equal Superposition of States
Operator to Rotate Phase
Inversion About Average Operator
Proof that Operations are Unitary
Proof that Algorithm Increases Amplitude of Desired State
A Special Case
Open Questions
How Many Iterations are Required
Searching for More Than One Item
Optimality of Grover's Algorithm
Implications on P = NP
Conclusion
Bibliography
About this document ...
Matthew Hayward 2008-04-26
