---
hide-toc: true
file_format: mystnb
kernelspec:
  name: python3
---

# Formulation Benchmarks

We have benchmarked the formulation of mathematical optimization models provided as a library in Python against the Amplify SDK. We measured the execution time to create a model and output it as QUBO using the [traveling salesperson problem formulation](tsp.ipynb) as an example, assuming using the QUBO solver.

However, each library, including the Amplify SDK, covers different features depending on the formulation method. Here is a summary of the features and policies of each library, formulated as follows.

```{list-table}
:width: 100%
:widths: 4 5 5 5 5 5
:header-rows: 1
:stub-columns: 1

*   - \-
    - [Amplify](https://amplify.fixstars.com/en/docs/amplify/v1/)
    - [PyQUBO](https://pyqubo.readthedocs.io/en/latest/)
    - [dimod](https://docs.ocean.dwavesys.com/en/stable/docs_dimod/)  
      BQM (index)
    - [dimod](https://docs.ocean.dwavesys.com/en/stable/docs_dimod/)  
      BQM (symbol)
    - [dimod](https://docs.ocean.dwavesys.com/en/stable/docs_dimod/)  
      CQM{sup}`*`
*   - Symbolic operation
    - ✅
    - ✅
    - ❌
    - ✅
    - ✅
*   - Objective function
    - ✅
    - ✅
    - ✅
    - ✅
    - ✅
*   - Constraint
    - ✅
    - ✅{sup}`**`
    - ❌{sup}`***`
    - ❌{sup}`***`
    - ✅{sup}`*`
*   - Higher order polynomial
    - ✅
    - ✅
    - ❌
    - ❌
    - ❌
*   - Coefficient matrix
    - ✅
    - ❌
    - ❌
    - ❌
    - ❌
*   - Variable type
    - B/S/I/R
    - B/S
    - B/S
    - B/S
    - B/S/I/R
*   - Supported machines
    - Various
    - Depends on user
    - D-Wave only
    - D-Wave only
    - D-Wave only
```

{.sd-text-right}
B: Binary, S: Ising Spin, I: Integer, R: Real

\*: Model creation only, as QUBO output (conversion of constraints to the penalty functions) is not available.  
\*\*: Must define penalty function  
\*\*\*: Constraints are expressed by adding penalty functions to the objective function  

(amplify-tsp-bench)=

````{dropdown} Amplify
```python
import amplify


def tsp_for_amplify(ncity: int, distances: np.ndarray, dmax: float):
    q = amplify.VariableGenerator().array("Binary", ncity + 1, ncity)
    q[-1, :] = q[0, :]

    # Objective function
    objective: amplify.Poly = amplify.einsum(
        "ij,ki,kj->", distances, q[:-1], q[1:]
    )

    # Constraints
    constraints: amplify.ConstraintList = amplify.one_hot(
        q[:-1], axis=1
    ) + amplify.one_hot(q[:-1], axis=0)

    return objective + dmax * constraints


class BenchTspAmplify:
    def create_model(self, ncity: int, distances: np.ndarray, dmax: float):
        self.model = tsp_for_amplify_v1(ncity, distances, dmax)

    def to_qubo(self):
        self.model.to_unconstrained_poly()
```
````

(pyqubo-tsp-bench)=

````{dropdown} PyQUBO
```python
import pyqubo


def tsp_for_pyqubo(ncity: int, distances: np.ndarray, dmax: float):
    # from https://github.com/recruit-communications/pyqubo/blob/master/notebooks/TSP.ipynb
    # NOTE: https://github.com/recruit-communications/pyqubo/blob/master/benchmark/benchmark.py
    # is not valid for TSP

    x = pyqubo.Array.create("c", (ncity, ncity), "BINARY")

    # Constraint not to visit more than two cities at the same time.
    time_const = 0.0
    for i in range(ncity):
        # If you wrap the hamiltonian by Const(...), this part is recognized as constraint
        time_const += pyqubo.Constraint(
            (sum(x[i, j] for j in range(ncity)) - 1) ** 2, label=f"time{i}"
        )

    # Constraint not to visit the same city more than twice.
    city_const = 0.0
    for j in range(ncity):
        city_const += pyqubo.Constraint(
            (sum(x[i, j] for i in range(ncity)) - 1) ** 2, label=f"city{j}"
        )

    # distance of route
    feed_dict = {}

    distance = 0.0
    for i in range(ncity):
        for j in range(ncity):
            for k in range(ncity):
                # we set the constant distance
                distance += distances[i, j] * x[k, i] * x[(k + 1) % ncity, j]

    # Construct hamiltonian
    A = pyqubo.Placeholder("A")
    H = distance + A * (time_const + city_const)

    feed_dict["A"] = dmax

    # Compile model
    return H.compile(), feed_dict


class BenchTspPyQubo:
    def create_model(self, ncity: int, distances: np.ndarray, dmax: float):
        self.model, self._feed_dict = tsp_for_pyqubo(ncity, distances, dmax)

    def to_qubo(self):
        self.model.to_qubo(index_label=False, feed_dict=self._feed_dict)

```
````

(dimod-bqm-idx-tsp-bench)=

````{dropdown} dimod BQM (index)
```python
import dimod


def tsp_for_dimod_bqm(ncity: int, distances: np.ndarray, dmax: float):
    bqm = dimod.BinaryQuadraticModel(ncity * ncity, dimod.BINARY)

    # Objective function
    for n in range(ncity):
        for i in range(ncity):
            for j in range(ncity):
                bqm.add_quadratic(
                    n * ncity + i,
                    ((n + 1) % ncity) * ncity + j,
                    distances[i, j],
                )

    # Constraint on each row
    for n in range(ncity):
        left = [(n * ncity + i, 1) for i in range(ncity)]
        bqm.add_linear_equality_constraint(left, dmax, -1)

    # Constraint on each column
    for i in range(ncity):
        left = [(n * ncity + i, 1) for n in range(ncity)]
        bqm.add_linear_equality_constraint(left, dmax, -1)

    return bqm


class BenchTspDimodBQM:
    def create_model(self, ncity: int, distances: np.ndarray, dmax: float):
        self.model = tsp_for_dimod_bqm(ncity, distances, dmax)

    def to_qubo(self):
        self.model.to_qubo()
```
````

