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.


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.

enter image description here

  • $\begingroup$ Thank you very much for your answer. And then are there some "important" algorithm that do not belong in this class. Actually I am more specifically interested in promising algo for nisq that use one run of a fixed circuit ? Or those algo are more candidate for ftqc and not really good candidate for nisq $\endgroup$ – StarBucK Jan 18 at 22:33
  • $\begingroup$ @StarBucK Right. For instance, Shor's factoring algorithm does not belongs to this class. But note that even in Shor's algorithm, we still uses classical computer, but just not in the same way as we do with VQA. But yes, in general, HHL, Shors etc. would require ftqc $\endgroup$ – KAJ226 Jan 18 at 22:40
  • $\begingroup$ I realized my question was not super clear. So I know that in quantum computing many algo do not require classical processing as in vqe (in the sense the circuit is being updated between each run for instance). My question is more: are there quantum algo which are seriously considered for nisq which do not require such behavior. The algo run on a fixed circuit for each run if various run are required. You probably understood my question in those terms and already answered it with your last sentence but I wanted to be sure. Sorry for my confusion. $\endgroup$ – StarBucK Jan 18 at 22:52
  • $\begingroup$ I guess this is what you meant with your last sentence but as i wasnt super clear i would be glad for a confirmation or infirmation of this. Thanks again $\endgroup$ – StarBucK Jan 18 at 22:53
  • 1
    $\begingroup$ Yes, that is correct. Algorithms like VQE and QAOA can't guarantee that you will get back the answer you are looking within a fixed number iterations... and worst, it might give you back the wrong solution as well depending on the surface structure (how complex it is) of the cost function. $\endgroup$ – KAJ226 Jan 18 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.