Prof. Dr. Robert König



Teaching
 Seminar Introduction to Information Theory (SS 2020)
 Seminar Matrix Analysis (SS 2020)
 Workshop: Das Buch der Beweise (SS 2020)
 Functional analysis (WS 2019/2020)
 Open problems in quantum information theory (WS 2019/2020)
 Coding and Information Theory (SS 2019)
 Representations of compact groups (SS 2019)
 Analysis 3 EI (WS 2018/2019)
 Workshop Kryptographie (SS 2018)
 Representations of compact groups (SS 2018)
 Matrix analysis in quantum theory (SS 2018)
 Reading group: Quantum Groups (WS 2017/2018)
 Mathematik fuer Physiker 2 (Analysis 1) (WS 2017/2018)
 Differential Topology (SS 2017)
 Concentration Inequalities (SS 2017)
 Fallstudien der Mathematischen Modellbildung (WS 2016/2017)
 Classical Mechanics (WS 2016/2017)
 Funktionentheorie (SS 2016)
 Reading group: Hypercontractivity (SS 2016)
 Workshop Kryptographie (SS 2016)
 Quantum Information Theory (SS 2016, with M. Wolf)
 Fallstudien der Mathematischen Modellbildung (WS 2015/2016)
 Reading group: Operator spaces (WS 2015/2016)
 Representations of compact groups (SS 2015)
 Entropie und Informationstheorie (SS 2015)
Research interests
 Quantum communication theory
 Faulttolerant quantum information processing
 Quantum computation
 Manybody physics and variational methods
Publications
 S. Bravyi, D. Gosset, R. König and M. Tomamichel. Quantum advantage
with noisy shallow circuits. Nature Physics 16, p. 1040–1045, July 2020.
arXiv
As increasingly sophisticated prototypes of quantum computers are being developed, a pressing challenge is to find computational problems that can be solved by an intermediatescale quantum computer, but are beyond the capabilities of existing classical computers. Previous work in this direction has introduced computational problems that can be solved with certainty by quantum circuits of depth independent of the input size (socalled shallow circuits) but cannot be solved with high probability by any shallow classical circuit. Here we show that such a separation in computational power persists even when the shallow quantum circuits are restricted to geometrically local gates in three dimensions and corrupted by noise. We also present a streamlined quantum algorithm that is shown to achieve a quantum advantage in a onedimensional geometry. The latter may be amenable to experimental implementation with the current generation of quantum computers.
 A. Kliesch and R. König. Continuum limits of homogeneous binary
trees and the Thompson group. Physical Review Letters vol. 124,
no. 010601, January 2020. arXiv
Tree tensor network descriptions of critical quantum spin chains are empirically known to reproduce correlation functions matching CFT predictions in the continuum limit. It is natural to seek a more complete correspondence, additionally incorporating dynamics. On the CFT side, this is determined by a representation of the diffeomorphism group of the circle. In a remarkable series of papers, Jones outlined a research program where the Thompson group T takes the role of the latter in the discrete setting, and representations of T are constructed from certain elements of a subfactor planar algebra. He also showed that for a particular example of such a construction, this approach only yields  in the continuum limit  a representation which is highly discontinuous and hence unphysical. Here we show that the same issue arises generically when considering tree tensor networks: the set of coarsegraining maps yielding discontinuous representations has full measure in the set of all isometries. This extends Jones’ nogo example to typical elements of the socalled tensor planar algebra. We also identify an easily verified necessary condition for a continuous limit to exist. This singles out a particular class of tree tensor networks. Our considerations apply to recent approaches for introducing dynamics in holographic codes.
 S. Bravyi, D. Gosset, R. König and M. Tomamichel. Quantum advantage
with noisy shallow circuits in 3D. Proceedings of Symposium on
Foundations of Computer Science, November 2019. arXiv
Prior work has shown that there exists a relation problem which can be solved with certainty by a constantdepth quantum circuit composed of geometrically local gates in two dimensions, but cannot be solved with high probability by any classical constant depth circuit composed of bounded fanin gates. Here we provide two extensions of this result. Firstly, we show that a separation in computational power persists even when the constantdepth quantum circuit is restricted to geometrically local gates in one dimension. The corresponding quantum algorithm is the simplest we know of which achieves a quantum advantage of this type. It may also be more practical for future implementations. Our second, main result, is that a separation persists even if the shallow quantum circuit is corrupted by noise. We construct a relation problem which can be solved with near certainty using a noisy constantdepth quantum circuit composed of geometrically local gates in three dimensions, provided the noise rate is below a certain constant threshold value. On the other hand, the problem cannot be solved with high probability by a noisefree classical circuit of constant depth. A key component of the proof is a quantum errorcorrecting code which admits constantdepth logical Clifford gates and singleshot logical state preparation. We show that the surface code meets these criteria. To this end, we provide a protocol for singleshot logical state preparation in the surface code which may be of independent interest.
 M. Fukuda and R. König. Typical entanglement for Gaussian states.
Journal of Mathematical Physics 60, 112203, November 2019. arXiv
We consider ensembles of bipartite states resulting from a random passive Gaussian unitary applied to a fiducial pure Gaussian state. We show that the symplectic spectra of the reduced density operators concentrate around that of a thermal state with the same energy. This implies, in particular, concentration of the entanglement entropy as well as other entropy measures. Our work extends earlier results on the typicality of entanglement beyond the two ensembles and the reduced purity measure considered in [A. Serafini, O. C. O. Dahlsten, D. Gross, and M. B. Plenio, J. Phys. A: Math. Theor., 40(31):9551 (2007)].
 M. Fukuda, R. König and I. Nechita. RTNI – A symbolic integrator for
