Evidence of Scaling Advantage for the QAOA Algorithm on a Classically Intractable Problem

View on GitHub

Open this notebook in GitHub to run it yourself

This notebook solve the Low Autocorrlation Binary Sequences (LABS) problem using QAOA. It follows the paper from Shaydulin et al.[1]. Later, the paper accepted to the Science Advances journal. The LABS problem is relevant in various fields, including communications engineering, design of radar pulses, and more, where sequences with low autocorrelation properties are desired. The LABS problem is known to be NP-hard. The LABS problem is defined as follows: For a given sequence of spins

s_{i} \in \{-1,+1\}

, we have the autocorrelation

A_{k}(s)

. First, define

A_{k}(s)

, the autocorrelation:

A_{k}(s) = \sum_{i=1}^{N-k} s_{i}s_{i+k}

The goal of LABS is to find a sequence of spins

s

that minimizes the so-called “sidelobe” energy:

E_{sidelobe} = \sum_{k=1}^{N-1} A_{k}^{2}(s)

import numpy as np
import pyomo.core as pyo


def LABS_pyo_model(N: int) -> pyo.ConcreteModel:
    # N - the binary sequence size - number of spins
    # return: pyomo classical optimization model of
    # Low Binary Autocorrelation Binary Sequence (LABS) problem.
    model = pyo.ConcreteModel()

    model.s = pyo.Var(range(N), domain=pyo.Binary)

    s_array = np.array(list(model.s.values()))
    # transformation: {0,1} -> {-1,+1}
    spin_s_array = 2 * s_array - 1

    autocorrelation_fun = lambda k: sum(
        [
            spin_s_array[i] * spin_s_array[i + k]
            for i in range(len(spin_s_array[: N - k]))
        ]
    )

    model.sidelobe_energy = pyo.Objective(
        expr=sum([autocorrelation_fun(k) ** 2 for k in range(N - 1)]),
        sense=pyo.minimize,
    )
    return model

Define the Pyomo Model

N = 13

labs_pyo_model = LABS_pyo_model(N)

Define QAOA Parameters

Define the number of layers, the number of iterations, optimizer, and more. And define the number of spins, which is the number of qubits as well.

from classiq import *
from classiq.applications.combinatorial_optimization import CombinatorialProblem

N = 13

combi = CombinatorialProblem(pyo_model=labs_pyo_model, num_layers=3, penalty_factor=0.0)

Combine All the QAOA Parameters to Form a Quantum Model

qmod = combi.get_model(constraints=Constraints(optimization_parameter="cx"))

Synthesize

qprog = combi.get_qprog()
show(qprog)

Output:

Quantum program link: https://platform.classiq.io/circuit/3IoS1Rg0QlkJHUFM5HbSMRjuCQs
  

Output:

https://platform.classiq.io/circuit/3IoS1Rg0QlkJHUFM5HbSMRjuCQs?login=True&version=22
  

Execute

optimized_params = combi.optimize(maxiter=60)

Output:

/home/dor/Sources/Classiq/library-13/lib/python3.13/site-packages/classiq/applications/combinatorial_optimization/combinatorial_problem.py:258: ClassiqDeprecationWarning: ExecutionSession.minimize is deprecated; use variational_minimize instead.
    result = _es.minimize(
  

See Results and Convergence Graph and Result Histogram

import matplotlib.pyplot as plt

plt.plot(combi.cost_trace)
plt.xlabel("Iterations")
plt.ylabel("Cost")
plt.title("Cost convergence")

Output:


Text(0.5, 1.0, 'Cost convergence')

optimization_result = combi.sample(optimized_params)
optimization_result.sort_values(by="cost", ascending=True).head(5)

	solution	probability	cost
1019	{‘s’: [0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0]}	0.000488	182
1164	{‘s’: [0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0]}	0.000488	182
330	{‘s’: [1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0]}	0.000488	182
531	{‘s’: [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0]}	0.000488	182
943	{‘s’: [0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0]}	0.000488	182

optimization_result.hist("cost", weights=optimization_result["probability"])

Output:

array([[<Axes: title={'center': 'cost'}>]], dtype=object)

References

[1]: Shaydulin, Ruslan, et al. “Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem.” arXiv preprint arXiv:2308.02342 (2023)..

Algorithms

Applications

Tutorials

Evidence of Scaling Advantage for the QAOA Algorithm on a Classically Intractable Problem

View on GitHub

Define the Pyomo Model

Define QAOA Parameters

Combine All the QAOA Parameters to Form a Quantum Model

Synthesize

Execute

See Results and Convergence Graph and Result Histogram

References

View on GitHub

​Define the Pyomo Model

​Define QAOA Parameters

​Combine All the QAOA Parameters to Form a Quantum Model

​Synthesize

​Execute

​See Results and Convergence Graph and Result Histogram

​References

Define the Pyomo Model

Define QAOA Parameters

Combine All the QAOA Parameters to Form a Quantum Model

Synthesize

Execute

See Results and Convergence Graph and Result Histogram

References