# Efficient QFT-based QPEA complexity

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.

In most cases you would have to apply the circuit $$2^n$$ times, where for an error tolerance on the solution of $$\epsilon$$ we have to choose $$n=\mathcal{O}(\log_21/\epsilon)$$. This is why most HHL algorithms based on QPE scale as $$\mathcal{O}(1/\epsilon)=\mathcal{O}(2^n)$$, and the reason many works try to circumvent QPE to achieve a runtime $$polylog(1/\epsilon)$$.
This problem is well explained in the Introduction section to this paper, which also presents a different quantum algorithm (not based on QPE) to solve systems of linear equations with a better dependency on $$\epsilon$$.