×

Linear nearest neighbor optimization in quantum circuits: a multiobjective perspective. (English) Zbl 1387.81171

Summary: Several current implementations of quantum circuits rely on the linear nearest neighbor restriction, which only allows interaction between adjacent qubits. Most methods that address the process of converting a generic circuit to an equivalent circuit which satisfies this restriction, minimize the number of additional SWAP gates required by this process. Moreover, most methods which address this problem are designed for 1D circuits. Considering the new and promising proposals for 2D quantum circuits, what we propose is a new perspective on this problem, namely that it can be seen as a multiobjective optimization problem. To test our hypothesis, we developed a multiobjective evolutionary algorithm that solves this problem by considering two objectives: minimizing the size of the 2D grid where the circuit is placed, and minimizing the number of additional SWAP gates. Of the methods designed for 2D circuits, only one considers different grid sizes which are much larger than strictly necessary. Consequently, our algorithm makes considerations which other methods do not make, since it naturally finds the grid which requires fewer SWAP gates for the circuit conversion, whether it is one-dimensional or two-dimensional. Our experimental results indicate that allowing a larger grid size results in fewer additional SWAP gates in about 73% of the tested circuits. Additionally, the average improvement we found when using larger grid sizes is about 30%, while the best improvement over using the smallest possible grid is 63.8%.

MSC:

81P68 Quantum computation
94C05 Analytic circuit theory

Software:

