Homology Computation of Large Point Clouds Using Quantum Annealing

By Raouf Dridi & Hedayat Alghassi
In this paper we present a quantum annealing algorithm for computation of homology of large point clouds. It is designed to work on resizable cloud computing platforms. The algorithm takes as input a witness complex K approximating the given point cloud. It uses quantum annealing to compute a clique cover of the 1-skeleton of K and then uses this cover to blow up K into a Mayer-Vietoris complex. Finally, it computes the homology of the Mayer-Vietoris complex in parallel. The novelty here is the use of clique covering which, compared to graph partitioning, substantially reduces the computational load assigned to each slave machine in the computing cluster. We describe two different clique covers and their quantum annealing formulation in the form of quadratic unconstrained binary optimization (QUBO).

Most Recent Papers

Scaling Overhead of Locality Reduction in Binary Optimization Problems

By Elisabetta Valiante, Maritza Hernandez, Amin Barzegar, & Helmut G. Katzgraber Recently, there has been considerable interest in solving optimization problems by mapping these onto a binary representation, sparked mostly by the use of quantum annealing machines....

Quantum Multiple Kernel Learning

By Seyed Shakib Vedaie, Moslem Noori, Jaspreet S. Oberoi, Barry C. Sanders, & Ehsan Zahedinejad Kernel methods play an important role in machine learning applications due to their conceptual simplicity and superior performance on numerous machine learning tasks....