Quantum Adversary (Upper) Bound

Abstract

We describe a method to upper bound the quantum query complexity of Boolean formula evaluation problems, using fundamental theorems about the general adversary bound. This nonconstructive method can give an upper bound on query complexity without producing an algorithm. For example, we describe an oracle problem which we prove (non-constructively) can be solved in $O(1)$ queries, where the previous best quantum algorithm uses a polylogarithmic number of queries. We then give an explicit $O(1)$-query algorithm for this problem based on span programs.

Journal version. Edited for clarity and conciseness. Haar transform algorithm removed

References in corpus (5)

• Negative weights make adversaries stronger
• Quantum query complexity of state conversion
• A Quantum Algorithm for the Hamiltonian NAND Tree
• Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
• Symmetry-assisted adversaries for quantum state generation

Cited by in corpus (2)

• Quantum SDP-Solvers: Better upper and lower bounds
• Quantum divide and conquer