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

TitleSuper-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
Publication TypeJournal Article
Year of Publication2012
AuthorsZhan, B, Kimmel, S, Hassidim, A
JournalITCS '12 Proceedings of the 3rd Innovations in Theoretical Computer Science Conference
Pages249-265
Date Published2012/01/08
ISBN Number978-1-4503-1115-1
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\omega})$ queries, where $\omega$ is independent of $n$ and
depends only on the type of subformulas within the tree. We also prove a
classical lower bound of $n^{\Omega(\log\log n)}$ queries, thus showing a
(small) super-polynomial speed-up.

URLhttp://arxiv.org/abs/1101.0796v3
DOI10.1145/2090236.2090258
Short TitleITCS 2012 Proceedings of the 3rd Innovations in Theoretical Computer Science