Quantum approximate optimization algorithm for Bayesian network structure learning. (English) Zbl 1508.81538
Summary: Bayesian network structure learning is an NP-hard problem that has been faced by a number of traditional approaches in recent decades. Currently, quantum technologies offer a wide range of advantages that can be exploited to solve optimization tasks that cannot be addressed in an efficient way when utilizing classic computing approaches. In this work, a specific type of variational quantum algorithm, the quantum approximate optimization algorithm, was used to solve the Bayesian network structure learning problem, by employing \(3n(n-1)/2\) qubits, where \(n\) is the number of nodes in the Bayesian network to be learned. Our results showed that the quantum approximate optimization algorithm approach offers competitive results with state-of-the-art methods and quantitative resilience to quantum noise. The approach was applied to a cancer benchmark problem, and the results justified the use of variational quantum algorithms for solving the Bayesian network structure learning problem.
MSC:
| 81P68 | Quantum computation |
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
| 62F15 | Bayesian inference |
Keywords:
quantum approximate optimization algorithm; variational quantum algorithm; quantum optimization; Bayesian network structure learningReferences:
| [1] | Koller, D.; Friedman, N., Probabilistic graphical models: principles and techniques (2009), Cambridge: The MIT Press, Cambridge · Zbl 1183.68483 |
| [2] | Murphy, KP, Machine learning: a probabilistic perspective (2012), Cambridge: The MIT press, Cambridge · Zbl 1295.68003 |
| [3] | Bielza, C.; Larrañaga, P., Bayesian networks in neuroscience: a survey, Front. Comput. Neurosci., 8, 131 (2014) · Zbl 1322.68147 · doi:10.3389/fncom.2014.00131 |
| [4] | Puerto-Santana, C.; Larrañaga, P.; Bielza, C., Autoregressive asymmetric linear Gaussian hidden Markov models, IEEE Trans. Pattern Anal. Mach. Intell. (2021) · doi:10.1109/TPAMI.2021.3068799 |
| [5] | Chickering, DM, Learning bayesian networks is np-complete (1996), Springer, New York: Learning from Data, Springer, New York · doi:10.1007/978-1-4612-2404-4_12 |
| [6] | Robinson, RW, Counting unlabeled acyclic digraphs. combinatorial mathematics (1977), New York: Springer, New York · Zbl 0376.05031 |
| [7] | Aouay, S., Jamoussi, S., Ayed, Y.B.: Particle swarm optimization based method for Bayesian network structure learning. In: 2013 5th International Conference on Modeling, Simulation and Applied Optimization, pp. 1-6 (2013). doi:10.1109/ICMSAO.2013.6552569. IEEE |
| [8] | Quesada, D., Bielza, C., Larrañaga, P.: Structure learning of high-order dynamic Bayesian networks via particle swarm optimization with order invariant encoding. In: International Conference on Hybrid Artificial Intelligence Systems, pp. 158-171 (2021). doi:10.1007/978-3-030-86271-8_14. Springer |
| [9] | Blanco, R.; Inza, I.; Larrañaga, P., Learning Bayesian networks in the space of structures by estimation of distribution algorithms, Int. J. Intell. Syst., 18, 2, 205-220 (2003) · Zbl 1028.68162 · doi:10.1002/int.10084 |
| [10] | Larrañaga, P.; Poza, M.; Yurramendi, Y.; Murga, RH; Kuijpers, CMH, Structure learning of Bayesian networks by genetic algorithms: a performance analysis of control parameters, IEEE Trans. Pattern Anal. Mach. Intell., 18, 9, 912-926 (1996) · doi:10.1109/34.537345 |
| [11] | Lee, S.; Kim, SB, Parallel simulated annealing with a greedy algorithm for Bayesian network structure learning, IEEE Trans. Knowl. Data Eng., 32, 6, 1157-1166 (2019) · doi:10.1109/TKDE.2019.2899096 |
| [12] | Ji, J-Z; Zhang, H-X; Hu, R-B; Liu, C-N, A tabu-search based Bayesian network structure learning algorithm, J. Beijing Univ. Technol., 37, 1274-1280 (2011) |
| [13] | Scanagatta, M.; Salmerón, A.; Stella, F., A survey on Bayesian network structure learning from data, Progr. Artif. Intell., 8, 4, 425-439 (2019) · doi:10.1007/s13748-019-00194-y |
| [14] | Nielsen, MA; Chuang, I., Quantum computation and quantum information (2002), Washington DC: American Association of Physics Teachers, Washington DC |
| [15] | Hauke, P.; Katzgraber, HG; Lechner, W.; Nishimori, H.; Oliver, WD, Perspectives of quantum annealing: methods and implementations, Rep. Progr. Phys., 83, 5, 054401 (2020) · doi:10.1088/1361-6633/ab85b8 |
| [16] | O’Gorman, B.; Babbush, R.; Perdomo-Ortiz, A.; Aspuru-Guzik, A.; Smelyanskiy, V., Bayesian network structure learning using quantum annealing, Eur. Phys. J. Special Topics, 224, 1, 163-188 (2015) · doi:10.1140/epjst/e2015-02349-9 |
| [17] | Shikuri, Y.: Efficient conversion of Bayesian network learning into quadratic unconstrained binary optimization. http://arxiv.org/abs/2006.06926 (2020). doi:10.48550/arXiv.2006.06926 |
| [18] | Schuld, M.; Petruccione, F., Supervised learning with quantum computers (2018), New York: Springer, New York · Zbl 1411.81008 · doi:10.1007/978-3-319-96424-9 |
| [19] | McClean, JR; Romero, J.; Babbush, R.; Aspuru-Guzik, A., The theory of variational hybrid quantum-classical algorithms, J. Phys., 18, 2, 023023 (2016) · Zbl 1456.81149 · doi:10.1088/1367-2630/18/2/023023 |
| [20] | Peruzzo, A.; McClean, J.; Shadbolt, P.; Yung, M-H; Zhou, X-Q; Love, PJ; Aspuru-Guzik, A.; O’Brien, JL, A variational eigenvalue solver on a photonic quantum processor, Nat. Commun., 5, 1, 1-7 (2014) · doi:10.1038/ncomms5213 |
| [21] | Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm. http://arxiv.org/abs/1411.4028 (2014). doi:10.48550/arXiv.1411.4028 · Zbl 1213.68284 |
| [22] | Utkarsh, Behera, B.K., Panigrahi, P.K.: Solving vehicle routing problem using quantum approximate optimization algorithm. http://arxiv.org/abs/2002.01351 (2020). doi:10.48550/arXiv.2002.01351 |
| [23] | Choi, J., Kim, J.: A tutorial on quantum approximate optimization algorithm (QAOA): Fundamentals and Applications. In: 2019 International Conference on Information and Communication Technology Convergence, pp. 138-142 (2019). doi:10.1109/ICTC46691.2019.8939749. IEEE |
| [24] | Shaydulin, R., Alexeev, Y.: Evaluating quantum approximate optimization algorithm: A case study. In: 2019 Tenth International Green and Sustainable Computing Conference, pp. 1-6 (2019). doi:10.1109/IGSC48788.2019.8957201. IEEE |
| [25] | Fontana, E.; Fitzpatrick, N.; Ramo, DM; Duncan, R.; Rungger, I., Evaluating the noise resilience of variational quantum algorithms, Phys. Rev. A, 104, 2, 022403 (2021) · doi:10.1103/PhysRevA.104.022403 |
| [26] | Verdon, G., Broughton, M., Biamonte, J.: A quantum algorithm to train neural networks using low-depth circuits. http://arxiv.org/abs/1712.05304 (2017). doi:10.48550/arXiv.1712.05304 |
| [27] | Streif, M., Leib, M.: Comparison of QAOA with quantum and simulated annealing. http://arxiv.org/abs/1901.01903 (2019). doi:10.48550/arXiv.1901.01903 |
| [28] | Xue, C.; Chen, Z-Y; Wu, Y-C; Guo, G-P, Effects of quantum noise on quantum approximate optimization algorithm, Chin. Phys. Lett., 38, 3, 030302 (2021) · doi:10.1088/0256-307X/38/3/030302 |
| [29] | Sharma, K.; Khatri, S.; Cerezo, M.; Coles, PJ, Noise resilience of variational quantum compiling, New J. Phys., 22, 4, 043006 (2020) · doi:10.1088/1367-2630/ab784c |
| [30] | Schwarz, G., Estimating the dimension of a model, Annal. Stat., 25, 461-464 (1978) · Zbl 0379.62005 · doi:10.1214/aos/1176344136 |
| [31] | Cooper, GF; Herskovits, E., A Bayesian method for the induction of probabilistic networks from data, Mach. Learn., 9, 4, 309-347 (1992) · Zbl 0766.68109 · doi:10.1007/BF00994110 |
| [32] | Heckerman, D.; Geiger, D.; Chickering, DM, Learning Bayesian networks: the combination of knowledge and statistical data, Mach. Learn., 20, 3, 197-243 (1995) · Zbl 0831.68096 · doi:10.1023/A:1022623210503 |
| [33] | Farhi, E., Goldstone, J., Gutmann, S.: Quantum adiabatic evolution algorithms with different paths. quant-ph/0208135 (2002). doi:10.48550/arXiv.quant-ph/0208135 · Zbl 1187.81063 |
| [34] | Aleksandrowicz, G., Alexander, T., Barkoutsos, P., Bello, L., Ben-Haim, Y., Bucher, D., Cabrera-Hernández, F.J., Carballo-Franquis, J., Chen, A., Chen, C.-F., et al.: Qiskit: An open-source framework for quantum computing (2021). doi:10.5281/zenodo.2573505 |
| [35] | ATOS: Quantum learning machine. https://atos.net/en/solutions/quantum-learning-machine. [Online; Accessed 26-January-2022] (2021) |
| [36] | Acerbi, C.; Tasche, D., On the coherence of expected shortfall, J. Bank. Financ., 26, 7, 1487-1503 (2002) · doi:10.1016/S0378-4266(02)00283-2 |
| [37] | Barkoutsos, PK; Nannicini, G.; Robert, A.; Tavernelli, I.; Woerner, S., Improving variational quantum optimization using CVaR, Quantum, 4, 256 (2020) · doi:10.22331/q-2020-04-20-256 |
| [38] | De Jong, K.: Evolutionary computation: A unified approach. In: Proceedings of the 2016 Genetic and Evolutionary Computation Conference Companion, pp. 185-199. The MIT Press, Cambridge (2016). doi:10.1007/s10710-007-9035-9 |
| [39] | Larrañaga, P.; Lozano, JA, Estimation of distribution algorithms: a new tool for evolutionary computation (2001), New York: Springer, New York · Zbl 0979.00024 |
| [40] | Powell, MJ, A direct search optimization method that models the objective and constraint functions by linear interpolation. in: advances in optimization and numerical analysis (1994), New York: Springer, New York · doi:10.1007/978-94-015-8330-5_4 |
| [41] | Bonet-Monroig, X., Wang, H., Vermetten, D., Senjean, B., Moussa, C., Bäck, T., Dunjko, V., O’Brien, T.E.: Performance comparison of optimization methods on variational quantum algorithms. http://arxiv.org/abs/2111.13454 (2021). doi:10.48550/arXiv.2111.13454 |
| [42] | Urbanek, M., Nachman, B., Pascuzzi, V.R., He, A., Bauer, C.W., de Jong, W.A.: Mitigating depolarizing noise on quantum computers with noise-estimation circuits. http://arxiv.org/abs/2103.08591 (2021). doi:10.1103/PhysRevLett.127.270502 |
| [43] | Kandala, A.; Temme, K.; Córcoles, AD; Mezzacapo, A.; Chow, JM; Gambetta, JM, Error mitigation extends the computational reach of a noisy quantum processor, Nature, 567, 7749, 491-495 (2019) · doi:10.1038/s41586-019-1040-7 |
| [44] | Sun, J.; Yuan, X.; Tsunoda, T.; Vedral, V.; Benjamin, SC; Endo, S., Mitigating realistic noise in practical noisy intermediate-scale quantum devices, Phys. Rev. Appl., 15, 3, 034026 (2021) · doi:10.1103/PhysRevApplied.15.034026 |
| [45] | Vovrosh, J.; Khosla, KE; Greenaway, S.; Self, C.; Kim, M.; Knolle, J., Simple mitigation of global depolarizing errors in quantum simulations, Phys. Rev. E, 104, 3, 035309 (2021) · doi:10.1103/PhysRevE.104.035309 |
| [46] | Henrion, M., Propagating uncertainty in Bayesian networks by probabilistic logic sampling. In: machine intelligence and pattern recognition (1988), Amsterdam: Elsevier, Amsterdam · Zbl 0649.68095 · doi:10.1016/B978-0-444-70396-5.50019-4 |
| [47] | Gámez, JA; Mateo, J.; Puerta, JM, Learning Bayesian networks by hill climbing: Efficient methods based on progressive restriction of the neighborhood, Data Min. Knowl. Discov., 22, 106-148 (2011) · Zbl 1235.68152 · doi:10.1007/s10618-010-0178-6 |
| [48] | Tsamardinos, I.; Brown, LE; Aliferis, CF, The max-min hill-climbing Bayesian network structure learning algorithm, Mach. Learn., 65, 1, 31-78 (2006) · Zbl 1470.68192 · doi:10.1007/s10994-006-6889-7 |
| [49] | Egger, DJ; Mareček, J.; Woerner, S., Warm-starting quantum optimization, Quantum, 5, 479 (2021) · doi:10.22331/q-2021-06-17-479 |
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.
