Complete Insecurity of Quantum Protocols for Classical Two-Party Computation
H. Buhrman; M. Christandl; C. Schaffner
2012
Complete Insecurity of Quantum Protocols for Classical Two-Party Computation
Type
Online Database
Author
H. Buhrman; M. Christandl; C. Schaffner
Year
2012
Abstract
A fundamental task in modern cryptography is the joint computation of a classical deterministic function which has two inputs, one from Alice and one from Bob, such that neither of the two can learn more about the other's input than what is implied by the value of the function (secure two-party computation). In this work we show that any quantum protocol that outputs the result to both parties (two-sided computation) and that is secure against a cheating Bob can be completely broken by a cheating Alice. Whereas it is known that quantum protocols for this task cannot be completely secure, our result implies that even partial security cannot be obtained. Our findings stand in stark contrast to recent works on coin tossing, where interesting quantum mechanical advantages can be obtained, and highlight the limits of cryptography within quantum mechanics. With help of von Neumann's minimax theorem we extend the result to the imperfect case, where the quantum protocol may not work perfectly and may not be perfectly secure.
Detection of Multiparticle Entanglement: Quantifying the Search for Symmetric Extensions
F. G.S.L. Brandao; M. Christandl
2011
Detection of Multiparticle Entanglement: Quantifying the Search for Symmetric Extensions
Type
Online Database
Author
F. G.S.L. Brandao; M. Christandl
Year
2011
Abstract
We provide quantitative bounds on the characterisation of multiparticle separable states by states that have locally symmetric extensions. The bounds are derived from two-particle bounds and relate to recent studies on quantum versions of de Finetti's theorem. We discuss algorithmic applications of our results, in particular a quasipolynomial-time algorithm to decide whether a multiparticle quantum state is separable or entangled (for constant number of particles and constant error in the LOCC or Frobenius norm). Our results provide a theoretical justification for the use of the Search for Symmetric Extensions as a practical test for multiparticle entanglement.
Quantum state tomography is the task of inferring the state of a quantum system by appropriate measurements. Since the frequency distributions of the outcomes obtained from any finite number of measurements will generally deviate from their asymptotic limits, the estimation of the state can never be perfectly accurate, thus requiring the specification of error bounds. Furthermore, the individual reconstruction of matrix elements of the density operator representation of a state may lead to inconsistent results (e.g., operators with negative eigenvalues). Here we introduce a framework for quantum state tomography that enables the computation of accurate and consistent estimates and reliable error bars from a finite set of data and show that these have a well-defined and universal operational significance. The method does not require any prior assumptions about the distribution of the possible states or a specific parametrization of the state space. The resulting error bars are tight, corresponding to the fundamental limits that quantum theory imposes on the precision of measurements. At the same time, the technique is practical and particularly well suited for tomography on systems consisting of a small number of qubits, which are currently in the focus of interest in experimental quantum information science.
A quasipolynomial-time algorithm for the quantum separability problem
F. G.S.L. Brandao; M. Christandl; J. Yard
2011
A quasipolynomial-time algorithm for the quantum separability problem
Type
Conference Proceedings
Author
F. G.S.L. Brandao; M. Christandl; J. Yard
Year of Conference
2011
Conference Name
ACM Symposium on Theory of Computation - STOC 2011
Abstract
We present a quasipolynomial-time algorithm for solving the weak membership problem for the convex set of separable, i.e. non-entangled, bipartite density matrices. The algorithm decides whether a density matrix is separable or whether it is eps-away from the set of the separable states in time exp(O(eps^-2 log |A| log |B|)), where |A| and |B| are the local dimensions, and the distance is measured with either the Euclidean norm, or with the so-called LOCC norm. The latter is an operationally motivated norm giving the optimal probability of distinguishing two bipartite quantum states, each shared by two parties, using any protocol formed by quantum local operations and classical communication (LOCC) between the parties. We also obtain improved algorithms for optimizing over the set of separable states and for computing the ground-state energy of mean-field Hamiltonians. The techniques we develop are also applied to quantum Merlin-Arthur games, where we show that multiple provers are not more powerful than a single prover when the verifier is restricted to LOCC protocols, or when the verification procedure is formed by a measurement of small Euclidean norm. This answers a question posed by Aaronson et al (Theory of Computing 5, 1, 2009) and provides two new characterizations of the complexity class QMA, a quantum analog of NP. Our algorithm uses semidefinite programming to search for a symmetric extension, as first proposed by Doherty, Parrilo and Spedialieri (Phys. Rev. A, 69, 022308, 2004). The bound on the runtime follows from an improved de Finetti-type bound quantifying the monogamy of quantum entanglement, proved in (arXiv:1010.1750). This result, in turn, follows from a new lower bound on the quantum conditional mutual information and the entanglement measure squashed entanglement.
Nonvanishing of Kronecker coefficients for rectangular shapes
P. Buergisser; M. Christandl; C. Ikenmeyer
2011
Nonvanishing of Kronecker coefficients for rectangular shapes
Type
Journal Article
Author
P. Buergisser; M. Christandl; C. Ikenmeyer
Year
2011
Journal
Advances in Mathematics
Abstract
We prove that for any partition $(\lambda_1,...,\lambda_{d^2})$ of size $\ell d$ there exists $k\ge 1$ such that the tensor square of the irreducible representation of the symmetric group $S_{k\ell d}$ with respect to the rectangular partition $(k\ell,...,k\ell)$ contains the irreducible representation corresponding to the stretched partition $(k\lambda_1,...,k\lambda_{d^2})$. We also prove a related approximate version of this statement in which the stretching factor $k$ is effectively bounded in terms of $d$. This investigation is motivated by questions of geometric complexity theory.
The Quantum Reverse Shannon Theorem based on One-Shot Information Theory
M. Berta; M. Christandl; R. Renner
2011
The Quantum Reverse Shannon Theorem based on One-Shot Information Theory
Type
Journal Article
Author
M. Berta; M. Christandl; R. Renner
Year
2011
Journal
Communications in Mathematical Physics
Abstract
The Quantum Reverse Shannon Theorem states that any quantum channel can be simulated by an unlimited amount of shared entanglement and an amount of classical communication equal to the channel’s entanglement assisted classical capacity. In this paper, we provide a new proof of this theorem, which has previously been proved by Bennett, Devetak, Harrow, Shor, and Winter. Our proof has a clear structure being based on two recent information-theoretic results: one-shot Quantum State Merging and the Post-Selection Technique for quantum channels.
Squashed entanglement is a measure for the entanglement of bipartite quantum states. In this paper we present a lower bound for squashed entanglement in terms of a distance to the set of separable states. This implies that squashed entanglement is faithful, that is, it is strictly positive if and only if the state is entangled. We derive the lower bound on squashed entanglement from a lower bound on the quantum conditional mutual information which is used to define squashed entanglement. The quantum conditional mutual information corresponds to the amount by which strong subadditivity of von Neumann entropy fails to be saturated. Our result therefore sheds light on the structure of states that almost satisfy strong subadditivity with equality. The proof is based on two recent results from quantum information theory: the operational interpretation of the quantum mutual information as the optimal rate for state redistribution and the interpretation of the regularised relative entropy of entanglement as an error exponent in hypothesis testing. The distance to the set of separable states is measured in terms of the LOCC norm, an operationally motivated norm giving the optimal probability of distinguishing two bipartite quantum states, each shared by two parties, using any protocol formed by local quantum operations and classical communication (LOCC) between the parties. A similar result for the Frobenius or Euclidean norm follows as an immediate consequence. The result has two applications in complexity theory. The first application is a quasipolynomial-time algorithm solving the weak membership problem for the set of separable states in LOCC or Euclidean norm. The second application concerns quantum Merlin-Arthur games. Here we show that multiple provers are not more powerful than a single prover when the verifier is restricted to LOCC operations thereby providing a new characterisation of the complexity class QMA.
We prove that for all natural numbers k,n,d with k<= d and every partition lambda of size kn with at most k parts there exists an irreducible GL(d, C)-representation of highest weight 2*lambda in the plethysm Sym^k(Sym^(2n) (C^d)). This gives an affirmative answer to a conjecture by Weintraub (J. Algebra, 129 (1):103-114, 1990). Our investigation is motivated by questions of geometric complexity theory and uses ideas from quantum information theory.
A natural question in characterizing the information theoretic power of quantum channels is to ask at what rate entanglement is needed in order to asymptotically simulate a quantum channel in the presence of free classical communication. We call this the entanglement cost of a channel, and prove a formula describing it for all channels. We discuss two applications. Firstly, our result has consequences for the study of the strong converse property of the quantum capacity. More precisely, we show that any coding scheme sending quantum information through a quantum channel at a rate larger than the entanglement cost of the channel is exponentially'bad'in the number of channel uses. Secondly, and independently of the first application, we are able to link the security in the noisy-storage model to a problem of sending quantum rather than classical information through the adversary's storage device. This not only greatly improves the range of parameters where security could be shown previously, but allows us to prove security for storage devices for which no non-trivial statements were known before.
Electric-magnetic duality and topological order on the lattice
O. Buerschaper; M. Christandl; L. Kong; M. Aguado
2010
Electric-magnetic duality and topological order on the lattice
Type
Online Database
Author
O. Buerschaper; M. Christandl; L. Kong; M. Aguado
Year
2010
Abstract
Dualities are deep conceptual tools in many areas of physics and mathematics; in particular, electric-magnetic (EM) duality has a long tradition ranging from Dirac's magnetic poles to S-duality in string and field theory. Here we investigate the duality structure in quantum lattice systems with topological order, a collective order also appearing in fractional quantum Hall systems. We define EM duality for all of Kitaev's quantum double models based on discrete gauge theories with Abelian and non-Abelian groups, and identify its natural habitat as a new class of topological models based on Hopf algebras. We interpret these as extended string-net models, whereupon Levin and Wen's string-nets, which describe all topological orders on the lattice with parity and time-reversal invariance, arise as magnetic and electric projections of the extended models. We conjecture that all string-net models can be extended in an analogous way, using a more general algebraic structure, such that EM duality continues to hold. Physical applications include topology probes in the form of pairs of dual tensor networks.
O. Buerschaper; J. M. Mombelli; M. Christandl; M. Aguado
2010
A hierarchy of topological tensor network states
Type
Online Database
Author
O. Buerschaper; J. M. Mombelli; M. Christandl; M. Aguado
Year
2010
Abstract
We present a hierarchy of quantum many-body states among which many examples of topological order can be identified by construction. We define these states in terms of a general, basis-independent framework of tensor networks based on the algebraic setting of finite-dimensional Hopf C*-algebras. At the top of the hierarchy we identify ground states of new topological lattice models extending Kitaev's quantum double models. For these states we exhibit the mechanism responsible for their non-zero topological entanglement entropy by constructing a renormalization group flow. Furthermore it is shown that those states of the hierarchy associated with Kitaev's original quantum double models are related to each other by the condensation of topological charges. We conjecture that charge condensation is the physical mechanism underlying the hierarchy in general.
The uncertainty principle in the presence of quantum memory
M. Berta; M. Christandl; R. Colbeck; J. M. Renes; R. Renner
2010
The uncertainty principle in the presence of quantum memory
Type
Journal Article
Author
M. Berta; M. Christandl; R. Colbeck; J. M. Renes; R. Renner
Year
2010
Journal
Nature Physics
Abstract
The uncertainty principle, originally formulated by Heisenberg, clearly illustrates the difference between classical and quantum mechanics. The principle bounds the uncertainties about the outcomes of two incompatible measurements, such as position and momentum, on a particle. It implies that one cannot predict the outcomes for both possible choices of measurement to arbitrary precision, even if information about the preparation of the particle is available in a classical memory. However, if the particle is prepared entangled with a quantum memory, a device that might be available in the not-too-distant future, it is possible to predict the outcomes for both measurement choices precisely. Here, we extend the uncertainty principle to incorporate this case, providing a lower bound on the uncertainties, which depends on the amount of entanglement between the particle and the quantum memory. We detail the application of our result to witnessing entanglement and to quantum key distribution.
In this paper we illuminate the relation between entanglement and secrecy by providing the first example of a quantum state that is highly entangled, but from which, nevertheless, almost no secrecy can be extracted. More precisely, we provide two bounds on the bipartite entanglement of the totally antisymmetric state in dimension d x d. First, we show that the amount of secrecy that can be extracted from the state is low, to be precise it is bounded by O(1/d). Second, we show that the state is highly entangled in the sense that we need a large amount of singlets to create the state: entanglement cost is larger than a constant, independent of d. In order to obtain our results we use representation theory, linear programming and the entanglement measure known as squashed entanglement. Our findings also clarify the relation between the squashed entanglement and the relative entropy of entanglement.
A Conceptually Simple Proof of the Quantum Reverse Shannon Theorem
M. Berta; M. Christandl; R. Renner
2010
A Conceptually Simple Proof of the Quantum Reverse Shannon Theorem
Type
Conference Proceedings
Author
M. Berta; M. Christandl; R. Renner
Year of Conference
2010
Publisher
Springer
Conference Name
Theory of Quantum Computation, Communication, and Cryptography - TQC 2010
Abstract
The Quantum Reverse Shannon Theorem states that any quantum channel can be simulated by an unlimited amount of shared entanglement and an amount of classical communication equal to the channel’s entanglement assisted classical capacity. In this extended ab- stract, we summarize a new and conceptually simple proof of this theorem [journal reference: arXiv.org:quant-ph/0912.3805], which has previously been proved in [Bennett et al., arXiv.org:quant-ph/0912.5537]. Our proof is based on optimal one-shot Quantum State Merging and the Post-Selection Technique for quantum channels.
We analyse the entanglement of the antisymmetric state in dimension d x d and present two main results. First, we show that the amount of secrecy that can be extracted from the state is low, more precisely, the distillable key is bounded by O(1/d). Second, we show that the state is highly entangled in the sense that a large number of ebits are needed in order to create the state: entanglement cost is larger than a constant, independent of d. The second result is shown to imply that the regularised relative entropy with respect to separable states is also lower bounded by a constant. In order to prove the first result we show that for all states the squashed entanglement upper bounds the distillable key. Using the unitary symmetry of the antisymmetric state we are then able to bound the squashed entanglement. A symmetry argument is also used in the second bound, where the representation theory of the unitary group is employed in order to reduce a semi-definite programming relaxation of the entanglement cost of the antisymmetric states to a manageable linear program. Finally, we note that the regularised relative entropy of entanglement is asymptotically continuous in the state. The results in this paper have previously been announced in Phys. Rev. Lett. 104, 240405 (2010).
Finite de Finetti theorem for conditional probability distributions describing physical theories
M. Christandl; B. Toner
2009
Finite de Finetti theorem for conditional probability distributions describing physical theories
Type
Journal Article
Author
M. Christandl; B. Toner
Year
2009
Journal
Journal of Mathematical Physics
Abstract
We work in a general framework where the state of a physical system is defined by its behavior under measurement and the global state is constrained by no-signaling conditions. We show that the marginals of symmetric states in such theories can be approximated by convex combinations of independent and identical conditional probability distributions, generalizing the classical finite de Finetti theorem of Diaconis and Freedman. Our results apply to correlations obtained from quantum states even when there is no bound on the local dimension, so that known quantum de Finetti theorems cannot be used.
Postselection Technique for Quantum Channels with Applications to Quantum Cryptography
M. Christandl; R. Koenig; R. Renner
2009
Postselection Technique for Quantum Channels with Applications to Quantum Cryptography
Type
Journal Article
Author
M. Christandl; R. Koenig; R. Renner
Year
2009
Journal
Physical Review Letters
Abstract
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)]
Broadcast Copies Reveal the Quantumness of Correlations
M. Piani; M. Christandl; C. E, Mora; P. Horodecki
2009
Broadcast Copies Reveal the Quantumness of Correlations
Type
Journal Article
Author
M. Piani; M. Christandl; C. E, Mora; P. Horodecki
Year
2009
Journal
Physical Review Letters
Abstract
We study the quantumness of bipartite correlations by proposing a quantity that combines a measure of total correlations—mutual information—with the notion of broadcast copies—i.e., generally nonfactorized copies—of bipartite states. By analyzing how our quantity increases with the number of broadcast copies, we are able to classify classical, separable, and entangled states. This motivates the definition of the broadcast regularization of mutual information, the asymptotic minimal mutual information per broadcast copy, which we show to have many properties of an entanglement measure.
A quantum information-theoretic proof of the relation between Horn's problem and the Littlewood-Richardson coefficients
M. Christandl
2008
A quantum information-theoretic proof of the relation between Horn's problem and the Littlewood-Richardson coefficients
Type
Conference Proceedings
Author
M. Christandl
Year of Conference
2008
Publisher
Springer
Conference Name
Computability in Europe - Logic and Theory of Algorithms
Abstract
Horn's problem asks for the conditions on sets of integers mu, nu and lambda that ensure the existence of Hermitian operators A, B and A+B with spectra mu, nu and lambda, respectively. It has been shown that this problem is equivalent to deciding whether the irreducible representation of GL(d) with highest weight lambda is contained in the tensor product of irreducible representations with highest weight mu and nu. In this paper we present a quantum information-theoretic proof of the relation between the two problems that is asymptotic in one direction. This result has previously been obtained by Klyachko using geometric invariant theory. The work presented in this paper does not, however, touch upon the non-asymptotic equivalence between the two problems, a result that rests on the recently proven saturation conjecture for GL(d).
Possibility, impossibility, and cheat sensitivity of quantum-bit string commitment
H. Buhrman; M. Christandl; P. Hayden; H.-K. Lo; S. Wehner
2008
Possibility, impossibility, and cheat sensitivity of quantum-bit string commitment
Type
Journal Article
Author
H. Buhrman; M. Christandl; P. Hayden; H.-K. Lo; S. Wehner
Year
2008
Journal
Physical Review A
Abstract
Unconditionally secure nonrelativistic bit commitment is known to be impossible in both the classical and the quantum worlds. But when committing to a string of n bits at once, how far can we stretch the quantum limits? In this paper, we introduce a framework for quantum schemes where Alice commits a string of n bits to Bob in such a way that she can only cheat on a bits and Bob can learn at most b bits of information before the reveal phase. Our results are twofold: we show by an explicit construction that in the traditional approach, where the reveal and guess probabilities form the security criteria, no good schemes can exist: a+b is at least n. If, however, we use a more liberal criterion of security, the accessible information, we construct schemes where a=4 log2 n+O(1) and b=4, which is impossible classically. We furthermore present a cheat-sensitive quantum bit string commitment protocol for which we give an explicit tradeoff between Bob’s ability to gain information about the committed string, and the probability of him being detected cheating.
A lower bound on the dimension of a quantum system given measured data
S. Wehner; M. Christandl; A. C. Doherty
2008
A lower bound on the dimension of a quantum system given measured data
Type
Journal Article
Author
S. Wehner; M. Christandl; A. C. Doherty
Year
2008
Journal
Physical Review A
Abstract
We imagine an experiment on an unknown quantum mechanical system in which the system is prepared in various ways and a range of measurements are performed. For each measurement M and preparation ρ the experimenter can determine, given enough time, the probability of a given outcome a: p(a∣M,ρ). How large does the Hilbert space of the quantum system have to be in order to allow us to find density matrices and measurement operators that will reproduce the given probability distribution? In this paper, we prove a simple lower bound for the dimension of the Hilbert space. The main insight is to relate this problem to the construction of quantum random access codes, for which interesting bounds on the Hilbert space dimension already exist. We discuss several applications of our result to hidden-variable or ontological models, to Bell inequalities, and to properties of the smooth min-entropy.
On Nonzero Kronecker Coefficients and their Consequences for Spectra
M. Christandl; A. Harrow; G. Mitchison
2007
On Nonzero Kronecker Coefficients and their Consequences for Spectra
Type
Journal Article
Author
M. Christandl; A. Harrow; G. Mitchison
Year
2007
Journal
Communications in Mathematical Physics
Abstract
A triple of spectra (r^A, r^B, r^{AB}) is said to be admissible if there is a density operator rho^{AB} with (Spec rho^A, Spec rho^B, Spec rho^{AB})=(r^A, r^B, r^{AB}). How can we characterise such triples? It turns out that the admissible spectral triples correspond to Young diagrams (mu, nu, lambda) with nonzero Kronecker coefficient [M. Christandl and G. Mitchison, to appear in Comm. Math. Phys., quant-ph/0409016; A. Klyachko, quant-ph/0409113]. This means that the irreducible representation V_lambda is contained in the tensor product of V_mu and V_nu. Here, we show that such triples form a finitely generated semigroup, thereby resolving a conjecture of Klyachko. As a consequence we are able to obtain stronger results than in [M. Ch. and G. M. op. cit.] and give a complete information-theoretic proof of the correspondence between triples of spectra and representations. Finally, we show that spectral triples form a convex polytope.
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_{mu+nu} for Young diagrams mu and nu. U_{mu+nu} is contained in the tensor product of U_mu and U_nu; let xi be the state obtained by tracing out U_nu. We show that xi is close to a convex combination of states Uv, where U is in U(d) and v is the highest weight vector in U_mu. When U_{mu+nu} 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 xi 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.
Quantum Computational Complexity of the N-Representability Problem: QMA Complete
Y.-K. Liu; M. Christandl; F. Verstraete
2007
Quantum Computational Complexity of the N-Representability Problem: QMA Complete
Type
Journal Article
Author
Y.-K. Liu; M. Christandl; F. Verstraete
Year
2007
Journal
Physical Review Letters
Abstract
We study the computational complexity of the N-representability problem in quantum chemistry. We show that this problem is quantum Merlin-Arthur complete, which is the quantum generalization of nondeterministic polynomial time complete. Our proof uses a simple mapping from spin systems to fermionic systems, as well as a convex optimization technique that reduces the problem of finding ground states to N representability.
M. Christandl; A. Ekert; M. Horodecki; P. Horodecki; J. Oppenheim; R. Renner
2007
Unifying classical and quantum key distillation
Type
Conference Proceedings
Author
M. Christandl; A. Ekert; M. Horodecki; P. Horodecki; J. Oppenheim; R. Renner
Year of Conference
2007
Publisher
Springer
Conference Name
Theory of Cryptography
Abstract
Assume that two distant parties, Alice and Bob, as well as an adversary, Eve, have access to (quantum) systems prepared jointly according to a tripartite state. In addition, Alice and Bob can use local operations and authenticated public classical communication. Their goal is to establish a key which is unknown to Eve. We initiate the study of this scenario as a unification of two standard scenarios: (i) key distillation (agreement) from classical correlations and (ii) key distillation from pure tripartite quantum states. Firstly, we obtain generalisations of fundamental results related to scenarios (i) and (ii), including upper bounds on the key rate. Moreover, based on an embedding of classical distributions into quantum states, we are able to find new connections between protocols and quantities in the standard scenarios (i) and (ii). Secondly, we study specific properties of key distillation protocols. In particular, we show that every protocol that makes use of pre-shared key can be transformed into an equally efficient protocol which needs no pre-shared key. This result is of practical significance as it applies to quantum key distribution (QKD) protocols, but it also implies that the key rate cannot be locked with information on Eve's side. Finally, we exhibit an arbitrarily large separation between the key rate in the standard setting where Eve is equipped with quantum memory and the key rate in a setting where Eve is only given classical memory. This shows that assumptions on the nature of Eve's memory are important in order to determine the correct security threshold in QKD.
H. Buhrmann; M. Christandl; M. Koucky; Z. Lotker; B. Patt-Shamir; N. Vereshchagin
2007
High Entropy Random Selection Protocols
Type
Conference Proceedings
Author
H. Buhrmann; M. Christandl; M. Koucky; Z. Lotker; B. Patt-Shamir; N. Vereshchagin
Year of Conference
2007
Publisher
Springer
Conference Name
Workshop on Randomization and Computation
Abstract
We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy n − O(1) and has 4 log∗n rounds, improving over the protocol of Goldreich et al. [3] that also achieves this entropy but needs O(n) rounds. Both these protocols need O(n2) bits of communication. Next we reduce the communication in our protocols. We show the existence, non- explicitly, of a protocol that has 6 rounds, 2n + 8 log n bits of communication and yields entropy n − O(log n) and min-entropy n/2 − O(log n). Our proto- col achieves the same entropy bound as the recent, also non-explicit, protocol of Gradwohl et al. [4], however achieves much higher min-entropy: n/2−O(log n) versus O(log n). Finally we exhibit very simple explicit protocols. We connect the security parameter of these geometric protocols with the well studied Kakeya problem motivated by harmonic analysis and analytical number theory. We are only able to prove that these protocols have entropy 3n/4 but still n/2 − O(log n) min-entropy. Therefore they do not perform as well with respect to the explicit constructions of Gradwohl et al. [4] entropy-wise, but still have much better min-entropy. We conjecture that these simple protocols achieve n − o(n) entropy. Our geometric construction and its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols.
Unconditional security of key distribution from causality constraints
L. Masanes; R. Renner; M. Christandl; A. Winter; J. Barrett
2006
Unconditional security of key distribution from causality constraints
Type
Online Database
Author
L. Masanes; R. Renner; M. Christandl; A. Winter; J. Barrett
Year
2006
Abstract
We analyze a protocol which generates secret key from correlations that violate a Bell inequality by a sufficient amount, and prove its security against eavesdroppers which are only constrained by the fact that any information accessible to them must be compatible with the impossibility of arbitrarily fast signaling. We prove unconditional security according to the strongest notion, the so called universally-composable security. The no-signaling assumption is imposed at the level of the outcome probabilities given the choice of the observable, therefore, the protocol remains secure in situations where the honest parties do not have a complete control over their quantum apparatuses, or distrust them. The techniques developed are very general and can be applied to other Bell inequality-based protocols. In particular, we provide a scheme for estimating Bell-inequality violations when the samples are not independent and identically distributed.
The Spectra of Density Operators and the Kronecker Coefficients of the Symmetric Group
M. Christandl; G. Mitchison
2006
The Spectra of Density Operators and the Kronecker Coefficients of the Symmetric Group
Type
Journal Article
Author
M. Christandl; G. Mitchison
Year
2006
Journal
Communications in Mathematical Physics
Abstract
Determining the relationship between composite systems and their subsystems is a fundamental problem in quantum physics. In this paper we consider the spectra of a bipartite quantum state and its two marginal states. To each spectrum we can associate a representation of the symmetric group defined by a Young diagram whose normalised row lengths approximate the spectrum. We show that, for allowed spectra, the representation of the composite system is contained in the tensor product of the representations of the two subsystems. This gives a new physical meaning to representations of the symmetric group. It also introduces a new way of using the machinery of group theory in quantum informational problems, which we illustrate by two simple examples.
Security of quantum bit string commitment depends on the information measure
H. Buhrman; M. Christandl; P. Hayden; H.-K. Lo; S. Wehner
2006
Security of quantum bit string commitment depends on the information measure
Type
Journal Article
Author
H. Buhrman; M. Christandl; P. Hayden; H.-K. Lo; S. Wehner
Year
2006
Journal
Physical Review Letters
Abstract
Unconditionally secure nonrelativistic bit commitment is known to be impossible in both the classical and the quantum world. However, when committing to a string of n bits at once, how far can we stretch the quantum limits? In this Letter, we introduce a framework of quantum schemes where Alice commits a string of n bits to Bob, in such a way that she can only cheat on a bits and Bob can learn at most b bits of information before the reveal phase. Our results are twofold: we show by an explicit construction that in the traditional approach, where the reveal and guess probabilities form the security criteria, no good schemes can exist: a+b is at least n. If, however, we use a more liberal criterion of security, the accessible information, we construct schemes where a=4log2n+O(1) and b=4, which is impossible classically. Our findings significantly extend known no-go results for quantum bit commitment.
The Structure of Bipartite Quantum States - Insights from Group Theory and Cryptography
M. Christandl
2006
The Structure of Bipartite Quantum States - Insights from Group Theory and Cryptography
Type
Thesis
Author
M. Christandl
Year
2006
Physics
Abstract
This thesis presents a study of the structure of bipartite quantum states. In the first part, the representation theory of the unitary and symmetric groups is used to analyse the spectra of quantum states. In particular, it is shown how to derive a one-to-one relation between the spectra of a bipartite quantum state and its reduced states, and the Kronecker coefficients of the symmetric group. In the second part, the focus lies on the entanglement of bipartite quantum states. Drawing on an analogy between entanglement distillation and secret-key agreement in classical cryptography, a new entanglement measure, `squashed entanglement', is introduced.
Implications of superstrong non-locality for cryptography
H. Buhrman; M. Christandl; F. Unger; S. Wehner; A. Winter
2006
Implications of superstrong non-locality for cryptography
Type
Journal Article
Author
H. Buhrman; M. Christandl; F. Unger; S. Wehner; A. Winter
Year
2006
Journal
Proceedings of the Royal Society A
Abstract
Non-local boxes are hypothetical ‘machines’ that give rise to superstrong non-local correlations, leading to a stronger violation of Bell/Clauser, Horne, Shimony&Holt inequalities than is possible within the framework of quantum mechanics. We show how non-local boxes can be used to perform any two-party secure computation. We first construct a protocol for bit commitment and then show how to achieve oblivious transfer using non-local boxes. Both have been shown to be impossible using quantum mechanics alone.
We consider the problem of hiding sender and receiver of classical and quantum bits (qubits), even if all physical transmissions can be monitored. We present a quantum protocol for sending and receiving classical bits anonymously, which is completely traceless: it successfully prevents later reconstruction of the sender. We show that this is not possible classically. It appears that entangled quantum states are uniquely suited for traceless anonymous transmissions. We then extend this protocol to send and receive qubits anonymously. In the process we introduce a new primitive called anonymous entanglement, which may be useful in other contexts as well.
Uncertainty, Monogamy, and Locking of Quantum Correlations
M. Christandl; A. Winter
2005
Uncertainty, Monogamy, and Locking of Quantum Correlations
Type
Journal Article
Author
M. Christandl; A. Winter
Year
2005
Journal
IEEE Transactions on Information Theory
Abstract
Squashed entanglement and entanglement of purification are quantum-mechanical correlation measures and are defined as certain minimizations of entropic quantities. In this paper, we present the first nontrivial calculations of both quantities. Our results lead to the conclusion that both measures can drop by an arbitrary amount when only a single qubit of a local system is lost. This property is known as “locking” and has previously been observed for other correlation measures such as accessible information, entanglement cost, and logarithmic negativity. In the case of squashed entanglement, the results are obtained using an inequality that can be understood as a quantum channel analogue of well-known entropic uncertainty relations. This inequality may prove a useful tool in quantum information theory. The regularized entanglement of purification is known to equal the entanglement needed to prepare many copies of a quantum state by local operations and a sublinear amount of communication. Here, monogamy of quantum entanglement (i.e., the impossibility of a system being maximally entangled with two others at the same time) leads to an exact calculation for all quantum states that are supported either on the symmetric or on the antisymmetric subspace of a$d times d$-dimensional system
Perfect Transfer of Arbitrary States in Quantum Spin Networks
M. Christandl; N. Datta; T. C. Dorlas; A. Ekert; A. Kay; A. J. Landahl
2005
Perfect Transfer of Arbitrary States in Quantum Spin Networks
Type
Journal Article
Author
M. Christandl; N. Datta; T. C. Dorlas; A. Ekert; A. Kay; A. J. Landahl
Year
2005
Journal
Physical Review A
Abstract
We propose a class of qubit networks that admit perfect state transfer of any two-dimensional quantum state in a fixed period of time. We further show that such networks can distribute arbitrary entangled states between two distant parties, and can, by using such systems in parallel, transmit the higher-dimensional systems states across the network. Unlike many other schemes for quantum computation and communication, these networks do not require qubit couplings to be switched on and off. When restricted to N-qubit spin networks of identical qubit couplings, we show that 2 log3N is the maximal perfect communication distance for hypercube geometries. Moreover, if one allows fixed but different couplings between the qubits then perfect state transfer can be achieved over arbitrarily long distances in a linear chain. This paper expands and extends the work done by Christandl et al., Phys. Rev. Lett. 92, 187902 (2004).
A Generic Security Proof for Quantum Key Distribution
M. Christandl; R. Renner; A. Ekert
2004
A Generic Security Proof for Quantum Key Distribution
Type
Online Database
Author
M. Christandl; R. Renner; A. Ekert
Year
2004
Abstract
Quantum key distribution allows two parties, traditionally known as Alice and Bob, to establish a secure random cryptographic key if, firstly, they have access to a quantum communication channel, and secondly, they can exchange classical public messages which can be monitored but not altered by an eavesdropper, Eve. Quantum key distribution provides perfect security because, unlike its classical counterpart, it relies on the laws of physics rather than on ensuring that successful eavesdropping would require excessive computational effort. However, security proofs of quantum key distribution are not trivial and are usually restricted in their applicability to specific protocols. In contrast, we present a general and conceptually simple proof which can be applied to a number of different protocols. It relies on the fact that a cryptographic procedure called privacy amplification is equally secure when an adversary's memory for data storage is quantum rather than classical.
IEEE International Symposium on Information Theory
Abstract
This paper introduces the public Eve scenario and shows that the secret key rate in this scenario is bounded by the intrinsic information. This elucidates previous results and gives new insights in the gap between formation and extraction of secret information. Intrinsic information, in its function as an upper bound on the secret key rate, is generalized to secret key agreement from arbitrary tripartite quantum states.
"Squashed Entanglement"- An Additive Entanglement Measure
M. Christandl; A. Winter
2004
"Squashed Entanglement"- An Additive Entanglement Measure
Type
Journal Article
Author
M. Christandl; A. Winter
Year
2004
Journal
Journal of Mathematical Physics
Abstract
In this paper, we present a new entanglement monotone for bipartite quantum states. Its definition is inspired by the so-called intrinsic information of classical cryptography and is given by the halved minimum quantum conditional mutual information over all tripartite state extensions. We derive certain properties of the new measure which we call “squashed entanglement”: it is a lower bound on entanglement of formation and an upper bound on distillable entanglement. Furthermore, it is convex, additive on tensor products, and superadditive in general. Continuity in the state is the only property of our entanglement measure which we cannot provide a proof for. We present some evidence, however, that our quantity has this property, the strongest indication being a conjectured Fannes-type inequality for the conditional von Neumann entropy. This inequality is proved in the classical case.
Mirror Inversion of Quantum States in Linear Registers
C. Albanese; M. Christandl; N. Datta; A. Ekert
2004
Mirror Inversion of Quantum States in Linear Registers
Type
Journal Article
Author
C. Albanese; M. Christandl; N. Datta; A. Ekert
Year
2004
Journal
Physical Review Letters
Abstract
Transfer of data in linear quantum registers can be significantly simplified with preengineered but not dynamically controlled interqubit couplings. We show how to implement a mirror inversion of the state of the register in each excitation subspace with respect to the center of the register. Our construction is especially appealing as it requires no dynamical control over individual interqubit interactions. If, however, individual control of the interactions is available then the mirror inversion operation can be performed on any substring of qubits in the register. In this case, a sequence of mirror inversions can generate any permutation of a quantum state of the involved qubits.
We propose a class of qubit networks that admit the perfect state transfer of any quantum state in a fixed period of time. Unlike many other schemes for quantum computation and communication, these networks do not require qubit couplings to be switched on and off. When restricted to N-qubit spin networks of identical qubit couplings, we show that 2log3N is the maximal perfect communication distance for hypercube geometries. Moreover, if one allows fixed but different couplings between the qubits, then perfect state transfer can be achieved over arbitrarily long distances in a linear chain.
IEEE International Symposium on Information Theory
Abstract
The so-called intrinsic mutual information is an important measure in the context of information-theoretic secret-key agreement. We prove a property of this information measure which, in particular, strongly simplifies its computation. More generally, our result is useful for analyzing the correlation of two random variables conditioned on a third one.
Entanglement is a valuable resource in quantum information processing and thus its detection and characterization is an important procedure. We review some of the criteria for separability and provide an efficient and physically realizable method by which entanglement may be detected within the “distant labs” paradigm.
Quantum cryptography based on qutrit Bell inequalities
D. Kaszlikowski; D. K. L. Oi; M. Christandl; K. Chang; A. Ekert; L. C. Kwek; C. H. Oh
2003
Quantum cryptography based on qutrit Bell inequalities
Type
Journal Article
Author
D. Kaszlikowski; D. K. L. Oi; M. Christandl; K. Chang; A. Ekert; L. C. Kwek; C. H. Oh
Year
2003
Journal
Physical Review A
Abstract
We present a cryptographic protocol based upon entangled qutrit pairs. We analyze the scheme under a symmetric incoherent attack and plot the region for which the protocol is secure and compare this with the region of violations of certain Bell inequalities.
Tomographic Quantum Cryptography: Equivalence of Quantum and Classical Key Distillation
D. Bruss; M. Christandl; A. Ekert; B.-G. Englert; D. Kaszlikowski; C. Macchiavello
2003
Tomographic Quantum Cryptography: Equivalence of Quantum and Classical Key Distillation
Type
Journal Article
Author
D. Bruss; M. Christandl; A. Ekert; B.-G. Englert; D. Kaszlikowski; C. Macchiavello
Year
2003
Journal
Physical Review Letters
Abstract
The security of a cryptographic key that is generated by communication through a noisy quantum channel relies on the ability to distill a shorter secure key sequence from a longer insecure one. For an important class of protocols, which exploit tomographically complete measurements on entangled pairs of any dimension, we show that the noise threshold for classical advantage distillation is identical with the threshold for quantum entanglement distillation. As a consequence, the two distillation procedures are equivalent: neither offers a security advantage over the other.
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser. More
information