Haarrandom tensor networks. Journal of Physics A: Mathematical and
Theoretical, vol. 52, no 425303, September 2019. arXiv
We provide a computer algebra package called Random Tensor Network Integrator (RTNI). It allows to compute averages of tensor networks containing multiple Haardistributed random unitary matrices and deterministic symbolic tensors. Such tensor networks are represented as multigraphs, with vertices corresponding to tensors or random unitaries and edges corresponding to tensor contractions. Input and output spaces of random unitaries may be subdivided into arbitrary tensor factors, with dimensions treated symbolically. The algorithm implements the graphical Weingarten calculus and produces a weighted sum of tensor networks representing the average over the unitary group. We illustrate the use of this algorithmic tool on some examples from quantum information theory, including entropy calculations for random tensor network states as considered in toy models for holographic duality. Mathematica and Python implementations are supplied.
 M. Gschwendtner, R. König, B. Sahinoglu and E. Tang. Quantum
ErrorDetection at Low Energies. Journal of High Energy Physics
vol. 2019, no. 21, September 2019. arXiv
Motivated by the close relationship between quantum errorcorrection, topological order, the holographic AdS/CFT duality, and tensor networks, we initiate the study of approximate quantum errordetecting codes in matrix product states (MPS). We first show that using openboundary MPS to define boundary to bulk encoding maps yields at most constant distance errordetecting codes. These are degenerate ground spaces of gapped local Hamiltonians. To get around this nogo result, we consider excited states, i.e., we use the excitation ansatz to construct encoding maps: these yield errordetecting codes with distance Ω(n^{1−ν}) for any ν ∈ (0, 1) for any ν ∈ (0, 1) and Ω(log n) encoded qubits. This shows that gapped systems contain – within isolated energy bands – errordetecting codes spanned by momentum eigenstates. We also consider the gapless HeisenbergXXX model, whose energy eigenstates can be described via Bethe ansatz tensor networks. We show that it contains – within its lowenergy eigenspace – an errordetecting code with the same parameter scaling. All these codes detect arbitrary dlocal (not necessarily geometrically local) errors even though they are not permutationinvariant. This suggests that a wide range of naturally occurring manybody systems possess intrinsic errordetecting features.
 M. Heinze and R. König. Universal Uhrig Dynamical Decoupling for
Bosonic Systems. Physical Review Letters,vol. 123, no. 010501, July 2019.
arXiv
We construct efficient deterministic dynamical decoupling schemes protecting continuous variable degrees of freedom. Our schemes target decoherence induced by quadratic systembath interactions with analytic timedependence. We show how to suppress such interactions to Nth order using only N pulses. Furthermore, we show to homogenize a 2mmode bosonic system using only (N + 1)^{2m+1} pulses, yielding  up to Nth order – an effective evolution described by noninteracting harmonic oscillators with identical frequencies. The decoupled and homogenized system provides natural decoherencefree subspaces for encoding quantum information. Our schemes only require pulses which are tensor products of singlemode passive Gaussian unitaries and SWAP gates between pairs of modes.
 S. Huber, R. König and M. Tomamichel. Jointly constrained semidefinite
bilinear programming with an application to Dobrushin curves. IEEE
Transactions on Information Theory, September 2019 (early access). arXiv
We propose a branchandbound algorithm for minimizing a bilinear functional of the form f(X,Y ) = tr+ tr(AX) + tr(BY ), of pairs of Hermitian matrices (X,Y ) restricted by joint semidefinite programming constraints. The functional is parametrized by selfadjoint matrices Q, A and B. This problem generalizes that of a bilinear program, where X and Y belong to polyhedra. The algorithm converges to a global optimum and yields upper and lower bounds on its value in every step. Various problems in quantum information theory can be expressed in this form. As an example application, we compute Dobrushin curves of quantum channels, giving upper bounds on classical coding with energy constraints.
 S. Bravyi, D. Gosset, R. König and K. Temme. Approximation algorithms
for quantum manybody problems. Journal of Mathematical Physics 60,
032203, March 2019. arXiv
We discuss classical algorithms for approximating the largest eigenvalue of quantum spin and fermionic Hamiltonians based on semidefinite programming relaxation methods. First, we consider traceless 2local Hamiltonians H describing a system of n qubits. We give an efficient algorithm that outputs a separable state whose energy is at least λ_{max}∕O(log n), where λ_{max} is the maximum eigenvalue of H. We also give a simplified proof of a theorem due to Lieb that establishes the existence of a separable state with energy at least λ_{max}∕9. Secondly, we consider a system of n fermionic modes and traceless Hamiltonians composed of quadratic and quartic fermionic operators. We give an efficient algorithm that outputs a fermionic Gaussian state whose energy is at least λ_{max}∕O(n log n). Finally, we show that Gaussian states can vastly outperform Slater determinant states commonly used in the HartreeFock method. We give a simple family of Hamiltonians for which Gaussian states and Slater determinants approximate λ_{max} within a fraction 1 − O(n^{−1}) and O(n^{−1}) respectively.
 S. Bravyi, D. Gosset and R. König. Quantum advantage with shallow
circuits. Science Vol. 362, Issue 6412, pp. 308311, October 2018. arXiv
We prove that constantdepth quantum circuits are more powerful than their classical counterparts. To this end we introduce a nonoracular version of the BernsteinVazirani problem which we call the 2D Hidden Linear Function problem. An instance of the problem is specified by a quadratic form q that maps nbit strings to integers modulo four. The goal is to identify a linear boolean function which describes the action of q on a certain subset of nbit strings. We prove that any classical probabilistic circuit composed of bounded fanin gates that solves the 2D Hidden Linear Function problem with high probability must have depth logarithmic in n. In contrast, we show that this problem can be solved with certainty by a constantdepth quantum circuit composed of one and twoqubit gates acting locally on a twodimensional grid.
 S. Bravyi, M. Englbrecht, R. König and N. Peard. Correcting coherent
errors with surface codes. npj Quantum Information, vol. 4, no. 55,
October 2018. arXiv
We study how well topological quantum codes can tolerate coherent noise caused by systematic unitary errors such as unwanted Zrotations. Our main result is an efficient algorithm for simulating quantum error correction protocols based on the 2D surface code in the presence of coherent errors. The algorithm has runtime O(n^{2}), where n is the number of physical qubits. It allows us to simulate systems with more than one thousand qubits and obtain the first error threshold estimates for several toy models of coherent noise. Numerical results are reported for storage of logical states subject to Zrotation errors and for logical state preparation with general SU(2) errors. We observe that for large code distances the effective logicallevel noise is wellapproximated by random Pauli errors even though the physicallevel noise is coherent. Our algorithm works by mapping the surface code to a system of Majorana fermions.
 S. Huber and R. König. Coherent state coding approaches the capacity
of nonGaussian bosonic noise channels. J. Phys. A: Math. Theor. 51,
184001, April 2018. arXiv
The additivity problem asks if the use of entanglement can boost the informationcarrying capacity of a given channel beyond what is achievable by coding with simple product states only. This has recently been shown not to be the case for phaseinsensitive onemode Gaussian channels, but remains unresolved in general. Here we consider two general classes of bosonic noise channels, which include phaseinsensitive Gaussian channels as special cases: these are beamsplitters with general, potentially nonGaussian environment states and classical noise channels with general probabilistic noise. We show that additivity violations, if existent, are rather minor for all these channels: the maximal gain in classical capacity is bounded by a constant independent of the input energy. Our proof shows that coding by simple classical modulation of coherent states is close to optimal.
 R. König and V. Scholz. Matrix product approximations to conformal
field theories. Nucl. Phys. B 920, 32–121, July 2017. arXiv
We establish rigorous error bounds for approximating correlation functions of conformal field theories (CFTs) by certain finitedimensional tensor networks. For chiral CFTs, the approximation takes the form of a matrix product state. For full CFTs consisting of a chiral and an antichiral part, the approximation is given by a finitely correlated state. We show that the bond dimension scales polynomially in the inverse of the approximation error and subexponentially in inverse of the minimal distance between insertion points. We illustrate our findings using WessZuminoWitten models, and show that there is a onetoone correspondence between groupcovariant MPS and our approximation.
 F. Hiai, R. König and M. Tomamichel. Generalized LogMajorization and
Multivariate Trace Inequalities. Ann. Hen. Poincare, pp. 123, March 2017.
arXiv
We show that recent multivariate generalizations of the ArakiLiebThirring inequality and the GoldenThompson inequality (Sutter et al. in Commun Math Phys, 2016) for Schatten norms hold more generally for all unitarily invariant norms and certain variations thereof. The main technical contribution is a generalization of the concept of logmajorization which allows us to treat majorization with regard to logarithmic integral averages of vectors of singular values
 M. Idel and R. König. On quantum additive Gaussian noise channels.
Quant. Inf. Comp. 17, no. 4, March 2017. arXiv
We give necessary and sufficient conditions for a Gaussian quantum channel to have a dilation involving a passive, i.e., nu mberpreserving unitary. We then establish a normal form of such channels: any passively dilatable channel is the result of applying passive unitaries to the input and output of a Gaussian additive channel. The latter combine the state of the system with that of the environment by means of a multimode beamsplitter.
 S. Huber, R. König and A. Vershynina. Geometric inequalities from phase
space translations. J. Math. Phys. 58, 012206, January 2017. arXiv
We establish a quantum version of the classical isoperimetric inequality relating the Fisher information and the entropy power of a quantum state. The key tool is a Fisher information inequality for a state which results from a certain convolution operation: the latter maps a classical probability distribution on phase space and a quantum state to a quantum state. We show that this inequality also gives rise to several related inequalities whose counterparts are wellknown in the classical setting: in particular, it implies an entropy power inequality for the mentioned convolution operation as well as the isoperimetric inequality and establishes concavity of the entropy power along trajectories of the quantum heat diffusion semigroup. As an application, we derive a LogSobolev inequality for the quantum OrnsteinUhlenbeck semigroup and argue that it implies fast convergence towards the fixed point for a large class of initial states.
 R. König and V. Scholz. Matrix product approximations to multipoint
functions in twodimensional conformal field theory. Phys. Rev. Lett.
117, 121601, September 2016. arXiv
Matrix product states (MPS) illustrate the suitability of tensor networks for the description of interacting manybody systems: ground states of gapped 1D systems are approximable by MPS as shown by Hastings [J. Stat. Mech. Theor. Exp., P08024 (2007)]. In contrast, whether MPS and more general tensor networks can accurately reproduce correlations in critical quantum systems, respectively quantum field theories, has not been established rigorously. Ample evidence exists: entropic considerations provide restrictions on the form of suitable Ansatz states, and numerical studies show that certain tensor networks can indeed approximate the associated correlation functions. Here we provide a complete positive answer to this question in the case of MPS and 2D conformal field theory: we give quantitative estimates for the approximation error when approximating correlation functions by MPS. Our work is constructive and yields an explicit MPS, thus providing both suitable initial values as well as a rigorous justification of variational methods.
 X. Ni, F. Pastawski, B. Yoshida and R. König. Preparing topologically
