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!

  • 1
    $\begingroup$ Is the idea that we want a computable/efficient method to produce $C'$, given $C$, or produce $C'$ given $C$ and $y$? $C'$ depends on $\phi$, but do we want a $C'_\phi$ that works for some $y$ (i.e., there exists a $y$ such that $\vert y\rangle \vert \phi\rangle$ is a possible outcome of measuring $C\vert 0\rangle$)? $\endgroup$
    – Sam Jaques
    Mar 6, 2019 at 15:07
  • $\begingroup$ @SamJaques The $y$ and $C$ are both given and fixed (so it fixes also the $|\phi\rangle$, and you want to say that there exists $C'_{C,y}$ such that $C'_{C,y}|0\rangle = |\phi\rangle$, with $C'_{C,y}$ polynomial circuit. Note I don't want to have a way to find this $C'_{C,y}$ efficiently (see remark 2), I just want to know that it exists. $\endgroup$ Mar 6, 2019 at 18:32
  • $\begingroup$ @SamJaques : and the other thing you say with "There exists a $y$ ..." could be interesting to have (as a first step), but to be usefull we need that the proportion of such "working y" is overwhelming. $\endgroup$ Mar 6, 2019 at 18:38
  • $\begingroup$ This is related to my question here: cstheory.stackexchange.com/questions/41625/… I still do not have a definitive answer here, but it seems like this problem would collapse some computational classes (although the argument is not fully worked out yet). $\endgroup$
    – John
    Mar 11, 2019 at 17:21
  • $\begingroup$ @John : Hum, I'm not 100% convinced the two problems are related (or at least it's not rock clear to me). Indeed, if you see the ancillae as the measurements, then as soon as your ancillae are set back to 0 (that's the usual definition of ancillae), then my problem becomes trivial. And if for some reasons your ancillae are just traced out without clearing them, then you'll end up with a density matrix, and you will lose the "measurement outcome": in my case I actually have the measurement outcome, and the final state is a pure state... $\endgroup$ Mar 18, 2019 at 9:36

1 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!

  • $\begingroup$ Thanks for the help. I like the idea, but there is an annoying issue: the p is usually in practice of the order of $\frac{1}{2^{k}}$ for, say, a uniform superposition. So it means the algorithm would run in time $O(\sqrt{2^k})$ which is still exponential in the number of measurements... So we gain a sqrt over the naive algorithm, but it's still exponential. But thanks, it's a first improvement ;-) $\endgroup$ Mar 18, 2019 at 9:26
  • $\begingroup$ I'm skeptical of improvements in that case, because if you had such a method, then I could pick any $k$ input boolean function $f$ then define $C$ as a circuit which (1) makes a superposition of all inputs in $\vert\phi\rangle$, (2) evaluates $f$ on those inputs, (3) saves the result to $\vert y\rangle$. Then you construct your circuit to produce $\vert \phi\rangle$ corresponding to $y=1$, and you've found a pre-image of 1 under $f$. We know that $O(\sqrt{2^k})$ is the best complexity for this problem, though. $\endgroup$
    – Sam Jaques
    Mar 19, 2019 at 19:49
  • $\begingroup$ Well there is no contradiction here, as finding this circuit corresponding to $y = 1$ may takes exponential time, but I don't mind. I just want the final circuit to be polynomial. So for example if the function is one-to-one, I could completely find the preimage $x$ of 1 (in time $O(2^k)$), and then output the circuit $C_1$ that maps 0 to $x$: $C_1 |0\rangle = |x\rangle$. And this $C_1$ is made only from few X's, so it's still polynomial. $\endgroup$ Mar 19, 2019 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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