Skip to main content

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 si∈{−1,+1}s_{i} \in \{-1,+1\}, we have the autocorrelation Ak(s)A_{k}(s). First, define Ak(s)A_{k}(s), the autocorrelation: Ak(s)=∑i=1N−ksisi+kA_{k}(s) = \sum_{i=1}^{N-k} s_{i}s_{i+k} The goal of LABS is to find a sequence of spins ss that minimizes the so-called “sidelobe” energy: Esidelobe=∑k=1N−1Ak2(s)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 OptimizerConfig, QAOAConfig

N = 13

qaoa_config = QAOAConfig(num_layers=3, penalty_energy=0.0)

optimizer_config = OptimizerConfig(opt_type="COBYLA", max_iteration=60)

​

​
Combine all the QAOA parameters to form a quantum model

qmod = construct_combinatorial_optimization_model(
    pyo_model=labs_pyo_model,
    qaoa_config=qaoa_config,
    optimizer_config=optimizer_config,
)

​
Synthesize

qprog = synthesize(model=qmod, constraints=Constraints(optimization_parameter="cx"))
show(qprog)
Output:

Quantum program link: https://platform.classiq.io/circuit/36pYxIFvXlrAXdIJ3RJ2i6uwwyZ

​
Execute

from classiq import execute

res = execute(qprog).result()

​
See results and convergence graph and result histogram

vqe_result = res[0].value
vqe_result.convergence_graph
output 
import pandas as pd

from classiq.applications.combinatorial_optimization import (
    get_optimization_solution_from_pyo,
)

solution = get_optimization_solution_from_pyo(
    labs_pyo_model, vqe_result=vqe_result, penalty_energy=qaoa_config.penalty_energy
)
optimization_result = pd.DataFrame.from_records(solution)
optimization_result.sort_values(by="cost", ascending=True).head(5)
probabilitycostsolutioncount
13200.000488182.0[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1]1
12720.000488182.0[1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0]1
11930.000488182.0[0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1]1
10870.000488186.0[1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0]1
10330.000488186.0[1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1]1
optimization_result.hist("cost", weights=optimization_result["probability"])
Output:
array([[<Axes: title={'center': 'cost'}>]], dtype=object)
output

​
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)..