Fetching the paper…
Reading the bibliography…
Quantum algorithms are believed to offer advantages in solving certain hard discrete optimization problems, yet identifying when such advantages persist in explicit distributions of problem instances remains a foundational challenge.
I. S. Reed and G. Solomon, Polynomial codes over certain finite fields, Journal of the society for industrial and applied mathematics 8
1960
Earlier work this paper cites.
R. Gallager, Low-density parity-check codes, IRE Trans. Inf. Theory 8
1962
Earlier work this paper cites.
V. V. Zyablov and M. S. Pinsker, Estimation of the error-correction complexity for Gallager low-density codes, Probl. Peredachi Inf. 11
1975
Earlier work this paper cites.
L. G. Khachiyan, A polynomial algorithm in linear programming, Proc. USSR Acad. Sci. 244
1979
Earlier work this paper cites.
C. H. Papadimitriou, On the complexity of integer programming, Journal of the ACM (JACM) 28
1981
Earlier work this paper cites.
A. Frieze, On the independence number of random graphs, Discrete Math. 81
1990
Earlier work this paper cites.
N. J. Calkin, Dependent sets of constant weight binary vectors, Comb. Probab. Comput. 6
1997
Earlier work this paper cites.
P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review 41
1999
Earlier work this paper cites.
T. J. Richardson and R. L. Urbanke, The capacity of low-density parity-check codes under message-passing decoding, IEEE Transactions on information theory 47
2001
Earlier work this paper cites.
D. Burshtein and G. Miller, Bounds on the performance of belief propagation decoding, IEEE Transactions on Information Theory 48
2002
Earlier work this paper cites.
J. Feldman, M. Wainwright, and D. R. Karger, Using linear programming to decode linear codes, in 37th annual Conference on Information Sciences and Systems (CISS’03) (2003)
2003
Earlier work this paper cites.
2004
Earlier work this paper cites.
R. Koetter, W. LI, P. Vontobel, and J. Walker, Characterizations of pseudo-codewords of ldpc codes, arxiv report, arXiv preprint cs.IT/0508049 (2005)
2005
Earlier work this paper cites.
J. Feldman, T. Malkin, R. A. Servedio, C. Stein, and M. J. Wainwright, Lp decoding corrects a constant fraction of errors, IEEE Transactions on Information Theory 53
2007
Earlier work this paper cites.
T. Richardson and R. Urbanke, Modern coding theory (Cambridge university press, 2008)
2008
Earlier work this paper cites.
A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Physical review letters 103
2009
Earlier work this paper cites.
2009
Earlier work this paper cites.
2014
Earlier work this paper cites.
B. Ghazi and E. Lee, Lp/sdp hierarchy lower bounds for decoding random ldpc codes, IEEE Transactions on Information Theory 64
2017
Cited alongside, same era.
M. Rahman and B. Virág, Local algorithms for independent sets are half-optimal, Ann. Probab. 45
2017
Cited alongside, same era.
D. Gamarnik and M. Sudan, Performance of sequential local algorithms for the random NAE-$K$-SAT problem, SIAM Journal on Computing 46
2017
Cited alongside, same era.
J. Sándor, Two applications of the Hadamard integral inequality, Notes Number Theory Discrete Math. 23
2017
Cited alongside, same era.
R. Vershynin, Concentration without independence, in High-Dimensional Probability: An Introduction with Applications in Data Science , Cambridge Series in Statistical and Probabilistic Mathematics (Cambridge University Press, 2018) pp. 98–126
2018
A. Bärtschi and S. Eidenbenz, Short-depth circuits for dicke state preparation, in 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE, 2022) pp. 87–96
2022
Later among the works it cites.
C. Jones, K. Marwaha, J. S. Sandhu, and J. Shi, Random Max-CSPs inherit algorithmic hardness from spin glasses, in 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , Leibniz International Proceedings in Informatics (LIPIcs), Vol. 251, edited by Y. Tauman Kalai (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2023) pp. 77:1–77:26
2023
Later among the works it cites.
D. Gamarnik and E. C. Kızıldağ, Algorithmic obstructions in the random number partitioning problem, Ann. Appl. Probab. 33
2023
Later among the works it cites.
A. Anshu and T. Metger, Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations, Quantum 7
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.
W.-K. Chen, D. Gamarnik, D. Panchenko, and M. Rahman, Suboptimality of local algorithms for a class of max-cut problems, Ann. Probab. 47
2019
Cited alongside, same era.
D. Gamarnik, The overlap gap property: A topological barrier to optimizing over random structures, Proc. Natl. Acad. Sci. U.S.A. 118
2021
Cited alongside, same era.
M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, et al. , Variational quantum algorithms, Nature Reviews Physics 3
2021
Cited alongside, same era.
G. De Palma, M. Marvian, D. Trevisan, and S. Lloyd, The quantum Wasserstein distance of order 1, IEEE Trans. Inf. Theory 67
2021
Cited alongside, same era.
A. El Alaoui, A. Montanari, and M. Sellke, Optimization of mean-field spin glasses, Ann. Probab. 49
2021
Cited alongside, same era.
J. Mosheiff, N. Resch, N. Ron-Zewi, S. Silas, and M. Wootters, Low-density parity-check codes achieve list-decoding capacity, SIAM Journal on Computing 53
2021
Cited alongside, same era.
N. Kirshner and A. Samorodnitsky, A moment ratio bound for polynomials and some extremal properties of Krawchouk polynomials and Hamming spheres, IEEE Trans. Inf. Theory 67
2021
Cited alongside, same era.
2023
Later among the works it cites.
A. Chailloux and J.-P. Tillich, The quantum decoding problem, arXiv preprint arXiv:2310.20651 (2023)
2023
Later among the works it cites.
2024
Later among the works it cites.
D. W. Berry, Y. Su, C. Gyurik, R. King, J. Basso, A. D. T. Barba, A. Rajput, N. Wiebe, V. Dunjko, and R. Babbush, Analyzing prospects for quantum advantage in topological data analysis, PRX Quantum 5
2024
Later among the works it cites.
2024
Later among the works it cites.
E. R. Anschuetz, D. Gamarnik, and B. Kiani, Combinatorial NLTS from the overlap gap property, Quantum 8
2024
Later among the works it cites.
D. Gamarnik, A. Jagannath, and E. C. Kızıldağ, Shattering in the Ising p p -spin glass model, Probab. Theory Relat. Fields 193
2025
Closest in time.
B. Huang and M. Sellke, Tight Lipschitz hardness for optimizing mean field spin glasses, Commun. Pure Appl. Math. 78
2025
Closest in time.
2025
Closest in time.
E. R. Anschuetz, A unified theory of quantum neural network loss landscapes, in International Conference on Learning Representations , edited by Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu (OpenReview, 2025)
2025
Closest in time.
2025
Closest in time.
2025
Closest in time.
2025
Closest in time.
E. R. Anschuetz, Quantum glassiness from efficient learning, Commun. Math. Phys. 407
2026
Closest in time.