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

Variationally Scheduled Quantum Simulation

By Shunji Matsuura, Samantha Buck, Valentin Senicourt, & Arman Zaribafiyan Eigenstate preparation is ubiquitous in quantum computing, and a standard approach for generating the lowest-energy states of a given system is by employing adiabatic state preparation...

A Quantum Annealing-Based Approach to Extreme Clustering

By Tim Jaschek, Marko Bucyk, & Jaspreet S. Oberoi Clustering, or grouping, dataset elements based on similarity can be used not only to classify a dataset into a few categories, but also to approximate it by a relatively large number of representative elements. In...