0000000000778636

AUTHOR

Shengyu Zhang

showing 1 related works from this author

Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer

2007

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.

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 computerSIAM Journal on Computing
researchProduct