Classical and Quantum Algorithms for Tensor Principal Component Analysis
We present classical and quantum algorithms based on spectral methods for a problem in tensor principal component analysis. The quantum algorithm achieves a quartic speedup while using exponentially smaller space than the fastest classical spectral algorithm, and a super-polynomial speedup over classical algorithms that use only polynomial space. The classical algorithms that we present are related to, but slightly different from those presented recently in Ref. 1. In particular, we have an improved threshold for recovery and the algorithms we present work for both even and odd order tensors. These results suggest that large-scale inference problems are a promising future application for quantum computers.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
An end-to-end trainable hybrid classical-quantum classifier
We introduce a hybrid model combining a quantum-inspired tensor network and a variational quantum circuit to perform supervised learning tasks. This architecture allows for the classical and quantum parts of the model to…
Tensor NetworksQuantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
A central roadblock to analyzing quantum algorithms on quantum states is the lack of a comparable input model for classical algorithms. Inspired by recent work of the author [E. Tang, STOC'19], we introduce such a model,…
ClusteringRecommendation SystemsQuantum Machine Learning Tensor Network States
Tensor network algorithms seek to minimize correlations to compress the classical data representing quantum states. Tensor network algorithms and similar tools---called tensor network methods---form the backbone of moder…
BIG-bench Machine LearningQuantum Machine LearningTensor NetworksQuantum-Inspired Classical Algorithm for Principal Component Regression
This paper presents a sublinear classical algorithm for principal component regression. The algorithm uses quantum-inspired linear algebra, an idea developed by Tang. Using this technique, her algorithm for recommendatio…
Recommendation SystemsregressionClassical Simulation of Variational Quantum Classifiers using Tensor Rings
In recent times, Variational Quantum Circuits (VQC) have been widely adopted to different tasks in machine learning such as Combinatorial Optimization and Supervised Learning. With the growing interest, it is pertinent t…
BIG-bench Machine LearningCombinatorial OptimizationQuantum Machine Learning