Skip to main content

View on GitHub

Open this notebook in GitHub to run it yourself

​
Background

Given a graph G=(V,E)G = (V,E) and number of colors K, find the largest induced subgraph that can be colored using up to K colors. A coloring is legal if:
  • each vetrex vi{v_i} is assigned with a color ki∈{0,1,...,k−1}k_i \in \{0, 1, ..., k-1\}
  • adajecnt vertex have different colors: for each vi,vjv_i, v_j such that (vi,vj)∈E(v_i, v_j) \in E, ki≠kjk_i \neq k_j.
An induced subgraph of a graph G=(V,E)G = (V,E) is a graph G′=(V′,E′)G'=(V', E') such that V′⊂VV'\subset V and E′={(v1,v2)∈E ∣ v1,v2∈V′}E' = \{(v_1, v_2) \in E\ |\ v_1, v_2 \in V'\}.

​
Define the Optimization Problem

​

​
Initialize the Model with Parameters

output

​

Output:

​
Setting Up the Classiq Problem Instance

In order to solve the Pyomo model defined above, we use the CombinatorialProblem python class. Under the hood it translates the Pyomo model to a quantum model of the QAOA algorithm [1], with cost hamiltonian translated from the Pyomo model. We can choose the number of layers for the QAOA ansatz using the argument num_layers.

​
Synthesizing the QAOA Circuit and Solving the Problem

We can now synthesize and view the QAOA circuit (ansatz) used to solve the optimization problem:
Output:
Output:
We now solve the problem by calling the optimize method of the CombinatorialProblem object. For the classical optimization part of the QAOA algorithm we define the maximum number of classical iterations (maxiter) and the α\alpha-parameter (quantile) for running CVaR-QAOA, an improved variation of the QAOA algorithm [2]:
We can check the convergence of the run:
Output:
output

​
Optimization Results

We can also examine the statistics of the algorithm. The optimization is always defined as a minimzation problem, so the positive maximization objective was tranlated to a negative minimization one by the Pyomo to qmod translator. In order to get samples with the optimized parameters, we call the sample method:
We will also want to compare the optimized results to uniformly sampled results:
And compare the histograms:
output Let us plot the best solution:
output

​
References

[1]: Farhi, Edward, Jeffrey Goldstone, and Sam Gutmann. “A quantum approximate optimization algorithm.” arXiv preprint arXiv:1411.4028 (2014). [2]: Barkoutsos, Panagiotis Kl, et al. “Improving variational quantum optimization using CVaR.” Quantum 4 (2020): 256.