Formulation and Implementation of a Support Vector Machine on D-Wave's Quantum Annealer

Overview

Quantum annealing is an emerging technology that promises important progress in the quantum computing sector. Along with quantum gates, they provide a change of paradigm in computing, as they shift to a quantum perspective while addressing computational problems. Namely, its possible applications are problems where low-energy states are useful such as optimization and probabilistic sampling problems. In this investigation, the main focus is the mathematical formulation and implementation of a support vector machine (SVM) algorithm in D-Wave’s quantum annealer. The first step was to formulate the problem as a quadratic unconstrained binary optimization (QUBO) problem. Several adaptations were made to overcome physical and connectivity limitations of the quantum computer. The first was to split the problem in subsets and the second of my contributions was to follow a hybrid approach using a combination of the QUBO formulation and the sampling capability of the annealer. Finally, I coded the algorithm in Python and executed it in the actual quantum annealer, along with a local simulated annealing version, and its classification performance was compared against that of the classical algorithm. All in all, through the proposal of a QUBO formulation of an SVM algorithm, it has been proven that it is possible to solve it in a quantum annealer and when executed with two datasets, excellent classifications which were close to the classical model were obtained, while not evidencing any quantum advantage. In that sense, these conclusions answer my research question. I genuinely believe that this new upcoming field of quantum information opens another perspective to some computational problems that will exceed the classical computer’s performance sooner than we expect.

Awards (1)

• Fourth Award of $500 $500

Competition history

• ISEF 2021 Physics and Astronomy · Entry PHYS078

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.