Quantum Schur Sampling Circuits can be Strongly Simulated

Abstract

Permutational Quantum Computing (PQC) [\emph{Quantum~Info.~Comput.}, \textbf{10}, 470--497, (2010)] is a natural quantum computational model conjectured to capture non-classical aspects of quantum computation. An argument backing this conjecture was the observation that there was no efficient classical algorithm for estimation of matrix elements of the $S_n$ irreducible representation matrices in the Young's orthogonal form, which correspond to transition amplitudes of a broad class of PQC circuits. This problem can be solved with a PQC machine in polynomial time, but no efficient classical algorithm for the problem was previously known. Here we give a classical algorithm that efficiently approximates the transition amplitudes up to polynomial additive precision and hence solves this problem. We further extend our discussion to show that transition amplitudes of a broader class of quantum circuits -- the Quantum Schur Sampling circuits -- can be also efficiently estimated classically.

Precision error and additional slip-ups corrected. Title changed to avoid confusion

References in corpus (5)

• Quantum Computational Supremacy
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• A Practical Quantum Algorithm for the Schur Transform

Cited by in corpus (14)

• Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ansätze
• An efficient high dimensional quantum Schur transform
• Efficient classical algorithms for simulating symmetric quantum systems
• Symmetry breaking/symmetry preserving circuits and symmetry restoration on quantum computers: A quantum many-body perspective
• Filtering states with total spin on a quantum computer
• Quantum simulation of partially distinguishable boson sampling
• Symmetry Protected Quantum Computation
• A Classical Algorithm for Quantum $\text{SU}(2)$ Schur Sampling
• Toward Super-polynomial Quantum Speedup of Equivariant Quantum Algorithms with SU($d$) Symmetry
• Amplitude Ratios and Neural Network Quantum States
• All you need is spin: SU(2) equivariant variational quantum circuits based on spin networks
• Exchange-Symmetrized Qudit Bell Bases and Bell-State Distinguishability
• SU(d)-Symmetric Random Unitaries: Quantum Scrambling, Error Correction, and Machine Learning
• Representation matching for delegated quantum computing