ordered states by Hamiltonian interpolation. New Journal of Physics, 18,
093027, September 2016. arXiv
We study the preparation of topologically ordered states by interpolating between an initial Hamiltonian with a unique product ground state and a Hamiltonian with a topologically degenerate ground state space. By simulating the dynamics for small systems, we numerically observe a certain stability of the prepared state as a function of the initial Hamiltonian. For small systems or long interpolation times, we argue that the resulting state can be identified by computing suitable effective Hamiltonians. For effective anyon models, this analysis singles out the relevant physical processes and extends the study of the splitting of the topological degeneracy by Bonderson. We illustrate our findings using Kitaev’s Majorana chain, effective anyon chains, the toric code and LevinWen stringnet models.
 M. E. Beverland, O. Buerschaper, R. König, F. Pastawski, J. Preskill and S.
Sijher. Protected gates for topological quantum field theories.
Journal of Mathematical Physics, 57, 022201, February 2016. arXiv
We study restrictions on localitypreserving unitary logical gates for topological quantum codes in two spatial dimensions. A localitypreserving operation is one which maps local operators to local operators for example, a constantdepth quantum circuit of geometrically local gates, or evolution for a constant time governed by a geometrically local boundedstrength Hamiltonian. Localitypreserving logical gates of topological codes are intrinsically fault tolerant because spatially localized errors remain localized, and hence sufficiently dilute errors remain correctable. By invoking general properties of twodimensional topological field theories, we find that the localitypreserving logical gates are severely limited for codes which admit nonabelian anyons, in particular, there are no localitypreserving logical gates on the torus or the sphere with M punctures if the braiding of anyons is computationally universal. Furthermore, for Ising anyons on the Mpunctured sphere, localitypreserving gates must be elements of the logical Pauli group. We derive these results by relating logical gates of a topological code to automorphisms of the Verlinde algebra of the corresponding anyon model, and by requiring the logical gates to be compatible with basis changes in the logical Hilbert space arising from local Fmoves and the mapping class group.
 R. König. The conditional entropy power inequality for Gaussian
quantum states. Journal of Mathematical Physics, 55, 022201, February
2015. arXiv
We propose a generalization of the quantum entropy power inequality involving conditional entropies. For the special case of Gaussian states, we give a proof based on perturbation theory for symplectic spectra. We discuss some implications for entanglementassisted classical communication over additive bosonic noise channels.
 R. König and J. Smolin. How to efficiently select an arbitrary Clifford
group element. Journal of Mathematical Physics, 55, 122202, December 2014.
arXiv
We give an algorithm which produces a unique element of the Clifford group C_{n} on n qubits from an integer 0 ≤ i < C_{n} (the number of elements in the group). The algorithm involves O(n^{3}) operations. It is a variant of the subgroup algorithm by Diaconis and Shahshahani which is commonly applied to compact Lie groups. We provide an adaption for the symplectic group Sp(2n,F_{2}) which provides, in addition to a canonical mapping from the integers to group elements g, a factorization of g into a sequence of at most 4n symplectic transvections. The algorithm can be used to efficiently select randomelements of C_{n} which is often useful in quantum information theory and quantum computation. We also give an algorithm for the inverse map, indexing a group element in time O(n^{3}).
 R. König and F. Pastawski. Generating topological order: no speedup
by dissipation. Physical Review B, 90, 045101, July 2014. arXiv
We consider the problem of converting a product state to a ground state of a topologically ordered system through a locally generated opensystem dynamic. Employing quantuminformation tools, we show that such a conversion takes an amount of time proportional to the diameter of the system. Our result applies to typical twodimensional topologically ordered systems as well as, for example, the threedimensional and fourdimensional toric codes. It is tight for the toric code, giving a scaling with the linear system size. Our results have immediate operational implications for the preparation of topologically ordered states, a crucial ingredient for topological quantum computation: Dissipation cannot provide any significant speedup compared to unitary evolution.
 R. König and G. Smith. The entropy power inequality for quantum
systems. IEEE Transactions on Information Theory, vol. 60, no. 3,
pp. 1536–1548, March 2014. arXiv
When two independent analog signals, X and Y are added together giving Z = X+Y , the entropy of Z, H(Z), is not a simple function of the entropies H(X) and H(Y ), but rather depends on the details of X and Y’s distributions. Nevertheless, the entropy power inequality (EPI), which states that exp[2H(Z)] ≥ exp[2H(X)] + exp[2H(Y )], gives a very tight restriction on the entropy of Z. This inequality has found many applications in information theory and statistics. The quantum analogue of adding two random variables is the combination of two independent bosonic modes at a beam splitter. The purpose of this work is to give a detailed outline of the proof of two separate generalizations of the entropy power inequality to the quantum regime. Our proofs are similar in spirit to standard classical proofs of the EPI, but some new quantities and ideas are needed in the quantum setting. Specifically, we find a new quantum de Bruijin identity relating entropy production under diffusion to a divergencebased quantum Fisher information. Furthermore, this Fisher information exhibits certain convexity properties in the context of beam splitters.
 J. Dengis, R. König and F. Pastawski. An optimal dissipative encoder for
the toric code. New Journal of Physics, 16, 013023, October 2013. arXiv
We consider the problem of preparing specific encoded resource states for the toric code by local, timeindependent interactions with a memoryless environment. We propose a construction of such a dissipative encoder which converts product states to topologically ordered ones while preserving logical information. The corresponding Liouvillian is made up of fourlocal Lindblad operators. For a qubit lattice of size L×L, we show that this process prepares encoded states in time O(L), which is optimal. This scaling compares favorably with known local unitary encoders for the toric code which take time of order Ω(L^{2}) and require active timedependent control.
 S. Bravyi and R. König. Classification of topologically protected gates
