Quantum Optimization (with IBM Quantum)

1. 00:00Hello everybody.
2. 00:01And welcome back to our course on quantum optimization.
3. 00:04What I want to do in this lecture is follow up on our extensions of QAOA.
4. 00:11In the previous one, we covered the recursive QAOA.
5. 00:15And what I want to do in this lecture is to go over warm start QAOA.
6. 00:23The intuition behind warm start is the following.
7. 00:25When you look at classical solvers, you will see that they are very efficient.
8. 00:30And one of the reasons why they can be so efficient is because they leverage relaxations to the problem.
9. 00:38What this means is that they solve an easier version of the hard combinatorial optimization problem.
10. 00:45And then they use that solution as a warm start to tackle the hard combinatorial optimization problem.
11. 00:55And what we do in warm start QAOA is we apply the same idea but to quantum algorithms.
12. 01:04So let's take a look at an example.
13. 01:07Let's suppose that we have a QUBO that we want to solve.
14. 01:11You can see its form given here.
15. 01:15And what we do is we relax this QUBO such that the decision variables now are no longer binary but become continuous.
16. 01:27And this makes the problem easier to solve.
17. 01:30For instance, if you take this small example with two decision variables, you can see that I go from a state space with discrete
18. 01:39solutions to a state space with continuous ones.
19. 01:42And I can then leverage gradients.
20. 01:44For instance, to find the minimum, you can see that this minimum in this particular instance is not too far away from the
21. 01:52true minimum.
22. 01:55And now if the quadratic program that we get out of this is convex, then we can efficiently solve it classically and get
23. 02:04a nice solution to warm start our quantum.
24. 02:06So let's take a look at the warm start QAOA and in particular the circuit.
25. 02:13So the first thing that we need to do is to solve this quadratic program which is a relaxation of our QUBO.
26. 02:21And this will give me a solution with values which are continuous in the interval zero
27. 02:27and one.
28. 02:28And what I can then do is I can create a quantum state that reflects this solution.
29. 02:34And I do this by applying Ry rotations on the ground state.
30. 02:39This means now that if you look at the QAOA circuit, it is no longer initialized with Hadamard gates here.
31. 02:47Instead we have these Ry rotations which corresponds to the initial state given by the relaxation.
32. 02:56And so the rotation angles here you can see are related to the solution of the relaxed problem.
33. 03:03Now what is important to keep in mind in QAOA is that the initial state should be the ground state of the
34. 03:11mixer operator.
35. 03:13And this means that if I take a look at my quantum circuit shown here, I also need to change the mixer operator to reflect
36. 03:21the warm start.
37. 03:23And this is what is done in this particular change here.
38. 03:26You can see that for one cubit, we change the mixer operator from an X gate to something a little bit different, something
39. 03:36that depends on the solution from the relaxation.
40. 03:41And so the solution from the relaxation here is this ci star.
41. 03:45And if you look at the ground state of this mixer, you will see that it corresponds to the initial state that we have started
42. 03:56our QAOA circuit with.
43. 03:58And so then the circuit that I'm showing you here is essentially what we call warm start QAOA. It corresponds to a change
44. 04:07of the initial state with a corresponding change in the mixer operator.
45. 04:13Just for completeness here, the circuit that we are showing is depth one warm start QAOA.
46. 04:21Now there is one subtlety that we need to keep in mind is that
47. 04:27let's suppose the following, if the solution to the relaxation c star is a continuous variable but doesn't take on the
48. 04:35values zero
49. 04:36and one, then I'm guaranteed to have some overlap between the initial state and the optimal solution that I want to find.
50. 04:45And this then means that through the adiabatic theorem, the warm start will converge to the optimal solution that I am trying
51. 04:55to find.
52. 04:56However, if there are some of the relaxed variables that have as solution, either a zero or a one, then you will see that
53. 05:08warm start QAOA may not converge to the ground state
54. 05:12if the ideal solution has a different value from the warm start.
55. 05:18As example, let's say that the relaxed variable number two gave a value of zero.
56. 05:24But in fact, the optimal solution as a value of one, then we will not converge.
57. 05:29And the way that we overcome this is by imposing a regularization constraint.
58. 05:35So this means then that if a value is either zero or one, I will then change its value to the interval epsilon one minus
59. 05:44epsilon.
60. 05:45And this then guarantees to me that there is some overlap between the initial state and the ideal solution.
61. 05:53And what is very interesting in this case also is that it gives me a parameter that allows me to continuously change from
62. 06:02warm start to standard QAOA.
63. 06:05More specifically, if I set epsilon equal 0.5, then I recover the standard QAOA.
64. 06:13Now I want to give an example of warm start QAOA and how it performs in practice.
65. 06:19And for this, we will look at portfolio optimization which is an example that has already been introduced in the first lecture.
66. 06:26What we want to do is we want to maximize the return of a set of assets and minimize the risk.
67. 06:34The x values here, our decision variables, they can be either zero or one, either the asset is in the portfolio or it is
68. 06:43not. The variable q here allows me to trade off risk and return.
69. 06:48And finally, I impose myself a budget constraint, namely I only want to invest in B assets. Maybe for instance, I have six
70. 06:56assets and I only want to invest in three of them, but I need to find the best three assets for me.
71. 07:05So let's take a look at how warm start QAOA performs
72. 07:09in comparison to Standard QAOA. We have two charts for this.
73. 07:13On the X axis, we have the QAOA depth P.
74. 07:19And then on the top chart here on the Y axis, we have the probability to sample the optimal state after the optimization
75. 07:29of the beta and gamma perimeters.
76. 07:32So a higher value here means that we have a higher likelihood of sampling the optimal solution.
77. 07:39And then on the second plot down below, we show the energy on the Y axis.
78. 07:44So this shows us how well our QAOA is doing in the optimization. Ideally, we would like to see low values for
79. 07:52the energy.
80. 07:54So what we can see in the top plot is that for standard QAOA, there is a relatively low probability of sampling
81. 08:03the optimal solution.
82. 08:04However, when you use a warm start leveraging a relaxation of the problem,
83. 08:10you can see that this probability increases quite dramatically.
84. 08:13So this means the warm start here is able to bias us towards good solutions for this problem.
85. 08:21Similarly, if you look at the energy, you will see that warm start can arrive at lower energies with less depth.
86. 08:29This then shows that warm starting is also a way that we can use to save quantum resources.
87. 08:36And this is important because the gate fidelities are not perfect and the cubits have a finite T one and T two.
88. 08:45Now as a sanity check, what you can also do is you can warm start your circuit from an initial state obtained from a relaxation
89. 08:54but do not change the mixer.
90. 08:57And if you do that you have an inconsistency in the circuit, and this is very nicely illustrated by this blue curve here.
91. 09:05What we are doing in this blue curve is something inconsistent.
92. 09:09We have the initial state from the warm start, but we do not adapt to the mixer.
93. 09:13And if you do this, you will see that the energy doesn't nicely converge to the lowest value as indicated by the dashed line.
94. 09:22And then the probability of sampling the optimal state is also somewhat more erratic.
95. 09:27You can also see that there is a larger standard deviation on the different instances.
96. 09:33So this brings me towards the end of this lecture on warm starting QAOA. I presented one way through which you can
97. 09:43warm start QAOA, namely through quadratic program relaxations.
98. 09:47But there is in fact many different ways that we can do this.
99. 09:51For instance, if you're dealing with a MaxCut problem, you might want to use a relaxation based on a semi definite program,
100. 09:59which is what the Goemans Williamson randomized rounding algorithm does.
101. 10:04So what is important to keep in mind here is that there are many different ways through which we can warm start QAOA.
102. 10:10And this particular example shown here is only one of them.
103. 10:15Thank you.

To enable the transcript, please select a language in the video player settings menu.