<p>In short, yes.</p>
<p>The circuit <span class="math-container">$Q$</span> you describe is unitary: let <span class="math-container">$|\phi\rangle=\sum_x a_x|x\rangle$</span> and <span class="math-container">$|\psi\rangle=\sum_x b_x|x\rangle$</span> be normalized states, then
<span class="math-container">$$\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.$$</span>
So we have that <span class="math-container">$Q$</span> preserves the norm as a unitary should when applied on state of the form <span class="math-container">$|\phi\rangle|0\rangle$</span>, and it can be extended to act as a unitary on arbitrary states (when the second qubit is not <span class="math-container">$|0\rangle$</span>). See e.g. Exercise 2.67 of Nielsen &amp; Chuang.</p>
<p>As to how <span class="math-container">$Q$</span> can be implemented in poly-size if <span class="math-container">$Q_x$</span> are poly-size, consider first that for any poly-size classical circuit <span class="math-container">${\tt S}(x)$</span>, you can construct a poly-size quantum circuit <span class="math-container">$U^{\tt S}$</span> whose action on basis states <span class="math-container">$|x\rangle|y\rangle$</span> is <span class="math-container">$$U^{\tt S}|x\rangle|y\rangle = |x\rangle |y\oplus {\tt S}(x)\rangle.$$</span>
This is how classical oracles are usually implemented as quantum gates.</p>
<p>Next, you need a quantum circuit that takes as input the description of a quantum circuit and applies it to the initial state <span class="math-container">$|0\rangle$</span>. 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<span class="math-container">$\times$</span>width<span class="math-container">$\times\log$</span>(size of gateset). Each batch of <span class="math-container">$k$</span> qubits can interpreted as a gate <span class="math-container">$|G_{(i,j)}\rangle$</span> to be applied to wire <span class="math-container">$i$</span> at timestep <span class="math-container">$j$</span>. Then you can use controlled-<span class="math-container">$G$</span> gates at the right places so that the right gate is applied to the right wire at the right time. I found <a href="https://arxiv.org/abs/0804.2429" rel="nofollow noreferrer">this paper</a> that I think goes into the details, but full disclosure I haven't read it.</p>

CC BY-SA 4.0
2022-07-18T01:21:07.510Z
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!
Cao Shuajiao
CC BY-SA 4.0
2022-07-15T19:52:25.390Z
2022-07-15T19:52:25.390Z
lamontap
<p>My question is that, assuming there exist  a sampler <span class="math-container">$\mathtt{S}$</span> (probably classically efficient) takes <span class="math-container">$x\in\{0,1\}^{n}$</span> as input and outputs a quantum polynomial-time circuit <span class="math-container">$\mathtt{S}(x)= Q_{x}$</span> satisfies
<span class="math-container">$$Q_{x}|0^{n}\rangle=|\phi_{x}\rangle.$$</span>
Then if there exists a circuit <span class="math-container">$Q$</span> such that
<span class="math-container">$$Q\sum_{x}a_{x}|x,0\rangle=\sum_{x}a_{x}|x,\phi_{x}\rangle,$$</span>
or equivalently
<span class="math-container">$$\sum_{x}a_{x}|x,Q_{x},0\rangle\rightarrow^{Q}\sum_{x}a_{x}|x,Q_{x},\phi_{x}\rangle ?$$</span></p>

CC BY-SA 4.0
2022-07-13T06:21:52.770Z
The circuit $Q$ here is also required to be polynomial-time circuit, apologize for the missing condition.
Cao Shuajiao
<quantum-computing><quantum-information>
Can a collection of quantum circuits be calculated in superposition state?
Cao Shuajiao
# Can a collection of quantum circuits be calculated in superposition state?

(Asked by: username_0 on 2022-07-13)

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

**Tags:** quantum-computing, quantum-information
> **Comments:**
> **username_0**: The circuit $Q$ here is also required to be polynomial-time circuit, apologize for the missing condition.  

---

## 1 answers

### Answer by username_1 on 2022-07-15. Score: 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](https://arxiv.org/abs/0804.2429) that I think goes into the details, but full disclosure I haven't read it.

> **Comments:**
> **username_0**: 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!  

---

