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

Cambridge University Press eBooks

Classical Typicality

Mark M. Wilde

Published Nov 2, 2016• 0 citations
Publisher

Abstract

This chapter begins our first technical foray into the asymptotic theory of information. We start with the classical setting in an effort to build up our intuition of asymptotic behavior before delving into the asymptotic theory of quantum information. The central concept of this chapter is the asymptotic equipartition property. The name of this property may sound somewhat technical at first, but it is merely an application of the law of large numbers to a sequence drawn independently and identically from a distribution p X ( x ) for some random variable X . The asymptotic equipartition property reveals that we can divide sequences into two classes when their length becomes large: those that are overwhelmingly likely to occur and those that are overwhelmingly likely not to occur. The sequences that are likely to occur are the typical sequences, and the ones that are not likely to occur are the atypical sequences. Additionally, the size of the set of typical sequences is exponentially smaller than the size of the set of all sequences whenever the random variable generating the sequences is not uniform. These properties are an example of a more general mathematical phenomenon known as “measure concentration,” in which a smooth function over a high-dimensional space or over a large number of random variables tends to concentrate around a constant value with high probability. The asymptotic equipartition property immediately leads to the intuition behind Shannon's scheme for compressing classical information. The scheme first generates a realization of a random sequence and asks the question: Is the produced sequence typical or atypical? If it is typical, compress it. Otherwise, throw it away. The error probability of this compression scheme is non-zero for any fixed length of a sequence, but it vanishes in the asymptotic limit because the probability of the sequence being in the typical set converges to one, while the probability that it is in the atypical set converges to zero. This compression scheme has a straightforward generalization to the quantum setting, in which we wish to compress qubits instead of classical bits. The bulk of this chapter is here to present the many technical details needed to make rigorous statements in the asymptotic theory of information. We begin with an example, follow with the formal definition of a typical sequence and a typical set, and prove the three important properties of a typical set.

DOI
10.1017/9781316809976.017

Related papers

Classical Typicality

Mark M. Wilde

This chapter begins our first technical foray into the asymptotic theory of information. We start with the classical setting in an effort to build up our intuition of asymptotic behavior before delving into the asymptotic theory of quantum information. The central concept of this chapter is the asymptotic equipartition property. The name of this property may sound somewhat technical at first, but it is merely an application of the law of large numbers to a sequence drawn independently and identically from a distribution pX(x) for some random variable X . The asymptotic equipartition property reveals that we can divide sequences into two classes when their length becomes large: those that are overwhelmingly likely to occur and those that are overwhelmingly likely not to occur. The sequences that are likely to occur are the typical sequences, and the ones that are not likely to occur are the atypical sequences. Additionally, the size of the set of typical sequences is exponentially smaller than the size of the set of all sequences whenever the random variable generating the sequences is not uniform. These properties are an example of a more general mathematical phenomenon known as “measure concentration,” in which a smooth function over a high-dimensional space or over a large number of random variables tends to concentrate around a constant value with high probability.

Cambridge University Press eBooks•Apr 18, 2013•0 citations

The Asymptotic Regime

Gilad Gour

Chapter 8 explores the asymptotic regime of quantum information processing, beginning with quantum typicality, which illustrates the convergence of quantum states toward a typical form with increasing copies. This leads to the asymptotic equipartition property (AEP), indicating that with a high number of copies, probability vectors become uniformly distributed. The method of types is introduced next, a tool from classical information theory that classifies sequences based on their statistical properties. This is crucial for understanding the behavior of large quantum systems and has implications for quantum data compression. Advancing to quantum hypothesis testing, the chapter outlines efficient strategies for distinguishing between two quantum states through repeated measurements. Central to this is the Quantum Stein’s lemma, which asserts the exponential decline in the error probability of hypothesis testing as the sample size of quantum systems increases. The chapter highlights the deep interplay between typicality, statistical methods, and hypothesis testing, laying the groundwork for asymptotic interconversion of quantum resources.

Cambridge University Press eBooks•Apr 10, 2025•0 citations

Quantum Typicality

Mark M. Wilde

This chapter marks the beginning of our study of the asymptotic theory of quantum information, where we develop the technical tools underpinning this theory. The intuition for it is similar to the intuition we developed in the previous chapter on typical sequences, but we will find some important differences between the classical and quantum cases. So far, there is not a single known information-processing task in quantum Shannon theory where the tools from this chapter are not helpful in proving the achievability part of a coding theorem. For the most part, we can straight-forwardly import many of the ideas from the previous chapter about typical sequences for use in the asymptotic theory of quantum information. Though, one might initially think that there are some obstacles to doing so. For example, what is the analogy of a quantum information source? Once we have established this notion, how would we determine if a state emitted from a quantum information source is a typical state? In the classical case, a simple way of determining typicality is to inspect all of the bits in the sequence. But there is a problem with this approach in the quantum domain—“looking at quantum bits” is equivalent to performing a measurement and doing so destroys delicate superpositions that we would want to preserve in any subsequent quantum information-processing task. So how can we get around the aforementioned problem and construct a useful notion of quantum typicality? Well, we should not be so destructive in determining the answer to a question when it has only two possible answers.

Cambridge University Press eBooks•Apr 18, 2013•1 citation

Quantum Typicality

Mark M. Wilde

This chapter marks the beginning of our study of the asymptotic theory of quantum information, where we develop the technical tools underpinning this theory. The intuition for it is similar to the intuition we developed in the previous chapter on typical sequences, but we will find some important differences between the classical and quantum cases. So far, there is not a single known information-processing task in quantum Shannon theory where the tools from this chapter are not helpful in proving the achievability part of a coding theorem. For the most part, we can straightforwardly import many of the ideas from the previous chapter about typical sequences for use in the asymptotic theory of quantum information. However, one might initially think that there are some obstacles to doing so. For example, what is the analogy of a quantum information source? Once we have established this notion, how would we determine if a state emitted from a quantum information source is a typical state? In the classical case, a simple way of determining typicality is to inspect all of the bits in the sequence. But there is a problem with this approach in the quantum domain—“looking at quantum bits” is equivalent to performing a measurement and doing so destroys delicate superpositions that we would want to preserve in any subsequent quantum information-processing task. So how can we get around the aforementioned problem and construct a useful notion of quantum typicality? Well, we should not be so destructive in determining the answer to a question when it has only two possible answers. After all, we are only asking “Is the state typical or not?”, and we can be a bit more delicate in the way that we ask this question. As an analogy, suppose Bob is curious to determine whether Alice could join him for dinner at a nice restaurant on the beach. He would likely just phone her and politely ask, “Sweet Alice, are you available for a lovely oceanside dinner?”, as opposed to barging into her apartment, probing through all of her belongings in search of her calendar, and demanding that she join him if she is available.

Cambridge University Press eBooks•Nov 2, 2016•0 citations

A Fully Quantum Asymptotic Equipartition Property

Marco Tomamichel, Roger Colbeck, Renato Renner

The classical asymptotic equipartition property is the statement that, in the limit of a large number of identical repetitions of a random experiment, the output sequence is virtually certain to come from the typical set, each member of which is almost equally likely. In this paper, a fully quantum generalization of this property is shown, where both the output of the experiment and side information are quantum. An explicit bound on the convergence is given, which is independent of the dimensionality of the side information. This naturally leads to a family of REacutenyi-like quantum conditional entropies, for which the von Neumann entropy emerges as a special case.

arXiv:0811.1221•IEEE Transactions on Information Theory•Nov 24, 2009•361 citations

Entropy Concentration and Universal Typicality for Almost i.i.d. Quantum Sources

Nilanjana Datta

We establish two concentration principles for almost i.i.d. quantum sources under the weakly almost i.i.d. condition, the broadest condition in the established hierarchy of almost i.i.d. sources. Our results therefore apply also to Wasserstein- and Mazzola-Sutter-Renner almost i.i.d. sources. Weakly almost i.i.d. sources are sequences of multipartite states whose fixed-size marginals converge, on average, to tensor powers of a reference state, while allowing arbitrary global correlations and entanglement. We prove a noncommutative weak law of large numbers for empirical observables, and a universal entropy-concentration principle showing asymptotic concentration on subspaces of exponential dimension governed by the von Neumann entropy of the reference state. These concentration principles provide a unified and conceptually transparent approach to several information-theoretic applications beyond the i.i.d. setting, including direct proofs of universal compression within classes of weakly almost i.i.d. sources sharing a common reference state and asymmetric quantum hypothesis-testing bounds. They also yield concentration of empirical local-measurement frequencies and of empirical averages of commuting single-site observables, with applications to single-site generalized Gibbs ensembles, together with bounds on smooth and spectral entropies.

