PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum-enhanced Markov Chain Monte Carlo for Combinatorial Optimization

Kate V. Marshall, Daniel J. Egger, Michael Garn, Francesca Schiavello, Sebastian Brandhofer, Christa Zoufal, Stefan Woerner

arXiv:2602.06171v2quant-ph

TL;DR

The paper addresses how near-term quantum computing might tackle combinatorial optimization despite limited evidence at classically difficult scales. It combines QeMCMC sampling with warm-starting and parallel tempering, then tests the workflow on MIS using IBM hardware. The method recovers global optima through 117 variables and provides early evidence of scaling advantages over comparable classical MCMC on selected instances.

  • Problem

    Near-term quantum optimization lacks strong empirical evidence at problem sizes that challenge state-of-the-art classical solvers, while hardware noise remains limiting.

  • Method

    The workflow combines quantum-enhanced MCMC sampling with warm-starting and parallel tempering for combinatorial optimization.

  • Results

    The algorithm recovered global optima for MIS instances with 17, 39, 52, 80, and 117 variables using corresponding quantum hardware.

  • Takeaways & Limitations

    The results provide early evidence of a scaling advantage over comparable classical MCMC approaches on the selected MIS instances.

  • Takeaways & Limitations

    Further experiments across larger instance sets and additional problem classes are needed to strengthen the conclusions.

Abstract

from arXiv · show

Quantum computing offers an alternative paradigm for addressing combinatorial optimization problems compared to classical computing. Despite recent hardware improvements, the execution of empirical quantum optimization experiments at scales known to be hard for state-of-the-art classical solvers is not yet in reach. In this work, we offer a different way to approach combinatorial optimization with near-term quantum computing. Motivated by the promising results observed in using quantum-enhanced Markov chain Monte Carlo (QeMCMC) for approximating complicated probability distributions, we combine ideas of sampling from the device with QeMCMC together with warm-starting and parallel tempering, in the context of combinatorial optimization. We demonstrate empirically that our algorithm recovers the global optima for instances of the Maximum Independent Set problem (MIS) up to 117 decision variables using 117 qubits on IBM quantum hardware. We show early evidence of a scaling advantage of our algorithm compared to similar classical methods for the chosen instances of MIS. MIS is practically relevant across domains like financial services and molecular biology, and, in some cases, already difficult to solve to optimality classically with only a few hundred decision variables.

I. INTRODUCTION

Quantum optimization is motivated by the potential of quantum methods for combinatorial problems, but noise and heuristic guarantees make near-term advantage difficult to establish. This work combines QeMCMC with warm-starting and parallel tempering to test a practical quantum-classical workflow on MIS.

  • Quantum optimization maps combinatorial problems to Ising ground-state search, but available hardware noise limits executable circuit width and depth.
  • Heuristic quantum-classical methods offer a near-term alternative despite generally lacking provable convergence or runtime guarantees.
  • QeMCMC uses quantum proposal distributions and has shown up to a quartic advantage in reaching target distributions over classical MCMC.
  • The proposed workflow combines QeMCMC, warm-starting, and parallel tempering for MIS instances up to 117 decision variables on IBM hardware.
  • MCMC samples Boltzmann distributions without explicitly computing their partition function, whose exact evaluation requires Ω(2^n) time.

B. Maximum Independent Sets

The paper formulates Maximum Independent Set as a QUBO and maps it to an Ising Hamiltonian, so low-temperature Boltzmann sampling favors configurations representing optimal independent sets.

  • A maximum independent set is an independent vertex subset of maximal size, with no selected pair connected by an edge.
  • MIS uses binary variables x_i ∈ {0, 1}, where x_i = 1 indicates that vertex v_i is selected.
  • The QUBO combines the MIS objective with a constraint penalty weighted by λ to enforce independence.
  • For λ ≥ 2, minimizing the QUBO yields an optimal MIS solution according to the stated formulation.
  • The QUBO is converted to an Ising Hamiltonian whose spin configurations define candidate solutions and associated energies.
  • As T → 0, the Boltzmann distribution concentrates on minimum-energy configurations corresponding to optimal MIS solutions.

III. METHODS

Quantum-enhanced MCMC replaces classical proposal generation with quantum-circuit sampling while preserving a tractable acceptance step through symmetric transition probabilities.

  • QeMCMC uses a quantum circuit to generate proposal configurations for exploring rugged low-temperature energy landscapes.
  • The proposal circuit is based on an annealing Hamiltonian combining a cost Hamiltonian and a mixing Hamiltonian.
  • A quantum device prepares |s⟩, applies a unitary U, and measures the result to obtain a proposed configuration s′.
  • Symmetric proposals satisfy Q(s′ | s) = Q(s | s′), canceling the transition-probability ratio in the acceptance rule.
  • The symmetry condition enforces reversible transitions and supports convergence to the target distribution through detailed balance.

B. Warm-starting QAOA

