Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911295653019648 |
|---|---|
| author | Chakrabarti, Shouvanik Herman, Dylan Ozgul, Guneykan Zhu, Shuchen Augustino, Brandon Hao, Tianyi He, Zichang Shaydulin, Ruslan Pistoia, Marco |
| author_facet | Chakrabarti, Shouvanik Herman, Dylan Ozgul, Guneykan Zhu, Shuchen Augustino, Brandon Hao, Tianyi He, Zichang Shaydulin, Ruslan Pistoia, Marco |
| contents | We analyze generalizations of quantum algorithms based on the short path framework first proposed by Hastings~[\textit{Quantum} 2, 78 (2018)], which has been extended and shown by Dalzell~et~al.~[STOC~'23] to achieve super-Grover speedups for certain binary optimization problems. We demonstrate that, under some commonly satisfied technical conditions, an appropriate generalization can achieve super-quadratic speedups not only over unstructured search but also over a classical optimization algorithm that searches for the optimum by drawing samples from the stationary distribution of a Markov chain. We employ this framework to obtain algorithms for problems including variants of Max Bisection, Max Independent Set, and finding the ground states of the Antiferromagnetic Ising Model and the Sherrington-Kirkpatrick Model, whose runtimes are asymptotically faster than those obtainable with previous short path techniques. In certain cases, our algorithms achieve super-quadratic speedups compared to the best known classical algorithms with rigorously established runtimes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23270 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization Chakrabarti, Shouvanik Herman, Dylan Ozgul, Guneykan Zhu, Shuchen Augustino, Brandon Hao, Tianyi He, Zichang Shaydulin, Ruslan Pistoia, Marco Quantum Physics Data Structures and Algorithms Optimization and Control We analyze generalizations of quantum algorithms based on the short path framework first proposed by Hastings~[\textit{Quantum} 2, 78 (2018)], which has been extended and shown by Dalzell~et~al.~[STOC~'23] to achieve super-Grover speedups for certain binary optimization problems. We demonstrate that, under some commonly satisfied technical conditions, an appropriate generalization can achieve super-quadratic speedups not only over unstructured search but also over a classical optimization algorithm that searches for the optimum by drawing samples from the stationary distribution of a Markov chain. We employ this framework to obtain algorithms for problems including variants of Max Bisection, Max Independent Set, and finding the ground states of the Antiferromagnetic Ising Model and the Sherrington-Kirkpatrick Model, whose runtimes are asymptotically faster than those obtainable with previous short path techniques. In certain cases, our algorithms achieve super-quadratic speedups compared to the best known classical algorithms with rigorously established runtimes. |
| title | Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization |
| topic | Quantum Physics Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2410.23270 |