$\textstyle{1}$$\textstyle{2}$$\textstyle{3}$$\textstyle{4}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}}$

  1. 1

(1 0 0 0)

  2. 2

(0 1 0 0)

  3. 3

(0 0 1 0)

  4. 4

(0 0 0 1)

  5. 5

(1 1 0 0)

  6. 6

(0 1 1 0)

  7. 7

(0 0 1 1)

  8. 8

(1 1 1 0)

  9. 9

(0 1 2 0)

  10. 10

(0 1 1 1)

  11. 11

(1 1 2 0)

  12. 12

(1 1 1 1)

  13. 13

(0 1 2 1)

  14. 14

(1 2 2 0)

  15. 15

(1 1 2 1)

  16. 16

(0 1 2 2)

  17. 17

(1 2 2 1)

  18. 18

(1 1 2 2)

  19. 19

(1 2 3 1)

  20. 20

(1 2 2 2)

  21. 21

(1 2 3 2)

  22. 22

(1 2 4 2)

  23. 23

(1 3 4 2)

  24. 24

(2 3 4 2)

$\bf E_{6}.$

$\textstyle{1}$$\textstyle{3}$$\textstyle{4}$$\textstyle{5}$$\textstyle{6}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}}$$\textstyle{\bullet}$$\textstyle{2}$

  1. 1

(1 0 0 0 0 0)

  2. 2

(0 1 0 0 0 0)

  3. 3

(0 0 1 0 0 0)

  4. 4

(0 0 0 1 0 0)

  5. 5

(0 0 0 0 1 0)

  6. 6

(0 0 0 0 0 1)

  7. 7

(1 0 1 0 0 0)

  8. 8

(0 1 0 1 0 0)

  9. 9

(0 0 1 1 0 0)

  10. 10

(0 0 0 1 1 0)

  11. 11

(0 0 0 0 1 1)

  12. 12

(1 0 1 1 0 0)

  13. 13

(0 1 1 1 0 0)

  14. 14

(0 1 0 1 1 0)

  15. 15

(0 0 1 1 1 0)

  16. 16

(0 0 0 1 1 1)

  17. 17

(1 1 1 1 0 0)

  18. 18

(1 0 1 1 1 0)

  19. 19

(0 1 1 1 1 0)

  20. 20

(0 1 0 1 1 1)

  21. 21

(0 0 1 1 1 1)

  22. 22

(1 1 1 1 1 0)

  23. 23

(1 0 1 1 1 1)

  24. 24

(0 1 1 2 1 0)

  25. 25

(0 1 1 1 1 1)

  26. 26

(1 1 1 2 1 0)

  27. 27

(1 1 1 1 1 1)

  28. 28

(0 1 1 2 1 1)

  29. 29

(1 1 2 2 1 0)

  30. 30

(1 1 1 2 1 1)

  31. 31

(0 1 1 2 2 1)

  32. 32

(1 1 2 2 1 1)

  33. 33

(1 1 1 2 2 1)

  34. 34

(1 1 2 2 2 1)

  35. 35

(1 1 2 3 2 1)

  36. 36

(1 2 2 3 2 1)

$\bf E_{7}.$

$\textstyle{1}$$\textstyle{3}$$\textstyle{4}$$\textstyle{5}$$\textstyle{6}$$\textstyle{7}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}}$$\textstyle{\bullet}$$\textstyle{2}$

  1. 1

(1 0 0 0 0 0 0)

  2. 2

(0 1 0 0 0 0 0)

  3. 3

(0 0 1 0 0 0 0)

  4. 4

(0 0 0 1 0 0 0)

  5. 5

(0 0 0 0 1 0 0)

  6. 6

(0 0 0 0 0 1 0)

  7. 7

(0 0 0 0 0 0 1)

  8. 8

(1 0 1 0 0 0 0)

  9. 9

(0 1 0 1 0 0 0)

  10. 10

(0 0 1 1 0 0 0)

  11. 11

(0 0 0 1 1 0 0)

  12. 12

(0 0 0 0 1 1 0)

  13. 13

(0 0 0 0 0 1 1)

  14. 14

(1 0 1 1 0 0 0)

  15. 15

(0 1 1 1 0 0 0)

  16. 16

(0 1 0 1 1 0 0)

  17. 17

(0 0 1 1 1 0 0)

  18. 18

(0 0 0 1 1 1 0)

  19. 19

(0 0 0 0 1 1 1)

  20. 20

(1 1 1 1 0 0 0)

  21. 21

(1 0 1 1 1 0 0)

  22. 22

(0 1 1 1 1 0 0)

  23. 23

(0 1 0 1 1 1 0)

  24. 24

(0 0 1 1 1 1 0)

  25. 25

(0 0 0 1 1 1 1)

  26. 26

(1 1 1 1 1 0 0)

  27. 27

(1 0 1 1 1 1 0)

  28. 28

(0 1 1 2 1 0 0)

  29. 29

(0 1 1 1 1 1 0)

  30. 30

(0 1 0 1 1 1 1)

  31. 31

(0 0 1 1 1 1 1)

  32. 32

(1 1 1 2 1 0 0)

  33. 33

(1 1 1 1 1 1 0)

  34. 34

(1 0 1 1 1 1 1)

  35. 35

(0 1 1 2 1 1 0)

  36. 36

(0 1 1 1 1 1 1)

  37. 37

(1 1 2 2 1 0 0)

  38. 38

(1 1 1 2 1 1 0)

  39. 39

(1 1 1 1 1 1 1)

  40. 40

(0 1 1 2 2 1 0)

  41. 41

(0 1 1 2 1 1 1)

  42. 42

(1 1 2 2 1 1 0)

  43. 43

(1 1 1 2 2 1 0)

  44. 44

(1 1 1 2 1 1 1)

  45. 45

(0 1 1 2 2 1 1)

  46. 46

(1 1 2 2 2 1 0)

  47. 47

(1 1 2 2 1 1 1)

  48. 48

(1 1 1 2 2 1 1)

  49. 49

(0 1 1 2 2 2 1)

  50. 50

(1 1 2 3 2 1 0)

  51. 51

(1 1 2 2 2 1 1)

  52. 52

(1 1 1 2 2 2 1)

  53. 53

(1 2 2 3 2 1 0)

  54. 54

(1 1 2 3 2 1 1)

  55. 55

(1 1 2 2 2 2 1)

  56. 56

(1 2 2 3 2 1 1)

  57. 57

(1 1 2 3 2 2 1)

  58. 58

(1 2 2 3 2 2 1)

  59. 59

(1 1 2 3 3 2 1)

  60. 60

(1 2 2 3 3 2 1)

  61. 61

(1 2 2 4 3 2 1)

  62. 62

(1 2 3 4 3 2 1)

  63. 63

(2 2 3 4 3 2 1)

$\bf E_{8}.$

$\textstyle{1}$$\textstyle{3}$$\textstyle{4}$$\textstyle{5}$$\textstyle{6}$$\textstyle{7}$$\textstyle{8}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\bullet}}$$\textstyle{\bullet}$$\textstyle{2}$

  1. 1

(1 0 0 0 0 0 0 0)

  2. 2

(0 1 0 0 0 0 0 0)

  3. 3

(0 0 1 0 0 0 0 0)

  4. 4

(0 0 0 1 0 0 0 0)

  5. 5

(0 0 0 0 1 0 0 0)

  6. 6

(0 0 0 0 0 1 0 0)

  7. 7

(0 0 0 0 0 0 1 0)

  8. 8

(0 0 0 0 0 0 0 1)

  9. 9

(1 0 1 0 0 0 0 0)

  10. 10

(0 1 0 1 0 0 0 0)

  11. 11

(0 0 1 1 0 0 0 0)

  12. 12

(0 0 0 1 1 0 0 0)

  13. 13

(0 0 0 0 1 1 0 0)

  14. 14

(0 0 0 0 0 1 1 0)

  15. 15

(0 0 0 0 0 0 1 1)

  16. 16

(1 0 1 1 0 0 0 0)

  17. 17

(0 1 1 1 0 0 0 0)

  18. 18

(0 1 0 1 1 0 0 0)

  19. 19

(0 0 1 1 1 0 0 0)

  20. 20

(0 0 0 1 1 1 0 0)

  21. 21

(0 0 0 0 1 1 1 0)

  22. 22

(0 0 0 0 0 1 1 1)

  23. 23

(1 1 1 1 0 0 0 0)

  24. 24

(1 0 1 1 1 0 0 0)

  25. 25

(0 1 1 1 1 0 0 0)

  26. 26

(0 1 0 1 1 1 0 0)

  27. 27

(0 0 1 1 1 1 0 0)

  28. 28

(0 0 0 1 1 1 1 0)

  29. 29

(0 0 0 0 1 1 1 1)

  30. 30

(1 1 1 1 1 0 0 0)

  31. 31

(1 0 1 1 1 1 0 0)

  32. 32

(0 1 1 2 1 0 0 0)

  33. 33

(0 1 1 1 1 1 0 0)

  34. 34

(0 1 0 1 1 1 1 0)

  35. 35

(0 0 1 1 1 1 1 0)

  36. 36

(0 0 0 1 1 1 1 1)

  37. 37

(1 1 1 2 1 0 0 0)

  38. 38

(1 1 1 1 1 1 0 0)

  39. 39

(1 0 1 1 1 1 1 0)

  40. 40

(0 1 1 2 1 1 0 0)

  41. 41

(0 1 1 1 1 1 1 0)

  42. 42

(0 1 0 1 1 1 1 1)

  43. 43

(0 0 1 1 1 1 1 1)

  44. 44

(1 1 2 2 1 0 0 0)

  45. 45

(1 1 1 2 1 1 0 0)

  46. 46

(1 1 1 1 1 1 1 0)

  47. 47

(1 0 1 1 1 1 1 1)

  48. 48

(0 1 1 2 2 1 0 0)

  49. 49

(0 1 1 2 1 1 1 0)

  50. 50

(0 1 1 1 1 1 1 1)

  51. 51

(1 1 2 2 1 1 0 0)

  52. 52

(1 1 1 2 2 1 0 0)

  53. 53

(1 1 1 2 1 1 1 0)

  54. 54

(1 1 1 1 1 1 1 1)

  55. 55

(0 1 1 2 2 1 1 0)

  56. 56

(0 1 1 2 1 1 1 1)

  57. 57

(1 1 2 2 2 1 0 0)

  58. 58

(1 1 2 2 1 1 1 0)

  59. 59

(1 1 1 2 2 1 1 0)

  60. 60

(1 1 1 2 1 1 1 1)

  61. 61

(0 1 1 2 2 2 1 0)

  62. 62

(0 1 1 2 2 1 1 1)

  63. 63

(1 1 2 3 2 1 0 0)

  64. 64

(1 1 2 2 2 1 1 0)

  65. 65

(1 1 2 2 1 1 1 1)

  66. 66

(1 1 1 2 2 2 1 0)

  67. 67

(1 1 1 2 2 1 1 1)

  68. 68

(0 1 1 2 2 2 1 1)

  69. 69

(1 2 2 3 2 1 0 0)

  70. 70

(1 1 2 3 2 1 1 0)

  71. 71

(1 1 2 2 2 2 1 0)

  72. 72

(1 1 2 2 2 1 1 1)

  73. 73

(1 1 1 2 2 2 1 1)

  74. 74

(0 1 1 2 2 2 2 1)

  75. 75

(1 2 2 3 2 1 1 0)

  76. 76

(1 1 2 3 2 2 1 0)

  77. 77

(1 1 2 3 2 1 1 1)

  78. 78

(1 1 2 2 2 2 1 1)

  79. 79

(1 1 1 2 2 2 2 1)

  80. 80

(1 2 2 3 2 2 1 0)

  81. 81

(1 2 2 3 2 1 1 1)

  82. 82

(1 1 2 3 3 2 1 0)

  83. 83

(1 1 2 3 2 2 1 1)

  84. 84

(1 1 2 2 2 2 2 1)

  85. 85

(1 2 2 3 3 2 1 0)

  86. 86

(1 2 2 3 2 2 1 1)

  87. 87

(1 1 2 3 3 2 1 1)

  88. 88

(1 1 2 3 2 2 2 1)

  89. 89

(1 2 2 4 3 2 1 0)

  90. 90

(1 2 2 3 3 2 1 1)

  91. 91

(1 2 2 3 2 2 2 1)

  92. 92

(1 1 2 3 3 2 2 1)

  93. 93

(1 2 3 4 3 2 1 0)

  94. 94

(1 2 2 4 3 2 1 1)

  95. 95

(1 2 2 3 3 2 2 1)

  96. 96

(1 1 2 3 3 3 2 1)

  97. 97

(2 2 3 4 3 2 1 0)

  98. 98

(1 2 3 4 3 2 1 1)

  99. 99

(1 2 2 4 3 2 2 1)

  100. 100

(1 2 2 3 3 3 2 1)

  101. 101

(2 2 3 4 3 2 1 1)

  102. 102

(1 2 3 4 3 2 2 1)

  103. 103

(1 2 2 4 3 3 2 1)

  104. 104

(2 2 3 4 3 2 2 1)

  105. 105

(1 2 3 4 3 3 2 1)

  106. 106

(1 2 2 4 4 3 2 1)

  107. 107

(2 2 3 4 3 3 2 1)

  108. 108

