Problems in implementing a VQA for MaxCut: [Optimization] Parameters do not update

I am trying to implement a custom variational quantum algorithm to solve the unweigthed Maximum Cut problem. It is inspired by the QAOA algorithm (in fact, it uses the same ansatz), but features some modifications, in turn inspired by this paper:

The problem that I’m running into is that, while trying to optimize my ansatz’s parameters (to minimize a specific cost function), using the Adam optimizer, through qml.AdamOptimizer, I notice that the parameters aren’t being updated. The output that I get, while training, looks like this (after 5 optimization steps):

Optimizing parameters...
Objective after step     1: 0.750000000000
Parameters after step    1: [[0.04851585 0.02871953]
 [0.04399233 0.08008254]].
Objective after step     2: 0.750000000000
Parameters after step    2: [[0.04851585 0.02871953]
 [0.04399233 0.08008254]].
Objective after step     3: 0.750000000000
Parameters after step    3: [[0.04851585 0.02871953]
 [0.04399232 0.08008254]].
Objective after step     4: 0.750000000000
Parameters after step    4: [[0.04851585 0.02871953]
 [0.04399232 0.08008254]].
Objective after step     5: 0.750000000000
Parameters after step    5: [[0.04851585 0.02871953]
 [0.04399233 0.08008254]].

I suspect the problem might come from how I define the objective function, but I haven’t been able to resolve this. I also tried testing the hypothesis of my optimization landscape being just really flat, but I wasn’t succesful. My idea was to compute the gradients, using the compute_grad method, from qml.AdamOptimizer, but I was having trouble getting this to work, as it appears to require a positional kwargs argument that I don’t know what is supposed to be in my case (I was trying running compute_grad(objective, parameters), but that didn’t work, as the function required something for kwargs. On the other hand, setting kwargs = {} led to other errors.)

To fully reproduce these results, here’s the utilized code:

# Required imports
import pennylane as qml
from pennylane import numpy as np
import matplotlib.pyplot as plt
import itertools
import time # For timing

# 8-node graph:
graph = [(0, 1), (0, 2), (0, 6), (1, 2), (1, 6), \
         (3, 2), (3, 4), (3, 5), (4, 5), (4, 7), \
         (5, 7), (6, 7)]; n_nodes = 8

# Basis states lists, to be associated with each graph node
n_qubits, basis_states_lists = n_nodes, []
permutations = ["".join(seq) for seq in itertools.product("01", repeat = n_qubits - 1)]
for i in range(n_qubits):
    individual_list = []
    for perm in permutations: individual_list.append(perm[:i] + "1" + perm[i:])

# VQA implementation
def iQAQE_QAOA_Ansatz(graph, n_qubits = None, n_layers = None, device = 'default.qubit', shots = None,
                      parameters = None, B = None, basis_states_lists = None,
                      max_iter = 100, step_size = 0.99):
    Implements the I-QA/QE VQA, for the MaxCut problem. [Modified to use the QAOA ansatz!
                                                         Will only work if n_qubits = n_nodes.
                                                         Not protected against other cases!]

    # Prelimary definitions
    def compute_nodes_probs(probabilities, basis_states_lists):
        Computes the probabilities associated with each node.

            probabilities (list): The probabilities of each basis state.
            basis_states_lists (list[list]): List of lists of basis states assigned to each graph node.

            list: The probabilities associated with each node.
        nodes_probs = []
        for sublist in basis_states_lists:
            node_prob = 0
            for basis_state in sublist: node_prob += probabilities[int(basis_state, 2)]
        nodes_probs = [prob/sum(nodes_probs) for prob in nodes_probs]
        return nodes_probs
    assert(n_qubits is not None and n_layers is not None and parameters is not None and B is not None and basis_states_lists is not None), "n_qubits, n_layers, parameters, B and basis_states_lists cannot be None."
    # Device setup
    dev = qml.device(device, wires = n_qubits, shots = shots)
    # Circuit setup
    # Unitary operator 'U_C' (Cost/Problem) with parameters 'gamma'.
    def U_C(gamma):
        for edge in graph:
            wire1, wire2 = edge[0], edge[1]
            qml.CNOT(wires = [wire1, wire2])
            qml.RZ(gamma, wires = wire2)
            qml.CNOT(wires = [wire1, wire2])

    # Unitary operator 'U_B' (Bias) with parameters 'beta'.
    def U_B(beta):
        for wire in range(n_qubits):
            qml.RX(2 * beta, wires=wire)

    # QAOA circuit ansatz
    def circuit(gammas, betas):
        for wire in range(n_qubits):
            qml.Hadamard(wires = wire)
        for i in range(n_layers):
        return qml.probs()

    # Draw the circuit, for visualization
    qml.drawer.use_style("pennylane") # Set the default style
    print(f'Quantum circuit drawing: n_qubits = {n_qubits}, n_layers = {n_layers}.')
    fig, ax = qml.draw_mpl(circuit, decimals=3)(parameters[0], parameters[1])

    # Status message, before optimization
    print(f"iQAQE level (# of layers): p = {n_layers}.")

    # Define the cost function
    def objective(params):
        # Get the parameters
        gammas, betas = params[0], params[1]

        # First - Compute the probaility associated to each node, from the 'n_qubit' probability distribution
        probs = circuit(gammas, betas); cost  = 0
        nodes_probs = compute_nodes_probs(probs, basis_states_lists)

        # Second - Compute the cost function itself (From
        for edge in graph:
            # j and k are the nodes connected by the edge
            # 0: j, 1: k
            d_jk = np.abs(nodes_probs[edge[0]] - nodes_probs[edge[1]]); s_jk = nodes_probs[edge[0]] + nodes_probs[edge[1]]
            edge_cost = (d_jk - 1/B)**2 + (s_jk - 1/B)**2
            cost += edge_cost
        return cost

    # Initialize optimizer: Adagrad works well empirically. We use Adam, though.
    print(f"Step size: {step_size}.")
    opt = qml.AdamOptimizer(stepsize = step_size, beta1 = 0.9, beta2 = 0.99, eps = 1e-08)

    # Optimize parameters in objective
    start_time = time.time(); i, cost_vec, ar_vec = 0, [], [] # For timing
    print("\nOptimizing parameters...")
        parameters, cost = opt.step_and_cost(objective, parameters); i += 1; cost_vec.append(cost)
        print(f"Objective after step {i:4d}: {cost:.12f}")
        print(f"Parameters after step {i:4d}: {parameters}.")

        # Check maximum iterations
        if i == max_iter:
            print(f"Maximum number of iterations reached: max_iter = {max_iter}")
    train_time = time.time() - start_time # Time taken for training
    print("--- Training took %s seconds ---" % (train_time))

    # Just take the exact distribution
    probabilities = circuit(parameters[0], parameters[1])

    # Computing the probaility associated to each node, from the 'n_qubit' probability distribution
    nodes_probs = compute_nodes_probs(probabilities, basis_states_lists)

    # Get the final, computed partition
    partition = ['0' if node_prob < 1 / (2*B) else '1' for node_prob in nodes_probs]

    return probabilities, nodes_probs, cost, cost_vec, ar_vec, parameters, partition, train_time

