PaperlayerView exact revision on arXiv

Source-linked AI summary

Filtering variational quantum algorithms for combinatorial optimization

David Amaro, Carlo Modica, Matthias Rosenkranz, Mattia Fiorentini, Marcello Benedetti, Michael Lubasch

arXiv:2106.10055v3quant-ph

TL;DR

Making combinatorial optimization more efficient on gate-based quantum hardware matters because even slight quantum speedups could affect industry and research. The paper introduces filtering-based variational algorithms and tests them on random weighted MaxCut problems. F-VQE outperforms VQE and QAOA in the reported comparisons, while HE-ITE obtains similar results with fewer qubits; F-VQE is also demonstrated on a trapped-ion processor.

  • Problem

    Making combinatorial optimization more efficient matters because even slight quantum speedups could have large impacts across industry and research.

    Source: §I · p. 1

  • Method

    QVF and F-VQE variationally approximate repeated filtering, while HE-ITE combines imaginary-time evolution with causal cones to reduce circuit qubit requirements.

    Source: §I · pp. 1–2, E. Causal cones · p. 5, §IV · p. 9

  • Results

    F-VQE achieved larger, more consistent approximation ratios and more reliable convergence than VQE and QAOA with fewer optimization steps; HE-ITE obtained similar results with drastically reduced qubit count, and F-VQE solved a 9-qubit MaxCut problem on the Honeywell H1 processor.

    Source: §IV · p. 9

  • Takeaways & Limitations

    F-VQE and HE-ITE are reported as powerful approaches for combinatorial optimization on noisy quantum computers.

    Source: §IV · p. 9

Abstract

from arXiv · show

Current gate-based quantum computers have the potential to provide a computational advantage if algorithms use quantum hardware efficiently. To make combinatorial optimization more efficient, we introduce the Filtering Variational Quantum Eigensolver (F-VQE) which utilizes filtering operators to achieve faster and more reliable convergence to the optimal solution. Additionally we explore the use of causal cones to reduce the number of qubits required on a quantum computer. Using random weighted MaxCut problems, we numerically analyze our methods and show that they perform better than the original VQE algorithm and the Quantum Approximate Optimization Algorithm (QAOA). We also demonstrate the experimental feasibility of our algorithms on a Honeywell trapped-ion quantum processor.

I. INTRODUCTION

Filtering-based methods target combinatorial optimization by increasing low-energy-state weight, and the reported MaxCut comparisons favor F-VQE over VQE and QAOA while HE-ITE uses fewer qubits.

I. INTRODUCTION

  • Even slight quantum speedups on combinatorial optimization problems could have large impacts across industry and research.Motivating applications include delivery routing, logistics storage, and manufacturing supply chains.Source: §I · p. 1

A. Filtering operators

  • Filtering operators reduce high-energy-state weight and increase ground-state overlap; QVF and F-VQE allow ansätze chosen for the available hardware.Imaginary-time evolution is one example of a filtering operator, and the study identifies it as the best-performing filter among those usable with causal cones.Source: §I · pp. 1–2

I. INTRODUCTION

  • F-VQE achieves larger, more consistent approximation ratios than VQE and QAOA in fewer optimization steps, while HE-ITE achieves similar results with fewer qubits and gates.The comparisons use random weighted MaxCut problems; Fig. 1 summarizes algorithm performance and causal-cone widths.Source: Figure 1 · p. 1, §I · p. 2

B. Quantum Variational Filtering (QVF)

QVF variationally approximates repeated filtering of an initial state by iteratively optimizing a parameterized circuit toward each filtered state.

B. Quantum Variational Filtering (QVF)

  • QVF starts from a state with finite ground-state overlap and iteratively approximates the filtered state at each optimization step.The filtering operator may change between steps, and the algorithm stops after a chosen number of steps.Source: B. Quantum Variational Filtering (QVF) · p. 3
  • At each step, QVF minimizes the Euclidean distance between the ansatz state and the state produced by applying the filter to the previous state.The resulting optimized parameter vector defines the state for that step.Source: B. Quantum Variational Filtering (QVF) · p. 3
  • The QVF cost can be minimized using a Hadamard test, which requires an additional ancilla qubit and controlled operations.The passage identifies this as an added quantum-resource cost of QVF.Source: B. Quantum Variational Filtering (QVF) · p. 3

C. Filtering VQE (F-VQE)

F-VQE avoids QVF’s added Hadamard-test resources by using a gradient-based update that requires essentially the same circuits as VQE.

