Layout Optimization for Quantum Circuits with Linear Nearest Neighbor Architectures
Authors:
- 23 May 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Circuits and Systems Magazine
- Vol. 16 (2) , 62-74
Abstract
This paper is concerned with the physical design of quantum logic circuits. More precisely, it addresses the problem of minimizing the number of required qubit reorderings (achieved by inserting explicit SWAP gates) when mapping a quantum circuit into a linear nearest neighbor quantum archi-tecture. First, an interaction graph that captures the interaction distances among various qubits in the quantum circuit is constructed. The interaction graph is utilized to partition the quantum circuit into a set of subcircuits such that the number of required qubit reoderings within each subcircuit is provably no more than a given threshold. Next, a Minimum Linear Arrangement problem for each subcircuit is formulated and solved to achieve the minimum number of internal qubit reorderings and determine the subcircuit input and output qubit orderings. Finally, a bubble sort algorithm is repeatedly employed to minimize the number of qubit reorderings that are required between the consecutive subcircuits. Experiments done on various quantum Fourier transform circuits as well as various reversible logic circuits demonstrate the effectiveness of the proposed approach.Keywords
This publication has 22 references indexed in Scilit:
- On the Effect of Quantum Interaction Distance on Quantum Addition CircuitsACM Journal on Emerging Technologies in Computing Systems, 2011
- Reversible circuit synthesis using a cycle-based approachACM Journal on Emerging Technologies in Computing Systems, 2010
- Quantum computersNature, 2010
- Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architecturesPhysical Review A, 2007
- Architectural implications of quantum computing technologiesACM Journal on Emerging Technologies in Computing Systems, 2006
- Scalable multiparticle entanglement of trapped ionsNature, 2005
- Discrete non-Abelian gauge theories in Josephson-junction arrays and quantum computationPhysical Review B, 2004
- Quantum-error correction on linear-nearest-neighbor qubit arraysPhysical Review A, 2004
- Experiments on the minimum linear arrangement problemACM Journal of Experimental Algorithmics, 2003
- Architecture for a large-scale ion-trap quantum computerNature, 2002