Quantum Optimization (with IBM Quantum)

1. 00:00Hi and welcome back to our course on quantum optimization.
2. 00:03Today, we're gonna be learning how to map QUBO problems which you learned about in the last lecture to ground state problems
3. 00:09which is what we can solve on quantum computers.
4. 00:11So let's briefly review QUBO problems.
5. 00:14You learned that the acronym stands for a quadratic unconstrained binary optimization.
6. 00:18The name in itself already provides a lot of information, but let's go through each of the words.
7. 00:22So quadratic tells us that our cost function will have at most an order of two.
8. 00:28So here the optimization variables are X and we can see that here is the quadratic term we have labeled the cost function as
9. 00:33c. Then unconstrained tells us that the variables will have no constraints.
10. 00:38Binary means they will take values in either zero or one.
11. 00:42An optimization tells us that the problem will be either a minimization problem or a maximization problem.
12. 00:47Here, I have chosen a minimization problem for the example.
13. 00:51This is typically what we see, but they can be easily mapped to each other.
14. 00:56As an example,
15. 00:57let's take MaxCut which he also briefly saw in the last lecture as a reminder graphs are composed of nodes and edges which
16. 01:05connect them.
17. 01:06And the goal of MaxCut is to partition the notes into two groups such that the number of edges connecting the nodes between
18. 01:13the two groups is maximized.
19. 01:15This is equivalent to choosing a path or cut that maximizes the number of edges it crosses.
20. 01:20This is why we call it MaxCut, because it is maximum cut.
21. 01:24We can easily design this as a binary problem by leveling each of the groups zero or one.
22. 01:29And then each of the variables becomes binary immediately.
23. 01:34We can also make the problem more complex by assigning weights to the edges.
24. 01:38So here, for example, we can design it and write it in the matrix.
25. 01:43So for example, between node zero and node one, we would take row zero column one and write one, which is the weight in the
26. 01:51matrix.
27. 01:51And notice that the matrix will be symmetric because we can also see that the edge is not directed.
28. 01:57So also from node one,
29. 01:59so row one column zero, we will also see a weight of one.
30. 02:04Similarly, for example, between node one and node two, we will have row one, column two and we will write a weight of three
31. 02:14and we will do this for all the weights and end up with the symmetric matrix.
32. 02:19Once we have written it down in this form, we want to find a way to express it in a cost function that is a
33. 02:25QUBO problem.
34. 02:26So our cost function for max cut will be the following.
35. 02:30Let me go through each of the terms.
36. 02:32The first one is here.
37. 02:34So why is it like this?
38. 02:36Well, this is ensuring that only the edges between nodes of different groups contribute.
39. 02:42Because if Xi and Xj are either both zero or both one, then the overall term will be zero.
40. 02:49And notice that even though weights appear twice in the matrix, this will also ensure that we only get a contribution from
41. 02:55one of them.
42. 02:56Because if Xi is zero, then the term will also be zero.
43. 02:59So we will only get contributions when Xi is one and Xj is zero, the weight will then obviously account for the amount of contribution
44. 03:08of that edge.
45. 03:09And I also want to point out this minus sign which as I was talking about transforms what we had as a maximization problem,
46. 03:17so maximum cut to a minimization problem, which is the way that I have chosen to write it here.
47. 03:22Now we can multiply this out and to make it look like the cost function of a QUBO problem, we can make this substitution.
48. 03:30So here the QUBO matrix is trivially just the weight matrix but just to keep notation consistent, I wrote it down as Q and
49. 03:37then we have the QUBO vector defined like this.
50. 03:40And if we make the substitution, we can see that in matrix notation, this is exactly the form that we wanted. Now that we
51. 03:48have this written down as a QUBO problem,
52. 03:51why do we need it in this way?
53. 03:53How can we solve it on a quantum quantum computer?
54. 03:56Right.
55. 03:56So the key is that quantum computers require for us to formulate our problems as Hamiltonian problems.
56. 04:02What does this mean?
57. 04:03Well, first of all, let me review what Hamiltonians are.
58. 04:06So Hamiltonians are operators which describe the energy of a physical system.
59. 04:12What this will mean is that if age is applied to the state X and if X is an eigenstate of the system, then the
60. 04:20Eigen value equation will be satisfied and we will get back the energy of that state as an Eigen value.
61. 04:25So we can find the energy of any eigenstate by using the Hamiltonian.
62. 04:31The goal is to find a specific Hamiltonian which we call Hc.
63. 04:34So the cost Hamiltonian that encodes our function.
64. 04:37What does this mean?
65. 04:38Well, it solves this Eigen value equation.
66. 04:41So here the Eigen value is the value of the cost function for that particular X.
67. 04:47And what this will mean is that if we can find this cost Hamiltonian that encode C we can then use the Hamiltonian problem
68. 04:54with a quantum computer to minimize C and solve the optimization problem. How? By solving the ground state problem.
69. 05:01So we want to find the state which gives the minimum energy.
70. 05:04So we look through all the states find their energy and then we choose the minimum.
71. 05:10But now we've learned why we want to map it to a Hamiltonian.
72. 05:15But how about how we map it to a Hamiltonian?
73. 05:17So I've just added C here as a reminder.
74. 05:21And now let's go through the steps.
75. 05:22So first we want to map each of the optimization variables which were binary variables to what we call spin variables.
76. 05:29So instead of taking values in zero and one, they take values and -1 and 1.
77. 05:34And once we have made the substitution, then now we can promote them to probably spin operators.
78. 05:40This just means they satisfy this definition.
79. 05:44And this is exactly equivalent to the above.
80. 05:46Since for a binary variable X, you can see that if we substitute zero here, then both sides are one.
81. 05:53And if we substitute minus one, then both sides are minus one.
82. 05:56So this substitution is equivalent.
83. 05:58And once we have that, then we can just plug it in and we get this from plugging in each of the Xi Xj etcetera.
84. 06:08And now we can multiply this out.
85. 06:10And then by noticing that if Qij is symmetric, which we said it was because Q is equal to the weight matrix
86. 06:18And we said that that by design of the problem is symmetric then in this term, we can interchange i and j and work through
87. 06:25the math and find this form.
88. 06:27This is actually called an Ising Hamiltonian because of this spin spin interaction term.
89. 06:32Um That's the important term we can also have additional um linear terms like for QUBO problems
90. 06:38this is usually a set term. For some ising Hamiltonian also have like an x operator term or maybe a constant like here.
91. 06:46But especially it's important that we see this spin spin interaction term and Ising Hamiltonian are useful because they're
92. 06:52very well studied in physics and particularly methods in quantum into solve Ising Hamiltonian.
93. 06:59So we like to map them onto problems that look like this. As a summary,
94. 07:04we have seen that in combinatorial optimization, we often encounter these problems which have the QUBO structure.
95. 07:11And we've seen as an example, the MaxCut, we also saw that we can map these types of problems to Ising Hamiltonian so
96. 07:18that we can solve them on quantum computers.
97. 07:20And we did this by substituting our binary variables with spin variables and then promoting them to spin operators.
98. 07:27And this took our cost function to a cost Hamiltonian.
99. 07:31And once we have encoded our cost function in a Hamiltonian, so recall this means that this equation is satisfied, then we
100. 07:38can minimize our cost function.
101. 07:40So solve our optimization problem by solving the ground state problem.
102. 07:44That means finding the ground state of our system.
103. 07:46So essentially our final solution will correspond to the ground state of our system which we can solve on a quantum computer
104. 07:53Thank you so much for your attention.

Щоб увімкнути запис, виберіть мову в меню налаштувань відео.