Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chakrabarti, Shouvanik, Herman, Dylan, Ozgul, Guneykan, Zhu, Shuchen, Augustino, Brandon, Hao, Tianyi, He, Zichang, Shaydulin, Ruslan, Pistoia, Marco
Format:	Preprint
Published:	2024
Subjects:	Quantum Physics Data Structures and Algorithms Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Quantum Speedups for Group Relaxations of Integer Linear Programs
by: Augustino, Brandon, et al.
Published: (2026)

On Speedups for Convex Optimization via Quantum Dynamics
by: Chakrabarti, Shouvanik, et al.
Published: (2025)

Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
by: He, Zichang, et al.
Published: (2023)

Quantum Speedups for Markov Chain Monte Carlo Methods with Application to Optimization
by: Ozgul, Guneykan, et al.
Published: (2025)

Parameter Setting in Quantum Approximate Optimization of Weighted Problems
by: Sureshbabu, Shree Hari, et al.
Published: (2023)

Variational Quantum Algorithm Landscape Reconstruction by Low-Rank Tensor Completion
by: Hao, Tianyi, et al.
Published: (2024)

Fast Convex Optimization with Quantum Gradient Methods
by: Augustino, Brandon, et al.
Published: (2025)

Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm
by: Omanakuttan, Sivaprasad, et al.
Published: (2025)

Mechanisms for Quantum Advantage in Global Optimization of Nonconvex Functions
by: Herman, Dylan, et al.
Published: (2025)

Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
by: He, Zichang, et al.
Published: (2024)

Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
by: Andrist, Ruben S., et al.
Published: (2023)

End-to-End Protocol for High-Quality QAOA Parameters with Few Shots
by: Hao, Tianyi, et al.
Published: (2024)

Quantum Speedups for Derivative Pricing Beyond Black-Scholes
by: Herman, Dylan, et al.
Published: (2026)

Performance of Quantum Approximate Optimization with Quantum Error Detection
by: He, Zichang, et al.
Published: (2024)

Non-Variational Quantum Random Access Optimization with Alternating Operator Ansatz
by: He, Zichang, et al.
Published: (2025)

Iterative Interpolation Schedules for Quantum Approximate Optimization Algorithm
by: Apte, Anuj, et al.
Published: (2025)

QAOA with $N\cdot p\geq 200$
by: Shaydulin, Ruslan, et al.
Published: (2023)

Regularized Warm-Started Quantum Approximate Optimization and Conditions for Surpassing Classical Solvers on the Max-Cut Problem
by: He, Zichang, et al.
Published: (2026)

Spin-Boson Mapping of the Quantum Approximate Optimization Algorithm
by: Boulebnane, Sami, et al.
Published: (2025)

Iceberg Beyond the Tip: Co-Compilation of a Quantum Error Detection Code and a Quantum Algorithm
by: Jin, Yuwei, et al.
Published: (2025)

Quantum Approximate Optimization Algorithm in Finite Size and Large Depth and Equivalence to Quantum Annealing
by: Boulebnane, Sami, et al.
Published: (2025)

Quantum counterdiabatic driving with local control
by: Li, Changhao, et al.
Published: (2024)

qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem
by: Schuetz, Martin J. A., et al.
Published: (2025)

Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
by: Acharya, Atithi, et al.
Published: (2024)

End-to-end quantum algorithms for tensor problems
by: Fontana, Enrico, et al.
Published: (2025)

The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
by: Fontana, Enrico, et al.
Published: (2023)

Prospects of Privacy Advantage in Quantum Machine Learning
by: Heredge, Jamie, et al.
Published: (2024)

Applications of Certified Randomness
by: Amer, Omar, et al.
Published: (2025)

Quantum Deep Hedging
by: Cherrat, El Amine, et al.
Published: (2023)

Privacy-preserving quantum federated learning via gradient hiding
by: Li, Changhao, et al.
Published: (2023)

Quantum Compilation Toolkit for Rydberg Atom Arrays with Implications for Problem Hardness and Quantum Speedups
by: Schuetz, Martin J. A., et al.
Published: (2024)

Quantum Speedup for Nonreversible Markov Chains
by: Claudon, Baptiste, et al.
Published: (2025)

A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems
by: Chen, Tyler, et al.
Published: (2025)

Compilation Pipeline for Predicting Algorithmic Break-Even in an Early-Fault-Tolerant Surface Code Architecture
by: Hao, Tianyi, et al.
Published: (2025)

Data for Certified randomness amplification by dynamically probing remote random quantum states
by: Liu, Minzhao, et al.
Published: (2025)

QC-Forest: a Classical-Quantum Algorithm to Provably Speedup Retraining of Random Forest
by: Yalovetzky, Romina, et al.
Published: (2024)

Blind quantum machine learning with quantum bipartite correlator
by: Li, Changhao, et al.
Published: (2023)

Quantum option pricing via the Karhunen-Loève expansion
by: Prakash, Anupam, et al.
Published: (2024)

Fault-tolerant execution of error-corrected quantum algorithms
by: Perlin, Michael A., et al.
Published: (2026)

Combinatorial Markov Search
by: Bowers, Robin, et al.
Published: (2025)