Quantum Approximate Multi-Objective Optimization

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.

19 pages, 12 figures

References in corpus (18)

• Warm-starting quantum optimization
• Challenges and Opportunities in Quantum Optimization
• Parameter Concentration in Quantum Approximate Optimization
• MAXCUT QAOA performance guarantees for p >1
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• Provable bounds for noise-free expectation values computed from noisy samples
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Transfer learning of optimal QAOA parameters in combinatorial optimization
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Fair Sampling Error Analysis on NISQ Devices
• Multi-Objective Optimization and Network Routing with Near-Term Quantum Computers
• Trainability Barriers in Low-Depth QAOA Landscapes
• Variational Quantum Multi-Objective Optimization
• JuliQAOA: Fast, Flexible QAOA Simulation
• Genuine Multipartite Entanglement in Quantum Optimization

Cited by in corpus (4)

• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers
• Constrained Shadow Tomography for Molecular Simulation on Quantum Devices
• Evidence for effectively constant shot complexity in the quantum approximate optimization algorithm without per-instance optimization