Multi-Objective Optimization by Quantum-Annealing-Inspired Algorithms

This paper demonstrates that GPU-based quantum-annealing-inspired algorithms (QAIAs) outperform both state-of-the-art classical heuristics and previously studied quantum processors in solving multi-objective MaxCut problems by achieving significantly faster end-to-end runtimes when accounting for full processing overheads.

The Gist

Imagine you are trying to organize a massive, chaotic party. You have three different goals that often clash: you want the music to be loud, the food to be cheap, and the guests to be happy. You can't maximize all three at once; if you spend more on food, the music might get quieter. Your goal isn't to find one "perfect" party plan, but to find a list of the best possible trade-offs (a "Pareto front") where you can't improve one thing without hurting another.

This is what Multi-Objective Optimization is: finding the best balance between conflicting goals.

This paper is about a new, super-fast way to find those trade-offs using a "quantum-inspired" computer program running on a standard graphics card (GPU). Here is the breakdown in simple terms:

The Problem: The "Party Planner" Dilemma

In the past, researchers tried to solve these problems using two main tools:

1. Real Quantum Computers: These are like magical, mysterious black boxes that can explore many possibilities at once. Recent studies showed they were good at finding party plans, but they were slow to set up and required a lot of extra work to clean up the results.
2. Classical Computers: These are the standard computers we use every day. They are reliable but sometimes slow at finding the best trade-offs.

The authors of this paper noticed that the previous studies comparing these two tools were unfair. They only counted how long the "magic box" took to spit out a raw list of ideas, ignoring the time it took to build the problem, run the machine, and clean up the list to find the actual winners.

The Solution: The "Quantum-Inspired" Speedster

The authors built a new algorithm called QAIA (Quantum-Annealing-Inspired Algorithm). Think of this not as a real quantum computer, but as a very clever simulation of one running on a powerful video card (GPU) inside a regular computer.

To make this simulation even better at finding diverse party plans, they added a little bit of "Gaussian Noise."

• The Analogy: Imagine a group of hikers trying to find the highest peaks in a foggy mountain range. A standard algorithm is like a hiker who gets stuck on the first hill they see. The authors' method adds a "breeze" (the noise) that gently pushes the hikers off their comfortable spots, forcing them to explore different valleys and peaks. This ensures they find a wider variety of the best trade-offs, not just one or two.

The Race: Who is Faster?

The team ran a race between their new method, real quantum computers, and the best classical methods.

1. The Sampling Speed (Finding Candidates):

   • The Result: Their GPU-based method was 100 times faster than the real quantum computers at generating raw lists of potential solutions.
   • The Metaphor: If the quantum computer is a race car that takes 10 seconds to start its engine and drive a lap, the new method is a Formula 1 car that is already running and completes the lap in a fraction of a second.

2. The End-to-End Time (The Full Job):

   • This includes building the problem, running the simulation, and cleaning up the results.
   • The Result: Their method was still 10 times faster than the best classical algorithms and significantly faster than the quantum computers when you count everything.
   • The Metaphor: Even after accounting for the time it takes to pack the car and drive to the track, the GPU method finished the whole trip much sooner than the others.

The Catch: Quality vs. Quantity

While the new method was incredibly fast at churning out numbers, the paper notes a small trade-off:

• Real Quantum Computers were very "efficient" in that they needed fewer total guesses to find the perfect list of trade-offs.
• The New Method needed to make a few more guesses (samples) to find the same list, but because it was so incredibly fast at making those guesses, it still won the race overall.

The Bottom Line

The paper claims that for the specific type of problem they tested (MaxCut with multiple goals), a standard computer running this new "quantum-inspired" code is currently the best tool available. It beats both the expensive, slow real quantum computers and the traditional classical methods in speed and overall performance.

They conclude that while real quantum computers are promising, this "quantum-inspired" approach on regular hardware is currently the champion for solving these complex balancing acts.

Technical Summary

1. Problem Definition

The paper addresses Multi-Objective Optimization (MOO), specifically the Multi-Objective MaxCut (MO-MaxCut) problem.

• Context: Unlike single-objective optimization, MOO seeks to find a set of Pareto-optimal solutions (the Pareto front), where no objective can be improved without degrading another.
• The Challenge: Existing studies comparing quantum solvers (Gate-based QAOA and Quantum Annealing) to classical heuristics often focus solely on sampling speed, ignoring the substantial overheads of model construction, circuit compilation, and the computationally intensive Pareto filtering (post-processing) required to extract the non-dominated set from raw samples.
• Goal: To provide a rigorous end-to-end comparison of quantum and classical solvers, accounting for total runtime (modeling + sampling + filtering) and evaluating whether current quantum hardware offers a practical advantage over state-of-the-art classical "quantum-inspired" algorithms.

2. Methodology

The authors propose and evaluate a GPU-accelerated Quantum-Annealing-Inspired Algorithm (QAIA) based on Simulated Bifurcation (SB).

A. Mathematical Formulation

