Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1011.1612 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

The locking-decoding frontier for generic dynamics

Frédéric Dupuis, Jan Florjanczyk, Patrick M. Hayden, Debbie Leung

Published Sep 18, 2013• 36 citations
arXivHTMLPDF

Abstract

It is known that the maximum classical mutual information, which can be achieved between measurements on pairs of quantum systems, can drastically underestimate the quantum mutual information between them. In this article, we quantify this distinction between classical and quantum information by demonstrating that after removing a logarithmic-sized quantum system from one half of a pair of perfectly correlated bitstrings, even the most sensitive pair of measurements might yield only outcomes essentially independent of each other. This effect is a form of information locking but the definition we use is strictly stronger than those used previously. Moreover, we find that this property is generic, in the sense that it occurs when removing a random subsystem. As such, the effect might be relevant to statistical mechanics or black hole physics. While previous works had always assumed a uniform message, we assume only a min-entropy bound and also explore the effect of entanglement. We find that classical information is strongly locked almost until it can be completely decoded. Finally, we exhibit a quantum key distribution protocol that is 'secure' in the sense of accessible information but in which leakage of even a logarithmic number of bits compromises the secrecy of all others.

DOI
10.1098/rspa.2013.0289

Related papers

The locking-decoding frontier for generic dynamics

Jan Florjanczyk

The intuition that the amount of classical correlations between two systems be bounded by their size does not hold true in general for quantum states. In the setting of information locking, measurements on a pair of quantum systems that appear to be completely uncorrelated can become maximally correlated with a small increment in the size of one of the systems. A new information locking scheme based on generic unitary channels is presented and a strengthened definition of locking based on a measure of indistinguishability is used. The new definition demonstrates that classical information can be kept arbitrarily low until it can be completely decoded. Unlike previous locking results, non-uniform input messages are allowed and shared entanglement between the pair of quantum systems is considered. Whereas past locking results relied on schemes with an explicit "key" register, this requirement is eliminated in favor of an arbitrary quantum subsystem. Furthermore, past results considered only projective measurements at the receiver. Here locking effects can be shown even in the case where the receiver is armed with the most general type of measurement. The locking effect is found to be generic and finds applications in entropic security and models for black hole evaporation.

•Jan 1, 2011•0 citations

The decoupling approach to quantum information theory

Frédéric Dupuis

Quantum information theory studies the fundamental limits that physical laws impose on information processing tasks such as data compression and data transmission on noisy channels. This thesis presents general techniques that allow one to solve many fundamental problems of quantum information theory in a unified framework. The central theorem of this thesis proves the existence of a protocol that transmits quantum data that is partially known to the receiver through a single use of an arbitrary noisy quantum channel. In addition to the intrinsic interest of this problem, this theorem has as immediate corollaries several central theorems of quantum information theory. The following chapters use this theorem to prove the existence of new protocols for two other types of quantum channels, namely quantum broadcast channels and quantum channels with side information at the transmitter. These protocols also involve sending quantum information partially known by the receiver with a single use of the channel, and have as corollaries entanglement-assisted and unassisted asymptotic coding theorems. The entanglement-assisted asymptotic versions can, in both cases, be considered as quantum versions of the best coding theorems known for the classical versions of these problems. The last chapter deals with a purely quantum phenomenon called locking. We demonstrate that it is possible to encode a classical message into a quantum state such that, by removing a subsystem of logarithmic size with respect to its total size, no measurement can have significant correlations with the message. The message is therefore "locked" by a logarithmic-size key. This thesis presents the first locking protocol for which the success criterion is that the trace distance between the joint distribution of the message and the measurement result and the product of their marginals be sufficiently small.

arXiv:1004.1641•Apr 9, 2010•90 citations

Aspects of generic entanglement

Patrick M. Hayden, Debbie Leung, Andreas Winter

We study entanglement and other correlation properties of random states in high-dimensional bipartite systems. These correlations are quantified by parameters that are subject to the "concentration of measure" phenomenon, meaning that on a large-probability set these parameters are close to their expectation. For the entropy of entanglement, this has the counterintuitive consequence that there exist large subspaces in which all pure states are close to maximally entangled. This, in turn, implies the existence of mixed states with entanglement of formation near that of a maximally entangled state, but with negligible quantum mutual information and, therefore, negligible distillable entanglement, secret key, and common randomness. It also implies a very strong locking effect for the entanglement of formation: its value can jump from maximal to near zero by tracing over a number of qubits negligible compared to the size of total system. Furthermore, such properties are generic. Similar phenomena are observed for random multiparty states, leading us to speculate on the possibility that the theory of entanglement is much simplified when restricted to asymptotically generic states. Further consequences of our results include a complete derandomization of the protocol for universal superdense coding of quantum states.

