next up previous contents
Next: Quantum Oracle Models Up: Preliminaries Previous: Preliminaries   Contents

Useful Definitions

We will prove lower bounds for functions from {0, 1}N to {0, 1}, we will call such functions N-bit Boolean functions, or just Boolean functions. In our proofs we will frequently need the notion of the Hamming weight of a bit string: this is the number of 1's in the string. We denote the Hamming weight of a bit string x as | x|. We also will frequently refer to all inputs which differ from a particular input in only one bit, we will call inputs which differ in a single bit Hamming neighbors.


next up previous contents
Next: Quantum Oracle Models Up: Preliminaries Previous: Preliminaries   Contents
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository