It follows from this lower bound that while the quantum query complexity of the \(\mathsf {OR}_n\)  function\(\mathsf {OR}_n\)  is the \(\mathsf {OR}\)  of \(n\)  variables.
From Grover's algorithm [1]}, [2]} we have \(\mathsf {Q}(\mathsf {OR}_n)= \sqrt{n}\) . On the other hand \(\mathsf {FC}(\mathsf {OR}_n) = \Omega (\mathsf {s}(\mathsf {OR}_n)) = \Omega (n)\) . is \(\Theta (\sqrt{n})\) , its quantum certificate game complexity is \(\mathsf {CG}^*(\mathsf {OR}_n) = \Theta (n)\) .
