Next:
List of Tables
Up:
Lower Query Bounds in
Previous:
Acknowledgments
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
Next:
List of Tables
Up:
Lower Query Bounds in
Previous:
Acknowledgments
Matthew Hayward
Lower Query Bounds in the Quantum Oracle Model GitHub Repository