PaperlayerView exact revision on arXiv

Source-linked AI summary

Challenges and Opportunities in Quantum Optimization

Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, Gerhard Kircher, Thomas Kleinert, Thorsten Koch, Georgios Korpas, Steve Lenk, Jakub Marecek, Vanio Markov, Guglielmo Mazzola, Stefano Mensa, Naeimeh Mohseni, Giacomo Nannicini, Corey O'Meara, Elena Peña Tapia, Sebastian Pokutta, Manuel Proissl, Patrick Rebentrost, Emre Sahin, Benjamin C. B. Symons, Sabine Tornow, Victor Valls, Stefan Woerner, Mira L. Wolf-Bauwens, Jon Yard, Sheir Yarkoni, Dirk Zechiel, Sergiy Zhuk, Christa Zoufal

arXiv:2312.02279v3quant-phmath.OC

TL;DR

Whether quantum optimization can deliver practical advantage remains an open question. This paper surveys complexity theory, algorithms, hardware scaling, and benchmarking, concluding that complexity-theoretic guarantees may not identify practical advantage.

  • Problem

    The potential for quantum advantage in unconstrained discrete optimization remains open, alongside questions about problem formulations, encodings, and quantum-specific preprocessing.

    Source: §1 · p. 17

  • Method

    The paper synthesizes complexity theory, optimization algorithms and problem classes, noisy-hardware scaling, benchmarking, and illustrative application domains.

    Source: §VIII · p. 51

  • Results

    The review concludes that complexity theory can guide provable guarantees but may not reveal practical quantum advantage, underscoring the need to analyze heuristics.

    Source: §VIII · p. 51

  • Takeaways & Limitations

    Analyzing quantum optimization heuristics and benchmarking them are important for understanding their effectiveness and identifying quantum advantages.

    Source: §VIII · p. 51

    The factoring-related exponential speedup applies to special QUBO instances not expected to arise naturally, and harnessing that relation for optimization remains open.

    Source: C. Quantum Phase Estimation · p. 11

Abstract

from arXiv · show

Recent advances in quantum computers are demonstrating the ability to solve problems at a scale beyond brute force classical simulation. As such, a widespread interest in quantum algorithms has developed in many areas, with optimization being one of the most pronounced domains. Across computer science and physics, there are a number of different approaches for major classes of optimization problems, such as combinatorial optimization, convex optimization, non-convex optimization, and stochastic extensions. This work draws on multiple approaches to study quantum optimization. Provably exact versus heuristic settings are first explained using computational complexity theory - highlighting where quantum advantage is possible in each context. Then, the core building blocks for quantum optimization algorithms are outlined to subsequently define prominent problem classes and identify key open questions that, if answered, will advance the field. The effects of scaling relevant problems on noisy quantum devices are also outlined in detail, alongside meaningful benchmarking problems. We underscore the importance of benchmarking by proposing clear metrics to conduct appropriate comparisons with classical optimization techniques. Lastly, we highlight two domains - finance and sustainability - as rich sources of optimization problems that could be used to benchmark, and eventually validate, the potential real-world impact of quantum optimization.

I. INTRODUCTION … 3. Hard versus complete problems

The paper surveys quantum optimization’s potential and practical limits, then uses complexity theory to frame where quantum advantage may arise and what formal separations can—and cannot—show.

I. INTRODUCTION

  • The paper examines quantum optimization through complexity, algorithm design, noisy-device execution, fair benchmarking, and real-world applications, stressing complementarity with classical methods.It proposes reproducible comparison metrics and discusses finance and sustainability as application domains for benchmarking and eventual validation.Source: §I · pp. 2–3
  • Noise motivates error mitigation as a possible bridge between today’s noisy quantum devices and fault-tolerant quantum computing for optimization.Fault tolerance through error correction entails significant qubit overhead; mitigation combines multiple noisy results to reduce noise.Source: §I · p. 3

II. QUANTUM ADVANTAGE & COMPLEXITY THEORY

  • Complexity theory guides the search for quantum advantage, but strict complexity separations are difficult to prove and are not necessary or sufficient to establish practical advantage.Quantum factoring by Shor’s algorithm is an example of an expected quantum efficiency without a formal proof that classical efficient factoring is impossible.Source: §II · p. 3

1. Decision and relational problems

  • Decision problems ask whether a solution exists, whereas relational problems require producing a valid solution, a distinction central to practical optimization.For TSP, a decision procedure can help find a minimum-length tour, but the actual route—not merely its existence—is needed in practice.Source: §1 · pp. 3–4

2. Deterministic, randomized and quantum computation

  • P and PO capture polynomial-time decision and optimization problems, while FP covers polynomial-time solution-finding; BQP allows quantum polynomial-time decisions with bounded error.Polynomial-time scaling alone does not settle practical efficiency: the polynomial’s degree and constants matter.Source: §2 · p. 4

Are quantum algorithms strictly more powerful than randomized algorithms?

  • Although oracle-relative results place some problems in BQP but not BPP, no conclusive proof separates quantum from randomized computation, and practical implications remain unclear.The passage notes that resolving the question is tied to the difficulty of proving PSPACE ≠ P.Source: Are quantum algorithms strictly more… · p. 4

3. Hard versus complete problems

  • Optimization problems in NP are NPO and NPO ⊂ FNP; NP-complete problems are hardest in NP, while QMA describes quantum-verifiable decision problems with QMA-complete variants.TSP and Graph Colorability are examples of NP-complete problems.Source: §3 · p. 5
  • The counting class #P relates to computing partition functions; PP is its decision analogue, and QMA ⊆ PP.The passage also notes #P in connection with a Gaussian Boson Sampling experiment.Source: §3 · p. 5

Can quantum computers solve NP-hard … Complexity theory is traditionally focused on worst-case

Worst-case complexity gives little reason to expect exponential quantum speedups across all NP-hard instances, but structure and parameterization may make practically relevant classes tractable. Oracle results leave BQP’s place in the polynomial hierarchy open while separating NISQ from BPP and BQP relative to an oracle.

problems?

  • Grover’s search is optimal in the black-box setting [1]; for an n-variable SAT formula, searching all 2^n assignments gives at most a quadratic speedup over classical unstructured search procedures.Source: problems? · p. 5

Can quantum computers solve NP-hard

  • For general instances, the discussion favors quantum algorithms that exploit structure arising in practice over attempts to find fast algorithms for every instance [32].This recommendation follows from the limited speedup expected for unstructured SAT search.Source: problems? · p. 5

4. Polynomial Time Hierarchy

  • Oracle-relative results leave open whether BQP is in PH, while an oracle separates BPP, NISQ, and BQP as BPP^O ⊊ NISQ ⊊ BQP^O.PH is built from levels formed by access to NP oracles.Source: §4 · pp. 5–6
  • Exponential quantum speedups are considered unlikely for NP-hard and NPO-hard problems, but remain possible for NP-intermediate problems such as decision versions of factoring.NP-intermediate problems lie outside P and within NP but are not NP-complete.Source: §4 · p. 6
  • Optimization classifications distinguish related formulations: relational TSP is FPNP-complete, MAX-SAT is NPO-complete, and Vertex-Cover and Bin-Packing are not NPO-complete despite NP-complete decision versions.These examples show that decision and optimization versions can occupy different complexity classes.Source: §4 · p. 6

Complexity theory is traditionally focused on worst-case

  • Worst-case results can miss easier typical instances: quantum computers may achieve exponential speedups on practically relevant instances that require exponential time classically.This possibility can hold even when worst-case complexity rules out quantum advantage for NP-hard problems.Source: Complexity theory is traditionally… · p. 6

5. Worst-case complexity and fixed-parameter tractability

  • Parameterization can make NP-hard instances fixed-parameter tractable; Vertex-Cover has an O(n) algorithm for constant-size covers, and FPQT denotes quantum-tractable parameterized decision problems [45].The dependence on the parameter may still be exponential in 1/ϵ.Source: Complexity theory is traditionally… · p. 6
  • Kernelization reduces parameterized instances before solving them, and the paper identifies kernels as important optimization benchmarks for FPT problems [46, Theorem 1.4].Many combinatorial optimization problems have polynomial kernels, making it sensible to benchmark FPT problems on the kernel.Source: Complexity theory is traditionally… · p. 6

B. Approximate Solutions … III. PARADIGMS IN THE DESIGN OF QUANTUM OPTIMIZATION ALGORITHMS

Approximation can make optimization useful without exact solutions, but many hard problems remain just as difficult to approximate; structured instances and heuristics may still offer opportunities for quantum advantage. The section also introduces core algorithmic paradigms and identifies open questions about average-case complexity, approximation, and quantum optimization.

B. Approximate Solutions

  • Approximation may suffice in practice, but for many hard problems, finding an approximate solution can be as difficult as finding the optimum.The approximation ratio measures solution quality relative to the optimum; hardness bounds may be unconditional or conditional on P̸ = NP. The quantum PCP conjecture concerns QMA-hardness of approximating sparse, bounded-norm k-local Hamiltonians with a constant relative promise gap; NLTS provides supporting evidence, but does not imply the conjecture’s converse under QMA ≠ NP.Source: B. Approximate Solutions · pp. 6–7, §1 · p. 7

1. Hardness of approximation

  • MAX-E3-SAT has a 7/8 approximation, while improving it classically beyond 7/8 is NP-hard unless P=NP; MAXCUT achieves ≈0.87856, tight under UGC.Improving these established ratios quantumly would imply NP-hard problems can be solved quantumly or, for MAXCUT, that the Unique Games Conjecture is false.Source: §1 · p. 7

2. Polynomial-time approximation schemes

  • APX contains NPO problems with constant-factor polynomial-time approximations; PTAS approaches 1 + ϵ, while FPTAS also runs polynomially in 1/ϵ.Euclidean TSP is in PTAS; quantum algorithms could provide new approaches or improve classical schemes.Source: §2 · p. 8

C. Heuristics in Quantum Optimization

  • Quantum heuristics target reasonable solutions on useful or typical instances without provable performance or runtime guarantees, and formal distributional definitions include HeurBPP and HeurBQP.Reported super-polynomial quantum advantages for NPO approximation rely on specially constructed factoring-derived instances [66] [67], not general-purpose optimization solvers.Source: C. Heuristics in Quantum Optimization · p. 8
  • Variational quantum algorithms can face exponentially flat barren-plateau landscapes that obstruct scaling, though a sufficiently good warm start may avoid them.Proposed causes include t-design-like ansätze, entanglement with partial measurements, dynamical Lie algebra structure, and induced light-cone behavior; choosing a good warm start is often unclear.Source: C. Heuristics in Quantum Optimization · pp. 8–9

D. Takeaways from Complexity Theory in Quantum Optimization

  • Average-case instances may permit quantum speedups beyond Grover; evidence includes faster random k-SAT [91], while OGP hardness for certain classical and low-depth quantum families leaves higher-depth approaches unresolved.Open questions include quantum saturation of unreached inapproximability bounds and speedups when classical approximation ratios cannot improve; problem structure can also change complexity dramatically, as Euclidean TSP’s PTAS illustrates.Source: D. Takeaways from Complexity Theory in… · p. 9
  • Problem structure changes the optimization landscape: general TSP is NP-hard and APX-hard, Euclidean TSP has a PTAS, and practical TSP heuristics handle millions of variables.Shortest path is in P; exploiting structure or enhancing classical approaches with quantum heuristics remains challenging.Source: D. Takeaways from Complexity Theory in… · p. 9

III. PARADIGMS IN THE DESIGN OF QUANTUM OPTIMIZATION ALGORITHMS

  • The paper introduces Grover (Adaptive) Search [97], the Quantum Adiabatic Algorithm, and Quantum Imaginary Time Evolution as core approaches to exact quantum optimization.These concepts serve as subroutines in quantum optimization algorithms discussed later in the paper.Source: §III · p. 9

A. Grover Search … F. Variational Methods

These sections survey exact and heuristic quantum optimization methods, explaining their mechanisms, potential advantages, and limits. They also describe Gibbs-sampling applications and variational approaches, whose practical value depends on computational and implementation constraints.

A. Grover Search

  • Grover search offers a quadratic query advantage, but its speedup over the best classical algorithm is usually sub-quadratic unless combined with other methods.Without additional problem assumptions, the quadratic advantage is the best general-case runtime improvement for discrete optimization; Grover-based subroutines can sometimes recover an overall quadratic speedup over the best exact classical algorithm.Source: A. Grover Search · p. 10

B. Quantum Adiabatic Algorithm

  • QAA slowly interpolates from an easily prepared mixing-Hamiltonian ground state to the problem-Hamiltonian ground state, with runtime scaling as O(1/∆^2).In the glassy phase, the gap can close exponentially with system size, implying exponentially long runtimes for precise adiabatic following and limiting speedups to at most polynomial; practical variants include finite-time, diabatic, and counter-diabatic annealing, while gate-based evolution can use Trotterization.Source: B. Quantum Adiabatic Algorithm · p. 10

C. Quantum Phase Estimation

  • QPE can find Hamiltonian ground states, but optimization use depends on a polynomial-overlap initial state; its factoring speedup applies only to QUBOs encoding factoring instances.Such instances are not expected to arise naturally, and diagonal Hamiltonians do not gain ground-state sampling probability from QPE; matrix tools including quantum signal processing, singular value transformation, and block encoding support broader applications.Source: C. Quantum Phase Estimation · pp. 10–11

D. Gibbs Sampling

  • Quantum Gibbs sampling is believed to be at least QMA-hard, and efficient state preparation is challenging, motivating variational and other approximate approaches.Variational methods include free-energy objectives, adaptive ansätze, and imaginary-time simulation, but can require entropy computation or accurate propagation; unbiased-sampling algorithms have outperformed classical Markov chains in some scenarios, while dissipative sampling uses local updates and may suit near-term hardware.Source: D. Gibbs Sampling · pp. 11–12
  • Gibbs states can support quantum speedups in convex and semidefinite optimization, including block-encoded n×n states with complexity O(√n) in the dimension parameter.Applications also include simulated-annealing approaches to approximately count graph colorings or matchings, specialized MAXCUT relaxations, zero-sum games, and Gibbs objective functions.Source: D. Gibbs Sampling · p. 12

E. Approximation Algorithms

  • Quantum subroutines may accelerate classical approximation algorithms, including SDP methods, but input/output bottlenecks can reduce end-to-end speedups to polynomial.Quantum SDP solvers may offer exponential speedups for special cases, yet practical obstacles likely require fault-tolerant quantum computing, and classical algorithms may achieve similar gains in some settings.Source: E. Approximation Algorithms · p. 12

F. Variational Methods

  • VQAs alternate quantum measurement of a parameterized circuit’s cost with classical parameter updates, offering heuristics even though optimal parameter finding is generally NP-hard.Despite convergence and iteration-complexity analyses, VQAs remain mostly heuristic; their design varies by ansatz, cost function, and optimizer.Source: F. Variational Methods · p. 12, Figure 3 · p. 13

IV. PROBLEM CLASSES & ALGORITHMS · A. Discrete Optimization · 1. Unconstrained Discrete Optimization

The section surveys discrete optimization and its algorithms, emphasizing that problem formulations affect which structures solvers can exploit. It focuses on unconstrained binary optimization and quantum heuristics, their guarantees and limitations, and open questions for practical advantage.

IV. PROBLEM CLASSES & ALGORITHMS

  • Optimization problem classes depend on variables, objectives, constraints, and stochasticity, and formally equivalent formulations can emphasize different properties and affect how problems are solved.The section introduces major problem classes, algorithms, and open questions for advancing optimization.Source: §IV · p. 13

A. Discrete Optimization

  • Discrete optimization uses discrete-valued variables, often creating combinatorial growth; constrained and unconstrained formulations can be converted into each other, but their solution approaches may differ.The equivalence may hold only when a global optimum is found, and exploiting available structure can be beneficial.Source: A. Discrete Optimization · p. 13

1. Unconstrained Discrete Optimization

  • QUBO is a central unconstrained binary formulation: it captures MAXCUT and many other problems, but conversions may preserve solutions only at the global optimum.Integer encodings may lose ordering structure, and penalty terms can leave equality constraints only approximately satisfied when solutions are approximate.Source: §1 · p. 13
  • For MAXCUT on 3-regular graphs, QAOA’s lower-bound approximation ratios are 0.692 at p = 1, 0.7559 at p = 2, and 0.7924 at p = 3; QAOA and QRAO remain below the classical 0.878567 ratio.For large-girth d-regular graphs, numerical results show QAOA outperforming many known SDP-based relaxations from p ≥ 11; for general QUBO, it has no performance guarantees.Source: §1 · pp. 14, 16
  • QAOA parameter strategies include physics-inspired initialization, classical loss estimation, and parameter transfer across instances; warm-start variants can outperform standard QAOA on some instances.Finite-depth guarantees for warm-started QAOA with custom mixers remain open; Recursive QAOA instead repeatedly fixes strongly correlated variables before classical solution of the reduced problem.Source: §1 · p. 15
  • Constant-depth QAOA cannot beat the Goemans-Williamson approximation on certain large d-regular MAXCUT instances, while other low-depth limits depend on problem structure.For MIS, when p < log(n)/log(d/ln(2))/2 and d is sufficiently large, QAOA’s approximation ratio is at most 0.854; these bounds do not apply to all variants or Recursive QAOA.Source: §1 · p. 15
  • QRAO encodes more variables than qubits and guarantees MAXCUT ratios of at least 0.555, 0.625, and 0.722 at variable-to-qubit ratios of 3, 2, and 1.5, respectively.These guarantees assume a feasible graph and sufficiently accurate ground-state approximation, which is not generally guaranteed; thus QRAO is strictly a heuristic. A ratio-2 variant imposes no graph constraints but may lack a non-trivial guarantee.Source: §1 · p. 16
  • Variational quantum imaginary-time and real-time evolution offer heuristics for unconstrained and black-box binary optimization, but suitable circuit design and circuit-evaluation costs remain challenges.For QITE, reaching a fixed ground-state overlap scales as T = O(n/∆) under the stated initial-overlap assumption; implementing its non-unitary evolution is difficult.Source: §1 · p. 16

2. Constrained Discrete Optimization · B. Continuous Optimization · 1. Convex Optimization

The section surveys quantum methods for constrained discrete and convex optimization, emphasizing speedups alongside the assumptions and implementation challenges that limit them. It describes constraint-handling strategies for discrete problems and quantum approaches to convex optimization, from MWU and interior-point methods to specialized algorithms.

2. Constrained Discrete Optimization

  • A quantum branch-and-bound algorithm solves most Sherrington-Kirkpatrick instances to optimality with high probability in O(20.226n) time, but requires FTQC and provides no a posteriori optimality-gap bounds.It adapts Grover Search to branch-and-bound trees.Source: §2 · p. 18
  • Constrained discrete optimization can use Grover search, penalties, or feasible-space restriction and projection; direct constraint handling can preserve sparsity but may shift complexity into mixers or deeper circuits.QAOA' uses constraint-preserving mixers, while quantum Zeno dynamics uses auxiliary qubits and mid-circuit measurements and may require FTQC. Penalty terms can densify the cost matrix and amplify objective values, creating numerical difficulties.Source: §2 · pp. 17–18

B. Continuous Optimization · 1. Convex Optimization

  • Quantum MWU methods for SDPs depend on γ = Rr/ϵ, which often scales poorly with n and m, while general black-box convex optimization can have matching classical and quantum query lower bounds.These methods often rely on QRAM, for which a scalable fault-tolerant implementation remains unavailable [278] [279] [280]; other notable MWU applications include shadow tomography, state discrimination, and E-optimal design.Source: §1 · pp. 19–20
  • Quantum IPMs can improve dependence on problem size, but tomography error and Newton-system conditioning leave overall speedup unclear, despite iterative refinement and methods allowing inexact directions.The condition number diverges near optimality, and QRAM is assumed [288].Source: §1 · p. 20
  • For LPs with m ≫ n, a QRAM-based quantum interior-point method scales as √m · poly(n, log(1/ϵ)), versus e O(mn + n^2.5) for the best classical solver.The speedup relies on a quantum subroutine for spectral approximations of BT B, which accelerates the Newton step.Source: §1 · p. 20
  • For MAXCUT SDP, iterative refinement improves precision dependence, and a QRAM-based algorithm achieves a polynomial speedup over the best known classical algorithm, though its gate-model version is outperformed classically.The earlier approach had O(ϵ−28) precision dependence; no classical lower bound is known for the problem [174].Source: §1 · p. 21
  • Quantum algorithms speed up both first- and second-order methods for matrix scaling without introducing a condition-number dependence.Techniques include amplitude amplification and graph sparsification [294] [297].Source: §1 · p. 21
  • QHD can converge to solutions even for certain nonconvex problems, while QCPM simulates the central path in one quantum evolution and is faster than IPMs in some regimes.QHD returns a classical solution by sampling without state tomography [298, 299]; QCPM also avoids QRAM, block-encodings, quantum linear system algorithms, and state tomography [300].Source: §1 · p. 21

2. Non-Convex Optimization

The section argues that unrestricted non-convex optimization offers no general quantum speedup, while specific query models, encodings, and landscape structures create conditional opportunities.

Problem scope

  • Many non-convex variants are undecidable, so the section focuses on k-th order critical points, defined by derivative conditions or, in non-smooth problems, Clarke-subdifferential conditions.Some variants are also inapproximable in the Banach–Mazur model [86].Source: §2 · p. 21

Quantum query bounds

  • Quantum SGD uses O(√nϵ−3) queries versus classical O(ϵ−4), advantageous only when n < ϵ−2; mean-squared smooth gradients improve O(ϵ−3) to O(√nϵ−5/2).These bounds assume quantum access to stochastic gradients; the first upper bound uses a probability-weighted superposition over bounded-variance gradients.Source: §2 · p. 22
  • Quantum query lower bounds match classical bounds: Ω(ϵ−(k+1)/k) with k-th order derivatives and Ω(ϵ−4) with stochastic-gradient access.Without further assumptions, classical lower bounds also apply to quantum algorithms; possible special cases depend on local minima, local behavior, and connecting barriers.Source: §2 · pp. 21–22

Direct quantum gradient descent

  • Gradient descent can encode iterates using O(polylog(n)) qubits, but final-state amplification may cost 2^T, and efficient gradient circuits are available only in special cases.For affine gradients of quadratic problems, Kerenidis and Prakash give an efficient phase-estimation implementation; circuits may also be approximated by pre-training a parameterized quantum circuit.Source: §2 · p. 22

Annealing and quantum walks

  • Quantum walks can speed simulated annealing and exploit tunneling between minima, with advantages over classical SGD when barriers are high but thin and minima are flat.Liu et al. study tunneling for SGD approximated by a continuous-time stochastic differential equation; restarting can help when searches enter barren plateaus, especially when such regions are many or large [196].Source: §2 · p. 22

Open questions

  • Open questions include lower bounds and runtime advantages, quantum sum-of-squares or SDP approaches, and which non-convex functions permit amplitude encoding, efficient gradient circuits, and convergence.The section also asks whether such approaches can extend to larger polynomial classes and beyond.Source: §2 · p. 22

C. Mixed-Integer Programming

Mixed-integer programs combine discrete and continuous decisions, and the section surveys quantum-hybrid and reformulation approaches while emphasizing that their overall advantage remains unresolved. It identifies open questions about speedups and calls for systematic benchmarking.

C. Mixed-Integer Programming

  • Classical branch-and-bound-and-cut solvers often prove optimality for instances with up to one million binary variables and sometimes structured instances with tens of millions.MIPs are non-convex and at least as hard as the discrete and continuous problems they subsume; instances with unbounded variables can be notoriously hard.Source: C. Mixed-Integer Programming · pp. 22–23
  • A hybrid branch-and-bound-and-cut approach could solve continuous relaxations quantumly, while quantum branching could add a quadratic speedup at substantially greater qubit and fault-tolerance requirements.The cited speedups differ by whether the task is finding all optima or one optimum; recent work suggests super-quadratic speedups may be possible in some cases.Source: C. Mixed-Integer Programming · p. 23
  • Quantum mixed-integer programs can be reformulated as high-dimensional LPs, SDPs via moment/SOS techniques, or linear programs over the dual copositive cone [330].Decomposition can solve QUBO subproblems quantumly and continuous subproblems classically; under restrictive conditions, the iteration can be globally convergent. Some SDP instances require dimension exponential in n+d.Source: C. Mixed-Integer Programming · p. 23
  • Open questions include whether convex-relaxation and branch-and-bound speedups combine into a general advantage, and whether branch-and-bound could generically yield super-quadratic speedups for NP-hard problems.The section also asks how to optimize Lagrangian design choices and which reformulations enable the best continuous-optimization speedups; quartic speedup has so far been shown only for learning majorities and the quantum counterfeit coin problem.Source: C. Mixed-Integer Programming · p. 24
  • Because most proposals place a quantum subroutine inside a classical algorithm, it remains unclear what subroutine advantage would yield an overall MIP advantage.Potential contributions could combine speed, solution quality, and diversity to accelerate branching; the section calls for further investigation and systematic benchmarking [254, 313–315].Source: C. Mixed-Integer Programming · p. 24

D. Dynamic Programming · E. Optimal Control

Dynamic programming uses Bellman recursions to solve large problems from smaller subproblems, and quantum approaches combine it with search for speedups. Optimal control connects differential-equation-constrained optimization to dynamic programming and reinforcement learning, while motivating quantum methods and open research directions.

D. Dynamic Programming

  • DP recursively optimizes Bellman equations over states and actions, with complexity O(Sm); for TSP, the passage gives eO(2n) complexity.The table is computed in an order that ensures successor-state values are already available; TSP states are city subsets, and DP also serves as a subroutine in approximation algorithms and solves MDPs.Source: D. Dynamic Programming · p. 24
  • Quantum dynamic-programming speedups combine classical DP with Grover search, often computing part of a subset-indexed table before searching for the best solution.For TSP, Ambainis et al. compute shortest paths through sets containing up to 24% of cities, then search for the shortest combination covering all cities; the approach also applies to problems such as graph coloring and minimum Steiner tree.Source: D. Dynamic Programming · p. 24

E. Optimal Control

  • HJB equations connect continuous optimal control to discrete Bellman recursions and MDP backward induction, but direct numerical solution faces a curse of dimensionality.When the value function lacks a classical gradient, viscosity solutions are defined through differentiable regularization and a limit; conventional methods quickly become intractable even for state dimensions n ≥ 10.Source: E. Optimal Control · pp. 25–26
  • With coherent oracle access, quantum reinforcement-learning methods achieve quadratic speedups for several tasks, but require fault tolerance and restricted environment access.Refs. give matching upper and lower bounds for multi-armed bandit problems and related tasks, including finding the optimal q-function; these gains count environment interactions and may not translate to wall-clock speedups.Source: E. Optimal Control · pp. 26–27
  • For parameterized policy optimization, quadratic speedups are possible under regularity conditions, and special contrived environments can yield provable exponential speedups.Parameterized quantum-circuit policies satisfy the stated regularity conditions; lower bounds show the quadratic improvements cannot be further improved in the general setting, while exponential results are unlikely to have practical implications.Source: E. Optimal Control · p. 27
  • Classical-access quantum reinforcement learning has conditional superpolynomial advantages in special environments, while practical work also explores parameterized-circuit heuristics.The provable advantages for optimal policies and q-functions in Refs. hold unless discrete logarithms have an efficient classical solution; empirical heuristic goals differ from exact optimality.Source: E. Optimal Control · p. 27
  • Quantum amplitude estimation gives a polynomial speedup for optimal stopping with quantum access to a stochastic-process sampler.The paper highlights American-option pricing as an application and asks whether these algorithms can extend to other problem classes and more decisions, or become more near-term quantum friendly.Source: E. Optimal Control · p. 27
  • Open directions include quantum sketching for value iteration or LSTD, quantum methods for suitable MDP feasible sets, and value-function approximation using inductive bias.The proposed inductive bias embeds prior knowledge—such as piecewise smoothness—into an approximator, and the paper encourages preserving links between discrete and continuous HJB equations.Source: E. Optimal Control · p. 27

F. Robust Optimization · G. Multi-Objective Optimization · V. EXECUTION ON NOISY DIGITAL HARDWARE AT SCALE

The sections describe robust optimization under uncertainty, multi-objective trade-offs and their limited quantum-algorithm literature, then outline noisy-hardware execution practices and scope.

F. Robust Optimization

  • Robust optimization requires parameterized constraints to hold for every uncertainty-set choice, with convex problem and uncertainty sets; scaling it incurs substantial computational overhead.The described formulation has convex objective functions in x and constraint functions concave in noise parameter u.Source: F. Robust Optimization · pp. 27–28
  • Quantum robust-optimization meta-algorithms use quantum access to functions, stochastic gradients, and quantum sampling subroutines, extending classical oracle-based approximate methods with polynomial advantage.Ben-Tal et al. developed classical meta-algorithms using an oracle for the original problem; Lim et al. [377] developed the quantum version.Source: F. Robust Optimization · p. 28

G. Multi-Objective Optimization

  • Multi-objective optimization seeks trade-offs among objectives, with Pareto-optimal solutions forming the efficient frontier; goals may be to approximate the full frontier or find one solution.Pareto optimality means one objective cannot be decreased without increasing at least one other objective.Source: G. Multi-Objective Optimization · p. 28
  • For certain bi-objective problems, approximating the Pareto curve within ϵ using fewer than twice the optimum number of solutions is NP-hard, while a 2-approximation is polynomial-time possible.The Pareto set can also have substantial cardinality.Source: G. Multi-Objective Optimization · p. 28
  • Weighted sums and constrained single-objective optimization can approximate the frontier for few objectives, but only constraints capture efficient solutions outside the convex hull; both strategies scale poorly as objectives grow.Hyper Volume measures volume spanned by found solutions, while Generational Distance measures distance to the optimal frontier or a reference solution.Source: G. Multi-Objective Optimization · p. 28
  • Quantum multi-objective optimization literature is sparse: proposals use quantum subroutines for resulting single-objective problems [382] or sample quantum states to approximate the frontier [383], leaving quantum-native algorithms open for research.Source: G. Multi-Objective Optimization · p. 28

V. EXECUTION ON NOISY DIGITAL HARDWARE AT SCALE

  • The hardware discussion focuses on cloud-accessible universal gate-based superconducting platforms; devices have reached 433 qubits, while IBM Quantum Eagle 127-qubit devices show median T1 near 300 µs and T2 near 150 µs.Superconducting qubits are arranged in planar lattices with each qubit connected only to immediate neighbors.Source: §V · pp. 28–29
  • The execution pipeline review covers algorithm translation to hardware, modeling and qubit encoding, transpilation, error mitigation, pulse-level opportunities, hardware benchmarks, and an execution example.Source: §V · p. 29

A. Quantum Stack … B. Hardware Benchmarks

The section traces how quantum optimization moves through a hardware-constrained stack, where modeling, compilation, noise handling, and pulse control create opportunities and bottlenecks. It argues that hardware utility should be assessed with application-tailored benchmarks, alongside general measures of scale, quality, and speed.

A. Quantum Stack

  • Hardware constraints and noise create scalability and performance bottlenecks across the quantum stack, but each stage offers opportunities to optimize execution.The algorithm progresses from abstract operations through hardware-native instructions and pulses to executable waveforms on a processor.Source: A. Quantum Stack · p. 29, Figure 5 · p. 29

1. Modeling, quantum algorithms, and encoding

  • Problem modeling must balance approximations and hardware noise, while encoding and constraint choices shape qubit needs and implementation demands.Quantum Random Access Codes can encode more decision variables than available qubits, but denser encodings trade retrieval probability for overhead and often a lower approximation ratio; Dupont et al. project a fully connected QUBO onto sparse hardware connectivity.Source: §1 · pp. 29–30
  • Hardware-aware algorithm choices should preserve solution quality while limiting circuit depth, because added mixer depth can constrain near-term utility.Warm-starts and adaptive bias-fields add only single-qubit rotations with negligible hardware overhead; heuristic methods require study at scale on actual quantum hardware.Source: §1 · p. 30

2. Transpilation

  • Transpilation must select qubits, synthesize native gates, and route circuits around connectivity limits, which can make dense problem graphs costly to execute.Qubit selection should reflect circuit properties such as gate fidelity or measurement quality; trapped-ion all-to-all connectivity permits denser graphs without added depth, though device scale limits problem sizes.Source: §2 · pp. 30–31

3. Error suppression and mitigation

  • Error mitigation can improve noisy expectation values, but PEC incurs a cost scaling as ¯γ^2nd, while ZNE extrapolation can fail when circuit depth limits stretch factors.Dynamical decoupling suppresses non-Markovian errors without extra shots, but dense circuits may leave little room for its pulses; PEC becomes infeasible at large scale, while PEA amplifies noise before extrapolating to zero noise.Source: §3 · p. 31
  • Because optimization needs good samples rather than only expectation values, developing error mitigation that produces error-mitigated samples is crucial.Expectation-value mitigation can help train variational parameters, but the optimization task ultimately seeks samples that minimize a cost function.Source: §3 · p. 31

4. Pulse-level and compiler

  • Pulse-level control can shorten schedules and improve QAOA sampling, but some advanced control methods may not be compatible with quantum error mitigation.Pulse-efficient transpilation can encode variational parameters in cross-resonance pulse durations, while tunable couplers can natively implement exchange-type operations useful for SWAP networks.Source: §4 · p. 32

B. Hardware Benchmarks

  • Application-tailored benchmarks are needed because general metrics may not predict a device’s optimization performance for a particular task or criterion.Scale counts qubits, quality metrics include Layer Fidelity and EPLG, and CLOPS measures gate-layer throughput including classical parameter-update overhead; squeezing is relevant to QAOA on fully connected MAXCUT [455].Source: B. Hardware Benchmarks · p. 32

C. Execution Example … 1. Model-(In)Dependence

The paper illustrates practical QAOA execution choices on noisy hardware and argues for fair, reproducible benchmarking of quantum and classical optimization. It distinguishes model-independent benchmarks, which can accommodate new formulations and hardware capabilities, from model-dependent tests of fixed formulations.

C. Execution Example

  • Sack and Egger [403] ran depth-two QAOA on R3R graphs up to 40 nodes using high-fidelity qubits and SWAP-engineered connectivity.Their mapping minimized SWAP gates using the approach of Matsuo et al.. Machine-learning error mitigation enabled parameter optimization, but noiseless expected samples still differed substantially from hardware samples, motivating sample error mitigation.Source: C. Execution Example · p. 32

D. Summary

  • Users have greater control over scalability at higher software-stack levels, while lower-level transpilation and pulse control can further reduce circuit depth and duration.Best practices include choosing algorithms and variants that reduce depth without compromising algorithmic speed or quality; transparency about lower-level methods remains important.Source: D. Summary · p. 33

VI. BENCHMARKS

  • Benchmarks should enable fair, reproducible comparisons across classical and quantum approaches, with clearly defined assumptions about implementation, data, and metrics.The section aims to provide best practices and problems for thorough, robust comparisons.Source: §VI · p. 33

A. Related Work

  • Classical benchmark competitions and libraries support solver comparisons, but quantum-compatible counterparts do not yet exist; existing frameworks measure selected hardware or solver properties [469].Finžgar et al. compare QUBO solvers by solution quality and time-to-solution, providing a useful baseline.Source: A. Related Work · pp. 33–34

B. Goals

  • Problem-centric benchmarks should compare classical and quantum runtime and solution quality, while tracking hardware and algorithm progress and how resources and solution quality scale with problem size.Benchmarks can reveal when algorithms fail to find good solutions, potentially because of hardware limitations.Source: B. Goals · p. 34

C. Design

  • Reproducible benchmarks should specify the model, preprocessing, platform, target metrics, algorithm, and suitable hyperparameters.Preprocessing can reduce a problem to its challenging core and may account for the platform used for execution.Source: C. Design · pp. 34–35

1. Model-(In)Dependence

  • Model-independent benchmarks allow varied solution strategies and formulations, potentially revealing quantum advantage while accommodating new capabilities such as dynamic circuits [433].The authors expect such benchmarks to show how quantum algorithms approach, meet, or exceed classical capabilities on particular instances.Source: §1 · p. 35
  • Model-dependent benchmarks compare algorithms and platforms using a fixed formulation, where model-specific solvers may outperform general solvers.MIPLIB, QPLIB, and the SAT Problem Library offer established instances; work on adaptive-bias QAOA for SAT phase transitions motivates further study of larger, denser instances.Source: §1 · p. 35

2. Pre-processing … D. Problems

The sections explain how pre-processing, hardware choice and benchmarking metrics shape quantum optimization comparisons, then outline criteria and candidate problems for standardized benchmarks. They emphasize matching evaluation to the problem and platform while accounting for classical methods and practical quantum-hardware constraints.

2. Pre-processing

  • Pre-processing can shrink optimization problems and resource needs, but its classical computational effort should count in benchmark evaluations.Its implementation depends on the formulation, data, algorithm and platform; for Euclidean TSP and Steiner tree, it can remove 95% of variables. QUBO reductions can conditionally fix variables while preserving at least one optimum, or split uncorrelated variables into independent sub-QUBOs.Source: §2 · p. 35

3. Platforms

  • Because platforms differ in strengths, bottlenecks, models and applicable algorithms, problem-matched platform selection and fair cross-platform benchmarking are important.Digital quantum systems face limited coherence times, circuit depths, qubit numbers and connectivity; hardware metrics alone may not describe useful computational potential.Source: §3 · p. 36

4. Metrics

  • Fair quantum-optimization benchmarks should measure resource cost, run time, solution quality and problem complexity, choosing and faithfully reporting metrics suited to the problem, model, algorithm and platform.Resource accounting includes classical and quantum resources, including pre- and post-processing and parallel resources; quality can include feasibility, optimality gap, diversity and heuristic success rate.Source: §4 · pp. 37–38
  • Run-time comparisons should define the benchmark goal and account for total time, including preprocessing, compilation, execution and post-processing, while separating costly steps when useful.Finding a solution and certifying optimality can take different amounts of time; feasibility benchmarks can count instances solved within a set time limit, and parallelization trades resources for run time.Source: §4 · p. 37

