.. _sec_vqa:

================
Examples: MaxCut
================

In this section, we present three implementations to solve the Max-Cut problem using quantum computing: QAOA :cite:`farhi2014`, FALQON :cite:`magann2022`, and VQE :cite:`peruzzo2014`. Here, our strict focus is on their implementation in Ket; for detailed algorithmic presentations, we refer the reader to the original works. The Max-Cut problem seeks to partition the vertices of a graph into two disjoint sets such that the number of edges spanning the two sets is maximized. 



-------------------------
Defining the Hamiltonians
-------------------------

For QAOA, FALQON, and VQE, the objective of Max-Cut can be encoded into a cost Hamiltonian :math:`H_c`. For a graph with edges :math:`\mathcal{E}`, the cost Hamiltonian assigns a lower energy to valid bitstrings representing the cuts. Additionally, for QAOA and FALQON, we require a mixer Hamiltonian :math:`H_m` to drive transitions between states.

**Cost Hamiltonian:**

.. math::

   H_c = -\frac{1}{2}\sum_{a,\ b\ \in\ \mathcal{E}} \left(1 - Z_a Z_b\right)

.. code-block:: python

    def cost_h(edges, q: Quant):
        with obs():
            hc = sum(1 - Z(q[a]) * Z(q[b])
                     for a, b in edges)
        return -hc / 2

**Mixer Hamiltonian:**

.. math::

   H_m = \sum_{q} X_q

.. code-block:: python

    def mixer_h(nodes: Quant):
        with obs():
            Hm = sum(X(q) for q in nodes)
        return Hm

----
QAOA
----

The QAOA ansatz consists of alternating applications of the time-evolution operators :math:`e^{-i \gamma H_c}` and :math:`e^{-i \beta H_m}`. Since the terms within :math:`H_c` and :math:`H_m` mutually commute, we can pass these Hamiltonians directly to Ket's :func:`~ket.gates.evolve` function.



.. code-block:: python

    def qaoa_layer(edges, qubits, gamma, beta):
        evolve(gamma * cost_h(edges, qubits))
        evolve(beta * mixer_h(qubits))

    def qaoa_ansatz(edges, qubits, gamma, beta):
        for g, b in zip(gamma, beta):
            qaoa_layer(edges, qubits, g, b)

A classical optimizer is needed to execute this algorithm. To use SciPy's :func:`scipy.optimize.minimize`, we must create a cost function that encapsulates the quantum process:

.. code-block:: python

    def qaoa_objective(graph, n, parameters):
        process = Process(num_qubits=n, simulator="dense",
                          execution="batch")

        p = len(parameters) // 2 # Number of layers
        gamma = parameters[p:]
        beta = parameters[:p]

        qubits = process.alloc(n)
        H(qubits) # Prepare the initial uniform superposition
        qaoa_ansatz(graph, qubits, gamma, beta)
        
        return exp_value(cost_h(graph, qubits)).get()

    res = minimize(
        partial(qaoa_objective, graph, n),
        parameters,      # Initial parameters
        method="COBYLA", # Gradient-free optimizer
    )

---
VQE
---

Unlike QAOA, VQE does not prescribe a rigidly structured ansatz. A possible, hardware-efficient implementation for the Max-Cut problem is as follows:



.. code-block:: python

    def vqe_ansatz(graph, qubits, parameters):
        for p in parameters:
            for a, b in graph:
                CZ(qubits[a], qubits[b])
            RY(p, qubits)

As with QAOA, we need an objective function to utilize the SciPy minimizer. It is common to use gradient-based optimizers for VQE; here, we implement the objective function so that the gradient is calculated and returned alongside the cost value:

.. code-block:: python

    def vqe_objective(graph, n, parameters):
        process = Process(num_qubits=n, simulator="dense",
                          execution="batch", gradient=True)
        # Register parameters for gradient calculation
        parameters = process.param(*parameters) 
        qubits = process.alloc(n)
        vqe_ansatz(graph, qubits, parameters)
        
        return (
            exp_value(cost_h(graph, qubits)).get(),
            [p.grad for p in parameters],
        )

    res = minimize(
        partial(vqe_objective, graph, n),
        parameters,        # Initial parameters
        method="L-BFGS-B", # Gradient-based optimizer
        jac=True,
    )

------
FALQON
------

FALQON utilizes a different approach from QAOA and VQE; it relies on feedback-based measurements to iteratively optimize the quantum state over several layers. 



.. code-block:: python

    def falqon_layer(graph, qubits, beta, delta_t):
        evolve(delta_t * cost_h(graph, qubits))
        evolve(beta * delta_t * mixer_h(qubits))

    def beta_h(graph, qubits):
        return -1j * commutator(mixer_h(qubits), cost_h(graph, qubits))

In Ket, we can use the KBW simulator and live execution to calculate the feedback parameter :math:`\beta` and the cost expectation :math:`\langle H_c \rangle` interactively for each layer.

.. code-block:: python

    beta, cost = [0.0], []
    process = Process()
    qubits = H(process.alloc(n))

    for _ in range(num_layers):
        falqon_layer(graph, qubits, beta[-1], delta_t)
        cost.append(exp_value(cost_h(graph, qubits)).get())
        beta.append(exp_value(beta_h(graph, qubits)).get())