PHASE ESTIMATION USING AN APPROXIMATE EIGENSTATE

摘要

A basic building block of many quantum algorithms is the Phase Estimation algorithm (PEA). It finds an eigenphase phi of a unitary operator using a copy of the corresponding eigenstate vertical bar phi >. Suppose, in place of vertical bar phi >, we have a copy of an approximate eigenstate vertical bar psi > whose component in vertical bar phi > is at least root 2/3. Then the PEA fails with a constant probability. Using multiple copies of vertical bar psi >, this probability can be made to decrease exponentially with the number of copies. Here we show that a single copy is sufficient to find phi if we can selectively invert the vertical bar psi > state. As an application, we consider the eigenpath traversal problem (ETP) where the goal is to travel a path of non-degenerate eigenstates of n different operators. The fastest algorithm for ETP is due to Boixo, Knill and Somma (BKS) which needs Theta(ln n) copies of the eigenstates. Using our method, the BKS algorithm can work with just a single copy but its running time Q increases to O(Q ln(2) Q). This tradeoff is beneficial if the spatial resources are more constrained than the temporal resources.