PaperlayerView exact revision on arXiv

Source-linked AI summary

Variational Quantum Multi-Objective Optimization

Linus Ekstrom, Hao Wang, Sebastian Schmitt

arXiv:2312.14151v3quant-ph

TL;DR

Many realistic combinatorial problems require balancing multiple conflicting objectives, but existing variational quantum optimization primarily addresses single objectives. QMOO encodes all objectives in a parametrized qudit circuit, samples Pareto candidates, and tunes the circuit by maximizing hypervolume. Across benchmark classes with up to five objectives, it produced results comparable to classical methods in several settings and remained effective with as few as 128 shots per iteration.

  • Problem

    Many realistic combinatorial optimization problems require balancing multiple conflicting objectives, whereas existing variational quantum approaches mainly target single-objective optimization.

    Source: §I · p. 1

  • Method

    QMOO incorporates all cost Hamiltonians into a parametrized quantum circuit, samples basis states, and optimizes the circuit using the hypervolume of extracted solutions.

    Source: §III · p. 2, §V · p. 3, §VIII · p. 7

  • Results

    QMOO produced solution quality comparable to purely classical methods for many benchmark cases, although it was not fully competitive with state-of-the-art classical multi-objective algorithms.

    Source: §VII · p. 7, §VIII · p. 8

  • Takeaways & Limitations

    Good results with as few as 128 measurement shots per iteration support QMOO’s prospective use on near-term quantum hardware.

    Source: §VIII · p. 8

Abstract

from arXiv · show

Solving combinatorial optimization problems on near-term quantum devices has gained a lot of attraction in recent years. Currently, most works have focused on single-objective problems, whereas many real-world applications need to consider multiple, mostly conflicting objectives, such as cost and quality. We present a variational quantum optimization algorithm to solve discrete multi-objective optimization problems on quantum computers. The proposed quantum multi-objective optimization (QMOO) algorithm incorporates all cost Hamiltonians representing the classical objective functions in the quantum circuit and produces a quantum state consisting of Pareto-optimal solutions in superposition. From this state we retrieve a set of solutions and utilize the widely applied hypervolume indicator to determine its quality as an approximation to the Pareto-front. The variational parameters of the QMOO circuit are tuned by maximizing the hypervolume indicator in a quantum-classical hybrid fashion. We show the effectiveness of the proposed algorithm on several benchmark problems with up to five objectives. We investigate the influence of the classical optimizer, the circuit depth and compare to results from classical optimization algorithms. We find that the algorithm is robust to shot noise and produces good results with as low as 128 measurement shots in each iteration. These promising result open the perspective to run the algorithm on near-term quantum hardware.

I. INTRODUCTION

Variational quantum optimization has largely targeted single objectives, although realistic problems often require balancing conflicting objectives. The paper motivates qudit-based QMOO as a direct approach to producing Pareto-optimal solution sets.

I. INTRODUCTION

  • Realistic applications often require simultaneous optimization of conflicting objectives such as cost and quality, making a single optimum inadequate.The target is instead a set of Pareto-optimal trade-off solutions.Source: §I · p. 1
  • Existing variational quantum optimization approaches address single-objective problems, and direct variational quantum treatment of multi-objective problems had not been available.Source: §I · p. 1
  • Qudit encodings are proposed to reduce the overhead that qubits can impose on integer optimization problems in the NISQ era.Prior work suggests possible benefits for circuit simplification, error correction, and algorithm speed-up.Source: §I · p. 1
  • The paper formulates and evaluates the proposed QMOO algorithm with qudit variables and assesses it through benchmark simulations.Source: §I · p. 1

II. RELATED WORK

Prior quantum approaches obtain Pareto solutions by repeatedly scalarizing objectives or use multi-objective methods only for constraints or circuit-structure trade-offs. QMOO instead places all objectives in one circuit and extracts the Pareto set from one resulting state.

