Analyzing Heuristic-based Randomized Search Strategies for the Quantum Circuit Compilation Problem

• Autorzy: Oddi Angelo , Rasconi Riccardo

Identyfikatory

DOI

10.3233/FI-2020-1942

• Języki publikacji: EN

Abstrakty

EN

In this work we investigate the performance of greedy randomised search (GRS) techniques to the problem of compiling quantum circuits to emerging quantum hardware. Quantum computing (QC) represents the next big step towards power consumption minimisation and CPU speed boost in the future of computing machines. Quantum computing uses quantum gates that manipulate multi-valued bits (qubits ). A quantum circuit is composed of a number of qubits and a series of quantum gates that operate on those qubits, and whose execution realises a specific quantum algorithm. Current quantum computing technologies limit the qubit interaction distance allowing the execution of gates between adjacent qubits only. This has opened the way to the exploration of possible techniques aimed at guaranteeing nearest-neighbor (NN) compliance in any quantum circuit through the addition of a number of so-called swap gates between adjacent qubits. In addition, technological limitations (decoherence effect) impose that the overall duration (makespan) of the quantum circuit realization be minimized. One core contribution of the paper is the definition of two lexicographic ranking functions for quantum gate selection, using two keys: one key acts as a global closure metric to minimise the solution makespan; the second one is a local metric, which favours the mutual approach of the closest qstates pairs. We present a GRS procedure that synthesises NN-compliant quantum circuits realizations, starting from a set of benchmark instances of different size belonging to the Quantum Approximate Optimization Algorithm (QAOA) class tailored for the MaxCut problem. We propose a comparison between the presented meta-heuristics and the approaches used in the recent literature against the same benchmarks, both from the CPU efficiency and from the solution quality standpoint. In particular, we compare our approach against a reference benchmark initially proposed and subsequently expanded in [1] by considering: (i) variable qubit state initialisation and (ii) crosstalk constraints that further restrict parallel gate execution.

Słowa kluczowe

EN

greedy heuristics; optimization; planning; quantum computing; random algorithms; scheduling

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 174, nr 3/4
• Strony: 259--281
• Opis fizyczny: Bibliogr. 26 poz., rys., tab., wykr.

Twórcy

autor

Oddi Angelo

• ISTC-CNR, Via San Martino della Battaglia, 44, 00185 Rome, Italy

autor

Rasconi Riccardo

• ISTC-CNR, Via San Martino della Battaglia, 44, 00185 Rome, Italy

Bibliografia

