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:1804.03027 · Physical Review X

Catalytic Quantum Randomness

Paul Boës, Henrik Wilming, R. Gallego, Jens Eisert

Published Oct 29, 2018• 31 citations
arXivHTMLPDF

Abstract

Randomness is a defining element of mixing processes in nature and an essential ingredient to many protocols in quantum information.In this work, we investigate how much randomness is required to transform a given quantum state into another one.Specifically, we ask whether there is a gap between the power of a classical source of randomness compared to that of a quantum one.We provide a complete answer to these questions, by identifying provably optimal protocols for both classical and quantum sources of randomness, based on a dephasing construction.We find that in order to implement any noisy transition on a d-dimensional quantum system it is necessary and sufficient to have a quantum source of randomness of dimension ffiffiffi d p or a classical one of dimension d.Interestingly, coherences provided by quantum states in a source of randomness offer a quadratic advantage.The process we construct has the additional features to be robust and catalytic; i.e., the source of randomness can be reused.Building upon this formal framework, we illustrate that this dephasing construction can serve as a useful primitive in both equilibration and quantum information theory: We discuss applications describing the smallest measurement device, capturing the smallest equilibrating environment allowed by quantum mechanics, or forming the basis for a cryptographic private quantum channel.We complement the exact analysis with a discussion of approximate protocols based on quantum expanders deriving from discrete Weyl systems.This gives rise to equilibrating environments of remarkably small dimension.Our results highlight the curious feature of randomness that residual correlations and dimension can be traded against each other.

DOI
10.1103/physrevx.8.041016

Related papers

Catalytic quantum randomness as a correlational resource

Seok Hyung Lie, Hyunseok Jeong

Catalysts are substances that assist transformation of other resourceful objects without being consumed in the process. However, the fact that their ``catalytic power'' is limited and can be depleted is often overlooked, especially in the recently developing theories on catalysis of quantum randomness utilizing building correlation with catalyst. In this work, we establish a resource theory of one-shot catalytic randomness in which uncorrelatedness is consumed in catalysis of randomness. We do so by completely characterizing bipartite unitary operators that can be used to implement catalysis of randomness using partial transpose. By doing so, we find that every catalytic channel is factorizable, and therefore there exists a unital channel that is not catalytic. We define a family of catalytic entropies that quantifies catalytically extractable R\'enyi entropies from a quantum state and show how much the degeneracy of a quantum state can boost the catalytic entropy beyond its ordinary entropy. Based on this, we demonstrate that a randomness source can be actually exhausted after a certain amount of randomness is extracted. We apply this theory to systems under superselection rules that forbids superposition of certain quantum states and find that nonmaximally mixed states can yield the maximal catalytic entropy. We discuss implications of this theory to various topics, including catalytic randomness absorption, the no-secret theorem, and the possibility of multiparty infinite catalysis.

arXiv:2104.00300•Physical Review Research•Oct 29, 2021•16 citations

Delocalized and dynamical catalytic randomness and information flow

Seok Hyung Lie, Hyunseok Jeong

