Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer

Details Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer

2007-03-02

arxiv.org/abs/quant-ph/0703015v3

Physics

Quantum Physics

14 pages, 3 figures, v2: substantially rewritten with clearer analysis, v3: using better discretization we have obtained an op

Scientific paper

For every NAND formula of size N, there is a bounded-error N^{1/2+o(1)}-time quantum algorithm, based on a coined quantum walk, that evaluates this formula on a black-box input. Balanced, or ``approximately balanced,'' NAND formulas can be evaluated in O(sqrt{N}) 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.

Affiliated with

Also associated with

No associations

Rating

Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer 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 Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-719978