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

2007/03/02 by Childs, Andrew M., Reichardt, Ben W., Spalek, Robert +1 · 1 citation
#FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.quant-ph/0703015

Abstract

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(sqrtN) 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.

Cited by

• Compositional Quantum Control Flow with Efficient Compilation in Qunity

Related

• A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
• Quantum algorithms for formula evaluation
• How fast can a quantum computer search?
• Tight Bounds on Quantum Searching
• How to Compile Some NAND Formula Evaluators