REVIEW 11 cited by
Challenges and Opportunities in Quantum Optimization
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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.
Forward citations
Cited by 11 Pith papers
-
Quantum-informed surrogate sampling for combinatorial optimization
QISS classically samples a pairwise model built from O(N) low-weight QAOA correlators and outperforms standard QAOA at larger depths on MaxCut and MIS benchmarks.
-
Performance enhancing of hybrid quantum-classical Benders approach for MILP optimization
Precomputed embeddings reduce the preprocessing overhead of a quantum-annealer-based Benders decomposition by about an order of magnitude on small transmission-network expansion problems, with no loss in solution quality.
-
Role of Nonstabilizerness in Quantum Optimization
QAOA on Sherrington-Kirkpatrick models shows a peak in nonstabilizerness at intermediate depth followed by a decline toward the solution, a magic barrier that also appears in adiabatic quantum annealing.
-
Left-Deep Join Order Selection with Higher-Order Unconstrained Binary Optimization on Quantum Computers
A HUBO-based encoding of left-deep join order selection claims DP-equivalent optimality and greedy-level guarantees with fewer variables, but the formal proof and validity constraints are incomplete.
-
Simulation and Benchmarking of Real Quantum Hardware
A calibration-only noise model that places depolarizing error on gates and T1/T2 decay on idle qubits reproduces a 20-qubit chip's output histograms and outperforms two prior noise models on deep circuits.
-
Optimizing QUBO on a quantum computer by mimicking imaginary time evolution
ITEMC iteratively mimics imaginary time evolution to solve QUBO instances, achieving high CVaR-based approximation ratios in simulation and finding the best known solution on IBM hardware for up to 80 qubits.
-
Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors
Density and treewidth make natively embeddable unit-disk graph MIS instances harder for CPLEX, and current neutral-atom quantum devices are still about three orders of magnitude slower than classical solvers.
-
Large Language Models for Next-Generation Wireless Network Management: A Survey and Tutorial
A survey and tutorial that organizes LLM-enabled wireless network optimization into formulation, solution, and verification stages, with case studies drawn from the authors' own prior papers.
-
Gaussian boson sampling for binary optimization
A threshold-detector Gaussian boson sampler trained with a risk-sensitive cost function samples solutions to small 3-SAT and graph partitioning instances with higher probability than random guessing.
-
Application of quantum annealing for scalable robotic assembly line optimization: a case study
Quantum annealing can solve a small robotic assembly line balancing problem as a QUBO, but it is slower and less reliable than classical baselines on the tested instance.
-
Perspectives on Utilization of Measurements in Quantum Algorithms
A survey that categorizes quantum measurement uses into static circuits, dynamic circuits, and challenge-solving techniques, and argues measurements deserve more attention in algorithm design.
Discussion (0). Continue with ORCID to comment.