Warm-starting QAOA initializes quantum optimization from a previously obtained good configuration and biases exploration toward its neighborhood.

  • Applying the QeMCMC unitary to a computational-basis state resembles warm-starting QAOA.
  • Warm-starting leverages a good solution from a classical or prior quantum procedure to initialize another quantum algorithm.
  • A regularization parameter ε converts the starting bitstring into a superposition of nearby states.
  • The softened solution defines single-qubit rotation angles used in the warm-started initial state and mixer.
  • The adjusted mixer has the softened state as its ground state, biasing MIS samples toward a known good starting point.

C. Parallel tempering

Parallel tempering uses replicas of the same Ising model at different temperatures, combining local MCMC updates with replica exchanges to help low-temperature chains escape local minima. The workflow also addresses quantum sampling noise by increasing samples and preferentially retaining low-energy proposals.

  • Parallel tempering: Parallel tempering runs replicas at ordered temperatures, each targeting the same Boltzmann distribution.Each iteration performs local MCMC updates followed by exchanges between selected replica pairs.
  • Replica exchange: Replica exchanges allow high-temperature chains to discover candidate solutions and transfer them to low-temperature chains.This helps low-temperature replicas escape local minima and sample around promising configurations.
  • Noise mitigation: Noise mitigation increases the number of quantum samples according to the circuit noise strength υ when feasible.The proposed scaling uses 1/√υ samples to increase the chance of obtaining samples from the corresponding noise-free distribution.
  • Proposal selection: The workflow ranks sampled configurations by energy and retains low-energy proposals to bias updates toward good solutions while preserving exploration.It tests both the single best sample and random subsampling from a set of the lowest-energy bitstrings.

E. Circuit construction

The circuit construction uses a first-order Lie–Trotter decomposition to implement a QAOA-like unitary, with warm-started proposals integrated into a replica-based optimization workflow. As graph sizes increase, simplified cost Hamiltonians reduce hardware implementation demands.

  • Circuit construction: A first-order Trotter decomposition approximates the QAOA-like circuit because the cost and mixer Hamiltonians do not commute.The construction uses two identical Trotter steps and has p = 2 QAOA form with γ1 = γ2 ≡γ and β1 = β2 ≡β.
  • Warm-starting: The warm-started quantum proposal distribution restricts sampling to promising low-energy configurations rather than initializing only from a computational-basis state.This adaptation avoids the lack of solution-space exploration observed with standard initialization and mixing.
  • Hardware scaling: Larger MIS instances use simplified cost Hamiltonians that omit Pauli terms requiring too many SWAP gates.This reduces circuit width and depth so the ansatz remains executable on quantum hardware.
  • Experimental workflow: The workflow uses identical replica circuits, random initial configurations, quantum sampling, energy filtering, and Metropolis–Hastings acceptance.Accepted configurations generate subsequent candidates through the warm-start QAOA proposal distribution.
  • Experimental workflow: Replica exchanges are performed at regular intervals to help low-temperature replicas escape local minima.The exchange probability is defined by the algorithm’s replica-exchange criterion.
  • Parameter tuning: The algorithm runs for at most 200,000 iterations or until convergence, with instance-specific parameter tuning affecting mixing efficiency and convergence.Parameters are selected using analytical guidelines and heuristic tuning.

IV. RESULTS

The results study five real-world animal-interaction graphs from 17 to 117 nodes using classical and quantum-enhanced replica-exchange methods. For the 117-node classical baseline, convergence required fewer iterations with 10,000 shots, but the much larger shot count provided little additional value in the noise-free setting.

  • Problem instances: Five graph instances contain n ∈{17, 39, 52, 80, 117} nodes and m ∈{91, 245, 454, 714, 1028} edges.The graphs come from real-world animal social interaction networks in the Network Repository.
  • Problem instances: The 117-node instance contains a fully connected 110-node component and 7 isolated nodes, and is analyzed without preprocessing.Experiments compare classical replica-exchange MCMC, classical MPS simulation, and IBM quantum hardware.
  • Classical baseline: The strongest classical baseline uses uniformly sampled proposals with up to 5 bitflips per iteration and compares 1-shot with 10,000-shot updates.The experiments use random subsampling from the best ten proposals in the multi-shot setting.
  • Classical baseline: The classical baseline repeats each experiment 10 times for 200,000 iterations per run.Initial samples come from a non-warm-started p = 2 QAOA circuit.
  • Convergence results: 6,293 samples are the lowest count needed to reach the global optimum with 1 shot per iteration.This is the best reported convergence count for the 1-shot setting.
  • Convergence results: 5,101 iterations are the lowest count needed to reach the global optimum with 10,000 shots per iteration.Although iteration counts are similar, the multi-shot setting uses substantially more total shots and adds little value in the noise-free experiment.

B. Simulation of quantum hardware

