1
$\begingroup$

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

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

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ Jul 18 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.