In classical optimization, the dimensionality of a problem—whether measured by the number of variables $d$, available strategies $n$, or financial assets $N$—acts as a fundamental computational tax. As the number of dimensions grows, classical algorithms typically must inspect each direction or strategy sequentially. This reality leads to linear, quadratic, or even exponential scaling bottlenecks, often referred to as the "curse of dimensionality."
A rapidly growing body of research demonstrates that quantum algorithms can fundamentally alter this scaling. By leveraging quantum superposition, interference, and wave dynamics, these algorithms can evaluate high-dimensional spaces simultaneously. Instead of merely speeding up calculations by a constant factor, quantum optimization can compress the dependency on the problem's dimension from linear to sublinear, or even from polynomial to polylogarithmic.
Sublinear Scaling in Strategy and Action Spaces
Consider an online learning scenario or a multi-player game where an agent must choose from a massive pool of $N$ strategies. Classically, updating the probabilities or weights for each strategy requires looking at every single option, incurring a cost that scales linearly as $\mathcal{O}(N)$.
Quantum algorithms bypass this linear scan by using amplitude amplification and quantum minimum-finding subroutines. In Quantum algorithms for hedging and the learning of Ising models, Patrick Rebentrost et al. demonstrated that quantum versions of online learning frameworks (like the Hedge algorithm and the Sparsitron) can reduce this strategy-dependent complexity from $\mathcal{O}(N)$ to $\mathcal{O}(\sqrt{N})$.
This quadratic relief directly translates to high-dimensional financial and game-theoretic problems:
- Portfolio Optimization: In large-scale asset management, classical transaction and optimization costs scale linearly with the number of available assets. To overcome this, Debbie Lim et al. combined quantum state preparation with multi-sampling techniques in A Quantum Online Portfolio Optimization Algorithm, proving that transaction costs can be made completely independent of the total asset count. Similarly, Patrick Rebentrost et al. applied zero-sum game formulations to derivative pricing in Quantum computational finance for martingale asset pricing in incomplete markets, achieving a quadratic speedup relative to the number of market outcomes and assets.
- Equilibrium Finding: Finding Nash or correlated equilibria in games typically requires exploring a massive joint action space. In Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games, Minbo Gao et al. introduced a fast quantum multi-Gibbs sampler that scales with the square root of the number of strategies rather than the total number of strategy pairs. For general-sum multi-player games, Tongyang Li et al. showed in Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games that quantum superposition and interference compress the query complexity of finding correlated equilibria from linear to sublinear relative to the action space.
Bypassing the Gradient Tax in Zeroth-Order Optimization
When optimizing a "black-box" function where explicit gradients are unavailable, algorithms must rely solely on function evaluations (zeroth-order optimization). Classically, estimating a gradient in a $d$-dimensional space requires perturbing the input along every single coordinate direction, costing at least $\mathcal{O}(d)$ function evaluations.
Classical Zeroth-Order: Evaluates each dimension sequentially
[Dimension 1] ---> f(x + e_1)
[Dimension 2] ---> f(x + e_2) ===> Total Cost: O(d)
[Dimension d] ---> f(x + e_d)
Quantum Zeroth-Order: Evaluates all dimensions in superposition
|x⟩ ⊗ |e_1 + e_2 + ...
+ e_d⟩ ---> [Quantum Oracle] ---> ===> Total Cost: Independent of d / Sub-linear
Quantum algorithms can evaluate these directional perturbations simultaneously by querying the objective function in superposition. In Fast Zeroth-Order Convex Optimization with Quantum Gradient Methods, Junhyung Lyle Kim et al. demonstrated that quantum algorithms can achieve an exponential reduction in query complexity relative to dimensionality. By evaluating noisy functions in superposition, the quantum approach matches the query complexity of classical algorithms that have full access to exact gradients, effectively making the optimization cost independent of the number of variables.
This dimensional relief extends across several derivative-free optimization domains:
- Minimax Optimization: Essential for training Generative Adversarial Networks (GANs) and robust AI, zeroth-order minimax optimization classically scales linearly with dimension. In Quantum Speedups for Minimax Optimization and Beyond, Chengchang Liu et al. proved that quantum methods can estimate Hessian matrices more efficiently, dropping the dimensional dependency to a fractional power ($\tilde{\mathcal{O}}(d^{2/3})$).
- Comparison Oracles: When an algorithm can only ask a comparison oracle which of two points is better, reconstructing the underlying landscape is notoriously difficult. Helin Wang et al. showed in Finding Stationary Points by Comparisons that while classical comparison-based optimization requires $\widetilde{O}(n^2)$ queries to extract second-order Hessian information, quantum techniques reduce this dependency quadratically to $\widetilde{O}(n)$.
Exploiting Physical Dynamics to Escape Saddle Points
In non-convex optimization, algorithms frequently get trapped near saddle points where the gradient vanishes but local downward paths exist. Classical methods typically escape these regions by injecting uniform random perturbations, hoping that a random vector will happen to align with a direction of negative curvature. In high-dimensional spaces, this is highly inefficient because the vast majority of random directions lead to flat or upward terrain.
Quantum mechanics provides a physical alternative to random guessing. By treating the optimization landscape as a potential energy field, an algorithm can simulate the physical evolution of a quantum wave packet via the Schrödinger or wave equations.
As shown by Chenyi Zhang et al. in Quantum algorithms for escaping from saddle points, a quantum wave packet naturally disperses and flows along directions of negative curvature. Because the wave's physical expansion inherently exploits the mathematical structure of the potential field, the algorithm avoids the need for isotropic trial-and-error. This physical mechanism reduces the query complexity required to escape saddle points from a polynomial function of the dimension $n$ down to a polylogarithmic relationship ($\mathcal{O}(\text{polylog}(n))$).
Taming Structure and Noise
The mathematical machinery driving these dimensional speedups has also been adapted to structured and constrained optimization problems:
- Submodular and Projection-Free Optimization: For discrete optimization, Patrick Rebentrost et al. accelerated the sampling processes required for stochastic subgradient descent in Quantum and Classical Algorithms for Approximate Submodular Function Minimization. For continuous DR-submodular maximization under systematically biased gradients, Shengminjie Chen et al. demonstrated in DR-Submodular Maximization with Stochastic Biased Gradients: Classical and Quantum Gradient Algorithms that quantum zero-order methods can drastically compress iteration complexity. Furthermore, Jianhao He et al. introduced quantum subroutines for gradient estimation and maximum finding within the Frank-Wolfe framework in Quantum Algorithms for Projection-Free Sparse Convex Optimization, yielding a square-root speedup in the problem dimension $d$.
- Noise Robustness: Quantum speedups are only useful if they can survive noise. In Isotropic Noise in Stochastic and Quantum Convex Optimization, Annie Marsden et al. developed a "quantum isotropifier" algorithm that handles gradient noise bounded uniformly in every direction, proving a polynomial improvement in dimensional scaling over previous quantum stochastic optimization methods. To address algorithmic noise in continuous optimization, Zeguan Wu et al. designed an Inexact-Feasible Quantum Interior Point Method in An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization that maintains solution feasibility despite quantum noise, outperforming classical algorithms in how computational cost scales with the problem dimension.
Ultimately, these diverse approaches share a core insight: by mapping mathematical dimensions to quantum states or physical potentials, optimization algorithms can navigate high-dimensional landscapes globally rather than coordinate-by-coordinate, fundamentally mitigating the curse of dimensionality.
Key Foundational Work
Quantum Algorithms for Escaping from Saddle Points (2021) — contributed 5 concept elements to this direction.
Quantum and Classical Algorithms for Approximate Submodular Function Minimization (2019) — contributed 1 concept elements to this direction.
Quantum algorithms for hedging and the learning of Ising models (2021) — contributed 1 concept elements to this direction.