Quantum Spectral Clustering through a Biased Phase Estimation Algorithm

2017/03/16 by Ammar Daskin, Daskin, Ammar · 4 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Amplitude #Artificial intelligence #Cluster analysis #Computational complexity theory #Computer science #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Mathematics #Matrix (chemical analysis) #Neural Networks and Reservoir Computing #Phase (matter) #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum algorithm #Quantum circuit #Quantum computer #Quantum error correction #Quantum mechanics #Quantum phase estimation algorithm #Qubit #Representation (politics) #Spectral clustering #cs.DS #quant-ph

paper · pdf · doi:10.48550/arxiv.1703.05568

published in arXiv (Cornell University) 10(1), 24-33 (Cornell University) · 5 pages, submitted to a conference, and any comments are welcomed

openalex publication_date 2017/03/16 · arxiv created 2017/07/21 · arxiv updated 2017/07/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

In this brief paper, we go through the theoretical steps of the spectral clustering on quantum computers by employing the phase estimation and the amplitude amplification algorithms. We discuss circuit designs for each step and show how to obtain the clustering solution from the output state. In addition, we introduce a biased version of the phase estimation algorithm which significantly speeds up the amplitude amplification process. The complexity of the whole process is analyzed: it is shown that when the circuit representation of a data matrix of order N is produced through an ancilla based circuit in which the matrix is written as a sum of L number of Householder matrices; the computational complexity is bounded by O(2^mLN) number of quantum gates. Here, m represents the number of qubits (e.g., 6) involved in the phase register of the phase estimation algorithm.

Citations

• A Quantum Approximate Optimization Algorithm
• Quantum Machine Learning
• A Survey of Quantum Learning Theory

Cited by

• Learnable quantum spectral filters for hybrid graph neural networks

Related

• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Quantum phase estimation based filtering: performance analysis and application to low-energy spectral calculation
• Experimental Challenges of Implementing Quantum Phase Estimation Algorithms on IBM Quantum Computer
• Distributed Phase Estimation Algorithm and Distributed Shor's Algorithm
• K-Means Clustering on Noisy Intermediate Scale Quantum Computers