Reaching for the Ratio | PennyLane Challenges

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

This challenge is part of the Q-SITE 2024 Hackathon. Learn more and join at https://www.qsiteconf.ca/

Challenge Statement

The Quantum Approximate Optimization Algorithm (QAOA) is well-known due to its efficacy in solving combinatorial optimization problems. In this challenge, we will use it to solve the Minimum Vertex Cover problem. Then we will compare the QAOA output to the exact classical solution in order to determine how well the algorithm performs.

The Minimum Vertex Cover problems ask us to find a set of vertices in a graph such that all of the edges in the graph are connected to at least one vertex in the set. This set must also contain the smallest possible number of vertices.

For example, in the figure below, the green vertices are in the set and the blue edges are adjacent to them. A vertex set that makes all the edges in the graph blue is a vertex cover. Finding a minimum vertex cover amounts to finding the minimum amount of green vertices that makes all the edges blue.

Our objective in this challenge is to write a routine that solves this problem for an arbitrary graph.

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.

You will build these Hamiltonians, implement the QAOA circuit, and optimize the QAOA parameters to find the minimum expectation value of the cost Hamiltonian.

As a reminder, the QAOA circuit consists of a series of a layer of Hadamard gates followed by the QAOA layers shown below.

The quality of your solution will be assessed via the approximation ratio $r^{*}.$ defined as

r^{*} = \frac{\text{Minimum expectation value estimated by QAOA}}{\text{True minimum eigenvalue of the cost Hamiltonian}}.

Your goal is to achieve a minimum approximation required for each of the test cases.

Challenge code

In this challenge, the graphs are encoded by their edges, which are an input for many of the given functions. The edges list's elements are ordered pairs of integers representing each edge in the graph. The integers in each pair are the vertices joined by the edge. For example, the following graph

is represented via edges = [[0,1], [0,2], [1,2], [2,3]].

You must complete the following functions:

cost_hamiltonian: which takes the graph's edges as an input and returns the cost Hamiltonian (pennylane.Operator) for the Minimum Vertex Cover problem, given in the statement above.
mixer_hamiltonian: which takes the graph's edges as an input and returns the mixer Hamiltonian (pennylane.Operator) for the Minimum Vertex Cover problem, given in the statement above.
qaoa_circuit: a quantum function that implements that QAOA circuit. It depends on the QAOA parameters (params) and the edges. This is simply a list of gates and you should not return any measurements.
optimize: which returns the QAOA parameters that minimize the expectation value of the cost Hamiltonian.

In addition, there are some additional function we have defined for you.

qaoa_expval: This is a QNode that implements your qaoa_circuit and returns the expectation value of the cost Hamiltonian. You should use this as the cost function in you optimization routine.
qaoa_probs: This is a QNode that implements your qaoa_circuit and returns the probabilities on all wires. This function is used by the grader to test whether you QAOA routine returns the correct ground state.
approximation_ratio: This function calculates the approximation ratio of your solution as compared to the exact solution. You must achieve a minimum approximation ratio for the three test cases given below.

Input

As input to this problem, you are given the edges of the graph to solve for, as explained above.

Output

The expected output is a float corresponding to the approximation ratio of the QAOA algorithm. This float will be automatically extracted from the output of the approximation_ratio function.

However, if your QAOA routine fails to find the ground state, the output will be the string "QAOA failed to find right answer".

Test cases

Your code must address the three following test cases. Your approximation ratio must be greater than the lower_bound in order for your solution to be graded as correct ("Success!"). Otherwise, you will receive an "Incorrect" prompt.

test_input: [[0, 1], [1, 2], [0, 2], [2, 3]]
lower_bound: 0.55

test_input: [[0, 1], [1, 2], [2, 3], [3, 0]]
lower_bound: 0.92

test_input: [[0, 1], [0, 2], [1, 2], [1, 3], [2, 4], [3, 4]]
lower_bound: 0.55

Good luck!