# specificity of quantum phase estimation in Childs et al.'s NAND formula evaluation algorithm

I have some uncertainties regarding the quantum algorithm for NAND formula evaluation presented in this paper : Every NAND formula of size N can be evaluated in time N^1/2 +o(1) on a quantum computer.

The author presents the algorithm as a quantum phase estimation over a defined walk operator, the definition of the algorithm can be found on page 4 of the paper. The first step of the algorithm is described as follows :

1. Initialization. Let T = 320⌊√N ⌋. Prepare three quantum registers in the state $$\left(\frac{1}{\sqrt{T}} \sum_{t=0}^{T-1}(-i)^{t}|t\rangle\right)\otimes\left|r^{\prime \prime}\right\rangle\mid\text{left}\rangle$$ The first register is a counter for quantum phase estimation, the second register holds a vertex index, and the third register is a qutrit “coin” holding ‘down’, ‘left’ or ‘right’ in this order.

This initialization raise two questions for me :

1. the counting register is initialized in: $$\left(\frac{1}{\sqrt{T}} \sum_{t=0}^{T-1}(-i)^{t}|t\rangle\right)$$ which differs from the classical QPE initialization by the $$(-i)^{t}$$ factor. Where does this factor comes from and what is its impact on the result of the QPE algorithm ?

2. the second and third registers are initialized in the state: $$\left|r^{\prime \prime}\right\rangle\mid\text{left}\rangle$$ which is not an eigenvector of the operator we want to get the phase. How does the QPE works in this case ?

Thanks a lot for your help!

## 1 Answer

I finally found an answer to the second question by myself so I leave it here for further readers :

The goal of the overall algorithm is not to find specifically an eigenvalue of the walk operator for a given eigenvector but to know if there exists for this operator a zero-energy eigenstate (i.e. an eigenvector with eigenvalue 0).

The second and third registers are thereby initialized in a vector (which is not an eigenvector but is necessarily a linear combination of eigenvectors of our walk operator) so that the result of the QPE is a linear combination of the phases corresponding to the eigenvectors.

We will therefore be able to know if one of them corresponds to the eigenstate we are looking for.

I am still looking for explanation of the $$(-1)^t$$ factor of the counting register initialization.