Contents

• List of Tables
• List of Figures
• Introduction
  • Motivation
  • Early Results
  • Quantum Computing
    • Error Models
  • Lower Bounds
  • Summary
  
  
• Lower Oracle Query Bounds
  • Preliminaries
  • A Lemma for Proving Lower Query Bounds
    • Application to Generalized XOR
  • Determining the Oracle String
  • Singleton Functions
  • Partially Symmetric Functions
  • AND, OR, MAJORITY, and PARITY
  • Nonconstant Symmetric Functions
  
  
• Graph Properties
  • Preliminaries
  • Non-trivial Monotone Graph Properties
    • Graph Connectivity
    • Bipartiteness
  • No Quantum Extension of the Aanderaa-Karp-Rosenberg Conjecture
  
  
• Boolean Functions
  • Tree Functions
  • Nondeterministic Decision Tree Complexity
  • Nondeterministically Evasive Functions
  • Sensitive Functions
  
  
• Open Questions
• Bibliography