- 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)
- Quantum communication theory
- Fault-tolerant quantum information processing
- Topological quantum computation
- Many-body physics and variational methods
- 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 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 Araki–Lieb–Thirring inequality and the Golden–Thompson 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
We give necessary and sufficient conditions for a Gaussian quantum channel to have a dilation involving a passive, i.e., number-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
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
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
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
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 0i < | 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
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
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 x 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
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
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
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
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
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
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
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
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
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 is directly related to the maximum achievable overlap with a maximally entangled state if only local actions on the B-part of 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 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
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
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.
- S. Bravyi, D. Gosset and R. König.
Quantum advantage with shallow circuits. April 2017. 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.
01/2015 - assistant professor Institute for Advanced Study and & Zentrum Mathematik, Technische Universität München 08/2012 - 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
- F. Hiai, R. König and M. Tomamichel.