• Hamiltonian: The MO-MaxCut problem is mapped to an Ising model. For $K$ objectives, the system minimizes a vector of Hamiltonians $H(s) = (H_1, \dots, H_K)$.
• Scalarization: To solve the multi-objective problem using single-objective solvers, the authors employ the Weighted Sum Method. They generate weight vectors using a Das–Dennis simplex-lattice design to create scalarized Hamiltonians: $H_{total}(s; c) = \sum c_k H_k(s)$.
• Pareto Filtering: Raw samples are processed via a classical Non-dominated Sorting algorithm to filter out dominated solutions and construct the final Pareto front approximation.

B. The Proposed Algorithm: Noise-Injected Simulated Bifurcation (NI-SB)

The core solver is a variant of the Simulated Bifurcation algorithm, which simulates classical Hamiltonian dynamics of nonlinear oscillators to find low-energy states.

• Ballistic (bSB) vs. Discrete (dSB): The authors utilize both continuous (ballistic) and discrete variants of SB.
• Gaussian Noise Injection: To address the lack of diversity in deterministic SB (which often converges to the same solution), the authors introduce Gaussian white noise into the momentum equation:
  $$\dot{y}_i = -[a_0 - a(t)]x_i + c_0 \sum J_{ij}\phi(x_j) + \alpha \eta_i$$
  where $\eta_i \sim \mathcal{N}(0, 1)$. This "synthetic thermal noise" allows trajectories to explore diverse regions of the solution space, crucial for covering the Pareto front effectively.
• Hardware Implementation: The algorithm is implemented on GPUs (NVIDIA RTX 4090), leveraging massive parallelism to process thousands of candidate solutions simultaneously using half-precision (float16) arithmetic.

3. Key Contributions

1. End-to-End Benchmarking: The paper shifts the evaluation metric from "sampling time" to total end-to-end runtime, explicitly including model construction and Pareto filtering overheads, which are often omitted in quantum advantage claims.
2. Strong Classical Baseline: The authors establish that GPU-accelerated QAIA serves as a formidable classical baseline, outperforming both quantum hardware and traditional classical heuristics.
3. Noise-Injected SB: The introduction of Gaussian noise to SB significantly improves sample diversity for MOO, allowing the algorithm to recover the complete Pareto set with fewer total samples compared to QAOA.
4. Comprehensive Comparison: The study compares the proposed method against:
   • Quantum: D-Wave Advantage/Advantage2 (QA) and IBM Fez (QAOA).
   • Classical Heuristics: DCM, DPA-a, MOEA/D, NSGA-II, NSGA-III, and RVEA.

4. Results

The experiments were conducted on MO-MaxCut instances with varying numbers of variables ($n$) and objectives ($K=3, 4$).

• Sampling Speed:

  • QAIA is approximately two orders of magnitude faster at sampling candidate solutions than previously studied quantum processors (QA and QAOA).
  • QAIA reaches the optimal Hypervolume plateau in $10^{-2}$ to $10^{-1}$ seconds, whereas QA systems require seconds to minutes.

• Sample Efficiency & Quality:

  • QAIA vs. QAOA: QAIA recovers the complete Pareto set with ~10$\times$ fewer candidates than QAOA.
  • QAIA vs. QA: While QA requires fewer samples on average to find the Pareto set, QAIA compensates with vastly superior sampling speed.

• End-to-End Performance:

  • Vs. Quantum: QAIA is ~1 order of magnitude faster than QA and ~4 orders of magnitude faster than QAOA in total runtime (including filtering).
  • Vs. Classical Heuristics: On dense 3-objective instances up to $n=200$, QAIA outperforms MOEA/D, NSGA-II, NSGA-III, and RVEA in both runtime and solution quality (Hypervolume).
    • Example: For $n=200$, QAIA achieved 99% of the optimal Hypervolume in <1 second, while classical heuristics took **9–11 seconds** and achieved lower Hypervolume ratios (60–93%).

• Scalability:

  • The method successfully handled $n=200$ (complete graph), exceeding the current embedding limits of D-Wave's Pegasus and Zephyr topologies (approx. 180–193 nodes).

5. Significance and Conclusion

• Redefining Quantum Advantage: The paper argues that for current MO-MaxCut benchmarks, GPU-accelerated quantum-inspired solvers currently provide a stronger end-to-end baseline than available quantum hardware. The "quantum advantage" in sampling speed is negated by the overheads of quantum execution and the superior parallelism of modern GPUs.
• Practical Utility: The results suggest that for practical multi-objective optimization tasks, classical Ising solvers (specifically NI-SB) are currently the most efficient tool, offering rapid convergence and high solution quality.
• Future Directions: The authors emphasize the need for metrics that separate sampling speed from sample quality (e.g., nondominated yield, Pareto-set recall). They also suggest testing these methods on broader MOO problems beyond MaxCut and exploring other QAIA variants (e.g., thermal-assisted SB).

In summary, this work demonstrates that while quantum hardware is improving, classical quantum-inspired algorithms running on GPUs currently dominate the landscape for multi-objective optimization in terms of total time-to-solution and scalability.