II. RELATED WORK

  • Weighted-sum scalarization solves several single objectives with regular QAOA and reconstructs only convex parts of the Pareto front.Source: §II · pp. 1–2
  • A quantum NSGA-II approach handles constraint satisfaction as a second objective while still targeting one optimized minimum-cost solution.Source: §II · p. 2
  • Another NSGA-II application trades circuit complexity against achievable minimum energy for each fixed circuit structure.Source: §II · p. 2
  • QMOO incorporates all objectives into the quantum circuit and extracts the full set of Pareto-optimal solutions from one quantum state.Source: §II · p. 2

III. MULTI-OBJECTIVE OPTIMIZATION

Multi-objective optimization minimizes several cost functions simultaneously and seeks efficient solutions whose objective values form the Pareto front. The hypervolume indicator evaluates solution-set quality relative to a reference point and is Pareto-compliant.

III. MULTI-OBJECTIVE OPTIMIZATION

  • A multi-objective problem minimizes K cost functions simultaneously over a feasible search space, rather than optimizing one scalar objective.The objective vector is C⃗ = (C1, …, CK).Source: §III · p. 2
  • A solution is Pareto-efficient when no other feasible solution improves the objective vector without worsening at least one objective; their objective images form the Pareto front.Source: §III · p. 2
  • The hypervolume indicator measures the dominated region bounded by a reference point and is Pareto-compliant, so it is used to assess multi-objective solution quality.The paper applies it to unconstrained combinatorial integer problems with X ⊆ {0, …, d −1}^N.Source: §III · p. 2

IV. QUDIT REPRESENTATION

The paper represents finite-range integer variables with qudits, whose computational basis states encode complete search vectors. Three angular-momentum-based generators are sufficient to construct arbitrary single-qudit unitaries through repeated rotations.

IV. QUDIT REPRESENTATION

  • An integer search vector x = (x1, …, xN)ᵀ is represented by N d-level qudits, with each computational-basis state corresponding to one possible vector.Source: §IV · p. 2
  • The resulting Hilbert space has dimension d^N, and arbitrary states are superpositions of orthonormal computational-basis states.Source: §IV · p. 2
  • Although SU(d) has d^2 − 1 Hermitian basis generators, the construction uses the three operators Lx, Lz, and L_z^2.Source: §IV · p. 2
  • Repeated finite rotations generated by Lx, Lz, and L_z^2 can implement arbitrary unitary operations because their iterated commutators generate the full Hermitian basis.Source: §IV · p. 2

V. QUANTUM MULTI-OBJECTIVE OPTIMIZATION

QMOO is a variational quantum algorithm that encodes multiple objective Hamiltonians in layered circuits and aims to concentrate probability on Pareto-optimal solutions. Measurements provide candidate solutions whose hypervolume tunes the circuit parameters through a quantum-classical loop.

V. QUANTUM MULTI-OBJECTIVE OPTIMIZATION

  • Each objective cost function is represented by a diagonal Hamiltonian whose computational-basis eigenvalues equal the corresponding classical objective values.These Hamiltonians generate the phase operators used to encode all objectives in the circuit.Source: §V · pp. 2–3
  • QMOO uses L circuit layers with independently adjustable parameters, and each layer contains K objective-specific phase and mixing blocks.The phase operators encode objective energies through cost Hamiltonians, while shared mixing structures use variational parameters.Source: §V · p. 3
  • The circuit starts from a uniform superposition, while the authors report that alternative initial states should not qualitatively change performance.They experimentally validated this argument with various initial states, although those results are not shown.Source: §V · p. 3
  • Measurements over Nshots produce candidate basis states, from which the NS most frequent states are selected and evaluated on all classical objectives.The non-dominated extracted solutions approximate the Pareto front, and their hypervolume becomes the classical optimization objective.Source: §V · p. 3
  • The method remains effective with finite, small shot counts, whereas infinitely many shots would correspond to selecting states with the largest spectral weights.The parameter count is Nparams = 3LK, or 2LK for qubits without local squeezing, a factor K larger than standard QAOA.Source: §V · pp. 3–4
  • The ideal QMOO state places predominant weight on the full set of Pareto-optimal solutions rather than one optimal basis state.This distinguishes QMOO from standard QAOA, which targets a single optimal solution.Source: §V · pp. 3–4

