Compositional Quantum Heuristics for Max-Clique Detection

• URL: http://arxiv.org/abs/2605.07611v1
• Date: Fri, 08 May 2026 11:38:57 GMT
• Title: Compositional Quantum Heuristics for Max-Clique Detection
• Abstract summary: In general, circuits that are sufficiently expressive to model complex behaviour often exhibit barren plateaus.<n>In this work we investigate a compositional approach to mitigate this trade-off by assembling larger quantum models from smaller subcomponents.<n>We use this framework to design permutation-equivariant quantum graph neural networks for identifying maximal cliques in graphs.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum machine learning holds the promise of combining the success of classical machine learning methods with the power of quantum computing, however one of the largest obstacles facing the field is the problem of barren plateaus. Parameterised quantum circuits offer a flexible framework for developing quantum machine learning models, but their practicality is constrained by a trade-off between trainability and classical simulability. In general, circuits that are sufficiently expressive to model complex behaviour often exhibit barren plateaus, where gradients vanish and optimisation fails. In this work we investigate a compositional approach to mitigate this trade-off by assembling larger quantum models from smaller subcomponents. To ensure trainability of these subcomponents, we describe a framework for constructing group-invariant loss functions, which introduce symmetry-induced inductive bias and lead to improved gradient behaviour and generalisation. In particular, we use this framework to design permutation-equivariant quantum graph neural networks for identifying maximal cliques in graphs. The models we construct exhibit superior training gradients through symmetry-induced bias, and our experiments demonstrate that the trained models generalise to larger, more complex problem instances. Finally, inspired by Quantum-Informed Recursive Optimisation Algorithms (arXiv:2308.13607), we implement a recursive hybrid quantum-classical heuristic using the learned quantum models to guide a classical search procedure, demonstrating improved inference accuracy and scalability. Together, these results suggest that compositional circuits could be a viable pathway towards scalable quantum learning models that remain challenging to reproduce classically.

Related papers

• Learnable yet not simulable: a quantum resource theory of learning models [57.695822250391906]
  It remains unclear which quantum resource governs the classical learnability of quantum circuits.<n>We study the expectation-value functions of families of tunable quantum circuits.<n>These results establish a quantitative resource-theoretic framework for delineating the boundary between classical simulation and learning.
  arXiv  Detail & Related papers  (2026-08-03T14:48:03Z)
• Beyond the Expressivity-Trainability Paradox: A Dynamical Lie Algebra Perspective on Navigating Barren Plateaus in Quantum Machine Learning [0.0]
  In Quantum Machine Learning (QML), increasing model capacity typically risks overfitting.<n>This study advances a counter-intuitive paradigm, driven by the "expressivity-trainability paradox"<n>We establish a comprehensive framework linking the algebraic dimension of circuit generators to their optimization dynamics.
  arXiv  Detail & Related papers  (2026-06-30T11:50:52Z)
• Trainable Quantum Channels as Computational Primitives for Quantum Learning [2.047424180164312]
  Variational quantum learning is traditionally constrained to unitary dynamics.<n>We establish a non-unitary quantum machine learning framework grounded in open-system dynamics.
  arXiv  Detail & Related papers  (2026-06-14T13:19:49Z)
• Efficient Quantum Algorithms for Higher-Order Coupled Oscillators [0.788073088949581]
  We develop quantum algorithms for two central tasks -- synchronization estimation and certification of the no-phase-locking regime -- in the simplicial Kuramoto model.<n>More broadly, these results extend quantum algorithms for higher-order networks from structural analysis to nonlinear diagnostics, easing a major computational bottleneck.
  arXiv  Detail & Related papers  (2026-04-22T02:12:43Z)
• Generative modeling with Gaussian Boson Sampling: classically trainable Bosonic Born Machines [0.1449880056570423]
  We introduce a photonic quantum generative model built on parametrized Gaussian Boson Sampling circuits.<n>The training is based on the efficient classical evaluation of expectation values enabled by the Gaussian structure of the state.<n>We demonstrate the effectiveness of the approach through numerical experiments on photonic systems with up to 805 modes and over a million trainable parameters.
  arXiv  Detail & Related papers  (2026-03-11T18:04:11Z)
• Quantum LEGO Learning: A Modular Design Principle for Hybrid Artificial Intelligence [63.39968536637762]
  We introduce Quantum LEGO Learning, a learning framework that treats classical and quantum components as reusable, composable learning blocks.<n>Within this framework, a pre-trained classical neural network serves as a frozen feature block, while a VQC acts as a trainable adaptive module.<n>We develop a block-wise generalization theory that decomposes learning error into approximation and estimation components.
  arXiv  Detail & Related papers  (2026-01-29T14:29:21Z)
• Superpositional Gradient Descent: Harnessing Quantum Principles for Model Training [0.0]
  Superpositional Gradient Descent (SGD) is a novel linking gradient updates with quantum superposition by injecting quantum circuit perturbations.<n>We present a mathematical framework and implement hybrid quantum-classical circuits in PyTorch and Qiskit.
  arXiv  Detail & Related papers  (2025-11-01T16:37:55Z)
• VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learning [50.95799256262098]
  Variational quantum circuits (VQCs) hold promise for quantum machine learning but face challenges in expressivity, trainability, and noise resilience.<n>We propose VQC-MLPNet, a hybrid architecture where a VQC generates the first-layer weights of a classical multilayer perceptron during training, while inference is performed entirely classically.
  arXiv  Detail & Related papers  (2025-06-12T01:38:15Z)
• Train on classical, deploy on quantum: scaling generative quantum machine learning to a thousand qubits [0.27309692684728604]
  We show that instantaneous generative models based on quantum circuits can be trained efficiently on classical hardware.<n>By combining our approach with a data-dependent parameter initialisation strategy, we do not encounter issues of barren plateaus.<n>We find that the quantum models can successfully learn from high dimensional data, and perform surprisingly well compared to simple energy-based classical generative models.
  arXiv  Detail & Related papers  (2025-03-04T19:00:02Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Efficient estimation of trainability for variational quantum circuits [43.028111013960206]
  We find an efficient method to compute the cost function and its variance for a wide class of variational quantum circuits. This method can be used to certify trainability for variational quantum circuits and explore design strategies that can overcome the barren plateau problem.
  arXiv  Detail & Related papers  (2023-02-09T14:05:18Z)
• The Quantum Path Kernel: a Generalized Quantum Neural Tangent Kernel for Deep Quantum Machine Learning [52.77024349608834]
  Building a quantum analog of classical deep neural networks represents a fundamental challenge in quantum computing. Key issue is how to address the inherent non-linearity of classical deep learning. We introduce the Quantum Path Kernel, a formulation of quantum machine learning capable of replicating those aspects of deep machine learning.
  arXiv  Detail & Related papers  (2022-12-22T16:06:24Z)
• Generalization despite overfitting in quantum machine learning models [0.0]
  We provide a characterization of benign overfitting in quantum models. We show how a class of quantum models exhibits analogous features. We intuitively explain these features according to the ability of the quantum model to interpolate noisy data with locally "spiky" behavior.
  arXiv  Detail & Related papers  (2022-09-12T18:08:45Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.