Unbounded Error Quantum Query Complexity

Understand

This work studies the quantum query complexity of Boolean functions in a scenario where it is only required that the query algorithm succeeds with a probability strictly greater than 1/2.

• We show that, just as in the communication complexity model, the unbounded error quantum query complexity is exactly half of its classical counterpart for any (partial or total) Boolean function.
• Moreover, we show that the "black-box" approach to convert quantum query algorithms into communication protocols by Buhrman-Cleve-Wigderson [STOC'98] is optimal even in the unbounded error setting.
• We also study a setting related to the unbounded error model, called the weakly unbounded error setting, where the cost of a query algorithm is given by q+log(1/2(p-1/2)), where q is the number of queries made and p>1/2 is the success probability of the algorithm.