We present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the Schur transform. The Schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. If we desire to implement the Schur transform to an accuracy of epsilon, then our circuit construction uses a number of gates which is polynomial in n, d and log(1/epsilon). The important insights we use to perform this construction are the selection of the appropriate subgroup adapted basis and the Wigner-Eckart theorem. Our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and is an important new efficient quantum circuit family which goes significantly beyond the standard paradigm of the quantum Fourier transform.
We present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the Schur transform. The Schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. If we desire to implement the Schur transform to an accuracy of epsilon, then our circuit construction uses a number of gates which is polynomial in n, d and log(1/epsilon). The important insights we use to perform this construction are the selection of the appropriate subgroup adapted basis and the Wigner-Eckart theorem. Our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and is an important new efficient quantum circuit family which goes significantly beyond the standard paradigm of the quantum Fourier transform.
We present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the Schur transform. The Schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. If we desire to implement the Schur transform to an accuracy of e-1, then our circuit construction uses a number of gates which is polynomial in n, d and log(e-1). The key tool in our construction is a poly(d, log n, log(e-1)) algorithm for the ud Clebsch-Gordan transform. Our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and yields a new possible approach to quantum algorithms which is distinct from the standard paradigm of the quantum Fourier transform.
The Schur basis on n d-dimensional quantum systems is a generalization of the total angular momentum basis that is useful for exploiting symmetry under permutations or collective unitary rotations. We present efficient {size poly[n,d,log(1/epsilon)] for accuracy epsilon} quantum circuits for the Schur transform, which is the change of basis between the computational and the Schur bases. Our circuits provide explicit efficient methods for solving such diverse problems as estimating the spectrum of a density operator, quantum hypothesis testing, and communicating without a shared reference frame. We thus render tractable a large series of methods for extracting resources from quantum systems and for numerous quantum information protocols.
We describe an efficient quantum algorithm for the quantum Schur transform. The Schur transform is an operation on a quantum computer that maps the standard computational basis to a basis composed of irreducible representations of the unitary and symmetric groups. We simplify and extend the algorithm of Bacon, Chuang, and Harrow, and provide a new practical construction as well as sharp theoretical and practical analyses. Our algorithm decomposes the Schur transform on n qubits into O(n^4\log(\frac{n}{\eps})) operators in the Clifford+T fault-tolerant gate set and uses exactly 2\lfloor\log_2(n)\rfloor-1 ancillary qubits. We extend our qubit algorithm to decompose the Schur transform on n qudits of dimension d into O(d^{1+p}n^{3d}\log^p(\frac{d n}{\eps})) primitive operators from any universal gate set, for p~3.97.
Quantum Fourier transforms (QFTs) are essential primitives in quantum algorithms. While abelian groups admit efficient QFT circuits, with circuit size polynomial in the logarithm of the group order, efficient constructions are known for relatively few non-abelian families. We develop two new approaches to QFT circuit construction, based on Mackey theory and Clifford theory, respectively, and use them to show exponential improvement in circuit cost for specific group families. Using the Mackey-theoretic approach, we obtain explicit quantum circuits for the QFT over GL2(Fq) that scale polynomially in logq, rather than polynomially in q. Using the Clifford-theoretic approach, we obtain QFT circuits for wreath products F≀Sn, whose cost depends on the cost of a QFT over F and the size of its representation registers. This removes the restriction ∣F∣=poly(n) required by previous generic constructions and can yield exponential improvements when F itself has an efficient QFT. Together, these methods provide new systematic tools to construct QFTs for broad classes of finite groups.
The quantum Fourier transform (QFT) is a fundamental primitive in quantum computation and quantum information. In this work, we extend the framework for the QFT from finite groups to finite-dimensional semisimple algebras, and give efficient QFTs for the partition algebra Pn(d), Brauer algebra Bn(d), and walled Brauer algebra Br,s(d). These algebras play important roles in generalized Schur-Weyl duality, statistical physics and many-body systems, and have recently found several applications in quantum algorithms.
Unlike the group case, the Fourier transform over a semisimple algebra can be non-unitary. Nevertheless, we show that when the parameter d is sufficiently large, the Fourier transform is well approximated by a unitary operator. Furthermore, we show that for each of the algebras A from above, such an approximate Fourier transform can be implemented efficiently: we give a quantum algorithm with gate complexity poly(n,logd,log(1/ε)) for approximating the Fourier transform to error (d−1/2+ε)⋅poly(∣A∣). Along the way, we establish several properties of the Fourier basis of semisimple algebras that may be of independent interest.
The Schur transform is a unitary operator that block diagonalizes the action of the symmetric and unitary groups on an n fold tensor product V ⊗ n of a vector space V of dimension d . Bacon, Chuang and Harrow [5] gave a quantum algorithm for this transform that is polynomial in n , d and log ϵ − 1 , where ϵ is the precision. In a footnote in Harrow's thesis [18], a brief description of how to make the algorithm of [5] polynomial in log d is given using the unitary group representation theory (however, this has not been explained in detail anywhere). In this article, we present a quantum algorithm for the Schur transform that is polynomial in n , log d and log ϵ − 1 using a different approach. Specifically, we build this transform using the representation theory of the symmetric group and in this sense our technique can be considered a ''dual" algorithm to [5]. A novel feature of our algorithm is that we construct the quantum Fourier transform over the so called permutation modules , which could have other applications.