Arul Mazumder and Sridhar Tayur from the Quantum Technologies Group at Carnegie Mellon University have created a tutorial on solving Quadratic Unconstrained Binary Optimization (QUBO) problems on quantum computers, specifically IBM and D-Wave machines. The tutorial covers three combinatorial optimization problems: Number Partitioning, MaxCut, and Minimum Vertex Cover, and models two practical problems: de novo discovery of driver genes in cancer genomics and Order Partitioning for AB testing at a hedge fund portfolio manager. The tutorial is aimed at industry professionals exploring near-term quantum applications.
Introduction to Quantum Computing and QUBO Models
Quantum Computing is a promising technology of the 21st century. However, due to the infancy of the hardware, many of the envisioned speedups remain largely theoretical. This tutorial by Arul Mazumder and Sridhar Tayur from the Quantum Technologies Group at Carnegie Mellon University provides a hands-on introduction to solving Quadratic Unconstrained Binary Optimization (QUBO) problems on currently available quantum computers, specifically IBM and D-Wave machines.
QUBO models can be used to represent a variety of problems. The general matrix form of a QUBO is minx01nxTQxc 1. Here, x represents a binary solution vector of size n, Q is an upper triangular matrix, and c is an arbitrary constant. QUBO models are a natural gateway to quantum computing due to their link with computer science and their mathematical equivalence to the Ising model in physics.
Canonical Problems in Quantum Computing
The tutorial covers three canonical combinatorial optimization problems: Number Partitioning, MaxCut, and Minimum Vertex Cover.
Number Partitioning involves partitioning a set of positive integer values into two sets such that the difference between the sums of the two sets is minimized. This objective function can be expressed as a QUBO.
MaxCut involves partitioning an undirected graph into two sets such that the number of edges connecting nodes between these two sets is maximized. The QUBO for MaxCut is framed as a minimization problem.
Minimum Vertex Cover seeks to find the minimum vertex cover of an undirected graph. A vertex cover is the subset of vertices such that each edge shares an endpoint with at least one vertex in the subset. The QUBO for Minimum Vertex Cover is to minimize the number of vertices in the vertex cover and the edges must be covered by the vertices.
Practical Applications of QUBO Models
The tutorial also models two practical problems: de novo discovery of driver genes in cancer genomics and Order Partitioning for AB testing at a hedge fund portfolio manager.
In cancer genomics, the application is to identify altered cancer pathways from shared mutations and gene exclusivity. The combinatorial criteria essential to identifying driver mutations are coverage and exclusivity. The Degree Matrix corresponds to the coverage criterion and the Adjacency Matrix corresponds to the exclusivity criterion.
Conclusion
This tutorial provides a quick introduction to solving QUBO problems on currently available quantum computers, covering both IBM and DWave machines. It also provides examples of three canonical problems and two models from practical applications. An associated GitHub repository provides the codes in five companion notebooks. This article aims to reach working industry professionals seeking to explore the potential of near-term quantum applications.
The article titled “Five Starter Problems: Solving Quadratic Unconstrained Binary Optimization Models on Quantum Computers” was published on January 17, 2024. The authors of this article are Arul Rhik Mazumder and Sridhar Tayur. The article was sourced from arXiv, a repository of electronic preprints approved for publication after moderation, hosted by Cornell University. The article can be accessed through its DOI reference https://doi.org/10.48550/arxiv.2401.08989.