Lab 2: Variational Algorithms
In this lab, you will learn how to create and work with parameterized quantum circuits and quadratic programs, and how to solve optimization problems using the Quantum Approximate Optimization Algorithm.
Graded Exercise 2-1: MaxCut
Graded Exercise 2-2: MaxCut to Quadratic Program
Graded Exercise 2-3: Quantum Approximate Optimization Algorithm
Graded Exercise 2-4: Conditional Value at Risk
Lab Tips / Hints
Exercise 1: For any given cut, think of the scenario when an edge E would contribute to the cut value -- either of its vertices have to belong to different sets. Intuitively, it follows that the weight of an edge is added to the cut value only if the bits corresponding to its vertices in the given bitstring are not identical. After generating the histogram showing the cut value for all possible n-bit strings, the bitstring with the maximum cut value should be your max-cut.
Exercise 2: Create a general QUBO cost function with QUBO Matrix Q = -W (negation of the weight matrix) and QUBO Vector c = sum of all entries in each row of the weight matrix W. Use binary optimisation variables in Quadratic Program and maximise it.
Exercise 3: For each layer i of p, use the following expression: [Image: Screenshot 2021-08-06 at 4.10.10 AM.png] Use RZ, RZZ and RX gates to the expressions in their corresponding brackets as shown in the image above. While applying RZZ gates to Qjk, make sure that j is not equal to k else it would make it a single qubit and entanglement would not make sense. You can check how the final circuit looks like using the draw() function.
Exercise 4: Do not forget to order the cut-values Ci in decreasing order! Simply get the number of best cuts n that are to be considered for our optimisation process by multiplying the number of shots by alpha. The top n cuts would be the first n Ci. Finally, calculate the energy.
Please refer to the doc here (https://cdn.discordapp.com/attachments/866843353408995328/867471161255919666/Lab2_hints.pdf). It contains a lot of additional useful hints.
FAQ (Exercise 1 & 2)
Is trajectory like a log of different parameters that have been tried?
Yes, the trajectory tracks the parameters and corresponding energies of the optimization process
How do we know that a _higher_ energy level isn't reached at a bigger depth?
Since we only enlarge the space of quantum states that we optimise over, the global optimum is actually guaranteed to get better with increasing depth. However, since we introduce more parameters when increasing the depth it also becomes more difficult to actually find this optimum.
My histogram looks correct but the grade won't accept the bitstring I obtained? (Ex 1)
The figure displaying the cut values for different bistrings is scrollable and part of the graph might be hidden, so make sure to scroll all the way to the right to see the optimal bitstring.
Why do I get the error "`Variable name already exists: x_0`"? (Ex 2)
This error indicates that you have not initialized the quadratic program in your function. The function will then attempt to add binary variables to the quadratic program defined in the code above this exercise which leads to the error above.
I believe that my code is correct and the quadratic program looks correct when I print it, but the grader still fails. Why? (Ex 2)
Are you sure you're maximizing your objective function?
FAQ (Exercise 3)
Which gates do I need to use to implement this circuit?
You will need to use the RZ, RX, and RZZ gates that are part of Qiskits gate library.
You can also use the decomposed version of RZZ gates shown in the circuit diagram. In that case you will also need the CNOT called CX in Qiskit.
On RZZ gates, which one is the control and which one is the target qubit?
These gates are symmetrical, so they are interchangeable.
Why does the circuit diagram in this exercise contain CNOT gates?
The RZZ gates in this circuit diagram have each been decomposed into a combination of two CNOT gates and an RZ gate.
My circuit looks correct but the grader does not accept it. Why?
Your circuit is most likely not correct. Remember to print the circuit and check:
The angles of the RZ gates --> On MaxCut they should be 0
The angles of the RZZ gates --> Do they match the reference circuit? Remember that each block CNOT-RZ-CNOT in the reference corresponds to a RZZ gate in your implementation
Why are the expressions for the gate angles given in the lab different from those given in the lecture?
The slides for the corresponding lecture contain a typo and are missing a factor of 2. To make sure that you pass the exercise, please use the expressions given in the Lab.
Why do the angles for my RZ gates evaluate to 0?
Note that in the special case of MaxCut that we consider in this Lab, the angles for the corresponding RZ gates in the QAOA circuit always evaluate to 0. So if your RZ angles are equal to 0, this is not a mistake and means that you calculated them correctly. This is also why the RZ gates are missing in the QAOA circuit diagram of this exercise.
Even when using the expressions from the lab, my angles seem to be off by a factor of 2. Why is that?
For calculating the angles for RZZ gates, make sure to sum correctly over qubit pairs. Note that in the equation given in the lab, we sum operators over all possible pairs i,j where i!=j. If in your code you only loop over j<i, you will only apply half of these gates, and therefore you will have to use twice the angle. This works because our matrix Q is symmetric, and therefore the following holds:
RZ_iZ_j(Q_ij) = RZ_iZ_j(1/2 Q_ij) + RZ_jZ_i(1/2 Q_ji)
So either you have to apply both gates on the right hand side of this equation or just the gate on the left but with double the angle.
I get an error related to the qubo object passed to the qaoa_circuit function
I get the error "`AttributeError: ... object has no attribute 'variables'`"
I have tried all of the above and still get an error?
This exercise makes use of your solution for exercise 2. If you get an error that seems to be related to the quadratic program and you are confident that you are constructing the circuit correctly, check your code for exercise 2.
FAQ (Exercise 4)
I get the error "`ValueError: Mismatching number of values and parameters. For partial binding please pass a dictionary of {parameter: value} pairs.`" Why?
This exercise makes use of your solution for exercise 3. The error indicates that the circuit you constructed does not contain the right amount of parameters (for depth p=1 it should include two parameters, beta and gamma). Note that sometimes the grader for exercise 3 can accept submissions that are slightly wrong.
My solution to exercise 3 passed the grader, but my solution to exercise 4 is not passing. Why?
This exercise makes use of your solutions for the previous exercises. There is a chance that your submissions for these exercises passed without being totally correct. Please review your solutions for the previous exercises (see tips above).
Suggested resources
