×

A novel ant colony optimization strategy for the quantum circuit compilation problem. (English) Zbl 1474.68322

Zarges, Christine (ed.) et al., Evolutionary computation in combinatorial optimization. 21st European conference, EvoCOP 2021, held as part of EvoStar 2021, virtual event, April 7–9, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12692, 1-16 (2021).
Summary: Quantum Computing represents the most promising technology towards speed boost in computation, opening the possibility of major breakthroughs in several disciplines including Artificial Intelligence. This paper investigates the performance of a novel Ant Colony Optimization (ACO) algorithm for the realization (compilation) of nearest-neighbor compliant quantum circuits of minimum duration. In fact, current technological limitations (e.g., decoherence effect) impose that the overall duration (makespan) of the quantum circuit realization be minimized, and therefore the production of minimum-makespan compiled circuits for present and future quantum machines is of paramount importance. In our ACO algorithm (QCC-ACO), we introduce a novel pheromone model, and we leverage a heuristic-based Priority Rule to control the iterative selection of the quantum gates to be inserted in the solution.
The proposed QCC-ACO algorithm has been tested on a set of quantum circuit benchmark instances of increasing sizes available from the recent literature. We demonstrate that the QCC-ACO obtains results that outperform the current best solutions in the literature against the same benchmark, succeeding in significantly improving the makespan values for a great number of instances and demonstrating the scalability of the approach.
For the entire collection see [Zbl 1471.68024].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W50 Evolutionary algorithms, genetic algorithms (computational aspects)
81P65 Quantum gates
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baioletti, M., Milani, A., Poggioni, V., Rossi, F.: Experimental evaluation of pheromone models in ACOPlan. Ann. Math. Artif. Intell. 62(3), 187-217 (2011). doi:10.1007/s10472-011-9265-7 · Zbl 1253.68294
[2] Baioletti, M.; Milani, A.; Santucci, V.; Shi, Y., A new precedence-based ant colony optimization for permutation problems, Simulated Evolution and Learning, 960-971 (2017), Cham: Springer, Cham · doi:10.1007/978-3-319-68759-9_79
[3] Booth, K.E.C., 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 \(28^{th}\) International Conference on Automated Planning & Scheduling, ICAPS 2018, pp. 366-374 (2018)
[4] Brierley, S.: Efficient implementation of quantum circuits with limited qubit interactions. Quantum Inf. Comput. 17(13-14), 1096-1104 (2017). http://dl.acm.org/citation.cfm?id=3179575.3179577
[5] Chand, S., Singh, H.K., Ray, T., Ryan, M.: Rollout based heuristics for the quantum circuit compilation problem. In: 2019 IEEE Congress on Evolutionary Computation (CEC), pp. 974-981 (2019)
[6] Cirac, J.I., Zoller, P.: Quantum computations with cold trapped ions. Phys. Rev. Lett. 74, 4091-4094 (1995). doi:10.1103/PhysRevLett.74.4091
[7] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001) · Zbl 1047.68161
[8] Do, M., Wang, Z., O’Gorman, B., Venturelli, D., Rieffel, E., Frank, J.: Planning for compilation of a quantum algorithm for graph coloring. ArXiv abs/2002.10917 (2020)
[9] Dorigo, M.; Stützle, T., Ant Colony Optimization (2004), USA: Bradford Company, USA · Zbl 1092.90066 · doi:10.7551/mitpress/1290.001.0001
[10] Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028. November 2014 · Zbl 1213.68284
[11] Guerreschi, G.G., Park, J.: Gate scheduling for quantum algorithms. arXiv preprint arXiv:1708.00023, July 2017
[12] Hart, J.; Shogan, A., Semi-greedy heuristics: an empirical study, Oper. Res. Lett., 6, 107-114 (1987) · Zbl 0615.90082 · doi:10.1016/0167-6377(87)90021-6
[13] Herrera-Martí, D.A., Fowler, A.G., Jennings, D., Rudolph, T.: Photonic implementation for the topological cluster-state quantum computer. Phys. Rev. A 82, 032332 (2010). doi:10.1103/PhysRevA.82.032332
[14] Merkle, D.; Merkle, M.; Schmeck, H., Ant colony optimization for resource-constrained project scheduling, IEEE Trans. Evol. Comput., 6, 4, 333-346 (2002) · doi:10.1109/TEVC.2002.802450
[15] Nau, D.; Ghallab, M.; Traverso, P., Automated Planning: Theory & Practice (2004), San Francisco: Morgan Kaufmann Publishers Inc., San Francisco · Zbl 1074.68613
[16] Nielsen, MA; Chuang, IL, Quantum Computation and Quantum Information: 10th Anniversary Edition (2011), New York: Cambridge University Press, New York · Zbl 1288.81001
[17] Oddi, A.; Rasconi, R.; van Hoeve, W-J, Greedy randomized search for scalable compilation of quantum circuits, Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 446-461 (2018), Cham: Springer, Cham · Zbl 1508.68341 · doi:10.1007/978-3-319-93031-2_32
[18] 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, pp. 7707-7714. AAAI Press (2019)
[19] Resende, M.G., Werneck, R.F.: A hybrid heuristic for the p-median problem. J. Heuristics 10(1), 59-88 (2004). doi:10.1023/B:HEUR.0000019986.96257.50 · Zbl 1069.68600
[20] Sete, E.A., Zeng, W.J., Rigetti, C.T.: A functional architecture for scalable quantum computing. In: 2016 IEEE International Conference on Rebooting Computing (ICRC), pp. 1-6, October 2016. doi:10.1109/ICRC.2016.7738703
[21] Stützle, T.: An ant approach to the flow shop problem. In: Proceedings of the 6th European Congress on Intelligent Techniques & Soft Computing, EUFIT 1998, Aachen, Germany, pp. 1560-1564 (1998)
[22] 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 2017, pp. 4440-4446 (2017). doi:10.24963/ijcai.2017/620
[23] Yao, N.Y., et al.: Quantum logic between remote quantum registers. Phys. Rev. A 87, 022306 (2013). doi:10.1103/PhysRevA.87.022306
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.