PaperlayerView exact revision on arXiv

Source-linked AI summary

QUBO Formulations for Training Machine Learning Models

Prasanna Date, Davis Arthur, Lauren Pusey-Nazzaro

arXiv:2008.02369v1cs.LGphysics.data-anstat.ML

TL;DR

Training machine-learning models is computationally intensive, motivating alternatives as Moore’s law ends and data-analysis demands grow. The paper formulates linear regression, SVM, and equal-sized k-means training as QUBO problems for adiabatic quantum computers and compares their theoretical complexities with classical methods. It reports better complexities for SVM and equal-sized k-means clustering and equivalent complexities for linear regression.

  • Problem

    Training machine-learning models is usually time- and compute-intensive, motivating quantum approaches for increasingly large-scale data analysis as Moore’s law approaches its end.

  • Method

    The paper formulates training for linear regression, SVM, and equal-sized k-means clustering as QUBO problems for adiabatic quantum computers and compares their time and space complexities with classical algorithms.

  • Results

    The formulations have better time and space complexities for SVM and equal-sized k-means clustering and equivalent complexities for linear regression compared with classical counterparts.

  • Takeaways & Limitations

    The results provide a promising outlook for training these machine-learning models on quantum computers in the future.

Abstract

from arXiv · show

Training machine learning models on classical computers is usually a time and compute intensive process. With Moore's law coming to an end and ever increasing demand for large-scale data analysis using machine learning, we must leverage non-conventional computing paradigms like quantum computing to train machine learning models efficiently. Adiabatic quantum computers like the D-Wave 2000Q can approximately solve NP-hard optimization problems, such as the quadratic unconstrained binary optimization (QUBO), faster than classical computers. Since many machine learning problems are also NP-hard, we believe adiabatic quantum computers might be instrumental in training machine learning models efficiently in the post Moore's law era. In order to solve a problem on adiabatic quantum computers, it must be formulated as a QUBO problem, which is a challenging task in itself. In this paper, we formulate the training problems of three machine learning models---linear regression, support vector machine (SVM) and equal-sized k-means clustering---as QUBO problems so that they can be trained on adiabatic quantum computers efficiently. We also analyze the time and space complexities of our formulations and compare them to the state-of-the-art classical algorithms for training these machine learning models. We show that the time and space complexities of our formulations are better (in the case of SVM and equal-sized k-means clustering) or equivalent (in case of linear regression) to their classical counterparts.

I. INTRODUCTION

The paper motivates quantum computing for computationally intensive machine-learning training and formulates three models as QUBO problems for adiabatic quantum computers. It compares the resulting theoretical complexities with classical training algorithms.

  • Training machine-learning models requires tuning parameters and is usually time- and compute-intensive, creating a trade-off between accuracy and training time.
  • The authors formulate linear regression, support vector machine, and equal-sized k-means clustering as QUBO problems for adiabatic quantum computers such as D-Wave 2000Q.
  • The paper equivalently expresses training for all three models as QUBO problems and theoretically compares the formulations with state-of-the-art classical training algorithms.
  • The formulations have better time and space complexities for SVM and equal-sized k-means clustering, and equivalent complexities for linear regression, relative to classical counterparts.
  • Adiabatic quantum computers use quantum annealing to seek global minima of objective functions and are adept at approximately solving QUBO problems.

IV. LINEAR REGRESSION

The paper places linear regression in a broad applied and quantum-annealing context, then presents a formulation that supports both positive and negative real-valued regression weights. Linear regression uses an augmented data matrix and has classical time complexity O(Nd^2).

  • Linear regression models the relationship between a dependent variable and one or more independent variables across applications including science, business, and weather forecasting.
  • Earlier quantum-annealing approaches for linear regression find only positive real-valued regression weights, whereas this formulation finds both positive and negative real-valued weights.
  • The augmented regression training matrix X has dimension N×(d+1), with each original row extended by unity; labels are Y and weights are w.
  • The regression error is represented geometrically by blue data points and a green fitted line characterized by the weights w.
  • O(Nd^2) is the stated classical time complexity for linear regression, using a pseudo-inverse when (X^T X)^-1 does not exist.

B. QUBO Formulation

The formulation discretizes regression weights with a precision vector and binary variables, then substitutes that representation into the error objective. The resulting objective has QUBO form after removing the constant Y^T Y term.

  • The original regression minimization objective is expressed as w^T X^T Xw − 2w^T X^T Y + Y^T Y.
  • A K-dimensional precision vector P and binary coefficients represent each regression weight as an inner product with finite precision.
  • Each binary coefficient selects or ignores entries of P, while allowing positive and negative precision values changes the number of attainable weight values.
  • The full binary vector w-hat concatenates K binary variables for each of the d+1 regression weights.
  • The precision matrix P has dimension (d+1)×K(d+1), enabling recovery of the original weight vector from the binary representation.
  • Substituting the binary weight representation yields a QUBO objective, because the constant Y^T Y term is omitted without changing the unconstrained optimum.

C. Theoretical Analysis

The linear-regression QUBO formulation uses a precision-dependent representation whose complexity matches the classical algorithm when precision is fixed, although variable precision adds overhead.

  • Linear regression: O(K^2d^2) qubits and O(Nd^2K^2) time characterize the linear-regression QUBO formulation when each weight uses K precision variables.The formulation has O(dK) binary variables, and annealing time is treated as O(1) for practical purposes.
  • Linear regression: O(d^2) qubits and O(Nd^2) time result when precision is fixed, making the formulation equivalent in time complexity to the classical O(Nd^2) algorithm.The fixed-precision assumption treats K as a constant.