•Jan 1, 2004•236 citations

Secrecy extraction from no-signaling correlations

Valerio Scarani, Nicolas Gisin, Nicolas Brunner +3 more

Quantum cryptography shows that one can guarantee the secrecy of correlation on the sole basis of the laws of physics, that is, without limiting the computational power of the eavesdropper. The usual security proofs suppose that the authorized partners, Alice and Bob, have a perfect knowledge and control of their quantum systems and devices; for instance, they must be sure that the logical bits have been encoded in true qubits and not in higher dimensional systems. In this paper, we present an approach that circumvents this strong assumption. We define protocols, both for the case of bits and for generic $d$-dimensional outcomes, in which the security is guaranteed by the very structure of the Alice-Bob correlations, under the no-signaling condition. The idea is that if the correlations cannot be produced by shared randomness, then Eve has poor knowledge of Alice's and Bob's symbols. The present study assumes on the one hand that the eavesdropper Eve performs only individual attacks (this is a limitation to be removed in further work), and on the other hand that Eve can distribute any correlation compatible with the no-signaling condition (in this sense her power is greater than what quantum physics allows). Under these assumptions, we prove that the protocols defined here allow extracting secrecy from noisy correlations, when these correlations violate a Bell-type inequality by a sufficiently large amount. The region in which secrecy extraction is possible extends within the region of correlations achievable by measurements on entangled quantum states.

arXiv:quant-ph/0606197•Physical Review A•Oct 30, 2006•121 citations

Informationally restricted quantum correlations

Armin Tavakoli, Emmanuel Zambrini Cruzeiro, Jonatan Bohr Brask +2 more

Quantum communication leads to strong correlations, that can outperform classical ones. Complementary to previous works in this area, we investigate correlations in prepare-and-measure scenarios assuming a bound on the information content of the quantum communication, rather than on its Hilbert-space dimension. Specifically, we explore the extent of classical and quantum correlations given an upper bound on the one-shot accessible information. We provide a characterisation of the set of classical correlations and show that quantum correlations are stronger than classical ones. We also show that limiting information rather than dimension leads to stronger quantum correlations. Moreover, we present device-independent tests for placing lower bounds on the information given observed correlations. Finally, we show that quantum communication carrying log⁡d bits of information is at least as strong a resource as d -dimensional classical communication assisted by pre-shared entanglement.

arXiv:1909.05656•Quantum•Sep 24, 2020•32 citations

From low-distortion norm embeddings to explicit uncertainty relations and efficient information locking

Omar Fawzi, Patrick M. Hayden, Pranab Sen

Quantum uncertainty relations are at the heart of many quantum cryptographic protocols performing classically impossible tasks. One operational manifestation of these uncertainty relations is a purely quantum effect referred to as information locking. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random n-bit message is encoded in a quantum system using a classical key of size much smaller than n. Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message (the message is "locked"). Furthermore, knowing the key, it is possible to recover (or "unlock") the message.

