  Variational (or, parameterized) quantum circuits are quantum circuits that
contain real-number parameters, that need to be optimized/"trained" in order to
achieve the desired quantum-computational effect. For that training, analytic
derivatives (as opposed to numerical derivation) are useful. Parameter shift
rules have received attention as a way to obtain analytic derivatives, via
statistical estimators. In this paper, using Fourier Analysis, we characterize
the set of all shift rules that realize a given fixed partial derivative of a
multi-parameter VQC. Then, using Convex Optimization, we show how the search
for the shift rule with smallest standard deviation leads to a primal-dual pair
of convex optimization problems. We study these optimization problems
theoretically, prove a strong duality theorem, and use it to establish optimal
dual solutions for several families of VQCs. This also proves optimality for
some known shift rules and answers the odd open question. As a byproduct, we
demonstrate how optimal shift rules can be found efficiently computationally,
and how the known optimal dual solutions help with that.