(1 2 3 4 4 3 2 1)

  109. 109

(2 2 3 4 4 3 2 1)

  110. 110

(1 2 3 5 4 3 2 1)

  111. 111

(2 2 3 5 4 3 2 1)

  112. 112

(1 3 3 5 4 3 2 1)

  113. 113

(2 3 3 5 4 3 2 1)

  114. 114

(2 2 4 5 4 3 2 1)

  115. 115

(2 3 4 5 4 3 2 1)

  116. 116

(2 3 4 6 4 3 2 1)

  117. 117

(2 3 4 6 5 3 2 1)

  118. 118

(2 3 4 6 5 4 2 1)

  119. 119

(2 3 4 6 5 4 3 1)

  120. 120

(2 3 4 6 5 4 3 2)

## Bibliography

  * [1]
  * [2] Andersen, H. H., Polo, P., Kexin, W., Representations of quantum algebras, Invent. Math. 104 (1991), 1–60.
  * [3] Asherova, R. M., Smirnov, Yu. F., Tolstoy, V. N., Projection operators for the simple Lie groups, Theor. Math. Phys. 8(1971), 813–825.
  * [4] Asherova, R. M., Smirnov, Yu. F., Tolstoy, V. N., Projection operators for the simple Lie groups. II. General scheme for construction of lowering operators. The case of the group SU(n), Theor. Math. Phys. 15 (1973), 392–393.
  * [5] Asherova, R. M., Smirnov, Yu. F., Tolstoy, V. N., A description of some class of projection operators for semisimple complex Lie algebras, Matem. Zametki 26 (1979), 499–504.
  * [6] Baader, F., Nipkow, T., Term Rewriting and All That, Cambridge University Press, Cambridge (1999).
  * [7] Bezrukavnikov, R., Mirkovic, I., Rumynin, D., Localization of modules for a semisimple Lie algebra in prime characteristic. With an appendix by Bezrukavnikov and Simon Riche, Ann. of Math. 167 (2008), 945–991.
  * [8] Belavin, A. A., Drinfeld, V. G., Solutions of the classical Yang-Baxter equation for simple Lie algebras, Funct. Anal. Appl. 16 (1981), 159–180.
  * [9] Bernstein, J. H., Gelfand, I. M., Gelfand, S. I., Schubert cells and cohomology of the spaces G/P, Uspekhi Mat. Nauk 28, no. 3 (171) (1973), 3–26; Russian Math. Surveys 28, no. 3 (1973), 1–26.
  * [10] Bourbaki, N., Groupes et algebras de Lie, Chap. 4,5,6, Paris, Hermann (1968).
  * [11] Brieskorn, E., Singular elements of semisimple algebraic groups, Actes Congrès Intern. Math. 2 (1970), 279–284.
  * [12] Brown, K. A., Goodearl, K. R., Lectures on Algebraic Quantum Groups, Birkhäuser (2002).
  * [13] Cantarini, N., Carnovale, G., Costantini, M., Spherical orbits and representations of ${U}_{\varepsilon}({\mathfrak{g}})$, Transf. Groups 10 (2005), 29–-62.
  * [14] Cantarini, N., The quantized enveloping algebra $U_{q}(sl(n))$ at the roots of unity, Comm. Math. Phys. 211 (2000), 207–-230.
  * [15] Cantarini, N., Spherical orbits and quantized enveloping algebras, Comm. Algebra 27 (1999), 3439–3458.
  * [16] Cantarini, N., Mod-p reduction for quantum groups, J. of Alg. 202 (1998), 357–-366.
  * [17] Carter, R. W., Simple groups of Lie type, John Wiley & Sons, Inc., New York (1989).
  * [18] Carter, R. W., Conjugacy classes in the Weyl group, Compositio Math. 25 (1972), 1–59.
  * [19] Carter, R. W., Finite groups of Lie type. Conjugacy classes and complex characters, John Wiley & Sons, Ltd., Chichester (1993).
  * [20] Chari, V., Pressley, A., A guide to quantum groups, Cambridge Univ. Press (1994).
  * [21] Coxeter, H. S. M., Regular Polytopes, Methuen & Co., London (1948).
  * [22] De Boer, J., Tjin, T., Quantization and representation theory of finite W–algebras, Comm. math. Phys., 158 (1993), 485–516.
  * [23] De Concini, C., Kac, V. G., Representations of quantum groups at roots of $1$. Operator algebras, unitary representations, enveloping algebras, and invariant theory (Paris, 1989), Progr. Math. 92, Birkhäuser Boston, Boston, MA (1990), 471–506.
  * [24] De Concini, C., Kac, V. G., Representations of quantum groups at roots of 1: reduction to the exceptional case, Int. J. Mod. Phys. A 7 Suppl. 1A (1992), 141–149.
  * [25] De Concini, C., Kac, V. G., Procesi, C., Quantum coadjoint action, J. Amer. Math. Soc. 5 (1992), 151–189.
  * [26] De Concini, C., Kac, V. G., Procesi, C., Some remarkable degenerations of quantum groups, Comm. Math. Phys. 157 (1993), 405–427.
  * [27] De Concini, C., Lyubashenko, V., Quantum function algebra at roots of 1, Adv. in Math. 108 (1994), 205–262.
  * [28] De Concini, C., Procesi, C., Quantum Schubert cells and representations at roots of 1. In: Algebraic groups and Lie groups (G. I. Lehrer ed.), Austral. Math. Soc. Lect. Ser. 9, Cambridge Univ. Press, Cambridge (1997), 127–160.
  * [29] De Concini, C., Procesi, C., Quantum Groups. In: D-modules, Representation Theory, and Quantum Groups (L. Boutet de Monvel et al.), Proc. Venezia 1992, Lecture Notes in Mathematics 1565, Springer, Berlin (1993), 31–140.
  * [30] Curtis, C. W., Reiner, I., Representation theory of finite groups and associative algebras, Interscience Publishers (1962).
  * [31] Drinfeld, V.G., Quantum groups, Proc. Int. Congr. Math. Berkley, California, 1986, Amer. Math. Soc., Providence (1987), 718–820.
  * [32] Drupieski, C. M., On injective modules and support varieties for the small quantum group, Int. Math. Res. Not. 2011 (2011), 2263–2294.
  * [33] Ellers, E. W., Gordeev, N., Intersection of conjugacy classes with Bruhat cells in Chevalley groups, Pacific J. Math. 214 (2004), 245–260.
  * [34] Fomin, S., Zelevinsky, A., Double Bruhat cells and total positivity, J. Amer. Math. Soc. 12 (1999), 335–380.
  * [35] Fomin, S., Zelevinsky, A., Recognizing Schubert cells, Journal of Algebraic Combinatorics 12 (2000), 37–57.
  * [36] Friedlander, E. M., Parshall, B. J., Support varieties for restricted Lie algebras Invent. Math. 86 (1986), 553–562.
  * [37] Friedlander, E. M., Parshall, B. J., Geometry of $p$-unipotent Lie algebras, J. of Alg. 109 (1987), 25–45.
  * [38] Friedlander, E. M., Parshall, B. J., Modular representation theory of Lie algebras, Amer. J. Math. 110 (1988), 1055–1093.
  * [39] Gan, W. L., Ginzburg, V., Quantization of Slodowy slices, Int. Math. Res. Not. 5 (2002), 243–255.
  * [40] Gasper, G., Rahman, M., Basic hypergeometric series, Cambridge Univ. Press (1990).
  * [41] Geck, M., Pfeiffer, G., Characters of finite Coxeter groups and Iwahori-Hecke algebras, London Mathematical Society Monographs. New Series 21, The Clarendon Press, Oxford University Press, New York (2000).
  * [42] Geck, M., Malle, G., On the existence of a unipotent support for the irreducible characters of a finite group of Lie type, Trans. Amer. Math. Soc. 352 (2000), 429–-456.
  * [43] Gelfand, I. M., Serganova, V. V., Combinatorial geometries and the strata of a torus on homogeneous compact manifolds, Russian Math. Surveys 42 (1987), 133–168.
  * [44] Ginzburg, V., Kumar, S., Cohomology of quantum groups at roots of unity, Duke Math. J.  69 (1993), 179–198.
  * [45] Goodearl, K. R., Yakimov, M. T., The Berenstein-Zelevinsky quantum cluster algebra conjecture, J. Eur. Math. Soc., doi: 10.4171/JEMS/969.
  * [46] Goto, M., and Grosshans, F.D., Semisimple Lie algebras, Marcel Dekker, Inc., New York and Basel (1978)
  * [47] Hartshorne, R., Algebraic geometry, Springer, New York (2006).
  * [48] Harzheim, E., Ordered Sets, Springer, New York (2006).
  * [49] He, X., Lusztig, G., A generalization of Steinberg’s cross-section, J. Amer. Math. Soc. 25 (2012), 739–757.
  * [50] He, X., Nie, S., Minimal length elements of finite Coxeter groups, Duke Math. J. 161 (2012), 2945–2967.
  * [51] Hesselink, W. H., Nilpotency in classical groups over a field of characteristic 2, Math. Z. 166 (1979), 165–-181.
  * [52] Iwahori, N., On the structure of a Hecke ring of a Chevalley group over a finite field, J. Fac, Sci. Uni. Tokyo, Sect. IA 10 (1964), 215–236.
  * [53] Jacobson, N., Lie algebras, Interscience Publishers, New York (1962).
  * [54] Jantzen, J. C., Lectures on Quantum Groups, Graduate Studies in Mathematics 6, AMS (1996).
  * [55] Joseph, A., Quantum groups and their primitive ideals. Ergebnisse der Mathematik und ihrer Grenzgebiete (3), 29, Springer-Verlag, Berlin (1995).
  * [56] Joseph, A., Letzter, G., Local finiteness of the adjoint action for quantized enveloping algebras, J. of Alg. 153 (1992), 289–318.
  * [57] Kac, V. G., Weisfeiler, B., The irreducible representations of Lie $p$-algebras, Funk. Anal. i ego Pril. 5 (1971), no. 2, 28–-36.
  * [58] Kac, V., Cheung, P., Quantum Calculus, Springer, New York (2002).
  * [59] Kawanaka, N., Generalized Gelfand–Graev representations and Ennola duality, in: Algebraic Groups and Related Topics, Advanced Studies in Pure Mathematics 6, North-Holland, Amsterdam/New York/Oxford (1985), 175–206.
  * [60] Kawanaka, N., Generalized Gelfand–Graev representations of exceptional simple groups over a finite field I, Invent. Math. 84 (1986), 575–616.
  * [61] Kazhdan, D., Lusztig, G., Fixed point varieties on affine flag manifolds, Israel J. Math. 62 (1988), 129–168.
  * [62] Khoroshkin, S. M., Ogievetsky O., Mickelsson algebras and Zhelobenko operators, J. of Alg. 319 (2008), 2113–2165.
  * [63] Khoroshkin, S. M., Tolstoy, V. N., The Cartan-Weyl basis and the universal R-matrix for quantum Kac-Moody algebras and superalgebras. Quantum symmetries (Clausthal, 1991), 336–351, World Sci. Publ., River Edge, NJ (1993).
  * [64] Khoroshkin, S.M., Tolstoy, V.N., Universal R–matrix for quantized (super)algebras, Comm. Math. Phys. 141 (1991), 599–617.
  * [65] Kostant, B., On Whittaker vectors and representation theory, Invent. Math. 48 (1978), 101–184.
  * [66] Kremnizer, K., Proof of the De Concini-Kac-Procesi conjecture, arXiv:math/0611236.
  * [67] Kumar, S., Representations of quantum groups at roots of unity, In: Quantum topology (ed. by D.N. Yetter), World Scientific, Singapore (1994) 187–224.
  * [68] Liebeck, M. W., Seitz, G. M., Unipotent and nilpotent classes in simple algebraic groups and Lie algebras, Mathematical Surveys and Monographs 180, American Mathematical Society, Providence, RI (2012).
  * [69] Losev, I., Finite dimensional representations of W-algebras, Duke Math. J. 159 (2011), 99–143.
  * [70] Losev, I., Ostrik, V., Classification of finite dimensional irreducible modules over W-algebras, Compositio Math. 150 (2014), 1024–1076.
  * [71] Löwdin, P.-O., Angular momentum wave functions constructed by projector operators Rev. Mod. Phys. 36 (1964), 966–976.
  * [72] Lu J.H., Momentum mapping and reduction of Poisson actions. In: Symplectic geometry, groupoids and integrable systems, Berkeley, 1989\. P.Dazord and A.Weinstein (eds), pp.209-226. Springer-Verlag.
  * [73] Lusztig, G., Introduction to quantum groups, Birkhäuser (1994).
  * [74] Lusztig, G., Quantum groups at roots of 1, Geom. Dedicata 35 (1990), no. 1–3, 89–113.
  * [75] Lusztig, G., On conjugacy classes in a reductive group. In: Representations of Reductive Groups (M. Nevins, P. E. Trapa eds.), Progress in Mathematics 312, Birkhäuser (2015), 333–363.
  * [76] Lusztig, G., Spaltenstein, N., On the generalized Springer correspondence for classical groups. Algebraic groups and related topics (Kyoto/Nagoya, 1983), 289–316, Adv. Stud. Pure Math. 6, North-Holland, Amsterdam, (1985).
  * [77] Lusztig, G., From conjugacy classes in the Weyl group to unipotent classes II. Represent. Theory 16 (2012), 189–211.
  * [78] Lusztig, G., From conjugacy classes in the Weyl group to unipotent classes, Represent. Theory 15 (2011), 494–-530.
  * [79] Lusztig, G., Unipotent elements in small characteristic, Transform. Groups 10 (2005), 449–487.
  * [80] Lusztig, G., Quantum Deformations of Certain Simple Modules over Enveloping Algebras, Adv. Math. 70 (1988), 237–249.
  * [81] Lynch, T. E., Generalized Whittaker vectors and representation theory, Thesis, M.I.T. (1979).
  * [82] McConnell, J.C., Quantum groups, filtered rings and Gelfand–KIrillov dimension, In Lecture Notes in Math 1448, Springer, Berlin (1991), 139–149.
  * [83] Ostrik, V. V., Cohomological supports for quantum groups, Funct. Anal. Appl. 32 (1999), 237–246.
  * [84] Passman, D. S., The algebraic structure of group rings, Jonh Wiley & Sons, New York (1977).
  * [85] Pierce, R.S., Associative algebras. Graduate Texts in Mathematics 88, Springer-Verlag, New York-Berlin (1982).
  * [86] Premet, A., Skryabin, S., Representations of restricted Lie algebras and families of associative $\mathcal{L}$–algebras, J. Reine Angew. Math. 507 (1999), 189–218.
  * [87] Premet, A., Special transverse slices and their enveloping algebras. With an appendix by Serge Skryabin, Adv. Math. 170 (2002), 1–55.
  * [88] Premet, A., Irreducible representations of Lie algebras of reductive groups and the Kac-Weisfeiler conjecture, Invent. Math. 121 (1995), 79–117.
  * [89] Premet, A., Support varieties of non-restricted modules over Lie algebras of reductive groups, J. London Math. Soc. (2) 55 (1997), 236–250.
  * [90] Reshetikhin, N.Yu., Semenov-Tian-Shansky, M.A., Factorization problems for quantum groups, in: Geometry and Physics, essays in honour of I. M. Gelfand (S. Gindikin and I. M. Singer eds.), North Holland, Amsterdam - London - New York (1991), 533–550.
  * [91] Richardson, R.W., Conjugacy classes of involutions in Coxeter groups, Bull. Austral. Math. Soc. 26 (1982), 1–15.
  * [92] Rotman, S., Advanced Linear Algebra, Springer, New York (2005).
  * [93] Saito, Y., PBW Basis of Quantized Universal Enveloping Algebras, Publ. Math. RIMS 30 (1994), 209–232.
  * [94] Semenov-Tian-Shansky, M.A., What is a classical $r$-matrix, Funct. Anal. Appl. 17 (1983), 17–33.
  * [95] Semenov-Tian-Shansky, M.A., Dressing transformations and Poisson–Lie group actions, Publ. Math. RIMS 21 (1985), 1237–1260.
  * [96] Semenov-Tian-Shansky, M. A., Poisson Lie groups, quantum duality principle and the quantum double, Contemp. Math. 175 (1994) , 219–248.
  * [97] Semenov-Tian-Shansky, M. A., Sevostyanov, A., Drinfeld-Sokolov reduction for difference operators and deformations of W-algebras. II. General Semisimple Case, Comm. Math. Phys. 192 (1998), 631–647.
  * [98] Sevostyanov, A., Regular nilpotent elements and quantum groups, Comm. Math. Phys. 204 (1999) 1–16.
  * [99] Sevostyanov, A., Reduction of quantum systems with arbitrary first-class constraints and Hecke algebras, Comm. Math. Phys. 204 (1999), 137–146.
  * [100] Sevostyanov, A., The Whittaker model of the center of the quantum group and Hecke algebras, Ph.D. thesis, Uppsala (1999).
  * [101] Sevostyanov, A., Quantum deformation of Whittaker modules and the Toda lattice, Duke Math. J. 105 (2000), 211–238.
  * [102] Sevostyanov, A., Towards Drinfeld-Sokolov reduction for quantum groups, J. Geom. Phys. 33 (2000), 235–256.
  * [103] Sevostyanov, A., Algebraic group analogues of Slodowy slices and deformations of Poisson W–algebras, Int. Math. Res. Not. 2011 (2011), 1880–1925.
  * [104] Sevostyanov, A., Conjugacy classes in Weyl groups and q-W algebras, Adv. Math. 228 (2011), 1315–1376.
  * [105] Sevostyanov, A., The geometric meaning of Zhelobenko operators, Transf. Groups. 18 (2013), 865–-875.
  * [106] Sevostyanov, A., Localization of quantum biequivariant $\mathcal{D}$-modules and q–W algebras, Proc. London Math. Soc. 113 (2016), 583–-626.
  * [107] Sevostyanov A., Representations of quantum groups at roots of unity, Whittaker vectors and q-W algebras, J. of Alg. 511 (2018), 63–94.
  * [108] Sevostyanov A., Strictly transversal slices to conjugacy classes in algebraic groups, J. of Alg. 520 (2019), 309–366.
  * [109] Sevostyanov A., The structure of q-W algebras, Transf. Groups 25, no. 1 (2020), 279–304.
  * [110] Skryabin, S., Representations of the Poisson algebra in prime characteristic, Math. Z. 243 (2003), 563–597.
  * [111] Slodowy, P., Simple Singularities and Simple Algebraic Groups, Lecture Notes in Mathematics 815, Springer-Verlag, New York-Berlin (1980).
  * [112] Spaltenstein, N., Classes unipotentes et sous-groupes de Borel, Lecture Notes in Mathematics 946, Springer-Verlag, Berlin-New York (1982).
  * [113] Spaltenstein, N., On the generalized Springer correspondence for exceptional groups. Algebraic groups and related topics (Kyoto/Nagoya, 1983), 317–-338, Adv. Stud. Pure Math. 6, North-Holland, Amsterdam, (1985).
  * [114] Steinberg, R., Finite Reflection Groups, Trans. Amer. Math. Soc. 91 (1959), 493–504.
  * [115] Steinberg, R., Regular elements of semisimple algebraic groups, Publ. Math. I.H.E.S. 25 (1965), 49–80.
  * [116] Tolstoy, V. N., Fortieth anniversary of extremal projector method for Lie symmetries. Noncommutative geometry and representation theory in mathematical physics, in: Contemp. Math. 391, Amer. Math. Soc., Providence, RI (2005), 371–384.
  * [117] Weinstein, A., Local structure of Poisson manifolds, J. Different. Geom. 18 (1983), 523–558.
  * [118] Yakimov, M., On the spectra of quantum groups, Mem. Amer. Math. Soc. 229 (2014).
  * [119] Zelobenko, D. P., Compact Lie groups and their representations, Amer. Math. Soc., Providence (1973).
  * [120] Zelobenko, D. P., Extremal cocycles on Weyl groups, Funk. Anal. i ego Pril. 21, no. 3 (1987), 11–21.
  * [121] Zelobenko, D. P., Constructive Modules and Extremal Projectors over Chevalley Algebras, Funk. Anal. i ego Pril. 27, no. 3 (1993), 5–14; Funct. Anal. Appl. 27, no. 3 (1993), 158–165.
  * [122] Zelobenko, D. P., S–algebras and Harish–Chandra modules over symmetric Lie algebras, Izv. Akad. Nauk SSSR Ser. Mat. 54, no. 4 (1990), 659–675; Math. USSR-Izv. 37, no 1 (1991), 1–17.
  * [123] Zelobenko, D. P., An introduction to the theory of S–algebras over reductive Lie algebras. In: Representation of Lie groups and related topics, Adv. Stud. Contemp. Math. 7, Gordon and Breach, New York (1990), 155–221.
  * [124] Zelobenko, D. P., Extremal projectors and generalized Mickelsson algebras over reductive Lie algebras, Izv. Akad. Nauk SSSR Ser. Mat. 52, no. 4 (1988), 758–773; Math. USSR-Izv. 33, no. 1 (1989), 85–100.
  * [125] Zelobenko, D. P., S–algebras and Harish–Chandra modules over reductive Lie algebras, Dokl. Akad. Nauk SSSR 283, no 6 (1985), 1306–1308.
  * [126] Zelobenko, D. P., Z-algebras over reductive Lie algebras, Dokl. Akad. Nauk SSSR 273, no. 6 (1983), 1301–1304.
  * [127] Zelobenko, D. P., S-algebras and Verma modules over reductive Lie algebras, Dokl. Akad. Nauk SSSR 273, no. 4 (1983), 785–788.
  * [128] Zelobenko, D. P., Representation Theory of Reductive Lie Algebras (in Russian), Nauka, Moscow (1994).


