Formulating and Solving Optimizations Problems via the Use Case Library
In this tutorial, you're going to set up an optimization problem using our ready-to-use use case library and solve it using the Quantum Approximate Optimization Algorithm (QAOA). All our use cases are set up to work well with quantum algorithms from the start. This guide is particularly useful for anyone who hasn't prepared their problems for quantum solutions yet or wants to investigate how algorithms perform for specific use cases on quantum hardware.
Before we begin, ensure you have installed the Luna Python SDK along with additional dependencies:
pip install networkx pandas numpy
Upon completing this tutorial, you will be able to:
- Develop an optimization model for the Traveling Salesperson Problem and for Portfolio Optimization using our use case library.
- Solve the optimization on real quantum hardware using QAOA and using the classical heuristic Simulated Annealing.
- Interpret your results in an easily understandable manner.
We strongly recommend to go through all examples to acquire a comprehensive overview of all capabilities of LunaSolve.
Example: Distributing wholesale products throughout Germany
Imagine you're in charge of coordinating the delivery of wholesale products across Germany efficiently. Your goal is to reach retailers in the seven biggest German cities, delivering all products at once using the shortest route to cut down on transport costs.
This situation is what's known as the Traveling Salesman Problem (TSP), a well-known challenge in optimization studies. It's widely used in fields like routing, logistics, DNA sequencing, and even astronomy, though sometimes the details of the problem are tweaked a bit.
LunaSolve makes it easy to set up and solve a TSP without needing to dive into complicated preparations. To learn more about how this works, you can check out the TSP Use Case section on our website.
Basically, the TSP is described by a weighted graph, where each node is a city, and each edge is the distance between cities.
1. Creating a TSP Instance
When creating a graph for the TSP, LunaSolve can work with either a nested dictionary or a graph built using networkx. For the sake of simplicity and making the code easier to read, we recommend using networkx.
In most scenarios, your graph data would likely be sourced from other business applications. However, for the purpose of this tutorial, we will create the graph from the ground up.
import networkx as nx
# Create an empty graph using networkx
graph = nx.Graph()
# Define the cities we want to visit
cities = ['Berlin', 'Hamburg', 'Munich', 'Cologne']
# Add the cities as nodes in our graph
graph.add_nodes_from(cities)
# Define the distances between each city
edges = [
('Berlin', 'Hamburg', 289),
('Berlin', 'Munich', 586),
('Berlin', 'Cologne', 574),
('Hamburg', 'Munich', 796),
('Hamburg', 'Cologne', 425),
('Munich', 'Cologne', 589),
]
# Add the distances as the edges in our graph
graph.add_weighted_edges_from(edges)
With this setup, we've accurately defined our graph, capturing all the necessary elements for a TSP. However, transforming this graph into a problem that algorithms can address requires a mathematical model. Within the field of quantum optimization, this typically involves a Quadratic Unconstrained Binary Optimization (QUBO) model. Fortunately, we have already developed this QUBO model for you, eliminating the need for you to do it yourself.
You are now ready to proceed by submitting your graph to LunaSolve. This will generate a TSP instance in QUBO format, preparing it for solution by quantum algorithms.
from luna_sdk import LunaSolve
from luna_sdk.schemas import TravellingSalesmanProblem
# Create a LunaSolve object and set your API key
ls = LunaSolve(api_key="<LUNA_API_KEY>")
# Convert the networkx graph to a digestible format for LunaSolve
graph_data = nx.to_dict_of_dicts(graph)
# Define that we want to create a TSP with the corresponding graph data
tsp = TravellingSalesmanProblem(graph=graph_data)
# Create a TSP instance and retrieve the corresponding ID
optimization = ls.optimization.create_from_use_case(name="My TSP", use_case=tsp)
2. Solving the TSP using Quantum Algorithms
LunaSolve provides access to a wide array of quantum algorithms and hardware platforms. For the purposes of this tutorial, we will focus on utilizing IBM's quantum hardware along with the QAOA (Quantum Approximate Optimization Algorithm) as our example.
IBM stands out as a leading company in superconducting quantum hardware. QAOA represents a popular hybrid algorithm designed for optimization tasks, leveraging both quantum and classical computing resources to find solutions efficiently.
To dive deeper into how QAOA operates and its application on IBM hardware, you can explore further details in our documentation.
Now, you're set to tackle your TSP with the QAOA algorithm. All you have to do is tell LunaSolve for which use case you want to create a solution and which algorithm you want to use.
As quantum hardware is still quite expensive these days, for the sake of this tutorial, we will use a simulator to create the solution. Therefore, no QPU token is required. If you wish to try real quantum hardware, you can simply change the backend parameter accordingly. We will also use real quantum hardware in the next part of this tutorial.
# Solve the QUBO using QAOA with the AerSimulator backend
job = ls.solution.create(
optimization_id=optimization.id,
solver_name="QAOA",
provider="ibm",
solver_parameters={
"backend": {"backend_type": "simulator", "backend_name": "aer"} ,
"maxiter": 10,
},
qpu_tokens=None
)
[Optional] Improve QAOA Results using Q-CTRL's FireOpal
Alternatively, we also provide the possibility to run QAOA via Fire Opal. Fire Opal is a service from Q-CTRL that allows anyone to easily run their most valuable quantum applications by abstracting hardware, automatically reducing error, and boosting algorithmic success on quantum computers in the NISQ era and beyond. Applying these techniques to QAOA significantly increases performance and the likelihood of getting the right result on real quantum hardware.
This time, we will use actual quantum hardware. Therefore, unlike in the previous section, you'll need to add your QPU token(s) to the LunaSolve solve job, as shown in the following code block.
from luna_sdk.schemas.qpu_token import QpuToken, TokenProvider
# Solve the QUBO using Fire Opal's QAOA and the least busy backend from IBM
job_fireopal = ls.solution.create(
optimization_id=optimization.id,
solver_name="QAOA_FO",
provider="qctrl",
qpu_tokens=TokenProvider(
qctrl=QpuToken(
source="inline",
token="<TOKEN>"
),
ibm=QpuToken(
source="inline",
token="<TOKEN>"
)
),
solver_parameters={
"backend": "least_busy",
# If you are a member of multiple organizations at Q-CTRL, specify your organization here
"organization_slug": "<Organization Slug>"
}
)
# After the execution of your algorithm has finished, retrieve your solution
solution_fireopal = ls.solution.get(
solution_id=job_fireopal.id
)
If you do not yet have an account with Fire Opal and would like to use this service, please contact us here.
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)
--------------------------------------------------------------------------------
META DATA:
--------------------------------------------------------------------------------
id: 66966f4e40b0c26ec747137d
name: Your_Solution_Name
created_date: 2024-07-16 13:02:06.088000
created_by: 6661cdd864cef9568f8bf876
modified_date: 2024-07-16 13:12:45.014000
modified_by: None
error_message: None
params:
backend:
backend_type: simulator
backend_name: aer
shots: 1024
dynamical_decoupling: {}
optimizer: COBYLA
maxiter: 10
optimization_level: 2
service_config:
channel: ibm_quantum
url: None
name: None
instance: None
proxies: None
verify: None
channel_strategy: None
qaoa_config:
reps: 1
name: QAOA
runtime:
total: 633.6336093640421
qpu: None
sense: SenseEnum.MIN
solver: QAOA
provider: ibm
status: StatusEnum.DONE
optimization:
id: 66964c00fb8c33b65b4f388f
name: My TSP
created_date: 2024-07-16 10:31:28.209000
created_by: 6661cdd864cef9568f8bf876
modified_date: 2024-07-16 13:12:45.024000
modified_by: None
input_type: OptFormat.qubo
use_case_name: TSP
params: None
representation: None
--------------------------------------------------------------------------------
RESULTS:
--------------------------------------------------------------------------------
1024 results found. Displaying first 5 results.
Result 1:
{'sample': {'x5': 1.0, 'x0': 1.0, 'x14': 1.0, 'x1': 0.0, 'x11': 1.0, 'x10': 0.0, 'x7': 0.0, 'x9': 0.0, 'x15': 0.0, 'x3': 0.0, 'x4': 0.0, 'x6': 0.0, 'x ....
Result 2:
{'sample': {'x5': 0.0, 'x0': 1.0, 'x14': 0.0, 'x1': 0.0, 'x11': 1.0, 'x10': 1.0, 'x7': 1.0, 'x9': 0.0, 'x15': 1.0, 'x3': 0.0, 'x4': 0.0, 'x6': 0.0, 'x ....
Result 3:
{'sample': {'x5': 1.0, 'x0': 0.0, 'x14': 0.0, 'x1': 0.0, 'x11': 1.0, 'x10': 1.0, 'x7': 0.0, 'x9': 0.0, 'x15': 0.0, 'x3': 0.0, 'x4': 1.0, 'x6': 1.0, 'x ....
Result 4:
{'sample': {'x5': 1.0, 'x0': 1.0, 'x14': 1.0, 'x1': 0.0, 'x11': 0.0, 'x10': q.0, 'x7': q.0, 'x9': 0.0, 'x15': 0.0, 'x3': 0.0, 'x4': 1.0, 'x6': 1.0, 'x ....
Result 5:
{'sample': {'x5': 1.0, 'x0': 0.0, 'x14': 1.0, 'x1': 0.0, 'x11': 0.0, 'x10': 1.0, 'x7': 0.0, 'x9': 0.0, 'x15': 0.0, 'x3': 1.0, 'x4': 1.0, 'x6': 1.0, 'x ....
....
--------------------------------------------------------------------------------
IBM META DATA:
--------------------------------------------------------------------------------
No metadata from provider..
As you can tell the displayed results in bitstrings are not easily understood. However, LunaSolve provides the possibility to transform those results into meaningful context. For a more intuitve representation of your optimization results read the chapter below.
4. Transforming Solutions into the Problem Domain
Understanding the results directly from these algorithms might be tricky, particularly if you're not deeply familiar with optimization techniques. To help with this, LunaSolve transforms the raw data into something that relates to your original problem. For a TSP, this means converting the output into a sequence of cities, showing the order in which they should be visited for optimal efficiency.
# Instead of retrieving the raw solution, get it in the format fitting for your problem formulation
solution = ls.solution.get_use_case_representation(job.id)
print(solution)
Output:
sense: SenseEnum.MIN
results: [{'representation': [['Berlin'], ['Hamburg'], ['Cologne'], ['Munich']], 'obj_value': -4487.0}]
description: The path as a list of lists of nodes. If the solution is valid, the inner lists only contain one node each and every node of the path occurs only once. This is not guaranteed given an arbitrary bit vector.
And there you have it, we've reached the end of our journey. As you can see, LunaSolve smoothly leads you through all the necessary steps to address your optimization challenges. Whether you're a newcomer to quantum computing or optimization strategies, LunaSolve ensures an effortless and understandable path to solving these complex problems.
Example: Maximizing Returns on S&P 500 Investments
Imagine you're interested in creating a portfolio of assets from the S&P500 index. Your primary goal is to ensure the security of your investment by minimizing the risk of potential losses. At the same time, you aim to achieve a certain minimum portfolio value to make the investment worthwhile. Additionally, you have a specific number of assets in mind that you intend to include in your portfolio.
As you explore our collection of pre-implemented use cases, you discover that we've already developed a solution tailored to your requirements via our Portfolio Optimization Problem. To define the problem, you need historical data on the returns of the candidate assets over a specified time period.
Let's assume you've prepared data containing the assets from the S&P500 index that you're considering for purchase. In this example, let's consider a scenario where you want to create a portfolio consisting of 2 out of 5 assets from the S&P500 index and achieve a target return that is higher or equal to the 75th percentile of all returns.
1. Creating a Portfolio Optimization Instance
To select assets for your portfolio effectively, you can use our LunaSolve service. It needs your data to be in the right format to work with our guidelines. For more information on how to set this up, check out our Portfolio Optimization Use Case.
First, you need to define your input data.
import pandas as pd
# Your relevant asset data
data = {
"Date": ["2023-05-02", "2023-05-03", "2023-05-04", "2023-05-05", "2023-05-08", "2023-05-09", "2023-05-10", "2023-05-11", "2023-05-12", "2023-05-15", "2023-05-16", "2023-05-17", "2023-05-18", "2023-05-19", "2023-05-22", "2023-05-23", "2023-05-24", "2023-05-25", "2023-05-26"],
"AAPL": [-0.006191, -0.006467, -0.009913, 0.046927, -0.000403, -0.009971, 0.010421, 0.001095, -0.005418, -0.002897, 0.000000, 0.003603, 0.013666, 0.000628, -0.005481, -0.015155, 0.001632, 0.006692, 0.014105],
"AMZN": [0.015483, 0.000193, 0.003377, 0.015962, 0.001609, 0.007465, 0.033483, 0.018060, -0.017115, 0.008525, 0.019784, 0.018519, 0.022944, -0.016081, -0.010667, -0.000174, 0.015306, -0.014989, 0.044435],
"GOOGL": [-0.017537, 0.000855, -0.006830, 0.008406, 0.020839, -0.003897, 0.040987, 0.043132, 0.008064, -0.008510, 0.025749, 0.011129, 0.016468, -0.000570, 0.018654, -0.019912, -0.013544, 0.021340, 0.009151],
"META": [-0.016202, -0.009238, -0.014808, -0.003169, 0.002105, 0.000429, -0.001243, 0.011627, -0.008397, 0.021599, -0.000167, 0.015367, 0.017980, -0.004902, 0.010910, -0.006363, 0.010011, 0.013964, 0.037002],
"MSFT": [-0.000491, -0.003307, 0.003318, 0.017157, -0.006438, -0.005346, 0.017296, -0.007044, -0.003676, 0.001586, 0.007368, 0.009452, 0.014395, -0.000565, 0.008921, -0.018432, -0.004472, 0.038458, 0.021386]
}
# Create a pandas DataFrame from the data
assets = pd.DataFrame(data)
# Visualize your data
print(assets)
Output:
Date AAPL AMZN GOOGL META MSFT
0 2023-05-02 -0.006191 0.015483 -0.017537 -0.016202 -0.000491
1 2023-05-03 -0.006467 0.000193 0.000855 -0.009238 -0.003307
2 2023-05-04 -0.009913 0.003377 -0.006830 -0.014808 0.003318
3 2023-05-05 0.046927 0.015962 0.008406 -0.003169 0.017157
4 2023-05-08 -0.000403 0.001609 0.020839 0.002105 -0.006438
5 2023-05-09 -0.009971 0.007465 -0.003897 0.000429 -0.005346
6 2023-05-10 0.010421 0.033483 0.040987 -0.001243 0.017296
7 2023-05-11 0.001095 0.018060 0.043132 0.011627 -0.007044
8 2023-05-12 -0.005418 -0.017115 0.008064 -0.008397 -0.003676
9 2023-05-15 -0.002897 0.008525 -0.008510 0.021599 0.001586
10 2023-05-16 0.000000 0.019784 0.025749 -0.000167 0.007368
11 2023-05-17 0.003603 0.018519 0.011129 0.015367 0.009452
12 2023-05-18 0.013666 0.022944 0.016468 0.017980 0.014395
13 2023-05-19 0.000628 -0.016081 -0.000570 -0.004902 -0.000565
14 2023-05-22 -0.005481 -0.010667 0.018654 0.010910 0.008921
15 2023-05-23 -0.015155 -0.000174 -0.019912 -0.006363 -0.018432
16 2023-05-24 0.001632 0.015306 -0.013544 0.010011 -0.004472
17 2023-05-25 0.006692 -0.014989 0.021340 0.013964 0.038458
18 2023-05-26 0.014105 0.044435 0.009151 0.037002 0.021386
According to the problem specification, you need the data as a two-dimensional list for the input. Let's go ahead and arrange your CSV data into this format, turning it into a list of lists where each inner list shows the return values for one asset over time.
# Numpy allows for easier modification of the data
import numpy as np
# Remove the Date column from the data
assets_no_date = assets.iloc[:, 1:]
# Convert the data to a numpy array
returns_np = np.array(assets_no_date)
# Switch axes to retrieve the time series of each asset
returns_np = np.transpose(returns_np)
# Convert the returns to a list of lists
returns = returns_np.tolist()
Next, you just need to set our target return and decide on the number of assets you wish to include in your final portfolio.
# Define the minimum return you want to achieve, at least the 75% quartile of all returns
target_return = np.percentile(returns, 75)
# Define the number of assets you want to buy
n_assets = 2
With your data now properly formatted, you've laid the groundwork necessary to optimize the portfolio. However, to translate this dataset into a format suitable for algorithmic problem-solving, a specialized mathematical approach is required. In our context, this means implementing a Quadratic Unconstrained Binary Optimization (QUBO) formulation. The good news is that we've already crafted this QUBO formulation for you, saving you the complexity of developing it on your own.
You're all set to move forward by submitting your data to LunaSolve. By doing so, you'll create a portfolio optimization instance in QUBO format, ready to be tackled with quantum computing solutions.
from luna_sdk import LunaSolve
from luna_sdk.schemas import PortfolioOptimization
# Create a LunaSolve object and set your API key
ls = LunaSolve(api_key="<LUNA_API_KEY>")
# Define that we want to create an instance of a PO with the corresponding data
po = PortfolioOptimization(returns=returns, R=target_return, n=n_assets)
# Create a PO instance and retrieve the corresponding ID
optimization = ls.optimization.create_from_use_case(name="My PO", use_case=po)
2. Optimizing Your Portfolio on Quantum Hardware
LunaSolve offers an array of algorithms designed to tackle various optimization problems effectively. In this tutorial, we'll explore the use of Simulated Annealing (SA), a powerful classical heuristic for finding solutions to optimization challenges through probabilistic techniques. This approach mimics the process of heating and then slowly cooling a material to achieve a stable configuration.
SA is known for its simplicity and flexibility, making it applicable to a wide range of problems. To demonstrate its capabilities, we'll focus on adjusting one important parameter that significantly influences the algorithm's performance:
- num_sweeps: This parameter, set to 200 in our example, represents the number of iterations the algorithm will perform. It's a key factor in allowing the algorithm sufficient time to explore potential solutions and converge towards an optimal configuration.
It's beneficial to experiment with various settings of num_sweeps and other parameters to fine-tune the algorithm's performance for your specific optimization task.`
Next up, we'll dive into solving our Portfolio Optimization problem using SA. You can configure the solver along with its specific parameters to move forward with solving the problem. Since SA does not access a QPU and instead runs on LunaSolve's servers, you do not need to specify a token.
# Solve the PO instance using the SA algorithm and retrieve a job
job = ls.solution.create(
optimization_id=optimization.id,
solver_name="SA",
provider="dwave",
solver_parameters={
'num_sweeps': 200
},
qpu_tokens=None
)
3. Retrieving Your Solution and Transforming it into the Problem Domain
The following steps are identical to the TSP example from above.
# 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: 664c59931640299105a3e831
name: Your_Solution_Name
created_date: 2024-05-21 10:21:39.049000
created_by: 66291cab401df553a5f5ccd6
modified_date: 2024-05-21 10:21:39.135000
modified_by: None
error_message: None
params:
num_reads: None
num_sweeps: 200
beta_range: None
beta_schedule_type: geometric
initial_states_generator: random
num_sweeps_per_beta: 1
seed: None
interrupt_function: None
beta_schedule: None
initial_states: None
randomize_order: False
proposal_acceptance_criteria: Metropolis
runtime:
total: 0.002015292000123736
qpu: None
sense: SenseEnum.MIN
solver: SA
provider: dwave
status: StatusEnum.DONE
optimization:
id: 664c598f1640299105a3e830
name: My PO
created_date: 2024-05-21 10:21:35.157000
created_by: 66291cab401df553a5f5ccd6
modified_date: None
modified_by: None
use_case_name: PO
params: None
representation: None
--------------------------------------------------------------------------------
RESULTS:
--------------------------------------------------------------------------------
1 results found. Displaying first 5 results.
Result 1:
{'sample': {'x0': 1.0, 'x1': 0.0, 'x2': 0.0, 'x3': 0.0, 'x4': 1.0}, 'obj_value': -0.0019084409595700052, 'feasible': True, 'constraints': {}}
--------------------------------------------------------------------------------
DWAVE META DATA:
--------------------------------------------------------------------------------
beta_range: [174.99827277002987, 8098.970611103293]
beta_schedule_type: geometric
timing:
preprocessing_ns: 1808125
sampling_ns: 90417
postprocessing_ns: 90916
# Instead of retrieving the raw solution, get it in the format fitting for your problem formulation
solution = ls.solution.get_use_case_representation(job.id)
print(solution)
Output:
sense: SenseEnum.MIN
results: [{'representation': [0, 4], 'obj_value': -0.0019084409595700052}]
description: The solution contains the list of assets that were selected for the portfolio.
Finally, you can also map the indices of the solution back to your initial assets.
assets = [assets_no_date.columns.tolist()[i] for i in solution.results[0].representation]
assets
Output:
['AAPL', 'MSFT']