Fetching the paper…
Reading the bibliography…
A canonical feature of the constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard for all known methods.
M. R. Garey, D. S. Johnson, and L. Stockmeyer, in Proceedings of the sixth annual ACM symposium on Theory of computing (1974), pp. 47–63
1974
Earlier work this paper cites.
J. D. Ullman, Journal of Computer and System sciences 10
1975
Earlier work this paper cites.
S. Sahni and T. Gonzalez, Journal of the ACM (JACM) 23
1976
Earlier work this paper cites.
G. Parisi, Physical Review Letters 43
1979
Earlier work this paper cites.
B. Derrida, Physical Review Letters 45
1980
Earlier work this paper cites.
G. S. Grest, C. Soukoulis, and K. Levin, Physical Review Letters 56
1986
Earlier work this paper cites.
A. Finnila, M. Gomez, C. Sebenik, C. Stenson, and J. Doll, Chemical physics letters 219
1994
Earlier work this paper cites.
P. Crescenzi, V. Kann, and M. Halldórsson, A compendium of np optimization problems (1995)
1995
Earlier work this paper cites.
D. S. Hochba, ACM Sigact News 28
1997
Earlier work this paper cites.
R. Monasson, Journal of Physics A: Mathematical and General 31
1998
Earlier work this paper cites.
T. Kadowaki and H. Nishimori, Physical Review E 58
1998
Earlier work this paper cites.
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, arXiv:quant-ph/0001106 (2000)
2000
Earlier work this paper cites.
J. Håstad, Journal of the ACM (JACM) 48
2001
Earlier work this paper cites.
M. Mézard, G. Parisi, and R. Zecchina, Science 297
2002
Earlier work this paper cites.
J. Roland and N. J. Cerf, Phys. Rev. A 65
2002
Earlier work this paper cites.
O. Dubois and J. Mandler, Comptes Rendus Mathematique 335
2002
Earlier work this paper cites.
J. Håstad and S. Venkatesh, in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (2002), pp. 43–52
2002
Earlier work this paper cites.
G. J. Woeginger, in Combinatorial optimization: eureka, you shrink! (Springer, 2003), pp. 185–207
2003
Earlier work this paper cites.
M. Alekhnovich, in 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. (IEEE, 2003), pp. 298–307
2003
Earlier work this paper cites.
D. J. Earl and M. W. Deem, Physical Chemistry Chemical Physics 7
2005
Earlier work this paper cites.
M. Mézard, T. Mora, and R. Zecchina, Physical Review Letters 94
2005
Earlier work this paper cites.
A. K. Hartmann and M. Weigt, Phase transitions in combinatorial optimization problems: basics, algorithms and statistical mechanics (John Wiley & Sons, 2006)
2006
Earlier work this paper cites.
S. Bravyi, D. P. Divincenzo, R. I. Oliveira, and B. M. Terhal, arXiv preprint quant-ph/0606140 (2006)
2006
Earlier work this paper cites.
F. Krzakala and J. Kurchan, Physical Review E 76
2007
Earlier work this paper cites.
S. Khot and A. Naor, in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07) (IEEE, 2007), pp. 318–328
2007
Earlier work this paper cites.
A. Das and B. K. Chakrabarti, Reviews of Modern Physics 80
2008
Earlier work this paper cites.
F. Altarelli, R. Monasson, and F. Zamponi, in Journal of Physics: Conference Series (IOP Publishing, 2008), vol. 95, p. 012013
2008
Earlier work this paper cites.
S. Arora and B. Barak, Computational complexity: a modern approach (Cambridge University Press, 2009)
2009
Earlier work this paper cites.
B. Altshuler, H. Krovi, and J. Roland, Proceedings of the National Academy of Sciences 107
2010
Earlier work this paper cites.
E. Farhi, J. Goldstone, D. Gosset, S. Gutmann, and P. Shor, arXiv preprint arXiv:1010.0009 (2010)
2010
Earlier work this paper cites.
A. Pal and D. A. Huse, Physical review b 82
2010
Earlier work this paper cites.
T. Jörg, F. Krzakala, J. Kurchan, A. C. Maggs, and J. Pujos, EPL (Europhysics Letters) 89
2010
Earlier work this paper cites.
B. H. Korte, J. Vygen, B. Korte, and J. Vygen, Combinatorial optimization , vol. 1 (Springer, 2011)
2011
Earlier work this paper cites.
M. W. Johnson, M. H. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, et al., Nature 473
2011
Earlier work this paper cites.
S. Bravyi, D. P. DiVincenzo, and D. Loss, Annals of physics 326
2011
Earlier work this paper cites.
M. Ibrahimi, Y. Kanoria, M. Kraning, and A. Montanari, in Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms (SIAM, 2012), pp. 760–779
2012
Cited alongside, same era.
V. Bapst, L. Foini, F. Krzakala, G. Semerjian, and F. Zamponi, Physics Reports 523
2013
Cited alongside, same era.
C. J. Hillar and L.-H. Lim, Journal of the ACM (JACM) 60
2013
Cited alongside, same era.
S. Boixo, T. F. Rønnow, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M. Martinis, and M. Troyer, Nature Physics 10
2014
Cited alongside, same era.
E. Farhi, J. Goldstone, and S. Gutmann, arXiv preprint arXiv:1411.4028 (2014)
2014
Cited alongside, same era.
W. Xu, F. Gong, and G. Zhou, Physica A: Statistical Mechanics and its Applications 537
2020
Later among the works it cites.
M. Bellitti, F. Ricci-Tersenghi, and A. Scardicchio, Entropic barriers as a reason for hardness in both classical and quantum algorithms (2021), eprint 2102.00182
2021
Later among the works it cites.
R. Babbush, J. R. McClean, M. Newman, C. Gidney, S. Boixo, and H. Neven, PRX Quantum 2
2021
Later among the works it cites.
A. Montanari, SIAM Journal on Computing pp. FOCS19–1 (2021)
2021
Later among the works it cites.
S. Boulebnane and A. Montanaro, arXiv preprint arXiv:2110.10685 (2021)
2021
Later among the works it cites.
J. Basso, E. Farhi, K. Marwaha, B. Villalonga, and L. Zhou, arXiv preprint arXiv:2110.14206 (2021)
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
D. Venturelli, S. Mandrà, S. Knysh, B. Gorman, R. Biswas, and V. Smelyanskiy, Physical Review X 5
2015
Cited alongside, same era.
S. R. Allen, R. O’Donnell, and D. Witmer, in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (IEEE, 2015), pp. 689–708
2015
Cited alongside, same era.
2015
Cited alongside, same era.
B. Heim, T. F. Rønnow, S. V. Isakov, and M. Troyer, Science 348
2015
Cited alongside, same era.
S. Knysh, Nature communications 7
2016
Cited alongside, same era.
J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik, New Journal of Physics 18
2016
Cited alongside, same era.
F. Pietracaprina, V. Ros, and A. Scardicchio, Physical Review B 93
2016
Cited alongside, same era.
2021
Later among the works it cites.
Z. Tang and E. Kapit, Physical Review A 103
2021
Later among the works it cites.
E. Kapit and V. Oganesyan, Quantum Science and Technology 6
2021
Later among the works it cites.
M. Kowalsky, T. Albash, I. Hen, and D. A. Lidar, arXiv preprint arXiv:2103.08464 (2021)
2021
Later among the works it cites.
A. Anshu, D. Gosset, K. J. M. Korol, and M. Soleimanifar, Physical Review Letters 127
2021
Later among the works it cites.
F. Zhang, N. Gomes, Y. Yao, P. P. Orth, and T. Iadecola, Physical Review B 104
2021
Later among the works it cites.
Y. Suzuki, Y. Kawase, Y. Masumura, Y. Hiraga, M. Nakadai, J. Chen, K. M. Nakanishi, K. Mitarai, R. Imai, S. Tamiya, et al., Quantum 5
2021
Later among the works it cites.
M. B. Hastings, Quantum 5
2021
Later among the works it cites.
A. Gilyén, M. B. Hastings, and U. Vazirani, in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021), pp. 1357–1369
2021
Later among the works it cites.
C. Jones, K. Marwaha, J. S. Sandhu, and J. Shi, arXiv preprint arXiv:2210.03006 (2022)
2022
Later among the works it cites.
S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, et al., Science 376
2022
Later among the works it cites.
E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou, Quantum 6
2022
Later among the works it cites.
J. Basso, D. Gamarnik, S. Mei, and L. Zhou, in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2022), pp. 335–343
2022
Later among the works it cites.
S. Boulebnane and A. Montanaro, arXiv preprint arXiv:2208.06909 (2022)
2022
Later among the works it cites.
T. d’Orsi and L. Trevisan, arXiv preprint arXiv:2204.10881 (2022)
2022
Later among the works it cites.
L. Zhu, H. L. Tang, G. S. Barron, F. Calderon-Vargas, N. J. Mayhall, E. Barnes, and S. E. Economou, Physical Review Research 4
2022
Later among the works it cites.
K. Marwaha and S. Hadfield, Quantum 6
2022
Later among the works it cites.
J. Tilly, H. Chen, S. Cao, D. Picozzi, K. Setia, Y. Li, E. Grant, L. Wossnig, I. Rungger, G. H. Booth, et al., Physics Reports 986
2022
Later among the works it cites.
A. D. King, J. Raymond, T. Lanting, R. Harris, A. Zucca, F. Altomare, A. J. Berkley, K. Boothby, S. Ejtemaee, C. Enderud, et al., Nature pp. 1–6 (2023)
2023
Closest in time.
G. Grattan, B. A. Barton, S. Feeney, G. Mossi, P. Patnaik, J. C. Sagal, L. D. Carr, V. Oganesyan, and E. Kapit, Exponential acceleration of macroscopic quantum tunneling in a floquet ising model (2023), eprint 2311.17814
2023
Closest in time.
2023
Closest in time.
I. Čepaitė, A. Polkovnikov, A. J. Daley, and C. W. Duncan, PRX Quantum 4
2023
Closest in time.
A. Anshu and T. Metger, Quantum 7
2023
Closest in time.
2023
Closest in time.
A. M. Dalzell, N. Pancotti, E. T. Campbell, and F. G. Brandão, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (2023), pp. 1131–1144
2023
Closest in time.
L. C. Tazi and A. J. Thom, arXiv preprint arXiv:2305.04783 (2023)
2023
Closest in time.
G. Mossi, V. Oganesyan, and E. Kapit, arXiv preprint arXiv:2306.10632 (2023)
2023
Closest in time.
H. M. Bauza and D. A. Lidar, Scaling advantage in approximate optimization with quantum annealing (2024), eprint 2401.07184
2024
Closest in time.
E. Granet and H. Dreyer, arXiv preprint arXiv:2404.16001 (2024)
2024
Closest in time.