### Volume 2013

#### Article 4

Published by the Department of Computer Science, The University of Chicago.

#### Quantum Adversary (Upper) Bound

Shelby Kimmel
Massachussetts Institute of Technology
skimmel AT mit DOT edu

April 5, 2013

#### 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.

• The article: PDF (252 KB)
• Source material: ZIP (110 KB)
• BibTeX entry for this article (222 bytes)

Submitted December 12, 2012, revised February 27, and April 2, 2013; published April 5, 2013.

Article 3 Article 5
Volume 2013 Published articles