Alireza Shafaei
Mehdi Saeedi
Massoud Pedram
ABSTRACT
Optimization of the interaction distance between qubits to map a quantum circuit into one-dimensional quantum architectures is addressed. The problem is formulated as the Minimum Linear Arrangement (MinLA) problem. To achieve this, an interaction graph is constructed for a given circuit, and multiple instances of the MinLA problem for selected subcircuits of the initial circuit are formulated and solved. In addition, a lookahead technique is applied to improve the cost of the proposed solution which examines different subcircuit candidates. Experiments on quantum circuits for quantum Fourier transform and reversible benchmarks show the effectiveness of the approach.
- D. Cheung, D. Maslov, and S. Severini. Translation techniques between quantum circuit architectures. Workshop on Quant. Inf. Proc., Dec 2007.Google Scholar
- H. Häffner et al. Scalable multiparticle entanglement of trapped ions. Nature, 438:643--646, Dec 2005.Google ScholarCross Ref
- M. Laforest et al. Using error correction to determine the noise model. Phys. Rev. A, 75(1):133--137, 2007.Google ScholarCross Ref
- B. Douçot, L. B. Ioffe, and J. Vidal. Discrete non-Abelian gauge theories in Josephson-junction arrays and quantum computation. Phys. Rev. B, 69(21):214501, Jun 2004.Google ScholarCross Ref
- C. A. Pérez-Delgado, M. Mosca, P. Cappellaro, D. G. Cory. Single spin measurement using cellular automata techniques. Phys. Rev. Lett., 97(10):100501, 2006.Google ScholarCross Ref
- Y. Takahashi, N. Kunihiro, and K. Ohta. The quantum Fourier transform on a linear nearest neighbor architecture. Quant. Inf. Comput., 7:383--391, 2007. Google ScholarDigital Library
- D. Maslov. Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite neighbor quantum architectures. Phys. Rev. A, 76, 2007.Google Scholar
- A. G. Fowler, S. J. Devitt, and L. Hollenberg. Implementation of Shor's algorithm on a linear nearest neighbour qubit array. Quant. Inf. Comput., 4:237--245, 2004. Google ScholarDigital Library
- S. A. Kutin. Shor's algorithm on a nearest-neighbor machine. Asian Conf. on Quant. Inf. Sci., 2007.Google Scholar
- P. Pham, K. Svore. A 2D nearest-neighbor quantum architecture for factoring. arXiv:1207.6655, 2012.Google Scholar
- B.-S. Choi and R. Van Meter. On the effect of quantum interaction distance on quantum addition circuits. J. Emerg. Technol. Comput. Sys., 7(3):11:1--11:17, August 2011. Google ScholarDigital Library
- A. G. Fowler, C. D. Hill, L. Hollenberg. Quantum error correction on linear nearest neighbor qubit arrays. Phys. Rev. A, 69:042314.1--042314.4, 2004.Google ScholarCross Ref
- M. Arabzadeh, M. Saheb Zamani, M. Sedighi, and M. Saeedi. Depth-optimized reversible circuit synthesis. Quant. Inf. Proc., 2012. Google ScholarDigital Library
- M. Möttönen, J. J. Vartiainen. Decompositions of general quantum gates. Ch. 7 in Trends in Quantum Computing Research, NOVA Publishers, 2006.Google Scholar
- V. V. Shende, S. S. Bullock, and I. L. Markov. Synthesis of quantum-logic circuits. IEEE Trans. CAD, 25(6):1000--1010, June 2006. Google ScholarDigital Library
- M. Saeedi, M. Arabzadeh, M. Saheb Zamani, and M. Sedighi. Block-based quantum-logic synthesis. Quant. Inf. Comput., 11(3--4):0262--0277, 2011. Google ScholarDigital Library
- M. Saeedi, M. Saheb Zamani, M. Sedighi, and Z. Sasanian. Reversible circuit synthesis using a cycle-based approach. J. Emerg. Technol. Comput. Sys., 6(4):13:1--13:26, 2010. Google ScholarDigital Library
- M. Saeedi, R. Wille, and R. Drechsler. Synthesis of quantum circuits for linear nearest neighbor architectures. Quant. Inf. Proc., 10(3):355--377, 2011. Google ScholarDigital Library
- Y. Hirata, M. Nakanishi, S. Yamashita, and Y. Nakashima. An efficient conversion of quantum circuits to a linear nearest neighbor architecture. Quant. Inf. Comput., 11(1--2):0142--0166, 2011. Google ScholarDigital Library
- M. Saeedi and I. L. Markov. Synthesis and optimization of reversible circuits - a survey. ACM Computing Surveys, to appear, arXiv:1110.2574, 2012. Google ScholarDigital Library
- D. Kielpinski, C. Monroe, and D. J. Wineland. Architecture for a large-scale ion-trap quantum computers. Nature, 417:709--711, Jun 2002.Google ScholarCross Ref
- R. Van Meter and M. Oskin. Architectural implications of quantum computing technologies. J. Emerg. Technol. Comput. Sys., 2(1):31--63, 2006. Google ScholarDigital Library
- M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge Univ. Press, 2000. Google ScholarDigital Library
- S. Kutin, D. Moulton, and L. Smithline. Computation at a distance. Chicago J. of Theor. Comput. Sci., 2007.Google Scholar
- J. Petit. Experiments on the minimum linear arrangement problem. J. Exp. Algorithmics, 8, 2003. Google ScholarDigital Library
- R. Wille et al. RevLib: An online resource for reversible functions and reversible circuits. Int'l Symp. on Multiple-Valued Logic, pages 220--225, May 2008. Google ScholarDigital Library
- M. Oswald, G. Reinelt, and S. Wiesberg. Exact solution of the 2-dimensional grid arrangement problem. Discrete Optimization, 9(3):189--199, 2012.Google ScholarCross Ref
- D. Maslov, S. M. Falconer, M. Mosca. Quantum circuit placement. IEEE Trans. CAD, 27(4):752--763, 2008. Google ScholarDigital Library
Index Terms
- Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures
Recommendations
Universal quantum computing in linear nearest neighbor architectures
We introduce a scheme for realizing universal quantum computing in a linear nearest neighbor architecturewith fixed couplings. We first show how to realize a controlled-NOT gate operation between two adjacentqubits without having to isolate the two ...
On the Effect of Quantum Interaction Distance on Quantum Addition Circuits
We investigate the theoretical limits of the effect of the quantum interaction distance on the speed of exact quantum addition circuits. For this study, we exploit graph embedding for quantum circuit analysis. We study a logical mapping of qubits and ...
Mapping from multiple-control Toffoli circuits to linear nearest neighbor quantum circuits
In recent years, quantum computing research has been attracting more and more attention, but few studies on the limited interaction distance between quantum bits (qubit) are deeply carried out. This paper presents a mapping method for transforming ...
Comments