arXiv:1701.06942 · Baltic Journal of Modern Computing
Optimal One-shot Quantum Algorithm for EQUALITY and AND
Andris Ambainis, Jānis Iraids
Abstract
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 .