A nearly optimal discrete query quantum algorithm for evaluating NAND formulas

2007/04/26 by Ambainis, Andris
#FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.0704.3628

Abstract

We present an O(√(N)) discrete query quantum algorithm for evaluating balanced binary NAND formulas and an O(N^1/2+O((1)/(√(log N)))) discrete query quantum algorithm for evaluating arbitrary binary NAND formulas.

Related

• Every NAND formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer
• Quantum algorithms for formula evaluation
• Span-program-based quantum algorithm for evaluating unbalanced formulas
• How to Compile Some NAND Formula Evaluators
• Quantum Query Algorithms for Certain Problems and Generalization of Algorithm Designing Techniques