Quantum Approximate Multi-Objective Optimization

2025/03/28 by Ayse Kotil, Elijah Pelofske, Kotil, Ayse +11 · 1 voice · 8 citations
Computer Science · Mathematics · #FOS: Physical sciences #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2503.22797

Abstract

The goal of multi-objective optimization is to understand optimal trade-offs between competing objective functions by finding the Pareto front, i.e., 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. In this work, we use 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.

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Julia: A Fresh Approach to Numerical Computing
• Pymoo: Multi-Objective Optimization in Python

Cited by

• Investigating methods to solve large windfarm optimization problems with a minimum number of qubits using circuit-based quantum computers
• A Lyapunov Framework for Quantum Algorithm Design in Combinatorial Optimization with Approximation Ratio Guarantees
• Progress on Data-Driven, Multi-Objective Quantum Optimization
• Taming Barren Plateaus in Arbitrary Parameterized Quantum Circuits without Sacrificing Expressibility
• Constrained Shadow Tomography for Molecular Simulation on Quantum Devices
• A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization: Quadratic Cost Functions and Empirical Evaluations
• Hybrid Sequential Quantum Computing
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms

Discussions

• Results from a collaboration between IBM Quantum, IBM Research Europe–Zurich, Los Alamos National Laboratory, and Zuse Institute Berlin published in Nature Computational Science @fc-modal.bsky.social [bsky, 0 points, 1 comments]

Related

• Multi-objective optimization by quantum annealing
• Variational Quantum Multi-Objective Optimization
• A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization: Quadratic Cost Functions and Empirical Evaluations