  This paper proposes a new procedure called quantum shadow gradient descent
(QSGD) that addresses these key challenges. Our method has the benefits of a
one-shot approach, in not requiring any sample duplication while having a
convergence rate comparable to the ideal update rule using exact gradient
computation. We propose a new technique for generating quantum shadow samples
(QSS), which generates quantum shadows as opposed to classical shadows used in
existing works. With classical shadows, the computations are typically
performed on classical computers and, hence, are prohibitive since the
dimension grows exponentially. Our approach resolves this issue by measurements
of quantum shadows. As the second main contribution, we study more general
non-product ansatz of the form $\exp\{i\sum_j \theta_j A_j\}$ that model
variational Hamiltonians. We prove that the gradient can be written in terms of
the gradient of single-parameter ansatzes that can be easily measured. Our
proof is based on the Suzuki-Trotter approximation; however, our expressions
are exact, unlike prior efforts that approximate non-product operators. As a
result, existing gradient measurement techniques can be applied to more general
VQAs followed by correction terms without any approximation penalty. We provide
theoretical proofs, convergence analysis and verify our results through
numerical experiments.
