Fetching the paper…
Reading the bibliography…
We study the performance of local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) for the maximum cut problem, and their relationship to that of classical algorithms.
Classical and quantum bounded depth approximation algorithms, 2019
M. B. Hastings · 1905
Earlier work this paper cites.
Obstacles to state preparation and variational optimization from symmetry protection
S. Bravyi, A. Kliesch, R. Koenig, and E. Tang · 1910
Earlier work this paper cites.
E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou · 1910
Earlier work this paper cites.
The finite group velocity of quantum spin systems
E. H. Lieb and D. W. Robinson · 1972
Earlier work this paper cites.
Universal sequential search problems
L. A. Levin · 1973
Earlier work this paper cites.
Some rigorous results on the sherrington-kirkpatrick spin glass model
M. Aizenman, J. L. Lebowitz, and D. Ruelle · 1987
Earlier work this paper cites.
Locality in distributed graph algorithms
N. Linial · 1992
Earlier work this paper cites.
A note on bipartite subgraphs of triangle-free graphs
J. B. Shearer · 1992
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. W. Shor · 1994
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
M. X. Goemans and D. P. Williamson · 1995
Earlier work this paper cites.
Fault-tolerant quantum computation with constant error rate
D. Aharonov and M. Ben-Or · 1997
Earlier work this paper cites.
Fault-tolerant quantum computation by anyons
A. Y. Kitaev · 1997
Earlier work this paper cites.
Resilient quantum computation
E. Knill, R. Laflamme, and W. H. Zurek · 1998
Earlier work this paper cites.
How good is the goemans–williamson max cut algorithm?
H. Karloff · 1999
Earlier work this paper cites.
Broadcasting on trees and the ising model
W. Evans, C. Kenyon, Y. Peres, and L. J. Schulman · 2000
Earlier work this paper cites.
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization
P. A. Parrilo · 2000
Earlier work this paper cites.
Some optimal inapproximability results
J. Håstad · 2001
Earlier work this paper cites.
Global optimization with polynomials and the problem of moments
J. B. Lasserre · 2001
Earlier work this paper cites.
Efficient classical simulation of random shallow 2d quantum circuits
J. Napp, R. L. La Placa, A. M. Dalzell, F. G. Brandao, and A. W. Harrow · 2001
Earlier work this paper cites.
On the power of unique 2-prover 1-round games
S. Khot · 2002
Cited alongside, same era.
What limits the simulation of quantum computers?
Y. Zhou, E. M. Stoudenmire, and X. Waintal · 2002
Cited alongside, same era.
The quantum approximate optimization algorithm needs to see the whole graph: a typical case
E. Farhi, D. Gamarnik, and S. Gutmann · 2004
Cited alongside, same era.
Quantum approximate optimization of non-planar graph problems on a planar superconducting processor
M. P. Harrigan, K. J. Sung, M. Neeley, et al · 2004
Cited alongside, same era.
Optimal inapproximability results for MAX-CUT and other 2-variable csps?
S. Khot, G. Kindler, E. Mossel, and R. O’Donnell · 2004
Cited alongside, same era.
Invariant gaussian processes and independent sets on regular graphs of large girth
E. Csóka, B. Gerencsér, V. Harangi, and B. Virág · 2015
Later among the works it cites.
Complexity-theoretic foundations of quantum supremacy experiments
S. Aaronson and L. Chen · 2016
Later among the works it cites.
Average-case complexity versus approximate simulation of commuting quantum computations
M. J. Bremner, A. Montanaro, and D. J. Shepherd · 2016
Later among the works it cites.
Extremal cuts of sparse random graphs
A. Dembo, A. Montanari, and S. Sen · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games
B. M. Terhal and D. P. DiVincenzo · 2004
Cited alongside, same era.
Spoofing linear cross-entropy benchmarking in shallow quantum circuits
B. Barak, C. Chou, and X. Gao · 2005
Cited alongside, same era.
The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples
E. Farhi, D. Gamarnik, and S. Gutmann · 2005
Cited alongside, same era.
Noise stability of functions with low influences: Invariance and optimality
E. Mossel, R. O’Donnell, and K. Oleszkiewicz · 2005
Cited alongside, same era.
Simulating quantum computation by contracting tensor networks
I. L. Markov and Y. Shi · 2008
Cited alongside, same era.
Lieb-robinson bounds for commutator-bounded operators
I. Prémont-Schwarz, A. Hamma, I. Klich, and F. Markopoulou-Kalamara · 2010
Cited alongside, same era.
The computational complexity of linear optics
S. Aaronson and A. Arkhipov · 2011
Cited alongside, same era.
R. Lyons · 2017
Later among the works it cites.
Architectures for quantum simulation showing a quantum speedup
J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert · 2018
Later among the works it cites.
Quantum advantage with shallow circuits
S. Bravyi, D. Gosset, and R. König · 2018
Later among the works it cites.
Quantum computing in the nisq era and beyond
J. Preskill · 2018
Later among the works it cites.
Quantum supremacy using a programmable superconducting processor
F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al · 2019
Later among the works it cites.
On the complexity and verification of quantum random circuit sampling
A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani · 2019
Later among the works it cites.
Suboptimality of local algorithms for a class of max-cut problems
W.-K. Chen, D. Gamarnik, D. Panchenko, and M. Rahman · 2019
Later among the works it cites.
Quantum supremacy through the quantum approximate optimization algorithm, 2019
E. Farhi and A. W. Harrow · 2019
Later among the works it cites.
Quantum optimization for maximum independent set using rydberg atom arrays
H. Pichler, S. T. Wang, L. Zhou, S. Choi, and M. Lukin · 2019
Later among the works it cites.
Noisy intermediate-scale quantum (nisq) algorithms, 2021
K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke, W.-K. Mok, S. Sim, L.-C. Kwek, and A. Aspuru-Guzik · 2021
Closest in time.
Noise and the frontier of quantum supremacy
A. Bouland, B. Fefferman, Z. Landau, and Y. Liu · 2021
Closest in time.
Local classical MAX-CUT algorithm outperforms p = 2 p=2 QAOA on high-girth regular graphs
K. Marwaha · 2021
Closest in time.
Optimization of the sherrington–kirkpatrick hamiltonian
A. Montanari · 2021
Closest in time.
Simulating the sycamore quantum supremacy circuits
F. Pan and P. Zhang · 2021
Closest in time.