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)