I am reading Harrow, Hassidim, and Lloyd's paper Quantum algorithms for linear systems of equations. On the third page of that paper, they write

Next we apply the conditional Hamiltonian evolution $\sum_{\tau=0}^{T-1} \left|\tau\right>\left<\tau\right|^{C}\otimes e^{iA\tau t_{o}/T}$ on $\left|\Psi_{0}\right>^{C}\otimes\left|b\right>\dots$

For the life of me, I cannot figure out the meaning of the $C$. What is it doing there? How would $\sum_{\tau=0}^{T-1} \left|\tau\right>\left<\tau\right|^{C}\otimes e^{iA\tau t_{o}/T}$ act on (say) $\left|0\right>\otimes \left|0\right>$ or $\left|1\right>\otimes \left|0\right>$?


2 Answers 2


I remember struggling with this very same question! Ultimately I concluded that the $C$ is just a notational device (it doesn't represent any mathematical operation), just to indicate that, for a specific $\tau$, the Hamiltonian evolution operator $e^{iA\tau t_0/T}$ is performed on $\left|b\right>$, but only when conditioned on $\left|b\right>$ being tensored with $\left|\tau\right>$.

If you ignore the $C$'s, I think a calculation will show that you just apply the operator $\sum_{\tau=0}^{T-1} \left|\tau\right>\left<\tau\right|\otimes e^{iA\tau t_{o}/T}$ "as-is". I hope this helps.

  • 2
    $\begingroup$ Ah thank you. By the way, I found a free source for the published version of the paper, in which the $C$ disappears. It lives here: dspace.mit.edu/handle/1721.1/51753 $\endgroup$
    – user14717
    Commented Apr 12, 2012 at 10:03

There's a Version 2 with appendix and there's write...

  1. Apply the Fourier transform to the register C. Denote the resulting basis states with |ki, for k = 0, . . . T − 1. Define λ˜ k := 2πk/t0.

if This does not answer properly, maybe take a look to this new version of this paper.


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.