Discovery of connectivity-trainability trade-off of IQP Circuits for Hamiltonian Optimization

The gist: The results reveal a clear trade-off between expressivity and trainability, demonstrating that circuit connectivity plays a key role in determining the ability of IQP circuits to reach low-energy states.

Introduction and Motivation

Combinatorial optimization problems arise in a broad range of scientific and engineering applications, including scheduling, portfolio optimization, logistics, machine learning, and computational physics <ref:2606.24264#pg2>. Many of these problems are NP-hard and can be reformulated as the task of finding the ground state of a suitably defined Hamiltonian [1]. Such Hamiltonian optimization problems establish a natural connection between discrete optimization and quantum computing, motivating the development of quantum algorithms capable of preparing lowenergy states efficiently <ref:2606.24264#pg2>. The performance of variational quantum algorithms depends critically on the choice of ansatz <ref:2606.24264#pg2>. Existing approaches, including hardware-efficient circuits [5], the quantum approximate optimization algorithm (QAOA) [6], and Hamiltonian variational ansatze [7]–[8], have demonstrated encouraging results for quantum chemistry and combinatorial optimization <ref:2606.24264#pg2>. However, designing an ansatz that simultaneously provides sufficient expressivity and favorable trainability remains a central challenge <ref:2606.24264#pg2>.

IQP Circuit Architecture

Instantaneous Quantum Polynomial-time (IQP) circuits consist entirely of commuting gates and have attracted considerable attention due to the conjectured classical hardness of their sampling problem [10]–[13] <ref:2606.24264#pg2>. IQP circuits possess a diagonal structure that naturally generates Pauli-Z correlations and can be implemented with shallow circuit depth and a high degree of parallelism <ref:2606.24264#pg2>. The paper considers three representative circuit architectures with increasing connectivity: single-Z circuits, circular connectivity, and fully connected IQP circuits <ref:2606.24264#pg2>. These architectures represent increasing levels of connectivity and expressivity, ranging from independent single-qubit rotations to local nearest-neighbor interactions and finally to all-to-all pairwise couplings <ref:2606.24264#pg2>.

Trade-off Analysis: Expressivity vs. Trainability

The study reveals a clear trade-off between expressivity and trainability <ref:2606.24264#pg2>. Fully connected IQP circuits exhibit high expressivity and nearly volume-law entanglement, allowing them to achieve superior optimization performance, but they also experience rapidly decaying gradient variance and are therefore more susceptible to barren plateaus <ref:2606.24264#pg2>. In contrast, single-Z circuits maintain favorable gradients but remain under-expressive and consequently perform poorly on complex optimization tasks <ref:2606.24264#pg2>. Circular connectivity occupies an intermediate regime, balancing expressivity and trainability and providing robust performance across different Hamiltonians <ref:2606.24264#pg2>.

Key Findings on Circuit Architectures

The comparison of the three architectures shows that fully connected circuits generally achieve the smallest relative approximation ratios, indicating their superior ability to approximate the ground-state energy <ref:2606.24264#pg2>. Circular architectures provide intermediate performance, whereas single-Z circuits consistently exhibit larger optimization errors <ref:2606.24264#pg2>. This trend becomes more pronounced for the Number Partition Hamiltonian, whose dense interaction structure requires the circuit to capture long-range correlations among qubits <ref:2606.24264#pg2>.

Gradient Variance and Barren Plateaus

The trainability of the different IQP architectures is investigated in Fig. 3 through the scaling behavior of the gradient variance <ref:2606.24264#pg2>. In contrast to the optimization results, fully connected circuits exhibit the fastest decay of gradient variance as the number of qubits increases, indicating a stronger tendency toward barren plateaus <ref:2606.24264#pg2>. Circular connectivity maintains significantly larger gradients, while single-Z circuits exhibit the slowest decay and therefore the most favorable optimization landscape <ref:2606.24264#pg2>. This behavior is consistent across all Hamiltonians and initialization strategies, suggesting that the tendency toward barren plateaus is primarily determined by the circuit architecture rather than the specific problem instance <ref:2606.24264#pg2>.

Expressibility and Entanglement

Both results show that increasing circuit connectivity generally enhances both state-space expressibility and entanglement generation <ref:2606.24264#pg2>. As shown in Fig. 4a, the Jensen-Shannon distance between the output fidelity distribution and the Haar distribution decreases as the connectivity increases, indicating that fully connected circuits are substantially more expressive than circular and single-Z structures <ref:2606.24264#pg2>. Fig. 4b further shows that the entanglement entropy follows a similar trend, with fully connected circuits exhibiting nearly volume-law scaling, circular architectures displaying intermediate entanglement growth, and single-Z circuits generating only weak correlations <ref:2606.24264#pg2>.