(dimod-bqm-sym-tsp-bench)=

````{dropdown} dimod BQM (symbol math)
```python
import dimod


def tsp_for_dimod_bqm_sym(
    ncity: int, distances: np.ndarray, dmax: float
) -> dimod.BinaryQuadraticModel:
    bqm = dimod.BinaryQuadraticModel(ncity * ncity, dimod.BINARY)
    vars = [
        [dimod.Binary(f"{n},{i}") for i in range(ncity)] for n in range(ncity)
    ]

    # Objective function
    for n in range(ncity):
        for i in range(ncity):
            for j in range(ncity):
                bqm += distances[i, j] * vars[n][i] * vars[(n + 1) % ncity][j]

    # Constraint on each row
    for n in range(ncity):
        bqm += dmax * (sum(vars[n][i] for i in range(ncity)) - 1) ** 2

    # Constraint on each column
    for i in range(ncity):
        bqm += dmax * (sum(vars[n][i] for n in range(ncity)) - 1) ** 2

    return bqm  # type: ignore


class BenchTspDimodBQMSym:
    def create_model(self, ncity: int, distances: np.ndarray, dmax: float):
        self.model = tsp_for_dimod_bqm_sym(ncity, distances, dmax)

    def to_qubo(self):
        self.model.to_qubo()
```
````

(dimod-cqm-tsp-bench)=

````{dropdown} dimod CQM
```python
import dimod


def tsp_for_dimod_cqm(ncity: int, distances: np.ndarray, dmax: float):
    cqm = dimod.ConstrainedQuadraticModel()
    vars = [
        [dimod.Binary(f"{n},{i}") for i in range(ncity)] for n in range(ncity)
    ]

    # Objective function
    obj = 0.0
    for n in range(ncity):
        for i in range(ncity):
            for j in range(ncity):
                obj += distances[i, j] * vars[n][i] * vars[(n + 1) % ncity][j]
    cqm.set_objective(obj)

    # Constraint on each row
    for n in range(ncity):
        cqm.add_constraint(sum(vars[n]) == 1)

    # Constraint on each column
    for i in range(ncity):
        cqm.add_constraint(sum(vars[n][i] for n in range(ncity)) == 1)

    return cqm


class BenchTspDimodCQM:
    def create_model(self, ncity: int, distances: np.ndarray, dmax: float):
        self.model = tsp_for_dimod_cqm(ncity, distances, dmax)

    def to_qubo(self):
        pass
```
````

````{dropdown} Benchmark code
```python
import time


def make_distance(ncity: int) -> tuple[np.ndarray, float]:
    rng = np.random.default_rng(12345)
    x = rng.random(ncity)
    y = rng.random(ncity)
    distances = (
        (x[:, np.newaxis] - x[np.newaxis, :]) ** 2
        + (y[:, np.newaxis] - y[np.newaxis, :]) ** 2
    ) ** 0.5
    dmax: float = np.max(distances)  # type: ignore
    return distances, dmax


for ncity in [32, 100, 317]:
    distances, dmax = make_distance(ncity)

    for bench_class in [
        BenchTspAmplify,
        BenchTspPyQubo,
        BenchTspDimodBQM,
        BenchTspDimodBQMSym,
        BenchTspDimodCQM,
    ]:
        bench = bench_class()
        start = time.time()
        bench.create_model(ncity, distances, dmax)
        end = time.time()
        t1 = end - start
        start = time.time()
        bench.to_qubo()
        end = time.time()
        t2 = end - start
        print(f"{t1} {t2}")
```
````

**Benchmark environment**

``````{grid} 1 2 2 2
:padding: 2 2 5 5

````{grid-item}
:padding: 0 0 0 3
:margin: 0
```{card} CPU
Intel{sup}`R` Core{sup}`TM` i9-12900K  
(E-Cores disabled)
```
```{card} OS
Ubuntu 22.04
```
````
```{grid-item-card} Python 3.11
:padding: 0 3 0 3
:margin: 0
*   amplify 1.0.0
*   pyqubo 1.4.0
*   dimod 0.12.14
```
``````

## Benchmark results

% workaround for showing Plotly figure
% https://github.com/readthedocs/sphinx_rtd_theme/issues/788
```{raw} html
<script src="https://cdnjs.cloudflare.com/ajax/libs/require.js/2.3.6/require.min.js" integrity="sha512-c3Nl8+7g4LMSTdrm621y7kf9v3SDPnhxLNhcjFJbKECVnmZHTdo+IRO05sNLTH/D3vA6u1X32ehoLC7WFVdheg==" crossorigin="anonymous" referrerpolicy="no-referrer"></script>
<script>require = requirejs;</script>
```

