Organizations: Xanadu Quantum Technologies, Toronto, ON, M5G 2C8, Canada∗ · Department of Physics, University of Trieste, Strada Costiera 11, 34151 Trieste, Italy · European Organization for Nuclear Research (CERN), CH-1211 Geneva, Switzerland · Istituto Nazionale di Fisica Nucleare, Sezione di Ferrara Via Saragat 1, Ferrara, Italy · Department of Physics and Earth Science, University of Ferrara, Via Saragat 1, Ferrara, 44122, Italy†
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.
Figures & tables
Figure 1: The probabilistic modeling process: The evolution of the belief state over permutations of n objects is captured by the probability distribution h(t)(σ) . Initialization ( t=0 ) begins with a deterministic assignment (canonical configuration), visualized here for n=3 as ABC→[1,2,3] . The process alternates between two operations: diffusion , which spreads probability mass (increasing entropy) to model the uncertainty in the system between steps; and conditioning , a Bayesian update that refines the distribution based on partial observations that are the training data. The process repeats for each observation in the training data.
Figure 2: Our quantum implementation : The probability distribution is encoded in the amplitudes of the quantum state ∣ψ(t)⟩∝∑σh(t)(σ)∣σ⟩ . We use Lehmer’s code to map permutations σ∈Sn to n! integers, which are then encoded to binary represented by computational basis states ∣σ⟩ . We implement diffusion in Fourier space by block-encoding an operator q^ (see Sec. III.2.1 ). The conditioning step is implemented by a block-encoding of the operator cφ in direct space that exploits Lehmer’s code. The Quantum Fourier Transform (QFT) over Sn efficiently toggles between Fourier and direct space. Each of these block-encodings requires a new ancilla. At the end, Amplitude Amplification boosts the probability that the output state encodes the full posterior probability distribution over permutations.
Figure 3: Scaling of the partitions of n and size of Sn . The number of partitions p(n) is equal to the number of irreps (and conjugacy classes) of Sn . While for big n , p(n) scales super-polynomially according to the asymptotic formula in Eq. ( 101 ), for moderate values of np(n) is significantly smaller than n! . As illustrated, it is possible to classically pre-compute all cλ ( p(n) values in total) for moderate n since we have closed formulas, allowing for an efficient block-encoding through QROM.
Figure 4: Reorder-update approach: The figure summarizes the reorder-update approach focusing on the example of partial rankings with a hard likelihood. Using the same canonical ordering of Fig. 1 , the observation A comes before C is an order k=1 ranking, comparing element i1=1 and i2=3 . Conditioning is achieved reordering the elements by mapping i1→2 , i.e. choosing π s.t. c(π)1=2 , computing φ coherently, and finally restoring the canonical ordering. If a hard likelihood is used, the qubit storing ∣φ(σ)⟩ can be directly used in the post-selection phase to implement cφ , and no additional ancillary registers are required.
School of Biomedical Engineering and Technology, Tianjin Medical University, Medical School, Tianjin University · School of Biomedical Engineering and Technology, Tianjin Medical University · Medical School, Tianjin University