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:0802.2370

Java Application that Outputs Quantum Circuit for Some NAND Formula Evaluators

Robert R. Tucci

Published Feb 17, 2008• 3 citations
arXivHTMLPDF

Abstract

This paper introduces QuanFruit v1.1, a Java application available for free. (Source code included in the distribution.) Recently, Farhi-Goldstone-Gutmann (FGG) wrote a paper arXiv:quant-ph/0702144 that proposes a quantum algorithm for evaluating NAND formulas. QuanFruit outputs a quantum circuit for the FFG algorithm.
DOI
10.48550/arxiv.0802.2370

Related papers

QuanFou, QuanGlue, QuanOracle and QuanShi, Four Special Purpose Quantum Compilers

Robert R. Tucci

This paper introduces QuanFou v1.1, QuanGlue v1.1, QuanOracle v1.1, QuanShi v1.1, four Java applications available for free. (Source code included in the distribution.) Each application compiles a different kind of input quantum evolution operator. The applications output a quantum circuit that equals the input evolution operator.

arXiv:0802.2367•Feb 17, 2008•4 citations

QOperAv, a Code Generator for Generating Quantum Circuits for Evaluating Certain Quantum Operator Averages

Robert R. Tucci

This paper introduces QOperAv v1.5, a Java application available for free. (Source code included in the distribution.) QOperAv is a "code generator" for generating quantum circuits. The quantum circuits generated by QOperAv can be used to evaluate with polynomial efficiency the average of $f(A)$ for some simple (that is, computable with polynomial efficiency) function $f$ and a Hermitian operator $A$, provided that we know how to compile $\exp(iA)$ with polynomial efficiency. QOperAv implements an algorithm described in earlier papers, that combines various standard techniques such as quantum phase estimation and quantum multiplexors.

arXiv:1010.4926•Oct 24, 2010•0 citations

QuanTree and QuanLin, Two Special Purpose Quantum Compilers

Robert R. Tucci

This paper introduces QuanTree v1.1 and QuanLin v1.1, two Java applications available for free. (Source code included in the distribution.) Each application compiles a different type of input quantum evolution operator. The applications output a quantum circuit that is approximately equal to the input evolution operator. QuanTree compiles an input evolution operator whose Hamiltonian is proportional to the incidence matrix of a balanced, binary tree graph. QuanLin compiles an input evolution operator whose Hamiltonian is proportional to the incidence matrix of a line (open string) graph. Both applications also output an error, defined as the distance in the Frobenius norm between the input evolution operator and the output quantum circuit.

arXiv:0712.3887•Dec 23, 2007•4 citations

Code Generator for Quantum Simulated Annealing

Robert R. Tucci

This paper introduces QuSAnn v1.2 and Multiplexor Expander v1.2, two Java applications available for free. (Source code included in the distribution.) QuSAnn is a "code generator" for quantum simulated annealing: after the user inputs some parameters, it outputs a quantum circuit for performing simulated annealing on a quantum computer. The quantum circuit implements the algorithm of Wocjan et al. (arXiv:0804.4259), which improves on the original algorithm of Somma et al. (arXiv:0712.1008). The quantum circuit generated by QuSAnn includes some quantum multiplexors. The application Multiplexor Expander allows the user to replace each of those multiplexors by a sequence of more elementary gates such as multiply controlled NOTs and qubit rotations.

arXiv:0908.1633•Aug 12, 2009•7 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

Discrete-query quantum algorithm for NAND trees

Andrew M. Childs, Richard Cleve, Stephen P. Jordan +1 more

This is a comment on the article “A Quantum Algorithm for the Hamiltonian NAND Tree” by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, Theory of Computing 4 (2008) 169-190. That paper gave a quantum algorithm for evaluating nand trees with running time $O(\sqrt{N})$ in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using $N^{1/2 + o(1)}$ queries in the conventional (discrete) quantum query model.

arXiv:quant-ph/0702160•Theory of Computing•Jan 1, 2009•33 citations
This paper introduces QOperAv v1.5, a Java application available for free. (Source code included in the distribution.) QOperAv is a "code generator" for generating quantum circuits. The quantum circuits generated by QOperAv can be used to evaluate with polynomial efficiency the average of f(A)f(A)f(A) for some simple (that is, computable with polynomial efficiency) function fff and a Hermitian operator AAA, provided that we know how to compile exp⁡(iA)\exp(iA)exp(iA) with polynomial efficiency. QOperAv implements an algorithm described in earlier papers, that combines various standard techniques such as quantum phase estimation and quantum multiplexors.
This paper introduces QuanTree v1.1 and QuanLin v1.1, two Java applications available for free. (Source code included in the distribution.) Each application compiles a different type of input quantum evolution operator. The applications output a quantum circuit that is approximately equal to the input evolution operator. QuanTree compiles an input evolution operator whose Hamiltonian is proportional to the incidence matrix of a balanced, binary tree graph. QuanLin compiles an input evolution operator whose Hamiltonian is proportional to the incidence matrix of a line (open string) graph. Both applications also output an error, defined as the distance in the Frobenius norm between the input evolution operator and the output quantum circuit.
This paper introduces QuSAnn v1.2 and Multiplexor Expander v1.2, two Java applications available for free. (Source code included in the distribution.) QuSAnn is a "code generator" for quantum simulated annealing: after the user inputs some parameters, it outputs a quantum circuit for performing simulated annealing on a quantum computer. The quantum circuit implements the algorithm of Wocjan et al. (arXiv:0804.4259), which improves on the original algorithm of Somma et al. (arXiv:0712.1008). The quantum circuit generated by QuSAnn includes some quantum multiplexors. The application Multiplexor Expander allows the user to replace each of those multiplexors by a sequence of more elementary gates such as multiply controlled NOTs and qubit rotations.
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.
This is a comment on the article “A Quantum Algorithm for the Hamiltonian NAND Tree” by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, Theory of Computing 4 (2008) 169-190. That paper gave a quantum algorithm for evaluating nand trees with running time O(N)O(\sqrt{N})O(N​) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using N1/2+o(1)N^{1/2 + o(1)}N1/2+o(1) queries in the conventional (discrete) quantum query model.