Click here to flash read.
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}{\epsilon}))$ Clifford + T gates, where $\epsilon$ is
the accuracy of the algorithm in terms of the trace norm. This matches the best
known upper bound for the ancilla count of previous implementations. 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.
No creative common's license