next up previous contents
Next: AND and OR Up: Lower Oracle Query Bounds Previous: Partially Symmetric Functions   Contents


AND, OR, MAJORITY, and PARITY

We can use Theorem 2.5.1 to easily prove lower bounds for the well-known symmetric functions AND, OR, MAJORITY, and PARITY. While these results have been previously established by Beals et al. [2], the ease with which they are proved through Ambainis' Theorem is noteworthy.



Subsections
next up previous contents
Next: AND and OR Up: Lower Oracle Query Bounds Previous: Partially Symmetric Functions   Contents
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository