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

Quantum optimization faces an open question: where can quantum methods provide meaningful advantage over classical optimization, especially beyond worst-case exact settings? The paper surveys complexity-theoretic and heuristic approaches, algorithmic building blocks, noisy-device scaling, benchmarks, and application domains. It concludes that complexity theory can guide guarantees, while practical progress requires analyzing heuristics, scaling constraints, fair benchmarks, and real-world optimization problems.

  • Problem

    The paper addresses the unresolved potential, challenges, and real-world relevance of quantum advantage across major optimization problem classes.

  • Method

    The paper combines complexity-theoretic analysis, reviews of quantum optimization algorithms and problem classes, discussions of noisy hardware, benchmarking, and application examples.

  • Results

    The paper identifies quantum optimization as a broad research area with open questions spanning encodings, preprocessing, algorithmic scaling, complexity, and practical applications.

  • Takeaways & Limitations

    Practical evaluation should combine theoretical guidance with heuristic analysis, noise-aware scaling studies, fair classical comparisons, and application-relevant benchmarks.

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

The introduction frames quantum optimization as a potentially high-impact field while emphasizing that practical advantage depends on problem structure, noise, benchmarking, and suitable complexity-theoretic interpretation.

  • Quantum optimization could improve solution quality, diversity, time-to-solution, or cost-to-solution across many application domains.
  • Quantum computers may offer only quadratic speedups over exponential classical search in worst-case combinatorial optimization.A quadratic improvement over exponential runtime remains exponential.
  • Noise motivates quantum error correction and error mitigation as strategies for obtaining meaningful results before scalable fault-tolerant hardware.Error correction adds substantial qubit overhead, while mitigation combines multiple noisy results.
  • Fair, reproducible benchmarks and metrics are needed because heuristic performance is instance-dependent and quantum advantage may not occur universally.
  • Complexity theory guides possible quantum advantage, but practical advantage requires broader evidence than rigorous separations alone.Factoring illustrates a provable quantum speedup that is expected to become meaningful with fault-tolerant hardware.

Can quantum computers solve NP-hard

General worst-case results do not support exponential quantum speedups for NP-hard problems, but practical, structured, typical, or special instances may still offer opportunities for quantum advantage.

  • Worst-case and unstructured problems: Grover’s algorithm gives at most a quadratic speedup for unstructured search over 2^n assignments, and is considered optimal in the black-box setting.This intuition is extended to general SAT instances because they are not known to contain exploitable structure.
  • Practical structure: Quantum algorithms are therefore encouraged to exploit structure in practical instances rather than target fast solutions for all NP-complete instances.The paper links this direction to the absence of known asymptotically faster quantum or classical algorithms for all SAT instances.
  • Complexity classes: Relative to a particular oracle, NISQ has power strictly between BPP and BQP: BPPO ⊊ NISQ ⊊ BQPO.NISQ is defined using a BPP machine with access to a noisy quantum device containing polynomially many qubits.
  • NP-intermediate problems: Exponential speedups cannot be ruled out for NP-intermediate problems, which lie inside NP but outside P and are not NP-complete.Factoring is given as a believed example of this class.
  • Typical instances: Typical instances can be much easier than worst-case instances, so worst-case results ruling out advantage for NP-hard problems do not exclude exponential speedups on practically relevant instances.Such speedups would occur when quantum algorithms solve instances efficiently that require exponential classical time.
  • Parameterized optimization: Polynomial kernels provide reduced benchmark instances for many fixed-parameter tractable combinatorial optimization problems.For such problems, the paper argues that benchmarking on the kernel is meaningful.

B. Approximate Solutions

Approximation can make optimization useful without exact solutions, but hardness-of-approximation results often limit achievable ratios. Quantum opportunities remain where classical bounds leave gaps or where quantum speedups need not improve approximation factors.

  • Hardness of approximation: The PCP theorem informally implies that, for many problems, arbitrary-precision approximation is as hard as exact computation.Approximation ratio measures the expected approximate solution relative to the optimum.
  • Hardness of approximation: For MAX-E3-SAT, random assignment achieves a 7/8-approximation ratio, while improving it to 7/8+ϵ classically is impossible in polynomial time unless P=NP.Improving such an inapproximability bound with quantum computers would imply quantum solutions to NP-hard problems.
  • Hardness of approximation: For MAXCUT, the Goemans–Williamson algorithm achieves c ≈0.87856, and surpassing c+ϵ is ruled out under the Unique Games Conjecture.The bound depends on the stated conjectural assumption.
  • Potential quantum opportunities: Quantum advantage may remain possible when known inapproximability bounds exceed provable approximation factors, as suggested for metric TSP.Quantum methods might also provide provable computational speedups while matching classical approximation factors.
  • Approximation classes: APX contains NPO problems with polynomial-time approximation ratios bounded by a constant, while PTAS contains problems admitting polynomial-time algorithms within 1+ϵ of optimum.These classes organize optimization problems by their approximation guarantees.
  • Heuristic settings: Heuristics target useful solutions for special, structured, typical, or average-case instances, motivating distributional classes such as HeurBPP and HeurBQP.These classes allow errors on a small fraction of instances drawn from an input-size-dependent distribution.
  • Heuristic settings: A reported separation shows a super-polynomial quantum advantage for a combinatorial optimization problem under special distributions derived from factoring problems, including in approximation.The separation uses cryptographic tools and applies to a restricted distributional setting.
  • Scaling limitations: Variational quantum algorithms face barren plateaus, whose exponentially flat loss landscapes create a central scaling bottleneck for practically relevant system sizes.The passage associates barren plateaus with ansätze close to t-designs or with excessive entanglement.

B. Quantum Adiabatic Algorithm

The Quantum Adiabatic Algorithm encodes an optimization problem in a problem Hamiltonian and slowly evolves an easily prepared initial ground state toward the solution. Its performance depends on the annealing schedule, total time, and spectral gap, while practical variants relax or modify ideal adiabatic evolution.

  • Quantum Adiabatic Algorithm: QAA encodes the optimization problem in a Hamiltonian H whose ground state represents the solution, alongside a mixing Hamiltonian H_X with an easily prepared ground state.The initial state must have non-zero overlap with the ground state of H.
  • Quantum Adiabatic Algorithm: The algorithm interpolates from H_X to H using H(t) = λ(t/T)H + (1 − λ(t/T))H_X while evolving the quantum state under H(t).The schedule satisfies λ(0) = 0 and λ(1) = 1.
  • Quantum Adiabatic Algorithm: If the annealing is sufficiently slow, the Adiabatic Theorem keeps the state in the instantaneous ground state, so the final state represents the encoded solution.The required annealing time depends on the minimum spectral gap along the evolution.
  • Quantum Adiabatic Algorithm: Practical implementations use repeated finite-time or diabatic runs, while counter-diabatic annealing adds Hamiltonian terms to suppress transitions to excited states.These variants relax the requirement of remaining continuously in the instantaneous ground state or actively reduce such transitions.
  • Quantum Adiabatic Algorithm: QPE-based optimization requires an initial state with polynomial overlap with the ground state, and factoring-related QUBOs may not arise naturally in practice.The paper identifies finding such an initial state and harnessing factoring reductions for optimization as open or limiting issues.

IV. PROBLEM CLASSES & ALGORITHMS

This section organizes optimization problems by formulation and surveys quantum approaches for discrete optimization, especially QUBO and QAOA. It contrasts provable guarantees with heuristic performance and identifies open questions around quantum advantage, encodings, and problem scaling.

  • Discrete Optimization: Discrete optimization uses variables with discrete values, often creating a combinatorial explosion as input size grows.The section considers both constrained and unconstrained discrete problems, whose solution approaches can differ substantially.
  • QUBO: QUBO encodes an objective as a diagonal Hamiltonian whose ground state represents the optimal binary solution.The mapping substitutes binary variables with spin variables and then replaces spins with Pauli Z matrices.
  • QAOA: QAOA alternates problem and mixing unitaries for p layers, using new parameters β_j and γ_j at each layer.It is a special case of VQE applied to QUBOs and begins from the state |+⟩⊗n.
  • QAOA: 0.692, 0.7559, and 0.7924 are lower bounds for QAOA approximation ratios on 3-regular MAXCUT at p = 1, 2, and 3, respectively.For general QUBO, however, QAOA remains a heuristic without performance guarantees.
  • QAOA Limitations: Constant-depth QAOA cannot outperform the Goemans-Williamson approximation on certain large d-regular MAXCUT instances, so depth must grow with problem size.Related low-depth limitations have also been established for particular QAOA approaches to Maximum Independent Set and k-local MAXCUT.
  • Alternative Heuristics: QRAO increases the variable-to-qubit ratio and uses a non-diagonal Hamiltonian to encode larger MAXCUT instances into a fixed qubit count.Neither QRAO nor QAOA reaches the classical MAXCUT approximation ratio 0.878567, leaving room for improved classical and quantum approximations.
  • Open Questions: Open questions span quantum-specific formulations, improved integer encodings, more efficient general encodings, and the potential for quantum advantage.QUBO problems are broadly useful but are generally NP-hard and APX-hard, while some QUBO-formulated problems admit stronger approximation results.

2. Constrained Discrete Optimization

This section surveys direct and indirect strategies for constrained optimization and reviews quantum algorithms for convex and related problems. It emphasizes that constraint handling, hardware assumptions, numerical conditioning, and benchmarking determine whether claimed speedups are practically meaningful.

  • Constrained Discrete Optimization: Constrained discrete optimization adds equality or inequality constraints to QUBO, while linear objectives remain relevant because constraints are present.Inequalities can be converted using slack variables, and equalities can then be incorporated as penalty terms.
  • Quantum Branch and Bound: A quantum branch-and-bound algorithm solves most Sherrington-Kirkpatrick instances to optimality with high probability in time O(20.226n).The method adapts Grover search to branch-and-bound trees and accelerates classical branch-and-bound algorithms.
  • Constraint Handling: Penalty-based constraint encoding often densifies the cost matrix and makes implementation on real quantum hardware more difficult.Native incorporation of cardinality, packing, or covering constraints could produce sparser problems, although complexity may shift into the mixer.
  • Constraint Handling: Quantum constraint-handling strategies use Grover search, penalty terms, or restrictions and projections into the feasible space.The paper identifies efficient constraint handling as crucial because constraints occur widely in practical optimization problems.
  • Convex Optimization: Quantum convex-optimization results depend strongly on access models and numerical parameters, including QRAM, precision, and condition numbers.Black-box convex optimization can have matching classical and quantum query lower bounds, while some quantum interior-point methods have favorable size dependence under QRAM assumptions.
  • Convex Optimization: Some convex problems exhibit polynomial quantum speedups, including MAXCUT semidefinite programming and matrix scaling, but the comparisons require careful baselines.One reported MAXCUT SDP speedup relies on QRAM and is outperformed classically in the standard gate model; matrix-scaling algorithms avoid condition-number dependence.
  • Nonconvex and Related Methods: Quantum Hamiltonian descent can converge to optimal solutions on certain nonconvex problems, although it may not do so efficiently because such problems can be provably hard.The Quantum Central Path Method instead simulates the central path directly through nonlinear complementarity equations.

2. Non-Convex Optimization

Quantum approaches to non-convex optimization range from gradient-based methods to quantum-walk and tunneling strategies, but broad speedups remain limited by classical lower bounds and implementation costs.

  • When derivative or stochastic-gradient access is available without further assumptions, classical lower bounds also apply to quantum algorithms.
  • Non-convex optimization seeks stationary points or minima of functions, including settings with smooth, non-smooth, stochastic, or higher-order derivative information.
  • Ω(ϵ−(k+1)/k) and Ω(ϵ−4) are quantum query lower bounds for higher-order derivative and stochastic-gradient access, respectively, matching classical bounds.
  • Quantum SGD can require O(√nϵ−3) queries with probability-weighted stochastic-gradient superpositions, improving on O(ϵ−4) only when dimension is < ϵ−2.
  • Quantum gradient-descent proposals use polylog(n) qubits and encode gradient steps in quantum states, but efficient gradient circuits are known only for special cases or approximations.
  • Quantum walks can provide polynomial speedups for simulated annealing, while quantum tunneling offers a mechanism for crossing barriers between local minima.

C. Mixed-Integer Programming

Mixed-integer programming combines discrete and continuous decisions, motivating hybrid quantum-classical methods based on decomposition, reformulation, and quantum subroutines. The section emphasizes that achieving overall quantum advantage remains unresolved, especially for proving speedups and exactness.

  • Mixed-integer programs combine binary or discrete variables with continuous variables and are at least as hard as the optimization classes they subsume.
  • Classical branch-and-bound-and-cut solvers can already solve instances with up to one million binary variables to proven optimality, complicating claims of practical quantum advantage.
  • Proposed approaches include classical branch-and-bound with quantum continuous relaxations, quantum QUBO subroutines within decomposition, and Lagrangian or other unconstrained reformulations.
  • Mixed-integer programs can be reformulated as high-dimensional LPs, SDPs, or completely positive problems, creating possible routes for quantum subroutines.
  • Exact cut generation is required to prove optimality in a hybrid QUBO-based approach, but solving that subproblem exactly can be difficult even classically.
  • Open questions concern general provable advantage, branch-and-bound speedups, reformulation quality, and the quantum subroutine performance needed for overall algorithmic advantage.

D. Dynamic Programming

Dynamic programming combines recursively computed subproblems, and quantum algorithms often add Grover search to classical dynamic-programming structure. The resulting speedup is generically bounded quadratically, while related applications include reinforcement learning, optimal control, and optimal stopping.

  • Dynamic programming recursively optimizes a Bellman equation by computing table entries after the successor states required for each entry are available.
  • The generic dynamic-programming complexity is O(Sm), with S possible states and m maximum actions per state; for TSP it is eO(2n).
  • Quantum speedups for dynamic programming commonly combine classical table computation with Grover search, including a TSP construction using paths through subsets of cities.
  • In the generic hypercube formulation, quantum speedup for dynamic-programming algorithms can be at most quadratic.
  • For quantum reinforcement learning, exact methods have matching upper and lower bounds for several oracle-access tasks, while parameterized policy optimization admits quadratic speedups under regularity conditions.
  • Optimal stopping problems, including American-option pricing, combine stochastic modeling, Monte Carlo estimation, least-squares regression, and dynamic programming.
  • Open directions include quantum implementations or sketching of value iteration and least-squares temporal-difference methods for noisy-device settings.

F. Robust Optimization

Robust optimization models constraints that must hold across an uncertainty set, but large-scale instances incur substantial computational overhead. Multi-objective optimization extends the setting to trade-offs among objectives, where quantum-native methods remain sparsely developed.

  • F. Robust Optimization: Robust optimization addresses inaccurate data by requiring parameterized constraints to hold for every parameter choice in an uncertainty set.
  • F. Robust Optimization: The robust formulation uses convex decision domains and uncertainty sets, with convex objective-side functions and concavity in the noise parameter.
  • F. Robust Optimization: Large-scale robust optimization has significant computational overhead, motivating quantum meta-algorithms that use quantum access to functions and stochastic gradients.
  • G. Multi-Objective Optimization: Multi-objective optimization addresses decisions requiring trade-offs among multiple objective functions rather than a single objective.
  • G. Multi-Objective Optimization: A solution is Pareto optimal when no objective can be improved without worsening at least one other objective.
  • G. Multi-Objective Optimization: For certain bi-objective shortest-path problems, approximating the Pareto curve with fewer than twice the optimum number of solutions is NP-hard, whereas a 2-approximation is polynomial-time achievable.
  • G. Multi-Objective Optimization: Quantum multi-objective optimization has little literature, with proposals mainly applying quantum subroutines to scalarized problems or sampling quantum states to approximate efficient frontiers.

A. Quantum Stack

The quantum stack maps an abstract optimization algorithm through hardware-native circuits, error mitigation, pulses, and executable waveforms. Hardware constraints and noise create scalability and performance bottlenecks, motivating optimization opportunities at every level.

  • Stack overview: Hardware constraints and noise limit the scalability and performance of quantum optimization algorithms.Analyzing the stack reveals where these bottlenecks arise.
  • Stack overview: The quantum stack transforms an abstract algorithm into a high-level circuit, hardware-native instructions, mitigated circuits, pulses, and executable waveforms.The final waveforms are run on the quantum processor.
  • High-level design: Problem modeling, encoding, and circuit design can simplify constraints and reduce quantum resource requirements.Examples include quadratic penalty terms, warm-starts, constraint-aware mixers, and counterdiabatic terms.
  • Transpilation: Transpilation selects hardware-compatible instructions, synthesizes operations, and routes circuits around limited qubit connectivity.Exploiting QAOA’s commuting two-qubit-gate structure can produce shallower circuits.
  • Hardware limits: Hardware architectures trade connectivity against scale, while heuristic quantum optimization methods require evaluation on actual quantum hardware.Trapped-ion devices offer all-to-all connectivity but have smaller problem sizes than superconducting devices.
  • Error suppression and mitigation: Error mitigation can improve noisy estimates but may substantially increase sampling costs.For PEC, the measured variance increases by γ^2, while a circuit with n qubits and d layers has cost scaling as γ̄^2nd.
  • Benchmarking: Application-tailored benchmarks are needed because general hardware metrics may not predict optimization performance on a specific task.Performance should be assessed on tasks similar to the problem of interest using the chosen criterion.

C. Execution Example

The paper uses execution examples and benchmarking guidance to connect noisy-hardware performance with fair comparisons between classical and quantum optimization. It emphasizes problem-centered, reproducible benchmarks that account for modeling choices, scaling, and evolving hardware.

  • Execution example: Depth-two QAOA was executed on random-three-regular graphs with up to forty nodes using superconducting processors with 127 qubits.Only a third of the physical qubits were needed, so the best qubits were selected using two-qubit gate fidelity.
  • Execution example: A large gap between noiselessly simulated optimized samples and hardware samples demonstrated the need for error mitigation of samples.The variational parameters were optimized using machine-learning-based mitigation of expectation values.
  • Benchmarking rationale: Benchmarking provides realistic performance insights when analytical complexity results do not capture real-world application difficulty.It can also motivate deeper analytical studies.
  • Benchmarking rationale: The proposed benchmarking setting aims to make classical and quantum comparisons thorough, robust, fair, and reproducible.The framework discusses benchmark goals, evaluation metrics, and representative optimization problems.
  • Related work: Classical optimization challenges and libraries provide useful precedents, but compatible competitions and libraries for near-term quantum optimization do not yet exist.Existing quantum-oriented frameworks mainly benchmark hardware using optimization problems as applications.
  • Benchmark goals: Problem-centric benchmarks should enable direct comparison of classical and quantum solver runtimes and solution qualities.The paper argues that established classical-platform benchmarks such as SPEC and LINPACK are not suited to this comparison.
  • Benchmark goals: Benchmarks can track hardware and algorithmic progress while revealing how solution resources scale with problem size.In MIPLIB examples, many but not all larger instances require longer solver runtimes.
  • Model-(In)Dependence: Model-independent benchmarks permit different mathematical formulations and can accommodate capabilities introduced by new hardware generations.The paper expects them to help assess whether quantum methods approach, meet, or exceed classical capabilities on particular instances.

2. Pre-processing