The study evaluates quantum-enhanced and classical methods for the 117-node MIS problem using simulations and IBM quantum hardware. Hardware experiments reached the global optimum, while comparisons across problem sizes provide early but qualified evidence about scaling.

  • Quantum hardware results: 151 and 83 iterations were required on average to reach the global optimum in two 117-node hardware experiments using 10,000 shots per iteration.The 10,000-shot choice was made to balance noise-related sampling requirements against practical runtime.
  • Quantum hardware results: 151 iterations reached the global optimum on ibm boston, compared with 796 iterations predicted for the same replica by MPS simulation.The authors suggest truncation error may be more detrimental than hardware noise in this simulation regime.
  • Comparison at 117 nodes: For the 117-node instance, 1-shot classical MCMC converged in about 6,000 iterations, whereas the 1-shot quantum simulation required about 90,000.With 10,000 shots per iteration and subsampling, classical MCMC required about 5,000 iterations, while the quantum hardware reached the target in 151 iterations in one reported experiment.
  • Scaling analysis: In the 1-shot setting, classical MCMC outperformed the simulated quantum method on every studied instance.The fitted exponential-growth line for the MPS simulations was approximately 83% of the classical results, which the authors describe as an early scaling indication.
  • Scaling analysis: Heron r3 hardware results outperformed both equivalent classical MCMC and simulated quantum results in the multi-shot setting.For the 80- and 117-node instances, real Heron r3 hardware also outperformed the MPS simulations.
  • Scaling analysis: The authors report initial evidence of favorable scaling with problem size, while noting that additional experiments are needed to support the conclusion.Scaling estimates used median convergence values across five graph sizes, with ten simulated trials and three hardware repeats.

V. DISCUSSION & CONCLUSIONS

The study combines QeMCMC sampling with warm-starting and parallel tempering for heuristic quantum combinatorial optimization. It recovers global optima through 117 decision variables on quantum hardware, while identifying remaining scaling and validation needs.

  • The workflow combines QeMCMC sampling, warm-started quantum optimization, and parallel tempering to explore combinatorial optimization cost landscapes.
  • 117 decision variables were tested using 117 qubits on real quantum hardware.
  • Global optima were recovered for all considered MIS instances with 17, 39, 52, 80, and 117 variables.
  • The chosen MIS instances provide early evidence of a scaling advantage over comparable classical MCMC approaches, and quantum hardware outperformed MPS simulations under the tested settings.
  • More experiments across larger instance sets and additional problem classes are needed to strengthen the conclusions.
  • Alternative circuits and scaling approaches such as problem decomposition or block sampling remain open directions beyond current hardware limitations.

Appendix A: Boltzmann sampling

The appendix develops Boltzmann sampling for MIS by constructing quantum proposal distributions and embedding them in a Metropolis-Hastings Markov chain. It examines convergence toward stationary distributions on a small instance and discusses practical execution constraints.

  • A five-node MIS instance is used to conduct small-scale Boltzmann sampling experiments across temperatures before applying QeMCMC in the heuristic setting.
  • Exact classical probabilities are obtained by enumerating all 2^n bitstrings, evaluating their energies, and applying the Boltzmann distribution.
  • The experiments demonstrate iterative convergence toward desired Boltzmann distributions at high and low temperatures on IBM superconducting hardware.
  • Quantum circuits generate proposal samples that define empirical transition probabilities from a starting state s to sampled states s′.
  • The Metropolis-Hastings acceptance rule converts the proposal matrix Q into a stochastic transition matrix P for generating Markov-chain moves.
  • QeMCMC execution used HPC resources for preparation and post-processing, while remote APIs sufficed during runs up to 117 qubits; larger problems are expected to increase classical demand.

Appendix C: Circuit optimization

The circuit-optimization appendix describes parameter selection for QeMCMC replicas, warm-starting, and parallel tempering. It uses heuristic tuning to balance sample quality, temperature exchange, and convergence across problem instances.

  • The MIS problem is encoded in a QUBO and Ising Hamiltonian, while p = 2 QAOA parameters are optimized through staged classical training.
  • Warm-starting solves a relaxed problem first and uses its solution to initialize subsequent QAOA circuits through a regularization parameter ε.
  • Parallel tempering selects the highest temperature using an inverted Boltzmann factor and extrapolates values from exact diagonalization of a 17-qubit instance to larger related problems.
  • The number of replicas is increased until adjacent-temperature swap acceptance is typically 20-40%, followed by construction of a geometric temperature ladder.
  • Geometric spacing concentrates replicas at lower temperatures while retaining higher-temperature replicas for exchanges across energy barriers.
  • The implementation attempts exchanges after k local updates, with k selected experimentally in the range 1 ≤ k ≤ 5 using a stochastic even-odd scheme.
  • MPS simulations visualize replica exchange and the resulting mixing behavior in the parallel-tempering experiment.

Appendix E: QAOA ansatz construction

The QAOA ansatz is simplified to accommodate hardware connectivity and noise. Overlapping subgraphs with different SWAP-layer budgets provide a tunable balance between problem-structure coverage and executable circuit depth.

  • A 117-node problem would require two-qubit gate depth 696 to implement the full cost operator, making deep SWAP networks problematic on noisy hardware.
  • Increasing SWAP layers can improve structural coverage until additional depth allows device noise to degrade sample quality.
  • The construction applies SWAP networks to generate overlapping subgraphs that become denser as more SWAP layers are allowed.
  • The selected ansatz balances sample quality against hardware feasibility by tuning the maximum number of SWAP layers.
  • The simplified cost operator may include only Z_iZ_j terms implementable with two SWAP layers on a line of qubits.
Loading 2602.06171v2…