A Classical Algorithm for Quantum $\text{SU}(2)$ Schur Sampling

Abstract

Many quantum algorithms can be represented in a form of a classical circuit positioned between quantum Fourier transformations. Motivated by the search for new quantum algorithms, we turn to circuits where the latter transformation is replaced by the $\text{SU}(2)$ quantum Schur Transform -- a global transformation which maps the computational basis to a basis defined by angular momenta. We show that the output distributions of these circuits can be approximately classically sampled in polynomial time if they are sufficiently close to being sparse, thus isolating a regime in which these Quantum $\text{SU}(2)$ Schur Circuits could lead to algorithms with exponential computational advantage. Our work is primarily motivated by a conjecture that underpinned the hardness of Permutational Quantum Computing, a restricted quantum computational model that has the above circuit structure in one of its computationally interesting regimes. The conjecture stated that approximating transition amplitudes of Permutational Quantum Computing model to inverse polynomial precision on a classical computer is computationally hard. We disprove the extended version of this conjecture -- even in the case when the hardness of approximation originated from a difficulty of finding the large elements in the output probability distributions. Finally, we present some evidence that output of the above Permutational Quantum Computing circuits could be efficiently approximately sampled from on a classical computer.

arXiv commentSignificant update of the article to improve clarity of the presentation

References in corpus (22)

• Reference frames, superselection rules, and quantum information
• Theory of Decoherence-Free Fault-Tolerant Universal Quantum Computation
• Quantum measurements and the Abelian Stabilizer Problem
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• State estimation for large ensembles
• Classical and quantum communication without a shared reference frame
• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• Estimating the spectrum of a density operator
• Topological Quantum Compiling
• Quantum universal variable-length source coding
• Applications of coherent classical communication and the Schur transform to quantum information theory
• Computing Spin Networks
• An efficient high dimensional quantum Schur transform
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• Quantum simulation of partially distinguishable boson sampling
• Quantum Schur Sampling Circuits can be Strongly Simulated
• Variable length universal entanglement concentration by local operations and its application to teleportation and dense coding
• A Practical Quantum Algorithm for the Schur Transform
• Extended Quantum Color Coding
• Fast quantum algorithms for approximating some irreducible representations of groups
• How SU(2)${}_4$ Anyons are Z${}_3$ Parafermions

Cited by in corpus (5)

• Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ansätze
• 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
• Toward Super-polynomial Quantum Speedup of Equivariant Quantum Algorithms with SU($d$) Symmetry
• All you need is spin: SU(2) equivariant variational quantum circuits based on spin networks