PaperlayerView exact revision on arXiv

Source-linked AI summary

Performance of hybrid quantum/classical variational heuristics for combinatorial optimization

Giacomo Nannicini

arXiv:1805.12037v3quant-phcs.DM

TL;DR

Practical performance evidence for hybrid quantum/classical variational optimization of combinatorial problems has been limited. The paper tests classical nonlinear optimizers on Hamiltonians for six problem classes using noise-free circuit simulations. It reports that global methods are more reliable than local ones and that Hamiltonian structure is associated with search difficulty.

  • Problem

    The paper addresses limited empirical study of the practical performance of hybrid variational methods on classical combinatorial optimization problems.

    Source: §I · p. 1

  • Method

    The study applies classical nonlinear optimization algorithms to variational Hamiltonian objectives for combinatorial problems using noise-free simulations of quantum circuits.

    Source: §I · p. 1, §II · p. 2

  • Results

    Global optimization appears more reliable than local methods, and ground-state search difficulty is associated with Hamiltonian eigenvalue counts and Pauli-term counts.

    Source: §I · p. 1

  • Takeaways & Limitations

    Distinct eigenvalue counts may provide a quick way to estimate the difficulty of finding a Hamiltonian's ground state with the variational approach.

    Source: §I · p. 1

    The experiments use noise-free classical simulations, and the authors note that conclusions might differ considerably on real hardware.

    Source: §I · p. 1

Abstract

from arXiv · show

The recent literature on near-term applications for quantum computers contains several examples of the applications of hybrid quantum/classical variational approaches. This methodology can be applied to a variety of optimization problems, but its practical performance is not well studied yet. This paper moves some steps in the direction of characterizing the practical performance of the methodology, in the context of finding solutions to classical combinatorial optimization problems. Our study is based on numerical results obtained applying several classical nonlinear optimization algorithms to Hamiltonians for six combinatorial optimization problems; the experiments are conducted via noise-free classical simulation of the quantum circuits implemented in Qiskit. We empirically verify that: (1) finding the ground state is harder for Hamiltonians with many Pauli terms; (2) classical global optimization methods are more successful than local methods due to their ability of avoiding the numerous local optima; (3) there does not seem to be a clear advantage in introducing entanglement in the variational form.

I. INTRODUCTION

The paper examines classical optimization of variational quantum states for combinatorial optimization, using Hamiltonians to encode problem objectives. Its introduction reports that search difficulty varies by problem and Hamiltonian, and that global optimization appears more reliable than local methods.

I. INTRODUCTION

  • The study uses noise-free classical circuit simulations and one variational form, without testing problem-dependent forms.The introduction describes the numerical study as covering six combinatorial optimization problem classes.Source: §I · p. 1, §III · p. 2
  • Global optimization appears more reliable than local methods, while difficulty varies by problem and is associated with Hamiltonian eigenvalue counts and Pauli-term counts.The study also reports that the number of required iterations grows more than linearly with problem size, within experiments of at most 18 qubits.Source: §I · pp. 1–2

II. THE VARIATIONAL APPROACH

  • The variational approach optimizes circuit parameters classically to minimize the Hamiltonian energy of a parameterized quantum state.The ansatz choice and the classical algorithm both matter, and choosing either appropriately is difficult in general.Source: §II · p. 2

III. HAMILTONIANS FOR BINARY OPTIMIZATION PROBLEMS

  • Binary quadratic objectives can be mapped to diagonal Hamiltonians made from weighted products of at most two Z Pauli operators.Constraints can be incorporated by adding sufficiently large quadratic penalties for violations.Source: §III · p. 2

A. Maximum stable set

The maximum stable-set problem seeks the largest set of pairwise nonadjacent vertices in a graph, and its objective penalizes selecting adjacent vertices.

A. Maximum stable set

  • The formulation rewards selected vertices and penalizes selecting two adjacent vertices, yielding a maximum-cardinality stable set.StableSet is a special case of set packing and is among the six basic NP-complete problems discussed in.Source: A. Maximum stable set · p. 3

B. Maximum 3-satisfiability

The paper describes Hamiltonian formulations for Max3SAT, number partitioning, and MaxCut. Max3SAT is represented through a StableSet transformation, while the latter two problems use spin-based formulations.