C. Filtering VQE (F-VQE)

  • F-VQE avoids the Hadamard-test resources required by QVF and uses essentially the same circuits as VQE.Its procedure performs one gradient-descent update per optimization step.Source: C. Filtering VQE (F-VQE) · pp. 3–4
  • F-VQE computes partial derivatives using parameter-shifted ansatz states, with a shared denominator across derivatives at a fixed step.The parameter-shift rule is used to evaluate the gradient at the current parameter vector.Source: C. Filtering VQE (F-VQE) · p. 3
  • Each F-VQE optimization step evaluates 2m + 1 circuits, and the samples for the filter expectation also provide the average energy at no extra cost.The algorithm uses computational-basis sampling for the diagonal QUBO Hamiltonians considered in the article.Source: C. Filtering VQE (F-VQE) · p. 4
  • The F-VQE gradient matches a modified VQE gradient only at the current state under stated assumptions; their second derivatives differ.The algorithms therefore explore parameter landscapes with different curvatures.Source: C. Filtering VQE (F-VQE) · p. 4

D. Adapting τ

F-VQE adapts τ by targeting a desired gradient norm, rather than simply rescaling the gradient.

D. Adapting τ

  • The τ choice is motivated by avoiding vanishing gradients and estimating their value more accurately with a fixed measurement count.The method adapts τ through the filter expectation value, which enters both the cost and its gradient.Source: D. Adapting τ · p. 4
  • F-VQE selects τ to keep the gradient norm as close as possible below a fixed threshold at each optimization step.The heuristic searches for a τ that solves g(τt) = gc, using a range search or the tried value closest below threshold if the norm saturates.Source: D. Adapting τ · p. 4
  • The τ heuristic is not constant gradient rescaling: individual partial derivatives change non-trivially with τ, while simulations show consistent gradient-norm dependence across steps and problems.Figure 3 plots the norm and selected partial derivatives against τ for one 13-qubit MaxCut problem.Source: D. Adapting τ · pp. 4–5, Figure 3 · p. 4

E. Causal cones

Causal cones restrict expectation-value evaluation to qubits and gates that affect the observable, and can reduce hardware requirements for small-support observables. The section also specifies the weighted MaxCut instances and Hamiltonian scaling used in the study.

E. Causal cones

  • For small-support observables, causal cones can reduce the required number of gates and qubits; cones for distant qubits split into independently realizable parts.The exponential, power, and Chebyshev filters can use causal cones, with the latter two evaluated as sums of simpler local-observable expectations.Source: E. Causal cones · p. 5

III. RESULTS

  • The numerical studies and Honeywell H1 trapped-ion experiment were compiled using TKET.The results section describes the simulation and experimental settings before analyzing algorithm performance.Source: §III · p. 5

A. Weighted MaxCut Hamiltonians

  • The study uses 25 random weighted 3-regular connected graphs per size, with n∈{5, 7, 9, 11, 13, 23} qubits and edge weights uniform on [0, 1].Each graph has N=n+1 vertices; fixing the last vertex's cut label to +1 removes the symmetry between the two subsets.Source: A. Weighted MaxCut Hamiltonians · p. 5
  • MaxCut variables are replaced by Pauli Z operators to form a Hamiltonian whose ground state represents an optimal cut; the cost range is rescaled to [0, 1].The upper bound is the optimum of the semidefinite-programming relaxation, and the lower bound is the trivial-cut cost 0.Source: A. Weighted MaxCut Hamiltonians · p. 5

B. Setup

The setup compares F-VQE, HE-ITE, VQE, and QAOA through their circuit and optimization settings. It also describes a 9-qubit Honeywell experiment and a simulation comparison across random weighted MaxCut instances.

Circuit settings

  • F-VQE and HE-ITE use the Fig. 4(a) parameterized circuit, while VQE uses that same ansatz and QAOA uses the circuit in Eq. (12).The Fig. 4 caption describes F-VQE sampling the full circuit for a global observable and HE-ITE using causal cones for 2-local observables.Source: B. Setup · pp. 5–7, Figure 4 · p. 6

Experimental settings

  • For the 9-qubit Honeywell H1 experiment, the ansatz removes all rotation gates except the first and last on each qubit.The experimental settings are distinguished from the simulation settings in Table I.Source: Table I · p. 6, B. Setup · p. 6

