第九章量子降维算法 机器学习需要处理的数据特征通常是高维，特别是计算机视 觉及自然语言处理领域。原始特征不但高维，而且包含了大量 与学习问题相关度小、甚至不相关的信息。部分算法会随着维 度的提高，出现高维空间中无法工作的情况。因此，降维操作 在机器学习中十分重要。降维操作降低了数据复杂程度，剔除 了不必要的无用信息，使模型能在降维之后进行有效的学习
第九章量子降维算法 机器学习需要处理的数据特征通常是高维，特别是计算机视 觉及自然语言处理领域。原始特征不但高维，而且包含了大量 与学习问题相关度小、甚至不相关的信息。部分算法会随着维 度的提高，出现高维空间中无法工作的情况。因此，降维操作 在机器学习中十分重要。降维操作降低了数据复杂程度，剔除 了不必要的无用信息，使模型能在降维之后进行有效的学习
经典机器学习常用的降维操作包括：主成分分析 (principle component analysis,.PCA),线性判 别分析(linear discriminant analysis,LDA), 流行学习等，其中常用到的是PCA
经典机器学习常用的降维操作包括：主成分分析 (principle component analysis, PCA) ，线性判 别分析（linear discriminant analysis, LDA） ， 流行学习等，其中常用到的是 PCA
一、量子主成分分析算法(Quantum principal component analysis,QPCA) Lloyd等人在2014年提出量子主成分分析算法 (Quantum principal component analysis,QPCA). 由于量子系统的密度矩阵均为厄米矩阵，其可表示成 Gram矩阵的形式，可看作是一组向量的协方差矩阵， 因此该方法使用量子系统的多个密度矩阵副本构造对 应特征值较大的特征向量
一、量子主成分分析算法(Quantum principal component analysis，QPCA） Lloyd 等人在 2014 年提出量子主成分分析算法 (Quantum principal component analysis，QPCA)。 由于量子系统的密度矩阵均为厄米矩阵，其可表示成 Gram 矩阵的形式，可看作是一组向量的协方差矩阵， 因此该方法使用量子系统的多个密度矩阵副本构造对 应特征值较大的特征向量
Quantum principal component analysis Seth Lloyd12*,Masoud Mohseni3 and Patrick Rebentrost2 The usual way to reveal properties of an unknown quantum state,given many copies of a system in that state,is to perform measurements of different observables and to analyse the results statistically12.For non-sparse but low-rank quantum states,revealing eigenvectors and corresponding eigenvalues in classical form scales super-linearly with the system dimension3-6.Here we show that multiple copies of a quantum system with density matrix o can be used to construct the unitary transformation e-it.As a result,one can perform quantum principal component analysis of an unknown low-rank density matrix,revealing in quantum form the eigenvectors corresponding to the large eigenvalues in time exponentially faster than any existing algorithm.We discuss applications to data analysis,process tomography and state discrimination
Suppose that one is presented with n copies of p.A simple trick allows one to apply the unitary transformation ei to any density matrix o up to nth order in t.Note that trp e⑧geaf=(cos2△t)o+(sin△t)p-isin△tcos△t[p,o] =o-i△t[p,o]+O(△t2)
Here trp is the partial trace over the first variable and S is the swap operator.S is a sparse matrix and its elements are efficiently computable,so e-isA can be performed efficiently-14.Repeated application of (1)with n copies of p allows one to construct e-ipmAePA.Comparison with the Suzuki-Trotter theory of quantum simulation-shows that to simulate e to accuracy e requires n=O(t2ep-)O(t2e-)steps,where t=nAt and is the sup norm.Thus,simply performing repeated infinitesimal swap operations on po allows us to construct the unitary operator
Density matrix exponentiation now allows us to apply the quantum phase algorithm to find the eigenvectors and eigenvalues of an unknown density matrix.If we have n copies of p,we use the ability to apply e to perform the quantum phase algorithm'. In particular,the quantum phase algorithm uses conditional applications ofei for varying times t to take any initial state)0) to∑；y;lXi)li),where|Xi〉are the eigenvectors of p,;are estimates of the corresponding eigenvalues,and v;=(xilv)
Here,in contrast,the conditional operation can be performed simply by replacing the SWAP operator with a conditional SWAP in the derivation above.More precisely,take t,=nAt,and apply the unitary∑mln△t)(n△t|⑧Πeis,arto the state ln△t)(n△t☒o☒p⑧..☒p where o =x)(xI and S;swaps o with the jth copy of p.Taking the partial trace over the copies of p yields the desired conditional operation|t)lx〉→lt)e-tX)
Using p itself as the initial state,the quantum phase algorithm yields the state rx)x⑧1) Sampling from this state allows us to reveal features of the eigenvectors and eigenvalues of p.The use of multiple copies of a state to construct its eigenvectors and eigenvalues will be referred to here as qPCA
(2).Using mn copies of p we obtain m copies of the decomposition (2),where the ith eigenvalue r;appearsrim times.The features of the ith eigenstate can then be determined by performing a quan- tum measurement to obtain the expectation value(xMIX)of the eigenvector with eigenvalue r for desired Hermitian M.As long as M is sparse-14 or efficiently simulable by the methods given in this paper,this measurement can itself be performed in time O(logd)
