Timeline for Rewrite circuit with measurements with unitaries
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 19, 2019 at 21:50 | comment | added | Léo Colisson | 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. | |
| Mar 19, 2019 at 19:49 | comment | added | Sam Jaques | 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. | |
| Mar 18, 2019 at 9:26 | comment | added | Léo Colisson | 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 ;-) | |
| Mar 12, 2019 at 12:36 | history | answered | Sam Jaques | CC BY-SA 4.0 |