A toy-problem to start solving middle scale optimization problem on the QC
Hi there!
I am a neophyte in QC, so please be tolerant to my questions :)
I want to try to apply QC for my current field of study because it potentially will allow to optimize large scaled problem. E.g. I need to do some simple optimizations millions of times.
Don't know where to start.
Registered on DWAVE, installed SDK.
Q0) Is there any "template from scratch" showing how to start the problem solve locally using SDK or Leap, or a video lecture with the simplest code example closest to the task explained in the bottom?
Task Explanation & Questions using toy-problem
I need to optimize some objective function with many binary features - x (e.g. several millions).
The simplified model is:
Ax = b
where A - known matrix,
x - solution vector,
b - known vector.
Let's assume for the toy problem next sizes A = m x n (3 x 4)
and b is 3, so the shape of numpy arrays are:
A = np.array([[ 1, 2, 3, 4],
[5, 6, 7, 8],
[10.99, 17, 19, 21.5]])
b = np.array([0.51, 0.2, 0.7])
So the sizes for toy-problem are:
A.shape = (3, 4)
b.shape = (3,)
The equation to optimize that is already in the form of a binary quadratic model, matrix form.
||Ax-b||^2 -> min
And I want to try to find the optimal x vector for a given A and b for both options:
a) without any constraints
b) with constraints, simple sum(x) = N
N = 3
np.sum(x) = 3 # constraint on the sum of binary solution variables sum(x) must equal to N
In real life we have equality and inequality constraints, but for the first example, it's better to have the simplest.
As I understood from the site materials we can add constraints two ways.
1) First - to use "updated objective function" and add a term that actually corresponds to a constraint, like this:
||Ax-b||^2 + gamma * (sum(x) - N)^2
Q0.1) Am I correct in my understanding?
2) second is to use CQM: to have direct representation of problem constraints.
In this case to provide constraints - must be more convenient and flexible,
e.g. if I need to use some advancements, like sum(x) must be within some known interval:
N_l <= sum(x) <= N_u
Q0.2) is it available to use CQM in a trial mode? what are the limitations on the size of the problem?
Q1) how to start actually? :)
I need to run the program locally (preferred for me) to be able to debug it, and see how the problem can be solved on a small scale, middle, and possibly relatively large. is it possible to use CPU/GPU for this to tune/debug all parameters? Or even in this case if I will use DWave-ocean-SDK it will use the computational nodes and solvers so actual optimization will take place on the nodes while the local machine is used only for task formulation and configuration of solvers used on the backend?
In this case - do I need to create some Python Jupyter Notebook/project locally and try to run it locally? and when I will succeed - try to create a github repository and run it from Leap providing the link to online IDE?
Q2) does CQM and BQM are actually the same? I mean if I want to generalize, CQM creates BQM for objective function and constraints to use both like BQM or CQM is completely different mathematical formulation?
Q3) Is it available to use CQM in a trial mode? what are the limitations on the size of the problem? or other limiations if I will use SDK or Leap?
Q4) Is there a simple way to compare speedup using DWAVE - e.g. for the middle-size of a problem run it using CPUs/ GPUs locally and using DWave SDK and quantum computing/solver, or hybrid service with quantum solver to understand in numbers how can I get an advantage on the optimization of a given toy-example to count the benefit?
Comments
Oleskii,
To find some code which most closely matches what you are trying to do, take a look at the Problem Solving Handbook, specifically, the Stating the Problem section, where they list a number of general problem types.
You can also look at the D-Wave Examples code on github: https://github.com/dwave-examples.
I run most of my code locally, using VS Code without any issues. You do not need to write your code in a Jupyter notebook, although that is an option.
Please sign in to leave a comment.