6533b831fe1ef96bd12999c5
RESEARCH PRODUCT
Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
Andris AmbainisAndrew M. ChildsShengyu ZhangBen W. ReichardtRobert Spaleksubject
Discrete mathematicsQuantum t-designComputational complexity theoryGeneral Computer ScienceGeneral MathematicsSpectrum (functional analysis)Value (computer science)0102 computer and information sciencesTree (graph theory)01 natural sciencesCombinatoricsTree (descriptive set theory)Discrete time and continuous time010201 computation theory & mathematics0103 physical sciencesQuantum operationQuantum phase estimation algorithmQuantum Fourier transformQuantum walkQuantum algorithm010306 general physicsMathematicsQuantum computerdescription
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 $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ 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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2007-10-01 | SIAM Journal on Computing |