How to implement a while loop in a quantum computer?

Question

How can a while loop be implemented in a quantum computer?

If quantum computing consists of :

1. preparing a state
2. applying a unitary operator
3. measuring,

then it seems like it's not possible to wait for an indefinite amount of time before measuring. How can one know that the while loop ended and that it's time to mesure ?

Answer 1

The way that many algorithms would deal with such a desire is to incorporate the measurement at a more fundamental level, essentially making it part of the 'while' condition. i.e. you have an output qubit that is 0/1 for computation complete or not, you measure it, and decide whether to continue or not. Because that's a bit of classical processing, it doesn't have to be reversible, and you avoid the need for infinite space.

For example, many quantum algorithms only have a finite probability of success. For example, search or Factoring. In both of these cases, you know if you succeeded, and so there's an additional bit of classical logical that says "repeat until successful" i.e. a while loop.

Answer 2

I think the closest thing to a "while loop" in a quantum algorithm is something like the Variational Quantum Eigensolver (VQE) or other classical-quantum hybrid algorithms. In these, a certain cutoff is defined for when the variational circuit is "close enough" to approximating the desired quantum state, so you can think of it as a while loop.

Generally, however. quantum algorithms (as they currently stand) are more closely related to classical programs which do computations, instead of ones that exhibit lots of higher level logic. Some work has begun to be done on stuff like quantum assertions, which might begin to allow us to start growing in that direction, but seeing as quantum gates are still applied by classical machines, bridging that quantum-classical gap requires a measurement.

Answer 3

One option would be to identify an upper bound for the number of iterations of the while loop and implement a traditional and conditional loop:

Consider you have three registers

• a control $|\text{cntl}\rangle$ bit
• some state $|\psi\rangle$
• some condition for the while loop $|\text{cond}\rangle$

Assume the maximal number of iterations is bounded to $B$, then you perform the following $B$ times:

1. Check if condition $|\text{cond}\rangle$ is fulfilled for register $|\psi\rangle$. Save the output in $|cntl\rangle$ (note that $|\text{ctl}\rangle$ will represent a superposition of $\{0,1\}$, s.t. its $1$ for those substates that require additional iteration)
2. Perform the unitary operation on register $|\psi\rangle$ conditioned on $|\text{ctl}\rangle$
3. (Uncompute $|cntl\rangle$)
4. Repeat.

(If someone can tell me how to use Tikz code or insert a picture, I can provide you a circuit representation)