We formalize the task of unitary Schur sampling -- an extension of weak Schur sampling -- which is the process of measuring the Young label and the unitary group register of an input $m$ qudit state. Intuitively, this task is equivalent to applying the Schur transform, projecting onto the isotypic subspaces of the unitary and symmetric groups indexed by the Young labels, and discarding of the permutation register. As such unitary Schur sampling is the natural task in processes such as quantum state tomography or spectrum estimation. We generalize this task to unitary mixed Schur sampling to account for the recently introduced mixed Schur-Weyl transform. We provide a streaming algorithm which achieves an exponential reduction in the memory complexity and a polynomial reduction in the gate complexity over naïve algorithms for the task of unitary (mixed) Schur sampling. Further, we show that if the input state has limited rank, the gate and memory complexities of our streaming algorithm as well as the algorithms for the full Schur and mixed Schur transforms are further reduced. Our work generalizes and improves on the results in arXiv2309.11947.
We formalize the task of unitary Schur sampling -- an extension of weak Schur sampling -- which is the process of measuring the Young label and the unitary group register of an input m qudit state. Intuitively, this task is equivalent to applying the Schur transform, projecting onto the isotypic subspaces of the unitary and symmetric groups indexed by the Young labels, and discarding of the permutation register. As such unitary Schur sampling is the natural task in processes such as quantum state tomography or spectrum estimation. We generalize this task to unitary mixed Schur sampling to account for the recently introduced mixed Schur-Weyl transform. We provide a streaming algorithm which achieves an exponential reduction in the memory complexity and a polynomial reduction in the gate complexity over naïve algorithms for the task of unitary (mixed) Schur sampling. Further, we show that if the input state has limited rank, the gate and memory complexities of our streaming algorithm as well as the algorithms for the full Schur and mixed Schur transforms are further reduced. Our work generalizes and improves on the results in arXiv2309.11947.
The quantum Schur transform maps the computational basis of a system of n qudits onto a \textit{Schur basis}, which spans the minimal invariant subspaces of the representations of the unitary and the symmetric groups acting on the state space of nd-level systems. We introduce a new algorithm for the task of weak Schur sampling. Our algorithm efficiently determines both the Young label which indexes the irreducible representations and the multiplicity label of the symmetric group. There are two major advantages of our algorithm for weak Schur sampling when compared to existing approaches which proceed via quantum Schur transform algorithm or Generalized Phase Estimation algorithm. First, our algorihtm is suitable for streaming applications and second it is exponentially more efficient in its memory usage. We show that an instance of our weak Schur sampling algorithm on n qubits to accuracy ε requires only O(log2n) qubits of memory and O(n3log2(εn)) gates from the Clifford+T set. Further, we show that our weak Schur sampling algorithm on n qudits decomposes into O(dn2dlog2p(εn2d)) gates from an arbitrary fault-tolerant qudit universal set, for p≈4, and requires a memory of O(logdn) qudits to implement.
Schur sampling is a fundamental primitive for extracting permutation-invariant information from many-body quantum systems and has broad applications in quantum information science. Circuit-based implementations typically rely on coherent representation-theoretic operations such as Clebsch-Gordan transforms, generalized phase estimation, or quantum Fourier transforms over the symmetric group. We show that unitary Schur sampling of arbitrary permutation-invariant mixed states on nd-dimensional qudits can instead be implemented using only pairwise SWAP tests, namely, two-qudit projective measurements onto the symmetric and antisymmetric subspaces. Our protocol achieves error ε in diamond distance using O(nmin{n,d}3log2(n/ε)) random SWAP tests. The central idea is to repeatedly identify and extract the largest antisymmetric subsystem. This turns unitary Schur sampling into a search for antisymmetry and gives the algorithm a natural interpretation as a stochastic traversal of a Young diagram. The protocol preserves the SU(d)-irrep state while preparing a canonical pure state in the multiplicity subsystem. As an application, we consider quantum purity amplification (QPA), in which multiple noisy copies of a pure quantum state are combined to produce a state of higher purity. We show that the optimal purified state can be obtained by retaining a single designated output qudit and discarding the rest.
We consider the computational task of anti-symmetrization of an unknown mixed quantum state: Given iid copies of a rank-r qudit state ρ=∑i=1rλi∣φi⟩⟨φi∣, prepare a copy of the state proportional to Πantir(∣φ1⟩⊗…⊗∣φr⟩), with Πantir the anti-symmetric subspace projector. We first give a simple algorithm for anti-symmetrization that uses O(r/λmin) copies of ρ, where λmin is the minimum non-zero eigenvalue of ρ. This algorithm works even in the streaming setting with small working memory, and it uses only simple quantum operations like controlled-SWAPs and constantly many layers of single-qubit gates. As an application of this streaming anti-symmetrization procedure, we give a reduction from gapped mixed-state one-way state generators to pure-state one-way state generators. Then, using tools from Schur-Weyl duality, we give and analyze a second (non-streaming) anti-symmetrization procedure that uses O(r/λmin) copies of ρ, which then serves as a building block in new algorithms for weak Schur sampling and unitary Schur sampling, outperforming existing approaches in some regimes of number of copies n and local dimension d, as well as in an algorithm for optimal purity amplification for qudit states.
Many quantum information tasks use inputs of the form ρ⊗m, which naturally induce permutation and unitary symmetries. We classify all quantum channels that respect both symmetries - i.e. unitary-equivariant and permutation-invariant quantum channels from (Cd)⊗m to (Cd)⊗n - via their extremal points. Operationally, each extremal quantum channel factors as unitary Schur sampling → an irrep-level unitary-equivariant quantum channel → the adjoint unitary Schur sampling. We give a streaming implementation ansatz that uses an efficient streaming implementation of unitary Schur sampling together with a resource-state primitive, and we apply it to state symmetrization, symmetric cloning, and purity amplification. In these applications we obtain polynomial-time algorithms with exponential memory improvements in m,n. Further, for symmetric cloning we present, to our knowledge, the first efficient (polynomial-time) algorithm with explicit memory and gate bounds.
We initiate the study of weak Schur sampling (WSS) under noisy inputs. Many optimal quantum learning algorithms rely on this measurement, for instance in quantum spectrum estimation (QSE) and quantum state tomography (QST). The standard analysis of WSS, QSE and QST assumes that the n input copies of the target state ρ are identical, i.e. ρ⊗n. We study what happens when they are not, a more realistic noisy scenario that breaks the very permutation symmetry on which WSS is built. In the simplest model the input is a noisy product state: the copies are independent but not necessarily identical and each is ε-close in trace distance to the d-dimensional target state ρ. A naive argument via the data-processing inequality allows the per-copy errors to accumulate to nε on the measurement outcome. We show that for QSE via WSS this does not happen: the expected estimation error in total variation is at most ε+η(n,d), where η(n,d)=O(d/n) is the noiseless error, and the additive noise term ε is optimal. The output error does not grow with n even though the input error does; in this sense WSS is robust. Beyond noisy product states, for arbitrary input ω we show that the error is at most η(n,d)+n1∥ω−ρ⊗n∥W1, where W1 is the quantum Wasserstein distance of De Palma et al. In particular, our results imply, for the first time, noise-robustness of Keyl and Werner's seminal algorithm for QSE, more than two decades after its introduction. Finally, we show that the noise cannot be too bad: within our model of robustness the promise on the input cannot be weakened to closeness of single-copy marginals or to a global trace-distance budget alone, as in both cases some inputs defeat every measurement and estimator.
Quantum state tomography is the fundamental physical task of learning a complete classical description of an unknown state of a quantum system given coherent access to many identical samples of it. The complexity of this task is commonly characterised by its sample-complexity: the minimal number of samples needed to reach a certain target precision of the description. While the sample complexity of quantum state tomography has been well studied, the memory complexity has not been investigated in depth. Indeed, the bottleneck in the implementation of naïve sample-optimal quantum state tomography is its massive quantum memory requirements. In this work, we propose and analyse a quantum state tomography algorithm which retains sample-optimality but is also memory-efficient. Our work is built on a form of unitary Schur sampling and only requires streaming access to the samples.