Instantaneous Quantum Polynomial-time (IQP) circuits are promising candidates for near-term quantum computing due to the conjectured classical hardness of their sampling task and their shallow, highly parallelizable structure. Despite extensive studies of their complexity-theoretic properties, the role of circuit connectivity in their trainability as variational ansatze remains poorly understood. In this work, we present an investigation of IQP circuits for Hamiltonian optimization that traces a mechanistic chain linking circuit connectivity, entanglement generation, and gradient scaling: increasing connectivity drives the circuit output toward Haar-like statistics and volume-law entanglement, and this increase in entanglement is consistently associated with an exponential decay of the gradient variance and degraded optimization performance, while sparser architectures retain stable gradients at the cost of global expressibility and entanglement capacity. This connectivity-entanglement-gradient mechanism produces a nontrivial connectivity-trainability trade-off, demonstrating that effective IQP-based Hamiltonian optimization requires a balance between global expressibility and trainability rather than maximal expressivity alone. In particular, on our benchmarks, a circuit generating no entanglement already matches the optimization performance of more highly connected circuits, and a circular topology retains entanglement capacity while preserving trainability, making it a broadly effective choice among the architectures considered.
Journal reference
Physica Scripta (2026) Physica Scripta Physica Scripta
Instantaneous Quantum Polynomial-time (IQP) circuits are promising candidates for near-term quantum computing due to the conjectured classical hardness of their sampling task and their shallow, highly parallelizable structure. Despite extensive studies of their complexity-theoretic properties, the role of circuit connectivity in their trainability as variational ansatze remains poorly understood. In this work, we present an investigation of IQP circuits for Hamiltonian optimization that traces a mechanistic chain linking circuit connectivity, entanglement generation, and gradient scaling: increasing connectivity drives the circuit output toward Haar-like statistics and volume-law entanglement, and this increase in entanglement is consistently associated with an exponential decay of the gradient variance and degraded optimization performance, while sparser architectures retain stable gradients at the cost of global expressibility and entanglement capacity. This connectivity-entanglement-gradient mechanism produces a nontrivial connectivity-trainability trade-off, demonstrating that effective IQP-based Hamiltonian optimization requires a balance between global expressibility and trainability rather than maximal expressivity alone. In particular, on our benchmarks, a circuit generating no entanglement already matches the optimization performance of more highly connected circuits, and a circular topology retains entanglement capacity while preserving trainability, making it a broadly effective choice among the architectures considered.
Instantaneous quantum polynomial quantum circuit Born machines (IQP-QCBMs) have been proposed as quantum generative models with a classically tractable training objective based on the maximum mean discrepancy (MMD) and a potential quantum advantage motivated by sampling-complexity arguments, making them an exciting model worth deeper investigation. While recent works have further proven the universality of a (slightly generalized) model, the next immediate question pertains to its trainability, i.e., whether it suffers from the exponentially vanishing loss gradients, known as the barren plateau issue, preventing effective use, and how regimes of trainability overlap with regimes of possible quantum advantage. Here, we provide significant strides in these directions. To study the trainability at initialization, we analytically derive closed-form expressions for the variances of the partial derivatives of the MMD loss function and provide general upper and lower bounds. With uniform initialization, we show that barren plateaus depend on the generator set and the spectrum of the chosen kernel. We identify regimes in which low-weight-biased kernels avoid exponential gradient suppression in structured topologies. Also, we prove that a small-variance Gaussian initialization ensures polynomial scaling for the gradient under mild conditions. As for the potential quantum advantage, we further argue, based on previous complexity-theoretic arguments, that sparse IQP families can output a probability distribution family that is classically intractable, and that this distribution remains trainable at initialization at least at lower-weight frequencies.
Instantaneous Quantum Polynomial-time (IQP) circuits are a candidate for demonstrating near-term quantum advantage, as their sampling task is believed to be classically hard in the ideal theoretical setting under standard complexity-theoretic assumptions. In noisy implementations, however, this hardness can disappear once circuit depth exceeds a noise-dependent critical threshold. We show that qubit connectivity is a key parameter in this transition, since sparse architectures require additional routing to implement long-range interactions, thereby increasing compiled circuit depth. To make this explicit, we present a connectivity-aware analysis of compiled IQP circuits. For a fixed abstract IQP instance, different hardware connectivity graphs yield different compiled depths and thus different effective positions relative to the noisy-IQP simulatability boundary. We quantify this architecture-dependent shift using the compiled depth overhead and the corresponding simulatability margin. We combine analytic depth estimates for sparse geometries, including the two-dimensional grid, with native-gateset-aware compilation experiments across seven hardware-grounded experimental device models derived from publicly available topologies. To compare these device models under a unified empirical framework, we approximate the effective noise level primarily through reported two-qubit gate error rates. This lets us compare how much effective noise sparse and fully connected architectures can tolerate for the same position relative to the noisy-IQP simulatability boundary. Our results show that sparse connectivity requires a lower effective noise level to sustain the same margin relative to the noisy-IQP simulatability boundary, and they provide a quantitative framework for determining when compiled IQP experiments are likely to remain outside, or instead enter, the classically simulatable regime.
Generative modeling is one of the most promising applications of quantum machine learning, yet training and deploying Quantum Generative Models (QGMs) on near-term hardware remains effectively intractable due to prohibitive gradient estimation and implementation costs. We propose a resource-efficient approach based on shallow Instantaneous Quantum Polynomial-time (IQP) circuits that circumvents these bottlenecks by leveraging efficient classical training while retaining the guarantee of sampling hardness. To validate this approach, we formalize graph generation as a hierarchy of physical correlations, allowing us to map abstract data features, such as edge density and bipartiteness, directly to the quantum observables required to learn them. We validate our protocol through demonstrations both on real hardware (from 28 to 153 qubits) and simulations (28 qubits). Results show that while global structural features exhibit significant degradation beyond 91 qubits, our models achieve high-precision reproduction of local correlations, even up to 153 qubits. These findings establish shallow IQP circuits as a robust, scalable candidate for generative tasks on current Noisy Intermediate-Scale Quantum (NISQ) devices.
Variational quantum algorithms (VQAs) are among the leading approaches for near-term quantum computing, yet their performance can degrade in barren plateau regimes characterized by vanishing gradients. A widely held intuition is that increasing circuit expressivity, often associated with random-state behavior, leads to a loss of trainability. Existing results show that sufficiently random circuits can lead to barren plateaus. Here we show that standard statistical signatures of randomness can emerge well before this regime, without degrading trainability. We demonstrate this behavior in structured variational circuits applied to the one-dimensional cluster-Ising model and a generalized toric code Hamiltonian. To characterize state complexity, we analyze Porter-Thomas statistics, entanglement-spectrum level statistics, and inverse participation ratios. Across both models, increasing circuit depth drives these diagnostics toward random-state-like or random-matrix-like behavior, while variational optimization remains effective, with no evidence of exponential gradient suppression in the regime studied. We interpret this behavior in terms of locality. Spectral correlations develop at relatively shallow depth through locally generated structure, while global state randomization and the associated concentration-of-measure effects are not yet realized. These results show that commonly used statistical diagnostics of complexity do not by themselves determine trainability. Instead, they point to a separation between different aspects of complexity in finite-depth variational circuits.
Quantum circuit Born machines based on instantaneous quantum polynomial-time (IQP) circuits are natural candidates for quantum generative modeling, both because of their probabilistic structure and because IQP sampling is provably classically hard in certain regimes. Recent proposals focus on training IQP-QCBMs using Maximum Mean Discrepancy (MMD) losses built from low-body Pauli-Z correlators, but the effect of initialization on the resulting optimization landscape remains poorly understood. In this work, we address this by first proving that the MMD loss landscape suffers from barren plateaus for random full-angle-range initializations of IQP circuits. We then establish lower bounds on the loss variance for identity and an unbiased data-agnostic initialization. We then additionally consider a data-dependent initialization that is better aligned with the target distribution and, under suitable assumptions, yields provable gradients and generally converges quicker to a good minimum (as indicated by our training of circuits with 150 qubits on genomic data). Finally, as a by-product, the developed variance lower bound framework is applicable to a general class of non-linear losses, offering a broader toolset for analyzing warm-starts in quantum machine learning.
Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, whose depth is greater than a critical O (1) threshold, the output distribution can be efficiently sampled by a classical computer. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit’s architecture, on anti-concentration properties, nor do we require Ω(log (n )) circuit depth. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought. Furthermore, we show that the critical depth threshold of our algorithm is tight, and below this threshold there are noisy IQP circuits which are hard to sample from. Thus we demonstrate that noisy IQP circuits exhibit a phase transition in the computational complexity of sampling, as circuit depth is increased.