Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge

Shalev Ben-David, Robin Kothari

We define a new query measure we call quantum distinguishing complexity, denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which must output a state close t…