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$?


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

  • $\begingroup$ Thanks. I guess the trick I was missing is that the clock always makes one step forward and thus can't destroy interference. $\endgroup$ Jun 9, 2021 at 6:41

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.