D. Problems

  • Benchmark problems should challenge classical solvers yet fit current or near-term quantum systems, but instance hardness and practical relevance are difficult to establish.Crafted instances risk exploitable structure or limited practical value; random instances may be easy or hard, while relevant, difficult real-world instances meeting hardware limits are hard to find and often unpublished or ill-defined.Source: D. Problems · p. 38
  • Maximum Independent Set offers a relatively sparse QUBO benchmark with instances hard to solve to proven optimality, while carefully weighted market-share problems can challenge classical methods even at small sizes.Market-share difficulty depends on coefficients and problem parameters; some instances with fewer than 100 variables and 8 constraints remain unsolved to proven optimality.Source: D. Problems · p. 39
  • LABS, QAP and sports timetabling provide distinct benchmark settings: LABS has one instance per size, QAP remains difficult at n ≈30, and some medium sports instances lack known feasible solutions.LABS has been solved to optimality up to N = 66 and N = 127 for skewsymmetric instances, but its quartic objective presents modeling challenges; QAP’s binary formulation squares the variable count and produces a dense QUBO.Source: D. Problems · pp. 39–40
  • Spin glasses are promising cross-platform benchmarks because they map naturally to sparse QUBOs and remain open to quantum advantage, including in average-case hard settings [95, 542].Classical solvers perform well on regular lattices, while possible advantages for digital quantum optimizers on non-regular structures remain open; binary benchmark candidates also support comparison with established classical methods.Source: D. Problems · pp. 38, 40

E. Demonstrations

The surveyed gate-based quantum optimization demonstrations provide valuable hardware capability tests, but feasible heuristic solutions alone do not establish a quantum performance advantage. The section presents them as a foundation for fair, comparable benchmarks.

E. Demonstrations

  • Feasible solutions from quantum heuristics do not establish advantage over classical methods, even for problems described as NPO-hard; these demonstrations are capability rather than performance benchmarks.The section calls for systematic, fair benchmarking and surveys selected gate-based experiments with more than 16 qubits.Source: E. Demonstrations · p. 40
  • Table IV surveys QAOA and VQE implementations on MAXCUT, Sherrington-Kirkpatrick, and QUBO/PUBO instances, while several larger experiments use alternative scaling strategies.Examples include QAMPA for 50 qubits [264], a greedy procedure for 72 qubits, parameter grid search or concentration above 100 qubits [547], and adaptive remapping for 82 qubits [546]; shot counts and parameter-update iterations are not reported comparably.Source: E. Demonstrations · pp. 40–41, Table IV · p. 41
  • Higher-qubit experiments generally use lower-density problems because added connections require SWAP gates and increase noise; fair approximation ratios require range normalization and separate best- and mean-sample values.The section defines the ratio as (Cmax − ⟨C⟩)/(Cmax − Cmin), converting the problem to minimization first.Source: E. Demonstrations · p. 41
  • QRAO achieved an approximation ratio of 0.905 on a 40-variable MAXCUT problem using up to 15 qubits, while qubit reuse scaled a QAOA variant to 130 variables on 32 qubits at around 0.8.These approaches target more variables than qubits, but their intrinsic differences make direct comparison with standard QAOA/VQE results difficult.Source: E. Demonstrations · pp. 41–42
  • The demonstrations establish a foundation for future benchmarks and underscore the need for agreed common metrics to make comparisons fair and comparable.The section describes itself as a first step toward a coordinated benchmarking effort.Source: E. Demonstrations · p. 42

VII. ILLUSTRATIVE APPLICATIONS … 3. Deep Dive: Optimal Asset Allocation

The paper frames finance and sustainability as real-world optimization playgrounds, not claims of near-term quantum advantage, and uses asset allocation to trace increasing complexity from idealized portfolios to uncertain, dynamic decisions.

VII. ILLUSTRATIVE APPLICATIONS

  • Finance and sustainability offer families of real-world optimization problems at increasing complexity, intended as research playgrounds rather than claims of likely near-term quantum advantage.The discussion aims to link practical complications to optimization problem classes and help track progress toward quantum advantage.Source: §VII · p. 42

A. Financial Asset Allocation

  • Finance spans risk management, asset allocation, option pricing, macroeconomic modeling, trading, and lending as potential use cases for quantum algorithm development.The section surveys quantitative finance, existing quantum approaches, asset allocation formulations, and future research directions.Source: A. Financial Asset Allocation · p. 42

1. Overview

  • Financial models face scarce or irregular data and trade-offs among complexity, computational feasibility, and regulatory or business constraints, motivating methods for decisions under uncertainty.Changing consumer banking, climate and energy risks, and geopolitical dynamics add further modeling challenges, while even small improvements may matter.Source: §1 · pp. 42–43
  • Stochastic, robust, and multi-objective finance problems include credit-risk minimization, portfolio estimation-risk control, and investing that combines returns, diversification, decarbonization, and ESG objectives.Examples also include asset-liability management and mortgage pricing that balances revenue, balance-sheet, and business objectives.Source: §1 · p. 43

2. Related Work

  • Quantum finance research mostly studies linear, quadratic, and simplified integer problems encoded as QUBOs and solved with QAOA or VQE, typically below 50 variables.Brandhofer et al. study covariance-based portfolio diversification; other work examines portfolio ansätze, circuit depth, annealing, VQE, tensor networks, and collateral optimization [577], [400],,,,. Proposed applications also include transaction settlement and anti-money-laundering motif matching.Source: §2 · pp. 43–44

3. Deep Dive: Optimal Asset Allocation

  • Asset allocation is a difficult, high-impact financial problem because stochastic markets and practical trade-offs resist a universal solution, while a systematic route to real-world quantum impact remains unclear.Solutions must accommodate particular use cases, market environments, asset classes, or investment scenarios.Source: §3 · p. 44
  • Level 1 models a risk-averse, myopic investor in a frictionless one-period market with known parameters, using mean-variance return-risk optimization over a preselected portfolio universe.These continuous formulations can be relatively easy to solve and provide benchmarks, but omit realistic market conditions; QUBO penalty encodings of constraints may require substantial post-processing.Source: §3 · pp. 44–45
  • Levels 2 and 3 address estimation uncertainty and temporal dynamics, respectively, moving asset allocation beyond unstable static estimates toward multi-period strategies.Level 2 responds to scarce data and sensitivity in expected returns and covariances with debiasing, robust or regularized optimization, and combined approaches; clustering can reduce dimensionality and isolate noise. Level 3 considers evolving correlations and inter-temporal effects, a computationally hard domain practitioners and enterprise solvers often cannot effectively tackle, and the paper urges quantum research to advance toward both levels.Source: §3 · pp. 45–46