# Challenges of variational quantum optimization with measurement shot noise

Giuseppe Scriva1,2,3, Nikita Astrakhantsev4, Sebastiano Pilati1,3, and
Guglielmo Mazzola2 1 Physics Division, School of Science and Technology,
University of Camerino, Via Madonna delle Carceri 9, I-62032 Camerino (MC),
Italy  2 Institute for Computational Science, University of Zurich,
Winterthurerstrasse 190, CH-8057 Zurich, Switzerland  3 INFN Sezione di
Perugia, Via A. Pascoli, I-06123 Perugia, Italy  4 Department of Physics,
University of Zurich, Winterthurerstrasse 190, CH-8057 Zurich, Switzerland
<EMAIL_ADDRESS>
###### Abstract

Quantum enhanced optimization of classical cost functions is a central theme
of quantum computing due to its high potential value in science and
technology. The variational quantum eigensolver (VQE) and the quantum
approximate optimization algorithm (QAOA) are popular variational approaches
that are considered the most viable solutions in the noisy-intermediate scale
quantum (NISQ) era. Here, we study the scaling of the quantum resources,
defined as the required number of circuit repetitions, to reach a fixed
success probability as the problem size increases, focusing on the role played
by measurement shot noise, which is unavoidable in realistic implementations.
Simple and reproducible problem instances are addressed, namely, the
ferromagnetic and disordered Ising chains. Our results show that: (i) VQE with
the standard heuristic ansatz scales comparably to direct brute-force search
when energy-based optimizers are employed. The performance improves at most
quadratically using a gradient-based optimizer. (ii) When the parameters are
optimized from random guesses, also the scaling of QAOA implies
problematically long absolute runtimes for large problem sizes. (iii) QAOA
becomes practical when supplemented with a physically-inspired initialization
of the parameters. Our results suggest that hybrid quantum-classical
algorithms should possibly avoid a brute force classical outer loop, but focus
on smart parameters initialization.

##  1 Introduction

Optimization is one of the most anticipated applications of quantum computers
due to its commercial value and widespread use in scientific and technological
applications. The first argument supporting the benefit of quantum
optimization is its ability to search through an exponentially large
computational space, of size $N=2^{L}$, using only $L$ qubits. However, such
memory compression alone is not sufficient, as the solution to a classical
combinatorial optimization problem is represented by a single (or very few)
$L$-bit string. This is in contrast with quantum algorithms for solving
genuinely quantum mechanics problems, where the source of possible quantum
advantage is easier to rationalize [1]. The quantum computational resource
enabling the search is interference. The process begins with a simple, easy-
to-prepare quantum state, which undergoes unitary evolution. Ideally, the
result of this evolution is such that, when the state is measured, the desired
bit string is observed with a high probability [2].

It is still unclear whether quantum optimization offers any advantage over the
existing classical methods, such as simulated annealing [3]. Interestingly,
optimization with quantum annealing has been the first application of
commercial quantum devices [4, 5], which mostly rely on incoherent tunneling
events to escape the cost-function local minima [6]. However, it is not easy
to prove systematic quantum speed-ups with analog quantum annealers [7, 8],
also because quantum Monte Carlo algorithms appear to be able to emulate their
tunneling dynamics [9, 10, 11, 12]. Yet, considerable effort is still ongoing
in improving the architecture of these machines [13] and their coherence times
[14].

As an alternative quantum optimization strategy, variational quantum
algorithms usually running on digital quantum devices, have gained attention
in the quantum computing community due to their short-depth circuits [15, 16].
In this approach, a long quantum state evolution is replaced by a series of
short-depth quantum circuits connected through a classical feedback loop.
Variational quantum computation features parametrized circuits that produce a
trial state $\ket{\psi({\boldsymbol{\theta}})}$. Its parameters
$\boldsymbol{\theta}$ are adjusted at every step following an iterative
classical procedure. The goal is to minimize a cost function $C$, which
corresponds to the expectation value
$\bra{\psi_{{\boldsymbol{\theta}}}}\hat{H}_{p}\ket{\psi_{{\boldsymbol{\theta}}}}$
of the the problem Hamiltonian $\hat{H}_{p}$, or a closely related measure. At
the end of a successful optimization, $\ket{\psi({\boldsymbol{\theta}})}$
should be peaked around the solution of the problem.

The two most popular variational algorithms for optimization are the quantum
approximate quantum optimization algorithm (QAOA) [17] and the variational
quantum eigensolver (VQE) [15]. QAOA is a digitized version of quantum
annealing in which the optimization parameters can be seen as tunable time
steps that control the evolution of the state under the alternating action of
the _problem_ and the _mixing_ operators, in a Trotterized fashion. The VQE
approach instead can be implemented with any parametrized quantum circuit,
with the problem Hamiltonian entering the algorithm only through the
evaluation of the cost function $C=\langle\hat{H}_{P}\rangle$.

Let us also recall that for combinatorial optimization problems, like Ising
spin glasses on general graphs [18], no polynomial-time algorithm can provably
find the global minimum, and the resources to exactly solve these problems
scale exponentially with problem size as $\sim 2^{kL}$. This is the type of
speed-up investigated in this Article. While quantum algorithms are not
expected to turn the exponential scaling into a polynomial one, the exponent
$k$ might be reduced, thus potentially realizing a substantial speed-up over
classical algorithms [19].

The QAOA method has been the subject of intense studies, including small and
medium-scale hardware experiments [20, 21, 22], numerical studies, and
theoretical works [23, 24, 25, 26, 27, 28, 29, 30]. Also VQE optimization has
been studied numerically and experimentally [31, 32, 33, 34, 35, 36, 37], and
it has been applied to diverse combinatorial optimization problems from
protein folding to finance [38, 39, 40, 41]. However, these previous studies
addressed small problem instances, without properly accounting for measurement
shot noise. In fact, the latter is unavoidable in physical implementations of
practically relevant problem sizes and it might affect the computational
complexity of these algorithms. To the best of our knowledge, the scaling of
the computational cost for a fixed target success probability, taking into
account the measurement overhead to compute the cost function $C$, has not
been exhaustively addressed yet.

The purpose of this study is to assess the efficiency of the VQE and QAOA
methods applied to simple and reproducible benchmarks while retaining the
general issue of the quantum-measurement noise. We numerically determine the
scaling of the runtimes for fixed success probabilities, taking into account
the overhead due to cost-function estimation for the optimal number of
measurements. Our results show that, in these realistic conditions, the basic
implementation of VQE and QAOA displays a problematic scaling. Notably, QAOA
with a smart variational-parameters initialization displays instead favorable
performances, indicating a promising route for practical applications.

The paper is organized as follows. In section 2, we define the testbed
problems and the quantum circuits. In section 3, we introduce the metric to
properly assess the computational scaling of the VQE and QAOA algorithms in
realistic conditions. In section 4.1, it is shown that in the presence of
quantum measurement noise, VQE displays a scaling not better than the direct
space enumeration when energy-based optimizers are used. The situation
improves using gradients, computed with the parameters shift rule (see section
4.2), but it remains scaling-wise impractical. In section 4.3, it is shown
that, while showing some scaling improvements, QAOA remains impractical when a
full optimization outer loop is required. In this case, the traditional
energy-based and a gradient-based optimizer show consistent scalings. Finally,
in section 4.5, we show that QAOA becomes competitive when the parameters are
initialized to mimic an adiabatic process. In section 5, we draw conclusions
and discuss realistic pathways toward quantum advantage in classical
optimization problems.

##  2 Optimization problems and quantum circuits

The optimization problems we address correspond to the Ising models defined
over $L$ variables $(\sigma_{1},\dots,\sigma_{L})=\boldsymbol{\sigma}$ with
$\sigma_{j}=\pm 1$. Specifically, we consider the one-dimensional
connectivity, nearest-neighbours interactions $J_{j,j+1}$ and local fields
$\\{h_{j}\\}_{j=1}^{L}$. The energy of a spin configuration
$\boldsymbol{\sigma}$ reads:

$E(\boldsymbol{\sigma})=-\sum_{j=1}^{L-1}J_{j,j+1}\sigma_{j}\sigma_{j+1}-\sum_{j=1}^{L}h_{j}\sigma_{j}.$
(1)

Representing a generic spin configuration
$\boldsymbol{\sigma}\in\\{1,-1\\}^{L}$ as a binary string
$\bi{x}\in\\{0,1\\}^{L}$, and writing the energy as
$E(\boldsymbol{\sigma})\rightarrow f(\bi{x})$, we write the problem
Hamiltonian $\hat{H}_{\mathrm{P}}$ as a diagonal operator

$\hat{H}_{\mathrm{P}}=\sum_{x}f(x)|x\rangle\langle x|,$ (2)

defined by its diagonal matrix elements
$f:\\{0,1\\}^{L}\rightarrow\mathbb{R}$. The classical spin variables
$\sigma_{j}$ are promoted to single-qubit Pauli operators
$\hat{\sigma}_{j}^{z}$.

Most analyses reported in this Article consider two problem Hamiltonians. The
first is the _ferromagnetic_ Hamiltonian defined by uniform couplings
$J_{j,j+1}=J=1$, and a (small) uniform local field $h_{j}=h=-0.05$ introduced
to break the degeneracy between the two fully-polarized configurations and
obtain a single global minimum. Despite its simplicity, this model turns out
to be hard for most of the considered algorithms. Its rugged energy surface
$f(x)$ is shown in figure 1, where the bitstrings are sorted in the
lexicographic order.

Figure 1:  (a) The energy landscape in the computational basis, where items
are sorted in the lexicographical order for a ferromagnetic model with $L=8$.
The small uniform field breaks the degeneracy between the $`00\dots 0`$ and
$`11\dots 1`$ bitstrings, with the latter being the global minimum. (b) The
RY-CNOT circuits used in the VQE and commonly employed in related literature.
(c) The QAOA circuit featuring the specific problem Hamiltonian.

The second optimization problem we address is an ensemble of _disordered_
Hamiltonians where the couplings and fields are sampled from a normal
distribution with zero mean and unit variance:
$J_{j,j+1},h_{j}\sim\mathcal{N}(0,1)$. In this case, 30 realizations of the
disorder are simulated for each problem size $L$.

###  2.1 VQE with heuristic circuit

Parameterized quantum circuits [15, 16] are the essential ingredients of any
variational quantum algorithm. These circuits employ parametrized gates,
including the single-qubit rotation gates, and multi-qubit entangling gates
such as the CNOT gate. The set of variational parameters $\boldsymbol{\theta}$
is optimized in a classical outer loop [15] to minimize a target cost
function.

The most commonly studied heuristic circuit is made of $d$ blocks built from a
layer of single-qubit rotations $U_{\mathrm{R}}(\boldsymbol{\theta}^{l})$ with
$l=1,\cdots,d+1$ and an entangling block $U_{\mathrm{ent}}$ that covers the
whole qubit register (see figure 1). In this Article, we consider the
entangling block made of a ladder of CNOT gates with linear connectivity, such
that the qubit $q_{j-1}$ controls the target qubit $q_{j}$, and the latter
controls the qubit $q_{j+1}$, obeying open boundary conditions. This choice is
commonly used as it mimics the existing sparse qubit connectivity of the
quantum hardware. The layer of single-qubit rotations
$U_{\mathrm{R}}(\boldsymbol{\theta}^{l})$ acts locally and it corresponds to a
tensor product of single-qubit rotations:

$U_{\mathrm{R}}(\boldsymbol{\theta}^{l})=\bigotimes_{j=1}^{L}R_{y}({\theta}_{j}^{l}),$
(3)

where
$R_{y}({\theta}^{l}_{j})=\exp{\left(-i\theta^{l}_{j}\hat{\sigma}^{y}/2\right)}$
is a rotation around the $y$–axis of the Bloch sphere of the qubit $q_{j}$,
and $l=1,\cdots,d+1$. Here, $\boldsymbol{\theta}^{l}$ denotes an array of $L$
angles. The full unitary circuit operation is described by

$U_{\mathrm{R-CNOT}}(\boldsymbol{\theta})=U_{\mathrm{R}}(\boldsymbol{\theta}^{d+1})~{}\overbrace{U_{\mathrm{ent}}U_{\mathrm{R}}(\boldsymbol{\theta}^{d})\ldots
U_{\mathrm{ent}}U_{\mathrm{R}}(\boldsymbol{\theta}^{1})}^{\textrm{$d$-times}},$
(4)

and the final parametrized state reads

$\ket{\psi(\boldsymbol{\theta})}=U_{\mathrm{R-CNOT}}(\boldsymbol{\theta})\left(\ket{0}^{\otimes
L}\right).$ (5)

The total number of variational parameters is $n_{\mathrm{par}}=L(d+1)$.
Notice that we do not use symmetries nor prior knowledge of the optimization
problem in building the circuit up.

###  2.2 The QAOA circuit

QAOA can be understood as a digitized version of quantum annealing [17] that
requires variational optimization of circuit parameters. These parameters can
be seen as the optimizable time steps that control the evolution of the state
under the action of the _problem_ and the _mixing_ operators in a Trotterized
fashion. Notice that the QAOA method precisely dictates the structure of the
quantum circuits, while VQE can be implemented with any parametrized quantum
circuit. In particular, the classical Hamiltonian (i. e., the cost function)
explicitly appears in the QAOA circuit, while a VQE circuit may be completely
heuristic, with the problem Hamiltonian informing the whole algorithm only
through the evaluation of the cost function after the wave function collapses.

The unitary operator defining the ansatz is made of $d$ blocks, each of them
being the product of two unitary operators
$\hat{U}_{\mathrm{P}}=\exp{\left(i\theta_{\mathrm{P}}^{l}\hat{H}_{\mathrm{P}}\right)}$,
and
$\hat{U}_{\mathrm{M}}=\exp{\left(i\theta_{\mathrm{M}}^{l}\hat{H}_{\mathrm{M}}\right)}$,
with $l=1,\cdots,d$ and where $\hat{H}_{\mathrm{P}}$ is the problem
Hamiltonian, and

$\hat{H}_{\mathrm{M}}=\sum_{j=1}^{L}\hat{\sigma}_{j}^{x}$ (6)

is the non-diagonal _mixing_ operator.

The implementation of these unitary operators involves efficient single-qubit
rotations along the $x$-axis, denoted as
$R_{x}(\theta)=\exp{\left(i\theta\hat{\sigma}^{x}/2\right)}$, and two-qubit
parametrized gates,
$R_{zz}(\theta)=\exp{\left(i\theta\hat{\sigma}^{z}\otimes\hat{\sigma}^{z}/2\right)}$.
The structure of the QAOA ansatz implies that all the local
$\hat{\sigma}^{z}\otimes\hat{\sigma}^{z}$ interactions within the same block
are ‘evolved’ with the same time step $\theta_{P}^{l}$, while all the
$x$-rotations within the block are parametrized by the same angle
$\theta_{M}^{l}$ (see figure 1). The total number of parameters is
$n_{\mathrm{par}}=2d$, i. e., is independent of the problem size $L$, and the
full unitary operator reads

$U_{\mathrm{QAOA}}(\boldsymbol{\theta})=\overbrace{\hat{U}_{\mathrm{M}}(\theta^{d}_{M})\hat{U}_{\mathrm{P}}(\theta^{d}_{P})\ldots\hat{U}_{\mathrm{M}}(\theta^{1}_{M})\hat{U}_{\mathrm{P}}(\theta^{1}_{P})}^{d\textrm{-times}}.$
(7)

The final parametrized state is

$\ket{\psi(\boldsymbol{\theta})}=U_{\mathrm{QAOA}}(\boldsymbol{\theta})~{}\left(\frac{\ket{0}+\ket{1}}{\sqrt{2}}\right)^{\otimes
L},$ (8)

where the initial non-entangled state can be obtained from the state
$\ket{0}^{\otimes L}$ by acting with one Hadamard gate on each qubit.

##  3 Resource counting and scaling analysis

###  3.1 Statistical noise in evaluating the cost function

The expectation value of $\hat{H}_{\mathrm{P}}$ over the prepared state is
given by the sum of all spin configurations

$\tilde{C}=\langle\psi_{\boldsymbol{\theta}}|\hat{H}_{\mathrm{P}}|\psi_{\boldsymbol{\theta}}\rangle=\sum_{x=0}^{2^{L}-1}|\psi_{\boldsymbol{\theta}}(x)|^{2}f(x).$
(9)

The full sum can be approximated using a finite sample of configurations

$\tilde{C}\approx\frac{1}{M}\sum_{i=1}^{M}f(x_{i}),$ (10)

where $x_{i}$ are sampled from $|\psi_{\boldsymbol{\theta}}(x)|^{2}$. The
precision of this estimate is affected by statistical noise induced by the
finite number of quantum measurements $M$. In numerous studies, (9) is
evaluated exactly, which is dubbed the _state-vector_ simulation. Instead, in
our analysis we account for the effects of the finite $M$.

It has been empirically shown that better performances for optimization
problems can be obtained by considering a modified version of the cost
function. In fact, in optimization problems one is not interested in the
average value, but in the minimum one. Therefore, we adopt the CVaR estimator
of [31], in which the cost function is evaluated by summing only over the best
$25\,\%$ of observed outcomes $f(x_{i})$:

${C}=\frac{1}{M^{*}}\sum_{i=1}^{M^{*}}f(x_{i}).$ (11)

Operatively, the $M$ readouts are sorted in non-decreasing order following
their output $f(x_{i})$, and only $M^{*}=M/4$ samples corresponding to the 25
% lowest values are retained. The value $C$ represents the cost-function that
is optimized at each iteration. We can also keep track of the current minimum
observed value $f_{\mathrm{min}}$, which is generally smaller than $C$. Its
final value is compared with the exact global minimum of the optimization
problem to determine the success rate of the algorithm.

###  3.2 Optimal scaling

The time complexity of an optimization algorithm can be expressed as the
number of function calls $f(x)$ necessary to find the optimum, aiming at a
_fixed_ success probability as the problem sizes increase. We recall that, in
all realistic implementations of variational algorithms, the value of the cost
function $C$ cannot be exactly computed. In fact, $C$ needs to be evaluated by
performing $M$ measurements as in (10). Notice that also in the case of (11)
one needs to draw $M$ samples.

Figure 2:  Optimization of the ferromagnetic Ising chain using the VQE ansatz
with depth $d=2$. (a-b): Success probability $F_{\mathrm{succ}}$ as a function
of the total number of function calls $n_{\mathrm{calls}}=M\times
n_{\mathrm{iter}}$, for (a) $L=8$ spins and (b) $L=14$ spins. Different colors
correspond to the different combinations of measurement-shot number $M$ and
classical optimization steps $n_{\mathrm{iter}}$. The dashed curve corresponds
to the random search with replacement. The inset of panel (b) shows an example
of the interplay between $M$ and $n_{\mathrm{iter}}$. To reach larger
$F_{\mathrm{succ}}$ it is better to systematically increase $M$. For
$F_{\mathrm{succ}}\approx 0.8$, using $M=512$ appears marginally better than
$M=1024$, which in turn becomes optimal at $F_{\mathrm{succ}}\approx 0.9$, and
so on. Crucially, each set-up performs worse than the random search. (c):
Minimal number of function calls $n_{\mathrm{calls}}^{*}$ as a function of the
number of spins $L$ for different $F_{\mathrm{succ}}$. Circuits with $d=1$
(full symbols) and $d=2$ (empty symbols) blocks are considered. The thick
dashed (red) line represents the scaling $n_{\mathrm{calls}}^{*}\sim 2^{L}$
corresponding to full enumeration. Thin continuous and dashed lines represent
fitting functions of the form $n_{\mathrm{calls}}^{*}=a2^{kL}$, and the
fitting parameters $a$ and $k$, obtained considering the large $L$ regime, are
given in the legend.

The total number of function calls required for a full optimization run is
therefore

$n_{\mathrm{calls}}=n_{\mathrm{iter}}\times M,$ (12)

where $n_{\mathrm{iter}}$ is the number of (classical) optimization steps. The
total runtime of the algorithm is proportional to $n_{\mathrm{calls}}$. A
lower bound is given by $t_{\mathrm{run}}=n_{\mathrm{calls}}\times d\times
t_{\mathrm{gate}}$, where again $d$ is the circuit depth, expressed as the
number of repetitions of a minimal unit (called block) of quantum gates, and
$t_{\mathrm{gate}}$ is the time to execute each block. The value of
$t_{\mathrm{gate}}$ strongly depends on the hardware. In the NISQ era, the
gate times can be of order $10$ ns ($100$ MHz) for superconducting hardware
[42], while digital gate time is predicted to be about $0.1$ ms ($10$ kHz) in
the fault-tolerant regime [43]. These estimates neglect the qubit reset time,
the classical communication, and the measurement time, so they clearly
represent optimistic perspectives.

For each problem size, there exists a trade-off between the number of
iterations $n_{\mathrm{iter}}$ needed to converge to the global minimum, and
the number $M$ of measurements, which controls the accuracy in evaluating the
cost function at each step. Large errors in $C$ may imply slower convergence
since the cost function landscape is not correctly reproduced, thus negatively
affecting the performance of the classical optimization algorithm.

One of the merits of the present study is the systematic identification of the
minimum $n_{\mathrm{calls}}^{*}$, corresponding to the optimal combination of
$n_{\mathrm{iter}}$ and $M$ for each problem size $L$, thus enabling a proper
scaling analysis. This concept is similar to the optimal time-to-solution
metric developed in quantum annealing [8]. We point out that one must have
$n_{\mathrm{calls}}^{*}<2^{L}$ to avoid quantum disadvantage [44], without
even discussing the values of $t_{\mathrm{gate}}$.

With the definitions given above, (12) can be used to compute the number of
function calls only in the case of so-called energy-based optimizers. However,
in this Article, we also consider gradient-based methods (see section 4.2 and
section 4.4). In this case, one needs to compute a $n_{\mathrm{par}}$-valued
array of energy derivatives at each optimization step. For each parameter, two
independent circuit runs need to be executed. This holds both for the
parameters shift rule (in this case, when applicable, the gradients are exact)
and the finite difference method. Therefore, the cost for a single iteration
has to be computed as $M=2n_{\mathrm{par}}\tilde{M}$, where $\tilde{M}$ is the
number of shots per single circuit execution.

##  4 Results

###  4.1 Impracticality of VQE

Here we analyze the performance of the VQE method for the ferromagnetic
problem. The circuit simulations are performed using the open-source Qiskit
framework [45]. In evaluating the algorithm’s efficiency, a run is considered
successful when the absolute minimum is found at least once within the
$n_{\mathrm{iter}}$ steps. This procedure is standard in benchmarking quantum
devices, such as quantum annealers, versus classical optimizers [5, 6, 8]. The
fraction $F_{\mathrm{succ}}$ of successful runs is estimated considering 1000
executions starting from different (random) initializations of the variational
parameters. It is crucial to note that, within the VQE heuristic circuit,
there is no _a priori_ method for a smart initialization of the parameters.
Therefore, we initialize the parameters using a random uniform distribution of
$\boldsymbol{\theta}$. Moreover, optimized parameters are not transferable to
different instances.

We first inspect how $F_{\mathrm{succ}}$ depends on the total number of
function calls $n_{\mathrm{calls}}$, for different problem sizes $L$. For each
$L$, several choices of $M$ and $n_{\mathrm{iter}}$ are considered, allowing
us to identify the minimal number of function calls $n_{\mathrm{calls}}^{*}$
for each target success rate. This procedure is crucial to correctly assess
the scaling of the computational cost with the problem size. In this section,
the classical parameter optimization is performed using the COBYLA optimizer,
a widely adopted energy-based algorithm for QAOA [31, 46]. Let us also recall
that the CVaR estimator of (10) is adopted. The gradient-based method, that
uses the parameters shift rule, is discussed in section 4.2. The performance
of the (COBYLA driven) VQE method, with circuit depths $d=1,\,2$, is shown in
figure 2. First, we observe that, for all choices of $M$ and
$n_{\mathrm{iter}}$, the value of $n_{\mathrm{calls}}$ required to reach a
target $F_{\mathrm{succ}}$ is not better than the one corresponding to random
search with replacement, see panel (a). Furthermore, as shown in panel (c),
the minimal number of function calls $n_{\mathrm{calls}}^{*}$ displays a
problematic scaling with the problem size, closely matching the exponential
law $n_{\mathrm{calls}}^{*}\sim 2^{kL}$ with $k\simeq 1$. This holds for all
the thresholds of $0.25\leqslant F_{\mathrm{succ}}\leqslant 0.9$ considered in
this study. Notably, VQE circuits with depths $d=1$ and $d=2$ display
comparable scaling, suggesting that simply increasing the circuit depth does
not help.

In A it is shown that hardware noise, which we simulate using a custom model
in Qiskit [45], does not significantly affect this scaling.

###  4.2 Gradient-based VQE optimization

Next, we consider the VQE algorithm driven by a gradient-based algorithm,
addressing again the ferromagnetic problem. The gradients are obtained using
the parameter shift rule, which is applicable under certain conditions on the
adopted gate set [47, 48]. The $n^{\mathrm{th}}$ component of the gradient is
computed as $n\in(1,\dots,n_{\mathrm{par}})$:

$\frac{\partial\tilde{C}}{\partial\theta_{n}}=\frac{1}{2}\Big{[}\langle\psi_{\boldsymbol{\theta}_{n}^{+}}|\hat{H}_{\mathrm{P}}|\psi_{\boldsymbol{\theta}_{n}^{+}}\rangle-\langle\psi_{\boldsymbol{\theta}_{n}^{-}}|\hat{H}_{\mathrm{P}}|\psi_{\boldsymbol{\theta}_{n}^{-}}\rangle\Big{]},$
(13)

where
$\boldsymbol{\theta}_{n}^{\pm}=\left(\theta_{1},\dots,\theta_{n}\pm\pi/2,\dots,\theta_{n_{\mathrm{par}}}\right)$.

Figure 3: Minimal number of function calls $n_{\mathrm{calls}}^{*}$ as a
function of the number of spins $L$ for different $F_{\mathrm{succ}}$. VQE
circuits of depth $d=2$ are considered with the gradient descent (full
symbols) and with the COBYLA optimizer (empty symbols). The thick dashed (red)
line represents the scaling $n_{\mathrm{calls}}^{*}\sim 2^{L}$ corresponding
to the exact enumeration. Thin continuous and dashed lines represent fitting
functions of the form $n_{\mathrm{calls}}^{*}=a2^{kL}$, and the fitting
parameters $a$ and $k$, obtained by fitting the large $L$ data, are given in
the keys.

Notice that, in this case, the cost function is computed as in (10), rather
than adopting the CVaR estimator.

At each iteration $i$, the parameter $\boldsymbol{\theta}^{(i)}$ is updated
as:

$\boldsymbol{\theta}_{i+1}=\boldsymbol{\theta}_{i}-\eta\nabla{\tilde{C}}\left({\boldsymbol{\theta}_{i}}\right),$
(14)

where $\eta$ is the learning rate. The value $\eta=0.1$ is chosen, as it turns
out to be reasonably close to optimal from a preliminary analysis on the
problem size $L=6$ . As before, the optimal combination of $M$ and
$n_{\mathrm{iter}}$ is found, and the computational complexity is analyzed by
observing the scaling of $n_{\mathrm{calls}}^{*}$ with the problem size (see
figure 3). Interestingly, an approximately quadratic speedup compared with the
COBYLA optimizer is found, at least for $F_{\mathrm{succ}}\leq 0.5$.

###  4.3 QAOA with random parameters initialization

Here, the performance of QAOA is analyzed, using the (energy-based) COBYLA
optimizer. The first tests focus on the ferromagnetic model. We expect to
observe a better performance compared to VQE, because QAOA features the
problem Hamiltonian also in the circuit, not only in the cost function. To
support this intuition, we perform a preliminary comparison, considering
circuits with random variational parameters, i. e., avoiding any classical
optimization iteration. Specifically, we prepare 1000 different QAOA circuits,
and just as many for VQE, using uniformly distributed parameters, and sample
$M=16$ measurements from each of them. The probability $F_{\mathrm{succ}}$ of
observing the exact solution at least once is then computed.

Figure 4: Success probability $F_{\mathrm{succ}}$ as a function of the system
size $L$ before the classical optimization, for a fixed shot number $M=16$.
The QAOA (circle markers) and VQE (square markers) ansatze have the same depth
$d=2$ and randomly chosen parameters. The lines represent fits, obtained from
the large $L$ data, as a guide for the eyes.

As shown in figure 4, the QAOA ansatz clearly outperforms VQE. We attribute
this to its higher degree of localization around the correct solution, even
when the parameters are random. Notice that in this analysis the choice of the
optimizer is not relevant, allowing us to compare the circuits independently
of the way they are optimized. One might also expect that, since the QAOA
circuit features fewer parameters, it should be easier to optimize as compared
to VQE [49].

Figure 5:  Optimization of the ferromagnetic (first row) and the disordered
(second row) Ising chains within the QAOA method. (a-b, d-e): Success
probability $F_{\mathrm{succ}}$ as a function of the total number of function
calls $n_{\mathrm{calls}}$, for $L=8$ spins (a, d) and $L=14$ spins (b, e).
The error bars indicate the 25th and the 75th percentiles. Different colors
correspond to the different combinations of measurement budgets $M$ and
classical optimization-step counts $n_{\mathrm{iter}}$. The dashed curve
corresponds to the random search with replacement. (c, f): The optimal number
of function calls $n_{\mathrm{calls}}^{*}$ as a function of the number of
spins $L$ for different $F_{\mathrm{succ}}$. Circuits with $d=2$ blocks (full
symbols) and with $d=4$ blocks (empty symbols) are considered. The thick
dashed (red) line represents the scaling $n_{\mathrm{calls}}^{*}\sim 2^{L}$
corresponding to exact enumeration. Thin continuous and dashed lines represent
fitting functions of the form $n_{\mathrm{calls}}^{*}=a2^{kL}$, and the
fitting parameters $a$ and $k$ are obtained by fitting the large $L$ data and
are given in the keys.

To exhaustively assess the QAOA performance, we repeat the procedure described
in section 4.1, exploring different combinations of $n_{\mathrm{iter}}$ and
$M$. Again, this allows us to identify the optimal number of function calls
$n_{\mathrm{calls}}^{*}$ for the target cumulative success probability
$F_{\mathrm{succ}}$ and problem size $L$. For each choice of
$n_{\mathrm{iter}}$ and $M$, 1000 circuit executions are performed starting
from random uniformly-distributed parameters. Notably, for all considered
success probabilities $F_{\mathrm{succ}}$, the number of function calls is
well described by the exponential scaling law $n_{\mathrm{calls}}^{*}\sim
2^{kL}$, with $k\simeq 0.4$. This corresponds to an approximately quadratic
speed-up as compared to the exact enumeration. Given that the choice of the
classical optimizer may change the observed scaling, in B, we test also the
SPSA algorithm [50]. We find that the SPSA and COBYLA results are compatible.
We further test this finding on a more challenging system, namely, the
disordered Ising model. The results are shown in figure 5 (d-f). Also in this
case they are averaged over 30 realizations of the random couplings and fields
of the problem Hamiltonian. Similarly to the ferromagnetic case, we observe a
profitable scaling, namely, $k\in[0.5,0.8]$, to be compared with the full
enumeration, corresponding to $k=1$. However, in this case, extracting the
scaling exponent is more difficult, because $n_{\mathrm{calls}}$ needs to be
increased to reach large $F_{\mathrm{succ}}$, leading to prohibitive
computational times for large problem sizes. Notably, both for the
ferromagnetic and the disordered problem Hamiltonians, increasing the circuit
depth from $d=2$ to 4 does not substantially affect the scaling.

To summarize the above findings, the observed QAOA scaling exponents are about
$k\simeq 0.4$ for the ferromagnetic problem, and $0.5\lesssim k\lesssim 0.8$
for the disordered models, using the COBYLA optimizer and random parameters
initialization. This scaling is comparable to the one of VQE using gradients.
While better than full enumeration, these scalings still determine unfeasible
runtimes (see discussions in section 5) for problem instances of practical
interest, i. e., featuring at least hundreds of spins.

###  4.4 Gradient based QAOA optimization

Figure 6: (a): Absolute error $|\mathrm{err}|$ in estimating the gradient as a
function of the step $\varepsilon$ of the finite difference approximation. We
compare results obtained with a different number of shots $M$. (b): The
minimal number of function calls $n_{\mathrm{calls}}^{*}$ as a function of the
number of spins $L$, for different success probabilities $F_{\mathrm{succ}}$.
Circuits with $d=2$ blocks are considered, with gradient descent (full
symbols) and with COBYLA optimizer (empty symbols). The thick dashed (red)
line represents the scaling $n_{\mathrm{calls}}^{*}\sim 2^{L}$ corresponding
to exact enumeration. Thin continuous and dashed lines represent fitting
functions of the form $n_{\mathrm{calls}}^{*}=a2^{kL}$, and the fitting
parameters $a$ and $k$, obtained considering the large $L$ data, are given in
the keys.

Here, we benchmark the scalings of QAOA driven by the COBYLA optimizer against
a gradient-based method. Contrary to the case described in section 4.2, the
QAOA circuit does not satisfy the assumptions to apply the parameter shift
rule. [48] While there are attempts to extend the parameter shift rule, see,
e. g., [51], here we adopt the finite difference approximation. The
$n^{\mathrm{th}}$ gradient component is computed as:

$\frac{\partial\tilde{C}}{\partial\theta_{n}}=\frac{1}{2\varepsilon}\Big{[}\langle\psi_{\boldsymbol{\theta}_{n}^{+\varepsilon}}|\hat{H}_{\mathrm{P}}|\psi_{\boldsymbol{\theta}_{n}^{+\varepsilon}}\rangle-\langle\psi_{\boldsymbol{\theta}_{n}^{-\varepsilon}}|\hat{H}_{\mathrm{P}}|\psi_{\boldsymbol{\theta}_{n}^{-\varepsilon}}\rangle\Big{]},$
(15)

where
$\boldsymbol{\theta}_{n}^{\pm\varepsilon}=\left(\theta_{1},\dots,\theta_{n}\pm\varepsilon,\dots,\theta_{n_{\mathrm{par}}}\right)$
and $\varepsilon>0$ is the increment. Small values reduce the finite-
difference error, but they also enhance the random fluctuations due to the
finite number of measurements $\tilde{M}$ used to estimate the expectation
values in (15). To identify the optimal trade-off regime, we compare the
estimated gradients with the exact results from state-vector simulations (see
panel (a) of figure 6). For the typically optimal shot numbers
$\tilde{M}\in\left[2,16\right]$, the error is minimized for increments close
to $\varepsilon=0.5$. This value is adopted hereafter.

With the above setting, we analyze the scaling of the optimal
$n_{\mathrm{call}}^{*}$ with the problem size $L$ (see panel (b) of figure 6).
Any benefit provided by the gradient turns out to be essentially compensated
by its cost in terms of measurement shots. Recently, the detrimental cost of
gradient estimation has been highlighted addressing the application of quantum
computers for electronic structure [52]. The overall improvement compared to
the scaling obtained with the COBYLA optimizer is not sizable. Furthermore, it
is worth noticing that even for the larger size considered in this work, the
gradient-based optimization requires larger $n_{\mathrm{call}}^{*}$.

This is the second main result of the paper: a naive textbook implementation
of QAOA using random starting parameters is practically inefficient, even when
gradient-based optimizers are used, despite showing an improved scaling with
respect to random search.

###  4.5 QAOA with annealing inspired parameters initialization

On one hand, the above findings indicate that QAOA is computationally
unfeasible for problem sizes of practical interest. On the other hand, QAOA
can be interpreted as a digitized version of quantum annealing, and previous
studies have shown that the available quantum-annealing devices can already
find solutions of large-scale spin-glass instances in a reasonable runtime [6]
even for problem sizes as large as $L=512$. To solve this apparent conundrum,
we perform QAOA in its adiabatic limit. Formally, this limit is reached when
$d\rightarrow\infty$. However, as pointed out in section 4.3, doubling the
number of layers does not decisively change the computational scaling. In
fact, the number of parameters increases with the circuit depth, and more
parameters usually require more optimization iterations.

Figure 7: Comparison of the optimizations starting from random (section 4.3)
and annealing-inspired initializations (linear schedule, section 4.5) for the
ferromagnetic model. (a-b): The success probability $P_{\mathrm{succ}}$ as a
function of the number of spins $L$, obtained within QAOA before (continuous
curves) and after (dashed curves) the classical optimization performed for
$n_{\mathrm{iter}}$ steps. The number of shots (a) $M=16$ and (b) $M=32$ are
considered, chosen so that $M\ll 2^{L}$. Note that $P_{\mathrm{succ}}$, i. e.
the probability to sample at least once the global minimum at the $n$-th
iteration, is equal by definition to $F_{\mathrm{succ}}$ when
$n_{\mathrm{iter}}=0$. (c): The minimal number of function calls
$n_{\mathrm{calls}}^{*}$ as a function of $L$ at fixed success probabilities
$F_{\mathrm{succ}}$, starting from the annealing-inspired initialization.
Circuits with $d=2$ blocks (full symbols) and with $d=4$ blocks (empty
symbols) are considered. The thick dashed (red) line represents the scaling
$n_{\mathrm{calls}}^{*}\sim 2^{L}$ corresponding to exact enumeration. The
thin continuous and dashed lines represent fitting functions of the form
$n_{\mathrm{calls}}^{*}=a2^{kL}$, and the fitting parameters $a$ and $k$,
obtained by fitting the large $L$ data, are given in the keys.

Still, the analogy with quantum annealing inspires a systematic way to
effectively initialize the parameters. Indeed, in [26] it was observed that,
in state-vector simulations, the optimal parameters often follow a pattern
similar to the quantum annealing prescription: the parameters controlling the
mixing operator $\boldsymbol{\theta}_{M}$ decrease, while the parameters
controlling the problem operator $\boldsymbol{\theta}_{P}$ increase with the
layer index. Following this idea, we initialize the parameters using the
simplest discretized linear schedule, as in [53]:

$\theta_{M}^{l}=\left(1-\frac{l}{d}\right)\Delta_{t},\qquad\theta_{P}^{l}=\frac{l}{d}\Delta_{t},$
(16)

where $l\in[1,\cdots,d]$. Notice that in most QAOA literature, the parameters
that control the mixing operators are denoted with $\beta$, while the problem
parameters are denoted with $\gamma$.

In [53], this initialization was found effective for MaxCut problems solved
via state-vector simulations, i. e., eliminating the measurement shot noise.
Here, we show that this initialization is not only an improvement to the QAOA
textbook strategy, but it is also essential to make the algorithm practical in
realistic conditions where measurement noise is accounted for. Notice that
with the re-parametrization in (16), the angles $\theta_{M}^{l}$ and
$\theta_{P}^{l}$ depend only on one real degree of freedom $\Delta_{t}$. More
complex reparametrizations could also be possible.

To guide us in the choice of a suitable value for $\Delta_{t}$, we perform a
reasonably exhaustive search, using 8 independent repetitions of state-vector
simulation using $L=4,6,8,10$ and depths $d=2,4,6,8$. It is found that the
value $\Delta_{t}\approx 0.80$ is the most frequent outcome of these
optimization runs. Notably, a similar optimal value was found in [53] in the
case of MaxCut instances on random graph. These combined findings suggest that
the quantum-annealing inspired initialization is a general and robust
procedure. This is further corroborated by the results for the disordered
Hamiltonian, discussed below.

Hereafter, we first tackle the ferromagnetic problem, using the above
prescription. The performance of the QAOA circuit with the annealing-inspired
parameters is compared to the ones of the QAOA circuits with the parameters
obtained after the fixed numbers of optimization iterations
$n_{\mathrm{iter}}=20$ and $n_{\mathrm{iter}}=60$, starting from the same
smart initialization. Notice that here the following definition of success
probability $P_{\mathrm{succ}}$ is adopted: $M$ measurements are performed on
the prepared state (with $M=16$ or $M=32$), and the fraction of successful
executions at a selected $n_{\mathrm{iter}}$ is recorded. This fraction
differs from $F_{\mathrm{succ}}$, which corresponds to the probability of
observing the solution at least once during all optimization iterations, not
only in the final state. The scaling of $P_{\mathrm{succ}}$ with problem size
is shown in figure 7, panels (a) and (b).

One observes that the QAOA ansatz with the annealing-inspired linear
initialization is already optimal, for both circuit depths $d=2$ and $d=4$.
The optimization of the parameters does not yield better ansatze to sample
from. Two important observations are due: (i) the scaling exponent $k$ is
reduced compared to the random initialization case, and (ii) $k$ decreases
with the circuit depth, as opposed to the case of random initialization
displayed in panel (c) of figure 5. In the panel (c) of figure 7, the scaling
of the optimal number of calls $n_{\mathrm{calls}}^{*}$ is shown, following
the procedure already discussed in section 4.1 and 4.3. This indicates that
optimizations started from random parameters, performed with a finite budget
of shots $M$, are not able to showcase the higher expressive power of deeper
circuits. These numerical results suggest that, with a deep enough circuit,
the exponent $k$ can be reduced enough to reach practically useful
performances for relevant problem sizes. This hypothesis is corroborated by
the analysis reported at the end of this subsection.

Figure 8: Success probability $P_{\mathrm{succ}}$ as a function of the number
of spins $L$, starting from random and from annealing-inspired initializations
for the disordered Hamiltonian. We compare the success probability
$P_{\mathrm{succ}}$ obtained via QAOA before (continuous curves) and after
(dashed curves) the classical optimization performed for $n_{\mathrm{iter}}$
steps.

As anticipated above, here we repeat the numerical experiment using ensembles
of disordered Ising chains. It turns out that the pre-computed value of
$\Delta_{t}\approx 0.80$ is appropriate, in most instances, also in this
setting. Importantly, in figure 8 we show that also in this case the smartly
initialized ansatz features almost converged parameters; indeed, the success
probability $P_{\mathrm{succ}}$ does not improve when the circuit is further
optimized up to $n_{\mathrm{iter}}=30$ steps. Notice that $P_{\mathrm{succ}}$,
i. e. the probability to sample at least once the global minimum at the $n$-th
iteration, is equal by definition to $F_{\mathrm{succ}}$ when
$n_{\mathrm{iter}}=0$. The random-initialized circuit instead benefits from
the optimization run, although it never reaches the success probability of the
linearly-initialized ansatz. This result clearly shows that it is much better
to use a clever parameters initialization without optimization, instead of
randomly initializing the parameters $\boldsymbol{\theta}$ and performing the
optimization.

Figure 9: Success probability $F_{\mathrm{succ}}$ as a function of the number
of spins $L$ without classical optimization. Using the smart linear
initialization, $F_{\mathrm{succ}}$ grows when the circuit depth is increased,
both for the (a) ferromagnetic model and (b) the disordered problems. In the
latter, we consider 30 instances of disorder and the error bars indicate the
25th and the 75th percentiles.

Finally, we try to numerically demonstrate that, with the annealing-inspired
initialization, sufficiently deep QAOA circuits can reach appealing
performances, even without performing classical parameter optimizations. To
this end, we determine the success probability $F_{\mathrm{succ}}$ as a
function of the problem size $L$, for several circuit depths $d$ at fixed shot
numbers $M$ (see figure 9). It is found that the performance systematically
and rapidly increases with $d$, reaching $F_{\mathrm{succ}}\simeq 1$ even for
the largest considered size $L$, for sufficiently deep circuits. This evidence
matches the intuition that QAOA reduces to quantum annealing when $d$ is
increased and the circuit parameters follow the pattern in (16) (although
different schedules are possible) [29]. Notice that here, the number of shots
is $M<2^{L}$ for the sizes considered.

##  5 Discussion

We critically analyze two popular quantum algorithms for optimization,
addressing controllable and reproducible testbed models, i. e., the
ferromagnetic and the disordered Ising chains. The two optimization
algorithms, namely, VQE and QAOA, are variational methods and rely on an outer
classical parameter optimization to (hopefully) identify a suitable circuit
that allows sampling of the exact solution with high probability.

