Oracle problems as communication tasks and optimization of quantum algorithms

Amit Te'eni, Zohar Schwartzman-Nowik, Marcin Nowakowski +2

Quantum query complexity studies the number of queries needed to learn some property of a black box. A closely related question is how well an algorithm can succeed with this learn…