MCMatthias Christandl

Matthias Christandl

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Matthias Christandl has a total of 11 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Computing Multiplicities of Lie Group Representations

    by Matthias Christandl, Brent Doran, Michael Walter

    For fixed compact connected Lie groups H \subseteq G, we provide a polynomial time algorithm to compute the multiplicity of a given irreducible representation of H in the restriction of an irreducible representation of G. Our algorithm is based on a finite difference formula which makes the multiplicities amenable to Barvinok's algorithm for counting integral points in polytopes. The Kronecker coefficients of the symmetric group, which can be seen to be a special case of such multiplicities, play an important role in the geometric complexity theory approach to the P vs. NP problem. Whereas their computation is known to be #P-hard for Young diagrams with an arbitrary number of rows, our algorithm computes them in polynomial time if the number of rows is bounded. We complement our work by showing that information on the asymptotic growth rates of multiplicities in the coordinate rings of orbit closures does not directly lead to new complexity-theoretic obstructions beyond what can be obtained from the moment polytopes of the orbit closures. Non-asymptotic information on the multiplicities, such as provided by our algorithm, may therefore be essential in order to find obstructions in geometric complexity theory.

  • Erratum to: Faithful Squashed Entanglement

    by Fernando G. S. L. Brandão, Matthias Christandl, Jon Yard


  • Reliable Quantum State Tomography

    by Matthias Christandl, Renato Renner

    Quantum state tomography is the task of inferring the state of a quantum system by appropriate measurements. Since the frequency distributions of the outcomes of any finite number of measurements will generally deviate from their asymptotic limits, the estimates computed by standard methods do not in general coincide with the true state and, therefore, have no operational significance unless their accuracy is defined in terms of error bounds. Here we show that quantum state tomography, together with an appropriate data analysis procedure, yields reliable and tight error bounds, specified in terms of confidence regions\char22{}a concept originating from classical statistics. Confidence regions are subsets of the state space in which the true state lies with high probability, independently of any prior assumption on the distribution of the possible states. Our method for computing confidence regions can be applied to arbitrary measurements including fully coherent ones; it is practical and particularly well suited for tomography on systems consisting of a small number of qubits, which are currently in the focus of interest in experimental quantum information science.


  • Open Access

    Faithful Squashed Entanglement

    by Fernando G. S. L. Brandao, Matthias Christandl, Jon Yard

    Squashed entanglement is a measure for the entanglement of bipartite quantum states. In this paper we present a lower bound for squashed entanglement in terms of a distance to the set of separable states. This implies that squashed entanglement is faithful, that is, strictly positive if and only if the state is entangled. We derive the bound on squashed entanglement from a bound on quantum conditional mutual information, which is used to define squashed entanglement and corresponds to the amount by which strong subadditivity of von Neumann entropy fails to be saturated. Our result therefore sheds light on the structure of states that almost satisfy strong subadditivity with equality. The proof is based on two recent results from quantum information theory: the operational interpretation of the quantum mutual information as the optimal rate for state redistribution and the interpretation of the regularised relative entropy of entanglement as an error exponent in hypothesis testing. The distance to the set of separable states is measured by the one-way LOCC norm, an operationally-motivated norm giving the optimal probability of distinguishing two bipartite quantum states, each shared by two parties, using any protocol formed by local quantum operations and one-directional classical communication between the parties. A similar result for the Frobenius or Euclidean norm follows immediately. The result has two applications in complexity theory. The first is a quasipolynomial-time algorithm solving the weak membership problem for the set of separable states in one-way LOCC or Euclidean norm. The second concerns quantum Merlin-Arthur games. Here we show that multiple provers are not more powerful than a single prover when the verifier is restricted to one-way LOCC operations thereby providing a new characterisation of the complexity class QMA.

  • Open Access

    Nonvanishing of Kronecker coefficients for rectangular shapes

    by Peter Bürgisser, Matthias Christandl, Christian Ikenmeyer

    We prove that for any partition $(\lambda_1,...,\lambda_{d^2})$ of size $\ell d$ there exists $k\ge 1$ such that the tensor square of the irreducible representation of the symmetric group $S_{k\ell d}$ with respect to the rectangular partition $(k\ell,...,k\ell)$ contains the irreducible representation corresponding to the stretched partition $(k\lambda_1,...,k\lambda_{d^2})$. We also prove a related approximate version of this statement in which the stretching factor $k$ is effectively bounded in terms of $d$. This investigation is motivated by questions of geometric complexity theory.

  • Open Access

    Entanglement of the Antisymmetric State

    by Matthias Christandl, Norbert Schuch, Andreas Winter

    We analyse the entanglement of the antisymmetric state in dimension d x d and present two main results. First, we show that the amount of secrecy that can be extracted from the state is low, more precisely, the distillable key is bounded by O(1/d). Second, we show that the state is highly entangled in the sense that a large number of ebits are needed in order to create the state: entanglement cost is larger than a constant, independent of d. The second result is shown to imply that the regularised relative entropy with respect to separable states is also lower bounded by a constant. Finally, we note that the regularised relative entropy of entanglement is asymptotically continuous in the state. Elementary and advanced facts from the representation theory of the unitary group, including the concept of plethysm, play a central role in the proofs of the main results.

  • Entanglement of the Antisymmetric State

    by Matthias Christandl, Norbert Schuch, Andreas Winter


  • Open Access

    The Quantum Reverse Shannon Theorem based on One-Shot Information Theory

    by Mario Berta, Matthias Christandl, Renato Renner

    The Quantum Reverse Shannon Theorem states that any quantum channel can be simulated by an unlimited amount of shared entanglement and an amount of classical communication equal to the channel's entanglement assisted classical capacity. In this paper, we provide a new proof of this theorem, which has previously been proved by Bennett, Devetak, Harrow, Shor, and Winter. Our proof has a clear structure being based on two recent information-theoretic results: one-shot Quantum State Merging and the Post-Selection Technique for quantum channels.

  • Open Access

    The Quantum Reverse Shannon Theorem Based on One-Shot Information Theory

    by Mario Berta, Matthias Christandl, Renato Renner


  • Open Access

    A quasipolynomial-time algorithm for the quantum separability problem

    by Fernando G. S. L. Brandao, Matthias Christandl, Jon Yard

    We present a quasipolynomial-time algorithm for solving the weak membership problem for the convex set of separable, i.e. non-entangled, bipartite density matrices. The algorithm decides whether a density matrix is separable or whether it is eps-away from the set of the separable states in time exp(O(eps^-2 log |A| log |B|)), where |A| and |B| are the local dimensions, and the distance is measured with either the Euclidean norm, or with the so-called LOCC norm. The latter is an operationally motivated norm giving the optimal probability of distinguishing two bipartite quantum states, each shared by two parties, using any protocol formed by quantum local operations and classical communication (LOCC) between the parties. We also obtain improved algorithms for optimizing over the set of separable states and for computing the ground-state energy of mean-field Hamiltonians. The techniques we develop are also applied to quantum Merlin-Arthur games, where we show that multiple provers are not more powerful than a single prover when the verifier is restricted to LOCC protocols, or when the verification procedure is formed by a measurement of small Euclidean norm. This answers a question posed by Aaronson et al (Theory of Computing 5, 1, 2009) and provides two new characterizations of the complexity class QMA, a quantum analog of NP. Our algorithm uses semidefinite programming to search for a symmetric extension, as first proposed by Doherty, Parrilo and Spedialieri (Phys. Rev. A, 69, 022308, 2004). The bound on the runtime follows from an improved de Finetti-type bound quantifying the monogamy of quantum entanglement, proved in (arXiv:1010.1750). This result, in turn, follows from a new lower bound on the quantum conditional mutual information and the entanglement measure squashed entanglement.