QUANTUM SPECTRAL CLUSTERING THROUGH A BIASED PHASEESTIMATION ALGORITHM

Abstract

In this paper, we go through the theoretical steps of the spectral clustering onquantum computers by employing the phase estimation and the amplitude amplificationalgorithms. We discuss circuit designs for each step and show how to obtain the clusteringsolution from the output state. In addition, we introduce a biased version of the phaseestimation algorithm which significantly speeds up the amplitude amplification process.The complexity of the whole process is analyzed: It is shown that when the circuit rep-resentation of a data matrix of orderNis produced through an ancilla based circuit inwhich the matrix is written as a sum ofLnumber of Householder matrices; the computa-tional complexity is bounded byO(2mLN) number of quantum gates. Here,mrepresentsthe number of qubits involved in the phase register of the phase estimation algorithm.Keywords: Spectral Clustering, Quantum Algorithms.