Challenges of variational quantum optimization with measurement shot noise

Quantum enhanced optimization of classical cost functions is a central theme of quantum computing due to its high potential value in science and technology. The variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) are popular variational approaches that are considered the most viable solutions in the noisy-intermediate scale quantum (NISQ) era. Here, we study the scaling of the quantum resources, defined as the required number of circuit repetitions, to reach a fixed success probability as the problem size increases, focusing on the role played by measurement shot noise, which is unavoidable in realistic implementations. Simple and reproducible problem instances are addressed, namely, the ferromagnetic and disordered Ising chains. Our results show that: (1) VQE with the standard heuristic Ansatz scales comparably to direct brute-force search when energy-based optimizers are employed. The performance improves at most quadratically using a gradient-based optimizer. (2) When the parameters are optimized from random guesses, also the scaling of QAOA implies problematically long absolute runtimes for large problem sizes. (3) QAOA becomes practical when supplemented with a physically inspired initialization of the parameters. Our results suggest that hybrid quantum-classical algorithms should possibly avoid a brute force classical outer loop, but focus on smart parameters initialization.

Figure 1

(a) The energy landscape in the computational basis, where items are sorted in the lexicographical order for a ferromagnetic model with $L=8$. The small uniform field breaks the degeneracy between the “$00\cdots 0$” and “$11\cdots 1$” bitstrings, with the latter being the global minimum. (b) Sketch of RY-cnot circuits, i.e., a circuit consisting only of $y$ rotations and cnot gates, used in the VQE and commonly employed in related literature. (c) Sketch of QAOA circuit featuring the specific problem Hamiltonian. In both cases we only show the gate decomposition of the first block. The circuit features $d$ blocks, which have the same structure but contain independent variational parameters.

Figure 2

Optimization of the ferromagnetic Ising chain using the VQE Ansatz with depth $d=2$. (a and b): Success probability $F_{\mathrm{succ}}$ as a function of the total number of function calls $n_{\mathrm{calls}}=M\times n_{\mathrm{iter}}$, for (a) $L=8$ spins and (b) $L=14$ spins. Different colors correspond to the different combinations of measurement-shot number $M$ and classical optimization steps $n_{\mathrm{iter}}$. The dashed curve corresponds to the random search with replacement. The inset of (b) shows an example of the interplay between $M$ and $n_{\mathrm{iter}}$. To reach larger $F_{\mathrm{succ}}$ it is better to systematically increase $M$. For $F_{\mathrm{succ}}\approx 0.8$, using $M=512$ appears marginally better than $M=1024$, which in turn becomes optimal at $F_{\mathrm{succ}}\approx 0.9$, and so on. Crucially, each setup performs worse than the random search. (c) Minimal number of function calls $n_{\mathrm{calls}}^{*}$ as a function of the number of spins $L$ for different $F_{\mathrm{succ}}$. Circuits with $d=1$ (full symbols) and $d=2$ (empty symbols) blocks are considered. The thick dashed (red) line represents the scaling $n_{\mathrm{calls}}^{*}\sim 2^L$ corresponding to full enumeration. Thin continuous and dashed lines represent fitting functions of the form $n_{\mathrm{calls}}^{*}=a{2}^{kL}$, and the fitting parameters $a$ and $k$, obtained considering the large $L$ regime, are given in the legend. All the quantities in this figure and the following are dimensionless.

Figure 3

Minimal number of function calls $n_{\mathrm{calls}}^{*}$ as a function of the number of spins $L$ for different $F_{\mathrm{succ}}$. Thin continuous and dashed lines represent fitting functions of the form $n_{\mathrm{calls}}^{*}=a{2}^{kL}$, and the fitting parameters $a$ and $k$, obtained by fitting the large $L$ data, are given in the keys.

Figure 4

Success probability $F_{\mathrm{succ}}$ as a function of the system size $L$ before the classical optimization, for a fixed shot number $M=16$. The QAOA (circles) and VQE (squares) Ansätze have the same depth $d=2$ and randomly chosen parameters. The lines represent fits, obtained from the large $L$ data, as a guide to the eye.

Figure 5

Optimization of the ferromagnetic (first row) and the disordered (second row) Ising chains within the QAOA method. (a), (b), (d), and (e) Success probability $F_{\mathrm{succ}}$ as a function of the total number of function calls $n_{\mathrm{calls}}$ for (a and d) $L=8$ spins and (b and e) $L=14$ spins. The error bars indicate the $25\mathrm{th}$ and the $75\mathrm{th}$ percentiles. Different colors correspond to the different combinations of measurement budgets $M$ and classical optimization-step counts $n_{\mathrm{iter}}$. The dashed curve corresponds to the random search with replacement. (c, f) The optimal number of function calls $n_{\mathrm{calls}}^{*}$ as a function of the number of spins $L$ for different $F_{\mathrm{succ}}$. Circuits with $d=2$ blocks (full symbols) and with $d=4$ blocks (empty symbols) are considered. The thick dashed (red) line represents the scaling $n_{\mathrm{calls}}^{*}\sim 2^L$ corresponding to exact enumeration. Thin continuous and dashed lines represent fitting functions of the form $n_{\mathrm{calls}}^{*}=a{2}^{kL}$, and the fitting parameters $a$ and $k$ are obtained by fitting the large $L$ data and are given in the keys.

