Can a collection of quantum circuits be calculated in superposition state?

Question

My question is that, assuming there exist a sampler $\mathtt{S}$ (probably classically efficient) takes $x\in\{0,1\}^{n}$ as input and outputs a quantum polynomial-time circuit $\mathtt{S}(x)= Q_{x}$ satisfies $$Q_{x}|0^{n}\rangle=|\phi_{x}\rangle.$$ Then if there exists a circuit $Q$ such that $$Q\sum_{x}a_{x}|x,0\rangle=\sum_{x}a_{x}|x,\phi_{x}\rangle,$$ or equivalently $$\sum_{x}a_{x}|x,Q_{x},0\rangle\rightarrow^{Q}\sum_{x}a_{x}|x,Q_{x},\phi_{x}\rangle ?$$

Answer 1

In short, yes.

The circuit $Q$ you describe is unitary: let $|\phi\rangle=\sum_x a_x|x\rangle$ and $|\psi\rangle=\sum_x b_x|x\rangle$ be normalized states, then $$\langle 0|\langle \psi|Q^*Q|\phi\rangle|0\rangle= \sum_x b^*_x\langle 0 | Q_x^* \cdot a_x Q_x |0\rangle = \sum_x b^*_x a_x=\langle\psi|\phi\rangle.$$ So we have that $Q$ preserves the norm as a unitary should when applied on state of the form $|\phi\rangle|0\rangle$, and it can be extended to act as a unitary on arbitrary states (when the second qubit is not $|0\rangle$). See e.g. Exercise 2.67 of Nielsen & Chuang.

As to how $Q$ can be implemented in poly-size if $Q_x$ are poly-size, consider first that for any poly-size classical circuit ${\tt S}(x)$, you can construct a poly-size quantum circuit $U^{\tt S}$ whose action on basis states $|x\rangle|y\rangle$ is $$U^{\tt S}|x\rangle|y\rangle = |x\rangle |y\oplus {\tt S}(x)\rangle.$$ This is how classical oracles are usually implemented as quantum gates.

Next, you need a quantum circuit that takes as input the description of a quantum circuit and applies it to the initial state $|0\rangle$. I won't go into the details, but it's not too hard to convince oneself that this is possible. Consider an encoding of size depth$\times$width$\times\log$(size of gateset). Each batch of $k$ qubits can interpreted as a gate $|G_{(i,j)}\rangle$ to be applied to wire $i$ at timestep $j$. Then you can use controlled-$G$ gates at the right places so that the right gate is applied to the right wire at the right time. I found this paper that I think goes into the details, but full disclosure I haven't read it.