B. Maximum 3-satisfiability

  • Max3SAT instances with m clauses are transformed into StableSet instances on graphs with 3m vertices for the study.A direct n-spin, 3-local Hamiltonian is possible, but the StableSet transformation supports comparison with random StableSet instances and classical Branch-and-Bound formulations.Source: B. Maximum 3-satisfiability · p. 3

C. Number partitioning

  • Number partitioning seeks a division of the numbers into two sets that minimizes the absolute difference between their sums.The Hamiltonian construction assigns an Ising spin to each number and expands the squared difference.Source: C. Number partitioning · p. 3

D. Maximum cut

  • MaxCut partitions a weighted graph's vertices into two sets to maximize the total weight of edges crossing between them.An Ising spin glass model without field is a weighted MaxCut problem.Source: D. Maximum cut · p. 3

E. Market split

The market split problem assigns customers between two subdivisions to balance their market shares. The TSP formulation uses position-indexed binary variables and has a different scaling requirement from the other test problems.

E. Market split

  • Market split assigns each customer to one of two subdivisions so that each product's market is roughly balanced between them.The paper describes the problem as difficult for classical Branch-and-Bound algorithms [17].Source: E. Market split · p. 3

F. Traveling salesman problem

  • The TSP formulation uses n² binary variables, so its qubit count does not scale linearly with problem size; it is the only test problem with this property.The formulation fixes the first node's position and adds sufficiently large penalties for constraint violations.Source: F. Traveling salesman problem · p. 4

IV. DATA AND EXPERIMENTAL SETUP

The experiments use randomly generated instances for six combinatorial optimization problems. Instance generation is tailored to each problem, and the Hamiltonians are characterized by their term counts and distinct eigenvalues.

A. Generation of random instances

  • The instances are generated for a desired number of qubits, and Table I reports average Hamiltonian-term counts and distinct-eigenvalue counts.The table caption specifies that Hamiltonian terms are tensor products of Pauli Z and values are rounded to the nearest integer.Source: A. Generation of random instances · p. 4, Table I · p. 4
  • The six problem classes use distinct random-instance constructions: StableSet, Max3SAT, Partition, MaxCut, Marketsplit, and TSP.StableSet uses an Erdős–Rényi graph; Max3SAT uses a random formula; Partition uses random integers; MaxCut and TSP use weighted complete graphs; Marketsplit follows a cited procedure.Source: A. Generation of random instances · p. 4

B. Experimental setup

The experiments compare VQE optimization across random instances and problem sizes, using Cplex-computed optima as references. They evaluate selected classical optimizers with data profiles and use matched seeds across algorithms.

B. Experimental setup

  • Across problem types and eligible sizes from 6 to 18 qubits, each setting is repeated 20 times with shared instance and starting-point seeds across algorithms.Max3SAT sizes must be multiples of 3 and TSP sizes perfect squares because of their Hamiltonian formulations.Source: B. Experimental setup · p. 4
  • Cplex 12.7.1 supplies certified optima, and data profiles assess VQE progress toward the corresponding Hamiltonian ground-state values.The ground-state values are computed from optimal 0-1 solutions obtained by Cplex.Source: B. Experimental setup · pp. 4–5
  • The reported optimizer set is COBYLA, RBFOpt, and occasionally LBFGS; PCD and SPSA were slower without adding insight in the noise-free experiments.The study classifies COBYLA and LBFGS as local methods and RBFOpt as global; SPSA's noise robustness was not exploited in this setting.Source: B. Experimental setup · p. 5

C. Analysis of difficulty with classical Branch-and-Bound

Cplex runtimes grow exponentially with problem size for Partition, Marketsplit, and MaxCut, while the other tested classes appear easier. The section also describes a ground-state-spanning variational form built in layers, while cautioning that the classical timing comparison is not state of the art.