The paper treats pre-processing, platform choice, benchmarking, and instance selection as central factors in evaluating quantum optimization. It emphasizes matching problems and platforms while reporting costs and limitations fairly.

  • Pre-processing: Pre-processing modifies instances before optimization and must be included in benchmark performance evaluations because it requires classical computational effort.Its implementation depends on the formulation, data, algorithm, and computational platform.
  • Platform choice: Different computational platforms have distinct strengths, bottlenecks, models, and applicable algorithms, so platform suitability depends on the optimization problem.Cross-platform benchmarking is needed to compare systems fairly and identify suitable matches.
  • Metrics: Four metric categories support fair comparisons across classical and quantum systems: resource cost, run time, quality, and problem complexity.Holistic benchmarks should select and faithfully report metrics according to the problem, model, algorithm, and execution platform.
  • Metrics: Effective run time can include pre-processing, transpilation, embedding, compilation, execution, and post-processing, with total time offering a fair comparison.Analyzing its composition can reveal costly steps and bottlenecks, while QPU time helps assess software efficiency.
  • Benchmark problems: Standardized benchmark problems should challenge classical solvers while remaining deployable on current or near-term quantum technologies.Suitable instances require manageable variable counts, connection density, and coefficient sizes, creating a potential comparison window for quantum advantage.
  • Benchmark problems: Benchmark candidates include crafted and random binary problems, although random instances lack structure and their practical meaning can be debated.Real-world difficult instances are scarce because relevant industrial problems are often unpublished, ill-defined, or solvable with existing methods.

E. Demonstrations

The demonstrations expose hardware, problem-selection, and comparison challenges in current quantum optimization experiments. They also show scaling strategies and motivate common metrics for future benchmarks.

  • Experimental challenges: Large-scale quantum optimization demonstrations must address hardware limitations and the difficulty of selecting appropriate benchmarking problems.Many demonstrations use QUBO-type problems with grid structures, and feasible quantum solutions do not by themselves establish superiority over classical methods.
  • Experimental overview: Table IV surveys gate-based experiments with more than 15 variables, covering QAOA or VQE variants on MAXCUT, Sherrington-Kirkpatrick, and QUBO/PUBO problems.The table reports approximation ratios and marks unavailable data as N/A while defining the listed abbreviations.
  • Scaling and noise: Higher-qubit experiments generally use lower problem densities, because denser interactions require additional SWAP gates and increase hardware noise.The same pattern appears in the resulting approximation ratios.
  • Metrics: Approximation ratios require consistent normalization across problem types, using (Cmax − ⟨C⟩)/(Cmax − Cmin) after converting problems to minimization.This accommodates objective values that may occupy arbitrary intervals in general problems.
  • Scaling demonstrations: QRAO solved planar MAXCUT instances with up to 40 variables using 15 qubits at an approximation ratio of 0.905.A qubit-reuse QAOA variant scaled to 130 variables on 32 qubits with an approximation ratio around 0.8, though comparisons with standard approaches are difficult.
  • Benchmarking outlook: These demonstrations provide a foundation for future quantum optimization benchmarks while underscoring the need for common metrics and fair comparisons.The section presents this work as an initial coordinated effort toward that goal.

VII. ILLUSTRATIVE APPLICATIONS

The applications survey uses finance and sustainability to illustrate optimization problems with increasing complexity and practical constraints. It emphasizes finance’s uncertainty, temporal dependence, and need for quantum approaches alongside rigorous classical benchmarking.

  • Applications: Finance and sustainable energy are presented as industries with numerous optimization challenges and increasing model complexity.The discussion uses these domains to motivate quantum algorithm development and benchmark construction.
  • Finance: Financial optimization must balance return, risk appetite, time horizon, additional objectives, and constraints in a stochastic system.Portfolio composition is described as one of finance’s hardest optimization problems, with substantial practical impact from marginal improvements.
  • Finance: Level 2 incorporates uncertainty in estimated returns and covariance, because small estimation changes can produce large differences in the optimal portfolio.Level 1’s omission of input uncertainty makes its investment decisions of limited practical value.
  • Finance: Limited financial data produces a positive observation ratio q = N/T, preventing sample estimators from generally converging to population parameters.Convergence is described only in the large-data limit q →0, whereas most asset-allocation problems have q > 0.
  • Finance: Level 3 extends portfolio optimization from a static one-period setting to market dynamics, temporal dependence, and multi-period uncertainty.The paper notes that correlations fluctuate, evolve over time, and may jump or change sign.
  • Finance: The paper argues that quantum optimization research should progress from Level 1 studies toward Level 2 and 3 problems involving uncertainty.This progression is framed as a route toward more valuable financial-industry contributions.

