Complexity of gaussian superposition preparation in Regev's factorisation algorithm

Question

I'm going through the Regev's factorisation algorithm, and I don't understand how, for the Gaussian state preparation, he achieves a complexity of $d(\log D+ \text{poly}(\log d))$.

He says:

"the $\text{poly}(\log d)$ term is for computing the rotation needed for each of the $O(\log d)$ most significant qubits"

But by using the method described in the referred Grover-Rodolph's paper, as I understand it, you'd need to do $O(2^n)$ controlled rotation (by recursively doing it for each of the $2^n$ possible states spanned by the $n$ qubits).

So even by only considering the $\log(d)$ most significant qubits, I get $O(2^{\log(d)}) = O(d)$. Therefore, I have that we need $\text{poly}(d)$ gates for the controlled rotation and not $\text{poly}(\log(d))$.

I guess I'm missing some optimisation somewhere. Even by using the symmetry of Gaussian, we cannot improve the asymptotic complexity.

Can you please enlighten me?

Answer 1

I think you may have somehow misunderstood the paper. The authors start off with a given discretized distribution, and then augment it one qubit at a time. For each additional qubit, there is only a single controlled rotation (by an angle $\theta_i$ that is stored in a quantum register, to use the notation from the paper). So if the final distribution is over $N = 2^n$ states, then there are at most $n$ such controlled rotations.

To answer the comment: Note that the authors write that they compute $\theta_i \equiv \text{arccos} \sqrt{f(i)}$ (in superposition) and then rotate by $\theta_i$ to map $|0\rangle \rightarrow \cos \theta_i |0\rangle + \sin \theta_i |1\rangle$ so as to partition the probability mass, see (5–6). (We have that $\cos^2 \theta_i + \sin^2 \theta_i = 1$.) There is only one angle $\theta_i$ (stored in a quantum register, in superposition) involved every time that we augment the distribution with an additional qubit.