Quantum Sabotage Complexity

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro

Given a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$, the goal in the usual query model is to compute $f$ on an unknown input $x\in \{0,1{\}}^n$ while minimizing the number of queries t…