Schur-Weyl duality and symmetric problems with quantum input

In many natural situations where the input consists of n quantum systems, each associated with a state space C^d, we are interested in problems that are symmetric under the permutation of the n systems as well as the application of the same unitary U to all n systems. Under these circumstances, the optimal algorithm often involves a basis transformation, known as (quantum) Schur transform, which simultaneously block-diagonalizes the said actions of the permutation and the unitary groups.

I will illustrate how Schur-Weyl duality can be used to identify optimal quantum algorithm for quantum majority vote and, more generally, compute symmetric Boolean functions on quantum data.

This is based on joint work "Quantum majority and other Boolean functions with quantum inputs" with H. Buhrman, N. Linden, A. Montanaro, and M. Ozols.