Quantum Approximate Optimization Algorithm (QAOA)

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm that solves combinatorial optimization problems.

Key features of QAOA:

  • Hybrid approach: Utilizes both quantum and classical resources efficiently.

  • Iterative optimization: Classical optimizer adjusts circuit parameters to minimize energy.

  • NISQ compatibility: This algorithm is designed to run on the noisy quantum computers of today.

  • Flexibility: Can be applied to various problems in quantum chemistry and optimization problems broadly.

# ============================================================================ #
# Copyright (c) 2024 NVIDIA Corporation & Affiliates.                          #
# All rights reserved.                                                         #
#                                                                              #
# This source code and the accompanying materials are made available under     #
# the terms of the Apache License 2.0 which accompanies this distribution.     #
# ============================================================================ #
import cudaq, cudaq_solvers as solvers
import networkx as nx, numpy as np

# Create the ligand-configuration graph
G = nx.Graph()
edges = [[0, 1], [0, 2], [0, 4], [0, 5], [1, 2], [1, 3], [1, 5], [2, 3], [2, 4],
         [3, 4], [3, 5], [4, 5]]
weights = [0.6686, 0.6686, 0.6686, 0.1453, 0.1453, 0.1453]
for i, weight in enumerate(weights):
    G.add_node(i, weight=weight)
G.add_edges_from(edges)

# Set some parameters we'll need 
penalty = 6.0
num_layers = 3

# Create the Clique Hamiltonian
H = solvers.get_clique_hamiltonian(G, penalty=penalty)

# Get the number of parameters we'll need
parameter_count = solvers.get_num_qaoa_parameters(H,
                                                  num_layers,
                                                  full_parameterization=True,
                                                  counterdiabatic=True)

# Create the initial parameters to begin optimization
init_params = np.random.uniform(-np.pi / 8, np.pi / 8, parameter_count)

# Run QAOA, specify full parameterization and counterdiabatic
# Full parameterization uses an optimization parameter for 
# every term in the clique Hamiltonian and the mixer hamiltonian. 
# Specifying counterdiabatic adds extra Ry rotations at the 
# end of each layer.
opt_value, opt_params, opt_config = solvers.qaoa(H,
                                                 num_layers,
                                                 init_params,
                                                 full_parameterization=True,
                                                 counterdiabatic=True)

# Print the results
print()
print('Optimal energy: ', opt_value)
print('Sampled states: ', opt_config)
print('Optimal Configuration: ', opt_config.most_probable())

/*******************************************************************************
 * Copyright (c) 2024 NVIDIA Corporation & Affiliates.                         *
 * All rights reserved.                                                        *
 *                                                                             *
 * This source code and the accompanying materials are made available under    *
 * the terms of the Apache License 2.0 which accompanies this distribution.    *
 ******************************************************************************/

#include "cudaq.h"
#include "cudaq/solvers/operators.h"
#include "cudaq/solvers/qaoa.h"

// Compile and run with
// nvq++ --enable-mlir -lcudaq-solvers molecular_docking_qaoa.cpp
// ./a.out

int main() {

  // Create the ligand-configuration graph
  cudaqx::graph g;
  std::vector<double> weights{0.6686, 0.6686, 0.6686, 0.1453, 0.1453, 0.1453};
  std::vector<std::pair<int, int>> edges{{0, 1}, {0, 2}, {0, 4}, {0, 5},
                                         {1, 2}, {1, 3}, {1, 5}, {2, 3},
                                         {2, 4}, {3, 4}, {3, 5}, {4, 5}};
  for (std::size_t node = 0; auto weight : weights)
    g.add_node(node++, weight);

  for (auto &edge : edges)
    g.add_edge(edge.first, edge.second);

  // Set some parameters we'll need
  double penalty = 6.0;
  std::size_t numLayers = 3;

  // Create the Clique Hamiltonian
  auto H = cudaq::solvers::get_clique_hamiltonian(g, penalty);

  // Get the number of required variational parameters
  auto numParams = cudaq::solvers::get_num_qaoa_parameters(
      H, numLayers,
      {{"full_parameterization", true}, {"counterdiabatic", true}});

  // Create the initial parameters to begin optimization
  auto initParams = cudaq::random_vector(-M_PI / 8., M_PI / 8., numParams);

  // Run QAOA, specify full parameterization and counterdiabatic
  // Full parameterization uses an optimization parameter for
  // every term in the clique Hamiltonian and the mixer hamiltonian.
  // Specifying counterdiabatic adds extra Ry rotations at the
  // end of each layer.
  auto [opt_value, opt_params, opt_config] = cudaq::solvers::qaoa(
      H, numLayers, initParams,
      {{"full_parameterization", true}, {"counterdiabatic", true}});

  // Print out the results
  std::cout << "Optimal energy: " << opt_value << "\n";
  std::cout << "Sampled states: ";
  opt_config.dump();
  std::cout << "Optimal configuraiton: " << opt_config.most_probable() << "\n";
}

Compile and run with

nvq++ --enable-mlir -lcudaq-solvers molecular_docking_qaoa.cpp -o molecular_docking_qaoa
./molecular_docking_qaoa

CUDA-Q Solvers Implementation

Here’s how to use CUDA-Q Solvers to solve the Maximum Clique Problem using QAOA:

Code Explanation

  1. Graph Creation:

    • A NetworkX graph is created to represent the problem.

    • Nodes and edges are added with specific weights.

  2. Clique Hamiltonian Generation:

    • solvers.get_clique_hamiltonian is used to create the Hamiltonian for the Maximum Clique Problem.

    • The penalty term and number of QAOA layers are defined.

  3. QAOA Parameter Setup:

    • The number of required parameters is calculated using solvers.get_num_qaoa_parameters.

    • Randomly generate initial parameters.

  4. QAOA Execution with solvers.qaoa:

    • Call the solver with the Hamiltonian, number of QAOA layers, and whether you want full parametrization and counterdiabatic driving.

    • Full parameterization: Uses an optimization parameter for every term in the clique Hamiltonian and the mixer Hamiltonian.

    • Counterdiabatic driving: Adds extra Ry rotations at the end of each layer.

  5. Results Analysis:

    • The optimal energy, sampled states, and most probable configuration are printed.

This implementation showcases the power of CUDA-Q Solvers in solving combinatorial optimization problems using hybrid quantum-classical algorithms. By using CUDA-Q Solvers with the networkx library, we very quickly set up and ran a QAOA application to compute optimal configurations for a molecular docking problem.