Search

We study representation theory of the partially transposed permutation matrix algebra, a matrix representation of the diagrammatic walled Brauer algebra. This algebra plays a prominent role in mixed Schur-Weyl duality that appears in various contexts in quantum information. Our main technical result is an explicit formula for the action of the walled Brauer algebra generators in the Gelfand-Tsetlin basis. It generalizes the well-known Gelfand-Tsetlin basis for the symmetric group (also known as Young's orthogonal form or Young-Yamanouchi basis). We provide two applications of our result to quantum information. First, we show how to simplify semidefinite optimization problems over unitary-equivariant quantum channels by performing a symmetry reduction. Second, we derive an efficient quantum circuit for implementing the optimal port-based quantum teleportation protocol, exponentially improving the known trivial construction. As a consequence, this also exponentially improves the known lower bound for the amount of entanglement needed to implement unitaries non-locally. Both applications require a generalization of quantum Schur transform to tensors of mixed unitary symmetry. We develop an efficient quantum circuit for this mixed quantum Schur transform and provide a matrix product state representation of its basis vectors. For constant local dimension, this yields an efficient classical algorithm for computing any entry of the mixed quantum Schur transform unitary.

Majority vote is a basic method for amplifying correct outcomes that is widely used in computer science and beyond. While it can amplify the correctness of a quantum device with classical output, the analogous procedure for quantum output is not known. We introduce quantum majority vote as the following task: given a product state $|\psi_1\rangle \otimes \dots \otimes |\psi_n\rangle$ where each qubit is in one of two orthogonal states $|\psi\rangle$ or $|\psi^\perp\rangle$, output the majority state. We show that an optimal algorithm for this problem achieves worst-case fidelity of $1/2 + \Theta(1/\sqrt{n})$. Under the promise that at least $2/3$ of the input qubits are in the majority state, the fidelity increases to $1 - \Theta(1/n)$ and approaches $1$ as $n$ increases. We also consider the more general problem of computing any symmetric and equivariant Boolean function $f: \{0,1\}^n \to \{0,1\}$ in an unknown quantum basis, and show that a generalization of our quantum majority vote algorithm is optimal for this task. The optimal parameters for the generalized algorithm and its worst-case fidelity can be determined by a simple linear program of size $O(n)$. The time complexity of the algorithm is $O(n^4 \log n)$ where $n$ is the number of input qubits., Comment: 85 pages, 8 figures

Unitary equivariance is a natural symmetry that occurs in many contexts in physics and mathematics. Optimization problems with such symmetry can often be formulated as semidefinite programs for a $d^{p+q}$-dimensional matrix variable that commutes with $U^{\otimes p} \otimes \bar{U}^{\otimes q}$, for all $U \in \mathrm{U}(d)$. Solving such problems naively can be prohibitively expensive even if $p+q$ is small but the local dimension $d$ is large. We show that, under additional symmetry assumptions, this problem reduces to a linear program that can be solved in time that does not scale in $d$, and we provide a general framework to execute this reduction under different types of symmetries. The key ingredient of our method is a compact parametrization of the solution space by linear combinations of walled Brauer algebra diagrams. This parametrization requires the idempotents of a Gelfand-Tsetlin basis, which we obtain by adapting a general method arXiv:1606.08900 inspired by the Okounkov-Vershik approach. To illustrate potential applications, we use several examples from quantum information: deciding the principal eigenvalue of a quantum state, quantum majority vote, asymmetric cloning and transformation of a black-box unitary. We also outline a possible route for extending our method to general unitary-equivariant semidefinite programs., Comment: 68 pages; new application: transformation (transposition) of a black-box unitary

The Solovay-Kitaev theorem states that universal quantum gate sets can be exchanged with low overhead. More specifically, any gate on a fixed number of qudits can be simulated with error $\epsilon$ using merely $\mathrm{polylog}(1/\epsilon)$ gates from any finite universal quantum gate set $\mathcal{G}$. One drawback to the theorem is that it requires the gate set $\mathcal{G}$ to be closed under inversion. Here we show that this restriction can be traded for the assumption that $\mathcal{G}$ contains an irreducible representation of any finite group $G$. This extends recent work of Sardharwalla et al. [arXiv:1602.07963], and applies also to gates from the special linear group. Our work can be seen as partial progress towards the long-standing open problem of proving an inverse-free Solovay-Kitaev theorem [arXiv:quant-ph/0505030, arXiv:0908.0512]., Comment: 16 pages, TQC 2018 proceedings version

We devise a ternary operation for combining three quantum states: it consists of permuting the input systems in a continuous fashion and then discarding all but one of them. This generalizes a binary operation recently studied by Audenaert et al. [arXiv:1503.04213] in the context of entropy power inequalities. Our ternary operation continuously interpolates between all such nested binary operations. Our construction is based on a unitary version of Cayley's theorem: using representation theory we show that any finite group can be naturally embedded into a continuous subgroup of the unitary group. Formally, this amounts to characterizing when a linear combination of certain permutations is unitary., Comment: 26 pages, 4 figures, 1 table. v2: small corrections throughout + the four-bar linkage