Quantum speedup of twin support vector machines

Zekun Ye, Lvzhou Li, Haozhen Situ, Yuyi Wang

Introduction

In the era of big data, the scalability of machine learning algorithms is a primary concern. As the number of samples ($m$) and features ($n$) grows, classical optimization techniques often face significant computational bottlenecks. Support Vector Machines (SVMs), while powerful for classification, require substantial resources for training on high-dimensional datasets. This paper explores a quantum framework for Twin Support Vector Machines (TSVM), demonstrating that quantum computing can reduce the time complexity of these models from polynomial to logarithmic scales.

The Twin Support Vector Machine (TSVM)

Traditional SVMs seek a single optimal hyperplane to separate two classes of data. In contrast, the Twin Support Vector Machine (TSVM) identifies two non-parallel hyperplanes—one for each class. Each hyperplane is designed to be as close as possible to one class and as far as possible from the other. This approach offers greater flexibility and often faster training times in classical settings compared to standard SVMs.

However, the "Least Square" formulation of TSVM (LSTSVM), which simplifies the optimization problem into a system of linear equations, still requires at least $\Omega(n^2)$ time classically. This quadratic dependence on dimensionality limits its application to massive datasets. The authors aim to bridge this gap by using quantum computing to handle these heavy matrix computations more efficiently.

Proposed Quantum Framework

The authors propose a quantum version of the TSVM (QTSVM) that leverages quantum linear system algorithms to accelerate both training and prediction.

1. Quantum State Preparation

The first challenge in quantum machine learning is encoding classical data into quantum states. The proposed framework utilizes Quantum RAM (qRAM) and a specific "Walsh-Hadamard" transformation to prepare quantum states representing the data matrices. Specifically, it encodes the matrices into states such as $|F^T e_2\rangle$ and $|E^T e_1\rangle$, which serve as the inputs for the linear solver.

2. Solving Linear Systems via QLSA

The training of an LSTSVM is mathematically equivalent to solving two systems of linear equations. The authors employ a Quantum Linear System Algorithm (QLSA), similar to the well-known HHL algorithm, to find the quantum states that represent the parameters of the two hyperplanes. Unlike many quantum algorithms that require sparse matrices, this framework uses density matrix exponentiation. This technique allows the algorithm to simulate the necessary Hamiltonians even for dense datasets, significantly broadening the algorithm's applicability to real-world data.

3. Quantum Prediction and the SWAP Test

Once the hyperplanes are "learned" as quantum states, the model must classify new samples. To maintain the quantum speedup, the algorithm avoids a full readout of the hyperplane vectors (which would incur polynomial costs). Instead, it employs a SWAP test circuit. The SWAP test estimates the inner product between the new sample state and the learned hyperplane states, allowing the system to determine the class of the sample based on its proximity to the respective hyperplanes in a quantum state space.

Complexity Analysis and Results

The primary contribution of this work is the rigorous mathematical proof of exponential speedup based on general parameters $m$ and $n$.

  • Training Complexity: The quantum training algorithm achieves a complexity of $O(\log mn)$. Classically, solving the linear systems for TSVM requires polynomial time, typically $\Omega(n^2)$ or higher depending on the solver.
  • Prediction Complexity: Classifying a new data point takes $O(\log n)$ time on a quantum computer, compared to the $\Omega(n)$ time required to compute a vector-vector dot product classically.

The total time complexity is dominated by the condition number of the matrices ($\kappa$) and the desired precision ($\epsilon$). While the scaling with respect to data size is logarithmic, the performance remains sensitive to the quality of the data (conditioning) and the accuracy requirements.

Discussion and Limitations

While the theoretical speedup is profound, several hurdles remain for practical implementation:

  • qRAM Dependency: The algorithm assumes the availability of efficient qRAM for data loading. Currently, building large-scale, reliable qRAM remains a significant hardware challenge.
  • Precision Bottlenecks: The SWAP test introduces a dependency on precision ($O(\epsilon^{-2})$). If extremely high precision is required, this could mitigate some of the speed benefits.
  • Conditioning: The algorithm's efficiency is tied to the condition number $\kappa$. Poorly conditioned datasets (where matrices are nearly singular) may reduce the effective speedup.

Conclusion

This research demonstrates that Twin Support Vector Machines are uniquely suited for quantum acceleration because they reduce optimization to linear systems rather than complex quadratic programming. By reformulating the TSVM training process as a quantum linear systems problem, the authors provide a path toward processing massive, high-dimensional datasets with logarithmic efficiency. Future work may explore how these methods perform on Noisy Intermediate-Scale Quantum (NISQ) devices.

Summary updated

BibTeX
@article{ye2020quantum,
  author = {Zekun Ye and Lvzhou Li and Haozhen Situ and Yuyi Wang},
  title = {{Quantum speedup of twin support vector machines}},
  journal = {Science China Information Sciences},
  year = {2020},
  doi = {10.1007/s11432-019-2783-7},
}
Figure