# Quantum Spectral Clustering of Mixed Graphs

Volya, Daniel and Mishra, Prabhat

December 2021

Abstract

Spectral graph partitioning is a well known technique to estimate clusters in undirected graphs. Recent approaches explored efficient spectral algorithms for directed and mixed graphs utilizing various matrix representations. Despite its success in clustering tasks, classical spectral algorithms suffer from a cubic growth in runtime. In this paper, we propose a quantum spectral clustering algorithm for discovering clusters and properties of mixed graphs. Our experimental results based on numerical simulations demonstrate that our quantum spectral clustering outperforms classical spectral clustering techniques. Specifically, our approach leads to a linear growth in complexity, while state-of-the-art classical counterpart leads to cubic growth. In a case study, we apply our proposed algorithm to preform unsupervised machine learning using both real and simulated quantum computers. This work opens an avenue for efficient implementation of machine learning algorithms on directed as well as mixed graphs by making use of the inherent potential quantum speedup.

Bibtex


@inproceedings{volyaQuantumSpectralClustering2021,
title = {Quantum Spectral Clustering of Mixed Graphs},
booktitle = {2021 58th ACM/IEEE Design Automation Conference (DAC)},
author = {Volya, Daniel and Mishra, Prabhat},
year = {2021},
month = {dec},
pages = {463--468},
issn = {0738-100X},
doi = {10.1109/DAC18074.2021.9586308},
abstract = {Spectral graph partitioning is a well known technique to estimate clusters in undirected graphs. Recent approaches explored efficient spectral algorithms for directed and mixed graphs utilizing various matrix representations. Despite its success in clustering tasks, classical spectral algorithms suffer from a cubic growth in runtime. In this paper, we propose a quantum spectral clustering algorithm for discovering clusters and properties of mixed graphs. Our experimental results based on numerical simulations demonstrate that our quantum spectral clustering outperforms classical spectral clustering techniques. Specifically, our approach leads to a linear growth in complexity, while state-of-the-art classical counterpart leads to cubic growth. In a case study, we apply our proposed algorithm to preform unsupervised machine learning using both real and simulated quantum computers. This work opens an avenue for efficient implementation of machine learning algorithms on directed as well as mixed graphs by making use of the inherent potential quantum speedup.},
keywords = {Clustering algorithms,Computers,eigenvalue computation,eigenvector projection,Machine learning,Machine learning algorithms,Partitioning algorithms,Quantum computing,Runtime,spectral graph clustering},
}