We generalize the theory of catalytic quantum randomness to distributed and dynamical settings. First, we expand the theory of catalytic quantum randomness by calculating the amount of (R\'enyi) entropy catalytically extractable from a distributed or dynamical randomness source. We show that no entropy can be catalytically extracted when one cannot implement local projective measurement on randomness source without altering its state. As an application, we prove that quantum operation cannot be hidden in correlation between two parties without using randomness, which is the dynamical generalization of the no-hiding theorem. Moreover, the formalism of distributed catalysis is applied to develop a formal definition of semantic quantum information and it follows that utilizing semantic information is equivalent to catalysis using a catalyst already correlated with the transforming system. By doing so, we unify the utilization of semantic and nonsemantic quantum information and conclude that one can always extract more information from an incompletely depleted classical randomness source, but it is not possible for quantum randomness sources.

arXiv:2206.11469•Physical Review A•Apr 24, 2023•5 citations

Randomness, catalysis and partial knowledge in quantum thermodynamics

Paul Boës

Quantum thermodynamics is a blossoming research program that uses tools and ideas from quantum information theory to extend the laws of thermodynamics to the domain of systems to which the laws of quantum mechanics apply and the thermodynamic limit does not necessarily apply. The contributions of this program are both foundational, in providing an approach to constructively derive the laws of phenomenological thermodynamics from the postulates of unitary quantum mechanics in a rigorous and bottom-up fashion, but also prac- tical, in providing the theory for an increasing number of experiments that attempt to build thermodynamic machines at scales that were previously inaccessible. One key mathematical tool used in quantum thermodynamics is the framework of resource theories, specifically the resource theory of thermal operations, in which the thermodynamic interaction of a system with a heat bath and various additional components such as work batteries, clocks or catalysts are modeled. In this cumulative thesis, various extensions and modifications of this framework are studied in order to derive novel results and insights about the possible thermodynamic evolution of quantum systems. In particular, following a system- atic exposition of the resource theory of thermal operations from first principles, I develop answers to the following questions: i) What is the smallest heat bath required to provide the necessary randomness for a system to undergo a given stochastic or thermodynamical evolution? ii) Does this size differ depending on whether the interaction between bath and system is quantum or classical? iii) How can quantum systems thermodynamically evolve in the presence of catalytic bystander systems and how can this be put to use? iv) What are the thermodynamic state transitions that an agent can operationally affect when she only has access to partial information about the underlying states of system and bath? v) How can we understand the emergence of the canonical ensemble in statistical thermodynamics from quantum mechanics? These questions cover a wide ground, but it will become clear that they can in fact all be discussed using the same formal tools. As such, the answers to the above questions provided in this thesis are both interesting in their own right — showing for example that there exists a gap in how efficiently randomness can be exploited quantumly as compared to classically or that catalytic bystander systems can be used to extract finite amounts of work per particle from macroscopic systems with non-vanishing probability — as well as illustrate the power of quantum thermodynamics as a set of tools to connect quantum mechanics and the theory of thermodynamics more generally.

•Jan 1, 2021•0 citations

Randomness for quantum channels: Genericity of catalysis and quantum advantage of uniformness

Seok Hyung Lie, Hyunseok Jeong

Randomness can help one to implement quantum maps that cannot be realized in a deterministic fashion.Recently, it was discovered that explicitly treating a randomness source as a quantum system could double the efficiency as a catalyst for some tasks.In this work, we first show that every quantum channel that can be implemented with a randomness source without leaking information to it must be a catalysis.For that purpose, we prove a new no-go theorem that generalizes the no-hiding theorem, the no-secret theorem that states no quantum information can be shared with other systems as a secret without leaking some information.Second, we show that nondegenerate catalysts should be used classically when no extra dimension is allowed, which leads to the fact that the quantum advantage of a catalytic process strictly comes from the uniformness of the randomness source.Finally, we discuss a method to circumvent the previous result that achieves quantum advantage with nondegenerate catalyst uniformized by employing extra work space.

arXiv:2010.14795•Physical Review Research•Mar 8, 2021•14 citations

Quantum to Classical Randomness Extractors

Mario Berta, Omar Fawzi, Stephanie Wehner

The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. When the source yields a classical string X, many extractor constructions are known. Yet, when considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system. When characterizing the power of a source to supply randomness, it is hence natural to ask how much classical randomness we can extract from a quantum system. To tackle this question, we here take on the study of quantum-to-classical randomness extractors (QC-extractors). We provide constructions of QC-extractors based on measurements in a full set of mutually unbiased bases (MUBs), and certain single qubit measurements. The latter are particularly appealing since they are not only easy to implement, but also appear throughout quantum cryptography. We proceed to prove an upper bound on the maximum amount of randomness that we could hope to extract from any quantum state. Some of our QC-extractors almost match this bound. We show two applications of our results. First, we show that any QC-extractor gives rise to entropic uncertainty relations with respect to quantum side information. Such relations were previously only known for two measurements. In particular, we obtain strong relations in terms of the von Neumann (Shannon) entropy as well as the min-entropy for measurements in (almost) unitary two-designs, a full set of MUBs, and single qubit measurements in three MUBs each. Second, we resolve the central open question in the noisy-storage model by linking security to the quantum capacity of the adversary's storage device. More precisely, we show that any two party cryptographic primitives can be implemented securely as long as the adversary's storage device has sufficiently low quantum capacity. Our protocol does not need any quantum storage to implement, and is technologically feasible using present-day technology.

arXiv:1111.2026•IEEE Transactions on Information Theory•Jan 24, 2014•50 citations

Efficient Quantum Pseudorandomness

Fernando G. S. L. Brandão, Aram W. Harrow, Michał Horodecki