Conclusion and Design Principles

The results indicate that neither maximum expressivity nor maximum trainability alone is sufficient for effective Hamiltonian optimization <ref:2606.24264#pg2>. Successful IQP-based optimization requires an appropriate balance between the two, highlighting circuit connectivity as a key design parameter for variational quantum algorithms <ref:2606.24264#pg2>. The paper suggests that effective variational ansatz design should seek a compromise between representational capability and optimization landscape rather than maximizing either property independently <ref:2606.24264#pg2>.

Future Work

One promising avenue is the investigation of adaptive or problem-informed connectivity structures, in which the architecture of the IQP circuit is designed to reflect the interaction graph of the target Hamiltonian <ref:2606.24264#pg2>. Another interesting direction is the incorporation of higher-order Pauli terms, allowing IQP circuits to capture many-body correlations that cannot be represented by pairwise interactions alone <ref:2606.24264#pg2>. Layered or repeated IQP architectures may also provide a means of enhancing expressivity without resorting to complete connectivity <ref:2606.24264#pg2>. Future work should also investigate advanced strategies for mitigating barren plateaus, such as data-driven initialization methods, layerwise training, parameter concentration techniques, and local cost functions <ref:2606.24264#pg2>.

Applications

Beyond Hamiltonian optimization, IQP circuits possess potential applications in several areas <ref:2606.24264#pg2>. Their ability to generate highly correlated quantum states makes them attractive for quantum generative modeling, including quantum circuit Born machines and hybrid quantum-classical machine learning <ref:2606.24264#pg2>. In combinatorial optimization, IQP circuits may provide efficient variational ansatze for problems such as graph coloring, traveling salesman, vehicle routing, and portfolio optimization through appropriate QUBO encodings <ref:2606.24264#pg2>. Their expressive yet shallow structure also makes them promising candidates for quantum optimal control, quantum state preparation, and benchmarking protocols for near-term quantum devices <ref:2606.24264#pg2>.

Data Availability

The code and data supporting the findings of this study are openly available at: https://github.com/ChuongQuoc1413017/IQP Optimization <ref:2606.24264#pg2>. The authors would like to thank Roland Farrell, Marlene Funck, and Carla Rieger for helpful discussions <ref:2606.24264#pg2>.

References

[1] A. Lucas, “Ising formulations of many np problems,” Frontiers in Physics, vol. Volume 2 - 2014, 2014 <ref:2606.24264#pg2>. [Online]. Available: https://www.frontiersin.org/journals/physics/articles/10.3389/fphy.2014.00005

[2] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou et al., “A variational eigenvalue solver on a photonic quantum processor,” Nature Communications, vol. 5, no. 1, p. 4213 <ref:2606.24264#pg2>. [Online]. Available: https://doi.org/10.1038/ncomms5213

[3] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, “Cost function dependent barren plateaus in shallow parametrized quantum circuits,” Nature Communications, vol. 12, no. 1, p. 1791 <ref:2606.24264#pg2>. [Online]. Available: https://doi.org/10.1038/s41467-021-21728-w

[4] Q. C. Nguyen, L. B. Ho, L. Nguyen Tran, and H. Q.

1. Adaptive Ansatz Design: AI systems can dynamically adjust their IQP circuit connectivity based on the target Hamiltonian's interaction graph to balance expressivity and trainability, potentially avoiding barren plateaus while maintaining low approximation errors.

2. Gradient Variance Monitoring: The AI system can actively monitor the scaling behavior of gradient variance during training; if it detects a rapid decay consistent with fully connected circuits, it can trigger adaptive parameter initialization or regularization techniques to stabilize the optimization landscape.

3. Optimized Initialization Strategies: Instead of relying on fixed Gaussian or uniform sampling, the AI system can employ data-driven initialization methods that dynamically select parameter starting points based on preliminary exploration of the cost function landscape to maximize initial gradient variance.

4. Hybrid Ansatz Integration: AI systems can integrate IQP circuits with classical neural networks, using the IQP component for generating highly correlated states and a classical component to refine the optimization process, leveraging both representational power and training stability.

Instantaneous Quantum Polynomial-time (IQP) circuits are promising candidates for near-term quantum advantage due to the conjectured classical hardness of their sampling task. However, their capabilities for optimization remain largely unexplored. We present a systematic investigation of the performance and trainability of IQP circuits for Hamiltonian optimization. Our results reveal a trade-off between optimization performance and circuit connectivity, demonstrating that the circuit structure plays a key role in determining the ability of IQP circuits to reach low-energy states.