A. Benchmark Functions

The benchmark suite combines randomized linear and quadratic objectives into two-, three-, and five-objective minimization problems with deliberately conflicting objectives. It includes spin-model, distance-based, and hybrid constructions, with normalized costs enabling a common hypervolume reference point.

A. Benchmark Functions

  • The benchmarks cover two-, three-, and five-objective minimization problems whose objectives are designed to trade off against one another.The benchmark functions are provided as Python functions in a repository.Source: A. Benchmark Functions · p. 4
  • Problem class II pairs ferromagnetic and anti-ferromagnetic quadratic spin objectives to create conflicting optimization goals.The coupling signs distinguish FM and AFM interactions, while local fields complete the spin-model construction.Source: A. Benchmark Functions · p. 4
  • Problem class III combines an AFM objective with a quadratic distance objective centered on a randomly selected point.The distance objective uses diagonal positive couplings and randomized local fields.Source: A. Benchmark Functions · pp. 4–5
  • Problem class IV contains three objectives: AFM and FM spin models plus a quadratic distance objective.The distance term is defined relative to a random vector x0.Source: A. Benchmark Functions · pp. 4–5
  • Problem class V contains five objectives combining AFM and FM nearest-neighbor chains, a random-vector distance objective, and two partially opposed spin-chain objectives.The latter objectives switch FM and AFM couplings between the first and second halves of the variables.Source: A. Benchmark Functions · p. 5
  • Objective values are normalized to [0, 1], allowing the hypervolume reference vector to be fixed as the all-ones vector.Figure 2 illustrates all solutions and the Pareto-optimal front for one CIII instance with N = 6 and d = 5.Source: A. Benchmark Functions · p. 5, Figure 2 · p. 5

B. Experimental Setup

The study evaluates QMOO across randomized benchmark instances while varying measurement shots, classical optimizers, and comparisons with classical multi-objective evolutionary algorithms.

Experimental protocol

  • QMOO is run 50 times per randomly generated benchmark instance with circuit parameters initialized uniformly in [−π, π].Each classical-optimization iteration uses Nshots measurements, from 128 to ∞, and selects NS = 20 most frequent solutions.Source: B. Experimental Setup · p. 5

Classical optimizers

  • The study tests COBYLA, L-BFGS-B, Powell, CMA-ES, PSO, and differential evolution as classical optimizers for tuning the quantum circuit.Population-based stochastic optimizers perform slightly better in most instances, but Powell is selected because it offers a favorable quality–resource trade-off.Source: B. Experimental Setup · p. 5

Classical baselines

  • NSGA-II, IBEA, and MOEA/D provide classical multi-objective baselines with population size 20, 40 independent runs, and 200 iterations.The population size matches the NS = 20 solutions extracted from QMOO quantum states.Source: B. Experimental Setup · p. 5

VII. RESULTS

QMOO improves normalized hypervolume across iterations and produces solution sets that move toward Pareto fronts, with weak shot dependence and performance comparable to classical methods for three- and five-objective problems.

Shot-noise robustness

  • For five-objective optimization, normalized hypervolume increases across iterations for all shot counts, including Nshots = 128, although fewer shots produce noisier progress.The corresponding figure summarizes 50 runs with Powell optimization and a one-layer circuit using Nshots = 128, 1024, 16384, and ∞.Source: §VII · p. 5, Figure 3 · p. 6

Solution-set progression

  • QMOO solution sets progress toward the Pareto front over iterations in the two-objective CII quadratic problem.The example begins with randomly initialized solutions in the top-right objective-space region and ends with solutions closer to the Pareto front.Source: §VII · pp. 5–6, Figure 4 · p. 6

