Challenges and Opportunities in Quantum Optimization
read the original abstract
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 6 Pith papers
-
Gated QKAN-FWP: Scalable Quantum-inspired Sequence Learning
Gated QKAN-FWP combines fast weight programming with quantum-inspired Kolmogorov-Arnold networks via single-qubit DARUAN activations and gated updates to deliver a 12.5k-parameter model that outperforms larger classic...
-
Scalable Determination of Penalization Weights for Constrained Optimizations on Approximate Solvers
A pre-computation method sets penalization weights for constrained QUBO problems with provable guarantees for Gibbs solvers and polynomial scaling for many problem classes.
-
Why Global LLM Leaderboards Are Misleading: Small Portfolios for Heterogeneous Supervised ML
Global Bradley-Terry rankings of LLMs are misleading due to structured heterogeneity in user preferences, and small (λ, ν)-portfolios recover coherent subpopulations that cover over 96% of votes with just five rankings.
-
Accelerating Noisy Variational Quantum Algorithms with Physics-Informed Denoising Networks
PIDN replaces repeated multi-noise ZNE evaluations with a trained network that denoises expectation values and gradients from noisy data plus history, achieving comparable optimization on quantum models with 4-6x fewe...
-
Hamiltonian-reconstruction distance as a success metric for the Variational Quantum Eigensolver
Hamiltonian-reconstruction distance is shown to correlate with ground-state fidelity and serves as a practical success metric for VQE on 1D and 2D Ising models in simulation and on trapped-ion hardware.
-
Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing
The authors integrate quantum annealing and QAOA as subroutines for pricing and separation in a branch-price-and-cut algorithm for vehicle routing problems.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.