6533b85ffe1ef96bd12c0ff1

RESEARCH PRODUCT

Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions

Andris AmbainisAndrew M. ChildsBen W. Reichardt

subject

CombinatoricsDiscrete mathematicsComputational complexity theoryOpen problemExistential quantificationQuantum algorithmQuantum walkComputational geometryUpper and lower boundsQuantum computerMathematics

description

For any AND-OR formula of size N, there exists a bounded-error N1/2+o(1)-time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(radicN) queries, which is optimal. It follows that the (2-o(1))th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.

yearjournalcountryeditionlanguage
2007-10-0148th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
https://doi.org/10.1109/focs.2007.10