```{code-cell}
---
tags: [remove-input, remove-stderr]
---
import pandas as pd
import plotly.express as px
import plotly.io as pio

data = [[16,"Amplify",9.27E-05],
[25,"Amplify",6.88E-05],
[36,"Amplify",9.97E-05],
[49,"Amplify",0.000118732],
[64,"Amplify",0.000119686],
[81,"Amplify",0.000145555],
[100,"Amplify",0.000160456],
[121,"Amplify",0.00019753],
[144,"Amplify",0.000222921],
[169,"Amplify",0.000273347],
[196,"Amplify",0.000327587],
[225,"Amplify",0.00036025],
[256,"Amplify",0.000391603],
[289,"Amplify",0.000477433],
[324,"Amplify",0.000590563],
[361,"Amplify",0.00060606],
[400,"Amplify",0.000651956],
[441,"Amplify",0.000794888],
[484,"Amplify",0.000905752],
[529,"Amplify",0.001135111],
[576,"Amplify",0.001049519],
[625,"Amplify",0.001177669],
[676,"Amplify",0.001416564],
[729,"Amplify",0.001593351],
[784,"Amplify",0.001718521],
[841,"Amplify",0.001957536],
[900,"Amplify",0.001943946],
[961,"Amplify",0.00222528],
[1024,"Amplify",0.002306581],
[1089,"Amplify",0.002649426],
[1156,"Amplify",0.002997875],
[1225,"Amplify",0.003309131],
[1296,"Amplify",0.003594875],
[1369,"Amplify",0.003966093],
[1444,"Amplify",0.003832459],
[1521,"Amplify",0.004283309],
[1600,"Amplify",0.004448295],
[1681,"Amplify",0.004890323],
[1764,"Amplify",0.005404234],
[1849,"Amplify",0.006014228],
[1936,"Amplify",0.006367326],
[2025,"Amplify",0.007068276],
[2116,"Amplify",0.007801414],
[2209,"Amplify",0.008617878],
[2304,"Amplify",0.007824183],
[2401,"Amplify",0.008245826],
[2500,"Amplify",0.00896287],
[2601,"Amplify",0.009761214],
[2704,"Amplify",0.010263085],
[2809,"Amplify",0.011022687],
[2916,"Amplify",0.01189208],
[3025,"Amplify",0.013104916],
[3136,"Amplify",0.013679743],
[3249,"Amplify",0.014846921],
[3364,"Amplify",0.016150236],
[3481,"Amplify",0.017695904],
[3600,"Amplify",0.016322494],
[3721,"Amplify",0.017001271],
[3844,"Amplify",0.017937064],
[3969,"Amplify",0.018792868],
[4096,"Amplify",0.019935846],
[4225,"Amplify",0.021067262],
[4356,"Amplify",0.022222757],
[4489,"Amplify",0.029886603],
[4624,"Amplify",0.031201243],
[4761,"Amplify",0.032712698],
[4900,"Amplify",0.034661531],
[5041,"Amplify",0.037011147],
[5184,"Amplify",0.039380789],
[5329,"Amplify",0.041349769],
[5476,"Amplify",0.044507861],
[5625,"Amplify",0.043555617],
[5776,"Amplify",0.046607852],
[5929,"Amplify",0.047909617],
[6084,"Amplify",0.049533486],
[6241,"Amplify",0.051884532],
[6400,"Amplify",0.053924799],
[6561,"Amplify",0.056623578],
[6724,"Amplify",0.058390856],
[6889,"Amplify",0.061252356],
[7056,"Amplify",0.064158797],
[7225,"Amplify",0.072519898],
[7396,"Amplify",0.074694872],
[7569,"Amplify",0.078118205],
[7744,"Amplify",0.081175208],
[7921,"Amplify",0.084622383],
[8100,"Amplify",0.088214993],
[8281,"Amplify",0.092220187],
[8464,"Amplify",0.088975668],
[8649,"Amplify",0.093203306],
[8836,"Amplify",0.097578645],
[9025,"Amplify",0.108216286],
[9216,"Amplify",0.117958546],
[9409,"Amplify",0.127122879],
[9604,"Amplify",0.130149245],
[9801,"Amplify",0.135959864],
[10000,"Amplify",0.139675379],
[10201,"Amplify",0.143155932],
[10404,"Amplify",0.14694488],
[10609,"Amplify",0.151726484],
[10816,"Amplify",0.158475161],
[11025,"Amplify",0.163659215],
[11236,"Amplify",0.169449806],
[11449,"Amplify",0.173620582],
[11664,"Amplify",0.190505624],
[11881,"Amplify",0.187952518],
[12100,"Amplify",0.191333294],
[12321,"Amplify",0.197302461],
[12544,"Amplify",0.203752041],
[12769,"Amplify",0.210929394],
[12996,"Amplify",0.216718078],
[13225,"Amplify",0.246912003],
[13456,"Amplify",0.255573273],
[13689,"Amplify",0.263508439],
[13924,"Amplify",0.273116589],
[14161,"Amplify",0.300814986],
[14400,"Amplify",0.309835076],
[14641,"Amplify",0.316710234],
[14884,"Amplify",0.285605073],
[15129,"Amplify",0.33084178],
[15376,"Amplify",0.30218637],
[15625,"Amplify",0.348266721],
[15876,"Amplify",0.31750679],
[16129,"Amplify",0.364827394],
[16384,"Amplify",0.335345507],
[16641,"Amplify",0.342283607],
[16900,"Amplify",0.348634124],
[17161,"Amplify",0.359068751],
[17424,"Amplify",0.3700068],
[17689,"Amplify",0.37945807],
[17956,"Amplify",0.38861239],
[18225,"Amplify",0.398347497],
[18496,"Amplify",0.409527779],
[18769,"Amplify",0.419436455],
[19044,"Amplify",0.428367853],
[19321,"Amplify",0.44172287],
[19600,"Amplify",0.45586741],
[19881,"Amplify",0.466280937],
[20164,"Amplify",0.481732845],
[20449,"Amplify",0.492578387],
[20736,"Amplify",0.511633873],
[21025,"Amplify",0.526583552],
[21316,"Amplify",0.541424751],
[21609,"Amplify",0.558040142],
[21904,"Amplify",0.575971246],
[22201,"Amplify",0.592509627],
[22500,"Amplify",0.584789634],
[22801,"Amplify",0.594039917],
[23104,"Amplify",0.619269371],
[23409,"Amplify",0.620789766],
[23716,"Amplify",0.635715604],
[24025,"Amplify",0.645790458],
[24336,"Amplify",0.660801291],
[24649,"Amplify",0.676979303],
[24964,"Amplify",0.689066291],
[25281,"Amplify",0.702891946],
[25600,"Amplify",0.717083931],
[25921,"Amplify",0.732932329],
[26244,"Amplify",0.741057992],
[26569,"Amplify",0.842698693],
[26896,"Amplify",0.860516667],
[27225,"Amplify",0.875992417],
[27556,"Amplify",0.893065691],
[27889,"Amplify",0.908732057],
[28224,"Amplify",0.928986073],
[28561,"Amplify",0.946311355],
[28900,"Amplify",0.964772701],
[29241,"Amplify",0.891912341],
[29584,"Amplify",1.006009698],
[29929,"Amplify",1.024284363],
[30276,"Amplify",1.045701623],
[30625,"Amplify",0.974162817],
[30976,"Amplify",1.093782783],
[31329,"Amplify",1.016245723],
[31684,"Amplify",1.140674472],
[32041,"Amplify",1.068394184],
[32400,"Amplify",1.194435716],
[32761,"Amplify",1.118344307],
[33124,"Amplify",1.14394486],
[33489,"Amplify",1.168364167],
[33856,"Amplify",1.209633231],
[34225,"Amplify",1.231564522],
[34596,"Amplify",1.261775136],
[34969,"Amplify",1.305404782],
[35344,"Amplify",1.336910844],
[35721,"Amplify",1.199819207],
[36100,"Amplify",1.216382742],
[36481,"Amplify",1.237865567],
[36864,"Amplify",1.262149572],
[37249,"Amplify",1.282259941],
[37636,"Amplify",1.294066906],
[38025,"Amplify",1.316236019],
[38416,"Amplify",1.34753716],
[38809,"Amplify",1.36692071],
[39204,"Amplify",1.384322524],
[39601,"Amplify",1.411111593],
[40000,"Amplify",1.436032295],
[40401,"Amplify",1.454410315],
[40804,"Amplify",1.481553197],
[41209,"Amplify",1.504740357],
[41616,"Amplify",1.533810377],
[42025,"Amplify",1.558588624],
[42436,"Amplify",1.57389617],
[42849,"Amplify",1.606753826],
[43264,"Amplify",1.637432933],
[43681,"Amplify",1.665415764],
[44100,"Amplify",1.692073464],
[44521,"Amplify",1.711081505],
[44944,"Amplify",1.753840089],
[45369,"Amplify",1.774175406],
[45796,"Amplify",1.801724792],
[46225,"Amplify",1.839895129],
[46656,"Amplify",1.875293851],
[47089,"Amplify",1.910146832],
[47524,"Amplify",1.942101002],
[47961,"Amplify",1.980130911],
[48400,"Amplify",2.018701673],
[48841,"Amplify",2.051336408],
[49284,"Amplify",2.087353587],
[49729,"Amplify",2.125805259],
[50176,"Amplify",2.172478199],
[50625,"Amplify",2.202131033],
[51076,"Amplify",2.249419332],
[51529,"Amplify",2.294949889],
[51984,"Amplify",2.358826995],
[52441,"Amplify",2.400712729],
[52900,"Amplify",2.656062007],
[53361,"Amplify",2.708972573],
[53824,"Amplify",2.771580815],
[54289,"Amplify",2.828468561],
[54756,"Amplify",2.886733294],
[55225,"Amplify",2.947639704],
[55696,"Amplify",3.021421909],
[56169,"Amplify",3.066215634],
[56644,"Amplify",2.768004775],
[57121,"Amplify",2.778854489],
[57600,"Amplify",2.817772269],
[58081,"Amplify",2.852214098],
[58564,"Amplify",2.882239819],
[59049,"Amplify",2.918477654],
[59536,"Amplify",2.964296818],
[60025,"Amplify",2.998894572],
[60516,"Amplify",3.035671592],
[61009,"Amplify",3.069847107],
[61504,"Amplify",3.117627621],
[62001,"Amplify",3.155214548],
[62500,"Amplify",3.192190289],
[63001,"Amplify",2.929602981],
[63504,"Amplify",3.279174328],
[64009,"Amplify",3.009449363],
[64516,"Amplify",3.359084487],
[65025,"Amplify",3.077080488],
[65536,"Amplify",3.458454132],
[66049,"Amplify",3.172464728],
[66564,"Amplify",3.187776446],
[67081,"Amplify",3.235719085],
[67600,"Amplify",3.270784259],
[68121,"Amplify",3.329084158],
[68644,"Amplify",3.370325208],
[69169,"Amplify",3.415745616],
[69696,"Amplify",3.474949479],
[70225,"Amplify",3.504231334],
[70756,"Amplify",3.557719469],
[71289,"Amplify",3.618027449],
[71824,"Amplify",3.675520539],
[72361,"Amplify",3.724296093],
[72900,"Amplify",3.772123694],
[73441,"Amplify",3.832803845],
[73984,"Amplify",3.876357913],
[74529,"Amplify",3.939578652],
[75076,"Amplify",4.004696965],
[75625,"Amplify",4.059197068],
[76176,"Amplify",4.487405896],
[76729,"Amplify",4.163074374],
[77284,"Amplify",4.601295352],
[77841,"Amplify",4.312493324],
[78400,"Amplify",4.363325953],
[78961,"Amplify",4.821487069],
[79524,"Amplify",4.534025431],
[80089,"Amplify",4.558062196],
[80656,"Amplify",4.636669636],
[81225,"Amplify",4.729419589],
[81796,"Amplify",4.832344174],
[82369,"Amplify",4.897665977],
[82944,"Amplify",4.992205262],
[83521,"Amplify",5.068235278],
[84100,"Amplify",5.127729535],
[84681,"Amplify",5.253166556],
[85264,"Amplify",5.334953547],
[85849,"Amplify",5.422147393],
[86436,"Amplify",5.520197272],
[87025,"Amplify",5.611216664],
[87616,"Amplify",5.732600331],
[88209,"Amplify",5.838080764],
[88804,"Amplify",5.919652462],
[89401,"Amplify",6.058257937],
[90000,"Amplify",5.140513897],
[90601,"Amplify",5.152812719],
[91204,"Amplify",5.239851356],
[91809,"Amplify",5.277008057],
[92416,"Amplify",5.376128674],
[93025,"Amplify",5.411436439],
[93636,"Amplify",5.506927371],
[94249,"Amplify",5.54893899],
[94864,"Amplify",5.64994812],
[95481,"Amplify",5.68894577],
[96100,"Amplify",5.71973896],
[96721,"Amplify",5.815832257],
[97344,"Amplify",5.910229802],
[97969,"Amplify",5.954457402],
[98596,"Amplify",5.972197771],
[99225,"Amplify",5.926132679],
[99856,"Amplify",5.902313232],
[100489,"Amplify",5.937704325],
[1024,"PyQUBO",0.29150 ],
[1024,"dimod BQM (index)",0.06412],
[1024,"dimod BQM (symbol)",1.087],
[1024,"dimod CQM",0.8959],
[10000,"PyQUBO",9.87900 ],
[10000,"dimod BQM (index)",2.126],
[10000,"dimod BQM (symbol)",32.77],
[10000,"dimod CQM",26.93],
[100489,"PyQUBO",349.00000 ],
[100489,"dimod BQM (index)",83.1],
[100489,"dimod BQM (symbol)",1062],
[100489,"dimod CQM",855],
[16,"Amplify 0.12.1",0.000173092],
[25,"Amplify 0.12.1",0.000225186],
[36,"Amplify 0.12.1",0.00030756],
[49,"Amplify 0.12.1",0.000432253],
[64,"Amplify 0.12.1",0.000560164],
[81,"Amplify 0.12.1",0.00068748],
[100,"Amplify 0.12.1",0.000941277],
[121,"Amplify 0.12.1",0.001128197],
[144,"Amplify 0.12.1",0.001369357],
[169,"Amplify 0.12.1",0.001817465],
[196,"Amplify 0.12.1",0.002255797],
[225,"Amplify 0.12.1",0.00243783],
[256,"Amplify 0.12.1",0.003099918],
[289,"Amplify 0.12.1",0.003789902],
[324,"Amplify 0.12.1",0.004154086],
[361,"Amplify 0.12.1",0.00454855],
[400,"Amplify 0.12.1",0.005934238],
[441,"Amplify 0.12.1",0.006604433],
[484,"Amplify 0.12.1",0.007256269],
[529,"Amplify 0.12.1",0.007932305],
[576,"Amplify 0.12.1",0.009629846],
[625,"Amplify 0.12.1",0.010630012],
[676,"Amplify 0.12.1",0.01249373],
[729,"Amplify 0.12.1",0.012948513],
[784,"Amplify 0.12.1",0.014122844],
[841,"Amplify 0.12.1",0.015902877],
[900,"Amplify 0.12.1",0.017157316],
[961,"Amplify 0.12.1",0.020729542],
[1024,"Amplify 0.12.1",0.022745728],
[1089,"Amplify 0.12.1",0.024587035],
[1156,"Amplify 0.12.1",0.025656343],
[1225,"Amplify 0.12.1",0.027319312],
[1296,"Amplify 0.12.1",0.029599071],
[1369,"Amplify 0.12.1",0.031652808],
[1444,"Amplify 0.12.1",0.038052201],
[1521,"Amplify 0.12.1",0.040365696],
[1600,"Amplify 0.12.1",0.045632362],
[1681,"Amplify 0.12.1",0.046342373],
[1764,"Amplify 0.12.1",0.048691511],
[1849,"Amplify 0.12.1",0.051237822],
[1936,"Amplify 0.12.1",0.054391742],
[2025,"Amplify 0.12.1",0.057870388],
[2116,"Amplify 0.12.1",0.061783791],
[2209,"Amplify 0.12.1",0.065680265],
[2304,"Amplify 0.12.1",0.07783246],
[2401,"Amplify 0.12.1",0.082075715],
[2500,"Amplify 0.12.1",0.086981773],
[2601,"Amplify 0.12.1",0.089370251],
[2704,"Amplify 0.12.1",0.094569921],
[2809,"Amplify 0.12.1",0.098874569],
[2916,"Amplify 0.12.1",0.102502465],
[3025,"Amplify 0.12.1",0.107627749],
[3136,"Amplify 0.12.1",0.119086742],
[3249,"Amplify 0.12.1",0.130530715],
[3364,"Amplify 0.12.1",0.133724928],
[3481,"Amplify 0.12.1",0.139126182],
[3600,"Amplify 0.12.1",0.161703467],
[3721,"Amplify 0.12.1",0.1691221],
[3844,"Amplify 0.12.1",0.176939368],
[3969,"Amplify 0.12.1",0.185654998],
[4096,"Amplify 0.12.1",0.191904783],
[4225,"Amplify 0.12.1",0.196415663],
[4356,"Amplify 0.12.1",0.2049402],
[4489,"Amplify 0.12.1",0.212720633],
[4624,"Amplify 0.12.1",0.220281243],
[4761,"Amplify 0.12.1",0.228739738],
[4900,"Amplify 0.12.1",0.237228632],
[5041,"Amplify 0.12.1",0.245768547],
[5184,"Amplify 0.12.1",0.255371213],
[5329,"Amplify 0.12.1",0.265177727],
[5476,"Amplify 0.12.1",0.274446011],
[5625,"Amplify 0.12.1",0.284912825],
[5776,"Amplify 0.12.1",0.330538154],
[5929,"Amplify 0.12.1",0.338934541],
[6084,"Amplify 0.12.1",0.34914577],
[6241,"Amplify 0.12.1",0.360873222],
[6400,"Amplify 0.12.1",0.377599359],
[6561,"Amplify 0.12.1",0.382658601],
[6724,"Amplify 0.12.1",0.390755177],
[6889,"Amplify 0.12.1",0.402357817],
[7056,"Amplify 0.12.1",0.414294362],
[7225,"Amplify 0.12.1",0.427267909],
[7396,"Amplify 0.12.1",0.43998313],
[7569,"Amplify 0.12.1",0.453189135],
[7744,"Amplify 0.12.1",0.468515277],
[7921,"Amplify 0.12.1",0.48476541],
[8100,"Amplify 0.12.1",0.502392173],
[8281,"Amplify 0.12.1",0.522226691],
[8464,"Amplify 0.12.1",0.539714694],
[8649,"Amplify 0.12.1",0.557114601],
[8836,"Amplify 0.12.1",0.573114276],
[9025,"Amplify 0.12.1",0.663230777],
[9216,"Amplify 0.12.1",0.680469036],
[9409,"Amplify 0.12.1",0.698078036],
[9604,"Amplify 0.12.1",0.717182279],
[9801,"Amplify 0.12.1",0.734380126],
[10000,"Amplify 0.12.1",0.755874157],
[10201,"Amplify 0.12.1",0.785692096],
[10404,"Amplify 0.12.1",0.767130852],
[10609,"Amplify 0.12.1",0.796575427],
[10816,"Amplify 0.12.1",0.816874385],
[11025,"Amplify 0.12.1",0.833752275],
[11236,"Amplify 0.12.1",0.856078625],
[11449,"Amplify 0.12.1",0.877023697],
[11664,"Amplify 0.12.1",0.898231387],
[11881,"Amplify 0.12.1",0.919370532],
[12100,"Amplify 0.12.1",0.937847376],
[12321,"Amplify 0.12.1",0.966069698],
[12544,"Amplify 0.12.1",0.982683301],
[12769,"Amplify 0.12.1",1.004372358],
[12996,"Amplify 0.12.1",1.075474381],
[13225,"Amplify 0.12.1",1.076647758],
[13456,"Amplify 0.12.1",1.10104537],
[13689,"Amplify 0.12.1",1.125991702],
[13924,"Amplify 0.12.1",1.153831124],
[14161,"Amplify 0.12.1",1.181185603],
[14400,"Amplify 0.12.1",1.378538609],
[14641,"Amplify 0.12.1",1.40635848],
[14884,"Amplify 0.12.1",1.436725616],
[15129,"Amplify 0.12.1",1.468566775],
[15376,"Amplify 0.12.1",1.501669049],
[15625,"Amplify 0.12.1",1.539886475],
[15876,"Amplify 0.12.1",1.582930803],
[16129,"Amplify 0.12.1",1.611595273],
[16384,"Amplify 0.12.1",1.609653711],
[16641,"Amplify 0.12.1",1.637283802],
[16900,"Amplify 0.12.1",1.664260149],
[17161,"Amplify 0.12.1",1.686968327],
[17424,"Amplify 0.12.1",1.720116615],
[17689,"Amplify 0.12.1",1.748004556],
[17956,"Amplify 0.12.1",1.782075763],
[18225,"Amplify 0.12.1",1.817974448],
[18496,"Amplify 0.12.1",1.847237468],
[18769,"Amplify 0.12.1",1.882803679],
[19044,"Amplify 0.12.1",1.924093127],
[19321,"Amplify 0.12.1",1.954374909],
[19600,"Amplify 0.12.1",1.991669774],
[19881,"Amplify 0.12.1",2.032533884],
[20164,"Amplify 0.12.1",2.073743939],
[20449,"Amplify 0.12.1",2.1244874],
[20736,"Amplify 0.12.1",2.157899141],
[21025,"Amplify 0.12.1",2.213461041],
[21316,"Amplify 0.12.1",2.25191927],
[21609,"Amplify 0.12.1",2.295990109],
[21904,"Amplify 0.12.1",2.348167777],
[22201,"Amplify 0.12.1",2.390437484],
[22500,"Amplify 0.12.1",2.4483459],
[22801,"Amplify 0.12.1",2.830868244],
[23104,"Amplify 0.12.1",2.876840115],
[23409,"Amplify 0.12.1",2.920388937],
[23716,"Amplify 0.12.1",2.975622416],
[24025,"Amplify 0.12.1",3.02257967],
[24336,"Amplify 0.12.1",3.074261427],
[24649,"Amplify 0.12.1",3.138824463],
[24964,"Amplify 0.12.1",3.185057521],
[25281,"Amplify 0.12.1",3.252398014],
[25600,"Amplify 0.12.1",3.27671814],
[25921,"Amplify 0.12.1",3.207731485],
[26244,"Amplify 0.12.1",3.324149132],
[26569,"Amplify 0.12.1",3.385492921],
[26896,"Amplify 0.12.1",3.440587401],
[27225,"Amplify 0.12.1",3.497018337],
[27556,"Amplify 0.12.1",3.552553654],
[27889,"Amplify 0.12.1",3.627676368],
[28224,"Amplify 0.12.1",3.677097082],
[28561,"Amplify 0.12.1",3.739594102],
[28900,"Amplify 0.12.1",3.79697752],
[29241,"Amplify 0.12.1",3.875931025],
[29584,"Amplify 0.12.1",3.939109564],
[29929,"Amplify 0.12.1",3.998035073],
[30276,"Amplify 0.12.1",4.067542434],
[30625,"Amplify 0.12.1",4.140975714],
[30976,"Amplify 0.12.1",4.211170554],
[31329,"Amplify 0.12.1",4.291448593],
[31684,"Amplify 0.12.1",4.379054308],
[32041,"Amplify 0.12.1",4.461811423],
[32400,"Amplify 0.12.1",4.562819123],
[32761,"Amplify 0.12.1",4.678703427],
[33124,"Amplify 0.12.1",4.72806251],
[33489,"Amplify 0.12.1",4.790589809],
[33856,"Amplify 0.12.1",4.850347638],
[34225,"Amplify 0.12.1",4.924911857],
[34596,"Amplify 0.12.1",5.010771036],
[34969,"Amplify 0.12.1",5.08455205],
[35344,"Amplify 0.12.1",5.17099607],
[35721,"Amplify 0.12.1",5.923170209],
[36100,"Amplify 0.12.1",6.039165258],
[36481,"Amplify 0.12.1",6.114944577],
[36864,"Amplify 0.12.1",6.221640944],
[37249,"Amplify 0.12.1",6.299827933],
[37636,"Amplify 0.12.1",6.360730886],
[38025,"Amplify 0.12.1",6.440552711],
[38416,"Amplify 0.12.1",6.535546541],
[38809,"Amplify 0.12.1",6.648950815],
[39204,"Amplify 0.12.1",6.70527482],
[39601,"Amplify 0.12.1",6.83101213],
[40000,"Amplify 0.12.1",6.952670097],
[40401,"Amplify 0.12.1",6.988735676],
[40804,"Amplify 0.12.1",6.878164291],
[41209,"Amplify 0.12.1",6.95722425],
[41616,"Amplify 0.12.1",7.045882702],
[42025,"Amplify 0.12.1",7.262242675],
[42436,"Amplify 0.12.1",7.344267607],
[42849,"Amplify 0.12.1",7.465735555],
[43264,"Amplify 0.12.1",7.566412807],
[43681,"Amplify 0.12.1",7.684015036],
[44100,"Amplify 0.12.1",7.824592471],
[44521,"Amplify 0.12.1",7.908399701],
[44944,"Amplify 0.12.1",8.021014214],
[45369,"Amplify 0.12.1",8.158521414],
[45796,"Amplify 0.12.1",8.247758746],
[46225,"Amplify 0.12.1",8.417805791],
[46656,"Amplify 0.12.1",8.521734357],
[47089,"Amplify 0.12.1",8.6638726],
[47524,"Amplify 0.12.1",8.78726995],
[47961,"Amplify 0.12.1",8.89971149],
[48400,"Amplify 0.12.1",9.042147994],
[48841,"Amplify 0.12.1",9.141168594],
[49284,"Amplify 0.12.1",9.294381857],
[49729,"Amplify 0.12.1",9.409124613],
[50176,"Amplify 0.12.1",9.586859941],
[50625,"Amplify 0.12.1",9.678881764],
[51076,"Amplify 0.12.1",9.802509785],
[51529,"Amplify 0.12.1",9.909022331],
[51984,"Amplify 0.12.1",10.07336318],
[52441,"Amplify 0.12.1",10.3845737],
[52900,"Amplify 0.12.1",10.54887342],
[53361,"Amplify 0.12.1",10.67626846],
[53824,"Amplify 0.12.1",10.84283984],
[54289,"Amplify 0.12.1",10.96669078],
[54756,"Amplify 0.12.1",11.12514305],
[55225,"Amplify 0.12.1",11.26253366],
[55696,"Amplify 0.12.1",11.43190312],
[56169,"Amplify 0.12.1",11.55493939],
[56644,"Amplify 0.12.1",13.11510456],
[57121,"Amplify 0.12.1",13.24709392],
[57600,"Amplify 0.12.1",13.37448502],
[58081,"Amplify 0.12.1",13.54280674],
[58564,"Amplify 0.12.1",13.66189134],
[59049,"Amplify 0.12.1",13.8125515],
[59536,"Amplify 0.12.1",13.99586904],
[60025,"Amplify 0.12.1",14.1542697],
[60516,"Amplify 0.12.1",14.30214226],
[61009,"Amplify 0.12.1",14.4767431],
[61504,"Amplify 0.12.1",14.61799502],
[62001,"Amplify 0.12.1",14.78278649],
[62500,"Amplify 0.12.1",14.98609567],
[63001,"Amplify 0.12.1",15.18546569],
[63504,"Amplify 0.12.1",15.45340025],
[64009,"Amplify 0.12.1",15.48715806],
[64516,"Amplify 0.12.1",15.56969213],
[65025,"Amplify 0.12.1",15.45804846],
[65536,"Amplify 0.12.1",15.93097901],
[66049,"Amplify 0.12.1",15.68845284],
[66564,"Amplify 0.12.1",15.79248047],
[67081,"Amplify 0.12.1",15.94654655],
[67600,"Amplify 0.12.1",16.07540512],
[68121,"Amplify 0.12.1",16.26151907],
[68644,"Amplify 0.12.1",16.39928234],
[69169,"Amplify 0.12.1",16.53768623],
[69696,"Amplify 0.12.1",16.7533704],
[70225,"Amplify 0.12.1",16.91872954],
[70756,"Amplify 0.12.1",17.08070564],
[71289,"Amplify 0.12.1",17.23229527],
[71824,"Amplify 0.12.1",17.42308593],
[72361,"Amplify 0.12.1",17.62183189],
[72900,"Amplify 0.12.1",17.81020045],
[73441,"Amplify 0.12.1",18.02867186],
[73984,"Amplify 0.12.1",18.19259679],
[74529,"Amplify 0.12.1",18.41549516],
[75076,"Amplify 0.12.1",18.5574497],
[75625,"Amplify 0.12.1",18.79428339],
[76176,"Amplify 0.12.1",18.93877161],
[76729,"Amplify 0.12.1",19.18607318],
[77284,"Amplify 0.12.1",19.36053765],
[77841,"Amplify 0.12.1",19.55815291],
[78400,"Amplify 0.12.1",19.78280187],
[78961,"Amplify 0.12.1",19.99346662],
[79524,"Amplify 0.12.1",20.16756022],
[80089,"Amplify 0.12.1",20.46861732],
[80656,"Amplify 0.12.1",20.66470444],
[81225,"Amplify 0.12.1",20.87595904],
[81796,"Amplify 0.12.1",21.14638197],
[82369,"Amplify 0.12.1",21.38422775],
[82944,"Amplify 0.12.1",21.61783504],
[83521,"Amplify 0.12.1",21.76913881],
[84100,"Amplify 0.12.1",22.01870918],
[84681,"Amplify 0.12.1",22.25100243],
[85264,"Amplify 0.12.1",22.48969519],
[85849,"Amplify 0.12.1",22.73059988],
[86436,"Amplify 0.12.1",23.00052762],
[87025,"Amplify 0.12.1",23.2231735],
[87616,"Amplify 0.12.1",23.53701568],
[88209,"Amplify 0.12.1",23.76956689],
[88804,"Amplify 0.12.1",24.03883123],
[89401,"Amplify 0.12.1",24.3881712],
[90000,"Amplify 0.12.1",27.47148049],
[90601,"Amplify 0.12.1",27.6653893],
[91204,"Amplify 0.12.1",27.91433907],
[91809,"Amplify 0.12.1",28.17641211],
[92416,"Amplify 0.12.1",28.43760538],
[93025,"Amplify 0.12.1",28.6461637],
[93636,"Amplify 0.12.1",28.9519031],
[94249,"Amplify 0.12.1",29.30131245],
[94864,"Amplify 0.12.1",29.59358513],
[95481,"Amplify 0.12.1",29.7363137],
[96100,"Amplify 0.12.1",30.06596696],
[96721,"Amplify 0.12.1",30.28914189],
[97344,"Amplify 0.12.1",30.63115132],
[97969,"Amplify 0.12.1",30.85390604],
[98596,"Amplify 0.12.1",31.153736],
[99225,"Amplify 0.12.1",31.47998548],
[99856,"Amplify 0.12.1",31.79635715],
[100489,"Amplify 0.12.1",32.07418537]]

pio.renderers.default = 'notebook'
df = pd.DataFrame(data, columns=["num variables", "formulation", "execution time (s)"])
fig = px.scatter(
    df, x="num variables", y="execution time (s)", color="formulation", log_x=True, log_y=True
)
fig.update_traces(visible="legendonly", selector=dict(name="Amplify 0.12.1"))
fig.show()
```

