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

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 ?$$

• The circuit $Q$ here is also required to be polynomial-time circuit, apologize for the missing condition. Jul 13 at 6:21

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.
• Thank you for your detailed answer, my question is mainly about the efficiency of the constructed $Q$. I doubted this transformation might not be efficient for some collections of polynomial-size circuits $\{Q_{x}\}$. I'll read the paper you mentioned. Thank you again! Jul 18 at 1:21