F-VQE and HE-ITE settings

  • F-VQE prepares |+⟩^⊗n, adapts τ during optimization, and uses the inverse Hessian diagonal as its learning rate; HE-ITE uses one layer and fixed τ=1.0.For HE-ITE's 23-qubit problems, each causal cone uses 2^(ncone+2) measurement shots.Source: B. Setup · p. 6, Table I · p. 6

VQE and QAOA settings

  • VQE's analytical gradient requires two quantum circuits per parameter, whereas QAOA uses analytical gradient descent with a fixed learning rate η=1.The QAOA parameters are initialized randomly in [0, π], and the learning rate was selected by comparing η=1, 0.1, and 0.01 on 5-qubit instances.Source: B. Setup · pp. 6–7

Simulation results

  • For approximation ratio 0.75, 25 instances succeeded for every algorithm and problem size except QAOA, which succeeded on 17, 22, 21, 9, and 3 of 25 instances for n=5, 7, 9, 11, and 13.Figure 5 also reports approximation-ratio means and standard deviations, optimization-step distributions, and fractions of instances with ground-state measurement probability above 0.25.Source: Figure 5 · p. 7

Learning-rate choice

  • The Hessian-diagonal learning-rate heuristic often diverged when diagonal elements vanished, so the simulations and experiments instead fixed η=1.The comparison of η=1, 0.1, and 0.01 was performed on 5-qubit MaxCut instances.Source: B. Setup · p. 7

C. Performance

F-VQE with the inverse filter outperforms VQE and QAOA on convergence, while HE-ITE also performs near optimally with circuits using at most six qubits. The study additionally reports results for HE-ITE across imaginary-time steps and an F-VQE experiment on a trapped-ion processor.

C. Performance

  • A high approximation ratio does not necessarily mean frequent ground-state sampling: a superposition of low-energy excited states can score highly while having low ground-state probability.The study therefore tracks both quantities.Source: C. Performance · p. 7
  • The best-performing filters achieve larger approximation ratios with smaller standard deviations, while all filters reach an approximation ratio above 0.75 within five optimization steps.The best filters also achieve ground-state sampling probability above 0.25 for a larger fraction of instances.Source: C. Performance · pp. 7–8
  • With total imaginary time 100, smaller τ systematically improves HE-ITE across 25 random weighted MaxCut instances; Figure 6 reports approximation ratios and the fraction exceeding a 0.25 ground-state probability.Approximation ratios are shown as averages with standard-deviation error bars.Source: Figure 6 · p. 8, C. Performance · p. 8
  • F-VQE with the inverse filter requires fewer optimization steps than VQE and QAOA while achieving larger, more consistent approximation ratios and more frequent ground-state convergence across problem sizes.The comparison is reported for random weighted MaxCut instances.Source: C. Performance · p. 8
  • HE-ITE achieves approximation ratios close to optimal and frequently reaches the ground state on 23-qubit instances using circuits of at most six qubits, with most circuits using four.The reported results cover 25 MaxCut instances.Source: C. Performance · p. 8
  • 0.9844±0.0062 final approximation ratio and 0.928±0.024 final ground-state sampling probability were obtained on one 9-qubit Honeywell H1 instance.The ± values are 95% confidence intervals.Source: Figure 7 · p. 8, C. Performance · p. 8

IV. CONCLUSIONS AND OUTLOOK

F-VQE and HE-ITE are evaluated against VQE and QAOA on random weighted MaxCut problems, with reported gains in convergence or qubit use. The conclusion also outlines possible extensions to other target states, black-box costs, and broader applications.

IV. CONCLUSIONS AND OUTLOOK

  • QVF approximates repeated filtering, while F-VQE is its efficient VQE-like case; both allow hardware-suitable ansatz circuits, and HE-ITE can use causal cones to reduce circuit size.HE-ITE approximates imaginary time evolution.Source: §IV · pp. 8–9
  • F-VQE achieved larger, more consistent approximation ratios and more reliable convergence than VQE and QAOA, while HE-ITE used drastically fewer qubits at similar performance.F-VQE also solved a 9-qubit MaxCut problem on Honeywell’s H1 trapped-ion processor.Source: §IV · p. 9
  • Possible improvements include CVaR-based filters, local costs, shallow or alternative ansätze, noise-aware selection, adaptive circuit growth, and optimizer or parameter-schedule changes.The passage presents these as strategies to explore, not established improvements.Source: §IV · p. 9
  • A modified filter f(|H − Etarget|; τ) could target a chosen energy, including a specific excited state, rather than only the ground state.Source: §IV · p. 9
  • QVF and F-VQE can optimize black-box costs mapping binary bitstrings to values, without requiring a QUBO representation; another representation might reduce qubit count.Source: §IV · p. 9
  • The authors point to filtering for quantum-Hamiltonian ground states and to quantum-inspired classical algorithms as further application areas.They also identify possible uses in tensor-network methods and related scientific computations.Source: §IV · p. 9

