Quantum algorithms for formula evaluation

Abstract

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

11 pages, survey for NATO ARW "Quantum Cryptography and Computing", Gdansk, September 2009

References in corpus (5)

• On the relationship between continuous- and discrete-time quantum walk
• Quantum Search on Bounded-Error Inputs
• Quantum vs. Classical Communication and Computation
• Hamiltonian Oracles
• A nearly optimal discrete query quantum algorithm for evaluating NAND formulas

Cited by in corpus (3)

• New Developments in Quantum Algorithms
• The Quantum Query Complexity of AC0
• Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs