Optimal One-shot Quantum Algorithm for EQUALITY and AND
Andris Ambainis, Jānis Iraids · Baltic Journal of Modern Computing · 2016
We study the computation complexity of Boolean functions in the quantum black box model.In this model our task is to compute a function f : {0, 1} → {0, 1} on an input x ∈ {0, 1} n that can be accessed by querying the black box.Quantum algorithms are inherently probabilistic; we are interested in the lowest possible probability that the algorithm outputs incorrect answer (the error probability) for a fixed number of queries.We show that the lowest possible error probability for ANDn and EQUALITY n+1 is 1 2 -n n 2 +1 .