On one hand, our results indicate that, in the practical regime where the
number of measurements $M$ per optimization step is much smaller than the
Hilbert-space dimension $2^{L}$, basic optimization strategies fail to
identify suitable circuit parameters. On the other hand, appealing
performances are achieved by deep QAOA circuits when a smart parameters
initialization is adopted, as further discussed below. To reach the above
conclusions, we track the total number of measurements
$n_{\mathrm{calls}}^{*}$ to reach a fixed target success probability
$F_{\mathrm{succ}}$ in the presence of measurement shot noise, and we analyze
its scaling with the problem size $L$. As expected, we find exponential
scalings in the form $n_{\mathrm{calls}}^{*}\propto 2^{kL}$, and we determine
the exponents $k$ considering different setups, including energy-based versus
gradient-based classical optimizers in both VQE and QAOA, different circuit
depths $d$, as well as random and annealing-inspired parameters
initializations in QAOA.

The first result of this Article is that VQE shows a very poor scaling with
problem size $L$. When an energy-based optimizer is adopted, the scaling is
not better than direct enumeration of the whole computational space, which
corresponds to $k=1$. Introducing additional noise due to simulated hardware
errors does not significantly affect the scaling compared to the error-free
case. Notice that our results are not in contrast with existing literature on
the use of VQE for classical cost functions [38, 31, 32, 33, 34], since these
studies report results in the regimes where $M\approx 2^{L}$ or
$n_{\mathrm{calls}}>2^{L}$. We also find that a gradient-based optimization,
which we implement in VQE via the parameters shift rule, is useful, leading up
to a quadratic speedup compared to the energy-based optimizer COBYLA.

Notable findings are obtained also for QAOA. The presence of the problem
Hamiltonian in the circuit leads to a functional optimization: the energy
landscape $f(x)$ is effectively queried in superposition, and by adjusting the
QAOA parameters one can create an interference pattern that enables the global
minima to be sampled more frequently than by uniform random choice. However,
the question we want to answer here is practical: how many total circuit
executions does QAOA need as the problem size increases, while maintaining a
fixed success probability? In contrast to most of the QAOA literature, we keep
in consideration that the cost function needs to be stochastically evaluated,
and in realistic conditions one can afford only $M\ll 2^{L}$ samples.

We first adopt a textbook version of QAOA, where we optimize the parameters
from scratch, i. e., starting from random initial values. While, as expected,
the total computation complexity is exponential, the exponent $k$ is sizeably
reduced compared to the full state enumeration. Notice that the performance
degradation with the system size at fixed quantum resources
$n_{\mathrm{calls}}$ is not due here to hardware noise [21], but to the
intrinsic quantum measurement shot noise, a crucial ingredient which is often
overlooked and usually leads to over-optimistic expectations for quantum
algorithms [54, 44]. Notice also that our numerical findings are compatible
with [55], which discusses the query complexity of variational algorithms but
only in the vicinity of the global minimum.

With the energy-based optimizer COBYLA, the QAOA scaling exponents turn out to
be $k\simeq 0.4$ for the ferromagnetic problem, and in the range $0.5<k<0.8$
for the disordered models; the circuit depth does not significantly affect the
scaling. As opposed to the VQE case, adopting a gradient-based optimization
does not sizeably change $k$. Furthermore, a third optimizer, the SPSA
algorithm, provides compatible results. These scaling exponents can be used to
estimate the hypothetical runtimes required to execute the QAOA algorithm on
physical quantum devices for realistic problem sizes. Assuming the best-
observed scenario of the ferromagnetic case, $n_{\mathrm{calls}}=1\times
2^{0.31\cdot L}$, some consequential bounds can be provided. For example,
considering the circuit depth $d=2$, gate execution time
$t_{\mathrm{gate}}=10$ ns for the NISQ era (best case scenario here), one
obtains runtimes of about tens of seconds for a hypothetical problem size
$L=100$, and a time much beyond the age of universe already for $L=500$. These
quotes need to be contrasted with tens of milliseconds of total CPU time of
simulated annealing [56], or minutes for exact algorithms [5] for $L=500$. To
achieve a runtime of order 10 ms (resp. minutes), for $L=500$, QAOA should
achieve a scaling exponent of about $k=0.04$ (resp. $0.07$). We conclude that
even the best-case scenario observed for the ferromagnetic model is
insufficient to provide practical advantage relatively to classical methods or
at least feasible absolute times.

Our numerical experiments are consistent with a very recent hardware
assessment of QAOA versus quantum annealing, which shows that a $d=2$ QAOA
circuit, while better than random sampling, delivers worse performance than
annealing [22]. However, it should be pointed out that, in that large-scale
experiment, the performance metric cannot be defined in terms of success
probability, since QAOA never provides the exact solution, nor approximate
solutions qualitatively comparable with those of simulated or quantum
annealing. This is again consistent with our picture. Moreover, our findings
are not in contrast with other previous numerical [23] or experimental QAOA
[20] studies, which are either presented in the $n_{\mathrm{calls}}>2^{L}$
regime or use a bootstrapping method to initialize the parameters.

To recover an effective algorithm, it is crucial to use a smart initialization
of the QAOA parameters. Indeed, our results show that smart initialization
allows one to effectively exploit deeper circuits, systematically increasing
the success probability. In fact, for the simple testbed models we consider,
the parameter values given by the annealing-inspired schedule turn out to be
very close to the optimal values, such that QAOA provides excellent success
probabilities without the need for further parameter optimization. Instead,
when QAOA is started from random parameters the classical optimization loop is
unable to systematically improve the ansatz in the physical regime $M\ll
2^{L}$. Interestingly, the same linear schedule proposed in [57] for MaxCut
problems, based on noise-free simulations, turns out to be suitable also for
our ferromagnetic and disordered Ising chains in the presence of measurement
shot noise. While one cannot associate a specific scaling exponent to the
smartly-initialized QAOA algorithm, as, fortunately, in this case the scaling
does improve with the circuit depth, it is quite plausible that sufficiently
deep circuits can reach feasible computational times for practically relevant
problem sizes.

It is worth remembering that the proposal to use a smart initialization of the
QAOA parameter is not new [26, 53, 29]. However, our findings show that this
choice should not only be considered as a good practice to marginally enhance
the algorithm efficiency, but it is the only route to make the algorithm
practical in the presence of shot noise. Indeed, if one performs (noise-free)
state-vector emulations of the optimization run, good parameters can be
recovered anyway, irrespective of the initialization [26, 53, 29].

Overall, we suggest that future implementation of QAOA should at least rethink
the use of the outer optimization loop, focusing in particular on smart
parameter initializations. While in this manuscript we adopt an annealing-
inspired initialization, more flexible solutions, suitable for shallower
circuits, are possible. In general, the angle array can be re-parametrized as
$\boldsymbol{\theta}\rightarrow\boldsymbol{\theta}(\boldsymbol{\alpha})$,
using a smaller number of optimizable parameters $\boldsymbol{\alpha}$. This
might allow performing fewer optimization steps, similar to the Fourier re-
parametrization of [26]. The research concerning pre-optimization is very
active. For instance, the QAOA smart initialization has been studied for the
Sherrington-Kirkpatrick model [58] and the MaxCut problem [28, 59, 60].
Moreover, the experimental results achieved in the studies cited above have
been analytically confirmed in [61]. Note that the issue of shot noise is
well-known in VQE for genuine many-body quantum Hamiltonians, for example, in
chemistry [54]. However, the fact that it also manifests so severely in the
case of a classical cost function, which can be measured in a single basis, is
important.

We expect our findings to apply in general to variational quantum algorithms
strongly relying on a classical optimization loop, but not to other
alternatives for quantum-enhanced optimization on digital hardware, including
quantum-powered sampling [62, 63], branch-and-bound algorithm [64], and
quantum-walks [65], to name a few proposals. On a methodological note, these
results demonstrate the importance of simple and controllable models to
analyze the scaling properties of quantum algorithms in realistic settings.

We acknowledge useful discussion with G. Carleo regarding the relation between
QAOA and quantum annealing. We thank A. Miessen and C. Cozza for helping us
set up the Qiskit simulation on the cluster. Computation for the work
described in this paper was supported by the Science Cluster at the University
of Zurich. G. S. acknowledges the hospitality of the Institute for
Computational Science at the University of Zurich and useful discussions with
E. Costa. G. M. acknowledges financial support from the Swiss National Science
Foundation. N. A is funded by the Swiss National Science Foundation, grant
number: PP00P2_176877. S. P. acknowledges PRACE for awarding access to the
Fenix Infrastructure resources at Cineca, which are partially funded by the
European Union’s Horizon 2020 research and innovation program through the ICEI
project under Grant Agreement No. 800858. This work was also partially
supported by the PNRR MUR project PE0000023-NQSTI.

##  Appendix A VQE with hardware errors

In this appendix, we inspect the possible role of hardware errors. For this, a
custom model of hardware noise is introduced, using the open-source Qiskit API
[45]. A realistic model is obtained, e. g., considering the thermal relaxation
due to the qubit environment. Each qubit is then parameterized by a thermal
relaxation time constant $T_{1}=50\,\upmu$s and a dephasing time constant
$T_{2}=70\,\upmu$s.

Figure 10: Minimal number of function calls $n_{\mathrm{calls}}^{*}$ as a
function of the problem size $L$, for different $F_{\mathrm{succ}}$. VQE
circuits with $d=2$ blocks are considered, both with (empty symbols) and
without (full symbols) simulated hardware errors, addressing ferromagnetic
chains. The thick dashed (red) line represents the scaling
$n_{\mathrm{calls}}^{*}\sim 2^{L}$ corresponding to the exact enumeration.
Thin continuous and dashed lines represent fitting functions of the form
$n_{\mathrm{calls}}^{*}=a2^{kL}$, and the fitting parameters $a$ and $k$,
obtained considering the large $L$ data, are given in the legend.

The performance comparison against the error-free VQE circuits is shown in
figure 10. Ferromagnetic chains are considered, using the CVaR estimator. It
turns out that the scaling of $n_{\mathrm{calls}}^{*}$ with $L$ is not
significantly affected by this simulated hardware noise.

##  Appendix B QAOA with SPSA

Figure 11: Scaling of $n_{\mathrm{calls}}^{*}$ for various depths $d$, CVaR
sample fractions $R$ and SPSA proposal lengths $W$. Three curves (from
transparent to solid) show $n_{\mathrm{calls}}^{*}$ for
$F_{\mathrm{succ}}=0.25,\,0.5$ and $0.75$, respectively. The colors indicate
different depths $d=2$ (blue), $d=3$ (green) and $d=4$ (purple). The numbers
$(a,k)$ in the brackets in the legends give the optimal values of the
exponential fit $n_{\mathrm{calls}}^{*}=a\,2^{kL}$ obtained by fitting the
data in the regime $L\geqslant 8$.

In this appendix, we analyse the computational scaling using an energy-based
optimizer alternative to COBYLA, namely, the SPSA algorithm [50]. This is used
to optimize QAOA circuits of depth in the range $2\leqslant d\leqslant 4$. The
testbed we consider here is the ferromagnetic Ising chain, corresponding to
setting $J_{j,j+1}=+1$ in (1).

In the SPSA algorithm, at each optimization step, a random uniformly-
distributed $n_{\mathrm{par}}$ parameters shift with a constrained length is
applied:
$\boldsymbol{\theta}\to\boldsymbol{\theta}+\Delta\boldsymbol{\theta}$, with
$\|\Delta\boldsymbol{\theta}\|\leqslant W$. We consider three values of this
maximum norm, namely: $W=0.01,$ $0.03$ and $0.06$. The shift vector is
generated as a random vector on a $n_{\mathrm{par}}$-dimensional unit sphere,
normalized to length $W$. We accept the new parameters if the cost function
decreases. As the cost function, we use the CVaR with either 25 % or 100 % of
the best-energy samples.

To obtain the optimal $n_{\mathrm{calls}}^{*}$, we use a procedure similar to
the one used in section 3. We consider optimization with $M$ samples generated
at each SPSA step, and optimize until $F_{\mathrm{succ}}$ reaches the target
value. We then compute $n_{\mathrm{calls}}^{*}=\min\,\left(M\times
n_{\mathrm{iter}}\right).$ The initial parameters are uniform random values in
the range $\theta_{n}\in(-1.0,1.0)$, and the results for
$n_{\mathrm{calls}}^{*}$ are obtained by averaging over 1000 simulations with
random starting points. The results are presented in figure 11.

Notably, we observe that the scaling sizeably worsens as $d$ increases from
$2$ to $4$. This could be attributed to a more complex optimization landscape
which requires a higher $M$ or $n_{\mathrm{calls}}$ to approach the global
minimum. At the same time, the ansatz with $d=2$ reaches the $k\simeq 0.5$
scaling, therefore it features a quadratic speed-up compared with the scaling
of the COBYLA-driven VQE optimization, as also found with the QAOA algorithm,
driven either by COBYLA or by the gradient-based optimizer.

## References

