⚛️ quantum physics

Probabilistic modeling over permutations using quantum computers

This paper proposes a quantum algorithm that leverages the super-exponential speedup of the Quantum Fourier Transform over the symmetric group to encode exact probabilistic models for permutation-structured data, thereby enabling spectral machine learning methods that are computationally intractable for classical computers.

Original authors: Vasilis Belis, Giulio Crognaletti, Matteo Argenton, Michele Grossi, Maria Schuld

Published 2026-03-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Vasilis Belis, Giulio Crognaletti, Matteo Argenton, Michele Grossi, Maria Schuld

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive jigsaw puzzle, but instead of 1,000 pieces, you have a puzzle with $n!$ (n factorial) pieces. If you have just 10 objects, there are 3.6 million ways to arrange them. If you have 20 objects, the number of arrangements is larger than the number of atoms in the universe.

This is the problem of permutations. It shows up everywhere:

Delivery trucks: Figuring out the best order to visit 50 houses.
Recommendation engines: Guessing which 10 movies you'll like out of thousands.
DNA sequencing: Reassembling a genome from tiny, shuffled fragments.

For a long time, computers have struggled with this. They try to look at every possible arrangement one by one, which takes forever. Or, they try to simplify the problem by ignoring the "complex" parts, which leads to bad guesses.

This paper proposes a way to use Quantum Computers to solve this not by looking at every piece, but by looking at the music of the puzzle.

The Core Idea: Listening to the "Music" of Arrangements

The authors use a mathematical concept called Harmonic Analysis. Think of a complex sound (like a symphony) not as a single noise, but as a mix of different musical notes (frequencies).

Low notes (Low Frequencies): These represent simple patterns. "Object A is usually first."
High notes (High Frequencies): These represent complex, intricate patterns. "If Object A is first, then B must be third, but only if C is last."

In classical computing, trying to hear all these notes at once is impossible because the "orchestra" (the math) is too big. You have to mute the high notes (simplify the problem) to make it manageable.

The Quantum Advantage:
Quantum computers have a special superpower called the Quantum Fourier Transform (QFT). It's like a magical tuning fork that can instantly hear every note in the symphony, from the deepest bass to the highest whistle, all at once. While a classical computer takes longer than the age of the universe to do this for large puzzles, a quantum computer could do it in seconds.

How the Quantum Algorithm Works: The "Belief" Dance

The paper describes a process that looks like a dance between two steps: Diffusion and Conditioning. Imagine you are trying to guess the secret order of a deck of cards.

Step 1: Diffusion (Spreading the Uncertainty)

Imagine you have a belief about the order of the cards. Maybe you think the Ace is on top.

The Action: You shake the deck slightly. This is Diffusion. It spreads your belief out. You become less sure. The Ace might be on top, or maybe second, or third.
The Quantum Trick: On a classical computer, spreading this uncertainty requires recalculating millions of possibilities. On a quantum computer, this is like a wave spreading out smoothly. The math says this step is easy to do in the "frequency" (music) domain.

Step 2: Conditioning (The Reality Check)

Now, you peek at the top card. It's the King!

The Action: This is Conditioning. You update your belief. "Okay, the Ace isn't on top. The King is." You throw away all the possibilities where the Ace was on top.
The Quantum Trick: This step is easy to do in the "direct" domain (looking at the actual cards).

The Magic Loop

The problem is that Diffusion is easy in "Music Mode," but Conditioning is easy in "Card Mode."

Classical computers get stuck switching between these two modes. The switch is so slow and expensive that they have to give up on the complex details.
The Quantum Computer has a super-fast elevator (the QFT) that instantly shuttles between "Music Mode" and "Card Mode." It can diffuse, switch, condition, switch, and diffuse again, keeping all the complex details intact without getting tired.

The Result: A "Super-Guesser"

By repeating this dance, the quantum computer builds a Probabilistic Model.

Instead of just giving you one answer (e.g., "The order is A-B-C"), it gives you a cloud of possibilities.
It tells you: "There is a 90% chance the order is A-B-C, a 5% chance it's A-C-B, and a tiny chance it's something else."

Because the quantum computer didn't have to cut out the "high notes" (the complex patterns), this cloud of possibilities is much more accurate than what classical computers can produce.

Why This Matters (The "So What?")

Better Recommendations: Netflix or Spotify could understand your taste not just as "I like rock," but as complex, subtle patterns like "I like rock songs with a specific drum beat that only play when it's raining."
Smarter Logistics: Delivery drones could find the perfect route for 100 stops, saving massive amounts of fuel and time, by understanding complex traffic patterns that current software misses.
New Physics: It opens the door to solving problems involving symmetry and order that were previously considered impossible.

The Catch (Reality Check)

The authors are honest: This is a blueprint, not a finished product.

Hardware: We don't have quantum computers big enough yet to hold the "deck of cards" for 20 or 30 items.
Noise: Current quantum computers are noisy; a little static can ruin the "music."
Next Steps: They need to prove this works on real-world data and build the specific circuits to make it happen.

In a Nutshell

This paper is like discovering a new instrument that can play a symphony of possibilities instead of just a single note. It suggests that by using quantum computers to listen to the "music" of arrangements, we can solve some of the most complex ordering puzzles in the world, unlocking a new level of intelligence for AI and logistics. It's the first step toward a future where computers don't just guess the answer, but understand the shape of the problem.

1. Problem Statement

Probabilistic modeling over permutations (the symmetric group $S_n$ ) is a fundamental challenge in machine learning applications such as multi-object tracking, recommendation systems, and preference learning.

Classical Bottleneck: The space of permutations grows factorially ( $n!$ ). Classical approaches using non-Abelian harmonic analysis (Group Fourier Transform) rely on the "Fourier spectrum" to capture correlations. Low frequencies correspond to simple marginals, while high frequencies capture complex multi-body dependencies.
Limitations:
- Band-limiting: To make computation tractable, classical methods must truncate the spectrum to low frequencies, losing high-order correlation information.
- Computational Complexity: Exact inference requires alternating between the direct space (permutations) and Fourier space. The classical Fast Fourier Transform (FFT) over $S_n$ scales super-exponentially as $O(n! n^2)$ , making exact modeling intractable for even moderate $n$ .
- Inference Difficulty: Computing the posterior distribution or finding the Maximum A Posteriori (MAP) estimate is computationally prohibitive without approximations.

2. Methodology

The authors propose a quantum algorithm that encodes the exact probabilistic model into the amplitudes of a quantum state, leveraging the Quantum Fourier Transform (QFT) over the symmetric group to bypass classical bottlenecks.

A. Core Framework: Markov Chain on $S_n$

The model evolves a belief state $h^{(t)}(\sigma)$ over permutations through alternating steps:

Diffusion: Models uncertainty growth between observations. Implemented as a group-equivariant convolution (random walk on the Cayley graph of $S_n$ $S_{n}$ generated by transpositions).
- Quantum Advantage: In Fourier space, convolution becomes a point-wise matrix multiplication.
Conditioning: Updates the belief state via Bayes' rule upon receiving new data (e.g., a sensor reading or user preference).
- Quantum Advantage: In direct space, conditioning is a simple point-wise product (likelihood $\times$ prior).

B. Quantum Implementation

The algorithm utilizes $O(n \log n)$ qubits to encode permutations using Lehmer codes (mapping permutations to integers). The process involves:

State Encoding: The probability distribution is encoded in the amplitudes of a quantum state $|\psi\rangle = \sum \sqrt{h(\sigma)} |\sigma\rangle$ (Born encoding) or $|\psi\rangle = \sum h(\sigma) |\sigma\rangle$ (Amplitude encoding).
QFT Swapping: The algorithm efficiently toggles between direct space and Fourier space using the QFT over $S_n$ , which has a runtime of $O(n^3 \log n)$ , offering a super-exponential speedup over the classical $O(n! n^2)$ .
Block-Encoding:
- Diffusion: Implemented in Fourier space. Since the diffusion kernel is a class function, its Fourier transform is block-diagonal (scalar multiples of identity). The algorithm uses block-encoding to apply these scalars to the state amplitudes.
- Conditioning: Implemented in direct space. The algorithm uses a "reorder-update" strategy to map specific observation constraints (e.g., "Object A is in position 3") to the beginning or end of the Lehmer code string, allowing efficient computation of the likelihood function $\phi(\sigma)$ without full decoding.
Amplitude Amplification: Since diffusion and conditioning are non-unitary operations implemented via ancilla qubits, Amplitude Amplification (or Fixed-Point Amplitude Amplification) is used at the end of the sequence to boost the probability of the correct state, ensuring the final state encodes the posterior distribution.

3. Key Contributions

Exact Quantum Probabilistic Modeling: The first algorithm to encode an exact probabilistic model over permutations (without band-limiting approximations) into a quantum state.
Efficient QFT Utilization: Demonstrates a practical application for the QFT over the symmetric group, a tool previously considered theoretically interesting but lacking practical use cases.
Scalability Analysis:
- Proves that the success probability of the diffusion step is lower-bounded by a constant (for "lazy" walks) or an inverse polynomial in $n$ (for general walks), ensuring the algorithm remains efficient.
- Shows that the total runtime is dominated by the QFT ( $O(n^3 \log n)$ ), provided the number of Markov chain steps $T$ scales logarithmically with $n$ .
Flexible Encoding Strategies:
- Amplitude Encoding: Produces samples from $|h(\sigma)|^2$ , sharpening the distribution (useful for finding modes).
- Born Encoding: Produces samples from $h(\sigma)$ directly, treating the diffusion as a non-Markovian evolution of amplitudes (analogous to imaginary time evolution).
Downstream Applications: Outlines methods for using the resulting state for generative modeling (sampling new permutations) and MAP estimation (finding the most likely permutation) using Quantum Singular Value Transformation (QSVT) to amplify high-probability peaks.

4. Results and Theoretical Findings

Complexity: The algorithm achieves a runtime dominated by $O(n^3 \log n)$ , a super-exponential improvement over classical exact methods.
Success Probability: The authors derive lower bounds for the success probability of the block-encoding steps.
- For a lazy random walk ( $p > 1/2$ ), success probability is bounded by a constant independent of $n$ .
- For general rational walks, it is bounded by $O(n^{-4})$ , which is sufficient for polynomial amplification.
Feasibility: The paper identifies a "sweet spot" for near-term fault-tolerant quantum computers, estimating that useful applications could arise for $n \approx 15$ to $30$. In this range, the number of partitions (irreps) is manageable for classical pre-computation of diffusion coefficients, yet the problem size is classically intractable for exact FFT.

5. Significance

Unlocking Spectral Methods: This work bridges the gap between abstract non-Abelian harmonic analysis and practical machine learning. It validates the hypothesis that quantum computers can unlock the full power of spectral methods for group-structured data.
Beyond Hidden Subgroup Problems: While early quantum algorithms focused on Abelian Hidden Subgroup Problems (e.g., Shor's algorithm), this work demonstrates the utility of non-Abelian QFTs for statistical inference and generative modeling, moving beyond graph isomorphism (which was shown to be difficult for QFTs).
New Paradigm for Inference: It proposes a shift from "computing marginals" (the classical approach) to "sampling from the posterior" (the quantum approach), offering a new pathway for solving combinatorial optimization problems like the Quadratic Assignment Problem or complex ranking tasks.
Foundation for Future Work: The paper serves as a "feasibility study," establishing the theoretical groundwork for future numerical experiments and the development of hardware-efficient implementations of non-Abelian QFTs.

In summary, Belis et al. present a rigorous quantum algorithm that overcomes the classical limitations of modeling permutations by utilizing the QFT over $S_n$ to perform exact spectral inference, offering a potential super-exponential speedup for critical machine learning tasks involving ordering and tracking.