n_layers, step_size = 2, 0.98
params_QAOA = 0.1 * np.random.rand(2, n_layers, requires_grad=True); print(f"Initial parameters [QAOA]: {params_QAOA}.")
dev = 'default.qubit'

_, _, _, _, _, _, _, _ = iQAQE_QAOA_Ansatz(graph, n_qubits = n_nodes, n_layers = n_layers, device = dev,
                                           parameters = params_QAOA, B = 4, basis_states_lists = basis_states_lists,
                                           max_iter = 100, step_size = step_size)

Is there anything that jumps out to you as seemingly wrong that could be causing this behaviour [parameters not updating]? Any help would be greatly appreciated!
Thank you in advance,

For debugging purposes, here’s the output of qml.about():

Name: PennyLane
Version: 0.34.0
Summary: PennyLane is a Python quantum machine learning library by Xanadu Inc.
License: Apache License 2.0
Location: [-]
Requires: appdirs, autograd, autoray, cachetools, networkx, numpy, pennylane-lightning, requests, rustworkx, scipy, semantic-version, toml, typing-extensions
Required-by: PennyLane-Lightning

Platform info:           Windows-10-10.0.22621-SP0
Python version:          3.11.5
Numpy version:           1.26.1
Scipy version:           1.11.3
Installed devices:
- default.gaussian (PennyLane-0.34.0)
- default.mixed (PennyLane-0.34.0)
- default.qubit (PennyLane-0.34.0)
- default.qubit.autograd (PennyLane-0.34.0)
- default.qubit.jax (PennyLane-0.34.0)
- default.qubit.legacy (PennyLane-0.34.0)
- (PennyLane-0.34.0)
- default.qubit.torch (PennyLane-0.34.0)
- default.qutrit (PennyLane-0.34.0)
- null.qubit (PennyLane-0.34.0)
- lightning.qubit (PennyLane-Lightning-0.34.0)

Hello @Afonso_Azenha ! Welcome to the forum!

I took a brief look at your code and I agree that the culprit is probably a mismatch between the cost function and the circuit design. If I understood it correctly, your circuit looks like a regular QAOA, however, you want to implement the cost function from the the paper you mentioned. Is this correct?

In that case, you have to prepare the unitary U_C matching the cost function Hamiltonian for the problem you want to optimize. :slight_smile:

In this demo, there is an example of how to implement QAOA for MaxCut. And here, there is a more detailed introduction of QAOA. I would suggest taking a look at those, especially the latter one.

I hope this helps! :slight_smile:

1 Like

Hello again,
thank you for the feedback @ludmilaaasb . I think I have figured out the problem. It really was a mismatch between the cost function and ansatz. I did the calculations by hand for a trivial graph and figured out that my cost function is actually independent of the parameters (quite the coincidence I must say :sweat_smile:), so it would make sense that the optimizer doesn’t update the parameters. With a slightly different cost function, this seems to be working properly now! Thank you for bringing this possibility to light!