How to Compile Some NAND Formula Evaluators
arXiv:0706.0479
Abstract
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.
Ver.1- 58 pages (files: 1 .tex, 2 .sty, 14 .eps); Ver.2- 64 pages (files: 1 .tex, 2 .sty, 15 .eps, 2 .m, 1 .xxx) Corrected serious error that arose from neglecting time-ordering of exponential. Tree graph compilation is now claimed approximate rather than exact
References in corpus (13)
- Elementary gates for quantum computation
- Exponential algorithmic speedup by quantum walk
- An approximate Fourier transform useful in quantum factoring
- Finding Exponential Product Formulas of Higher Orders
- A Quantum Algorithm for the Hamiltonian NAND Tree
- Quantum Walks, Quantum Gates and Quantum Computers
- A Rudimentary Quantum Compiler(2cnd Ed.)
- 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
- Quantum Fast Fourier Transform Viewed as a Special Case of Recursive Application of Cosine-Sine Decomposition
- Qubiter Algorithm Modification, Expressing Unstructured Unitary Matrices with Fewer CNOTs
- A new algorithm for producing quantum circuits using KAK decompositions
- Simplifying Quantum Circuits via Circuit Invariants and Dressed CNOTs
Cited by in corpus (5)
- Code Generator for Quantum Simulated Annealing
- QuanFou, QuanGlue, QuanOracle and QuanShi, Four Special Purpose Quantum Compilers
- QuanTree and QuanLin, Two Special Purpose Quantum Compilers
- Java Application that Outputs Quantum Circuit for Some NAND Formula Evaluators
- Quibbs, a Code Generator for Quantum Gibbs Sampling