Published in

Proceedings of the 3rd Innovations in Theoretical Computer Science Conference on - ITCS '12

DOI: 10.1145/2090236.2090258

Links

Tools

Export citation

Search in Google Scholar

Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure

Journal article published in 2011 by Bohua Zhan, Shelby Kimmel ORCID, Avinatan Hassidim
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

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

Abstract

We give a quantum algorithm for evaluating a class of boolean formulas (such as NAND trees and 3-majority trees) on a restricted set of inputs. Due to the structure of the allowed inputs, our algorithm can evaluate a depth $n$ tree using $O(n^{2+\logω})$ queries, where $ω$ is independent of $n$ and depends only on the type of subformulas within the tree. We also prove a classical lower bound of $n^{Ω(\log\log n)}$ queries, thus showing a (small) super-polynomial speed-up. ; Comment: 30 pages, 2 figures, v3: clarified exposition, matches journal reference