V. SUPPORT VECTOR MACHINE (SVM)

SVM training seeks a separating classifier through a convex quadratic program, and the paper converts its Lagrangian formulation into a QUBO suitable for adiabatic quantum computers.

  • SVM formulation: SVM finds weights and a bias that separate labeled training data subject to yi(wTxi + b) ≥ 1 for every training example.The model is formulated using data X, labels Y, weights w, and bias b.
  • SVM formulation: The SVM objective and linear constraints form a convex quadratic programming problem, which the paper solves first through its Lagrangian dual.The dual uses nonnegative Lagrangian multipliers, whose nonzero values correspond to support vectors.
  • QUBO formulation: The QUBO encoding introduces K binary variables for each SVM weight, bias, and Lagrangian multiplier, using a precision vector and stacked binary representations.The construction also defines matrix and vector transformations to express the objective in QUBO form.
  • QUBO formulation: Equation 23 converts the SVM training problem into a QUBO with z = θ̂, A = P^TUP, b = P^Tv, and M = K(N + d + 1).The resulting QUBO can be solved on adiabatic quantum computers.

C. Theoretical Analysis

For SVM, the QUBO formulation has complexity controlled by the precision-vector length K; fixed precision reduces its time complexity below the classical baseline while retaining a quadratic qubit footprint.

  • SVM: O(NK) variables and an O(N^2K^2) qubit footprint result from encoding K binary variables for each original SVM variable.The original SVM problem contains O(N + d) variables and O(Nd) data.
  • SVM: O(NdK^2) total time complexity characterizes the SVM QUBO conversion and practical quantum-annealing solution.The conversion cost is dominated by the second term in the expanded objective.
  • SVM: O(N^2) qubits and O(Nd) time result under fixed precision, with time complexity better than the classical O(N^3) algorithm.These bounds follow when K is treated as a constant, such as for 32-bit or 64-bit precision.

A. Background

Equal-sized k-means partitions data into approximately equal clusters, extending ordinary k-means with a balance constraint. Its classical solution uses a modified iterative Lloyd algorithm, while approximate balance can prevent exact equivalence to generic k-means.

  • A. Background: Equal-sized k-means adds an approximately N/k membership constraint to ordinary k-means clustering.Ordinary k-means minimizes within-cluster variance by assigning each point to its nearest centroid.
  • A. Background: Balanced clustering supports applications including network design, marketing, and document clustering.
  • A. Background: When practical cluster sizes are only approximately equal, the balanced formulation may not produce the exact generic k-means solution.
  • A. Background: Modified Lloyd’s algorithm enforces the equal-size constraint and runs in O(N^3.5k^3.5) time classically.

B. QUBO Formulation

The equal-sized clustering objective is converted into an unconstrained QUBO by encoding assignments as binary variables and adding penalties for cluster-size and one-cluster-per-point constraints.

  • B. QUBO Formulation: A binary matrix assigns each data point to a cluster, with approximately N/k ones per column and exactly one one per row.
  • B. QUBO Formulation: The formulation stacks the Nk assignment variables into a binary vector and applies a linear transformation for the row constraints.
  • B. QUBO Formulation: Penalty terms enforce approximately equal cluster sizes and exactly one cluster assignment per data point.The column constraints use α, while the row constraints use β.
  • B. QUBO Formulation: Combining the objective with both constraint penalties yields a quadratic binary optimization expression.
  • B. QUBO Formulation: Equation 39 matches the paper’s QUBO form with z = ˆw, A = (Ik ⊗ (D + αF) + QT (IN ⊗ βG)Q), and b = 0.This establishes the equal-sized k-means formulation as a QUBO solvable on an adiabatic quantum computer.

C. Theoretical Analysis

The equal-sized k-means QUBO uses O(Nk) variables and has total quantum time complexity O(N^2kd), improving on the classical worst-case bound while not always outperforming practical classical runs.

  • C. Theoretical Analysis: O(Nk) QUBO variables produce a quadratic qubit footprint of O(N^2k^2).The original problem has O(Nd) data and O(N) variables.
  • C. Theoretical Analysis: O(N^2kd) is the total quantum time complexity for constructing and solving the equal-sized k-means QUBO.The conversion term dominates, while quantum annealing is treated as constant time for practical purposes.
  • C. Theoretical Analysis: O(N^2kd) is better than the classical worst-case O(N^3.5k^3.5) bound, but favorable classical initialization can make classical convergence faster.

VII. CONCLUSION

The paper formulates training for three machine learning models as QUBOs and theoretically compares their resource complexities with classical methods. Empirical evaluation on real quantum hardware and comparisons with state-of-the-art classical approaches remain future work.

  • VII. CONCLUSION: The paper formulates linear regression, SVM, and equal-sized k-means training as QUBO problems for adiabatic quantum computers.
  • VII. CONCLUSION: The authors analyze time and space complexity and provide theoretical comparisons with state-of-the-art classical training methods.
  • VII. CONCLUSION: Empirical evaluation on real quantum computers and direct comparison with state-of-the-art classical approaches are identified as future work.
Loading 2008.02369v1…