BannerHauptseite TUMHauptseite LehrstuhlMathematik SchriftzugHauptseite LehrstuhlHauptseite Fakultät

Prof. Dr. Robert König



Zentrum Mathematik, M5
Technische Universität München
Boltzmannstrasse 3
85748 Garching

Büro: 03.12.039
Tel.: +49 89 289-17042
E-Mail: robert.koenigemattum.de

We are hiring! Postdoctoral positions available.

Teaching

Research interests

  • Quantum communication theory
  • Fault-tolerant quantum information processing
  • Quantum computation
  • Many-body physics and variational methods

Publications

  [Show/hide figures]
  [Show/hide abstracts]
  • 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

    PIC

    As increasingly sophisticated prototypes of quantum computers are being developed, a pressing challenge is to find computational problems that can be solved by an intermediate-scale 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 (so-called 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 one-dimensional 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

    PIC

    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 coarse-graining maps yielding discontinuous representations has full measure in the set of all isometries. This extends Jones’ no-go example to typical elements of the so-called 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

    PIC

    Prior work has shown that there exists a relation problem which can be solved with certainty by a constant-depth 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 fan-in gates. Here we provide two extensions of this result. Firstly, we show that a separation in computational power persists even when the constant-depth 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 constant-depth 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 noise-free classical circuit of constant depth. A key component of the proof is a quantum error-correcting code which admits constant-depth logical Clifford gates and single-shot logical state preparation. We show that the surface code meets these criteria. To this end, we provide a protocol for single-shot 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 Haar-random tensor networks. Journal of Physics A: Mathematical and Theoretical, vol. 52, no 425303, September 2019. arXiv

    PIC

    We provide a computer algebra package called Random Tensor Network Integrator (RTNI). It allows to compute averages of tensor networks containing multiple Haar-distributed 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 Error-Detection at Low Energies. Journal of High Energy Physics vol. 2019, no. 21, September 2019. arXiv

    Motivated by the close relationship between quantum error-correction, topological order, the holographic AdS/CFT duality, and tensor networks, we initiate the study of approximate quantum error-detecting codes in matrix product states (MPS). We first show that using open-boundary MPS to define boundary to bulk encoding maps yields at most constant distance error-detecting codes. These are degenerate ground spaces of gapped local Hamiltonians. To get around this no-go result, we consider excited states, i.e., we use the excitation ansatz to construct encoding maps: these yield error-detecting codes with distance Ω(n1ν) for any ν (0, 1) for any ν (0, 1) and Ω(log n) encoded qubits. This shows that gapped systems contain – within isolated energy bands – error-detecting codes spanned by momentum eigenstates. We also consider the gapless Heisenberg-XXX model, whose energy eigenstates can be described via Bethe ansatz tensor networks. We show that it contains – within its low-energy eigenspace – an error-detecting code with the same parameter scaling. All these codes detect arbitrary d-local (not necessarily geometrically local) errors even though they are not permutation-invariant. This suggests that a wide range of naturally occurring many-body systems possess intrinsic error-detecting features.

  • M. Heinze and R. König. Universal Uhrig Dynamical Decoupling for Bosonic Systems. Physical Review Letters,vol. 123, no. 010501, July 2019. arXiv

    PIC

    We construct efficient deterministic dynamical decoupling schemes protecting continuous variable degrees of freedom. Our schemes target decoherence induced by quadratic system-bath interactions with analytic time-dependence. We show how to suppress such interactions to N-th order using only N pulses. Furthermore, we show to homogenize a 2m-mode bosonic system using only (N + 1)2m+1 pulses, yielding - up to N-th order – an effective evolution described by non-interacting harmonic oscillators with identical frequencies. The decoupled and homogenized system provides natural decoherence-free subspaces for encoding quantum information. Our schemes only require pulses which are tensor products of single-mode 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

    PIC

    We propose a branch-and-bound algorithm for minimizing a bilinear functional of the form f(X,Y ) = tr((X ⊗Y )Q )+ tr(AX) + tr(BY ), of pairs of Hermitian matrices (X,Y ) restricted by joint semidefinite programming constraints. The functional is parametrized by self-adjoint 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 many-body 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 2-local 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 λmax9. 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 Hartree-Fock method. We give a simple family of Hamiltonians for which Gaussian states and Slater determinants approximate λmax within a fraction 1 O(n1) and O(n1) respectively.

  • S. Bravyi, D. Gosset and R. König. Quantum advantage with shallow circuits. Science Vol. 362, Issue 6412, pp. 308-311, October 2018. arXiv

    PIC

    We prove that constant-depth quantum circuits are more powerful than their classical counterparts. To this end we introduce a non-oracular version of the Bernstein-Vazirani problem which we call the 2D Hidden Linear Function problem. An instance of the problem is specified by a quadratic form q that maps n-bit 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 n-bit strings. We prove that any classical probabilistic circuit composed of bounded fan-in 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 constant-depth quantum circuit composed of one- and two-qubit gates acting locally on a two-dimensional 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

    PIC

    We study how well topological quantum codes can tolerate coherent noise caused by systematic unitary errors such as unwanted Z-rotations. 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(n2), 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 Z-rotation errors and for logical state preparation with general SU(2) errors. We observe that for large code distances the effective logical-level noise is well-approximated by random Pauli errors even though the physical-level 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 non-Gaussian 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 information-carrying 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 phase-insensitive one-mode Gaussian channels, but remains unresolved in general. Here we consider two general classes of bosonic noise channels, which include phase-insensitive Gaussian channels as special cases: these are beamsplitters with general, potentially non-Gaussian 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

    PIC

    We establish rigorous error bounds for approximating correlation functions of conformal field theories (CFTs) by certain finite-dimensional tensor networks. For chiral CFTs, the approximation takes the form of a matrix product state. For full CFTs consisting of a chiral and an anti-chiral 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 sub-exponentially in inverse of the minimal distance between insertion points. We illustrate our findings using Wess-Zumino-Witten models, and show that there is a one-to-one correspondence between group-covariant MPS and our approximation.

  • F. Hiai, R. König and M. Tomamichel. Generalized Log-Majorization and Multivariate Trace Inequalities. Ann. Hen. Poincare, pp. 1-23, 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 log-majorization 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

    PIC

    We give necessary and sufficient conditions for a Gaussian quantum channel to have a dilation involving a passive, i.e., nu mber-preserving 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 multi-mode 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 well-known 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 Log-Sobolev inequality for the quantum Ornstein-Uhlenbeck 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 two-dimensional conformal field theory. Phys. Rev. Lett. 117, 121601, September 2016. arXiv

    PIC

    Matrix product states (MPS) illustrate the suitability of tensor networks for the description of interacting many-body systems: ground states of gapped 1-D 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

    PIC

    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 Levin-Wen string-net 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

    PIC

    We study restrictions on locality-preserving unitary logical gates for topological quantum codes in two spatial dimensions. A locality-preserving operation is one which maps local operators to local operators for example, a constant-depth quantum circuit of geometrically local gates, or evolution for a constant time governed by a geometrically local bounded-strength Hamiltonian. Locality-preserving 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 two-dimensional topological field theories, we find that the locality-preserving logical gates are severely limited for codes which admit non-abelian anyons, in particular, there are no locality-preserving 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 M-punctured sphere, locality-preserving 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 F-moves 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

    PIC

    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 entanglement-assisted 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 Cn on n qubits from an integer 0 i < |Cn| (the number of elements in the group). The algorithm involves O(n3) 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,F2) 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 Cn 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(n3).

  • R. König and F. Pastawski. Generating topological order: no speedup by dissipation. Physical Review B, 90, 045101, July 2014. arXiv

    PIC

    We consider the problem of converting a product state to a ground state of a topologically ordered system through a locally generated open-system dynamic. Employing quantum-information tools, we show that such a conversion takes an amount of time proportional to the diameter of the system. Our result applies to typical two-dimensional topologically ordered systems as well as, for example, the three-dimensional and four-dimensional 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 divergence-based 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

    PIC

    We consider the problem of preparing specific encoded resource states for the toric code by local, time-independent 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 four-local 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 Ω(L2) and require active time-dependent 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

    PIC

    Given a quantum error correcting code, an important task is to find encoded operations that can be implemented efficiently and fault-tolerantly. In this Letter we focus on topological stabilizer codes and encoded unitary gates that can be implemented by a constant-depth quantum circuit. Such gates have a certain degree of protection since propagation of errors in a constant-depth circuit is limited by a constant size light cone. For the 2D geometry we show that constant-depth 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 constant-depth circuit only if the image of any Pauli operator under conjugation by U belongs to the Clifford group. This class of gates includes some non-Clifford 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

    PIC

    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(N3) while a single-mode measurement is simulated in time O(N2). The steady state of the Lindblad equation can be computed in time O(N3).

  • S. Bravyi and R. König. Disorder-assisted error correction in Majorana chains. Communications in Mathematical Physics, vol. 361, pp. 641–692, October 2012. arXiv

    PIC

    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 site-dependent chemical potential. The corresponding one-particle problem is a one-dimensional Anderson model with disorder in the hopping amplitudes. We focus on the zero-temperature 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 error-correction step. Assuming dynamical localization of the one-particle 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 one-particle 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 two-party cryptographic primitives based on the sole assumption that no large-scale 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 so-called bounded-storage model which is a special case of our setting. Our protocols can be implemented with present-day 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 non-local quantum computation with applications to position-based cryptography. New Journal of Physics, vol. 13, 093036, September 2011. arXiv

    PIC

    Instantaneous measurements of non-local observables between space-like 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 non-local measurement. These results relate to position-based 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 min-entropy relative to quantum knowledge. IEEE Transactions on Information Theory, vol. 57, no. 7, pp. 4760–4787, July 2011. arXiv

    Let X1,,Xn 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 min-entropy of the sample is not smaller than, roughly, a fraction r∕n of the total min-entropy of all positions X1,,Xn, 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 min-entropy is measured relative to a quantum system. Because min-entropy 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 quantum-mechanical. In particular, it implies that key agreement in the bounded-storage model (using a standard sample-and-hash protocol) is fully secure against quantum adversaries, thus solving a long-standing open problem.

  • R. König, G. Kuperberg and B. Reichardt. Quantum computation with Turaev-Viro codes. Annals of Physics, vol. 325, no. 12, pp. 2707–2749, December 2010. arXiv

    PIC

    The Turaev-Viro invariant for a closed 3-manifold 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 error-correcting code. The code has local stabilizers determined by Levin and Wen. For example, applied to the genus-one handlebody using the 2 category, this construction yields the well-known toric code. For other categories, such as the Fibonacci category, the construction realizes a non-abelian 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 five-qudit 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 fault-tolerance schemes using continuous stabilizer measurements and active error-correction.

  • G. Alagic, S. Jordan, R. König and B. Reichardt. Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation. Phys. Rev. A 81, 052309 (R), October 2010. arXiv

    PIC

    The Turaev-Viro invariants are scalar topological invariants of compact, orientable 3-manifolds. We give a quantum algorithm for additively approximating Turaev-Viro 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 Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation. This establishes a novel relation between the task of distinguishing non-homeomorphic 3-manifolds 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

    PIC

    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 multi-scale entanglement renormalization ansatz for spin chains. In particular, it has the same interpretation as a coarse-graining 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 non-abelian 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

    PIC

    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 non-topological 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. 292-324, March 2010. arXiv

    PIC

    Perturbative gadgets were originally introduced to generate effective k-local interactions in the low-energy sector of a 2-local Hamiltonian. Extending this idea, we present gadgets which are specifically suited for realizing Hamiltonians exhibiting non-abelian anyonic excitations. At the core of our construction is a perturbative analysis of a widely used hopping-term Hamiltonian. We show that in the low-energy 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 d-dimensional depolarizing channel and the Werner-Holevo channel. This further justifies the interpretation of the classical capacity as a sharp threshold for information-transmission.

  • R. König, R. Renner and C. Schaffner. The operational meaning of min- and max-entropy. IEEE Transactions on Information Theory, vol. 55, no. 9, pp. 4337-4347, September 2009. arXiv

    We show that the conditional min-entropy Hmin(A|B) of a bipartite state ρAB is directly related to the maximum achievable overlap with a maximally entangled state if only local actions on the B-part 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 max-entropy Hmax(A|B) 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 max-entropies are known to characterize information-processing 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 string-net models. Phys. Rev. B 79, 195123, May 2009. arXiv

    PIC

    We construct an explicit renormalization group (RG) transformation for Levin and Wen’s string-net models on a hexagonal lattice. The transformation leaves invariant the ground-state ”fixed-point” wave function of the string-net condensed phase. Our construction also produces an exact representation of the wave function in terms of the multi-scale entanglement renormalization ansatz (MERA). This sets the stage for efficient numerical simulations of string-net models using MERA algorithms. It also provides an explicit quantum circuit to prepare the string-net ground-state 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 k-partite density operator of an n-partite symmetric state can be approximated by a convex combination of k-fold product states. Variations of this result include Renner’s “exponential” approximation by “almost-product” states, a theorem which deals with certain triples of representations of the unitary group, and D’Cruz et al.’s result for infinite-dimensional 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 infinite-dimensional systems.

  • M. Christandl, R. König and R. Renner. Post-selection 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 n-partite 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 Finetti-type 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 information-theoretic problems. For example, in quantum cryptography, we get a simple proof for the fact that security of a discrete-variable 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 permutation-invariant continuous variable quantum states and their covariance matrices. We provide a complete characterization of the latter with respect to permutation-invariance, 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 Finetti-type 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 one-bit 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

    PIC

    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 near-optimal bounds for the approximation of ξ by a convex combination of product states. For the class of symmetric Werner states, we give a second de Finetti-style theorem (our ’half’ theorem); the de Finetti-approximation 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 one-time 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 n-fold 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 so-called 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. 2391-2401, 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 n-bit 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 n-bit strings to s-bit strings (for some s < n r), chosen publicly from a two-universal 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 surface-GKP 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. 341-352.
  • R. König. de Finetti theorems for Quantum States. PhD thesis, University of Cambridge, 2007.
  • R. König. de Finetti theorems and extractors: group-theoretic 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 Symbol-fixing 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

CV

12/2020 - associate professor Zentrum Mathematik, Technische Universität München
01/2015 - 11/2020assistant professor Institute for Advanced Study and & Zentrum Mathematik, Technische Universität München
08/2012 - 12/2014assistant professor Department of Applied Mathematics and Institute for Quantum Computing, University of Waterloo
06/2011 - 06/2012postdoctoral researcher Physics of Information/Quantum Information group, IBM Watson Research Center
11/2007 - 05/2011postdoctoral 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 assistantInstitute for Theoretical Computer Science, Swiss Federal Institute of Technology (ETH), Zurich
1998 - 2003 diploma (MSc.) Theoretical Physics, ETH Zurich