ACM Symposium on Theory of Computing (STOC)•Jun 6, 2011•12 citations
It is known that the maximum classical mutual information, which can be achieved between measurements on pairs of quantum systems, can drastically underestimate the quantum mutual information between them. In this article, we quantify this distinction between classical and quantum information by demonstrating that after removing a logarithmic-sized quantum system from one half of a pair of perfectly correlated bitstrings, even the most sensitive pair of measurements might yield only outcomes essentially independent of each other. This effect is a form of information locking but the definition we use is strictly stronger than those used previously. Moreover, we find that this property is generic, in the sense that it occurs when removing a random subsystem. As such, the effect might be relevant to statistical mechanics or black hole physics. While previous works had always assumed a uniform message, we assume only a min-entropy bound and also explore the effect of entanglement. We find that classical information is strongly locked almost until it can be completely decoded. Finally, we exhibit a quantum key distribution protocol that is 'secure' in the sense of accessible information but in which leakage of even a logarithmic number of bits compromises the secrecy of all others.
The intuition that the amount of classical correlations between two systems be bounded by their size does not hold true in general for quantum states. In the setting of information locking, measurements on a pair of quantum systems that appear to be completely uncorrelated can become maximally correlated with a small increment in the size of one of the systems. A new information locking scheme based on generic unitary channels is presented and a strengthened definition of locking based on a measure of indistinguishability is used. The new definition demonstrates that classical information can be kept arbitrarily low until it can be completely decoded. Unlike previous locking results, non-uniform input messages are allowed and shared entanglement between the pair of quantum systems is considered. Whereas past locking results relied on schemes with an explicit "key" register, this requirement is eliminated in favor of an arbitrary quantum subsystem. Furthermore, past results considered only projective measurements at the receiver. Here locking effects can be shown even in the case where the receiver is armed with the most general type of measurement. The locking effect is found to be generic and finds applications in entropic security and models for black hole evaporation.
Quantum information theory studies the fundamental limits that physical laws impose on information processing tasks such as data compression and data transmission on noisy channels. This thesis presents general techniques that allow one to solve many fundamental problems of quantum information theory in a unified framework. The central theorem of this thesis proves the existence of a protocol that transmits quantum data that is partially known to the receiver through a single use of an arbitrary noisy quantum channel. In addition to the intrinsic interest of this problem, this theorem has as immediate corollaries several central theorems of quantum information theory. The following chapters use this theorem to prove the existence of new protocols for two other types of quantum channels, namely quantum broadcast channels and quantum channels with side information at the transmitter. These protocols also involve sending quantum information partially known by the receiver with a single use of the channel, and have as corollaries entanglement-assisted and unassisted asymptotic coding theorems. The entanglement-assisted asymptotic versions can, in both cases, be considered as quantum versions of the best coding theorems known for the classical versions of these problems. The last chapter deals with a purely quantum phenomenon called locking. We demonstrate that it is possible to encode a classical message into a quantum state such that, by removing a subsystem of logarithmic size with respect to its total size, no measurement can have significant correlations with the message. The message is therefore "locked" by a logarithmic-size key. This thesis presents the first locking protocol for which the success criterion is that the trace distance between the joint distribution of the message and the measurement result and the product of their marginals be sufficiently small.
We study entanglement and other correlation properties of random states in high-dimensional bipartite systems. These correlations are quantified by parameters that are subject to the "concentration of measure" phenomenon, meaning that on a large-probability set these parameters are close to their expectation. For the entropy of entanglement, this has the counterintuitive consequence that there exist large subspaces in which all pure states are close to maximally entangled. This, in turn, implies the existence of mixed states with entanglement of formation near that of a maximally entangled state, but with negligible quantum mutual information and, therefore, negligible distillable entanglement, secret key, and common randomness. It also implies a very strong locking effect for the entanglement of formation: its value can jump from maximal to near zero by tracing over a number of qubits negligible compared to the size of total system. Furthermore, such properties are generic. Similar phenomena are observed for random multiparty states, leading us to speculate on the possibility that the theory of entanglement is much simplified when restricted to asymptotically generic states. Further consequences of our results include a complete derandomization of the protocol for universal superdense coding of quantum states.
Quantum cryptography shows that one can guarantee the secrecy of correlation on the sole basis of the laws of physics, that is, without limiting the computational power of the eavesdropper. The usual security proofs suppose that the authorized partners, Alice and Bob, have a perfect knowledge and control of their quantum systems and devices; for instance, they must be sure that the logical bits have been encoded in true qubits and not in higher dimensional systems. In this paper, we present an approach that circumvents this strong assumption. We define protocols, both for the case of bits and for generic ddd-dimensional outcomes, in which the security is guaranteed by the very structure of the Alice-Bob correlations, under the no-signaling condition. The idea is that if the correlations cannot be produced by shared randomness, then Eve has poor knowledge of Alice's and Bob's symbols. The present study assumes on the one hand that the eavesdropper Eve performs only individual attacks (this is a limitation to be removed in further work), and on the other hand that Eve can distribute any correlation compatible with the no-signaling condition (in this sense her power is greater than what quantum physics allows). Under these assumptions, we prove that the protocols defined here allow extracting secrecy from noisy correlations, when these correlations violate a Bell-type inequality by a sufficiently large amount. The region in which secrecy extraction is possible extends within the region of correlations achievable by measurements on entangled quantum states.
Quantum communication leads to strong correlations, that can outperform classical ones. Complementary to previous works in this area, we investigate correlations in prepare-and-measure scenarios assuming a bound on the information content of the quantum communication, rather than on its Hilbert-space dimension. Specifically, we explore the extent of classical and quantum correlations given an upper bound on the one-shot accessible information. We provide a characterisation of the set of classical correlations and show that quantum correlations are stronger than classical ones. We also show that limiting information rather than dimension leads to stronger quantum correlations. Moreover, we present device-independent tests for placing lower bounds on the information given observed correlations. Finally, we show that quantum communication carrying log⁡d bits of information is at least as strong a resource as d -dimensional classical communication assisted by pre-shared entanglement.
Quantum uncertainty relations are at the heart of many quantum cryptographic protocols performing classically impossible tasks. One operational manifestation of these uncertainty relations is a purely quantum effect referred to as information locking. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random n-bit message is encoded in a quantum system using a classical key of size much smaller than n. Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message (the message is "locked"). Furthermore, knowing the key, it is possible to recover (or "unlock") the message.