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

and that the mixer Hamiltonian is

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

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 ( and 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 If you achieve the lower bound, the output will be "Success!". Otherwise, you will receive an "Incorrect" prompt.

Good luck!

import json

import pennylane as qml

import pennylane.numpy as np

edges = [(0, 1), (1, 2), (2, 0), (2, 3)]

num_wires = 4

# We define the Hamiltonian for you!

ops = [qml.PauliZ(0), qml.PauliZ(1),qml.PauliZ(2), qml.PauliZ(3), qml.PauliZ(0)@qml.PauliZ(1), qml.PauliZ(0)@qml.PauliZ(2),qml.PauliZ(1)@qml.PauliZ(2),qml.PauliZ(2)@qml.PauliZ(3)]

coeffs = [0.5, 0.5, 1.25, -0.25, 0.75, 0.75, 0.75, 0.75]

cost_hamiltonian = qml.Hamiltonian(coeffs, ops)

# Write any helper functions you need here

dev = qml.device('default.mixed', wires = num_wires)

@qml.qnode(dev)

def qaoa_circuit(params, noise_param):

"""

Define the noisy QAOA circuit with only CNOT and rotation gates, with Depolarizing noise

in the target qubit of each CNOT gate.

Args:

params(list(list(float))): A list with length equal to the QAOA depth. Each element is a list that contains

the two QAOA parameters of each layer.

noise_param (float): The noise parameter associated with the depolarization gate

Returns:

(np.tensor): A numpy tensor of 1 element corresponding to the expectation value of the cost Hamiltonian

"""

# Put your code here #

def approximation_ratio(qaoa_depth, noise_param):

"""

Returns the approximation ratio of the QAOA algorithm for the Minimum Vertex Cover of the given graph

with depolarizing gates after each native CNOT gate

Args:

qaoa_depth (float): The number of cost/mixer layer in the QAOA algorithm used

noise_param (float): The noise parameter associated with the depolarization gate

Returns:

(float): The approximation ratio for the noisy QAOA

"""

# Put your code here #

# These functions are responsible for testing the solution.

random_params = np.array([np.random.rand(2)])

ops_2 = [qml.PauliX(0), qml.PauliX(1), qml.PauliX(2), qml.PauliX(3)]

coeffs_2 = [1,1,1,1]

mixer_hamiltonian = qml.Hamiltonian(coeffs_2, ops_2)

@qml.qnode(dev)

def noiseless_qaoa(params):

for wire in range(num_wires):

qml.Hadamard(wires = wire)

for elem in params:

qml.ApproxTimeEvolution(cost_hamiltonian, elem[0], 1)

qml.ApproxTimeEvolution(mixer_hamiltonian, elem[1],1)

return qml.expval(cost_hamiltonian)

random_params = np.array([np.random.rand(2)])

circuit_check = (np.isclose(noiseless_qaoa(random_params) - qaoa_circuit(random_params,0),0))

def run(test_case_input: str) -> str:

input = json.loads(test_case_input)

output = approximation_ratio(*input)

return str(output)

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

solution_output = json.loads(solution_output)

expected_output = json.loads(expected_output)

# These are the public test cases

test_cases = [

('[2,0.005]', '0.4875'),

('[1, 0.003]', '0.1307')

]

# 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