## References

  * [1] Feynman R P 1982 Int. J. Theor. Phys. 21 467–488 ISSN 1572-9575 URL https://doi.org/10.1007/BF02650179
  * [2] Nielsen M A and Chuang I L 2010 Quantum Computation and Quantum Information: 10th Anniversary Edition (Cambridge University Press)
  * [3] Kirkpatrick S, Gelatt C D and Vecchi M P 1983 Science 220 671–680 URL https://www.science.org/doi/10.1126/science.220.4598.671
  * [4] Johnson M W, Amin M H, Gildert S, Lanting T, Hamze F, Dickson N, Harris R, Berkley A J, Johansson J, Bunyk P et al. 2011 Nature 473 194–198 URL https://doi.org/10.1038/nature10012
  * [5] Boixo S, Rønnow T F, Isakov S V, Wang Z, Wecker D, Lidar D A, Martinis J M and Troyer M 2014 Nat. Phys. 10 218–224 URL https://doi.org/10.1038/nphys2900
  * [6] Rønnow T F, Wang Z, Job J, Boixo S, Isakov S V, Wecker D, Martinis J M, Lidar D A and Troyer M 2014 Science 345 420–424 URL https://doi.org/10.1126/science.1252319
  * [7] Denchev V S, Boixo S, Isakov S V, Ding N, Babbush R, Smelyanskiy V, Martinis J and Neven H 2016 Phys. Rev. X 6 031015 URL https://doi.org/10.1103/PhysRevX.6.031015
  * [8] Albash T and Lidar D A 2018 Phys. Rev. X 8(3) 031016 URL https://link.aps.org/doi/10.1103/PhysRevX.8.031016
  * [9] Isakov S V, Mazzola G, Smelyanskiy V N, Jiang Z, Boixo S, Neven H and Troyer M 2016 Phys. Rev. Lett. 117 180402 URL https://doi.org/10.1103/PhysRevLett.117.180402
  * [10] Mazzola G, Smelyanskiy V N and Troyer M 2017 Phys. Rev. B 96(13) 134305 URL https://link.aps.org/doi/10.1103/PhysRevB.96.134305
  * [11] Inack E M, Giudici G, Parolini T, Santoro G and Pilati S 2018 Phys. Rev. A 97(3) 032307 URL https://link.aps.org/doi/10.1103/PhysRevA.97.032307
  * [12] Parolini T, Inack E M, Giudici G and Pilati S 2019 Phys. Rev. B 100(21) 214303 URL https://link.aps.org/doi/10.1103/PhysRevB.100.214303
  * [13] Ozfidan I, Deng C, Smirnov A, Lanting T, Harris R, Swenson L, Whittaker J, Altomare F, Babcock M, Baron C et al. 2020 Phys. Rev. Applied 13 034037 URL https://doi.org/10.1103/PhysRevApplied.13.034037
  * [14] King A D, Suzuki S, Raymond J, Zucca A, Lanting T, Altomare F, Berkley A J, Ejtemaee S, Hoskinson E, Huang S et al. 2022 Nat. Phys. 18 1324–1328 URL https://doi.org/10.1038/s41567-022-01741-6
  * [15] Peruzzo A, McClean J, Shadbolt P, Yung M H, Zhou X Q, Love P J, Aspuru-Guzik A and O’Brien J L 2014 Nat. Commun. 5 4213 URL https://doi.org/10.1038/ncomms5213
  * [16] Cerezo M, Arrasmith A, Babbush R, Benjamin S C, Endo S, Fujii K, McClean J R, Mitarai K, Yuan X, Cincio L et al. 2021 Nat. Rev. Phys. 3 625–644 URL https://doi.org/10.1038/s42254-021-00348-9
  * [17] Farhi E, Goldstone J and Gutmann S 2014 A quantum approximate optimization algorithm (Preprint 1411.4028)
  * [18] Barahona F 1982 J. Phys. A: Math. Gen. 15 3241 URL https://dx.doi.org/10.1088/0305-4470/15/10/028
  * [19] Rønnow T F, Wang Z, Job J, Boixo S, Isakov S V, Wecker D, Martinis J M, Lidar D A and Troyer M 2014 Science 345 420–424 URL https://www.science.org/doi/abs/10.1126/science.1252319
  * [20] Pagano G, Bapat A, Becker P, Collins K S, De A, Hess P W, Kaplan H B, Kyprianidis A, Tan W L, Baldwin C, Brady L T, Deshpande A, Liu F, Jordan S, Gorshkov A V and Monroe C 2020 Proc. Natl. Acad. Sci. 117 25396–25401 URL https://www.pnas.org/doi/abs/10.1073/pnas.2006373117
  * [21] Harrigan M P, Sung K J, Neeley M, Satzinger K J, Arute F, Arya K, Atalaya J, Bardin J C, Barends R, Boixo S et al. 2021 Nat. Phys. 17 332–336 URL https://doi.org/10.1038/s41567-020-01105-y
  * [22] Pelofske E, Bärtschi A and Eidenbenz S 2023 Quantum annealing vs. QAOA: 127 qubit higher-order Ising problems on NISQ computers High Performance Computing ed Bhatele A, Hammond J, Baboulin M and Kruse C (Cham: Springer Nature Switzerland) pp 240–258 ISBN 978-3-031-32041-5
  * [23] Guerreschi G G and Smelyanskiy M 2017 Practical optimization for hybrid quantum-classical algorithms (Preprint 1701.01450)
  * [24] Hadfield S, Wang Z, O’Gorman B, Rieffel E, Venturelli D and Biswas R 2019 Algorithms 12 34 ISSN 1999-4893 URL http://dx.doi.org/10.3390/a12020034
  * [25] Guerreschi G G and Matsuura A Y 2019 Sci. Rep. 9 1–7 URL https://doi.org/10.1038/s41598-019-43176-9
  * [26] Zhou L, Wang S T, Choi S, Pichler H and Lukin M D 2020 Phys. Rev. X 10(2) 021067 URL https://link.aps.org/doi/10.1103/PhysRevX.10.021067
  * [27] Moussa C, Calandra H and Dunjko V 2020 Quantum Sci. Technol. 5 044009 URL https://dx.doi.org/10.1088/2058-9565/abb8e5
  * [28] Boulebnane S and Montanaro A 2021 Predicting parameters for the quantum approximate optimization algorithm for MAX-CUT from the infinite-size limit (Preprint 2110.10685)
  * [29] Willsch M, Willsch D, Jin F, De Raedt H and Michielsen K 2020 Quantum Inf. Process. 19 197 URL https://doi.org/10.1007/s11128-020-02692-8
  * [30] Binkowski L, Koßmann G, Ziegler T and Schwonnek R 2023 Elementary proof of QAOA convergence (Preprint 2302.04968)
  * [31] Barkoutsos P K, Nannicini G, Robert A, Tavernelli I and Woerner S 2020 Quantum 4 256 ISSN 2521-327X URL https://doi.org/10.22331/q-2020-04-20-256
  * [32] Díez-Valle P, Porras D and García-Ripoll J J 2021 Phys. Rev. A 104(6) 062426 URL https://link.aps.org/doi/10.1103/PhysRevA.104.062426
  * [33] Amaro D, Modica C, Rosenkranz M, Fiorentini M, Benedetti M and Lubasch M 2022 Quantum Sci. Technol. 7 015021 URL https://dx.doi.org/10.1088/2058-9565/ac3e54
  * [34] Zoufal C, Mishmash R V, Sharma N, Kumar N, Sheshadri A, Deshmukh A, Ibrahim N, Gacon J and Woerner S 2023 Quantum 7 909 URL https://doi.org/10.22331/q-2023-01-26-909
  * [35] Kolotouros I and Wallden P 2022 Phys. Rev. Res. 4(2) 023225 URL https://link.aps.org/doi/10.1103/PhysRevResearch.4.023225
  * [36] Liu X, Angone A, Shaydulin R, Safro I, Alexeev Y and Cincio L 2022 IEEE Trans. Autom. Sci. Eng. 3 1–20 URL https://doi.org/10.1186/s41313-021-00032-6
  * [37] Chakrabarti S, Krishnakumar R, Mazzola G, Stamatopoulos N, Woerner S and Zeng W J 2021 Quantum 5 463 ISSN 2521-327X URL https://doi.org/10.22331/q-2021-06-01-463
  * [38] Robert A, Barkoutsos P K, Woerner S and Tavernelli I 2021 Npj Quantum Inf. 7 38 URL https://doi.org/10.1038/s41534-021-00368-4
  * [39] Harwood S, Gambella C, Trenev D, Simonetto A, Bernal D and Greenberg D 2021 IEEE Trans. Autom. Sci. Eng. 2 1–17 URL https://doi.org/10.1109/TQE.2021.3049230
  * [40] Wang X, Song Z and Wang Y 2021 Quantum 5 483 ISSN 2521-327X URL https://doi.org/10.22331/q-2021-06-29-483
  * [41] Braine L, Egger D J, Glick J and Woerner S 2021 IEEE Trans. Autom. Sci. Eng. 2 1–8 URL https://doi.org/10.1109/TQE.2021.3063635
  * [42] Arute F, Arya K, Babbush R, Bacon D, Bardin J C, Barends R, Biswas R, Boixo S, Brandao F G, Buell D A et al. 2019 Nature 574 505–510 URL https://www.nature.com/articles/s41586-019-1666-5
  * [43] Gidney C and Fowler A G 2019 Quantum 3 135 ISSN 2521-327X URL https://doi.org/10.22331/q-2019-04-30-135
  * [44] Mazzola G and Carleo G 2022 Exponential challenges in unbiasing quantum Monte Carlo algorithms with quantum computers (Preprint 2205.09203)
  * [45] Anis Sajid M et al. 2021 Qiskit: An open-source framework for quantum computing
  * [46] Weidenfeller J, Valor L C, Gacon J, Tornow C, Bello L, Woerner S and Egger D J 2022 Quantum 6 870 ISSN 2521-327X URL https://doi.org/10.22331/q-2022-12-07-870
  * [47] Mitarai K, Negoro M, Kitagawa M and Fujii K 2018 Phys. Rev. A 98(3) 032309 URL https://link.aps.org/doi/10.1103/PhysRevA.98.032309
  * [48] Schuld M, Bergholm V, Gogolin C, Izaac J and Killoran N 2019 Phys. Rev. A 99(3) 032331 URL https://link.aps.org/doi/10.1103/PhysRevA.99.032331
  * [49] Holmes Z, Sharma K, Cerezo M and Coles P J 2022 PRX Quantum 3(1) 010313 URL https://link.aps.org/doi/10.1103/PRXQuantum.3.010313
  * [50] Spall J 1998 IEEE Trans. Aerosp. Electron. Syst. 34 817–823 URL https://doi.org/10.1109/7.705889
  * [51] Wierichs D, Izaac J, Wang C and Lin C Y Y 2022 Quantum 6 677 ISSN 2521-327X URL https://doi.org/10.22331/q-2022-03-30-677
  * [52] Liu H Y, Chen Z Y, Sun T P, Xue C, Wu Y C and Guo G P 2023 Can variational quantum algorithms demonstrate quantum advantages? Time really matters (Preprint 2307.04089)
  * [53] Sack S H and Serbyn M 2021 Quantum 5 491 ISSN 2521-327X URL https://doi.org/10.22331/q-2021-07-01-491
  * [54] Wecker D, Hastings M B and Troyer M 2015 Phys. Rev. A 92(4) 042303 URL https://link.aps.org/doi/10.1103/PhysRevA.92.042303
  * [55] Harrow A W and Napp J C 2021 Phys. Rev. Lett. 126(14) 140502 URL https://link.aps.org/doi/10.1103/PhysRevLett.126.140502
  * [56] Isakov S, Zintchenko I, Rønnow T and Troyer M 2015 Comput. Phys. Commun. 192 265–271 ISSN 0010-4655 URL https://www.sciencedirect.com/science/article/pii/S0010465515000727
  * [57] Brandao F G S L, Broughton M, Farhi E, Gutmann S and Neven H 2018 For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances (Preprint 1812.04170)
  * [58] Farhi E, Goldstone J, Gutmann S and Zhou L 2022 Quantum 6 759 ISSN 2521-327X URL https://doi.org/10.22331/q-2022-07-07-759
  * [59] Galda A, Liu X, Lykov D, Alexeev Y and Safro I 2021 Transferability of optimal QAOA parameters between random graphs 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) pp 171–180 URL https://doi.org/10.1109/QCE52317.2021.00034
  * [60] Egger D J, Mareček J and Woerner S 2021 Quantum 5 479 ISSN 2521-327X URL https://doi.org/10.22331/q-2021-06-17-479
  * [61] Akshay V, Rabinovich D, Campos E and Biamonte J 2021 Phys. Rev. A 104(1) L010401 URL https://link.aps.org/doi/10.1103/PhysRevA.104.L010401
  * [62] Mazzola G 2021 Phys. Rev. A 104(2) 022431 URL https://link.aps.org/doi/10.1103/PhysRevA.104.022431
  * [63] Layden D, Mazzola G, Mishmash R V, Motta M, Wocjan P, Kim J S and Sheldon S 2023 Nature 619 282–287 URL https://doi.org/10.1038/s41586-023-06095-4
  * [64] Montanaro A 2020 Phys. Rev. Research 2(1) 013056 URL https://link.aps.org/doi/10.1103/PhysRevResearch.2.013056
  * [65] Callison A, Chancellor N, Mintert F and Kendon V 2019 New J. Phys. 21 123022 URL https://dx.doi.org/10.1088/1367-2630/ab5ca2