# How to implement NM Algorithm for Variational Quantum Eigensolver?

First of all: thanks for reading again. I appreciate the feedback I have gotten from this community the past weeks as I started to feel ready to ask questions about quantum computing topics.

I am trying implement the following paper: https://arxiv.org/abs/1509.04279.

I have used the ansatz represented the quantum circuit shown in Cirq's tutorial. I even tried to apply Farhi and Neven's method of gradient descent to see whether that could help find the minimal expected energy of the system. (It did not).

But I have gone back to the original paper by McClean et al. and they discuss about NM Algorithm to find the minimal energy of the system.

Here it is my question: how can it be possible to apply NM when you cannot have a given order a-priori.

Here it is what I think I understand:

1. The objective function is the energy measurement operation from Cirq's tutorial.
2. $$x_1,...., x_n$$ are the gate parameters in each of the quantum gates for the circuit representing the ansatz.

So one of my questions would be how to frame the algorithm using Cirq's circuit to properly implement it to reproduce the results of the paper. I am unsure right now of how to use the measured energy as a way to calculate the adjustments necessary to the gate parameters to minimize the measured energy.

And also, how should I think about the objective function? Is it comparable to a cost function, or loss function, of the circuit in question?

If you are looking for a more complete implementation of a quantum variational algorithm in the context of Cirq, I would recommend looking at the second example in the OpenFermion-Cirq notebook found here. It uses a custom ansatz for hydrogen in a minimal basis, but makes a bit more explicit all the required pieces. Another good example, perhaps without the chemistry overhead, is the QAOA notebook written more generally for Cirq, and has some of the experimental considerations (such as finite sampling) included. I realize these examples are not completely telling for all of your questions, but following each of the subroutines down their respective rabbit holes should allow you to see all of the pieces.

I want to offer a word of caution however that the first example (and many others you will find) explores variational algorithms in a context that can be useful, but is not completely true to how one would experience it in an experiment and hence there are big caveats for evaluation of classical optimizers (like NM) in this setting. In particular, it queries the objective function (which is the same as the energy or a cost / loss function in this case) essentially perfectly (close to achievable precision on the classical device) for negligible cost. This lets one explore the parameter space and cost function surface, but is not informative as to the best optimizer to use in an experiment.

The reason is that classical computers do arithmetic 1 digit at a time for floating point numbers (sometimes phrased as costing $$\log(1/\epsilon)$$ for precision $$\epsilon$$) while readout from quantum computers costs you something more like $$1/\epsilon^\alpha$$ in number of circuit repetitions, where usually for a near-term device $$\alpha=2$$, analogous to Monte Carlo scaling. This means you can choose to pay more for additional precision in the readout, but the cost is steep.

As a result, practical optimizers for these problems need to tolerate heavy noise to be effective, often lumped into their own subcategories of optimizers for stochastic functions. The original work used Nelder-Mead as a hack to avoid focusing on the classical part of the problem (the quantum experiment was the focus), however this was perhaps a mistake in hindsight. I would never recommend using it (or other optimizers which are for deterministic problems by design) for these problems in practice, especially in gearing up for a challenging experiment.

Considering the case where one is gearing up for experiment, with real readout considerations, it's absolutely crucial to judge success based on expected experimental time, and not something intangible or missing information like "number of iterations". My practical recommendation at the moment would be to pair a reasonable, unbiased estimator of the gradient(such as that in the work by Farhi and Neven, the recent work by Napp and Harrow, or something like simultaneous perturbation by stochastic approximation) with a decaying step size (sometimes called learning rate) that is adjusted for problem instances. Tuning this decay and other method hyperparameters in a good way is crucial for success.

If one merely wants to toy with the ansatz and problem without worrying about performance in experiment (where one assumes extremely accurate evaluations are possible in negligible time), the considerations are different and simple implementations that are already available are probably preferred. For example, BFGS for local optimization and basin hopping using BFGS as the local optimizer if global search is of interest are probably good default choices.

As an additional note, it's important to remember that most quantum variational algorithms today will generally be non-convex optimizations. As a result, having a good initial guess for the parameters is extremely important. Also, random initialization (as one often does in machine learning) is fraught with difficulties that we explored in some depth.