  We propose an algorithm for variational quantum algorithms (VQAs) to optimize
the structure of parameterized quantum circuits (PQCs) efficiently. The
algorithm optimizes the PQC structure on-the-fly in VQA by sequentially
replacing a single-qubit gate with the optimal one to minimize the objective
function. To directly find the optimal gate, our method uses the factorization
of matrices whose elements are evaluated on a set of the slightly-modified
circuits. The matrix factorization enables us to not only unify the existing
sequential methods for further extension but also provide rigorous proofs of
their limitation and potential in comparison with conventional gradient-based
optimizers. Firstly, when the circuits are sufficiently deep, the sequential
methods encounter a barren plateau that the spectrum of the matrix concentrates
on a single value exponentially fast with respect to the number of qubits.
Secondly, if the objective functions are local observables, they can avoid
barren plateaus as long as the depth of the n-qubit PQCs is $O(\log{n})$.
Although the family of these optimizers does not directly employ gradients of
the objective function, our results establish their connection with
conventional optimizations providing a consistent picture of the barren
plateau. We also perform numerical experiments showing the advantages over
conventional VQAs and confirm the successful optimization getting over the
barren plateau in the ground state problem of the mixed field Ising model up to
12 qubits.
