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

and that the mixer Hamiltonian is

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 defined as

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!

import json

import pennylane as qml

import pennylane.numpy as np

# Write any helper functions you need here

def cost_hamiltonian(edges):

"""

This function build the QAOA cost Hamiltonian for a graph, encoded in its edges

Args:

- Edges (list(list(int))): A list of ordered pairs of integers, representing

the edges of the graph for which we need to solve the minimum vertex cover problem.

Returns:

- pennylane.Operator: The cost Hamiltonian associated with the graph.

"""

# Put your code here #

def mixer_hamiltonian(edges):

"""

This function build the QAOA mixer Hamiltonian for a graph, encoded in its edges

Args:

- edges (list(list(int))): A list of ordered pairs of integers, representing

the edges of the graph for which we need to solve the minimum vertex cover problem.

Returns:

- pennylane.Operator: The mixer Hamiltonian associated with the graph.

"""

# Put your code here #

def qaoa_circuit(params, edges):

"""

This quantum function (i.e. a list of gates describing a circuit) implements the QAOA algorithm

You should only include the list of gates, and not return anything

Args:

- params (np.array): A list encoding the QAOA parameters. You are free to choose any array shape you find

convenient.

- edges (list(list(int))): A list of ordered pairs of integers, representing

the edges of the graph for which we need to solve the minimum vertex cover problem.

Returns:

- This function does not return anything. Do not write any return statements.

"""

# Put your code here

# This function runs the QAOA circuit and returns the expectation value of the cost Hamiltonian

dev = qml.device("default.qubit")

@qml.qnode(dev)

def qaoa_expval(params, edges):

qaoa_circuit(params, edges)

return qml.expval(cost_hamiltonian(edges))

def optimize(edges):

"""

This function returns the parameters that minimize the expectation value of

the cost Hamiltonian after applying QAOA

Args:

- edges (list(list(int))): A list of ordered pairs of integers, representing

the edges of the graph for which we need to solve the minimum vertex cover problem.

"""

# Your cost function should be the expectation value of the cost Hamiltonian

# You may use the qaoa_expval QNode defined above

# Write your optimization routine here

# These are auxiliary functions that will help us grade your solution. Feel free to check them out!

@qml.qnode(dev)

def qaoa_probs(params, edges):

qaoa_circuit(params, edges)

return qml.probs()

def approximation_ratio(params, edges):

true_min = np.min(qml.eigvals(cost_hamiltonian(edges)))

approx_ratio = qaoa_expval(params, edges)/true_min

return approx_ratio

# These functions are responsible for testing the solution.

def run(test_case_input: str) -> str:

ins = json.loads(test_case_input)

params = optimize(ins)

output= approximation_ratio(params,ins)

ground_energy = np.min(qml.eigvals(cost_hamiltonian(ins)))

index = np.argmax(qaoa_probs(params, ins))

vector = np.zeros(len(qml.matrix(cost_hamiltonian(ins))))

vector[index] = 1

calculate_energy = np.real_if_close(np.dot(np.dot(qml.matrix(cost_hamiltonian(ins)), vector), vector))

verify = np.isclose(calculate_energy, ground_energy)

if verify:

return str(output)

return "QAOA failed to find right answer"

def check(solution_output: str, expected_output: str) -> None:

assert not solution_output == "QAOA failed to find right answer", "QAOA failed to find the ground eigenstate."

solution_output = json.loads(solution_output)

expected_output = json.loads(expected_output)

assert solution_output >= expected_output-0.01, "Minimum approximation ratio not reached"

# These are the public test cases

test_cases = [

('[[0, 1], [1, 2], [0, 2], [2, 3]]', '0.55'),

('[[0, 1], [1, 2], [2, 3], [3, 0]]', '0.92'),

('[[0, 1], [0, 2], [1, 2], [1, 3], [2, 4], [3, 4]]', '0.55')

]

# This will run the public test cases locally

for i, (input_, expected_output) in enumerate(test_cases):

print(f"Running test case {i} with input '{input_}'...")

try:

output = run(input_)

except Exception as exc:

print(f"Runtime Error. {exc}")

else:

if message := check(output, expected_output):

print(f"Wrong Answer. Have: '{output}'. Want: '{expected_output}'.")

else:

print("Correct!")

or to submit your code