NISQ algorithm: do they all have circuit updated between each run AND impossible to predict when they will stop?

Question

I don't know very much the NISQ algorithms, but the ones that I know are based on kind of "Hybrid" calculation between a quantum computer and a classical computer.

Indeed, for instance in QAOA, we can try to find the fundamental of some Hamiltonian. To do this, we run a circuit with a given set of gates. We measure the qubit and "feed" it to some classical processing that either say "fundamental may have been found: stop", or "make more iterations". When "more iterations" occurs the circuit is changed according to a classical algorithm and the quantum algorithm is run again. And so on until we believe we found the solution (my summary is probably a little bit short/exagerated as I don't have in full memory the details but from what I remember it is something roughly like this)

In this algorithm there are two important features:

• There is a classical processing around that is used in parallel of the quantum which goal is to "update" the quantum circuit.
• We basically cannot know when the algorithm will stop "theoretically". It is not like in fault tolerant quantum computing where an algorithm has a fixed Depth so that we can deduce when it will stop.

I wanted to know if all (seriously considered) NISQ algorithms are based on those two elements: circuit updated from classical processing AND you don't know "in advance" when the algorithm will stop ?

From the example I read I think this is true but I don't know enough to be sure.

Answer 1

What you described is the class of Variational Quantum Algorithms. Variational Quantum Eigensolver (VQE) and QAOA (Quantum Approximate Optimization Algorithm) are belong into this class. Says, you want to solve the following eigenvalue problem for some Hermitian operator $H$

$$ H|\psi \rangle = E|\psi\rangle $$

In particular, you want to find the smallest eigenvalue of $H$, then you can define a functional

$$ E\big[ |\psi \rangle \big] = \langle \psi|H|\psi\rangle $$

then base on the variational principle, minimizing this functional $\min E\big[ |\psi \rangle \big] $ gives you approximately the lowest eigenvalue.

The key ingredient on why these type of problems is appropriate on NISQ is because you can prepare $|\psi\rangle$ and potentially evalutating $\langle \psi|H|\psi\rangle $ much faster on a quantum computer. This is especially true for some problems, like the electronic structure problem in quantum chemistry.

Now, during the classical minimization process, you can absolutely stuck at a local minimum. And you are right that we don't know when this optimization process will stop, but you can place a threshold in your algorithm. That is you can set the maximum number of iterations to be says 1000.

It should also be noted that if your parameterized circuit (the circuit that one uses to prepare the trial state $|\psi\rangle$ ) has a lot of variables then you tends to run into the problem of Barren Plateaus.