Authors
Andris Ambainis, Andrew M Childs, Ben W Reichardt, Robert Špalek, Shengyu Zhang
Publication date
2010/4/30
Journal
SIAM Journal on Computing
Volume
39
Issue
6
Pages
2513-2530
Publisher
Society for Industrial and Applied Mathematics
Description
Consider the problem of evaluating an AND-OR formula on an N-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time . In particular, approximately balanced formulas can be evaluated in queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.
Total citations
Scholar articles
A Ambainis, AM Childs, BW Reichardt, R Špalek… - SIAM Journal on Computing, 2010
A Ambainis, AM Childs, BW Reichardt, R Spalek… - Proceedings of the 48th Annual IEEE Symposium on …