Solving practical problems on quantum computers and quantum-inspired hardware with Quadratic Unconstrained Binary Optimization (QUBO)
In my first article on quantum computing I took a look at gate based quantum computing using the MATLAB Support Package for quantum computing. This is when we program a quantum computer by constructing quantum circuits such as this:
% Optimized 7 qubit GHZ state taken from https://www.ibm.com/quantum/blog/whole-device-entanglement
gates = [hGate(1);cxGate(1,4); cxGate(1,2);cxGate(4,6);cxGate(2,3);cxGate(4,5);cxGate(6,7)];
ghz_state = quantumCircuit(gates);
p = plot(ghz_state);
My article showed how to use MATLAB to simulate such quantum circuits on your desktop or laptop and also how to run them on real quantum hardware in the cloud. MATLAB's documentation includes several examples of how to use gate based quantum computing to solve real world problems such as Graph Coloring and Ground-State Protein Folding.
Although important, gate based quantum computers aren't the only type of quantum computer in town.
There is another!
Quadratic Unconstrained Binary Optimization (QUBO) - The key to programming quantum annealers
A QUBO problem is a type of optimisation problem. We'll get to the details later. What you need to know right now is that it turns out that a huge variety of important optimization problems that arise in industry, science and government [1] can be transformed into qubo problems. In turn, QUBO problems can be efficiently solved using a class of quantum hardware called quantum annealers. So, programming a quantum annealer can be reduced to 'How do I transform my problem into a QUBO problem?
A veritable zoo of hardware and software can solve QUBO problems
Quantum annealers aren't the only hardware type that can solve QUBO problems. There's also a fascinating set of quantum-inspired hardware devices that can do the job such as Complementary Metal Oxide Semiconductor (CMOS) annealers. Other groups have developed a set of powerful metaheuristic algorithms that work on classical hardware including both CPUs and GPUs. One of these algorithms, tabu search, is built into MATLAB's Quantum Computing support package. Finally, you can also solve QUBO problems on gate-based quantum hardware which is something I'll explore in a future article.
In short, if you can pose your problem as a QUBO problem, you can run it on a whole zoo of devices with very little additional effort. Which hardware or software combination is best is very much problem dependent.
What is a QUBO problem and how do I solve one in MATLAB?
The QUBO optimization problem is:
QUBO: minimize/maximize $ y = x^t Q x $
where x is a vector of binary decision variables (0 or 1) and Q is a square matrix of constants
An example of a QUBO problem that first helped me make sense of what this means is given in the paper Quantum Bridge Analytics I: A Tutorial on Formulating and Using QUBO Models [1] so I'll reproduce it here.
Minimize $ y = -5x_1 - 3x_2 - 8x_3 -6x_4 + 4x_1x_2 + 8x_1x_3 + 2x_2x_3 + 10x_3x_4 $ where the variables $ x_j $ are binary.
This has a linear part, $ y = -5x_1 - 3x_2 - 8x_3 -6x_4 $ and a quadratic part $ y = 4x_1x_2 + 8x_1x_3 + 2x_2x_3 + 10x_3x_4 $. We can input this into MATLAB using the qubo function which is part of the MATLAB Support Package for Quantum Computing.
Q = [0 2 4 0; 2 0 1 0; 4 1 0 5; 0 0 5 0]; % Quadratic part
c = [-5; -3; -8; -6]; % Linear part
problem = qubo(Q, c)
Since binary variables satisfy , the linear part can be written as $ y = -5x_1^2 - 3x_2^2 - 8x_3^2 -6x_4^2 $ and so our problem can be also be written as
Minimize
This is exactly the form used in the definition of a QUBO problem above. If I prefer, I can also construct the QUBO problem in MATLAB using this matrix directly
Q = [-5 2 4 0; 2 -3 1 0; 4 1 -8 5; 0 0 5 -6];
problem = qubo(Q)
Both formulations are equivalent so we can use whatever we prefer. Let's request the solution
solution = solve(problem)
So, the minimum of our function is -11 and the set of that gives this is
solution.BestX
MATLAB currently makes use of the Tabu search algorithm to solve QUBO problems on your local machine. Tabu search is a stochastic algorithm, so each time you run the algorithm, you might get a different result and there is no guarantee that it finds the global minimum. In this case, however, we are OK. This is the global minimum and you could even check by exhaustive evaluation without much difficulty.
Finally, for the sake of illustration, let's explicitly evaluate the function we've minimized with the vector BestX found above.
(solution.BestX)' * Q * solution.BestX
This matches what MATLAB reported in the QUBO solution and so now I have some confidence that I understand what's going on:
solution.BestFunctionValue
This might not look like much but it turns out that a vast array of important problems that arise in real applications can be turned into QUBO problems
What problems can be solved using QUBO?
Initially, QUBO seemed quite unassuming to me It's such a simple problem statement that I couldn't imagine that you could do much with it. I could not be more wrong! Examples from MATLAB's documentation include Traveling Salesperson Problem, Capacitated Vehicle Routing Problem and Feature Selection for Machine Learning but these are just the tip of the iceberg. A quick scan of the literature reveals dozens of important problems that can be reposed as QUBO problems : Maximum cut problems, Capital Budgeting problems, Task Allocation Problems, Quadratic Knapsack, Warehouse location problems, portfolio optimisation and much much more. An active area of research is to uncover more problems that can be tackled by QUBO, I guess because this means that the problem in question can then be tackled by quantum annealing computers and other quantum-inspired hardware.
Although the U in QUBO stands for unconstrained, it is possible to tackle constrained problems by making use of penalty functions. This is discussed in the MATLAB documentation Constraints in QUBO Problems and also in Glover et al [1].
Many interesting problems can be formulated as QUBOs and the number of problems that can be solved in this way is expanding all the time. A colleague sent me a great list that's being maintained by blogger Daniel Ratke that has over 110 problems at the time of writing.
One of these is the traveling salesperson problem. Here is an abridged version of the demo in the MATLAB documentation. Let's make up a bunch of randomly distributed cities.
N = 9; % Number of cities
rng default % For reproducibility
stopsLon = 1.5*rand(N,1);
stopsLat = rand(N,1);
plot(stopsLon,stopsLat,"ko")
Calculate the distances between the cities using the hypot function.
[X,Y] = meshgrid(1:N);
dist = hypot(stopsLon(X) - stopsLon(Y),stopsLat(X) - stopsLat(Y));
Qtsp = tsp2qubo(dist)
We've already seen how to solve QUBO problems in MATLAB so we just have to plug this problem into the same framework.
% Solve the QUBO problem using MATLAB
MATLABresult = solve(Qtsp)
Finally, we need to interpret the result showing the optimal way to visit these cities
binx = MATLABresult.BestX;
binx = reshape(binx,N,[]);
ordr = zeros(1,N);
for i = 1:N
ordr(i) = find(binx(i,:)); % Find order of cities in route
end
hold on
plot(stopsLon(ordr),stopsLat(ordr),"ko")
plot(stopsLon(ordr),stopsLat(ordr),"b-")
plot(stopsLon(ordr([N 1])),stopsLat(ordr([N,1])),"b-")
for i = 1:length(stopsLon)
text(stopsLon(i)+0.02,stopsLat(i),num2str(i))
end
title("Solution to traveling salesperson problem using QUBO")
hold off
Solving QUBO problems on real quantum annealing hardware (and other devices) using Strangeworks
One of the reasons why there has been so much excitement around QUBO problems recently is that they can be directly solved on Quantum Annealers such as those developed by D-Wave along with several other specialized hardware and software platforms such as Hitachi CMOS Annealers and Simulated Quantum Bifurcation Machines (SQBM) by Toshiba.
To do this on MATLAB as of R2024b, we can make use of the Strangeworks platform. If you are wondering who Strangeworks are, you can head over to their website and ask their ChatAI cat called Schrödy (get it?)
Me: Tell me who Strangeworks are in three sentences
Schrödy: Strangeworks is a company that specializes in quantum computing, aiming to make quantum computing accessible to a broad audience. They provide a platform that allows researchers, developers, and enthusiasts to collaborate on quantum computing projects, offering tools to write, test, and run quantum code. Strangeworks collaborates with industry leaders in quantum computing to integrate various quantum technologies into their platform, making it a hub for quantum computing resources.
A demo using Strangeworks
Install and configure the Strangeworks SDK that's available on the MathWorks File Exchange, have a chat with their sales team to hook you up with access to the hardware (https://strangeworks.com/#contact) and you are good to go.
First we connect to the Strangeworks platform's optimization service. You get your apiKey and resource_slug from their website once you have an account.
% This won't work unless you use your correct apiKey and resource_slug
apiKey = "";
resource_slug = ""; % This must be the resource slug related to their optimization service
sw = strangeworks().authenticate(apiKey);
sw = sw.get_resource(resource_slug);
fprintf("Connected to SW service : %s \n", sw.product_slug)
The great thing about this service is that it makes it trivial to submit our QUBO problem to a range of very different hardware platforms via Strangeworks.
Let's solve our traveling salesperson QUBO problem using Toshiba's Simulated Bifurcation Machine (SBM).
solver = "toshiba.qubo";
solver_options = struct();
job = sw.run(solver, Qtsp, solver_options)
The Strangeworks platform assigns a unique name to the job called a job_slug which we use to query if the job has completed or not and also to fetch results.
job_slug = "floral-eagle-0186"
sw.status(job_slug)
Now we can get the result.
QuantumResult = sw.result(job_slug)
Extract the order we should visit each city from this result.
QuantumMinimum = QuantumResult.energy;
QuantumBinx = QuantumResult.result;
QuantumBinx = reshape(QuantumBinx,N,[]);
QuantumOrdr = zeros(1,N);
for i = 1:N
QuantumOrdr(i) = find(QuantumBinx(i,:)); % Find order of cities in route
end
Comparing this to the MATLAB result, we can see that it's just as good but there is a different starting position for the optimal tour. There are minor differences in the naming convention between the result from Strangeworks and the native MATLAB result but it's straightforward to see how they compare to each other.
MATLABresult
MATLABMinimum = MATLABresult.BestFunctionValue;
MATLABBinx = MATLABresult.BestX;
MATLABBinx = reshape(MATLABBinx,N,[]);
MATLABOrdr = zeros(1,N);
for i = 1:N
MATLABOrdr(i) = find(MATLABBinx(i,:)); % Find order of cities in route
end
disp(table([QuantumMinimum;MATLABMinimum],[QuantumOrdr;MATLABOrdr], ...
RowNames=["MATLAB Tabu","Strangeworks (Toshiba)"],VariableNames=["BestFunctionValue","Visits"]))
The two solution methods have essentially come up with the same result. In practice, it doesn't matter which city you start from within this problem.
One of the nice things with using MATLAB and the Strangeworks platform is that I've now done all of the programming I need to do in order to run this problem on many different hardware and software platforms. Once I have access to the required resources on the StangeWorks platform, all I do is change the solver. I could try Gurobi's QUBO optimisation service, for example.
solver = "gurobi.qubo";
solver_options = struct();
job = sw.run(solver, Qtsp, solver_options)
gurobiResult = sw.result("winter-dust-0907")
If you have access to them on your Strangeworks account, It would be just as easy to switch to using quantum computers from D-Wave, CMOS Annealing machines from Hitachi or a range of other systems but I didn't have access to them as part of this trial.
In this case, all of the solvers I tried returned the same result other than having different starting cities. For such a small problem, this is what you'd expect but you could imagine that for much larger problems differences between solution quality, cost and execution time will emerge.
The combination of MATLAB and Strangeworks is a great way to explore this solution space.
To QUBO, or not to QUBO, that is the question:
The Quadratic Unconstrained Binary Optimization (QUBO) formulation is attractive due to its compatibility with emerging hardware paradigms such as quantum annealers and other quantum-inspired hardware. However, as with any modeling approach, the decision to frame a problem as a QUBO or not is not always straightforward.
The combination of MATLAB's support for Quantum Computing and Strangeworks' straightforward access to a range of hardware and software solvers helps you make this decision in practice.
References and further study
[1] Fred Glover, Gary Kochenberger, Yu Du (2022), A Tutorial on Formulating and Using QUBO Models, Annals of OR
[3] Andrew Lucas. Ising formulations of many NP problems. Available at https://arxiv.org/pdf/1302.5843.pdf.
[4] Gary Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng Lü, Haibo Wang & Yang Wang (2014), "The Unconstrained Binary Quadratic Programming Problem: A Survey". Journal of Combinatorial Optimization, Vol. 28, Issue 1, pp. 58-81.
[6] List of QUBO formulations: A blog post containing a list of over 100 optimization problems with references to their QUBO formulation,
- Category:
- Optimization,
- quantum computing
Comments
To leave a comment, please click here to sign in to your MathWorks Account or create a new one.