for local stabilizer codes. Physical Review Letters, vol. 110, no. 170503,
April 2013. arXiv
Given a quantum error correcting code, an important task is to find encoded operations that can be implemented efficiently and faulttolerantly. In this Letter we focus on topological stabilizer codes and encoded unitary gates that can be implemented by a constantdepth quantum circuit. Such gates have a certain degree of protection since propagation of errors in a constantdepth circuit is limited by a constant size light cone. For the 2D geometry we show that constantdepth circuits can only implement a finite group of encoded gates known as the Clifford group. This implies that topological protection must be ”turned off” for at least some steps in the computation in order to achieve universality. For the 3D geometry we show that an encoded gate U is implementable by a constantdepth circuit only if the image of any Pauli operator under conjugation by U belongs to the Clifford group. This class of gates includes some nonClifford gates such as the π∕8 rotation. Our classification applies to any stabilizer code with geometrically local stabilizers and sufficiently large code distance.
 R. König and G. Smith. The classical capacity of quantum thermal
noise channels to within 1.45 bits. Physical Review Letters, vol. 110,
no. 040501, January 2013. arXiv
We find a tight upper bound for the classical capacity of quantum thermal noise channels that is within 1∕ ln 2 bits of Holevo’s lower bound. This lower bound is achievable using unentangled, classical signal states, namely displaced coherent states. Thus, we find that while quantum tricks might offer benefits, when it comes to classical communication they can only help a bit.
 R. König and G. Smith. Limits on classical communication from
quantum entropy power inequalities. Nature Photonics, vol. 7,
pp. 140–146, January 2012. arXiv
Almost all modern communication systems rely on electromagnetic fields as a means of information transmission, and finding the capacities of these systems is a problem of significant practical importance. The Additive White Gaussian Noise (AWGN) channel is often a good approximate description of such systems, and its capacity is given by a simple formula. However, when quantum effects are important, estimating the capacity becomes difficult: a lower bound is known, but a similar upper bound is missing. We present strong new upper bounds for the classical capacity of quantum additive noise channels, including quantum analogues of the AWGN channel. Our main technical tool is a quantum entropy power inequality that controls the entropy production as two quantum signals combine at a beam splitter. Its proof involves a new connection between entropy production rates and a quantum Fisher information, and uses a quantum diffusion that smooths arbitrary states towards gaussians.
 S. Bravyi and R. König. Classical simulation of dissipative fermionic
linear optics. Quantum Information and Computation, vol. 12, pp. 925–943,
November 2012. arXiv
Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of available computational gates: in addition to unitaries and measurements, we allow dissipative evolution governed by a Markovian master equation with linear Lindblad operators. We show that this more general form of fermionic computation is also simulable efficiently by classical means. Given a system of N fermionic modes, our algorithm simulates any such gate in time O(N^{3}) while a singlemode measurement is simulated in time O(N^{2}). The steady state of the Lindblad equation can be computed in time O(N^{3}).
 S. Bravyi and R. König. Disorderassisted error correction in Majorana
chains. Communications in Mathematical Physics, vol. 361, pp. 641–692,
October 2012. arXiv
It was recently realized that quenched disorder may enhance the reliability of topological qubits by reducing the mobility of anyons at zero temperature. Here we compute storage times with and without disorder for quantum chains with unpaired Majorana fermions  the simplest toy model of a quantum memory. Disorder takes the form of a random sitedependent chemical potential. The corresponding oneparticle problem is a onedimensional Anderson model with disorder in the hopping amplitudes. We focus on the zerotemperature storage of a qubit encoded in the ground state of the Majorana chain. Storage and retrieval are modeled by a unitary evolution under the memory Hamiltonian with an unknown weak perturbation followed by an errorcorrection step. Assuming dynamical localization of the oneparticle problem, we show that the storage time grows exponentially with the system size. We give supporting evidence for the required localization property by estimating Lyapunov exponents of the oneparticle eigenfunctions. We also simulate the storage process for chains with a few hundred sites. Our numerical results indicate that in the absence of disorder, the storage time grows only as a logarithm of the system size. We provide numerical evidence for the beneficial effect of disorder on storage times and show that suitably chosen pseudorandom potentials can outperform random ones.
 R. König, S. Wehner and J. Wullschleger. Unconditional security from
noisy quantum storage. IEEE Transactions on Information Theory, vol. 58,
no. 3, pp. 1962 1984, March 2012. arXiv
We consider the implementation of twoparty cryptographic primitives based on the sole assumption that no largescale reliable quantum storage is available to the cheating party. We construct novel protocols for oblivious transfer and bit commitment, and prove that realistic noise levels provide security even against the most general attack. Such unconditional results were previously only known in the socalled boundedstorage model which is a special case of our setting. Our protocols can be implemented with presentday hardware used for quantum key distribution. In particular, no quantum storage is required for the honest parties.
 S. Beigi and R. König. Simplified instantaneous nonlocal quantum
computation with applications to positionbased cryptography. New
Journal of Physics, vol. 13, 093036, September 2011. arXiv
Instantaneous measurements of nonlocal observables between spacelike separated regions can be performed without violating causality. This feat relies on the use of entanglement. Here we propose novel protocols for this task and the related problem of multipartite quantum computation with local operations and a single round of classical communication. Compared to previously known techniques, our protocols reduce the entanglement consumption by an exponential amount. We also prove a linear lower bound on the amount of entanglement required for the implementation of a certain nonlocal measurement. These results relate to positionbased cryptography: an amount of entanglement scaling exponentially in the number of communicated qubits is sufficient to render any such scheme insecure. Furthermore, we show that certain schemes are secure under the assumption that the adversary has less entanglement than a given linear bound and is restricted to classical communication.
 R. König and R. Renner. Sampling of minentropy relative to quantum