Shot-noise robustness

  • QMOO’s performance is almost unchanged from 128 to 16384 shots and remains similar under full-state tomography across the studied problem classes.For class CIII, 128 shots even appear slightly better, while class CII shows slightly worse and more variable full-tomography results.Source: §VII · p. 6, Figure 5 · p. 7

Optimizer and circuit-depth effects

  • CMA-ES performs best among tested optimizers, Powell and COBYLA follow closely, and L-BFGS-B performs significantly worse with large statistical variation.Powell is used for the main results because CMA-ES requires an order of magnitude more circuit evaluations, while QMOO values are comparable to classical optimization for the representative CIV setting.Source: §VII · p. 6, Figure 6 · p. 7
  • Increasing QMOO circuit layers increases hypervolume for all tested optimizers, but the improvement is minor in this study.This limited gain motivates focusing on single-layer circuits in the proof-of-concept evaluation.Source: §VII · p. 7, Figure 6 · p. 7

Overall results

  • Across five benchmark classes and qubit, qutrit, and ququint setups, 128-shot QMOO performance is similar to full-state tomography and comparable to classical methods for three- and five-objective classes.The reported comparisons also show slightly lower QMOO performance for two-objective problems and suggest further gains from hyperparameter tuning or warm-starting.Source: §VII · p. 7

Classical comparison

  • QMOO is slightly inferior to classical optimizers for two-objective problems but comparable for three- and five-objective problems.The figure compares normalized hypervolume across CII, CIV, and CV using 11 instances and 50 randomly initialized runs per instance.Source: §VII · pp. 6–7, Figure 5 · p. 7

VIII. DISCUSSION AND CONCLUSION

QMOO represents non-dominated solutions in superposition and optimizes a parametrized circuit using the hypervolume indicator. Across benchmark classes, it achieved similar quality to classical methods in many cases and remained effective with 128 shots, but was not fully competitive overall.

VIII. DISCUSSION AND CONCLUSION

  • QMOO represents a set of non-dominated solutions in superposition rather than targeting one computational-basis solution.The circuit is optimized to maximize the hypervolume of extracted classical solutions, ideally approximating the Pareto front.Source: §VIII · pp. 7–8
  • QMOO found solutions of similar quality to purely classical methods in many benchmark cases, although it was not fully competitive with state-of-the-art classical algorithms overall.The benchmark classes use randomized linear and quadratic cost functions with arbitrary numbers of qudit variables.Source: §VIII · p. 8
  • 128 measurement shots per iteration produced consistently good results without detectable systematic degradation up to Hilbert-space dimension approximately 2·10^4.The results suggest that the number of shots need not scale exponentially with Hilbert-space dimension.Source: §VIII · p. 8
  • The analysis is a first step, with future work including richer SU(d) mixers, individual qudit mixing parameters, and deeper circuits.These extensions may improve performance but increase variational parameters and classical optimization complexity.Source: §VIII · p. 8
  • QMOO's trainability and susceptibility to barren plateaus remain open questions, especially for deeper circuits with many layers.Sampling individual basis states avoids expectation-value calculations, eliminating one prominent source of trainability issues.Source: §VIII · p. 8
  • The work presents a first step toward quantum algorithms that use quantum resources to compute Pareto-optimal sets for multi-objective optimization.The authors position QMOO as a route toward solving multi-objective problems natively on quantum hardware.Source: §VIII · pp. 8–9

Appendix A: Visualization of exemplary benchmark problems

Figure 8 visualizes benchmark objective spaces across qubits, qutrits, and ququints, distinguishing all possible solutions from the true Pareto-optimal front.

Appendix A: Visualization of exemplary benchmark problems

  • Figure 8 compares linear and quadratic two- and three-objective benchmarks across qubits, qutrits, and ququints.Rows correspond to qubits, qutrits, and ququints, while gray and blue dots distinguish all solutions from Pareto-optimal solutions.Source: Appendix A · p. 9
Loading 2312.14151v3…