In Prakash's thesis - (link to PDF), section 2.2.2 Constant size vector states:

We show that the vector state $|x\rangle$ for $x\in R^b$ can be created in time $\widetilde{O}(\log(b))$ using a specialized quantum circuit of size $O(b)$ and pre computed amplitudes. The method is useful for creating constant sized superpositions and is illustrated for a 4 dimensional state $|\phi\rangle$ in figure 2.4.

enter image description here


Wouldn't a sequence of conditional rotations on all nodes of a binary tree of depth $\log(b)$ result in a circuit with $O(b)$ number of conditional rotations?

For example in this circuit we need a rotation on the first qubit, then 2 conditional rotations from the first qubit on the second qubit. And if we had 3 qubits we'd have a 4 conditional rotation from the first and second qubit on the 3rd qubit.

I am having trouble understanding how an exponential speedup over a typical QRAM was achieved here.


I should clarify that I also think that the number of gates would be the same as the depth of the circuit. Here is an example of a circuit preparing a state of 4 qubits from https://arxiv.org/abs/2010.00831

enter image description here

  • $\begingroup$ I'm not sure this is a duplicate but, does this answer your question? quantumcomputing.stackexchange.com/a/10282/10454 Essentially, you can perform the $2^k$ controlled rotations with $O(\log b)$ gates if I'm not mistaken, assuming you have a function $f$ that you can implement as a unitary gate that gives you the angle of rotation. If you don't understand, feel free to ping me and i'll add more details in an actual answer $\endgroup$
    – Tristan Nemoz
    May 23, 2023 at 18:17
  • $\begingroup$ @TristanNemoz Yes it looks like this question is very related to my what I'm asking. I have all the angles precomputed, I guess I'm trying to understand how can the C-R_00 and C-R_01 gate be ran in parallel. A full answer would be appreciated :) $\endgroup$ May 23, 2023 at 23:51

1 Answer 1


As mentioned in this answer, it is possible to perform each succession of rotation in parallel.

Let us suppose that we're at depth $k$ in our tree. If we were to implement the successive rotations as depicted in the circuit you've linked, the qubit number $k$ would undergo $2^k$ controlled rotations. More precisely, each of these rotations would be controlled off of a different number. For notation's sake, let us say that we want to apply a $R_Y$ gate with angle $\theta_x$ only if the $k-1$ previous qubits are in state $|x\rangle$. That is, we want to implement this gate: $$|x\rangle|0\rangle\to|x\rangle\left(\cos\left(2\pi\theta_x\right)|0\rangle+\sin\left(2\pi\theta_x\right)|1\rangle\right)=|x\rangle R_Y\left(4\pi\theta_x\right)|0\rangle$$ (Note: using $2\pi\theta_x$ ensures that $\theta_x\in[0\,;\,1)$).

Note that what you want to do, if I understand correctly, is to load a state from a QRAM structure. In such a case, the coefficients of the vector you load could be negative, in which case some additional gates should be added, as described in Algorithm 1 of this paper. Here, I'll focus on a state with all amplitudes being positive as in your example, since it shows the gist of why we can implement such a gate efficiently.

Suppose that we have access to a function $f$ such that: $$f(x)=\theta_x$$ with $\theta_x$ being represented on $p$ qubits, $p$ translating the precision of the angle. Computing $f$ can be done efficiently thanks to the tree structure. As such, we can implement $f$ as a quantum oracle: $$U_f|x\rangle|y\rangle=|x\rangle\left|y\oplus\theta_x\right\rangle$$ We assume that this oracle can be implemented in time $T_f(k)$. Now, let's look at what happens when we apply $P$ gates on $|x\rangle\left|\theta_x\right\rangle$. Let us write $\theta_x$ in binary as: $$\theta_x=\sum_{i=1}^{p}b_{x, i}2^{-i}$$ Suppose now that we apply a $P(2\pi)$ gate on the first qubit of the second register, a $P\left(\pi\right)$ gate on the second qubit of the second register, etc... up to a $P\left(\frac{\pi}{2^{p-2}}\right)$ gate on the last qubit of the last register. As a recall, the $P(\theta)$ gates leaves $|0\rangle$ untouched and apply a $\theta$ phase on $|1\rangle$: $$P(\theta)=\begin{pmatrix}1&0\\0&\mathrm{e}^{\mathrm{i}\theta}\end{pmatrix}$$ Thus, the $P$ gate that is applied on qubit $i$ doesn't do anything if $b_{x, i}=0$. If $b_{x, i}=1$, then it adds a $\frac{2\pi}{2^{1-i}}$ phase to the state. Thus, all in all, the phase of this state is now: $$2\pi\sum_{i=1}^{p}b_{x, i}2^{1-i}=4\pi\theta_x$$ Thus, using a single layer of gates we've managed to implement the following transformation: $$\left|\theta_x\right\rangle\to\mathrm{e}^{4\mathrm{i}\pi\theta_x}\left|\theta_x\right\rangle$$ Suppose now that we replace these $P$ gates by controlled-$P$ gates controlled on the single qubit target. Then this would implement the following transformation: $$\begin{align}\left|\theta_x\right\rangle|0\rangle\to{}&\left|\theta_x\right\rangle|0\rangle\\\left|\theta_x\right\rangle|1\rangle\to{}&\mathrm{e}^{4\mathrm{i}\pi\theta_x}\left|\theta_x\right\rangle|0\rangle\end{align}$$ That is, by replacing the $P$ gates by controlled ones, we've actually implemented a $P\left(4\pi\theta_x\right)$ gate on the last qubit. Let us denote by $V$ the following gate: $$V=\frac{1}{\sqrt{2}}\begin{pmatrix}1&-\mathrm{i}\\\mathrm{i}&-1\end{pmatrix}$$ Note that we have: $$\begin{align} VP(\theta)V^\dagger &= \frac12\begin{pmatrix}1&-\mathrm{i}\\\mathrm{i}&-1\end{pmatrix}\begin{pmatrix}1&0\\0&\mathrm{e}^{\mathrm{i}\theta}\end{pmatrix}\begin{pmatrix}1&-\mathrm{i}\\\mathrm{i}&-1\end{pmatrix} \\&=\mathrm{e}^{\mathrm{i}\frac{\theta}{2}}\begin{pmatrix}\cos\left(\frac{\theta}{2}\right)&-\sin\left(\frac{\theta}{2}\right)\\\sin\left(\frac{\theta}{2}\right)&\cos\left(\frac{\theta}{2}\right)\end{pmatrix}\\&=\mathrm{e}^{\mathrm{i}\frac{\theta}{2}}R_Y(\theta)\end{align}$$ Thus, if we apply a $V$ gate on the single target qubit before and after the $P$ gate, this transforms it into a $R_Y$ rotation (up to an unconvenvient phase).