knowledge. IEEE Transactions on Information Theory, vol. 57, no. 7,
pp. 4760–4787, July 2011. arXiv
Let X_{1},…,X_{n} be a sequence of n classical random variables and consider a sample of r positions selected at random. Then, except with (exponentially in r) small probability, the minentropy of the sample is not smaller than, roughly, a fraction r∕n of the total minentropy of all positions X_{1},…,X_{n}, which is optimal. Here, we show that this statement, originally proven by Vadhan [LNCS, vol. 2729, Springer, 2003] for the purely classical case, is still true if the minentropy is measured relative to a quantum system. Because minentropy quantifies the amount of randomness that can be extracted from a given random variable, our result can be used to prove the soundness of locally computable extractors in a context where side information might be quantummechanical. In particular, it implies that key agreement in the boundedstorage model (using a standard sampleandhash protocol) is fully secure against quantum adversaries, thus solving a longstanding open problem.
 R. König, G. Kuperberg and B. Reichardt. Quantum computation with
TuraevViro codes. Annals of Physics, vol. 325, no. 12, pp. 2707–2749,
December 2010. arXiv
The TuraevViro invariant for a closed 3manifold is defined as the contraction of a certain tensor network. The tensors correspond to tetrahedra in a triangulation of the manifold, with values determined by a fixed spherical category. For a manifold with boundary, the tensor network has free indices that can be associated to qudits, and its contraction gives the coefficients of a quantum errorcorrecting code. The code has local stabilizers determined by Levin and Wen. For example, applied to the genusone handlebody using the ℤ_{2} category, this construction yields the wellknown toric code. For other categories, such as the Fibonacci category, the construction realizes a nonabelian anyon model over a discrete lattice. By studying braid group representations acting on equivalence classes of colored ribbon graphs embedded in a punctured sphere, we identify the anyons, and give a simple recipe for mapping fusion basis states of the doubled category to ribbon graphs. We explain how suitable initial states can be prepared efficiently, how to implement braids, by successively changing the triangulation using a fixed fivequdit local unitary gate, and how to measure the topological charge. Combined with known universality results for anyonic systems, this provides a large family of schemes for quantum computation based on local deformations of stabilizer codes. These schemes may serve as a starting point for developing faulttolerance schemes using continuous stabilizer measurements and active errorcorrection.
 G. Alagic, S. Jordan, R. König and B. Reichardt. Approximating
TuraevViro 3manifold invariants is universal for quantum
computation. Phys. Rev. A 81, 052309 (R), October 2010. arXiv
The TuraevViro invariants are scalar topological invariants of compact, orientable 3manifolds. We give a quantum algorithm for additively approximating TuraevViro invariants of a manifold presented by a Heegaard splitting. The algorithm is motivated by the relationship between topological quantum computers and (2 + 1) − D topological quantum field theories. Its accuracy is shown to be nontrivial, as the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer. Thus approximating certain TuraevViro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation. This establishes a novel relation between the task of distinguishing nonhomeomorphic 3manifolds and the power of a general quantum computer.
 R. König and E. Bilgin. Anyonic entanglement renormalization. Phys.
Rev. B 82, 125118, September 2010. arXiv
We introduce a family of variational ansatz states for chains of anyons which optimally exploits the structure of the anyonic Hilbert space. This ansatz is the natural analog of the multiscale entanglement renormalization ansatz for spin chains. In particular, it has the same interpretation as a coarsegraining procedure and is expected to accurately describe critical systems with algebraically decaying correlations. We numerically investigate the validity of this ansatz using the anyonic golden chain and its relatives as a testbed. This demonstrates the power of entanglement renormalization in a setting with nonabelian exchange statistics, extending previous work on qudits, bosons and fermions in two dimensions.
 R. König. Composite anyon coding and the initialization of a
topological quantum computer. Phys. Rev. A 81, 052309, May 2010. arXiv
Schemes for topological quantum computation are usually based on the assumption that the system is initially prepared in a specific state. In practice, this state preparation is expected to be challenging as it involves nontopological operations which heavily depend on the experimental realization and are not naturally robust against noise. Here we show that this assumption can be relaxed by using composite anyons: starting from an unknown state with reasonable physical properties, it is possible to efficiently distill suitable initial states for computation purely by braiding. This is achieved by encoding logical information in a subsystem code with gauge system corresponding to the internal degrees of freedom of composite objects.
 R. König. Simplifying quantum double Hamiltonians using
perturbative gadgets. Quantum Information and Computation, vol. 10, no. 3,
pp. 292324, March 2010. arXiv
Perturbative gadgets were originally introduced to generate effective klocal interactions in the lowenergy sector of a 2local Hamiltonian. Extending this idea, we present gadgets which are specifically suited for realizing Hamiltonians exhibiting nonabelian anyonic excitations. At the core of our construction is a perturbative analysis of a widely used hoppingterm Hamiltonian. We show that in the lowenergy limit, this Hamiltonian can be approximated by a certain ordered product of operators. In particular, this provides a simplified realization of Kitaev’s quantum double Hamiltonians.
 R. König and S. Wehner. A strong converse for classical channel coding
