Quantum algorithms for formula evaluation

2010/06/18 by Ambainis, Andris
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.1006.3651

Abstract

We survey the recent sequence of algorithms for evaluating Boolean formulas consisting of NAND gates.

Related

• Span-program-based quantum algorithm for evaluating unbalanced formulas
• A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
• Every NAND formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer
• Java Application that Outputs Quantum Circuit for Some NAND Formula Evaluators
• How to Compile Some NAND Formula Evaluators