Fetching the paper…
Reading the bibliography…
We present new advances towards achieving exponential quantum speedups for solving optimization problems by low-depth quantum algorithms.
Strengths and weaknesses of quantum computing
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani · 1997
Earlier work this paper cites.
How powerful is adiabatic quantum computation?
Wim van Dam, Michele Mosca, and Umesh Vazirani · 2001
Earlier work this paper cites.
Quantum adiabatic evolution algorithms versus simulated annealing
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2002
Earlier work this paper cites.
Noise-tolerant learning, the parity problem, and the statistical query model
Avrim Blum, Adam Kalai, and Hal Wasserman · 2003
Earlier work this paper cites.
The quantum approximate optimization algorithm needs to see the whole graph: A typical case
Edward Farhi, David Gamarnik, and Sam Gutmann · 2004
Earlier work this paper cites.
The quantum adiabatic optimization algorithm and local minima
Ben W. Reichardt · 2004
Earlier work this paper cites.
The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples
Edward Farhi, David Gamarnik, and Sam Gutmann · 2005
Earlier work this paper cites.
Public-key cryptography from different assumptions
Benny Applebaum, Boaz Barak, and Avi Wigderson · 2010
Earlier work this paper cites.
Cryptography from learning parity with noise
Krzysztof Pietrzak · 2012
Earlier work this paper cites.
A Quantum Approximate Optimization Algorithm
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2014
Earlier work this paper cites.
Tunneling and speedup in quantum optimization for permutation-symmetric problems
Siddharth Muthukrishnan, Tameem Albash, and Daniel A. Lidar · 2016
Earlier work this paper cites.
Data extraction via histogram and arithmetic mean queries: Fundamental limits and algorithms
I-Hsiang Wang, Shao-Lun Huang, Kuan-Yun Lee, and Kwang-Cheng Chen · 2016
Earlier work this paper cites.
Partial data extraction via noisy histogram queries: Information theoretic bounds
Wei-Ning Chen and I-Hsiang Wang · 2017
Cited alongside, same era.
The saddle-point method in ℂ N \mathbb{C}^{N} and the generalized Airy functions
Francesco Pinna and Carlo Viola · 2019
Cited alongside, same era.
Quantum approximate optimization of the long-range ising model with a trapped-ion quantum simulator
Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine S. Collins, Arinjoy De, Paul W. Hess, Harvey B. Kaplan, Antonis Kyprianidis, Wen Lin Tan, Christopher Baldwin, Lucas T. Brady, Abhinav Deshpande, Fangli Liu, Stephen Jordan, Alexey V. Gorshkov, and Christopher Monroe · 2020
Cited alongside, same era.
Obstacles to variational quantum optimization from symmetry protection
Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang · 2020
Cited alongside, same era.
Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin · 2020
The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou · 2022
Later among the works it cites.
The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou · 2022
Later among the works it cites.
Talk presented at 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC’22), 2022
The QAOA at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model · 2022
Later among the works it cites.
On the parallel reconstruction from pooled data
Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Philipp Loick · 2022
Later among the works it cites.
Concentration Bounds for Quantum States and Limitations on the QAOA from Polynomial Approximations
Anurag Anshu and Tony Metger · 2023
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Quantum approximate optimization of non-planar graph problems on a planar superconducting processor
Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, et al · 2021
Cited alongside, same era.
Sami Boulebnane and Ashley Montanaro · 2021
Cited alongside, same era.
Instance independence of single layer quantum approximate optimization algorithm on mixed-spin models at infinite size
Jahan Claes and Wim van Dam · 2021
Cited alongside, same era.
Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
Sepehr Ebadi, Alexander Keesling, Madelyn Cain, Tout T. Wang, Harry Levine, Dolev Bluvstein, Giulia Semeghini, Ahmed Omran, Jinguo Liu, Rhine Samajdar, Xiu-Zhe Luo, Beatrice Nash, Xun Gao, Boaz Barak, Edward Farhi, Subir Sachdev, Nathan Gemelke, Leo Zhou, Soonwon Choi, Hannes Pichler, Shengtao Wang, Markus Greiner, Vladan Vuletic, and Mikhail D. Lukin · 2022
Cited alongside, same era.
Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond
Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi · 2022
Cited alongside, same era.
Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
Joao Basso, David Gamarnik, Song Mei, and Leo Zhou · 2022
Cited alongside, same era.
Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs
Antares Chen, Neng Huang, and Kunal Marwaha · 2023
Later among the works it cites.
Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke · 2023
Later among the works it cites.
Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem
Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, and Marco Pistoia · 2024
Closest in time.
Solving Boolean Satisfiability Problems With The Quantum Approximate Optimization Algorithm
Sami Boulebnane and Ashley Montanaro · 2024
Closest in time.
Algorithms for Sparse LPN and LSPN Against Low-noise
Xue Chen, Wenxuan Shu, and Zhaienhe Zhou · 2024
Closest in time.
A Non-Adaptive Algorithm for the Quantitative Group Testing Problem
Mahdi Soleymani and Tara Javidi · 2024
Closest in time.