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 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.