4. Outlook

The outlook identifies finance and sustainable energy as sources of realistic optimization challenges and benchmarking instances. It stresses that these problems can expose where quantum optimization may or may not have potential over classical methods.

  • Finance: Financial optimization spans risk management, asset allocation, option pricing, macroeconomic modeling, trading, and lending.The paper presents these applications as a broad source of challenging use cases for quantum algorithmic development.
  • Finance: The paper’s financial review highlights the need to combine problem modeling and optimization to obtain practically relevant industry results.It also identifies skewed distributions, Bayesian approaches, subgroup-specific priors, and non-Markovian processes as further directions.
  • Sustainable Energy Transition: Sustainable energy transition is used as a source of optimization problems with societal benefit and examples derived from real-world data.The use cases are intended to benchmark algorithms and study problem characteristics relevant to quantum and classical methods.
  • Sustainable Energy Transition: Renewable energy is intermittent and probabilistic, requiring coordination of many assets to match supply with demand.Energy storage is essential for managing renewable variability but introduces additional challenges.
  • Sustainable Energy Transition: The power-grid discussion covers unit commitment and e-Mobility use cases, including charging problems linked to optimization problem classes and algorithms.The section presents three types of power-grid optimization problems and outlines related research directions.

2. Related Work

Related work in quantum optimization for power grids remains early and focuses largely on small, simplified models. The paper develops e-Mobility and storage examples that connect practical energy challenges to established optimization formulations.

  • Power Grids: Power-grid quantum-optimization research is currently early-stage, with predominant attention to unit commitment problems.Existing approaches combine quantum treatment of binary variables with classical optimization of continuous variables or formulate problems as QUBOs.
  • Power Grids: Existing power-grid studies commonly use small illustrative instances and simple mathematical models that do not capture real-world complexity.Their value is primarily advancing theory, formulations, algorithms, and understanding of practical requirements.
  • e-Mobility: Energy storage and coordinated charging are motivated by renewable generation that often occurs when demand is low.The paper identifies optimized storage coordination as important for addressing this mismatch.
  • e-Mobility: EV charging is positioned as an increasingly important storage resource, with projected growth to about 240 million vehicles in 2030.The passage estimates that 400 EVs could theoretically deliver 4 MWh, approximately matching an energy-storage substation’s output power.
  • e-Mobility: Parking-site scheduling allocates EVs to regular or charging-enabled spaces to maximize charging volumes and profit.The formulation represents EV presence, value, requested energy, site input-power limits, and capacity constraints.
  • e-Mobility: The parking-allocation problem is a binary optimization with 2K knapsack constraints covering parking spaces and available site energy.Extensions can add time-varying power, pricing, charging flexibility, and uncertain arrivals or renewable forecasts.
  • e-Mobility: The EV charging-and-discharging problem can be modeled as discrete optimal control, but is less promising for near-term industrial quantum advantage.The formulation maps to unit commitment, which commercial solvers can handle efficiently with hundreds of units.
  • e-Mobility: The resulting convex optimization problem can be solved efficiently with conventional tools when its random inputs are independent of the decision variables.Under that condition, the problem separates into K independent problems.

4. Outlook

The outlook emphasizes benchmarking, empirical testing, and responsible application as quantum optimization develops toward practical impact. It identifies sustainability as a promising application area while noting that practical quantum advantage remains to be demonstrated.

  • Sustainable energy transition problems offer illustrative test cases, although their classical difficulty depends on assumptions about the problem data.
  • Benchmarking problem instances is crucial for identifying which cases are classically difficult and where potential quantum advantage may exist.
  • Complexity theory can guide provable performance guarantees, but quantum optimization also needs heuristic development and empirical evaluation.
  • Experiments on improving quantum hardware can provide intuition and help validate algorithmic proposals, even without immediately demonstrating practical quantum advantage.
  • Responsible research requires avoiding overstatement, interpreting results through clear benchmarks, and prioritizing applications with positive social impact.
  • Practical quantum advantage remains challenging to demonstrate despite quantum optimization’s potential across applications.
Loading 2312.02279v3…