Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1006.3651

Quantum algorithms for formula evaluation

Andris Ambainis

Published Jun 18, 2010• 8 citations
arXivHTMLPDF

Abstract

We survey the recent sequence of algorithms for evaluating Boolean formulas consisting of NAND gates.
DOI
10.48550/arxiv.1006.3651

Related papers

Quantum algorithms for formula evaluation

Andris Ambainis

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

NATO science for peace and security series. D, Information and communication security•Jan 1, 2010•2 citations

How to Compile Some NAND Formula Evaluators

Robert R. Tucci

We say a unitary operator acting on a set of qubits has been compiled if it has been expressed as a SEO (sequence of elementary operations, like CNOTs and single-qubit operations). SEO's are often represented as quantum circuits. arXiv:quant-ph/0702144 by Farhi-Goldstone-Gutmann has inspired a recent flurry of papers, that propose quantum algorithms for evaluating NAND formulas via quantum walks over tree graphs. These algorithms use two types of unitary evolution: oracle and non-oracle. Non-oracle evolutions are independent of the NAND formula input, whereas oracle evolutions depend on this input. In this paper we compile (i.e., give explicit SEOs and their associated quantum circuits for) the oracle and non-oracle evolution operators used in some of these NAND formula evaluators. We consider here only the case of balanced binary NAND trees. Our compilation methods are based on the CSD (Cosine Sine Decomposition), a matrix decomposition from Linear Algebra. The CS decomposition has been used very successfully in the past to compile unstructured unitary matrices exactly.

arXiv:0706.0479•Jun 4, 2007•5 citations

Quantum Algorithms for Cryptographically Significant Boolean Functions

Tharrmashastha Sapv, Debajyoti Bera, Arpita Maitra +1 more

SpringerBriefs in computer science•Jan 1, 2021•1 citation

Quantum logic gate construction and quantum algorithms

Xinlan Zhou

•Jan 1, 2002•0 citations

Span-program-based quantum algorithm for evaluating formulas

Ben W. Reichardt, Robert Špalek

We give a quantum algorithm for evaluating formulas over an extended gate set, including all two- and three-bit binary gates (e.g., NAND, 3-majority). The algorithm is optimal on read-once formulas for which each gate's inputs are balanced in a certain sense.

ACM Symposium on Theory of Computing (STOC)•May 17, 2008•95 citations

A quantum algorithm for approximating the influences of Boolean functions and its applications

Hongwei Li, Li Yang

arXiv:1409.1416•Quantum Information Processing•Mar 4, 2015•31 citations
We say a unitary operator acting on a set of qubits has been compiled if it has been expressed as a SEO (sequence of elementary operations, like CNOTs and single-qubit operations). SEO's are often represented as quantum circuits. arXiv:quant-ph/0702144 by Farhi-Goldstone-Gutmann has inspired a recent flurry of papers, that propose quantum algorithms for evaluating NAND formulas via quantum walks over tree graphs. These algorithms use two types of unitary evolution: oracle and non-oracle. Non-oracle evolutions are independent of the NAND formula input, whereas oracle evolutions depend on this input. In this paper we compile (i.e., give explicit SEOs and their associated quantum circuits for) the oracle and non-oracle evolution operators used in some of these NAND formula evaluators. We consider here only the case of balanced binary NAND trees. Our compilation methods are based on the CSD (Cosine Sine Decomposition), a matrix decomposition from Linear Algebra. The CS decomposition has been used very successfully in the past to compile unstructured unitary matrices exactly.