next up previous contents
Next: Introduction Up: Lower Query Bounds in Previous: List of Figures   Contents

List of Abbreviations

A x B:
The Cartesian product of the sets A and B.
AND:
The Boolean function that returns 1 if and only if every input bit is 1.
D(f ):
The decision tree complexity of the function f.
D(f, x):
The minimum number of bits of input x that determine the value of f (x).
D0(f ):
The nondeterministic decision tree complexity of verifying that f (x) = 0.
D1(f ):
The nondeterministic decision tree complexity of verifying that f (x) = 1.
N(f ):
The nondeterministic decision tree complexity of the function f.
OR:
The Boolean function that returns 0 if and only if every input bit is 0.
PARITY:
The Boolean function that returns 1 if and only if the number of 1 bits in the input is even.
MAJORITY:
The Boolean function that returns 1 if and only if more than half of the input bits are 1.


next up previous contents
Next: Introduction Up: Lower Query Bounds in Previous: List of Figures   Contents
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository