Do quantum loops exist?

Question

I was checking the book from Nielsen and Cheng and they mention in chapter 1, page 23, that quantum circuits don't have loops:

"There are a few features allowed in classical circuits that are not usually present in quantum circuits. First of all, we don’t allow ‘loops’, that is, feedback from one part of the quantum circuit to another; we say the circuit is acyclic."

But then, reading a paper about it, I found this:

"To help reasoning about the correctness of quantum programs, we extend the proof rules presented by Morgan for classical probabilistic loops to quantum loops. These rules are shown to be complete in the sense that any correct assertion about the quantum loops can be proved using them. Some illustrative examples are also given to demonstrate the practicality of our proof rules." Reference: https://www.sciencedirect.com/science/article/pii/S0304397507004926

So, can quantum algorithms have loops or not? the paper does not talk about quantum circuits, but more generally, it talks about quantum loops. Are the absence of loops in quantum computation a limitation of the circuit-based model?

thanks

Answer 1

It depends what you mean by "loop".

Nielsen and Chuang are referring to loops like the ones that appear in an SR latch. Wires literally running backwards to earlier in the circuit, creating dynamics:

These kinds of loops would allow you to make quantum circuits that, if read literally, required violating the no-cloning theorem. Allowing them would create a lot of problems, so Nielsen and Chuang don't.

Giving a consistent treatment to these kinds of loops isn't impossible. For example, the ZX calculus is a quantum diagram language that allows loops and contains quantum circuits as a subset. But it does cause a lot of hassle. For example, although the meaning of a ZX diagram is unambiguous, it can be expensive to translate a ZX diagram into a series of steps that can be executed on a quantum computer, and that series of steps might be enormous.

Your other reference is referring to "loops" like loops in a programming language, where certain steps are repeated until a condition is met. Those are fine.