quant-pharXiv:2605.20092•May 20, 2026•5 citations
This chapter begins our first technical foray into the asymptotic theory of information. We start with the classical setting in an effort to build up our intuition of asymptotic behavior before delving into the asymptotic theory of quantum information. The central concept of this chapter is the asymptotic equipartition property. The name of this property may sound somewhat technical at first, but it is merely an application of the law of large numbers to a sequence drawn independently and identically from a distribution p X ( x ) for some random variable X . The asymptotic equipartition property reveals that we can divide sequences into two classes when their length becomes large: those that are overwhelmingly likely to occur and those that are overwhelmingly likely not to occur. The sequences that are likely to occur are the typical sequences, and the ones that are not likely to occur are the atypical sequences. Additionally, the size of the set of typical sequences is exponentially smaller than the size of the set of all sequences whenever the random variable generating the sequences is not uniform. These properties are an example of a more general mathematical phenomenon known as “measure concentration,” in which a smooth function over a high-dimensional space or over a large number of random variables tends to concentrate around a constant value with high probability. The asymptotic equipartition property immediately leads to the intuition behind Shannon's scheme for compressing classical information. The scheme first generates a realization of a random sequence and asks the question: Is the produced sequence typical or atypical? If it is typical, compress it. Otherwise, throw it away. The error probability of this compression scheme is non-zero for any fixed length of a sequence, but it vanishes in the asymptotic limit because the probability of the sequence being in the typical set converges to one, while the probability that it is in the atypical set converges to zero. This compression scheme has a straightforward generalization to the quantum setting, in which we wish to compress qubits instead of classical bits. The bulk of this chapter is here to present the many technical details needed to make rigorous statements in the asymptotic theory of information. We begin with an example, follow with the formal definition of a typical sequence and a typical set, and prove the three important properties of a typical set.
This chapter begins our first technical foray into the asymptotic theory of information. We start with the classical setting in an effort to build up our intuition of asymptotic behavior before delving into the asymptotic theory of quantum information. The central concept of this chapter is the asymptotic equipartition property. The name of this property may sound somewhat technical at first, but it is merely an application of the law of large numbers to a sequence drawn independently and identically from a distribution pX(x) for some random variable X . The asymptotic equipartition property reveals that we can divide sequences into two classes when their length becomes large: those that are overwhelmingly likely to occur and those that are overwhelmingly likely not to occur. The sequences that are likely to occur are the typical sequences, and the ones that are not likely to occur are the atypical sequences. Additionally, the size of the set of typical sequences is exponentially smaller than the size of the set of all sequences whenever the random variable generating the sequences is not uniform. These properties are an example of a more general mathematical phenomenon known as “measure concentration,” in which a smooth function over a high-dimensional space or over a large number of random variables tends to concentrate around a constant value with high probability.
Chapter 8 explores the asymptotic regime of quantum information processing, beginning with quantum typicality, which illustrates the convergence of quantum states toward a typical form with increasing copies. This leads to the asymptotic equipartition property (AEP), indicating that with a high number of copies, probability vectors become uniformly distributed. The method of types is introduced next, a tool from classical information theory that classifies sequences based on their statistical properties. This is crucial for understanding the behavior of large quantum systems and has implications for quantum data compression. Advancing to quantum hypothesis testing, the chapter outlines efficient strategies for distinguishing between two quantum states through repeated measurements. Central to this is the Quantum Stein’s lemma, which asserts the exponential decline in the error probability of hypothesis testing as the sample size of quantum systems increases. The chapter highlights the deep interplay between typicality, statistical methods, and hypothesis testing, laying the groundwork for asymptotic interconversion of quantum resources.
This chapter marks the beginning of our study of the asymptotic theory of quantum information, where we develop the technical tools underpinning this theory. The intuition for it is similar to the intuition we developed in the previous chapter on typical sequences, but we will find some important differences between the classical and quantum cases. So far, there is not a single known information-processing task in quantum Shannon theory where the tools from this chapter are not helpful in proving the achievability part of a coding theorem. For the most part, we can straight-forwardly import many of the ideas from the previous chapter about typical sequences for use in the asymptotic theory of quantum information. Though, one might initially think that there are some obstacles to doing so. For example, what is the analogy of a quantum information source? Once we have established this notion, how would we determine if a state emitted from a quantum information source is a typical state? In the classical case, a simple way of determining typicality is to inspect all of the bits in the sequence. But there is a problem with this approach in the quantum domain—“looking at quantum bits” is equivalent to performing a measurement and doing so destroys delicate superpositions that we would want to preserve in any subsequent quantum information-processing task. So how can we get around the aforementioned problem and construct a useful notion of quantum typicality? Well, we should not be so destructive in determining the answer to a question when it has only two possible answers.
This chapter marks the beginning of our study of the asymptotic theory of quantum information, where we develop the technical tools underpinning this theory. The intuition for it is similar to the intuition we developed in the previous chapter on typical sequences, but we will find some important differences between the classical and quantum cases. So far, there is not a single known information-processing task in quantum Shannon theory where the tools from this chapter are not helpful in proving the achievability part of a coding theorem. For the most part, we can straightforwardly import many of the ideas from the previous chapter about typical sequences for use in the asymptotic theory of quantum information. However, one might initially think that there are some obstacles to doing so. For example, what is the analogy of a quantum information source? Once we have established this notion, how would we determine if a state emitted from a quantum information source is a typical state? In the classical case, a simple way of determining typicality is to inspect all of the bits in the sequence. But there is a problem with this approach in the quantum domain—“looking at quantum bits” is equivalent to performing a measurement and doing so destroys delicate superpositions that we would want to preserve in any subsequent quantum information-processing task. So how can we get around the aforementioned problem and construct a useful notion of quantum typicality? Well, we should not be so destructive in determining the answer to a question when it has only two possible answers. After all, we are only asking “Is the state typical or not?”, and we can be a bit more delicate in the way that we ask this question. As an analogy, suppose Bob is curious to determine whether Alice could join him for dinner at a nice restaurant on the beach. He would likely just phone her and politely ask, “Sweet Alice, are you available for a lovely oceanside dinner?”, as opposed to barging into her apartment, probing through all of her belongings in search of her calendar, and demanding that she join him if she is available.
The classical asymptotic equipartition property is the statement that, in the limit of a large number of identical repetitions of a random experiment, the output sequence is virtually certain to come from the typical set, each member of which is almost equally likely. In this paper, a fully quantum generalization of this property is shown, where both the output of the experiment and side information are quantum. An explicit bound on the convergence is given, which is independent of the dimensionality of the side information. This naturally leads to a family of REacutenyi-like quantum conditional entropies, for which the von Neumann entropy emerges as a special case.
We establish two concentration principles for almost i.i.d. quantum sources under the weakly almost i.i.d. condition, the broadest condition in the established hierarchy of almost i.i.d. sources. Our results therefore apply also to Wasserstein- and Mazzola-Sutter-Renner almost i.i.d. sources. Weakly almost i.i.d. sources are sequences of multipartite states whose fixed-size marginals converge, on average, to tensor powers of a reference state, while allowing arbitrary global correlations and entanglement. We prove a noncommutative weak law of large numbers for empirical observables, and a universal entropy-concentration principle showing asymptotic concentration on subspaces of exponential dimension governed by the von Neumann entropy of the reference state. These concentration principles provide a unified and conceptually transparent approach to several information-theoretic applications beyond the i.i.d. setting, including direct proofs of universal compression within classes of weakly almost i.i.d. sources sharing a common reference state and asymmetric quantum hypothesis-testing bounds. They also yield concentration of empirical local-measurement frequencies and of empirical averages of commuting single-site observables, with applications to single-site generalized Gibbs ensembles, together with bounds on smooth and spectral entropies.