next up previous contents
Next: No Quantum Extension of Up: Non-trivial Monotone Graph Properties Previous: Graph Connectivity   Contents


Bipartiteness

A second fundamental non-trivial monotone graph property is whether a graph is bipartite. This graph property is also evasive.

Theorem 3.2.2   $ \Omega$(V) oracle queries are required to decide whether a simple undirected graph is bipartite.


\begin{proof} % latex2html id marker 1852We apply Lemma \ref{lm:1xky}, we will... ...lm:1xky} implies the lower bound $\Omega(\sqrt{V^{2}}) = \Omega(V)$. \end{proof}

If this lower bound is known elsewhere the author is unaware of it. It is not known if this lower bound is asymptotically tight.

Having seen two fundamental monotone graph properties with lower bounds potentially quadratically lower than the classical case it is tempting to believe these lower bounds are tight and that there is quadratic speedup in the quantum bounded error model for non-trivial monotone graph properties. To see this is not the case we need only examine the non-trivial monotone graph property analogous to MAJORITY.

next up previous contents
Next: No Quantum Extension of Up: Non-trivial Monotone Graph Properties Previous: Graph Connectivity   Contents
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository