Physical adjacency is a typical constraint for quantum circuit realization in technologies such as liquid state Nuclear Magnetic Resonance (NMR) and simple trapped-ions. This restriction requires circuit realization to only Linear Nearest Neighbor (LNN) architectures which results in increased cost due to the introduction of additional gates to ensure adjacency. In this work, we present an input line ordering algorithm to reduce the overall quantum cost of circuits to be realized in LNN architecture. Experimental results shows that the proposed algorithm improves the cost of the reordered benchmark circuits by 29% on average compared to their unordered counterparts..
P. Shor, “Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Journal on Computing, vol. 26, no. 5, pp. 1484–1509, October 1997.
L. Grover, “Quantum computers can search arbitrarily large databases by a single query,” Physical Review Letters, vol. 79, no. 23, pp. 4709– 4712, 1997.
F. Magniez, M. Santha, and M. Szegedy, “Quantum algorithms for the triangle problem,” in 16th annual ACM-SIAM symposium on Discrete algorithms, 2005, pp. 1109–1117.
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, 2002.
V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes, “Synthesis of reversible logic circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, no. 6, pp. 710–722, June 2003.
M. Saeedi and I. L. Markov, “Synthesis and optimization of reversible circuits - a survey,” ACM Computing Surveys, vol. 45, no. 2, June 2013.
V. V. Shende, S. S. Bullock, and I. L. Markov, “Synthesis of quantumlogic circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 6, pp. 1000–1010, june 2006.
K. N. Patel, I. L. Markov, and J. P. Hayes, “Optimal synthesis of linear reversible circuits,” Quantum Information & Computing, vol. 8, no. 3, pp. 282–294, March 2008.
O. Golubitsky and D. Maslov, “A study of optimal 4-bit reversible toffoli circuits and their synthesis,” IEEE Transactions on Computers, vol. 61, no. 9, pp. 1341–1353, September 2012.
M. Saeedi, M. S. Zamani, M. Sedighi, and Z. Sasanian, “Reversible circuit synthesis using a cycle-based approach,” ACM Journal on Emerging Technologies in Computing Systems, vol. 6, no. 4, pp. 1–26, December 2010.
D. M. Miller, D. Maslov, and G. W. Dueck, “A transformation based algorithm for reversible logic synthesis,” in 40th annual Design Automation Conference, June 2003, pp. 318–323.
D. Maslov, G. W. Dueck, and D. M. Miller, “Techniques for the synthesis of reversible toffoli networks,” ACM Transactions on Design Automation of Electronic Systems, vol. 12, no. 4, pp. 42:1–42:28, 2007.
D. Wang, S. Sun, and H. Chen, “Matrix-based algorithm for 4-qubit reversible logic circuits synthesis,” Energy Procedia, vol. 13, pp. 365– 371, 2011.
K. Fazel, M. A. Thornton, and J. E. Rice, “Esop-based toffoli gate cascade generation,” in IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, August 2007, pp. 206–209.
M. H. A. Khan and M. A. Perkowski, “Multi-output esop synthesis with cascades of new reversible gate family,” in International Symposium On Representations and Methodology of Future Compo Technology, 2003.
P. Gupta, A. Agrawal, and N. K. Jha, “An algorithm for synthesis of reversible logic circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 11, pp. 2317–2330, November 2006.
J. Donald and N. K. Jha, “Reversible logic synthesis with fredkin and peres gates,” ACM Journal on Emerging Technologies in Computing Systems, vol. 4, no. 1, pp. 2:1–2:19, April 2008.
P. Kerntopf, “A new heuristic algorithm for reversible logic synthesis,” in 41st Design Automation Conference, July 2004, pp. 834–837.
R. Wille and R. Drechsler, “Bdd-based synthesis of reversible logic for large functions,” in 46th Annual Design Automation Conference, 2009, pp. 270–275.
R. Drechsler and R. Wille, “Reversible circuits: Recent accomplishments and future challenges for an emerging technology,” in Progress in VLSI Design and Test, vol. LNCS 7373, 2012, pp. 383–392.
P. Kerntopf, M. Perkowski, and K. Podlaski, “Synthesis of reversible circuits: A view on the state-of-the-art,” in 12th IEEE Conference on Nanotechnology (IEEE-NANO), August 2012, pp. 1–6.
A. Younes and J. F. Miller, “Representation of boolean quantum circuits as reed muller expansions,” International Journal of Electronics, vol. 91, no. 7, pp. 431–444, 2004.
Y. Takahashi, N. Kunihiro, and K. Ohta, “The quantum fourier transform on a linear nearest neighbor architecture,” Quantum Information & Computation, vol. 7, no. 4, pp. 383–391, May 2007.
S. A. Kutin, “Shor’s algorithm on a nearest-neighbor machine,” in Asian Conference on Quantum Information Science (AQIS), 2007.
B. S. Choi and R. V. Meter, “On the effect of quantum interaction distance on quantum addition circuits,” ACM Journal on Emerging Technologies in Computing Systems, vol. 7, no. 3, pp. 11:1–11:17, August 2011.
A. G. Fowler, C. D. Hill, and L. C. L. Hollenberg, “Quantum error correction on linear nearest neighbor qubit arrays,” Physical Review A, vol. 69, no. 4, pp. 042 314.1–042 314.4, 2004.
D. Cheung, D. Maslov, and S. Severini, “Translation techniques between quantum circuit architectures,” in Workshop on Quantum Information Processing, 2007.
K. N. Patel, I. L. Markov, and J. P. Hayes, “Efficient synthesis of linear reversible circuits,” in International Workshop on Logic Synthesis (IWLS), June 2004, pp. 4470–4477.
B. Schaeffer and M. Perkowski, “Linear reversible circuit synthesis in the linear nearest-neighbor model,” in 42nd IEEE International Symposium on Multiple-Valued Logic, May 2012, pp. 157–160.
A. Chakrabarti and S. Sur-Kolay, “Nearest neighbour based synthesis of quantum boolean circuits,” Engineering Letters, vol. 15, no. 2, pp. 356–361, 2007.
M. H. Khan, “Cost reduction in nearest neighbour based synthesis of quantum boolean circuits,” Engineering Letters, vol. 16, pp. 1–5, 2008.
Y. Hirata, M. Nakanishi, S. Yamashita, and Y. Nakashima, “An efficient method to convert arbitrary quantum circuits to ones on a linear nearest neighbor architecture,” in Third International Conference on Quantum, Nano and Micro Technologies, February 2009, pp. 26–33.
——, “An efficient conversion of quantum circuits to a linear nearest neighbor architecture,” Quantum Information & Computing, vol. 11, no. 1, pp. 142–166, January 2011.
M. Saeedi, R. Wille, and R. Drechsler, “Synthesis of quantum circuits for linear nearest neighbor architectures,” Quantum Information Processing, vol. 10, no. 3, pp. 355–377, June 2011.
M. Perkowski, M. Lukac, D. Shah, and M. Kameyama, “Synthesis of quantum circuits in linear nearest neighbor model using positive davio lattices,” Electronics and Energetics, vol. 24, no. 1, pp. 71–87, 2011.
A. Chakrabarti, S. Sur-Kolay, and A. Chaudhury, “Linear nearest neighbor synthesis of reversible circuits by graph partitioning,” http://arxiv.org/abs/1112.0564, vol. v2[cs.ET], 2012.
M. Arabzadeh, M. Saeedi, and M. S. Zamani, “Rule-based optimization of reversible circuits,” in 15th Asia and South Pacific Design Automation Conference (ASP-DAC), January 2010, pp. 849–854.
V. V. Shende and I. L. Markov, “On the cnot-cost of toffoli gates,” Quantum Info. Comput., vol. 9, no. 5, pp. 461–486, May 2009.
R. Wille, D. Grosse, L. Teuber, G. W. Dueck, and R. Drechsler, “Revlib: An online resource for reversible functions and reversible circuits,” in 38th IEEE International Symposium on Multiple Valued Logic, May 2008, pp. 220–225.
M. Arabzadeh and M. Saeedi, RCViewer+, 2nd ed., available at http://ceit.aut.ac.ir/QDA/RCV.htm, February 2013.
M. AlFailakawi, L. AlTerkawi, I. Ahmad, and S. Hamdan, “Line ordering of reversible circuits for linear nearest neighbor realization,” Quantum Information Processing, pp. 1–21, 2013. [Online]. Available: http://dx.doi.org/10.1007/s11128-013-0601-1