using entangled inputs. Phys. Rev. Lett. 103, 070504, August 2009. arXiv
A fully general strong converse for channel coding states that when the rate of sending classical information exceeds the capacity of a quantum channel, the probability of correctly decoding goes to zero exponentially in the number of channel uses, even when we allow code states which are entangled across several uses of the channel. Such a statement was previously only known for classical channels and the quantum identity channel. By relating the problem to the additivity of minimum output entropies, we show that a strong converse holds for a large class of channels, including all unital qubit channels, the ddimensional depolarizing channel and the WernerHolevo channel. This further justifies the interpretation of the classical capacity as a sharp threshold for informationtransmission.
 R. König, R. Renner and C. Schaffner. The operational meaning of min
and maxentropy. IEEE Transactions on Information Theory, vol. 55, no. 9,
pp. 43374347, September 2009. arXiv
We show that the conditional minentropy H_{min}(AB) of a bipartite state ρ_{AB} is directly related to the maximum achievable overlap with a maximally entangled state if only local actions on the Bpart of ρ_{AB} are allowed. In the special case where A is classical, this overlap corresponds to the probability of guessing A given B. In a similar vein, we connect the conditional maxentropy H_{max}(AB) to the maximum fidelity of ρ_{AB} with a product state that is completely mixed on A. In the case where A is classical, this corresponds to the security of A when used as a secret key in the presence of an adversary holding B. Because min and maxentropies are known to characterize informationprocessing tasks such as randomness extraction and state merging, our results establish a direct connection between these tasks and basic operational problems. For example, they imply that the (logarithm of the) probability of guessing A given B is a lower bound on the number of uniform secret bits that can be extracted from A relative to an adversary holding B.
 R. König, B. Reichardt and G. Vidal. Exact entanglement renormalization
for stringnet models. Phys. Rev. B 79, 195123, May 2009. arXiv
We construct an explicit renormalization group (RG) transformation for Levin and Wen’s stringnet models on a hexagonal lattice. The transformation leaves invariant the groundstate ”fixedpoint” wave function of the stringnet condensed phase. Our construction also produces an exact representation of the wave function in terms of the multiscale entanglement renormalization ansatz (MERA). This sets the stage for efficient numerical simulations of stringnet models using MERA algorithms. It also provides an explicit quantum circuit to prepare the stringnet groundstate wave function using a quantum computer.
 R. König and G. Mitchison. A most compendious and facile quantum de
Finetti theorem. J. Math. Phys. 50, 012105, January 2009. arXiv
In its most basic form, the finite quantum de Finetti theorem states that the reduced kpartite density operator of an npartite symmetric state can be approximated by a convex combination of kfold product states. Variations of this result include Renner’s “exponential” approximation by “almostproduct” states, a theorem which deals with certain triples of representations of the unitary group, and D’Cruz et al.’s result for infinitedimensional systems. We show how these theorems follow from a single, general de Finetti theorem for representations of symmetry groups, each instance corresponding to a particular choice of symmetry group and representation of that group. This gives some insight into the nature of the set of approximating states, and leads to some new results, including an exponential theorem for infinitedimensional systems.
 M. Christandl, R. König and R. Renner. Postselection technique for
quantum channels with applications to quantum cryptography. Phys.
Rev. Lett. 102, 020504, January 2009. arXiv
We propose a general method for studying properties of quantum channels acting on an npartite system, whose action is invariant under permutations of the subsystems. Our main result is that, in order to prove that a certain property holds for any arbitrary input, it is sufficient to consider the special case where the input is a particular de Finettitype state, i.e., a state which consists of n identical and independent copies of an (unknown) state on a single subsystem. A similar statement holds for more general channels which are covariant with respect to the action of an arbitrary finite or locally compact group.
Our technique can be applied to the analysis of informationtheoretic problems. For example, in quantum cryptography, we get a simple proof for the fact that security of a discretevariable quantum key distribution protocol against collective attacks implies security of the protocol against the most general attacks. The resulting security bounds are tighter than previously known bounds obtained by proofs relying on the exponential de Finetti theorem [Renner, Nature Physics 3,645(2007)].  R. König and M. Wolf. On Exchangeable Continuous Variable Systems.
J. Math. Phys. 50, 012102, January 2009. arXiv
We investigate permutationinvariant continuous variable quantum states and their covariance matrices. We provide a complete characterization of the latter with respect to permutationinvariance, exchangeability and representing convex combinations of tensor power states. On the level of the respective density operators this leads to necessary criteria for all these properties which become necessary and sufficient for Gaussian states. For these we use the derived results to provide de Finettitype theorems for various distance measures.
 R. König and B. Terhal. The Bounded Storage Model in The Presence
of a Quantum Adversary. IEEE Transactions on Information Theory,
vol. 54, no. 7, pp. 749–762, February 2008. arXiv
An extractor is a function E that is used to extract randomness. Given an imperfect random source X and a uniform seed Y, the output E(X,Y) is close to uniform. We study properties of such functions in the presence of prior quantum information about X, with a particular focus on cryptographic applications. We prove that certain extractors are suitable for key expansion in the bounded storage model where the adversary has a limited amount of quantum memory. For extractors with onebit output we show that the extracted bit is essentially equally secure as in the case where the adversary has classical resources. We prove the security of certain constructions that output multiple bits in the bounded storage model.
 M. Christandl, R. König, G. Mitchison and R. Renner. 1 1/2 de Finetti
