Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2025 Oct 24.
doi: 10.1038/s43588-025-00873-y. Online ahead of print.

Quantum approximate multi-objective optimization

Ayse Kotil  1   2 , Elijah Pelofske  3 , Stephanie Riedmüller  2 , Daniel J Egger  1 , Stephan Eidenbenz  3 , Thorsten Koch  2   4 , Stefan Woerner  5
Affiliations

Quantum approximate multi-objective optimization

Ayse Kotil et al. Nat Comput Sci. .

Abstract

The goal of multi-objective optimization is to understand optimal trade-offs between competing objective functions by finding the Pareto front, that is, the set of all Pareto-optimal solutions, where no objective can be improved without degrading another one. Multi-objective optimization can be challenging classically, even if the corresponding single-objective optimization problems are efficiently solvable. Thus, multi-objective optimization represents a compelling problem class to analyze with quantum computers. Here we use a low-depth quantum approximate optimization algorithm to approximate the optimal Pareto front of certain multi-objective weighted maximum-cut problems. We demonstrate its performance on an IBM Quantum computer, as well as with matrix product state numerical simulation, and show its potential to outperform classical approaches.

PubMed Disclaimer

Conflict of interest statement

Competing interests: The authors declare no competing interests.

References

    1. Abbas, A. et al. Challenges and opportunities in quantum optimization. Nat. Rev. Phys. 6, 718–735 (2024). - DOI
    1. Ehrgott, M. Multicriteria Optimization 2nd edn (Springer, 2005).
    1. Figueira, J. et al. Easy to say they are hard, but hard to see they are easy—towards a categorization of tractable multiobjective combinatorial optimization problems. J. Multi-Criteria Decis. Anal. 24, 82–98 (2016).
    1. Allmendinger, R., Jaszkiewicz, A., Liefooghe, A. & Tammer, C. What if we increase the number of objectives? Theoretical and empirical implications for many-objective combinatorial optimization. Comput. Oper. Res. 145, 105857 (2022). - DOI
    1. Bhattacharyya, B., Capriotti, M. & Tate, R. Solving general QUBOs with warm-start QAOA via a reduction to Max-Cut. Preprint at http://arxiv.org/abs/2504.06253 (2025).

LinkOut - more resources