Figure 6

(a) Absolute error $\left|\mathrm{err}\right|$ in estimating the gradient as a function of the step $\varepsilon$ of the finite difference approximation. We compare results obtained with a different number of shots $M$. (b) The minimal number of function calls $n_{\mathrm{calls}}^{*}$ as a function of the number of spins $L$, for different success probabilities $F_{\mathrm{succ}}$. Circuits with $d=2$ blocks are considered, with gradient descent (full symbols) and with COBYLA optimizer (empty symbols). The thick dashed (red) line represents the scaling $n_{\mathrm{calls}}^{*}\sim 2^L$ corresponding to exact enumeration. Thin continuous and dashed lines represent fitting functions of the form $n_{\mathrm{calls}}^{*}=a{2}^{kL}$, and the fitting parameters $a$ and $k$, obtained considering the large $L$ data, are given in the keys.

Figure 7

Comparison of the optimizations starting from random (Sec. 4c) and annealing-inspired initializations (linear schedule, Sec. 4e) for the ferromagnetic model. (a and b) The success probability $P_{\mathrm{succ}}$ as a function of the number of spins $L$, obtained within QAOA before (continuous curves) and after (dashed curves) the classical optimization performed for $n_{\mathrm{iter}}$ steps. The number of shots (a) $M=16$ and (b) $M=32$ are considered, chosen so that $M\ll 2^L$. Note that $P_{\mathrm{succ}}$, i.e., the probability to sample at least once the global minimum at the $n$-th iteration, is equal by definition to $F_{\mathrm{succ}}$ when $n_{\mathrm{iter}}=0$. (c) The minimal number of function calls $n_{\mathrm{calls}}^{*}$ as a function of $L$ at fixed success probabilities $F_{\mathrm{succ}}$, starting from the annealing-inspired initialization. Circuits with $d=2$ blocks (full symbols) and with $d=4$ blocks (empty symbols) are considered. The thick dashed (red) line represents the scaling $n_{\mathrm{calls}}^{*}\sim 2^L$ corresponding to exact enumeration. The thin continuous and dashed lines represent fitting functions of the form $n_{\mathrm{calls}}^{*}=a{2}^{kL}$, and the fitting parameters $a$ and $k$, obtained by fitting the large $L$ data, are given in the key.

Figure 8

Success probability $P_{\mathrm{succ}}$ as a function of the number of spins $L$, starting from random and from annealing-inspired initializations for the disordered Hamiltonian. We compare the success probability $P_{\mathrm{succ}}$ obtained via QAOA before (continuous curves) and after (dashed curves) the classical optimization performed for $n_{\mathrm{iter}}$ steps.

Figure 9

Success probability $F_{\mathrm{succ}}$ as a function of the number of spins $L$ without classical optimization. Using the smart linear initialization, $F_{\mathrm{succ}}$ grows when the circuit depth is increased, both for the (a) ferromagnetic model and (b) the disordered problems. In the latter, we consider 30 instances of disorder and the error bars indicate the $25\mathrm{th}$ and the $75\mathrm{th}$ percentiles.

Figure 10

Minimal number of function calls $n_{\mathrm{calls}}^{*}$ as a function of the problem size $L$, for different $F_{\mathrm{succ}}$. VQE circuits with $d=2$ blocks are considered, both with (empty symbols) and without (full symbols) simulated hardware errors, addressing ferromagnetic chains. The thick dashed (red) line represents the scaling $n_{\mathrm{calls}}^{*}\sim 2^L$ corresponding to the exact enumeration. Thin continuous and dashed lines represent fitting functions of the form $n_{\mathrm{calls}}^{*}=a{2}^{kL}$, and the fitting parameters $a$ and $k$, obtained considering the large $L$ data, are given in the legend.

Figure 11

Scaling of $n_{\mathrm{calls}}^{*}$ for various depths $d$, CVaR sample fractions $R$, and SPSA proposal lengths $W$. Three curves (from transparent to solid) show $n_{\mathrm{calls}}^{*}$ for $F_{\mathrm{succ}}=\{0.25,0.5,0.75\}$, respectively. The colors indicate different depths $d=2$ (blue, lowest data), $d=3$ (green, intermediate data), and $d=4$ (purple, highest data). The numbers $(a,k)$ in the brackets in the legends give the optimal values of the exponential fit $n_{\mathrm{calls}}^{*}=a{2}^{kL}$ obtained by fitting the data in the regime $L⩾8$.