Suppose Alice asks to use Eve's quantum computer. Alice loads her hidden quantum state into the computer, then gives Eve a program to run. The program will apply unitary operations and measurements to Alice's state, and Eve will report the measurements to Alice.
Eve wants to make an approximate clone of Alice's final state (the state after the program has run). Eve knows the program that ran, and all the measurement results that were generated, but isn't allowed to tamper with the program or the state.
If Eve has no measurement results, then the no-cloning theorem applies. The best Eve can do is use the optimal [approximate] cloning procedure, which will do terribly. But it's also possible that there's lots of measurement results that together imply Alice's whole state... it's just a matter of putting all the pieces together. I'm interested in the latter scenario.
Assuming Eve wants to generate an optimal clone given the available measurement information, what is the expected computational complexity of her task in terms of the number of qubits $n$ and the number of operations $m$? How hard is it to take a "this was done then that was measured then this was done then that was measured" history and produce a plausible output state? Are there any viable algorithms, or is this simply an exponentially difficult problem?
- The measurement results are computed live; they're not given. As a result, exponentially unlikely measurement results (such as the ones you'd use to trivially encode NP-hard problems into Eve's task) have an exponentially reduced impact on the expected running time.
- A naive classical algorithm is to store a $2^n \times 2^n$ density matrix on a classical computer and mimic all operations and measurements onto the density matrix. But this has complexity $O(m 4^n)$, which is not very good. Inference is expensive.
- A naive quantum algorithm is to create lots random states, mimic all operations and measurements applied to the real state onto each of the initially-random states, and throw out any that don't match the observed measurements. This has complexity $O(m 2^m)$, which is worse than $m 4^n$ since $m$ will generally be much much larger than $n$. Post-selection is expensive.
- A magical Post-BQP machine could trivially solve the problem in $O(m)$ time.
- Related blog post
- It seems like a lot of cryptography problems would fall under this regime. An answer that's just a hardness-by-reduction-from-cracking-AES is fine, though I feel like if Eve knows the qubits are not superposed in the computational basis then measuring them should be fair game.