Introduction to the structure of free operations in the resource theories of entanglement and magic
The operational and axiomatic definitions have a gap in both entanglement and magic
After three semesters into grad school, I’m realizing that my initial lofty goal of keeping a blog is not going to happen easily. I just prioritize everything else (homework, classes, research, private life) over it. However, I still generate some form of written material - final projects in classes. So, for the next two semesters (of my last three classes), I’m just going to put down here my final projects in the form of blog posts. As final projects are typically done in a rush, I’ll probably clean them up a bit in the process of translating them to markdown from LaTeX.
This particular write-up was for my 2022 Fall semester Quantum Information Theory class taught by Professor Iman Marvian.
Resource theories formalize the notion of valuable resources. A quantum resource theory identifies “free states” that can be created with “free operations” - these are “easy” relative to assumed capabilities. To create “resource states”, one must either have states that contain “some” of the resource or use resource-generating operations. The theory of entanglement (where the resource is entanglement) and the theory of magic (where the resource is “non-stabilizerness”, or “magic”) share a similar structure through the lens of resource theory. Our main focus is a particular hierarchical structure of free operations, namely, the gap between the operational definition and the axiomatic definition of these classes of operations. For entanglement, this is the gap between the classes of Local Operations and Classical Communication (LOCC) and Separable Operators. In the case of magic, the gap is between the classes of Stabilizer Operators and Completely Stabilizer Preserving operators. These gaps have potential implications for protocols related to entanglement and magic state distillation.
The majority of physical theories establish laws based on experimental observations of nature and predict behavior for situations that were not yet verified experimentally. Resource theories in contrast have an inherent process-, or engineering focus as they examine what is possible given a demarcation line in operational capabilities. With roots in Carnot’s explorations of how to exploit thermodynamic non-equilibrium as a resource for heat engines, resource theories provide a framework to organize the concepts and questions of availability and quantification of resources, conversion rates, reversibility, and more. At the core of a quantum resource theory, a set of operations is defined to be the free operations, or resource-non-generating (RNG) operations, and a set of states defined to be the free states. The intuition is that RNG operations and free states are the “easy ones”, i.e. assumed to be available to acquire without incurring high costs. This is in contrast to valuable dynamic resources (resource generating operations), i.e. operations generating static resources (resource states) which are “hard” to acquire. (Chitambar & Gour, 2019).
While there are numerous quantum resource theories, the two we are interested in in this report are the theories of entanglement and magic. It is well known that quantum entanglement can be used as a resource for communication to extend our capabilities and open up use cases like super-dense coding or quantum teleportation (Wilde, 2017). These use cases would be impossible with the “free” separable states, and Local Quantum Operations and Classical Communication (LOCC).
Magic is a resource for universal fault-tolerant quantum computation (FTQC). Under the stabilizer formalism (Gottesman, 1997), large classes of Quantum Error Correction codes can be expressed for both storing and fault tolerantly executing quantum computation in the logical space of these codes. However, stabilizer operations are not universal in the quantum sense, and in-fact are classically efficiently simulatable, as stated by the Gottesman-Knill theorem (missing reference). The term “magic” was introduced in (Bravyi & Kitaev, 2005), where Bravyi and Kitaev showed that for universal quantum computation, one has to inject the valuable resource of magic states or use non-stabilizer operations.
This report focuses on a particular aspect of resource theories of magic and entanglement, namely, the structure of free operations. Free operations are defined either axiomatically or operationally. The operational definition is usually the more natural, stemming from the assumed limitation on capabilities, and having a clear operational interpretation. Axiomatically defined free operations are more mathematically motivated, they have less clear operational meaning; they are the maximal set of operations that map free states to free states. The question we are interested in is whether the axiomatic class is larger or not than the operational one and if yes, what the implications may be.
In entanglement theory, the class of separable channels (SEP) are the axiomatically defined free operations and the operational ones are the LOCC operations. Chitambar et al. (Chitambar et al., 2012) found an operationally interpretable measure of entanglement, that shows a 12.5% gap between SEP and LOCC. In the case of magic theory, a recent counterexample from Heimendahl et al. (Heimendahl et al., 2022) shows that the axiomatically defined class of free operations, Completely Stabilizer Preserving (CSP) is strictly larger than the operationally defined class of stabilizer operations (SO).
The structure of this paper is as follows: in Fundamental concepts we will cover the minimum prerequisite of notations and concepts to understand the separation of these two classes in these two theories. In The structure of free operations we will then get into the details of the separation of these classes in the two theories and finally, in Discussion, we discuss the potential consequences and draw our conclusions.
In this section, we review the concepts and mathematical tools in our two theories of interest and establish notation, mostly following Wilde (Wilde, 2017) for the quantum information theoretical and entanglement-related concepts. To introduce the stabilizer formalism, we will follow multiple sources (Gottesman, 1997), (Aaronson & Gottesman, 2004), (Heimendahl et al., 2022).
State vector and density matrix representation of quantum states
Quantum mechanics is inherently probabilistic in the sense that measurement outcomes on a system are defined by the amplitude square of a set of complex numbers (probability amplitudes) that describe a state as defined by the Born rule. If we can describe the probability amplitudes of a quantum mechanical system with certainty, we call that state a pure state. However, this is far from realistic, usually, we don’t know perfectly the description of a system. Thus, on top of the inherent “quantum probability distribution”, we might have an uncertainty of these amplitudes themselves, layering a “classical probability distribution” over the quantum probability, which we then call mixed states (or noisy states).
Pure quantum states are represented as normalized vectors (or we can think of them as rays) in a potentially composite Hilbert space, i.e. one that allows for a structure of with each sub-Hilbert space having dimension . We will only discuss cases where , i.e. , and where is prime. When , we talk about a Hilbert space of qubits. If , we call each subsystem a qutrit and is the case of qudits. We denote pure states in the Dirac notation as . The members of the computational basis for the qudit Hilbert space of -dimensional qudits will be labeled by the elements of the vector space over the finite field (i.e. a length vector with elements 0 to , with addition is modulo ). For example is a 3-qudit state of dimension 5.
As for mixed states, we don’t know exactly which pure state a system is in, we can represent this lack of knowledge as a probability distribution over possible pure states . This ensemble of states and their probabilities affords a density operator representation , where is the density operator for the pure state defined by the outer product of and . We denote the set of square linear operators acting on with . A density operator is always positive semi-definite, denoted as , and has unit trace, . The set of density operators is denoted as .
Describing change with operators and quantum channels
When the change in a system is noiseless, i.e. the system is closed, it is postulated to be a transformation on the system that is unitary, i.e. . In the vector representation, the effect of is , in the density operator formalism, it is . We will make use of the generalizations of the Pauli group, which is generated by the Pauli-X and Pauli-Z operators for a single qubit, with their action on the computational basis:
The generalized -qudit Pauli-group for dimension qudits is generated by the generalized -qudit X and Z operators, with action:
, where is the th root of unity and is the inner product between and .
However, in a realistic scenario, evolution is not perfectly known, and as such, it can be thought of as a probabilistic mixture of certain operators. Formally, we represent the most general type of evolution an experimenter can impart on a system with the quantum channel formalism. A quantum channel is a map , that must map density operators to density operators, i.e. we have to make sure that the output operator has trace 1 and is positive. This leads to two mandatory properties. The first property a quantum channel has to satisfy is to be trace-preserving (TP), i.e. . The second related to positivity is more subtle, namely that is not enough, because positivity is not closed under the tensor product. Our map has to be completely positive (CP), meaning that for a density operator on a system , even if it is extended with an arbitrary reference system to a density operator , , i.e. the total system stays positive semi-definite. Both of these properties can be tested via the Choi-Jamiokołwski representation of a channel :
, where is the maximally entangled bipartite state on -qudits in the computational basis, and is the identity channel acting on the Hilbert space of -qudits. Namely, is TP if and only if , and is CP if and only if .
We will use the Kraus representation of a quantum channel , where, for a set of operators called Kraus operators , such that they are complete, i.e. , the channel’s effect is expressed as
Measurement of an observable can be described as a quantum channel. An observable is a Hermitian operator, , and thus has a spectral decomposition, say , where are the eigenvalues and are the corresponding eigenstates. When representing a measurement with this observable, the measurement outcomes are the eigenvalues, and after a certain eigenvalue is observed, the system’s state will be projected to the corresponding eigensubspace (of dimension equal to the multiplicity of the eigenvalue), e.g. if has multiplicity 1: , where is the probability of observing .
Finally, we can always find a Stinespring dilation of a channel acting on system , which is a unitary on a larger bipartite system such that on the subsystem its effect (i.e. after tracing out system ) is exactly the channel :
, where is an arbitrary pure state picked from the reference subsystem .
A pure quantum state on a bipartite system is called a tensor product state (TPS) or product state if it can be expressed as a tensor product of two local states: . When there are no states local to the subsystems that can completely describe the state of a pure state, it is entangled. A prototypical example is the Bell state, , the qubit case of .
In the case of mixed states, a density operator is called separable if it is a convex combination of pure product states, i.e. . We say that a mixed state is entangled when it is not separable. The set of separable states is convex, i.e. separable, for all is also separable.
Stabilizer formalism and magic
The stabilizer formalism is an efficient way to represent certain subspaces and states in a Hilbert space. For the class of states called stabilizer states, which we will define precisely in a moment, simulation and computation with stabilizer operations (SO) become classically simulatable. This result is the Gottesman-Knill theorem (Gottesman, 1997), and one of its implications is that it identifies a large subset of quantum computing states and operations that are not classical but can be simulated efficiently classically. If one could simulate everything that a quantum computer can do, the field of quantum computing would be in trouble justifying their efforts. Fortunately, this is not the case, as in order to achieve universality, one has to use extra resources: either use operations outside of the stabilizer operations or use a generous amount of special states called magic states. While we will not need magic states in the later exposition, we remark that Bravyi and Kitaev (Bravyi & Kitaev, 2005) defined magic states as states that are any Clifford transformations of one of these two types of pure magic states:
A state is stabilized by an qudit Hermitian Pauli operator (Hermiticity is a requirement for it to be an observable) if the state is an eigenstate of it with +1 eigenvalue, i.e . For example is stabilized by and is stabilized by .
For two qubits, the situation changes, one might think that for a state, would be sufficient, however, the +1 eigenspace of is two dimensional, both and have +1 eigenvalues. We need then another operator to “filter out” the extra dimension but has as its +1 eigenstate. We find that is a good example. We can also notice that , which is also a stabilizer for , and naturally is also a stabilizer. The set is a group, that is closed under operator multiplication. Also, all of its members commute with each other (i.e. it’s Abelian), thus they can be diagonalized simultaneously. Their shared +1 eigenspace is the stabilized subspace.
In general, we can represent an Abelian group of size with only independent elements, the generators. An Abelian subgroup of the -qudit Pauli group is called a stabilizer group if it does not contain the element (to ensure that all stabilizers are Hermitian). As each generator “halves” the Hilbert space, we can see that a dimensional stabilizer group stabilizes an dimensional subspace. When , we have a stabilizer state. Single qubit stabilizer states are:
, also stabilizes all states, and stabilizes no states. For two-qubit states, stabilizes the Bell state, and in general, is a stabilizer state. The set of stabilizer states is denoted as . Convex combinations of stabilizer states are mixed stabilizer states, and they form stabilizer polytope, denoted . In the single qubit case, this is a simple octahedron on the Bloch sphere as displayed in the figure below.
An -qubit Pauli operator can be represented by bits, with 2 bits for each qubit for the choice of and 1 bit for the global phase, the sign . Thus a stabilizer state can be described by -qubit Pauli operators, and as such it requires only bits. This polynomial cost is in sharp contrast with the complex numbers required to represent a general state.
Beyond the efficient representation of states, it is possible to efficiently update the state if we limit the set of operations to those that map stabilizer states to stabilizer states. As an -qubit stabilizer state can be represented by -qubit Pauli operators, we need these operators to map Pauli operators to Pauli operators. The largest set of unitary operators that satisfy this criterion is the Clifford group, , generated by the , , and the gates. Gottesman and Knill showed that a polynomial number of operations is sufficient to simulate Clifford operations or Pauli measurements.
The structure of free operations
In this section, we will review how the structure of free operations has a gap between axiomatic and operational definitions. In the case of entanglement, after a quick descriptive example for separation from Bennett et al. (Bennett et al., 1999), we follow Chitambar et al. (Chitambar et al., 2012) and for magic, the work by Heimendahl et al. (Heimendahl et al., 2022).
As mentioned before, in entanglement theory, the operational and axiomatic classes of RNG operations are the LOCC and the Separable (SEP) channels.
DefinitionA channel on a Hilbert space of qudits is a separable channel if it has a Kraus decomposition with separable Kraus operators, i.e.:
The set of separable channels is denoted SEP.
An early example by Bennett et al. (Bennett et al., 1999) shows the separation between these two classes, which shows “non-locality without entanglement”. In the figure below, we can see 9 states in a domino notation. Alice and Bob both have a qutrit and they can be in one of the 9 states. They are each a bipartite, separable state and mutually orthogonal to each other. However, in order to distinguish them, one has to do a non-local measurement. To create the states we have to use Separable channels. Let denote the 9 states. Then, the measurement that can distinguish these states can be represented by the Kraus representation , where:
An intuition around how local measurements would act here is that they would always “cut” at least one of the dominoes “in half”, which would make those states indistinguishable. It is laboriously derived and carefully argued in (Bennett et al., 1999) that this measurement operator cannot be implemented by LOCC operations (however, it can be prepared locally!), on the other hand, it is clearly a separable channel. Thus, .
The seminal work from Bennett et al. also quantified the gap, but only to the order of . A central objective of the approach by (Chitambar et al., 2012) was to quantify this gap and define a measure of entanglement that can have a significant difference between the two classes. They managed to show a 12.5% gap using a measure that also has an operational interpretation.
Definition Suppose we have an arbitrary state , and a set of LOCC transformations, each executed with probability , converting into . Then, we call a function an entanglement monotone, when it satisfies the following inequality:
Chitambar et al. defined a monotone that measures the success rate of a particular task: random-EPR pair distillation from W-class states. W-class states are any state that is obtainable from the state with LOCC operations and can be parameterized as . Due to normalization is fully determined by , thus we will label W-class states as . In random-EPR pair distillation, one uses a protocol to transform an initial W-class state to random singlet states between any two of the 3 parties as shown in the figure below.
For , let be a labeling of so that . Then, the function
is an entanglement monotone that strictly decreases on average when a party with maximum component value makes a measurement by Theorem 1 in (Chitambar et al., 2012).
The function can reach 1 if and only if and , and thus for any - thus we have an upper bound on the total probability of the success rate for the random-EPR distillation of . Interestingly, by Theorem 2. in (missing reference), for a class of states, the success rate of LOCC operations can get arbitrarily close to this bound, for any , , but no LOCC operation can exactly reach .
The situation is different for SEP channels as there exists a set of separable measurement operators that can randomly distill a three-qubit W-class state with with probability one:
, where .
The example where the 12.5% difference shows up is the following family of states parameterized by :
While the SEP probability is 1, the LOCC probability is bound by . We plot the two functions in the figure below, where the separation is clearly visible.
The operationally defined set of free operations in the stabilizer formalism is the Stabilizer Operators. We will formally define them here. All the above concepts in Fundamental concepts including the Pauli group , the stabilizer group , the Clifford group , and stabilizer states STAB() readily generalize from qubits to qudits as described in (Heimendahl et al., 2022). Our formal definitions then will be stated using qudits:
Definition A quantum channel mapping -qudits to -qudits, for prime dimension , is defined as a Stabilizer operation when it is a concatenation of operations that fall into one of the following categories:
- preparation of qudits in stabilizer states
- application of a Clifford unitary
- measurement of a Pauli observable
- discarding of qudits
Beyond the above, arbitrary random functions of previous measurement results can act as classical logic to decide which quantum operation to do in each step.
We are taking the stabilizer polytope for -qudits of dimension, to be the set of free states. Then, the axiomatically defined RNG operations are the ones that map the stabilizer-polytope to itself. Similar to positivity, in some resource theories, these channels are not closed under tensor product. In order to enforce closeness under tensor product, the set of completely-RNG channels are of interest - in our case the Completely Stabilizer Preserving (CSP) channels, which - for any arbitrary dimensional extension, maps the dimensional stabilizer polytope to the dimensional stabilizer polytope:
Definition A linear superoperator mapping and qudit spaces of dimension is Completely Stabilizer Preserving if and only if for all .
A CSP operator is also CPTP (Heimendahl et al., 2022), thus they are legitimate quantum channels. How can we determine whether a stabilizer-preserving channel is also CSP? An interesting result (Seddon & Campbell, 2019) utilizes the Choi operator to prove that if the Choi operator (which can be looked at as a state) of is stabilizer-preserving and trace-preserving, then is CSP.
With the definitions out of the way, let’s look at the main result by Heimendahl et al. For the single qudit (qubit) case, . This is intuitively reasonable, as However, starting from two qubits, CSP is strictly larger than SO. Heimendahl et al used the following channel as a counterexample to prove the separation between and :
, where .
This channel can be written as the following three operations:
- measure a projective measurement that distinguishes between and the subspace spanned by , i.e. . This operation cannot be implemented using stabilizer operations. This makes the density matrix block-diagonal:
- Apply partial dephasing with probability 1/2. Off-diagonal terms become half their size:
- Depending on the outcome of the measurement, apply Hadamard on both qubits if was observed. At this point, we get the expression for .
It is possible to show that all three steps are necessary for the channel to be CSP but not SO. In a bit more intuitive explanation, in the geometry of the space of channels, after the first step, we are outside of the CSP class (which is also a polytope). The dephasing step removes sufficient “magic” from the channel to make it CSP and the Hadamard at the end sets the direction the CSP polytope is being approached from to make the channel a vertex.
We will introduce the notion of a Clifford dilation for the sketch of the proof. A superoperator mapping and qudit spaces of dimension has a Clifford dilation if there exists a number , a stabilizer state and a Clifford unitary on qudits such that:
The channels that have a Clifford dilation are the ones that have no measurements or classical randomness.
The sketch of the proof is the following:
- it is shown that is an almost-diagonal channel, meaning that it belongs to that is defined by its effect on the computational basis states:
- This property is then used to show that is extremal in . From here, if is a stabilizer operation, then it would follow that it is an extremal point in as well. This is due to convex subsets inheriting the extremality of points from their supersets.
- It is shown that extremal points in do not have a Clifford dilation.
- However, it can be proved that cannot have a Clifford dilation - thus it must be that but
For larger qubit and qudit dimensions we refer the reader to (Heimendahl et al., 2022). For the full picture though, it is worth mentioning that for larger dimensional qudit states even might not be maximal in terms of free operations. For odd dimensions, resource theories of magic use the Wigner function representation of a function. This is a quasi-probability distribution in phase-space and its total negativity is a magic monotone called mana. Thus, the set of free states can be enlarged to include those with positive Wigner functions, and channels that preserve the positivity of the Wigner function and do so closed under the tensor product are called the completely-Wigner-positivity-preserving () channels. Thus in case of odd dimensions, the full hierarchy is , where the last containment is conjectured to be proper by Heimendahl et al.
Starting from the basics, we reviewed how the structure of the free operations in the theories of entanglement and magic are structured. To explore entanglement, we looked at an early example by Bennett et al. that demonstrated measurement that is separable but not LOCC. Following Chitambar et al., we explored an entanglement monotone specifically designed to measure the maximum success of random-EPR distillation from W-class states, and how it can show a 12.5% gap between LOCC and SEP.
For the theory of magic, Heimendahl et al. did not work with magic monotones, instead, for 2-qubit states, they showed through a specific counter-example that is a completely stabilizer preserving operation but not a stabilizer operation. One could say that their result is similar in spirit to the Bennett et al. example, where careful arguments around a specific set of counterexamples demonstrate the separation of the two classes. Future work might explore actually quantifying the gap in this theory as well for magic distillation tasks. Further implications of the CSP / SO separation could be that the classically simulatable class of channels will become larger, beyond the Gottesman-Knill theorem.
Comments are provided by giscus and Github Discussions. You will have to login with your Github account to comment.
- Chitambar, E., & Gour, G. (2019). Quantum Resource Theories. Reviews of Modern Physics, 91(2), 025001. https://doi.org/10.1103/RevModPhys.91.025001
- Wilde, M. (2017). Quantum information theory (Second edition). Cambridge University Press.
- Gottesman, D. (1997). Stabilizer Codes and Quantum Error Correction. ArXiv:Quant-Ph/9705052. http://arxiv.org/abs/quant-ph/9705052
- Bravyi, S., & Kitaev, A. (2005). Universal Quantum Computation with ideal Clifford gates and noisy ancillas. Physical Review A, 71(2), 022316. https://doi.org/10.1103/PhysRevA.71.022316
- Chitambar, E., Cui, W., & Lo, H.-K. (2012). Increasing Entanglement Monotones by Separable Operations. Physical Review Letters, 108(24), 240504. https://doi.org/10.1103/PhysRevLett.108.240504
- Heimendahl, A., Heinrich, M., & Gross, D. (2022). The axiomatic and the operational approaches to resource theories of magic do not coincide. Journal of Mathematical Physics, 63(11), 112201. https://doi.org/10.1063/5.0085774
- Aaronson, S., & Gottesman, D. (2004). Improved simulation of stabilizer circuits. Physical Review A, 70(5), 052328. https://doi.org/10.1103/PhysRevA.70.052328
- Bennett, C. H., DiVincenzo, D. P., Fuchs, C. A., Mor, T., Rains, E., Shor, P. W., Smolin, J. A., & Wootters, W. K. (1999). Quantum nonlocality without entanglement. Physical Review A, 59(2), 1070–1091. https://doi.org/10.1103/PhysRevA.59.1070
- Seddon, J. R., & Campbell, E. T. (2019). Quantifying magic for multi-qubit operations. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 475(2227), 20190251. https://doi.org/10.1098/rspa.2019.0251