Theorems. Comm. Math. Phys., 273 (2), 473–498, July 2007. arXiv
We prove a new kind of quantum de Finetti theorem for representations of the unitary group U(d). Consider a pure state that lies in the irreducible representation U_{μ+ν} for Young diagrams μ and ν. U_{μ+ν} is contained in the tensor product of U_{μ} and U_{ν}; let ξ be the state obtained by tracing out U_{ν}. We show that ξ is close to a convex combination of states Uv, where U is in U(d) and v is the highest weight vector in U_{μ}. When U_{μ+ν} is the symmetric representation, this yields the conventional quantum de Finetti theorem for symmetric states, and our method of proof gives nearoptimal bounds for the approximation of ξ by a convex combination of product states. For the class of symmetric Werner states, we give a second de Finettistyle theorem (our ’half’ theorem); the de Finettiapproximation in this case takes a particularly simple form, involving only product states with a fixed spectrum. Our proof uses purely group theoretic methods, and makes a link with the shifted Schur functions. It also provides some useful examples, and gives some insight into the structure of the set of convex combinations of product states.
 R. König, R. Renner, A. Bariska and U. Maurer. Small Accessible Quantum
Information Does Not Imply Security. Phys. Rev. Lett. 98, 140502, April
2007. arXiv
The unconditional security of a quantum key distribution protocol is often defined in terms of the accessible information, that is, the maximum mutual information between the distributed key S and the outcome of an optimal measurement on the adversary’s (quantum) system. We show that, even if this quantity is small, certain parts of the key S might still be completely insecure when S is used in applications, such as for onetime pad encryption. This flaw is due to a locking property of the accessible information: one additional (physical) bit of information might increase the accessible information by more than one bit.
 R. König and R. Renner. A de Finetti Representation for Finite
Symmetric Quantum States. J. Math. Phys. 46, 122108, December 2005.
arXiv
Consider a symmetric quantum state on an nfold product space, that is, the state is invariant under permutations of the n subsystems. We show that, conditioned on the outcomes of an informationally complete measurement applied to a number of subsystems, the state in the remaining subsystems is close to having product form. This immediately generalizes the socalled de Finetti representation to the case of finite symmetric quantum states.
 R. König, U. Maurer and R. Renner. On the Power of Quantum
Memory. IEEE Transactions on Information Theory, vol. 51, no. 7, pp.
23912401, July 2005. arXiv
We address the question whether quantum memory is more powerful than classical memory. In particular, we consider a setting where information about a random nbit string X is stored in r classical or quantum bits, for r < n, i.e., the stored information is bound to be only partial. Later, a randomly chosen binary question F about X is asked, which has to be answered using only the stored information. The maximal probability of correctly guessing the answer F(X) is then compared for the cases where the storage device is classical or quantum mechanical, respectively. We show that, despite the fact that the measurement of quantum bits can depend arbitrarily on the question F to be answered, the quantum advantage is negligible already for small values of the difference n − r. An implication for cryptography is that privacy amplification by application of a compression function mapping nbit strings to sbit strings (for some s < n − r), chosen publicly from a twouniversal class of hash functions, remains essentially equally secure when the adversary’s memory is allowed to be r quantum rather than only r classical bits.
Other publications
 L. Hänggli, M. Heinze and R. König. Enhanced noise resilience of the surfaceGKP code via designed bias. arXiv
 S. Bravyi, A. Kliesch, R. König and E. Tang. Obstacles to State Preparation and Variational Optimization from Symmetry Protection. arXiv.
 R. König, U. Maurer and S. Tessaro. Abstract Storage Devices, SOSFEM 2009: Theory and Practice of Computer Science, Lecture Notes in Computer Science, Springer, vol. 5404, pp. 341352.
 R. König. de Finetti theorems for Quantum States. PhD thesis, University of Cambridge, 2007.
 R. König. de Finetti theorems and extractors: grouptheoretic and combinatorial tools for quantum information processing. First year report/essay, University of Cambridge, 2007.
 R. König and U. Maurer. Generalized Strong Extractors and Deterministic Privacy Amplification. Cryptography and Coding 2005, Lecture Notes in Computer Science, Springer, vol. 3796, pp. 322–339.
 R. Renner and R. König. Universally composable privacy amplification against quantum adversaries. Theory of Cryptography 2005, Lecture Notes in Computer Science, Springer, Springer, vol. 3378, pp. 407–425. arXiv
 R. König, U. Maurer and R. Renner. Privacy Amplification Secure Against an Adversary with Selectable Knowledge. In Proceedings of 2004 IEEE International Symposium on Information Theory, 2004.
 R. König and U. Maurer. Extracting Randomness From Generalized Symbolfixing and Markov Sources. In Proceedings of 2004 IEEE International Symposium on Information Theory, 2004.
 R. König. On the Capacity of Quantum Memory. Diploma Thesis in theoretical physics at ETH Zurich, 2003.
Current funding
 Quantum Code Design and Architecture, QuantERA
 Quantum Science and Technology, DFG Cluster of Excellence
 Quantum Science and Technology, International Max Planch Research School
CV
01/2015   assistant professor  Institute for Advanced Study and & Zentrum Mathematik, Technische Universität München 
08/2012  12/2014  assistant professor  Department of Applied Mathematics and Institute for Quantum Computing, University of Waterloo 
06/2011  06/2012  postdoctoral researcher  Physics of Information/Quantum Information group, IBM Watson Research Center 
11/2007  05/2011  postdoctoral researcher  Institute for Quantum Information, California Institute of Technology (supported by an SNF fellowship starting 11/2009) 
2005  2007  Ph.D.  Department of Applied Mathematics and Theoretical Physics, University of Cambridge, UK 
2003  2005  research and teaching assistant  Institute for Theoretical Computer Science, Swiss Federal Institute of Technology (ETH), Zurich 
1998  2003  diploma (MSc.)  Theoretical Physics, ETH Zurich 