In classical deep learning, calculating gradients for models with billions of parameters is remarkably efficient. This efficiency is driven by backpropagation, an implementation of reverse-mode automatic differentiation. Backpropagation allows a classical computer to evaluate the gradient of a loss function with respect to every single parameter in a network at a computational cost roughly proportional to a single forward execution of the network.
In variational quantum algorithms (VQAs) and quantum neural networks (QNNs), this mathematical luxury disappears. As explained by Amira Abbas et al., quantum mechanics imposes a fundamental constraint: measurement collapse. You cannot inspect or cache the intermediate state of a quantum circuit without destroying its quantum superposition, and the no-cloning theorem prevents making a copy of the state to process later.
Because we cannot propagate errors backward through an active quantum state, quantum optimization faces a severe gradient estimation bottleneck.
The Linear Scaling of the Parameter-Shift Rule
To calculate the gradient of a cost function on real quantum hardware, researchers typically rely on the parameter-shift rule. The core intuition behind the parameter-shift rule is elegant: for many quantum gates, the derivative of an expectation value with respect to a gate parameter $\theta$ can be computed by evaluating the exact same circuit with the parameter shifted forward and backward by a constant amount:
$$\frac{\partial \langle O \rangle}{\partial \theta} \propto \langle O \rangle_{\theta + \frac{\pi}{2}} - \langle O \rangle_{\theta - \frac{\pi}{2}}$$
While mathematically exact, this mechanism introduces a steep "parameter tax." To compute a full gradient vector for a circuit containing $M$ tunable parameters, the circuit must be executed at least $2M$ times. As highlighted by Di Luo et al. and Philipp Schleich et al., this linear scaling ($O(M)$) creates a massive computational barrier as models grow.
Classical Backpropagation:
[Forward Pass] -> [Cache Activations] -> [Backward Pass] = O(1) circuit equivalents for ALL parameters
Quantum Parameter-Shift:
Parameter 1: [Shift +] [Shift -]
Parameter 2: [Shift +] [Shift -]
...
Parameter M: [Shift +] [Shift -]
Total Cost = O(M) circuit executions
This linear scaling is further worsened by the statistical nature of quantum mechanics. Quantum computers do not output exact expectation values; they output discrete measurement outcomes. To resolve an expectation value to a precision of $\epsilon$, a quantum device must sample the circuit $1/\epsilon^2$ times (known as shot noise).
When a quantum network is initialized randomly, it often encounters a barren plateau—a vast, flat region of the optimization landscape where the variance of the gradient vanishes exponentially with the number of qubits. As demonstrated by Sergio Boixo et al., if the true gradient is exponentially small, the number of measurement shots required to distinguish the gradient from random noise scales exponentially ($1/\epsilon^2 \sim e^n$). Even outside of barren plateaus, Mohsen Heidari et al. note that the sheer volume of measurement shots required across hundreds or thousands of parameters severely limits the scalability of on-chip training workflows (Hanrui Wang et al.).
The Quadratic Escalation of Geometric Tensors
The bottleneck becomes even more restrictive when moving beyond standard first-order gradient descent. Advanced optimization strategies—such as natural gradient descent or variational quantum time evolution—require tracking how the quantum state changes geometrically as parameters change. This requires calculating the Quantum Geometric Tensor (QGT), which serves as a metric tensor for the parameter space.
Because the QGT measures the relationships and overlaps between variations of pairs of parameters, its calculation requires evaluating combinations of shifts across multiple gates simultaneously. As Jannes Nys et al. point out, this escalates the hardware execution overhead from linear to quadratic ($O(M^2)$). For a relatively modest variational circuit with 1,000 parameters, a single optimization step can require millions of independent circuit evaluations, transforming a training run from a matter of hours into weeks of continuous hardware runtime. A similar scaling challenge appears in adaptive algorithms, where Gaurav Gyawali observes a severe classical bottleneck when calculating gradients for every candidate operator in a large pool to determine the next optimal gate.
Strategies for Bypassing the Bottleneck
To make near-term quantum machine learning viable, researchers are developing methods to bypass or mitigate this linear and quadratic scaling. These approaches generally fall into three categories:
1. Stochastic and Coordinate Approximations
Instead of calculating the exact gradient vector at every step, can we get away with cheaper approximations? One popular approach is Simultaneous Perturbation Stochastic Approximation (SPSA). As explored by Maniraman Periyasamy et al. and Marco Wiedmann et al., SPSA perturbs all parameters simultaneously by a random sign vector. This reduces the required circuit evaluations per optimization step to a constant (typically just 2 evaluations), completely decoupling the step cost from the number of parameters $M$.
Alternatively, Ziyan Ding et al. propose Random Coordinate Descent (RCD). Instead of updating every parameter at once, RCD selects a single random parameter to evaluate and update at each step. This trades the directional accuracy of a full gradient vector for a dramatic reduction in quantum hardware calls per iteration.
2. Dynamical Forecasting
Rather than trying to optimize the gradient evaluation itself, another strategy treats the optimization path as a continuous dynamical system. Di Luo et al. developed QuACK, a framework that uses classical machine learning to learn a "Koopman operator" from a few initial hardware gradient steps.
Once trained, this classical operator can predict future parameter trajectories over multiple steps. By substituting expensive quantum hardware measurements with fast classical model inferences, this approach can skip hundreds of intermediate gradient evaluations entirely.
3. Structural and Classical Shortcuts
Other methods look to avoid iterative hardware optimization altogether. H. Eric Tseng et al. utilize Lie group theory to perform "one-shot" transfer learning, calculating optimal parameter updates analytically for new datasets rather than running iterative loops.
On the simulation front, frameworks like TensorCircuit, developed by Jonathan Allcock et al., leverage classical tensor network contraction backends (such as JAX or PyTorch) to enable exact automatic differentiation during the algorithm design phase. Similarly, Sachin Kasture et al. identify specific classes of generative circuits that can be efficiently described and pre-trained classically, shielding the optimization process from physical hardware constraints until the final deployment stage.
Key Foundational Work
Partial Compilation of Variational Algorithms for Noisy Intermediate-Scale Quantum Machines (2019) — contributed 2 concept elements to this direction.
Optimizing quantum optimization algorithms via faster quantum gradient computation. (2019) — contributed 1 concept elements to this direction.
Barren plateaus in quantum neural network training landscapes (2018) — contributed 1 concept elements to this direction.