Appendix A: Hadamard test for QVF

The appendices describe a Hadamard-test evaluation for QVF and analytical derivative procedures for QVF, F-VQE, VQE, and QAOA. For QVF and F-VQE, the derivation uses parameterized rotation gates and parameter shifts.

Appendix A: Hadamard test for QVF

  • The QVF cost and gradient require overlaps of the form ⟨ψ(φ)|Ft|ψ(θ)⟩, evaluated with a Hadamard test using Zanc ⊗ Ft.The test uses an ancilla and an n-qubit register.Source: Appendix A · p. 10

Appendix B: Analytical derivatives

  • The analytical-gradient derivation uses the parameter-shift rule for F-VQE and also applies the procedure to VQE and QAOA.Source: Appendix B · p. 10

1. QVF and F-VQE

  • For QVF and F-VQE, each parameter occurs in a rotation gate RG(θj)=exp(−iθjG/2), with G a Pauli operator or a tensor product of Pauli operators.The circuit is expressed using fixed unitaries around the parameter’s rotation gate, acting on the initial register state |0⟩.Source: §1 · p. 10
  • The cost-function derivatives are evaluated at θt−1; because Ft is Hermitian, the gradient numerator can be expressed as a sum of two circuits using the parameter-shift rule.Source: §1 · p. 10

2. VQE

For VQE, the cost is the ansatz state’s average energy, and each parameter appears in one rotation gate. This structure permits parameter-shift evaluation of derivatives.

2. VQE

  • VQE uses the average energy ⟨H⟩ψ(θ) as its cost and the same ansatz circuit as F-VQE.Source: §2 · p. 10
  • Because each parameter appears in only one rotation gate, the analytical gradient can be evaluated by shifting θj by ±π/2.Source: §2 · p. 10
  • The same methods evaluate each parameter’s second derivative; the derivation identifies the unshifted state and the state with a +π shift.Source: §2 · p. 10

3. QAOA

The QAOA derivative procedure accounts for parameters multiplying sums of Pauli products, so gradient components require multiple circuit evaluations. The accompanying figure describes a Hadamard-test circuit for a parameterized circuit.

3. QAOA

  • QAOA parameters multiply sums of tensor products of Pauli operators, so their ansatz derivatives become sums of circuit evaluations.Source: §3 · pp. 10–11
  • Figure 8’s Hadamard-test circuit computes Re ⟨ψ(φ)|Ft|ψ(θ)⟩; it shows one layer, with θ′=φ−θ.Source: Figure 8 · p. 11
  • The parameter-shift rule applied term by term gives the analytical QAOA gradient from circuits with varied parameter sets.Source: §3 · p. 11
  • Evaluating all gradient components requires 2p(n+K) circuits, formed by inserting a rotation gate into the ansatz.Source: §3 · p. 11

Appendix C: Experimental details

The appendix documents a Honeywell H1 trapped-ion experiment on a 10-node weighted MaxCut problem, including its solution encoding and the circuit used and compiled for the processor.

Appendix C: Experimental details

  • The experiment maps the 10-node MaxCut solution to the 9-qubit computational state |011001011⟩.The corresponding 10-variable solution vector is (1, −1, −1, 1, 1, −1, 1, −1, −1, −1); Tab. II lists the graph weights, including edge (4, 10) at 0.9927.Source: Appendix C · pp. 11–12, Table II · p. 12
  • The experimental F-VQE circuit uses one layer, with two single-qubit rotation gates per qubit, and is simpler than the simulation circuits.Figure 9(b) shows the circuit and Fig. 9(c) its compiled counterpart.Source: Appendix C · p. 11, Figure 9 · p. 12
  • Compilation converts the circuit to Honeywell H1 native gates: Z-axis rotations, PX rotations in the X-Y plane, and Uzz two-qubit interactions.The original two-qubit gates also change the single-qubit rotation angles during compilation.Source: Appendix C · p. 11, Figure 9 · p. 12

Related papers

Loading 2106.10055v3…