Skip to main content

Advertisement

Springer Nature Link
Log in

Evaluating the practicality of quantum optimization algorithms for prototypical industrial applications

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

The optimization of the power consumption of antenna networks is a problem with a potential impact in the field of telecommunications. In this work, we investigate the application of the quantum approximate optimization algorithm (QAOA) and the quantum adiabatic algorithm (QAA), to the solution of a prototypical model in this field. We use state vector emulation in a high-performance computing environment to compare the performance of these two algorithms in terms of solution quality, using selected evaluation metrics. We estimate the circuit depth scaling with the problem size while maintaining a certain level of solution quality, and we extend our analysis up to 31 qubits, which is rarely addressed in the literature. Our calculations show that as the problem size increases, the probability of measuring the exact solution decreases exponentially for both algorithms. This issue is particularly severe when we include constraints in the problem, resulting in full connectivity between the sites. Nonetheless, we observe that the cumulative probability of measuring solutions close to the optimal one remains high also for the largest instances considered in this work. Our findings keep the way open to the application of these algorithms, or variants thereof, to generate suboptimal solutions at scales relevant to industrial use cases.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Kochenberger, G., Hao, J.-K., Glover, F., Lewis, M., Lü, Z., Wang, H., Wang, Y.: The unconstrained binary quadratic programming problem: a survey. J. Comb. Optim. 28(1), 58–81 (2014). https://doi.org/10.1007/s10878-014-9734-0

    Article  MathSciNet  Google Scholar 

  2. Lucas, A.: Ising formulations of many NP problems. Front. Phys. (2014). https://doi.org/10.3389/fphy.2014.00005

    Article  Google Scholar 

  3. Lodewijks, B.: Mapping np-hard and np-complete optimisation problems to quadratic unconstrained binary optimisation problems (2020) arXiv:1911.08043 [cs.DS]

  4. Barahona, F.: On the computational complexity of Ising spin glass models. J. Phys. A Math. Gen. 15(10), 3241 (1982). https://doi.org/10.1088/0305-4470/15/10/028

    Article  ADS  MathSciNet  Google Scholar 

  5. Farhi, E., Harrow, A.W.: Quantum supremacy through the quantum approximate optimization algorithm (2019) arXiv:1602.07674 [quant-ph]

  6. Guerreschi, G.G., Matsuura, A.Y.: Qaoa for max-cut requires hundreds of qubits for quantum speed-up. Sci. Rep. 9(1), 6903 (2019). https://doi.org/10.1038/s41598-019-43176-9

    Article  ADS  Google Scholar 

  7. MacQuarrie, E.R., Simon, C., Simmons, S., Maine, E.: The emerging commercial landscape of quantum computing. Nat. Rev. Phys. 2(11), 596–598 (2020). https://doi.org/10.1038/s42254-020-00247-5

    Article  Google Scholar 

  8. Wurtz, J., Love, P.: Maxcut quantum approximate optimization algorithm performance guarantees for \(p > 1\). Phys. Rev. A 103, 042612 (2021). https://doi.org/10.1103/PhysRevA.103.042612

    Article  ADS  MathSciNet  Google Scholar 

  9. Farhi, E., Goldstone, J., Gutmann, S., Zhou, L.: The Quantum approximate optimization algorithm and the Sherrington–Kirkpatrick model at infinite size. Quantum 6, 759 (2022) https://doi.org/10.22331/q-2022-07-07-759

  10. Zhou, L., Wang, S.-T., Choi, S., Pichler, H., Lukin, M.D.: Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices. Phys. Rev. X 10, 021067 (2020). https://doi.org/10.1103/PhysRevX.10.021067

    Article  Google Scholar 

  11. Koßmann, G., Binkowski, L., Luijk, L., Ziegler, T., Schwonnek, R.: Deep-circuit QAOA (2023) arXiv:2210.12406 [quant-ph]

  12. Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355–5363 (1998). https://doi.org/10.1103/PhysRevE.58.5355

    Article  ADS  Google Scholar 

  13. Johnson, M.W., Amin, M.H.S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A.J., Johansson, J., Bunyk, P., Chapple, E.M., Enderud, C., Hilton, J.P., Karimi, K., Ladizinsky, E., Ladizinsky, N., Oh, T., Perminov, I., Rich, C., Thom, M.C., Tolkacheva, E., Truncik, C.J.S., Uchaikin, S., Wang, J., Wilson, B., Rose, G.: Quantum annealing with manufactured spins. Nature 473(7346), 194–198 (2011). https://doi.org/10.1038/nature10012

    Article  ADS  Google Scholar 

  14. Boixo, S., Rønnow, T.F., Isakov, S.V., Wang, Z., Wecker, D., Lidar, D.A., Martinis, J.M., Troyer, M.: Evidence for quantum annealing with more than one hundred qubits. Nat. Phys. 10(3), 218–224 (2014). https://doi.org/10.1038/nphys2900

    Article  Google Scholar 

  15. Smelyanskiy, V.N., Rieffel, E.G., Knysh, S.I., Williams, C.P., Johnson, M.W., Thom, M.C., Macready, W.G., Pudenz, K.L.: A Near-term quantum computing approach for hard computational problems in space exploration (2012) arXiv:1204.2821 [quant-ph]

  16. Rieffel, E.G., Venturelli, D., O’Gorman, B., Do, M.B., Prystay, E.M., Smelyanskiy, V.N.: A case study in programming a quantum Annealer for hard operational planning problems. Quantum Inf. Process. 14(1), 1–36 (2015). https://doi.org/10.1007/s11128-014-0892-x

    Article  ADS  Google Scholar 

  17. Venturelli, D., Marchand, D.J.J., Rojo, G.: Quantum annealing implementation of job-shop scheduling (2016) arXiv:1506.08479 [quant-ph]

  18. Clark, J., West, T., Zammit, J., Guo, X., Mason, L., Russell, D.: Towards real time multi-robot routing using quantum computing technologies. In: Proceedings of the International Conference on High Performance Computing in Asia-Pacific Region. HPC Asia 2019, pp. 111–119. Association for Computing Machinery, New York (2019). https://doi.org/10.1145/3293320.3293333

  19. Stollenwerk, T., O’Gorman, B., Venturelli, D., Mandra, S., Rodionova, O., Ng, H., Sridhar, B., Rieffel, E.G., Biswas, R.: Quantum annealing applied to de-conflicting optimal trajectories for air traffic management. IEEE Trans. Intell. Transp. Syst. 21(1), 285–297 (2020). https://doi.org/10.1109/tits.2019.2891235

    Article  Google Scholar 

  20. Yarkoni, S., Raponi, E., BÃck, T., Schmitt, S.: Quantum annealing for industry applications: introduction and review. Reports on Progress in Physics 85(10), 104001 (2022) https://doi.org/10.1088/1361-6633/ac8c54

  21. Domino, K., Kundu, A., Salehi, K.K.: Quadratic and higher-order unconstrained binary optimization of railway rescheduling for quantum computing. Quantum Inform. Process. (2022). https://doi.org/10.1007/s11128-022-03670-y

    Article  MathSciNet  Google Scholar 

  22. Guillaume, A., Goh, E.Y., Johnston, M.D., Wilson, B.D., Ramanan, A., Tibble, F., Lackey, B.: Deep space network scheduling using quantum annealing. IEEE Trans. Quantum Eng. 3, 1–13 (2022). https://doi.org/10.1109/TQE.2022.3199267

    Article  Google Scholar 

  23. Wilson, B., Goh, E., Guillaume, A., Alimo, R., Claudet, T., Venkataram, H.: Automating antenna scheduling problems using quantum computing and deep reinforcement learning. In: IGARSS 2022–2022 IEEE International Geoscience and Remote Sensing Symposium, pp. 4915–4918 (2022). https://doi.org/10.1109/IGARSS46834.2022.9884342

  24. Colucci, G., Linde, S., Phillipson, F.: Power network optimization: A quantum approach. IEEE Access, pp. 1–1 (2023) https://doi.org/10.1109/ACCESS.2023.3312997

  25. Jing, H., Wang, Y., Li, Y.: Data-driven quantum approximate optimization algorithm for power systems. Commun. Eng. 2(1), 12 (2023). https://doi.org/10.1038/s44172-023-00061-8

    Article  Google Scholar 

  26. Stollenwerk, T., Hadfield, S., Wang, Z.: Toward quantum gate-model heuristics for real-world planning problems. IEEE Trans. Quantum Eng. 1, 1–16 (2020)

    Article  Google Scholar 

  27. Leonidas, I.D., Dukakis, A., Tan, B., Angelakis, D.G.: Qubit efficient quantum algorithms for the vehicle routing problem on quantum computers of the NISQ era (2023) arXiv:2306.08507 [quant-ph]

  28. Quetschlich, N., Koch, V., Burgholzer, L., Wille, R.: A hybrid classical quantum computing approach to the satellite mission planning problem (2023) arXiv:2308.00029 [quant-ph]

  29. Rainjonneau, S., Tokarev, I., Iudin, S., Rayaprolu, S., Pinto, K., Lemtiuzhnikova, D., Koblan, M., Barashov, E., Kordzanganeh, M., Pflitsch, M., Melnikov, A.: Quantum algorithms applied to satellite mission planning for earth observation. IEEE J. Selected Topics Appl. Earth Observ. Remote Sensing 16, 7062–7075 (2023). https://doi.org/10.1109/jstars.2023.3287154

    Article  ADS  Google Scholar 

  30. Carreras-Coch, A., Navarro, J., Sans, C., Zaballos, A.: Communication technologies in emergency situations. Electronics (2022). https://doi.org/10.3390/electronics11071155

    Article  Google Scholar 

  31. Mozaffari, M., Saad, W., Bennis, M., Debbah, M.: Efficient deployment of multiple unmanned aerial vehicles for optimal wireless coverage. IEEE Commun. Lett. 20(8), 1647–1650 (2016). https://doi.org/10.1109/LCOMM.2016.2578312

    Article  Google Scholar 

  32. Sun, J., Wang, W., Li, S., Da, Q., Chen, L.: Scheduling optimization for UAV communication coverage using virtual force-based PSO model. Digit. Commun. Netw. (2023). https://doi.org/10.1016/j.dcan.2023.01.007

    Article  Google Scholar 

  33. Barahona, F., Grötschel, M., Jünger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36(3), 493–513 (1988). https://doi.org/10.1287/opre.36.3.493

    Article  Google Scholar 

  34. Yoshioka, T., Sasada, K., Nakano, Y., Fujii, K.: Fermionic quantum approximate optimization algorithm. Phys. Rev. Res. 5, 023071 (2023). https://doi.org/10.1103/PhysRevResearch.5.023071

    Article  Google Scholar 

  35. Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm (2014) arXiv:1411.4028 [quant-ph]

  36. Yuan, X., Endo, S., Zhao, Q., Li, Y., Benjamin, S.C.: Theory of variational quantum simulation. Quantum 3, 191 (2019). https://doi.org/10.22331/q-2019-10-07-191

    Article  Google Scholar 

  37. Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S.C., Endo, S., Fujii, K., McClean, J.R., Mitarai, K., Yuan, X., Cincio, L., Coles, P.J.: Variational quantum algorithms. Nat. Rev. Phys. 3(9), 625–644 (2021). https://doi.org/10.1038/s42254-021-00348-9

    Article  Google Scholar 

  38. Larkin, J., Jonsson, M., Justice, D., Guerreschi, G.G.: Evaluation of QAOA based on the approximation ratio of individual samples. Quantum Sci. Technol. 7(4), 045014 (2022). https://doi.org/10.1088/2058-9565/ac6973

    Article  ADS  Google Scholar 

  39. Chai, Y., Han, Y.-J., Wu, Y.-C., Li, Y., Dou, M., Guo, G.-P.: Shortcuts to the quantum approximate optimization algorithm. Phys. Rev. A 105, 042415 (2022). https://doi.org/10.1103/PhysRevA.105.042415

    Article  ADS  Google Scholar 

  40. Morales, M.E.S., Biamonte, J.D., Zimborás, Z.: On the universality of the quantum approximate optimization algorithm. Quantum Inform. Process. (2020). https://doi.org/10.1007/s11128-020-02748-9

    Article  MathSciNet  Google Scholar 

  41. Akshay, V., Philathong, H., Morales, M.E.S., Biamonte, J.D.: Reachability deficits in quantum approximate optimization. Phys. Rev. Lett. 124, 090504 (2020). https://doi.org/10.1103/PhysRevLett.124.090504

    Article  ADS  MathSciNet  Google Scholar 

  42. Farhi, E., Gamarnik, D., Gutmann, S.: The quantum approximate optimization algorithm needs to see the whole graph: a typical case (2020) arXiv:2004.09002 [quant-ph]

  43. Binkowski, L., Koßmann, G., Ziegler, T., Schwonnek, R.: Elementary proof of QAOA convergence (2023) arXiv:2302.04968 [quant-ph]

  44. Chandarana, P., Hegade, N.N., Paul, K., Albarrán-Arriagada, F., Solano, E., Campo, A., Chen, X.: Digitized-counterdiabatic quantum approximate optimization algorithm. Phys. Rev. Res. 4, 013141 (2022). https://doi.org/10.1103/PhysRevResearch.4.013141

    Article  Google Scholar 

  45. Leontica, S., Amaro, D.: Exploring the neighborhood of 1-layer QAOA with instantaneous quantum polynomial circuits (2023) arXiv:2210.05526 [quant-ph]

  46. Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., Summer, A.: A review on quantum approximate optimization algorithm and its variants (2023) arXiv:2306.09198 [quant-ph]

  47. Egger, D.J., Mareček, J., Woerner, S.: Warm-starting quantum optimization. Quantum 5, 479 (2021). https://doi.org/10.22331/q-2021-06-17-479

    Article  Google Scholar 

  48. Tate, R., Moondra, J., Gard, B., Mohler, G., Gupta, S.: Warm-started QAOA with custom mixers provably converges and computationally beats Goemans-Williamson’s max-cut at low circuit depths (2023) arXiv:2112.11354 [quant-ph]

  49. Crosson, E., Farhi, E., Lin, C.Y.-Y., Lin, H.-H., Shor, P.: Different strategies for optimization using the quantum adiabatic algorithm (2014) arXiv:1401.7320 [quant-ph]

  50. Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution (2000) arXiv:quant-ph/0001106 [quant-ph]

  51. Hogg, T.: Adiabatic quantum computing for random satisfiability problems. Phys. Rev. A 67, 022314 (2003). https://doi.org/10.1103/PhysRevA.67.022314

    Article  ADS  Google Scholar 

  52. Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., Preda, D.: A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science 292(5516), 472–475 (2001). https://doi.org/10.1126/science.1057726

    Article  ADS  MathSciNet  Google Scholar 

  53. Albash, T., Lidar, D.A.: Adiabatic quantum computation. Rev. Mod. Phys. 90, 015002 (2018). https://doi.org/10.1103/RevModPhys.90.015002

    Article  ADS  MathSciNet  Google Scholar 

  54. Kremenetski, V., Hogg, T., Hadfield, S., Cotton, S.J., Tubman, N.M.: Quantum alternating operator ansatz (QAOA) phase diagrams and applications for quantum chemistry (2021) arXiv:2108.13056 [quant-ph]

  55. Bittel, L., Kliesch, M.: Training variational quantum algorithms is NP-hard. Phys. Rev. Lett. 127, 120502 (2021). https://doi.org/10.1103/PhysRevLett.127.120502

    Article  ADS  MathSciNet  Google Scholar 

  56. Sack, S.H., Medina, R.A., Kueng, R., Serbyn, M.: Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement. Phys. Rev. A 107, 062404 (2023). https://doi.org/10.1103/PhysRevA.107.062404

    Article  ADS  MathSciNet  Google Scholar 

  57. Tibaldi, S., Vodola, D., Tignone, E., Ercolessi, E.: Bayesian optimization for QAOA (2023) arXiv:2209.03824 [quant-ph]

  58. Carrascal, G., Roman, B., Botella, G., Barrio, A.: Differential evolution VQE for crypto-currency arbitrage. quantum optimization with many local minima (2023) arXiv:2308.01427 [quant-ph]

  59. Brandao, F.G.S.L., Broughton, M., Farhi, E., Gutmann, S., Neven, H.: For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances (2018) https://doi.org/10.48550/ARXIV.1812.04170

  60. Preskill, J.: Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018). https://doi.org/10.22331/q-2018-08-06-79

    Article  Google Scholar 

  61. Qiskit contributors: Qiskit: An open-source framework for quantum computing (2023) https://doi.org/10.5281/zenodo.2573505

  62. Virtanen, P., Gommers, R., Oliphant, T.E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S.J., Brett, M., Wilson, J., Millman, K.J., Mayorov, N., Nelson, A.R.J., Jones, E., Kern, R., Larson, E., Carey, C.J., Polat, İ., Feng, Y., Moore, E.W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E.A., Harris, C.R., Archibald, A.M., Ribeiro, A.H., Pedregosa, F., van Mulbregt, P., SciPy 1.0 Contributors: SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods 17, 261–272 (2020) https://doi.org/10.1038/s41592-019-0686-2

  63. Scriva, G., Astrakhantsev, N., Pilati, S., Mazzola, G.: Challenges of variational quantum optimization with measurement shot noise (2023) arXiv:2308.00044 [quant-ph]

  64. Gonthier, J.F., Radin, M.D., Buda, C., Doskocil, E.J., Abuan, C.M., Romero, J.: Measurements as a roadblock to near-term practical quantum advantage in chemistry: resource analysis. Phys. Rev. Res. 4, 033154 (2022). https://doi.org/10.1103/PhysRevResearch.4.033154

    Article  Google Scholar 

  65. Kim, Y., Eddins, A., Anand, S., Wei, K.X., Berg, E., Rosenblatt, S., Nayfeh, H., Wu, Y., Zaletel, M., Temme, K., Kandala, A.: Evidence for the utility of quantum computing before fault tolerance. Nature 618(7965), 500–505 (2023). https://doi.org/10.1038/s41586-023-06096-3

    Article  ADS  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Quantum Computing Research Laboratory, Leonardo S.p.A., Via R. Pieragostini 80, 16151, Genoa, Italy

    Matteo Vandelli, Alessandra Lignarolo & Daniele Dragoni

  2. Digital Infrastructures, Leonardo S.p.A., Via R. Pieragostini 80, 16151, Genoa, Italy

    Carlo Cavazzoni & Daniele Dragoni

Authors
  1. Matteo Vandelli
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alessandra Lignarolo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Carlo Cavazzoni
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Daniele Dragoni
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

M.V. and D.D. developed the code for the quantum simulation and performed the calculations. All authors contributed equally to the conception of this work, to the data analysis, and to the writing of the manuscript.

Corresponding author

Correspondence to Matteo Vandelli.

Ethics declarations

Conflict of interest

The authors declare no competing commercial or financial interest that could be construed as a potential conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Vandelli, M., Lignarolo, A., Cavazzoni, C. et al. Evaluating the practicality of quantum optimization algorithms for prototypical industrial applications. Quantum Inf Process 23, 344 (2024). https://doi.org/10.1007/s11128-024-04560-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-024-04560-1

Keywords

Search

Navigation