# A simpler algorithm to mark the unknown eigenstates

Research paper by **Avatar Tulsi**

Indexed on: **08 Nov '16**Published on: **08 Nov '16**Published in: **arXiv - Quantum Physics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

For an unknown eigenstate $|\psi\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 $\Delta$. In the
eigenstate-marking problem (EMP), the goal is to implement a selective phase
transformation of the $|\psi\rangle$ state (known as \emph{marking} the
$|\psi\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 $\Theta(\frac{1}{\Delta}\ln
\frac{1}{\epsilon})$ applications of $U$ where $\epsilon$ is the tolerable
error. It needs $\Theta\left(\ln \frac{1}{\Delta}\right)$ ancilla qubits for
the phase estimation and another $\Theta\left(\ln \frac{1}{\epsilon}\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 $\Theta\left(\ln
\frac{1}{\epsilon}\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 $\Theta \left(\ln \frac{1}{\epsilon}\right)$. This tradeoff can
be beneficial in typical situations where spatial resources are more
constrained or where the controlled transformations are very expensive.