The HHL algorithm lies on an implementation of the Quantum Phase Estimation algorithm. One popular implementation is based on the Quantum Fourier Transform which can be divided in three steps. Let $U$ be a unitary matrix and $|\psi\rangle$ an eigenvector s.t. $U|\psi\rangle = e^{2\pi i\theta}|\psi\rangle$ and $|0\rangle^{\otimes n }|\psi\rangle$ the initial state of the system.
- Apply $n$-bit Hadamard gate operation $H^{{\otimes}n}$ to the first register. The state of system becomes $\frac{1}{\sqrt N} (|0\rangle + |1\rangle)^{\otimes n} |\psi\rangle$.
- Apply controlled unitary operations $C-U$ to the first register. More precisely, we want to apply a $C-U^{2^{j}}$ to the $(n-j)^{th}$ qubit of the first register for all $j$. Now the state of the first register is $\frac{1}{\sqrt N} \underbrace{ \left (|0\rangle + e^{2\pi i 2^{n-1} \theta}|1\rangle \right )}_{1^{st} \ qubit} \otimes \cdots \otimes \underbrace{\left (|0\rangle + e^{2\pi i 2^1 \theta}|1\rangle \right )}_{n-1^{th} \ qubit} \otimes\underbrace{\left (|0\rangle + e^{2\pi i 2^{0} \theta}|1\rangle \right )}_{n^{th} \ qubit} = \frac{1}{\sqrt N}\sum_{k=0}^{2^n -1} e^{2\pi i \theta k} |k\rangle$
- Apply inverse Quantum Fourier Transform on the first register, which yields to a binary approximation of $\theta$ stored in the first register.
The following picture summarize all these steps :
My question : how do one implement efficiently the circuit $C-U^{2^{j}}$ ? A naive approach would be to use $2^j$ circuit $C-U$ and apply them successfully but the overall complexity would be of order $O(2^n)$ which is not what we want in the HHL algorithm.
