Noisy QAOA | PennyLane Challenges

To attempt this challenge, please switch to a larger screen size.

Challenge statement

This challenge was part of the Canadian Quantum Cup 2023 coding competition.

The Quantum Approximate Optimization Algorithm (QAOA) has garnered widespread interest due to its ease of implementation and potential applications in combinatorial optimization. One of the problems that QAOA can tackle is known as the Minimum Vertex Cover. It consists of finding a set of vertices in a graph such that all of the edges in the graph are connected to one vertex in the set. See the image below for an example.

In this problem, we will solve the unconstrained Minimum Vertex Cover problem using QAOA for the following graph.

We remind you that the cost Hamiltonian for this problem is given by

H_{\text{cost}} = \frac{3}{4}\sum_{(i,j) \in \text{edges}}(Z_iZ_j +Z_i +Z_j) - \sum_{i \in \text{vertices}}Z_i

and that the mixer Hamiltonian is

H_{\text{mixer}} = \sum_{i \in \text{vertices}}X_i.

This seems simple enough, there's even a PennyLane tutorial that has already done this for us! But there's a catch. You are asked to implement the QAOA algorithm using only the qml.RX, qml.RX, qml.RZ and qml.CNOT gates. Moreover, every CNOT gate is noisy, which we model by adding a Depolarizing gate (qml.DepolarizingChannel) in the target qubit after each CNOT application. This also means that you will need to Trotterize the cost and mixer Hamiltonians. Please, work with a Trotterization depth equal to 1 and assume that all CNOT gates introduce the same amount of noise.

You will need to optimize the QAOA parameters to find the minimum expectation value of the cost Hamiltonian. Your task is to find the approximation ratio

r^{*} = \frac{\text{Minimum estimated by the noisy QAOA}}{\text{True minimum of the cost Hamiltonian}}

in terms of the noise parameter of the depolarization gate and the number of cost/mixer layers we use in QAOA, as shown below.

Challenge code

In the code below, you must complete one helper function:

qaoa_circuit: a QNode that uses only RX, RZ, and noisy CNOT gates (with a Depolarizing channel on the target qubit) to implement the QAOA algorithm with the cost and mixer Hamiltonian given above. You must complete this function. The arguments of this function are:
- params (list(list(float))): A list of lists of length 2. Each element of params contains the QAOA parameters ( $\gamma$ and $\alpha$ in the figure) of each QAOA layer. Therefore, the length of params is equal to the QAOA depth.
- noise_param (float): The noise parameter for the Depolarization channel that adds noise to the CNOT gates. All CNOT gates are assumed to be equally noisy.
The function must return the expectation value of the cost Hamiltonian. Don't forget that any Trotterizations must be of depth equal to 1.

Then, you must complete the main function:

approximation_ratio: By optimizing the noisy QAOA parameters, this function finds the minimum expectation value of the cost Hamiltonian and compares it to the true minimum by returning the approximation ratio as defined above. The arguments of this function are the number of QAOA layers qaoa_depth (int) and the noise parameter noise_param (float) for the depolarizing gates.

Input

As input to this problem, you are given:

qaoa_depth (int): The number of cost/mixed layers in the QAOA circuit.
noise_param (float): The noise parameter of the Depolarizing channels.

Output

This code must output a float corresponding to the approximation ratio of the noisy QAOA circuit.

Test cases

The test cases are given as arrays of the form [qaoa_depth, noise_param]. The following public test cases are available for you to check your work. There are also some hidden test cases which we will use to check that your solution works in full generality.

test_input = [2,0.005]
expected_output = 0.4875

test_input = [1, 0.003]
expected_output = 0.1307

The outputs above represent the minimum approximation ratio your circuit should achieve with the parameters given, up to an absolute error of $0.02.$ If you achieve the lower bound, the output will be "Success!". Otherwise, you will receive an "Incorrect" prompt.

Good luck!