All the references in this question refer to Quantum algorithm for solving linear systems of equations (Harrow, Hassidim & Lloyd, 2009).

The question I have is about the step where they apply controlled-rotations to transfer the eigenvalue encoded in a quantum register to the amplitudes of a state:

After the quantum phase estimation, the state of the quantum registers is (see page 3): $$ \sum_{j=1}^{N} \sum_{k=0}^{T-1} \alpha_{k|j}\beta_j \vert \tilde\lambda_k\rangle \vert u_j \rangle $$ Then, the HHL algorithm consists in applying rotations controlled by $\vert\tilde\lambda_k\rangle$ to produce the state $$ \sum_{j=1}^{N} \sum_{k=0}^{T-1} \alpha_{k|j}\beta_j \vert \tilde\lambda_k\rangle \vert u_j \rangle \left( \sqrt{1 - \frac{C^2}{\tilde\lambda_k^2}} \vert 0 \rangle + \frac{C}{\tilde\lambda_k}\vert 1 \rangle \right) $$ where "$C = O(1/\kappa)$" (still page 3).

My question: why do they introduce $C$? Isn't $C=1$ valid?


1 Answer 1


If $\tilde{\lambda_{k}} < C$, the controlled rotation becomes non-physical since you have coeffecient greater than 1 on your $|1\rangle$ state.

As a result $C < \lambda_{min}$ is a safer choice, and that is $O(1/\kappa)$ according to the 4th paragraph in the intro.


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.