Randomness is both a useful way to model natural systems and a useful tool for engineered systems, e.g., in computation, communication, and control. Fully random transformations require exponential time for either classical or quantum systems, but in many cases pseudorandom operations can emulate certain properties of truly random ones. Indeed, in the classical realm there is by now a well-developed theory regarding such pseudorandom operations. However, the construction of such objects turns out to be much harder in the quantum case. Here, we show that random quantum unitary time evolutions ("circuits") are a powerful source of quantum pseudorandomness. This gives for the first time a polynomial-time construction of quantum unitary designs, which can replace fully random operations in most applications, and shows that generic quantum dynamics cannot be distinguished from truly random processes. We discuss applications of our result to quantum information science, cryptography, and understanding the self-equilibration of closed quantum dynamics.

arXiv:1605.00713•Physical Review Letters•Apr 29, 2016•53 citations
Randomness is a defining element of mixing processes in nature and an essential ingredient to many protocols in quantum information.In this work, we investigate how much randomness is required to transform a given quantum state into another one.Specifically, we ask whether there is a gap between the power of a classical source of randomness compared to that of a quantum one.We provide a complete answer to these questions, by identifying provably optimal protocols for both classical and quantum sources of randomness, based on a dephasing construction.We find that in order to implement any noisy transition on a d-dimensional quantum system it is necessary and sufficient to have a quantum source of randomness of dimension ffiffiffi d p or a classical one of dimension d.Interestingly, coherences provided by quantum states in a source of randomness offer a quadratic advantage.The process we construct has the additional features to be robust and catalytic; i.e., the source of randomness can be reused.Building upon this formal framework, we illustrate that this dephasing construction can serve as a useful primitive in both equilibration and quantum information theory: We discuss applications describing the smallest measurement device, capturing the smallest equilibrating environment allowed by quantum mechanics, or forming the basis for a cryptographic private quantum channel.We complement the exact analysis with a discussion of approximate protocols based on quantum expanders deriving from discrete Weyl systems.This gives rise to equilibrating environments of remarkably small dimension.Our results highlight the curious feature of randomness that residual correlations and dimension can be traded against each other.
Catalysts are substances that assist transformation of other resourceful objects without being consumed in the process. However, the fact that their ``catalytic power'' is limited and can be depleted is often overlooked, especially in the recently developing theories on catalysis of quantum randomness utilizing building correlation with catalyst. In this work, we establish a resource theory of one-shot catalytic randomness in which uncorrelatedness is consumed in catalysis of randomness. We do so by completely characterizing bipartite unitary operators that can be used to implement catalysis of randomness using partial transpose. By doing so, we find that every catalytic channel is factorizable, and therefore there exists a unital channel that is not catalytic. We define a family of catalytic entropies that quantifies catalytically extractable R\'enyi entropies from a quantum state and show how much the degeneracy of a quantum state can boost the catalytic entropy beyond its ordinary entropy. Based on this, we demonstrate that a randomness source can be actually exhausted after a certain amount of randomness is extracted. We apply this theory to systems under superselection rules that forbids superposition of certain quantum states and find that nonmaximally mixed states can yield the maximal catalytic entropy. We discuss implications of this theory to various topics, including catalytic randomness absorption, the no-secret theorem, and the possibility of multiparty infinite catalysis.
We generalize the theory of catalytic quantum randomness to distributed and dynamical settings. First, we expand the theory of catalytic quantum randomness by calculating the amount of (R\'enyi) entropy catalytically extractable from a distributed or dynamical randomness source. We show that no entropy can be catalytically extracted when one cannot implement local projective measurement on randomness source without altering its state. As an application, we prove that quantum operation cannot be hidden in correlation between two parties without using randomness, which is the dynamical generalization of the no-hiding theorem. Moreover, the formalism of distributed catalysis is applied to develop a formal definition of semantic quantum information and it follows that utilizing semantic information is equivalent to catalysis using a catalyst already correlated with the transforming system. By doing so, we unify the utilization of semantic and nonsemantic quantum information and conclude that one can always extract more information from an incompletely depleted classical randomness source, but it is not possible for quantum randomness sources.
Quantum thermodynamics is a blossoming research program that uses tools and ideas from quantum information theory to extend the laws of thermodynamics to the domain of systems to which the laws of quantum mechanics apply and the thermodynamic limit does not necessarily apply. The contributions of this program are both foundational, in providing an approach to constructively derive the laws of phenomenological thermodynamics from the postulates of unitary quantum mechanics in a rigorous and bottom-up fashion, but also prac- tical, in providing the theory for an increasing number of experiments that attempt to build thermodynamic machines at scales that were previously inaccessible. One key mathematical tool used in quantum thermodynamics is the framework of resource theories, specifically the resource theory of thermal operations, in which the thermodynamic interaction of a system with a heat bath and various additional components such as work batteries, clocks or catalysts are modeled. In this cumulative thesis, various extensions and modifications of this framework are studied in order to derive novel results and insights about the possible thermodynamic evolution of quantum systems. In particular, following a system- atic exposition of the resource theory of thermal operations from first principles, I develop answers to the following questions: i) What is the smallest heat bath required to provide the necessary randomness for a system to undergo a given stochastic or thermodynamical evolution? ii) Does this size differ depending on whether the interaction between bath and system is quantum or classical? iii) How can quantum systems thermodynamically evolve in the presence of catalytic bystander systems and how can this be put to use? iv) What are the thermodynamic state transitions that an agent can operationally affect when she only has access to partial information about the underlying states of system and bath? v) How can we understand the emergence of the canonical ensemble in statistical thermodynamics from quantum mechanics? These questions cover a wide ground, but it will become clear that they can in fact all be discussed using the same formal tools. As such, the answers to the above questions provided in this thesis are both interesting in their own right — showing for example that there exists a gap in how efficiently randomness can be exploited quantumly as compared to classically or that catalytic bystander systems can be used to extract finite amounts of work per particle from macroscopic systems with non-vanishing probability — as well as illustrate the power of quantum thermodynamics as a set of tools to connect quantum mechanics and the theory of thermodynamics more generally.
Randomness can help one to implement quantum maps that cannot be realized in a deterministic fashion.Recently, it was discovered that explicitly treating a randomness source as a quantum system could double the efficiency as a catalyst for some tasks.In this work, we first show that every quantum channel that can be implemented with a randomness source without leaking information to it must be a catalysis.For that purpose, we prove a new no-go theorem that generalizes the no-hiding theorem, the no-secret theorem that states no quantum information can be shared with other systems as a secret without leaking some information.Second, we show that nondegenerate catalysts should be used classically when no extra dimension is allowed, which leads to the fact that the quantum advantage of a catalytic process strictly comes from the uniformness of the randomness source.Finally, we discuss a method to circumvent the previous result that achieves quantum advantage with nondegenerate catalyst uniformized by employing extra work space.
The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. When the source yields a classical string X, many extractor constructions are known. Yet, when considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system. When characterizing the power of a source to supply randomness, it is hence natural to ask how much classical randomness we can extract from a quantum system. To tackle this question, we here take on the study of quantum-to-classical randomness extractors (QC-extractors). We provide constructions of QC-extractors based on measurements in a full set of mutually unbiased bases (MUBs), and certain single qubit measurements. The latter are particularly appealing since they are not only easy to implement, but also appear throughout quantum cryptography. We proceed to prove an upper bound on the maximum amount of randomness that we could hope to extract from any quantum state. Some of our QC-extractors almost match this bound. We show two applications of our results. First, we show that any QC-extractor gives rise to entropic uncertainty relations with respect to quantum side information. Such relations were previously only known for two measurements. In particular, we obtain strong relations in terms of the von Neumann (Shannon) entropy as well as the min-entropy for measurements in (almost) unitary two-designs, a full set of MUBs, and single qubit measurements in three MUBs each. Second, we resolve the central open question in the noisy-storage model by linking security to the quantum capacity of the adversary's storage device. More precisely, we show that any two party cryptographic primitives can be implemented securely as long as the adversary's storage device has sufficiently low quantum capacity. Our protocol does not need any quantum storage to implement, and is technologically feasible using present-day technology.
Randomness is both a useful way to model natural systems and a useful tool for engineered systems, e.g., in computation, communication, and control. Fully random transformations require exponential time for either classical or quantum systems, but in many cases pseudorandom operations can emulate certain properties of truly random ones. Indeed, in the classical realm there is by now a well-developed theory regarding such pseudorandom operations. However, the construction of such objects turns out to be much harder in the quantum case. Here, we show that random quantum unitary time evolutions ("circuits") are a powerful source of quantum pseudorandomness. This gives for the first time a polynomial-time construction of quantum unitary designs, which can replace fully random operations in most applications, and shows that generic quantum dynamics cannot be distinguished from truly random processes. We discuss applications of our result to quantum information science, cryptography, and understanding the self-equilibration of closed quantum dynamics.