C. Analysis of difficulty with classical Branch-and-Bound

  • Partition, Marketsplit, and MaxCut show exponentially scaling Cplex runtimes, while the other problem classes appear considerably easier.The reported average solution times use single-threaded Cplex and are plotted on a logarithmic y-axis.Source: C. Analysis of difficulty with… · p. 5, Figure 2 · p. 6
  • The Cplex timing results are not state of the art because the Hamiltonian-to-QUBO translation was untuned and Cplex used default parameters.The authors characterize the resulting formulations as weak and say improved classical methodologies may substantially improve performance.Source: C. Analysis of difficulty with… · pp. 5–6
  • Dense quadratic forms are associated with greater Cplex difficulty: Marketsplit and Partition are fully dense, followed by MaxCut, while most instances have many negative eigenvalues.The study examines Q density and eigenvalue distributions; Table II reports average density and the fraction of negative eigenvalues.Source: C. Analysis of difficulty with… · p. 6, Table II · p. 6

D. Variational form

  • Experiments use up to three low-depth layers, but RBFOpt is tested only with one or two because three-layer optimization is too time-consuming.The entangling layers allow the study to vary entanglement; the authors note that entanglement is not necessary in principle for 0-1 optimization because an optimal solution can be a computational basis state.Source: D. Variational form · p. 6
  • The variational form spans the ground state: an initial layer of single-qubit Y rotations can generate any binary string, and later layers add controlled-Z gates and Y rotations.The illustrated circuit has three qubits; each layer has one parameter per qubit, and nearest-neighbor controlled-Z gates did not change the study's conclusions.Source: D. Variational form · p. 6, Figure 3 · p. 6

V. RESULTS AND ANALYSIS

Across the tested instances, global optimization continues to converge where local methods plateau, but high accuracy remains difficult for many instances. Performance also varies substantially by problem class, and adding layers does not show a clear benefit.

A. Convergence versus number of iterations

  • Convergence is measured against tolerance τ, and iteration counts are normalized as equivalent gradient iterations using n + 1 function evaluations per iteration.For q qubits and ℓ layers, the variational form has n = qℓ parameters; the maximum evaluation budget is 100(n + 1).Source: A. Convergence versus number of… · p. 7
  • COBYLA plateaus while RBFOpt continues improving and ultimately converges on more instances; all algorithms still miss high accuracy on many instances.LBFGS behaves similarly to COBYLA, suggesting local methods become stuck in local minima.Source: A. Convergence versus number of… · p. 7, Figure 4 · p. 7
  • The apparent effect of extra variational layers depends on the optimizer, so the experiments do not establish that their added entanglement helps.Two-layer plots suggest extra layers may help local methods but hinder RBFOpt, possibly because it performs better with fewer parameters.Source: A. Convergence versus number of… · p. 7, Figure 5 · p. 8
  • Max3SAT is easiest for all tested optimizers, while Marketsplit, Partition, and to a lesser extent MaxCut and TSP are hardest.This difficulty ranking matches that obtained with classical Branch-and-Bound.Source: A. Convergence versus number of… · p. 7, Figure 5 · p. 8
  • Different problem classes show different difficulty levels regardless of optimizer, with performance varying in a way that resembles classical Branch-and-Bound.The authors note that instance-generation procedures may contribute to the differences.Source: A. Convergence versus number of… · p. 8

B. Density and eigenvalues

Experiments with random Hamiltonians indicate that distinct eigenvalue count is more informative about optimization difficulty than Pauli-term count alone. The relationship between terms and difficulty depends on the weight distribution, and eigenvalue count may be difficult to compute in practice.

B. Density and eigenvalues

  • Harder problems tend to have more distinct eigenvalues and more Hamiltonian terms, although TSP is an exception to the apparent eigenvalue-count pattern.The authors identify investigating these relationships as a motivation for further experiments.Source: B. Density and eigenvalues · p. 8, Table III · p. 8
  • Density is not a good difficulty indicator, while the number of distinct eigenvalues is; beyond small Hamiltonians, Pauli-term count alone has no strong correlation with difficulty.With weights in [−1, 1], distinct eigenvalues saturate at about 30 Pauli terms, limiting further increases in difficulty expected from term count.Source: B. Density and eigenvalues · pp. 8–9, Figure 6 · p. 9
  • For the same Pauli-term count, Hamiltonians with weights in [−1, 1] and more distinct eigenvalues take longer to converge than those with weights in {−1, 1}.A Friedman test rejected the no-difference null hypothesis (p-value 1.11e−16); Table IV reports a subset of pairwise comparisons.Source: B. Density and eigenvalues · p. 9, Table IV · p. 9
  • The experiments suggest that difficulty increases with distinct eigenvalue count, while its relationship to Pauli-term count depends on the weight distribution.Computing the distinct eigenvalue count is not easy unless the Hamiltonian is known in the full Hilbert space.Source: B. Density and eigenvalues · p. 9