4. Outlook · B. Sustainable Energy Transition · 1. Power Grid Overview

The outlook identifies finance and the sustainable energy transition as sources of optimization problems for quantum-algorithm research and benchmarking. The energy-grid overview describes how renewables and digitization create new coordination challenges and motivates study of grid optimization and e-mobility.

4. Outlook

  • The financial industry presents hard optimization problems, and practical progress depends on combining effective problem modeling with optimization.The review also identifies skewed, heavy-tailed distributions, Bayesian approaches, sector-specific priors, and non-Markovian decision processes as directions for research and benchmarking.Source: §4 · p. 46

B. Sustainable Energy Transition

  • Sustainable energy transition offers optimization test cases with societal benefit, including real-world-data examples for studying where quantum optimization may help or may not outperform classical algorithms.The use cases are presented as a way to understand problem characteristics, not necessarily as near-term candidates for practical quantum advantage.Source: B. Sustainable Energy Transition · p. 47

1. Power Grid Overview

  • Power grids are shifting from centralized, carbon-intensive generation toward renewable sources, while digitization enables real-time monitoring, data-driven decisions, and enhanced control.Source: §1 · p. 47
  • Intermittent, probabilistic solar and wind generation requires coordination of many assets to match supply and demand, while storage faces cost and scalability challenges.Source: §1 · p. 47
  • Grid digitization also raises cybersecurity and data-privacy challenges, and adapting systems requires substantial investment and innovative solutions.The passage suggests these adaptations may exceed the capabilities of classical computer systems.Source: §1 · p. 47
  • The section roadmap covers three power-grid optimization problem types, related quantum-optimization work, and three families of e-mobility use cases linked to problem classes and algorithms.It concludes with potential research directions.Source: §1 · p. 47

2. Related Work · 3. Leveraging the Flexibility of e-Mobility

Quantum optimization for power grids remains largely focused on small, illustrative models, while e-mobility offers three optimization use cases whose practical and quantum relevance depends on realistic constraints, uncertainty, and problem difficulty. The section outlines their core formulations and how real-world extensions can change their complexity.

2. Related Work

  • Early quantum power-grid work mainly targets UCP, via QAOA/classical hybrids, annealing QUBOs [616] [618], and decomposition, alongside power-flow and storage-scheduling formulations.The UCP formulations include binary unit on-off decisions, network-switch QUBOs with penalty constraints, and sequences of quadratic continuous and binary subproblems.Source: §2 · p. 47
  • These studies use small illustrative problems and simple models, mostly QUBOs, that do not capture real-world complexity, though they may advance theory, formulations, algorithms, and practical requirements.Source: §2 · p. 47

3. Leveraging the Flexibility of e-Mobility

  • EVs can store energy to balance renewable supply and demand, but wider charging access, deadline-aware charging control, and grid integration are key challenges.The cited outlook notes more than 26 million EVs on roads in 2022 and about 240 million expected by 2030; in principle, 400 EVs can deliver 4 MWh to the grid.Source: §3 · pp. 47–48
  • Parking-site scheduling selects EVs for plug-in spaces to maximize value subject to charger-capacity and site-power limits, yielding a binary optimization with 2K knapsack constraints.The base formulation assumes EV arrivals and departures are known; the decision variable indicates whether to admit each EV to a charging space.Source: §3 · p. 48
  • The parking problem can be modeled as a QUBO, and potentially classically challenging instances merit benchmarking; practical extensions add variable power, pricing, flexible charge targets, or uncertain arrivals and renewables.These extensions can increase problem size, introduce continuous variables and MIP formulations, or shift offline optimization toward online or stochastic methods.Source: §3 · pp. 48–49
  • Overnight fleet charging and discharging can be formulated as discrete optimal control to minimize supply costs while fully charging EVs by departure, but the problem maps to a UCP solvable efficiently by commercial solvers.Dynamic programming with Grover search has been proposed, but practical short-term speedups are unlikely because it requires fault-tolerant quantum computing and its quadratic speedup may be insufficient.Source: §3 · p. 49
  • Adding energy constraints, stochastic arrival or departure times, and stochastic costs makes fleet control harder, potentially requiring MDPs that face a curse of dimensionality.Such variants may offer small test cases for quantum approaches; an MDP policy separates optimization and inference, potentially relaxing time-to-solution requirements.Source: §3 · pp. 49–50
  • Energy retailing with storage is a stochastic optimization that is convex and separable into K conventional problems when demand, storage, and high-price energy are decision-independent, so the basic form is not a promising quantum-advantage candidate.Extensions can couple storage to past decisions, add risk constraints such as CVaR, and make the problem non-convex depending on cost functions, linking it to optimal control and robust or chance-constrained optimization.Source: §3 · p. 50

4. Outlook · VIII. CONCLUSION & OUTLOOK

Quantum optimization has broad potential, but demonstrating practical quantum advantage remains a challenge. The paper outlines research directions and benchmarking needs, including real-world use cases such as the sustainable energy transition.

4. Outlook

  • Sustainable-energy optimization problems derived from real-world data may provide test cases, and some instances could be classically challenging even with few variables under certain data assumptions.The paper relates problem classes of increasing complexity to use cases of increasing real-world relevance.Source: §4 · p. 50
  • Benchmarking is crucial to identify which proposed instances are truly classically difficult and where potential quantum advantage may exist.The paper calls for further algorithm research to address complications that stand in the way of practical impact.Source: §4 · p. 51

VIII. CONCLUSION & OUTLOOK

  • Complexity theory can guide provable performance guarantees but may not reveal practical quantum advantage, motivating analysis of heuristics alongside research on key optimization classes.The paper reviews existing algorithms and suggests new research directions, while discussing challenges of executing and scaling them on noisy hardware.Source: §VIII · p. 51
  • As hardware improves, quantum optimization research should combine theoretical analysis with empirical testing of algorithms, including heuristics without provable guarantees, on real quantum computers.Real-hardware experiments can validate proposals and build intuition even without immediately establishing practical advantage.Source: §VIII · p. 51
  • Responsible research should avoid overstating results, establish clear benchmarks for reliable interpretation, and prioritize applications with positive social impact, such as the sustainable energy transition.Quantum optimization use cases span contexts with positive societal impact as well as nefarious intent.Source: §VIII · p. 51
  • Quantum optimization has vast potential, but significant challenges remain in demonstrating practical quantum advantage; the paper offers a blueprint for defining and measuring progress.The authors expect demonstrated advantage to influence many domains because optimization is widely relevant.Source: §VIII · p. 51

Related papers

Loading 2312.02279v3…