Efficient Synthesis of Linear Reversible Circuits
arXiv:quant-ph/0302002
Abstract
In this paper we consider circuit synthesis for n-wire linear reversible circuits using the C-NOT gate library. These circuits are an important class of reversible circuits with applications to quantum computation. Previous algorithms, based on Gaussian elimination and LU-decomposition, yield circuits with O(n^2) gates in the worst-case. However, an information theoretic bound suggests that it may be possible to reduce this to as few as O(n^2/log n) gates. We present an algorithm that is optimal up to a multiplicative constant, as well as Theta(log n) times faster than previous methods. While our results are primarily asymptotic, simulation results show that even for relatively small n our algorithm is faster and yields more efficient circuits than the standard method. Generically our algorithm can be interpreted as a matrix decomposition algorithm, yielding an asymptotically efficient decomposition of a binary matrix into a product of elementary matrices.
12 pages, 4 figures
References in corpus (1)
Cited by in corpus (10)
- A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
- Techniques for the Synthesis of Reversible Toffoli Networks
- Direct randomized benchmarking for multi-qubit devices
- Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
- Detection and Elimination of Non-Trivial Reversible Identities
- Dynamic Qubit Routing with CNOT Circuit Synthesis for Quantum Compilation
- Synthesis and Optimization of Reversible Circuits for Homogeneous Boolean Functions
- Fault-tolerant ancilla preparation and noise threshold lower bounds for the 23-qubit Golay code
- Efficient CNOT Synthesis for NISQ Devices
- Quadratic Form Expansions for Unitaries