RevLib; RevKit
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] AlFailakawi, M., Ahmad, I., Hamdan, S.: Lnn reversible circuit realization using fast harmony search based heuristic. In: Asia-Pacific Conference on Computer Science and Electrical Engineering (2014)
[2] AlFailakawi, M., AlTerkawi, L., Ahmad, I., Hamdan, S.: Line ordering of reversible circuits for linear nearest neighbor realization. Quantum Inf. Process. 12(10), 3319-3339 (2013) · Zbl 1286.81042 · doi:10.1007/s11128-013-0601-1
[3] Alfailakawi, M.G., Ahmad, I., Hamdan, S.: Harmony-search algorithm for 2d nearest neighbor quantum circuits realization. Expert Syst. Appl. 61, 16-27 (2016) · doi:10.1016/j.eswa.2016.04.038
[4] Amarilla, A., Lima, J., Baran, B.: An improved algorithm for quantum circuit lnn conversion. In: IARIA Ninth International Conference on Quantum, Nano/Bio, and MicroTechnologies—ICQNM2015 (2015)
[5] Beals, R., Brierley, S., Gray, O., Harrow, A.W., Kutin, S., Linden, N., Shepherd, D., Stather, M.: Efficient distributed quantum computing. In: Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 469, p. 20120686. The Royal Society (2013) · Zbl 1371.81074
[6] Cheung, D., Maslov, D., Severini, S.: Translation techniques between quantum circuit architectures. In: Workshop on Quantum Information Processing. Citeseer (2007)
[7] Córcoles, A., Magesan, E., Srinivasan, S.J., Cross, A.W., Steffen, M., Gambetta, J.M., Chow, J.M.: Demonstration of a quantum error detection code using a square lattice of four superconducting qubits. Nat. Commun. 6, 6979 (2015). doi:10.1038/ncomms7979
[8] Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Trans. Evol. Comput. 6(2), 182-197 (2002) · doi:10.1109/4235.996017
[9] Fowler, A., Devitt, S., Hollenberg, L.: Implementation of shor’s algorithm on a linear nearest neighbour qubit array. Quantum Inf. Comput. 4(quant-ph/0402196), 237-251 (2004) · Zbl 1175.81053
[10] Frutos, L., Baran, B.: State of the art in the conversion of quantum circuits to the lnn architecture. In: IEEE ARANDUCON2012 (2012)
[11] Garigipati, R.C., Kumar, P.: Implementing gate operations between uncoupled qubits in linear nearest neighbor arrays using a learning algorithm. Quantum Inf. Process. 12(7), 2291-2308 (2013) · Zbl 1270.81060 · doi:10.1007/s11128-013-0526-8
[12] Goldberg, D.E.: Genetic Algorithms. Pearson Education India (2006)
[13] Häffner, H., Hänsel, W., Roos, C., Benhelm, J., Chwalla, M., Körber, T., Rapol, U., Riebe, M., Schmidt, P., Becher, C., et al.: Scalable multiparticle entanglement of trapped ions. Nature 438(7068), 643-646 (2005) · doi:10.1038/nature04279
[14] Hirata, Y., Nakanishi, M., Yamashita, S., Nakashima, Y.: 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, 2009. ICQNM’09, pp. 26-33. IEEE (2009)
[15] Jones, N.C., Van Meter, R., Fowler, A.G., McMahon, P.L., Kim, J., Ladd, T.D., Yamamoto, Y.: Layered architecture for quantum computing. Phys. Rev. X 2(3), 031007 (2012)
[16] Kumar, P.: Efficient quantum computing between remote qubits in linear nearest neighbor architectures. Quantum Inf. Process. 12(4), 1737-1757 (2013) · Zbl 1267.81115 · doi:10.1007/s11128-012-0485-5
[17] Kumph, M., Brownnutt, M., Blatt, R.: Two-dimensional arrays of radio-frequency ion traps with addressable interactions. New J. Phys. 13(7), 3043 (2011) · doi:10.1088/1367-2630/13/7/073043
[18] Lin, C.C., Sur-Kolay, S., Jha, N.K.: Paqcs: physical design-aware fault-tolerant quantum circuit synthesis. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 23(7), 1221-1234 (2015) · doi:10.1109/TVLSI.2014.2337302
[19] von Lücken, C., Barán, B., Brizuela, C.: A survey on multi-objective evolutionary algorithms for many-objective problems. Comput. Optim. Appl. 58(3), 707-756 (2014) · Zbl 1334.90219
[20] Lye, A., Wille, R., Drechsler, R.: Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits. In: 2015 20th Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 178-183. IEEE (2015)
[21] Maslov, D., Dueck, G.W.: Improved quantum cost for n-bit toffoli gates. arXiv preprint quant-ph/0403053 (2004)
[22] Matsuo, A., Yamashita, S.: Changing the gate order for optimal lnn conversion. In: Reversible Computation, pp. 89-101. Springer, Berlin (2012) · Zbl 1451.81147
[23] Meza, E., Fernandez, J., Baran, B., Lima, J.: A parallel approach to convert quantum circuits to an lnn architecture. In: IARIA Ninth International Conference on Quantum, Nano/Bio, and MicroTechnologies—ICQNM2015 (2015)
[24] Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2010) · Zbl 1288.81001 · doi:10.1017/CBO9780511976667
[25] Ohliger, M., Eisert, J.: Efficient measurement-based quantum computing with continuous-variable systems. Phys. Rev. A 85(6), 062318 (2012) · doi:10.1103/PhysRevA.85.062318
[26] Petit, J.: Experiments on the minimum linear arrangement problem. J. Exp. Algorithm. (JEA) 8, 2-3 (2003) · Zbl 1069.90117
[27] Riquelme, N., Von Lücken, C., Baran, B.: Performance metrics in multi-objective optimization. In: Computing Conference (CLEI), 2015 Latin American, pp. 1-11. IEEE (2015)
[28] Ruffinelli, D., Baran, B.: A multiobjective approach to linear nearest neighbor optimization for 2d quantum circuits. In: CLEI 2016 (Latin American Conference on Informatics)—Latin American Symposium on Infrastructure, Hardware and Software (SLIHS’2016) (2016) · Zbl 1387.81171
[29] Saeedi, M., Shafaei, A., Pedram, M.: Constant-factor optimization of quantum adders on 2d quantum architectures. In: International Conference on Reversible Computation, pp. 58-69. Springer, Berlin (2013) · Zbl 1407.68188
[30] Saeedi, M., Wille, R., Drechsler, R.: Synthesis of quantum circuits for linear nearest neighbor architectures. Quantum Inf. Process. 10(3), 355-377 (2011) · Zbl 1216.81052 · doi:10.1007/s11128-010-0201-2
[31] Saeedi, M., Zamani, M.S., Sedighi, M., Sasanian, Z.: Reversible circuit synthesis using a cycle-based approach. ACM J. Emerg. Technol. Comput. Syst. (JETC) 6(4), 13 (2010)
[32] Sasanian, Z., Wille, R., Miller, D.M.: Realizing reversible circuits using a new class of quantum gates. In: Proceedings of the 49th Annual Design Automation Conference, pp. 36-41. ACM, New York (2012)
[33] Shafaei, A., Saeedi, M., Pedram, M.: Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures. In: Proceedings of the 50th Annual Design Automation Conference, p. 41. ACM, New York (2013) · Zbl 1407.68188
[34] Shafaei, A., Saeedi, M., Pedram, M.: Qubit placement to minimize communication overhead in 2d quantum architectures. In: 2014 19th Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 495-500. IEEE (2014)
[35] Shrivastwa, R.R., Datta, K., Sengupta, I.: Fast qubit placement in 2d architecture using nearest neighbor realization. In: 2015 IEEE International Symposium on Nanoelectronic and Information Systems, pp. 95-100. IEEE (2015)
[36] Soeken, M., Frehse, S., Wille, R., Drechsler, R.: Revkit: a toolkit for reversible circuit design. Multiple Valued Log. Soft Comput. 18(1), 55-65 (2012)
[37] Spedalieri, F.M., Roychowdhury, V.P.: Latency in local, two-dimensional, fault-tolerant quantum computing. arXiv preprint arXiv:0805.4213 (2008) · Zbl 1178.81046
[38] Strauch, F.W., Johnson, P.R., Dragt, A.J., Lobb, C., Anderson, J., Wellstood, F.: Quantum logic gates for coupled superconducting phase qubits. Phys. Rev. Lett. 91(16), 167005 (2003) · doi:10.1103/PhysRevLett.91.167005
[39] Takahashi, Y., Kunihiro, N., Ohta, K.: The quantum fourier transform on a linear nearest neighbor architecture. Quantum Inf. Comput. 7(4), 383-391 (2007) · Zbl 1152.81819
[40] Wille, R., Große, D., Teuber, L., Dueck, G.W., Drechsler, R.: Revlib: An online resource for reversible functions and reversible circuits. In: 38th International Symposium on Multiple Valued Logic, 2008. ISMVL 2008, pp. 220-225. IEEE (2008)
[41] Wille, R., Keszocze, O., Walter, M., Rohrs, P., Chattopadhyay, A., Drechsler, R.: Look-ahead schemes for nearest neighbor optimization of 1d and 2d quantum circuits. In: 2016 21st Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 292-297. IEEE (2016)
[42] Wille, R., Lye, A., Drechsler, R.: Exact reordering of circuit lines for nearest neighbor quantum architectures. IEEE Trans. Comput. Aided Design Integr. Circuits Syst. 33(12), 1818-1831 (2014) · doi:10.1109/TCAD.2014.2356463
[43] Wineland, D.J., Barrett, M., Britton, J., Chiaverini, J., DeMarco, B., Itano, W., Jelenković, B., Langer, C., Leibfried, D., Meyer, V., et al.: Quantum information processing with trapped ions. Philos. Trans. R. Soc. Lond. A Math. Phys. Eng. Sci. 361(1808), 1349-1361 (2003) · Zbl 1068.81526 · doi:10.1098/rsta.2003.1205
[44] Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans. Evol. Comput. 3(4), 257-271 (1999) · doi:10.1109/4235.797969
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.