Probabilistic modeling over permutations using quantum computers

• URL: http://arxiv.org/abs/2603.22401v1
• Date: Mon, 23 Mar 2026 18:00:12 GMT
• Title: Probabilistic modeling over permutations using quantum computers
• Abstract summary: We develop a quantum algorithm that encodes the exact probabilistic model into the amplitudes of a quantum state.<n>We envision the scaling, limitations, and practical use of such an approach, which we envision to be a first step towards useful applications of non-Abelian QFTs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum computers provide a super-exponential speedup for performing a Fourier transform over the symmetric group, an ability for which practical use cases have remained elusive so far. In this work, we leverage this ability to unlock spectral methods for machine learning over permutation-structured data, which appear in applications such as multi-object tracking and recommendation systems. It has been shown previously that a powerful way of building probabilistic models over permutations is to use the framework of non-Abelian harmonic analysis, as the model's group Fourier spectrum captures the interaction complexity: "low frequencies" correspond to low order correlations, and "high frequencies" to more complex ones. This can be used to construct a Markov chain model driven by alternating steps of diffusion (a group-equivariant convolution) and conditioning (a Bayesian update). However, this approach is computationally challenging and hence limited to simple approximations. Here we construct a quantum algorithm that encodes the exact probabilistic model -- a classically intractable object -- into the amplitudes of a quantum state by making use of the Quantum Fourier Transform (QFT) over the symmetric group. We discuss the scaling, limitations, and practical use of such an approach, which we envision to be a first step towards useful applications of non-Abelian QFTs.

Related papers

• A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features [0.9558392439655014]
  We develop a classical algorithm to address this type of quantum-advantage candidate.<n>Applying this method dequantizes the sampler for optimized random features, giving a classical sampler with prescribed accuracy and runtime.
  arXiv  Detail & Related papers  (2026-09-09T18:23:55Z)
• Beyond Gates: Pulse Level Quantum Fourier Models [1.0482211230201115]
  We evaluate quantum Fourier models (QFMs) through the lens of pulse parameters.<n>We show that control over pulse shapes does not significantly alter the global expressibility or structural correlations of the Ansatz.<n>For composite gates, independent pulse scalings replace a single logical angle by multiple independently tunable sub-angles.
  arXiv  Detail & Related papers  (2026-05-06T14:13:44Z)
• Quantum Random Features: A Spectral Framework for Quantum Machine Learning [0.0]
  We introduce textitQuantum Random Features (QRF) and textitQuantum Dynamical Random Features (QDRF)<n>QRF and QDRF generate high-dimensional spectral representations without variational optimization.<n>By linking spectral theory with experimentally feasible quantum dynamics, this work provides a compact and hardware-compatible route to scalable quantum learning.
  arXiv  Detail & Related papers  (2026-01-29T14:01:52Z)
• Quantum Random Feature Method for Solving Partial Differential Equations [36.58357595906332]
  Quantum computing holds promise for scientific computing due to its potential for exponential speedups over classical methods.<n>In this work, we introduce a quantum random method (QRFM) that leverages advantages from both numerical analysis and neural analysis.
  arXiv  Detail & Related papers  (2025-10-09T08:42:09Z)
• Quantum-assisted Gaussian process regression using random Fourier features [8.271361104403802]
  We introduce a quantum-assisted algorithm for Gaussian process regression based on the random Fourier feature kernel approximation.<n>We achieve a sparse-order computational speedup relative to the classical method.
  arXiv  Detail & Related papers  (2025-07-30T12:49:53Z)
• QML Essentials -- A framework for working with Quantum Fourier Models [2.5914756674389463]
  This framework is based on the PennyLane simulator and facilitates the evaluation and training of Variational Quantum Circuits.<n>It provides two methods for calculating the corresponding spectrum via the Fast Fourier Transform and another analytical method based on the expansion of the expectation value using trigonometrics.
  arXiv  Detail & Related papers  (2025-06-07T07:22:43Z)
• Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
  We propose quantum algorithms for linear differential equations.<n>The gate complexity of our algorithms exhibits an $mathcalO(dlog(Nd))$ dependence on the dimensions.<n>The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, Brownian motions, and one-dimensional L'evy flights.
  arXiv  Detail & Related papers  (2024-12-19T14:04:11Z)
• Approximately Equivariant Quantum Neural Network for $p4m$ Group Symmetries in Images [30.01160824817612]
  This work proposes equivariant Quantum Convolutional Neural Networks (EquivQCNNs) for image classification under planar $p4m$ symmetry. We present the results tested in different use cases, such as phase detection of the 2D Ising model and classification of the extended MNIST dataset.
  arXiv  Detail & Related papers  (2023-10-03T18:01:02Z)
• Variational Quantum Approximated Spectral Clustering [0.6718184400443239]
  We propose Variational Quantum Approximated Spectral Clustering (VQASC), which extends quantum distance-based classifier models to the clustering framework.<n>Our approach uses efficient quantum circuit designs whose depth scales sub-quadratically with dataset size, enabling the computation of weighted sums over various matrix representations of an undirected graph.
  arXiv  Detail & Related papers  (2023-09-08T17:54:42Z)
• Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms [0.39886149789339326]
  We show how many techniques from randomized linear algebra can be adapted to work under this weaker assumption.<n>We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms.
  arXiv  Detail & Related papers  (2023-04-11T02:09:13Z)
• Protocols for Trainable and Differentiable Quantum Generative Modelling [21.24186888129542]
  We propose an approach for learning probability distributions as differentiable quantum circuits (DQC) We perform training of a DQC-based model, where data is encoded in a latent space with a phase feature map, followed by a variational quantum circuit. This allows fast sampling from parametrized distributions using a single-shot readout.
  arXiv  Detail & Related papers  (2022-02-16T18:55:48Z)
• 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)
• Quantum Markov Chain Monte Carlo with Digital Dissipative Dynamics on Quantum Computers [52.77024349608834]
  We develop a digital quantum algorithm that simulates interaction with an environment using a small number of ancilla qubits. We evaluate the algorithm by simulating thermal states of the transverse Ising model.
  arXiv  Detail & Related papers  (2021-03-04T18:21:00Z)

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.