Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Schur Sampling is Classically Tractable

Vojtěch Havlíček, Sergii Strelchuk

Published Jan 15, 2018• 1 citation
OpenAlex

Abstract

Permutational Quantum Computing (Jordan, 2009) is a natural quantum computational model that was conjectured to capture non-classical aspects of quantum computation. Contrary to the previous conjecture, we find a classical algorithm that efficiently approximates output distributions of the model up to polynomially small additive precision. We extend this algorithm to show that a large class of important quantum circuits - the Quantum Schur Sampling circuits - can be also efficiently simulated classically. The algorithm can be used to efficiently estimate non-trivial elements of irreducible representation matrices of the symmetric group on $n$ elements and might be also used to approximate transition amplitudes of the Ponzano-Regge model.

Related papers

Quantum Schur Sampling Circuits can be Strongly Simulated

Vojtěch Havlíček, Sergii Strelchuk

Permutational quantum computing (PQC) [Quantum Inf. Comput., 10, 470-497 (2010)QICUAW1533-7146] is a natural quantum computational model conjectured to capture nonclassical 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 also be efficiently classically approximated.

arXiv:1801.04795•Physical Review Letters•Aug 8, 2018•17 citations

Classical algorithm for quantum SU(2) Schur sampling

Vojtěch Havlíček, Sergii Strelchuk, Kristan Temme

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 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 they could lead to algorithms with exponential computational advantages. Our paper 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 in this case. 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:1809.05171•Physical Review A•Jun 27, 2019•8 citations

Sampling from quantum Schur circuits with sparse output

Vojtěch Havlíček, Sergii Strelchuk, Kristan Temme

A large class of quantum algorithms can be represented by placing a reversible classical circuit, or diagonal gates, between a pair of quantum Fourier transformations. Notable examples include the circuit from Shor's factoring algorithm and IQP circuits. Here we study quantum circuits with a similar structure, where the QFT has been replaced by a sequentially coupled quantum Schur transform. We extend the Kushilevitz-Mansour algorithm for sampling from Fourier-sparse output distributions to these circuits. It is shown that samples from a classical distribution close to the output of a sparse Schur circuit can be efficiently generated by this classical method. In particular, it implies that circuits as found in a computationally interesting regime of Permutational Quantum Computing can be sampled from efficiently classically, assuming they give rise to sparse output distributions. Numerical simulations indicate that a significant fraction of Permutational circuits on a small number of qubits have this property, allowing for efficient sampling of their output.

•Sep 13, 2018•0 citations

Simulating Quantum Circuits with Sparse Output Distributions

Martin Schwarz, Maarten Van den Nest