• [1] Booth KEC, Do M, Beck C, Rieffel E, Venturelli D, Frank J. Comparing and Integrating Constraint Programming and Temporal Planning for Quantum Circuit Compilation. In: Proceedings of the 28th International Conference on Automated Planning & Scheduling, ICAPS-18. 2018 pp. 366-374.
• [2] Hart J, Shogan A. Semi-greedy heuristics: An empirical study. Operations Research Letters, 1987. 6:107-114.
• [3] Resende MG, Werneck RF. A Hybrid Heuristic for the p-Median Problem. Journal of Heuristics, 2004. 10(1):59-88. doi:10.1023/B:HEUR.0000019986.96257.50. URL https://doi.org/10.1023/B:HEUR.0000019986.96257.50.
• [4] Oddi A, Smith S. Stochastic Procedures for Generating Feasible Schedules. In: Proceedings 14th National Conference on AI (AAAI-97). 1997 pp. 308-314.
• [5] Nielsen MA, Chuang IL. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, New York, NY, USA, 10th edition, 2011. ISBN 1107002176, 9781107002173.
• [6] Cirac JI, Zoller P. Quantum Computations with Cold Trapped Ions. Phys. Rev. Lett., 1995. 74:4091-4094. doi:10.1103/PhysRevLett.74.4091. URL https://link.aps.org/doi/10.1103/PhysRevLett.74.4091.
• [7] Herrera-Martí DA, Fowler AG, Jennings D, Rudolph T. Photonic implementation for the topological cluster-state quantum computer. Phys. Rev. A, 2010. 82:032332. doi:10.1103/PhysRevA.82.032332. URL https://link.aps.org/doi/10.1103/PhysRevA.82.032332.
• [8] Yao NY, Gong ZX, Laumann CR, Bennett SD, Duan LM, Lukin MD, Jiang L, Gorshkov AV. Quantum logic between remote quantum registers. Phys. Rev. A, 2013. 87:022306. doi:10.1103/PhysRevA.87.022306. URL https://link.aps.org/doi/10.1103/PhysRevA.87.022306.
• [9] Brierley S. Efficient Implementation of Quantum Circuits with Limited Qubit Interactions. Quantum Info. Comput., 2017. 17(13-14):1096-1104. URL http://dl.acm.org/citation.cfm?id=3179575.3179577.
• [10] Farhi E, Goldstone J, Gutmann S. A Quantum Approximate Optimization Algorithm. arXiv preprint arXiv:1411.4028, 2014.
• [11] Guerreschi GG, Park J. Gate scheduling for quantum algorithms. arXiv preprint arXiv:1708.00023, 2017.
• [12] Sete EA, Zeng WJ, Rigetti CT. A functional architecture for scalable quantum computing. In: 2016 IEEE International Conference on Rebooting Computing (ICRC). 2016 pp. 1-6. doi:10.1109/ICRC.2016.7738703.
• [13] Venturelli D, Do M, Rieffel E, Frank J. Temporal Planning for Compilation of Quantum Approximate Optimization Circuits. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17. 2017 pp. 4440-4446. doi:10.24963/ijcai.2017/620. URL https://doi.org/10.24963/ijcai.2017/620.
• [14] Oddi A, Rasconi R. Greedy Randomized Search for Scalable Compilation of Quantum Circuits. In: van Hoeve WJ (ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer International Publishing, Cham. ISBN 978-3-319-93031-2, 2018 pp. 446-461.
• [15] Maslov D, Falconer SM, Mosca M. Quantum Circuit Placement: Optimizing Qubit-to-qubit Interactions Through Mapping Quantum Circuits into a Physical Experiment. In: Proceedings of the 44th Annual Design Automation Conference, DAC ’07. ACM, New York, NY, USA. ISBN 978-1-59593-627-1, 2007 pp. 962-965. doi:10.1145/1278480.1278717. URL http://doi.acm.org/10.1145/1278480.1278717.
• [16] Fox M, Long D. PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains. J. Artif. Int. Res., 2003. 20(1):61-124. URL http://dl.acm.org/citation.cfm?id=1622452.1622454.
• [17] Nau D, Ghallab M, Traverso P. Automated Planning: Theory & Practice. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2004. ISBN 1558608567.
• [18] Kole A, Datta K, Sengupta I. A Heuristic for Linear Nearest Neighbor Realization of Quantum Circuits by SWAP Gate Insertion Using N-Gate Lookahead. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2016. 6(1):62-72. doi:10.1109/JETCAS.2016.2528720.
• [19] Kole A, Datta K, Sengupta I. A New Heuristic for N -Dimensional Nearest Neighbor Realization of a Quantum Circuit. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018. 37(1):182-192. doi:10.1109/TCAD.2017.2693284.
• [20] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. MIT Press, second edition, 2001.
• [21] Gomes CP, Selman B, Kautz H. Boosting Combinatorial Search Through Randomization. In: Proceedings of the Fifteenth National/Tenth Conference on Artificial Intelligence/Innovative Applications of Artificial Intelligence, AAAI ’98/IAAI ’98. American Association for Artificial Intelligence, Menlo Park, CA, USA. ISBN 0-262-51098-7, 1998 pp. 431-437. URL http://dl.acm.org/citation.cfm?id=295240.295710.
• [22] Eyerich P, Mattmüller R, Röger G. Using the Context-enhanced Additive Heuristic for Temporal and Numeric Planning. In: Proceedings of the 19th International Conference on Automated Planning and Scheduling, ICAPS 2009, Thessaloniki, Greece, September 19-23, 2009. 2009 pp. 130-137. URL http://aaai.org/ocs/index.php/ICAPS/ICAPS09/paper/view/742.
• [23] Wah BW, Chen Y. Subgoal Partitioning and Global Search for Solving Temporal Planning Problems in Mixed Space. International Journal on Artificial Intelligence Tools, 2004. 13(04):767-790. doi:10.1142/S0218213004001806. http://www.worldscientific.com/doi/pdf/10.1142/S0218213004001806, URL http://www.worldscientific.com/doi/abs/10.1142/S0218213004001806.
• [24] Chen Y, Wah BW, Hsu CW. Temporal Planning Using Subgoal Partitioning and Resolution in SGPlan. J. Artif. Int. Res., 2006. 26(1):323-369. URL http://dl.acm.org/citation.cfm?id=1622559.1622568.
• [25] Gerevini A, Saetti A, Serina I. Planning Through Stochastic Local Search and Temporal Action Graphs in LPG. J. Artif. Int. Res., 2003. 20(1):239-290. URL http://dl.acm.org/citation.cfm?id=1622452.1622462.
• [26] Rasconi R, Oddi A. An Innovative Genetic Algorithm for the Quantum Circuit Compilation Problem. In: Proceeding of the Thirty-Third Conference on Artificial Intelligence AAAI-2019. AAAI Press, 2019 pp. 7707-7714.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).