Which single fixed unitary can be used to efficiently simulate arbitrary quantum circuit?

Question

Let $|p\rangle|00\ldots0\rangle$ be an initial (basis) state, where $p$ is a binary encoding of the circuit to be simulated and zeros are the working space. We apply some fixed unitary transformation $U$ repeatedly $k_p$ times to the initial state and then measure. Whatever final state we obtain is interpreted as an encoding of the final measured state of the simulated circuit.

Intuitively, $U$ must exist as this is how the universe supposedly works to allow implementation of quantum computers within. But how do we actually realise such a $U$?

Answer 1

You're basically talking here about a quantum cellular automaton. I found a summary here, which I'm not particularly familiar with but looks good at first glance. The papers that I used in the dim and distant past when thinking about this are here and here. Two caveats: (i) they don't restrict themselves to binary. You could surely make an equivalence if you wanted, and (ii) they describe several rounds of unitaries. To just have a single $U$ as you describe, you just have to multiply the multiple steps together. But the multiple rounds make the implementation clearer.

In fact, the above papers do slightly more than you're asking because they are translationally invariant and local. To do what you ask is conceptually a little easier, and I can describe it here:

• you have a computer of 3 registers: the program, a clock and the actual computation. Both the clock and the computation systems start in 0.
• the program consists of binary descriptions of the circuit elements (chosen from a finite set), the qubits they act upon and the time step at which they act. Let's assume for simplicity that you've written out your circuit so that only one gate acts at each time step.
• You can define (in the abstract) an operation which is controlled off one of the "time step" components of the program register (we'll repeat for each one in turn), implementing the specified unitary on the computational register if and only if the time step label matches the time stored in the clock.
• Once you've done that for every time step in the register, add one to the clock.
• repeat

There's a lot of overhead in this, and the $U$ is horribly complicated (hence why I'm only describing it in the abstract), but it's only a polynomial overhead in converting from a circuit.