Fetching the paper…

Reading the bibliography…

2019

Classical and Quantum Bounded Depth Approximation Algorithms

Hastings, M. B.

Original
PDF
Post on X

Understand

We consider some classical and quantum approximate optimization algorithms with bounded depth.

First, we define a class of "local" classical optimization algorithms and show that a single step version of these algorithms can achieve the same performance as the single step QAOA on MAX-3-LIN-2.
Second, we show that this class of classical algorithms generalizes a class previously considered in the literature, and also that a single step of the classical algorithm will outperform the single-step QAOA on all triangle-free MAX-CUT instances.
In fact, for all but $4$ choices of degree, existing single-step classical algorithms already outperform the QAOA on these graphs, while for the remaining $4$ choices we show that the generalization here outperforms it.

Classical and Quantum Bounded Depth Approximation Algorithms · Around

Built on

E. Aarts and J. Korst, Simulated annealing and Boltzmann machines (New York, NY; John Wiley and Sons Inc., 1988)
1988
Earlier work this paper cites.
S. R. White, Physical Review Letters 69
1992
Earlier work this paper cites.
G. Vidal, J. I. Latorre, E. Rico, and A. Kitaev, Physical Review Letters 90
2003
Earlier work this paper cites.
M. B. Hastings, Journal of Statistical Mechanics: Theory and Experiment 2007
2007
Earlier work this paper cites.
B. Pirvu, V. Murg, J. I. Cirac, and F. Verstraete, New Journal of Physics 12
2010
Earlier work this paper cites.

Similar

J. Suomela, ACM Computing Surveys (CSUR) 45
2013
Cited alongside, same era.
J. Hirvonen, J. Rybicki, S. Schmid, and J. Suomela, arXiv preprint arXiv:1402.2543 (2014)
Original
2014
Cited alongside, same era.
E. Farhi, J. Goldstone, and S. Gutmann, arXiv preprint arXiv:1412.6062 (2014)
Original
2014
Cited alongside, same era.
R. O’Donnell, Analysis of boolean functions (Cambridge University Press, 2014)
2014
Cited alongside, same era.

Then

B. Barak, A. Moitra, R. O’Donnell, P. Raghavendra, O. Regev, D. Steurer, L. Trevisan, A. Vijayaraghavan, D. Witmer, and J. Wright, arXiv preprint arXiv:1505.03424 (2015)
Original
2015
Later among the works it cites.
Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Physical Review A 97
2018
Later among the works it cites.
C. Ryan-Anderson, arXiv preprint arXiv:1812.04735 (2018)
Original
2018
Later among the works it cites.
M. B. Hastings, arXiv:1904.13339 (2019)
Original
2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…