We show that several quantum circuit families can be simulated efficiently classically if it is promised that their output distribution is approximately sparse i.e. the distribution is close to one where only a polynomially small, a priori unknown subset of the measurement probabilities are nonzero. Classical simulations are thereby obtained for quantum circuits which---without the additional sparsity promise---are considered hard to simulate. Our results apply in particular to a family of Fourier sampling circuits (which have structural similarities to Shor's factoring algorithm) but also to several other circuit families, such as IQP circuits. Our results provide examples of quantum circuits that cannot achieve exponential speed-ups due to the presence of too much destructive interference i.e. too many cancelations of amplitudes. The crux of our classical simulation is an efficient algorithm for approximating the significant Fourier coefficients of a class of states called computationally tractable states. The latter result may have applications beyond the scope of this work. In the proof we employ and extend sparse approximation techniques, in particular the Kushilevitz-Mansour algorithm, in combination with probabilistic simulation methods for quantum circuits.

arXiv:1310.6749•Electronic colloquium on computational complexity•Oct 24, 2013•23 citations

Generalised Coupling and An Elementary Algorithm for the Quantum Schur Transform

Adam Wills, Sergii Strelchuk

The quantum Schur transform is a fundamental building block that maps the computational basis to a coupled basis consisting of irreducible representations of the unitary and symmetric groups. Equivalently, it may be regarded as a change of basis from the computational basis to a simultaneous spin eigenbasis of Permutational Quantum Computing (PQC) [Quantum Inf. Comput., 10, 470-497 (2010)]. By adopting the latter perspective, we present a transparent algorithm for implementing the qubit quantum Schur transform which uses $O(\log(n))$ ancillas and can be decomposed into a sequence of $O(n^3\log(n)\log(\frac{n}ε))$ Clifford + T gates, where $ε$ is the accuracy of the algorithm in terms of the trace norm. We discuss the necessity for some applications of implementing this operation as a unitary rather than an isometry, as is often presented. By studying the associated Schur states, which consist of qubits coupled via Clebsch-Gordan coefficients, we introduce the notion of generally coupled quantum states. We present six conditions, which in different combinations ensure the efficient preparation of these states on a quantum computer or their classical simulability (in the sense of computational tractability). It is shown that Wigner 6-j symbols and SU(N) Clebsch-Gordan coefficients naturally fit our framework. Finally, we investigate unitary transformations which preserve the class of computationally tractable states.

arXiv:2305.04069•May 6, 2023•0 citations

Classical Simulation of Peaked Shallow Quantum Circuits

Sergey B. Bravyi, David Gosset, Yinchen Liu

An n-qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of n. We describe a classical algorithm with quasipolynomial runtime nO(logn) that approximately samples from the output distribution of a peaked constant-depth circuit. We give even faster algorithms for circuits composed of nearest-neighbor gates on a D-dimensional grid of qubits, with polynomial runtime nO(1) if D=2 and almost-polynomial runtime nO(loglogn) for D>2. Our sampling algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error, improving previously known methods. As a simple application, we obtain a quasipolynomial algorithm to estimate the magnitude of the expected value of any Pauli observable in the output state of a shallow circuit (which may or may not be peaked). This is a dramatic improvement over the prior state-of-the-art algorithm which had an exponential scaling in √n.

arXiv:2309.08405•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•4 citations
Permutational Quantum Computing (Jordan, 2009) is a natural quantum computational model that was conjectured to capture non-classical aspects of quantum computation. Contrary to the previous conjecture, we find a classical algorithm that efficiently approximates output distributions of the model up to polynomially small additive precision. We extend this algorithm to show that a large class of important quantum circuits - the Quantum Schur Sampling circuits - can be also efficiently simulated classically. The algorithm can be used to efficiently estimate non-trivial elements of irreducible representation matrices of the symmetric group on nnn elements and might be also used to approximate transition amplitudes of the Ponzano-Regge model.
Permutational quantum computing (PQC) [Quantum Inf. Comput., 10, 470-497 (2010)QICUAW1533-7146] is a natural quantum computational model conjectured to capture nonclassical 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 also be efficiently classically approximated.
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 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 they could lead to algorithms with exponential computational advantages. Our paper 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 in this case. 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.
A large class of quantum algorithms can be represented by placing a reversible classical circuit, or diagonal gates, between a pair of quantum Fourier transformations. Notable examples include the circuit from Shor's factoring algorithm and IQP circuits. Here we study quantum circuits with a similar structure, where the QFT has been replaced by a sequentially coupled quantum Schur transform. We extend the Kushilevitz-Mansour algorithm for sampling from Fourier-sparse output distributions to these circuits. It is shown that samples from a classical distribution close to the output of a sparse Schur circuit can be efficiently generated by this classical method. In particular, it implies that circuits as found in a computationally interesting regime of Permutational Quantum Computing can be sampled from efficiently classically, assuming they give rise to sparse output distributions. Numerical simulations indicate that a significant fraction of Permutational circuits on a small number of qubits have this property, allowing for efficient sampling of their output.
We show that several quantum circuit families can be simulated efficiently classically if it is promised that their output distribution is approximately sparse i.e. the distribution is close to one where only a polynomially small, a priori unknown subset of the measurement probabilities are nonzero. Classical simulations are thereby obtained for quantum circuits which---without the additional sparsity promise---are considered hard to simulate. Our results apply in particular to a family of Fourier sampling circuits (which have structural similarities to Shor's factoring algorithm) but also to several other circuit families, such as IQP circuits. Our results provide examples of quantum circuits that cannot achieve exponential speed-ups due to the presence of too much destructive interference i.e. too many cancelations of amplitudes. The crux of our classical simulation is an efficient algorithm for approximating the significant Fourier coefficients of a class of states called computationally tractable states. The latter result may have applications beyond the scope of this work. In the proof we employ and extend sparse approximation techniques, in particular the Kushilevitz-Mansour algorithm, in combination with probabilistic simulation methods for quantum circuits.
The quantum Schur transform is a fundamental building block that maps the computational basis to a coupled basis consisting of irreducible representations of the unitary and symmetric groups. Equivalently, it may be regarded as a change of basis from the computational basis to a simultaneous spin eigenbasis of Permutational Quantum Computing (PQC) [Quantum Inf. Comput., 10, 470-497 (2010)]. By adopting the latter perspective, we present a transparent algorithm for implementing the qubit quantum Schur transform which uses O(log⁡(n))O(\log(n))O(log(n)) ancillas and can be decomposed into a sequence of O(n3log⁡(n)log⁡(nε))O(n^3\log(n)\log(\frac{n}ε))O(n3log(n)log(εn​)) Clifford + T gates, where εεε is the accuracy of the algorithm in terms of the trace norm. We discuss the necessity for some applications of implementing this operation as a unitary rather than an isometry, as is often presented. By studying the associated Schur states, which consist of qubits coupled via Clebsch-Gordan coefficients, we introduce the notion of generally coupled quantum states. We present six conditions, which in different combinations ensure the efficient preparation of these states on a quantum computer or their classical simulability (in the sense of computational tractability). It is shown that Wigner 6-j symbols and SU(N) Clebsch-Gordan coefficients naturally fit our framework. Finally, we investigate unitary transformations which preserve the class of computationally tractable states.
An n-qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of n. We describe a classical algorithm with quasipolynomial runtime nO(logn) that approximately samples from the output distribution of a peaked constant-depth circuit. We give even faster algorithms for circuits composed of nearest-neighbor gates on a D-dimensional grid of qubits, with polynomial runtime nO(1) if D=2 and almost-polynomial runtime nO(loglogn) for D>2. Our sampling algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error, improving previously known methods. As a simple application, we obtain a quasipolynomial algorithm to estimate the magnitude of the expected value of any Pauli observable in the output state of a shallow circuit (which may or may not be peaked). This is a dramatic improvement over the prior state-of-the-art algorithm which had an exponential scaling in √n.