From barren plateaus through fertile valleys: Conic extensions of parameterised quantum circuits

1. Problem Statement

The paper addresses a critical bottleneck in Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA), used for combinatorial optimization on Near-Term Intermediate Scale Quantum (NISQ) devices.

• Barren Plateaus: As the depth of parameterized quantum circuits (PQCs) increases to solve complex problems, the optimization landscape often develops "barren plateaus." In these regions, the gradients of the cost function vanish exponentially with the number of qubits, rendering gradient-based classical optimizers ineffective.
• Local Minima & Geometric Constraints: Even when gradients exist, the optimization is restricted to a unitary manifold (the surface of the Bloch sphere in single-qubit terms). The optimal path to the ground state may lie "outside" this manifold (through the interior of the Hilbert space), which unitary gates cannot access directly.
• Limitations of Current Approaches: Simply increasing circuit depth to escape local minima often exacerbates the barren plateau problem, leading to a trade-off between expressibility and trainability.

2. Methodology: Quantum Conic Programming (QCP)

The authors propose a general framework called Quantum Conic Programming (QCP) to overcome these limitations by extending the variational ansatz from a unitary manifold to a variational cone.

Core Concept: Non-Unitary Extensions

Instead of restricting the search to unitary operations, the method introduces non-unitary gates constructed as Linear Combinations of Unitaries (LCU).

• The Ansatz: The state update is defined as:
  $$M_\alpha |\phi\rangle = \frac{\sum_{i=1}^\ell \alpha_i U_i |\phi\rangle}{\|\sum_{i=1}^\ell \alpha_i U_i |\phi\rangle\|}$$
  Here, $U_i$ are fixed unitary gates (derived from the preceding PQC components), and $\alpha_i$ are complex variational parameters.
• Geometric Advantage: While unitary gates traverse the boundary of the variational cone, the non-unitary operator $M_\alpha$ allows the algorithm to take steps through the interior of the cone. This enables the system to move in directions orthogonal to the tangent space of the original unitary manifold, effectively "jumping" out of barren plateaus.

Optimization Strategy

1. Hybrid Loop: The algorithm runs a standard unitary PQC (e.g., QAOA) until the gradient vanishes or stagnation is detected.
2. LCU Step: Upon stagnation, a non-unitary LCU step is applied.
3. Generalized Eigenvalue Problem (GEP): Finding the optimal parameters $\alpha$ is reduced to solving a low-dimensional Generalized Eigenvalue Problem:
   $$H\alpha = \lambda E\alpha$$
   Where:
   • $H_{ij} = \langle \phi | U_i^\dagger H U_j | \phi \rangle$ (Energy moment matrix)
   • $E_{ij} = \langle \phi | U_i^\dagger U_j | \phi \rangle$ (Overlap moment matrix)
     These matrices are efficiently estimated using Hadamard tests or similar protocols.
4. Implementation: The LCU step is implemented via a non-deterministic channel using an ancilla register and mid-circuit measurements. Success is determined by post-selecting on a specific measurement outcome.

3. Key Contributions

• Variational Cone Framework: The paper introduces a systematic method to extend PQC ansatzes into a "variational cone," allowing optimization beyond the constraints of unitary evolution.
• LCU-Assisted Optimization: It demonstrates that non-unitary operations, implemented via LCU, can be integrated into standard VQA workflows (like QAOA) to escape barren plateaus and local minima.
• Reduction to GEP: The complex optimization of non-unitary parameters is reduced to a low-dimensional Generalized Eigenvalue Problem, which is computationally cheap for classical solvers and robust against shot noise.
• Proof of Concept: The method is successfully integrated into QAOA, showing that it can outperform state-of-the-art classical solvers (like Goemans-Williamson) on specific instances where standard QAOA fails.

4. Results

The authors validated their approach through extensive noise-free simulations on the MAXCUT problem (3-regular graphs) with qubit counts ranging from 4 to 22.

• Overcoming Stagnation:
  • Standard QAOA (without LCU) stagnated after ~10 iterations with an approximation ratio of 0.785, failing to reach the Goemans-Williamson (GW) bound of 0.878.
  • A single LCU step immediately boosted the ratio to 0.842.
  • Three sequential LCU steps (interspersed with QAOA layers) pushed the approximation ratio to 0.904, significantly surpassing the GW bound.
• Scalability:
  • For larger instances (14+ qubits), standard QAOA consistently failed to exceed the GW bound.
  • QAOA with two or three LCU steps maintained approximation ratios well above the GW bound across all tested sizes.
• Success Probability:
  • The LCU method is non-deterministic. The probability of success decreases with each step (e.g., ~36.5% for one step, ~14.1% for three consecutive steps).
  • However, the authors note that success probabilities did not degrade with increasing problem size in the tested regime (up to 22 qubits), remaining above 10% even for the largest instances.
• Solution Quality: Histograms of the output states showed that while standard QAOA produced states with minimal overlap with optimal solutions, the LCU-assisted version concentrated probability mass sharply on high-quality solutions (approximation ratio > 0.9).

5. Significance and Future Outlook

• Breaking the Barren Plateau: This work provides a concrete, NISQ-compatible mechanism to bypass the vanishing gradient problem, which has been a major theoretical and practical hurdle for deep quantum circuits.
• Beyond Unitary Limits: It challenges the paradigm that VQAs must be strictly unitary, showing that non-unitary extensions can access "fertile valleys" in the optimization landscape that unitary paths cannot reach.
• Practical Impact: The ability to surpass classical benchmarks (GW bound) on MAXCUT using a hybrid quantum-classical approach with non-unitary steps suggests a viable path toward quantum advantage in combinatorial optimization.
• Open Challenges: The primary limitation remains the success probability of the non-deterministic LCU channel. Future work aims to improve this probability (potentially via iterative versions) and test the method on actual noisy hardware to assess robustness against decoherence.

In summary, the paper proposes a paradigm shift from "deeper unitary circuits" to "conic extensions via non-unitary steps," offering a robust solution to the barren plateau problem and demonstrating superior performance on optimization benchmarks.