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

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

2011-01-04

arxiv.org/abs/1101.0796v2

Physics

Quantum Physics

25 pages, 3 figures, Poster at QIP 2011. v2: clarified exposition, typos corrected, references added

Scientific paper

We give a quantum algorithm for evaluating a class of boolean formulas (such as the NAND tree and the 3-majority tree) 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^2w^{\log n})$ queries where $w$ is independent of $n$. Furthermore we prove a classical lower bound of $n^{\Omega(\log\log n)}$ queries, which admits a (small) super-polynomial speed-up.

Affiliated with

Also associated with

No associations

Rating

Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-75422