C. Impact of problem size

As qubit count increases, aggregate convergence declines slightly, though the trend varies by problem class. Approximation-ratio results show substantial differences across problems and algorithms.

C. Impact of problem size

  • The aggregate convergence rate declines slightly as qubit count rises, suggesting that a linear increase in allowed iterations is insufficient to maintain high-accuracy convergence.The study does not establish the iteration scaling needed to maintain a constant convergence fraction.Source: C. Impact of problem size · p. 9, Figure 7 · p. 10
  • Convergence does not deteriorate with problem size on Partition or TSP, but does on the remaining problem classes.The class-specific plots separate these exceptions from the aggregate downward trend.Source: C. Impact of problem size · p. 10, Figure 8 · p. 10

D. Approximation ratio

  • On MaxCut, RBFOpt eventually approaches an approximation ratio of 1 while local solvers remain at ≥1.05; all algorithms reach near 1 quickly on Max3SAT.On TSP, ratios fall from ≈10^3 to ≤10, but no algorithm reaches 1; penalty costs from infeasible starting points explain the large initial ratios.Source: D. Approximation ratio · pp. 10–11, Figure 9 · p. 11

E. Probability of sampling the optimal solution

The paper examines whether optimization finds states likely to yield optimal binary solutions, not only states with low energy. Local algorithms quickly plateau, while global search explores qualifying states on more instances, though its optimistic curves may overstate what it can detect.

E. Probability of sampling the optimal solution

  • A state can have high probability of sampling an optimal binary string even when its energy exceeds the optimum, so energy and optimal-solution sampling probability are distinct measures.The energy is the expected objective value of binary solutions sampled from the state.Source: E. Probability of sampling the optimal… · p. 11
  • Local COBYLA quickly plateaus in the fraction of instances with states likely to yield the optimum, while RBFOpt’s fraction rises steadily as iterations increase.The plotted measure counts whether an algorithm has explored a qualifying state, not whether it detects or stops at that state; this can especially affect global search.Source: E. Probability of sampling the optimal… · pp. 11–12, Figure 10 · p. 12, Figure 11 · p. 12
  • Results vary sharply by problem class: some are quickly solved to high optimal-sampling probability, while others remain difficult, especially for local algorithms.The authors note that optimizing expected objective value may not be best when the goal is only a target probability of sampling an optimum.Source: E. Probability of sampling the optimal… · p. 12, Figure 11 · p. 12

F. Entanglement vs. no entanglement

Tests comparing entangling and non-entangling variational forms show no clear overall benefit from two-qubit gates in this setting. The conclusions also identify local minima, slow scaling, and problem-agnostic modeling as obstacles for VQE on combinatorial problems.

F. Entanglement vs. no entanglement

  • For COBYLA and LBFGS, two- and three-layer forms perform essentially alike with CZ entanglers or T gates; RBFOpt still performs best with 1L.The comparison covers convergence and probability of sampling an optimum; for local solvers, multilayer forms appear better than 1L, but CZ and T variants show no significant difference.Source: Figure 13 · p. 13, Figure 14 · p. 13, F. Entanglement vs. no entanglement · p. 13
  • The experiments are inconclusive but show no observed advantage from two-qubit gates over single-qubit-only forms in this setting.The authors suggest performance differences may reflect algorithms’ response to additional variational parameters rather than entanglement itself.Source: F. Entanglement vs. no entanglement · p. 13

VI. CONCLUSIONS

  • Local optimizers often get trapped in local minima on some problem classes, and convergence to the optimum requires more iterations as problem size grows.The authors suggest nonconvex optimization methods, different variational forms, or quantum-computed derivatives as possible ways to address these obstacles.Source: §VI · p. 14
  • VQE performs well only on problem classes where a naive classical Branch-and-Bound translation also performs well, limiting its advantage on harder classes.The authors suggest systematically exploiting problem structure rather than using problem-agnostic VQE.Source: §VI · p. 14
Loading 1805.12037v3…