Quantum spectral clustering algorithm for unsupervised learning

doi:10.1007/s11432-022-3492-x

Quantum spectral clustering algorithm for unsupervised learning

2022-07-15

8

PRE

AI

DOI：10.1007/s11432-022-3492-x

Original

Original request for help

Save

Abstract

En 中文

Clustering is one of the most crucial problems in unsupervised learning, and the well-known k-means algorithm can be implemented on a quantum computer with a significant speedup. However, for the clustering problems that cannot be solved using the k-means algorithm, a powerful method called spectral clustering is used. In this study, we propose a circuit design to implement spectral clustering on a quantum processor with substantial speedup by initializing the processor into a maximally entangled state and encoding the data information into an efficiently simulatable Hamiltonian. Compared to the established quantum k-means algorithms, our method does not require a quantum random access memory or a quantum adiabatic process. It relies on an appropriate embedding of quantum phase estimation into Grover's search to gain the quantum speedup. Simulations demonstrate that our method effectively solves clustering problems and is an important supplement to quantum k-means algorithm for unsupervised learning.

Keywords:

quantum algorithm

machine learning

spectral clustering

quantum phase estimation

Grover's search

Hamiltonian simulation

Quantum spectral clustering algorithm for unsupervised learning

Abstract

Journal

Organization