An Improved Algorithm for Quantum Principal Component Analysis

2019/03/10 by Changpeng Shao, Shao, Changpeng
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata #quant-ph

paper · pdf · doi:10.48550/arxiv.1903.03999

The result is not true

openalex publication_date 2019/03/10 · arxiv created 2019/04/07 · arxiv updated 2019/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Principal component analysis is an important dimension reduction technique in machine learning. In [S. Lloyd, M. Mohseni and P. Rebentrost, Nature Physics 10, 631-633, (2014)], a quantum algorithm to implement principal component analysis on quantum computer was obtained by computing the Hamiltonian simulation of unknown density operators. The complexity is O((log d)t²/ε), where d is the dimension, t is the evolution time and ε is the precision. We improve this result into O((log d)t^1+(1)/(k)/ε^(1)/(k)) for arbitrary constant integer k≥ 1. As a result, we show that the Hamiltonian simulation of low-rank dense Hermitian matrices can be implemented in the same time.

Related

• Refined Quantum Algorithms for Principal Component Analysis and Solving Linear System
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• A Low Complexity Quantum Principal Component Analysis Algorithm
• New Quantum Algorithm for Principal Component Analysis
• Parametrized Complexity of Quantum Inspired Algorithms