### 32 cities (1,024 binary variables)

```{list-table}
:width: 100%
:widths: 1 1 1 1
:header-rows: 1

*   - Formulation
    - Model construction
    - QUBO construction
    - Total
*   - [Amplify](#amplify-tsp-bench)
    - **1.309 ms**
    - **0.998 ms**
    - **2.307 ms** 🏆
*   - [PyQUBO](pyqubo-tsp-bench)
    - 266.8 ms
    - 24.63 ms
    - 291.5 ms (x126.3)
*   - [dimod BQM (index)](#dimod-bqm-idx-tsp-bench)
    - 22.53 ms
    - 41.58 ms
    - 64.12 ms (x27.8)
*   - [dimod BQM (symbol)](#dimod-bqm-sym-tsp-bench)
    - 1028 ms
    - 58.48 ms
    - 1087 ms (x471.2)
*   - [dimod CQM](#dimod-cqm-tsp-bench)
    - 895.9 ms
    - N/A ms
    - 895.9 ms (x388.4)
```

### 100 cities (10,000 binary variables)

```{list-table}
:width: 100%
:widths: 1 1 1 1
:header-rows: 1

*   - Formulation
    - Model construction
    - QUBO construction
    - Total
*   - [Amplify](#amplify-tsp-bench)
    - **0.063 s**
    - **0.077 s**
    - **0.140 s** 🏆
*   - [PyQUBO](pyqubo-tsp-bench)
    - 8.519 s
    - 1.360 s
    - 9.879 s (x70.7)
*   - [dimod BQM (index)](#dimod-bqm-idx-tsp-bench)
    - 0.706 s
    - 1.419 s
    - 2.126 s (x15.2)
*   - [dimod BQM (symbol)](#dimod-bqm-sym-tsp-bench)
    - 30.83 s
    - 1.935 s
    - 32.77 s (x234.6)
*   - [dimod CQM](#dimod-cqm-tsp-bench)
    - 26.93 s
    - N/A
    - 26.93 s (x192.8)
```

### 317 cities (100,489 binary variables)

```{list-table}
:width: 100%
:widths: 1 1 1 1
:header-rows: 1

*   - Formulation
    - Model construction
    - QUBO construction
    - Total
*   - [Amplify](#amplify-tsp-bench)
    - **2.992 s**
    - **2.946 s**
    - **5.938 s** 🏆
*   - [PyQUBO](pyqubo-tsp-bench)
    - 279.7 s
    - 69.23 s
    - 349.0 s (x58.8)
*   - [dimod BQM (index)](#dimod-bqm-idx-tsp-bench)
    - 31.05 s
    - 52.05 s
    - 83.10 s (x14.0)
*   - [dimod BQM (symbol)](#dimod-bqm-sym-tsp-bench)
    - 991.5 s
    - 70.83 s
    - 1062 s (x178.9)
*   - [dimod CQM](#dimod-cqm-tsp-bench)
    - 855.3 s
    - N/A
    - 855.3 s (x144.0)
```