Are quantum computers turing complete?

Some days ago, I’ve been participating the Qiskit Summer school. It was such a great experience that made me learn a lot.

Besides techniques on error mitigation, correction, optimization, etc; that were exposed during the course, the event brought me some pretty nice ideas that led me to write this blog post.

Back story

Sometime ago, I answered a question in the quantum computing stackexchange about if there were such a thing like a quantum operational system. The answer I gave was:

Since then, I’ve been thinking on the topic.

Are we able to have something relative to classical operational systems, or even CPUs, in quantum computers?

Maybe?

In theory, quantum computation is an extension of classical computation. We can have the same bit-strings generated by a classical computer in a quantum form by quantum means.

Since we can have universal gate set that act in many different states in the Hilbert space and we can map the same classical bit-strings in a quantum system, shouldn’t it be possible to have such a quantum OS/CPU?

Even thought it seems a little easy to answer that, at the same time some questions might appear:

1. How does these systems could benefit from quantum weirdness, like entanglment and superposition?
2. Since every operation must be reversible, isn’t it a waste of time undoing each computation in order to have clean qubits to work with?
3. What about measurements? A quantum OS would be pretty much a program in superposition that when we measure it turns into its classical relative?

At first, It may not seem as something useful, since we would have constantly measure the system and have the OS, or whatever program, we want to be collapsed with some probability.

Classical systems have some advantages when dealing with these issues. Adding a bit in classical systems is way easier and cheaper than current quantum computers.

In a classical computer we can copy, move and transform data as much as we can. However, in quantum systems we are limited by the Non-cloning theory and desctrutive measurements.

In comparison, a classical system can easily apply operations, get the result imediately, or after some CPU cycles, and apply another operation in response. In a quantum system otherwise, we would require classical intervention or the addition of auxiliary qubits and mathematical tricks that could be expensive to generalize, or maybe not possible at all.

ALU in superposition

After sometime thinking on the topic, I decided to make a simple circuit to start reasoning on the topic.

My first attempt was to get a relative to an ALU in quantum.

In this simple circuit, we have $6$ qubits. The first three are in charge of holding the address of an operation. The next two are the inputs $\ket{ab}$. The last one is the data bus which I named $\ket{c}$.

The circuit implements the following operations for two bits (the sequence will differ when using little-endian or big-endian, we are using big-endian but Quirk circuits use little-endian):

After operating these inputs and recieving the outcome, we could store it in a sort of memory such as the bucket memory or many other methods for QRAM.

I remember sometime ago I “implemented” a relative to a Latch/Flip-Flop in a quantum circuit, I couldn’t find it, unfortunately, but I remember it made me so glad.

To make a complete 1:1 transition from classical to quantum, we could also implement this Latch as a data saver, composing it to get larger memories.

Another interesting thing about such quantum systems is the ability to put things in superposition. Taking the previous ALU example, we could define equal superpositions for input qubits.

Using superposition we would be able to evaluate multiple things at once, however it would be trick to store in memory due to no-cloning theory.

Another interesting thing is that, to process anything we need to apply this unitary onto a state $\ket{\phi}$ and then to reutilize these qubits we would need to undo the computationby applying $U^\dagger$.

In general!

We can conclude three things here:

1. It is therorectically possible to map a classical system into quantum, since it’s pretty much an extension, so using classical methods are some way possible (not quite sure on that tho)
2. What would be the usefulness of that?
3. How difficult it would be to exploit the quantum effects to actually create an OS or CPU that’s better than its classical relative.

Discussion

Even though having a quantum OS or CPU would be a really insteresting and nerdy stuff to see, it would have no use for now.

The quantum systems now days are pretty much static things. We don’t have enough coeherent time to get outcomes in between.

Classical computers rely deeply on their memory management and the iterative calls to the CPU and peripherals. If we could some way apply dinamically operations, read and store we would get something similar to classical.

One would argue that we already have dynamic circuits. Althought that’s true, what’s the use of having a classical computer to manage a quantum computer that’s simulating a classical computer.