Algorithms
Optimizer

Algorithms for NISQ devices are mostly quantum-classical hybrid algorithms in which some parameters $\vec{\theta}$ are optimized through classical algorithms. Here we introduce classical algorithms used in NISQ applications.

Powell method

Powell method is a gradient-free optimization algorithm for scaler real-valued functions. Details are found here.

BFGS (Broyden–Fletcher–Goldfarb–Shanno) method

BFGS method belongs to the quasi-Newton methods and requires gradients of objective functions for optimization. Details are found here.

Sequential minimal optimization (SMO) method for quantum-classical hybrid algorithms

SMO method for quantum-classical hybrid algorithms optimizes parameters of a quantum circuit appearing in typical quantum-classical hybrid algorithms for NISQ devices. SMO method works under following conditions (which most quantum-classical hybrid algorithms with parameterized quantum circuits satisfy):

1. The parameterized quantum circuit $U(\vec{\theta})$ is product of Pauli rotation gates with a single parameter and some gates without parameters, i.e., $$ U(\vec{\theta}) = U_1 e^{i\theta_1 P_1} U_2 e^{i\theta_2 P_2}\cdots U_N e^{i\theta_N P_N}U_{N+1}, $$ where $P_i^2 = I$ (identity) for all $i$.
2. The cost function under optimization is a linear combination of $M$ expectation values of observables for the parametrized quantum state $|\psi(\vec{\theta})\rangle = U(\vec{\theta})|0\rangle$, $$L(\vec{\theta}) = \sum_{k=1}^M c_k \langle \psi(\vec{\theta})|O_k |\psi(\vec{\theta})\rangle, $$ where $c_k$ is coefficient and $O_k$ is observable.

It can be shown that the cost function is a $\pi$-periodic function of $\theta_i$ for all $i$ under these conditions. Therefore, one can determine the exact argmin/argmax of $\theta_i$ by evaluating the cost function at only three independent points with respect to the parameter $\theta_i$. This approach gives a fast and stable way to optimize the parameterized circuit $U(\vec{\theta})$. More details are found in the reference below.

Reference

• "Sequential minimal optimization for quantum-classical hybrid algorithms", K. M. Nakanishi, K. Fujii, and S. Todo, https://arxiv.org/abs/1903.12166
• "A Jacobi Diagonalization and Anderson Acceleration Algorithm For Variational Quantum Algorithm Parameter Optimization", R. M. Parrish et al., https://arxiv.org/abs/1904.03206