Rewrite circuit with measurements with unitaries

Question

In quantum physics, because of the no-cloning theorem, lots of classical proofs of cryptographic problems cannot be turned into quantum proofs (rewinding is usually not possible quantumly). A dream theorem would be the following:

Dream theorem: Let C be a circuit on $n$ qubits made of a polynomial (in $n$) number of 1-qubit and 2-qubits gates (say $H, T, Ctrl-X)$. Now, run this circuit on input $|0\rangle^{\otimes n}$, and measure the first $k$ qubits in computational basis, giving you the state $|y\rangle\otimes |\phi\rangle$, with $y \in \{0,1\}^k$. Then, there exists a circuit $C'$ with a polynomial number of gates such that $C' |0\rangle^{\otimes (n-k)} = |\phi\rangle$.

Do you have any argument to say that this theorem is true? Or wrong?

Note 1: it would also be great to have "only" an approximate version of this, with $C' |0\rangle^{\otimes n}$ being exponentially close to $|\phi\rangle$.

Note 2: Note that computing $C'$ given $U$ and $y$ should be very hard to do (as soon as PostBQP != BQP), because otherwise it would be more or less equivalent to perform post-selection. But I don't mind, I don't need a constructive proof.

Note 3: This does not directly contradict the theorem (coming from Harrow, Recht and Chuang?) that states that to produce any state $|\phi \rangle$ on $n-k$ qubits, up to precision $\varepsilon$, you need $O(2^{2(n-k)}\log(1/\varepsilon))$ gates", as here $|\phi\rangle$ is quite specific and needs to be produced by a polynomial unitary + measurements.

My intuition on why of course it's true/wrong:

Note 4: One intuition to say that it's not true would be to take a pseudo-random function $h : \{0,1\}^{2l} \rightarrow \{0,1\}^{l}$ (say based on sha hash functions), and implement the unitary $U_h(H^{\otimes2l}|0\rangle^{\otimes 2l})\otimes|0\rangle^{\otimes l} = \sum_{x \in \{0,1\}^{2l}} |x\rangle |h(x)\rangle = \sum_{y \in \{0,1\}^{l}} (\sum_{x \in f^{-1}(y) }|x\rangle) |y\rangle$ and measure the second register, giving $(\sum_{x \in f^{-1}(y) }|x\rangle) |y\rangle$, and then see that if $f$ is truly random the left register seems impossible to generate in polynomial time as it contains an exponential number of elements. But the thing is that it's not even possible to have truly random functions in polynomial time, so the argument does not really work, as for polynomial $h$ an underlying simple representation may exist to efficiently reproduce this state.

Note 5: on the other hand, it seems plausible that the coefficient of the matrix of $C$ are "simple enough" as they are generated from a small circuit, and therefore could be reproduced. I tried to see how to "backpropagate" a measurement in the circuit, by trying to generate lots of possible sub-matrices, and for now I didn't reached a fixed point... but maybe I will at some point!

Answer 1

Here's a silly method that works if you know $y$, you know the probability of measuring $y$, and you can efficiently generate arbitrary-size superpositions of the form $$\frac{1}{\sqrt{N}}\sum_{b < N}\vert b\rangle.$$ To do this, use a Grover-like search: You need two circuits $U_y$ and $U_0$, with the following action: $$U_y\vert x\rangle \vert \psi\rangle = \begin{cases}\phantom{-}\vert x\rangle\vert\psi\rangle&,x\neq y\\-\vert x\rangle\vert \psi\rangle&,x=y\end{cases}$$

$$U_0\vert x\rangle= \begin{cases}\phantom{-}\vert x\rangle&,x=0\\-\vert x\rangle&,x\neq 0\end{cases}$$

Define a "Grover Iteration" $G:=CU_yC^{-1}U_0$ and just apply this repeatedly. If the probability of measuring $y$ is $p$, you will need $O(\sqrt{1/p})$ iterations to have a high probability that the final state is close to $\vert y\rangle \vert\phi\rangle$.

Why: If we define $\vert\psi\rangle=C^{-1}\vert y\rangle\vert \phi\rangle$, and decompose $\vert 0\rangle=\alpha_1\vert \psi\rangle+\alpha_2\vert \psi^\perp\rangle$, then this algorithm will rotate through the space spanned by $\vert \psi\rangle$ and $\vert \psi^\perp\rangle$, the same as Grover's algorithm. Each iteration will rotate by the angle $\theta:= \arccos(\vert\langle \psi^\perp\vert 0\rangle\vert)\approx \sqrt{p}$.

The problem is that we need $\pi/2$ to be near an integer multiple of $\theta$ to get an exact answer. Thus, we add some number $N$ of ancilla qubits, expand the circuit to $C'=C\otimes H^{\otimes N}$, and expand $U_y$ to be

$$U_y\vert x\rangle \vert \psi\rangle\vert n\rangle = \begin{cases}\phantom{-}\vert x\rangle\vert\psi\rangle\vert n\rangle&,x\neq y\text{ or }n>q\\-\vert x\rangle\vert \psi\rangle\vert n\rangle&,x=y\text{ and }n\leq q\end{cases}$$

We choose $q$ such that the probability of both getting $y$ in the first register and $n\leq q$ in the third register is precisely enough that an integer number of these "Grover" iterations will take us to the state $$\frac{1}{\sqrt{q}}\sum_{n\leq q}\vert y\rangle\vert \phi\rangle\vert n\rangle$$

Then we use the arbitrary superposition circuit to clear the third register, and we use a series of $X$ gates to clear $y$ in the first register (since it is a bitstring that is known to us). All that's left is $\vert\phi\rangle$.

Ultimately, the complexity is roughly $O(1/\sqrt{p})$ times the complexity of $C$ itself, plus some number of ancilla (for the $\vert n\rangle$ register) that will be logarithmic in the desired precision of the final state (since we should be able to get $\epsilon$-close to an integer multiple of $\pi/2$ with $\Omega(\log(1/\epsilon))$ ancilla).

Hence: Not very efficient, requires a lot of knowledge of the circuit $C$, but doesn't need any measurements!