Published in

Springer, Lecture Notes in Computer Science, p. 557-568, 2012

DOI: 10.1007/978-3-642-31594-7_47

Links

Tools

Export citation

Search in Google Scholar

Quantum Adversary (Upper) Bound

Journal article published in 2011 by Shelby Kimmel ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Red circle
Preprint: archiving forbidden
Orange circle
Postprint: archiving restricted
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

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. ; Comment: Journal version. Edited for clarity and conciseness. Haar transform algorithm removed