The phase/state duality in reversible circuit design
arXiv:2105.13410 · doi:10.1103/PhysRevA.104.052602
Abstract
The reversible implementation of classical functions accounts for the bulk of most known quantum algorithms. As a result, a number of reversible circuit constructions over the Clifford+ gate set have been developed in recent years which use both the state and phase spaces, or and bases, to reduce circuit costs beyond what is possible at the strictly classical level. We study and generalize two particular classes of these constructions: relative phase circuits, including Giles and Selinger's multiply-controlled gates and Maslov's qubit Toffoli gate, and measurement-assisted circuits, including Jones' Toffoli gate and Gidney's temporary logical-AND. In doing so, we introduce general methods for implementing classical functions up to phase and for measurement-assisted termination of temporary values. We then apply these techniques to find novel -count efficient constructions of some classical functions in space-constrained regimes, notably multiply-controlled Toffoli gates and temporary products.
arXiv comment16 pages, comments welcome
References in corpus (11)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Elementary gates for quantum computation
- Halving the cost of quantum addition
- Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
- Quantum circuits of T-depth one
- Automated optimization of large quantum circuits with continuous parameters
- Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
- Novel constructions for the fault-tolerant Toffoli gate
- On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
- Exact synthesis of multiqubit Clifford+T circuits
- On the CNOT-complexity of CNOT-PHASE circuits