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