Putting everything together, we start with the following state: $$|x\rangle|0\rangle|0\rangle$$ We apply $U_f$: $$|x\rangle\left|\theta_x\right\rangle|0\rangle$$ We apply $V$ on the target qubit: $$|x\rangle\left|\theta_x\right\rangle V|0\rangle$$ We apply the $P\left(4\pi\theta_x\right)$ gate on the last qubit using the method outlined above: $$|x\rangle\left|\theta_x\right\rangle P\left(4\pi\theta_x\right)V|0\rangle$$ We then apply the $V$ gate once again: $$|x\rangle\left|\theta_x\right\rangle VP\left(4\pi\theta_x\right)V|0\rangle=|x\rangle\left|\theta_x\right\rangle \mathrm{e}^{2\mathrm{i}\pi\theta_x}R_Y\left(4\pi\theta_x\right)|0\rangle$$ We now remove the unwanted phase by applying $P(-\pi),P\left(-\frac{\pi}{2}\right),\cdots$ on the second register: $$|x\rangle\left|\theta_x\right\rangle R_Y\left(4\pi\theta_x\right)|0\rangle$$ And finally, we uncompute the second register by applying $U_f$ once again: $$|x\rangle\left|0\right\rangle R_Y\left(4\pi\theta_x\right)|0\rangle$$ We can now discard the second register as it is not entangled with the others. All in all, the depth of this circuit is $2T_f(k)+2+p+1=2T_f+p+3$, where $2T_f(k)$ comes from computing and uncomputing the second register, $p$ comes from the controlled-$P$ gates on the target qubit, $2$ comes from the two $V$ gates on the target qubit and $1$ comes from the layer of $P$ gates used to uncompute the unwanted relative phase (since they're applied on the same layer). Note that the only term that depends on $k$ is $2T_f(k)$.

$p$ has to be chosen accordingly to the desired precision. Thus, all the depth essentially comes from the $2T_f(k)$ term. I'm less confident on that part, but I think that thanks to the tree structure, $f$ can be computed in time $O(\log b)$, which in turns ensures that $U_f$ can be implemented in time $\DeclareMathOperator{\polylog}{polylog}O(\polylog b)$, hence the final complexity.

  • $\begingroup$ Thank you this helps a lot! But it seems like we simply moved the problem to $U_f$. $f(x)$ can be completely arbitrary map (depending on the tree). So the question now becomes: How can we do an exponential number of Controlled-$\oplus f(x)$ simultaneously? $\endgroup$ May 25, 2023 at 3:44
  • $\begingroup$ To make my question more concrete using the example tree in my question: we would want $U_f$ to do the following: |00>|0> -> |00>|0.4/sqrt(2)}> and |10>|0> -> |10>|0.8/sqrt(0.8)> for 2nd level of the tree. How can we run both of these gates in parallel? $\endgroup$ May 25, 2023 at 3:47
  • $\begingroup$ @bubakazouba I think I get your point. However, the difference lies on the nature of $U_f$. As a gate implementing a classical function, $U_f$ is a permutation matrix. In fact, when building up the tree, it is possible for the user to also implement a (classical) circuit for $f$. Being given this circuit for $f$, it is possible to implement a quantum circuit that implements $U_f$ with at most a polynomial overhead. So, as long as the classical circuit for $f$ scales polynomially with the number of bits, you're fine. $\endgroup$
    – Tristan Nemoz
    May 25, 2023 at 8:01
  • $\begingroup$ @bubakazouba The operations that you describe are not two different gates. The whole point of $U_f$ is to be applied in superposition. You would have $U_f|000\rangle=|00\rangle\left|\frac{0.4}{\sqrt{2}}\right\rangle$ and $U_f|100\rangle=|10\rangle\left|\frac{0.8}{\sqrt{8}}\right\rangle$. $\endgroup$
    – Tristan Nemoz
    May 25, 2023 at 8:03
  • 1
    $\begingroup$ Thank you this makes sense! $\endgroup$ May 25, 2023 at 21:52

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.