Creating and Solving Custom Optimization Problems using QUBOs
In this tutorial, we'll explore how you can use LunaSolve to solve custom Quadratic Unconstrained Binary Optimization (QUBO) problems with the QAGA+ algorithm, a hybrid QUBO-solver developed by Aqarios. This guide is perfect for those who have created their own optimization problems and are looking to harness the power of quantum computing. It's also ideal for anyone wishing to keep their use case confidential while benefiting from advanced quantum solutions.
Before we dive in, make sure you have the Luna Python SDK installed.
Upon completing this tutorial, you will be able to:
- Formulate your optimization problem in QUBO format.
- Utilize hybrid QAGA+ algorithm on quantum hardware for solving your QUBO.
- Retrieve and understand your optimization results.
1. Preparing Your QUBO
First, you'll need to locally convert any optimization problem into a QUBO format. This process involves formulating the problem in a way that quantum algorithms can efficiently process, focusing on binary variables and their interactions. A QUBO can be represented in two ways: a matrix, represented as a list of lists, or a BinaryQuadraticModel (BQM) from the dimod package from D-Wave Ocean. While you can upload QUBO matrices, these will be transformed into a BQM afterwards.
Once created, you can directly submit the QUBO to LunaSolve.
# Load the LunaSolve package
from luna_sdk import LunaSolve
from luna_sdk.schemas.optimization_formats.bqm import BQMSchema
# Initialize LunaSolve with your API key
ls = LunaSolve(api_key="<LUNA_API_KEY>")
# Define your QUBO matrix as a list of lists
qubo_matrix = [
[4, 0, 0, 0, -2],
[0, -2, 0, 1, 0],
[0, 0, 6, -3, 0],
[0, 1, -3, 2, 0],
[-2, 0, 0, 0, 5]
]
# Upload your QUBO to LunaSolve
optimization = ls.optimization.create_from_qubo(name="My QUBO", matrix=qubo_matrix)
# Alternatively, define your QUBO as BQM
bqm_data = {
"linear": {"0": 4.0, "1": -2.0, "2": 6.0, "3": 2.0, "4": 5.0},
"quadratic": {("3", "1"): 2.0, ("3", "2"): -6.0, ("4", "0"): -4.0},
"vartype": "BINARY"
}
bqm = BQMSchema(**bqm_data)
# Upload your BQM to LunaSolve
optimization = ls.optimization.create_from_bqm(name="My BQM", bqm=bqm)
2. Solving the QUBO Problem on Quantum Hardware
LunaSolve provides a wide selection of algorithms pre-configured to address a variety of optimization challenges. For the purpose of this guide, we'll focus on using the QAGA+ solver. This is a hybrid algorithm developed by Aqarios that makes use of both traditional computing and Quantum Annealers, specifically from D-Wave Systems, to find solutions.
The QAGA+ algorithm is versatile, offering many settings to tweak its performance for different kinds of optimization tasks. To keep things straightforward in this tutorial, we'll adjust just three key parameters commonly used in evolutionary algorithms:
- p_size: This is the population size, which affects how many solutions are considered in each step of the algorithm.
- mut_rate: The mutation rate determines the chance of changes occurring in each solution per iteration.
- rec_rate: The recommendation rate decides how many pairings are made for creating new solutions.
For real-world applications, it's a good idea to explore all the adjustable parameters to tailor the algorithm to your specific problem.
Next up, we'll dive into solving our QUBO matrix using QAGA+. LunaSolve offers the option to securely store your token, removing the need to provide it with each request as token_type=inline as in the previous section. This feature allows you to reuse your token across multiple solve calls. In this tutorial, we’ll set up your D-Wave access token within the LunaSolve platform.
Note: Storing tokens works the same way for other hardware providers. For IBM, QPU tokens currently cannot be stored due to specific usage guidelines. Therefore, when using IBM hardware, keep using token_type=inline. See User Guide - QPU Tokens for more details about token types in LunaSolve.
Note: The name of your token has to be unique. You might refer to it later again, so make sure to select a name you can remember.
# Set your token to access D-Wave's hardware
ls.qpu_token.create(
name="My D-Wave Token",
provider="dwave",
token="<TOKEN>",
token_type="personal"
)
Now, you can configure the solve job, reference your token previously uploaded to LunaSolve and specify its parameters to move forward with solving the problem.
from luna_sdk.schemas.qpu_token import QpuToken, TokenProvider
# Solve the QUBO using the QAGA+ algorithm and retrieve a job
job = ls.solution.create(
optimization_id=optimization.id,
solver_name="QAGA+",
provider="dwave",
qpu_tokens=TokenProvider(
dwave=QpuToken(
source="personal",
name="My D-Wave Token"
)
),
solver_parameters={
'p_size': 40,
'mut_rate': 0.3,
'rec_rate': 2
}
)
3. Retrieving Your Solution
Since certain algorithms, particularly those executed on quantum hardware, may require some time for completion, we have designed the process to be asynchronous. When you request a solution, LunaSolve will manage all the necessary steps in the background. You're free to continue with other tasks while the computation is underway, returning at your convenience when it's finished.
# After the execution of your algorithm has been finished, retrieve your solution
solution = ls.solution.get(job.id)
print(solution.head)
Output:
--------------------------------------------------------------------------------
META DATA:
--------------------------------------------------------------------------------
id: 664dca668bcad25f8e115241
name: Your_Solution_Name
created_date: 2024-05-22 12:35:18.836000
created_by: 66291cab401df553a5f5ccd6
modified_date: 2024-05-22 12:35:20.943000
modified_by: None
error_message: None
params:
p_size: 40
p_inc_num: 0
p_max: -1
pct_random_states: 0
mut_rate: 0
rec_rate: 2
rec_method: one_point_crossover
num_sweeps: 1000
num_sweeps_inc_factor: 1
num_sweeps_inc_max: -1
beta_range_type: default
beta_range: beta_range
target: None
atol: 0
rtol: 0
timeout: 5
max_iter: -1
max_consistent_iters: -1
return_overhead: False
use_qpu: True
runtime:
total: 0.0006803750002291054
qpu: 0.0
sense: SenseEnum.MIN
solver: QAGA+
provider: dwave
status: StatusEnum.DONE
optimization:
id: 664dc9142836c25997a5ea7c
name: My BQM
created_date: 2024-05-22 12:29:40.184000
created_by: 66291cab401df553a5f5ccd6
modified_date: None
modified_by: None
use_case_name: None
params: None
representation: None
--------------------------------------------------------------------------------
RESULTS:
--------------------------------------------------------------------------------
40 results found. Displaying first 5 results.
Result 1:
{'sample': {'0': 0.0, '1': 1.0, '2': 1.0, '3': 0.0, '4': 0.0}, 'obj_value': 4.0, 'feasible': True, 'constraints': {}}
Result 2:
{'sample': {'0': 1.0, '1': 1.0, '2': 0.0, '3': 0.0, '4': 1.0}, 'obj_value': 3.0, 'feasible': True, 'constraints': {}}
Result 3:
{'sample': {'0': 1.0, '1': 0.0, '2': 0.0, '3': 1.0, '4': 0.0}, 'obj_value': 6.0, 'feasible': True, 'constraints': {}}
Result 4:
{'sample': {'0': 1.0, '1': 1.0, '2': 1.0, '3': 1.0, '4': 1.0}, 'obj_value': 7.0, 'feasible': True, 'constraints': {}}
Result 5:
{'sample': {'0': 1.0, '1': 1.0, '2': 1.0, '3': 0.0, '4': 1.0}, 'obj_value': 9.0, 'feasible': True, 'constraints': {}}
....
--------------------------------------------------------------------------------
DWAVE META DATA:
--------------------------------------------------------------------------------
timing:
network_overhead: 0.0
embedding_overhead: 1.9572877089995018
Some algorithms, such as QAGA+, calculate several solutions for your problem. You can also simply retrieve the best solutions from these options.
best_result = ls.solution.get_best_result(solution)
print(best_result)
sample:
0: 0.0
1: 1.0
2: 0.0
3: 0.0
4: 0.0
obj_value: -2.0
feasible: True
constraints:
Other Optimization Formats
LunaSolve supports not only QUBOs but also many other optimization formats. For more details, refer to our user guide on available optimization formats.