How to convert a combinatorial optimization problem into a problem hamiltonian

Question

I want to ask how I can convert any combinatorial optimization problem into a Problem Hamiltonian, since such a conversion is needed in order to solve an optimization problem on quantum hardware (e.g. IBM's using Qiskit).

Or is there any way where I can load an LP file and then convert it into problem Hamiltonian?

Answer 1

This video tutorial is a very good starting point to the subject.

Then you can go through the paper "Ising formulations of many NP problems" by Lucas for more advanced mappings.

Answer 2

You can convert pyomo (an open-source Python library for defining and solving classical optimization problems) problems to Hamiltonian problems using Classiq. Check this user guide to see how to do it. You also have a notebook teaching it here.

In the Git Public repo it is in https://github.com/Classiq/classiq-library/tree/main/applications/optimization

Generally speaking, once you define a Pyomo ConcreteModel (contains objective function and constraints), you can create a qmod based on it using construct_combinatorial_optimization_model which is a shortcut for explicitly writing the entire model. It calculates the Hamiltonian for you, builds a proper ansatz, and defines the QAOA for this problem.

So for example:

import pandas as pd
import pyomo.environ as pyo
from classiq import (
    construct_combinatorial_optimization_model,
    execute,
    show,
    synthesize,
)
from classiq.applications.combinatorial_optimization import OptimizerConfig, QAOAConfig
Application object definitions and fields
application_object = pyo.ConcreteModel()
application_object.x = pyo.Var(
    [1, 2],  # variables names
    domain=pyo.NonNegativeIntegers,  # variables type
    bounds=(0, 3),  # variables range
)
application_object.cost = pyo.Objective(
    expr=3 * application_object.x[1] + 2 * application_object.x[2]
)
application_object.constraint = pyo.Constraint(
    expr=3 * application_object.x[1] + application_object.x[2] >= 2
)
application_object.pprint()
going quantum - QAOA preferences
qaoa_config = QAOAConfig(num_layers=1)  # QAOA sub-circuit number of repetitions
defining the model
model = construct_combinatorial_optimization_model(
    pyo_model=application_level_object,
    qaoa_config=qaoa_config,
)
synthesizing a quantum circuit
qprog = synthesize(model)
executing the circuit to solve the optimzation problem:
res = execute(qprog).result()
post-processing the results:
from classiq.applications.combinatorial_optimization import (
    get_optimization_solution_from_pyo,
)
solution = get_optimization_solution_from_pyo(
    application_level_object,
    vqe_result=res[0].value,
    penalty_energy=qaoa_config.penalty_energy,
)
optimization_result = pd.DataFrame.from_records(solution)
optimization_result.sort_values(by="cost", ascending=True).head(5)
idx = optimization_result.cost.idxmin()
print(
    "x =", optimization_result.solution[idx], ", cost =", optimization_result.cost[idx]
)
view and analyze the quantum circuit:
show(qprog)

Will give this circuit in platform.classiq.io:

And this solution

x = [1, 0] , cost = 2.9999999999999964

If you need the qiskit circuit object of, use this command to get the QASM:

QuantumProgram.parse_raw(qprog).transpiled_circuit.qasm

And convert it with the answer here

In the code I attached, you can also see the execution, and you can choose from the list of backends (all that are in IBM, Azure, AWS, NVIDIA GPU Simulator cloud)

Disclaimer - I am an engineer at Classiq

Answer 3

Qiskit Optimization has a QuadraticProgram object that can read_from_lp_file and can then be converted to_ising Hamiltonian. This LP file reading does need CPLEX installed, as the docs note, but if you are using LP files I imagine you have that. The docs also have installation info, tutorials, the API ref etc.