A simpler algorithm to mark the unknown eigenstates

Abstract

For an unknown eigenstate $|ψ\rangle$ of a unitary operator $U$, suppose we have an estimate of the corresponding eigenvalue which is separated from all other eigenvalues by a minimum gap of magnitude $Δ$. In the eigenstate-marking problem (EMP), the goal is to implement a selective phase transformation of the $|ψ\rangle$ state (known as \emph{marking} the $|ψ\rangle$ state in the language of the quantum search algorithms). The EMP finds important applications in the construction of several quantum algorithms. The best known algorithm for the EMP combines the ideas of the phase estimation algorithm and the majority-voting. It uses $Θ(\frac{1}Δ\ln \frac{1}ε)$ applications of $U$ where $ε$ is the tolerable error. It needs $Θ\left(\ln \frac{1}Δ\right)$ ancilla qubits for the phase estimation and another $Θ\left(\ln \frac{1}ε\right)$ ancilla qubits for the majority-voting. In this paper, we show that the majority-voting is not a crucial requirement for the EMP and the same purpose can also be achieved using the fixed-point quantum search algorithm which does not need any ancilla qubits. In the case of majority-voting, these ancilla qubits were needed to do controlled transformations which are harder to implement physically. Using fixed-point quantum search, we get rid off these $Θ\left(\ln \frac{1}ε\right)$ ancilla qubits and same number of controlled transformations. Thus we get a much simpler algorithm for marking the unknown eigenstates. However, the required number of applications of $U$ increases by the factor of $Θ\left(\ln \frac{1}ε\right)$. This tradeoff can be beneficial in typical situations where spatial resources are more constrained or where the controlled transformations are very expensive.