Understanding QUBOs
QUBO problems serve as fundamental building blocks for more complex optimization models that can address many real-world problems, and are one of the primary types of problems that can be solved by Dirac entropy quantum computing systems. This module will start with a basic introduction to QUBOs and then provide tutorials based off of QUBOs.
Module Outline
Module Overview
1. QUBO on Dirac
This tutorial introduces the overall core Quadratic Unconstrained Binary Optimization (QUBO) problems, which aim to optimize quadratic objective functions without constraints on decision variables. The tutorial explains the significance of QUBOs, their applications across fields like machine learning and finance, and provides guidance on running QUBO problems on QCi's Dirac entropy quantum computing systems.
2. QBoost for QUBO
This tutorial introduces QBoost, a QUBO-based binary classifier, discussing its methodology and implementation using the IRIS dataset. QBoost leverages boosting techniques to construct a "strong" classifier from a collection of "weak" classifiers, aiming to minimize a quadratic objective function while penalizing non-zero weights to push many weights to zero. The implementation involves building weak classifiers based on decision trees with one, two, or three features and training the classifier using QUBO optimization.
3. Max-cut on Dirac
The tutorial discusses the Max-cut problem, a well-known NP-hard problem in combinatorial optimization. It outlines the problem's formulation as a QUBO or Ising Hamiltonian, where the objective is to partition the nodes of a graph into two subsets to maximize the number of edges between them. The text explains the process of constructing the Hamiltonian, uploading coefficients to Qatalyst, and running the job to obtain results. The resulting solution is visualized on the graph, with edges between nodes in different sets indicating cuts, and the cut size compared to the known optimal solution.
4. Dimensionality reduction on Dirac
This tutorial introduces a Quantum Dimensionality Reduction approach utilizing QCi's technology, specifically focusing on implementing a QUBO-based algorithm that makes use of the Singular Value Decomposition (SVD). The method decomposes the data matrix into orthonormal bases and discusses the selection of principal components based on eigenvalues. The tutorial further demonstrates the application of this approach to a dataset on prescription opioids in the United States, obtained from public Medicare data, emphasizing the initial step of cleaning the dataset.
5. Set partitioning on Dirac
This tutorial introduces the Set Partitioning Problem (SPP) as an optimization problem aimed at selecting sets from a collection such that each member is included in exactly one of the selected sets. Applications of SPP range from logistics to manufacturing and scheduling. Formulation involves creating constraints ensuring each member belongs to only one selected set and an objective function measuring the cost or benefit of selecting certain sets.
Conclusion
After completing this module, you should be equipped to create and execute QUBOs and other optimization problems that are based on QUBO formulations. Next, visit our module on Understanding QLCBOs.