Experimentally scalable protocol for identification of correctable codes

The task of finding a correctable encoding that protects against some physical quantum process is in general hard. Two main obstacles are that an exponential number of experiments are needed to gain complete information about the quantum process, and known algorithmic methods for finding correctable encodings involve operations on exponentially large matrices. However, we show that in some cases it is possible to find such encodings with only partial information about the quantum process. Such useful partial information can be systematically extracted by averaging the channel under the action of a set of unitaries in a process known as"twirling". In this paper we prove that correctable encodings for a twirled channel are also correctable for the original channel. We investigate the particular case of twirling over the set of Pauli operators and qubit permutations, and show that the resulting quantum operation can be characterized experimentally in a scalable manner. We also provide a postprocessing scheme for finding unitarily correctable codes for these twirled channels which does not involve exponentially large matrices.


Introduction -
The coherent experimental manipulation of quantum systems, and their application to various quantum information tasks, confronts significant limitations in the presence of noise, and in particular, decoherence. The discovery of quantum error correction codes enables methods for overcoming these limitations whenever the decoherence satisfies various well-defined sets of conditions. Specifically, the appliciability of particular codes depends crucially on the detais of the physical noise model affecting a particular system. The standard approach for experimentally characterizing the full noise model and then assessing the usefulness of a given code are costly procedures, in particular, requiring a number of experiments [1,2] that grows exponentially with the number of subsystems and the (classical) post-processing of matrices [7,8] whose dimension grows similarly exponentially. These limitations make the standard approach infeasible for the kinds of quantum information systems required in practice. In this paper we describe a method that overcomes both of these issues.
First, we demonstrate that partial information about the noise is sufficient to construct correctable encodings. This is motivated by the recent demonstration that valuable partial information about the noise can be extracted by symmetrising or "twirling" the quantum channel [3,4,5]. Twirling consists of averaging the action of a sequence of gates over some distribution of unitaries, in effect randomising aspects of the channel. This leads to scalable protocols which answer questions of practical interest about the noise. In particular, it is possible to experimentally estimate the average gate fidelity between a quantum operation and the identity map [4], as well as to obtain information about noise correlations in a quantum process [5].
We then focus on a particular type of twirl, the Pauli twirl, which has a number of special features that make finding noiseless and unitarily correctable encodings more tractable than the general case. First, the partial information obtained via a Pauli twirl can be accessed with only a polynomial number of experiments, making such experimental characterisation strictly scalable. Then, we discuss how this partial information lends itself to an algebraic algorithm for finding correctable encodings. This new approach does not require the manipulation of exponentially large matrices. We also discuss how these encodings can be verified experimentally in an efficient manner.
Twirled Quantum Operations -Consider a trace preserving linear quantum operation Λ(ρ) = i,j [χ] ij P i ρP j acting on n qubits, where the P i,j ∈ P n are all Pauli operators acting acting on n qubits. Trace-preservation requires that i,j [χ] ij P j P i = 1 1 (in particular, trχ = 1), while Hermiticity-preservation requires [χ] ij = [χ] * ji . Completelypositive (CP) operations have the aditional requirement that χ ≥ 0, which follows from the fact that CP maps can be written as a Choi-Kraus sum Λ(ρ) = k A k ρA † k [10]. This implies that for CP maps, ∀i [χ] ii ≥ 0, so the [χ] ii can be interpreted as probabilities.
Quantum operations require O(2 4n ) parameters to be fully described, and thus require an exponential number of experiments to be fully characterised [1,2]. Due to this exponential cost, it is impractical to obtain a complete description about noise and decoherence acting on even a moderately large system of qubits. Useful partial information about the noise can be obtained by averaging the action of the quantum operation under the composition U • Λ • U † for unitary operations U(ρ) = U ρU † randomly chosen according to some distribution [4,5]. This averaging is known as a "twirl", and the averaged channelΛ(ρ) = dµ(U)U • Λ • U † (ρ) is known as the "twirled channel". The case where the distribution over unitaries is discrete is of particular interest. In that case, the twirled channel is given byΛ(ρ) = Pr where Pr(U i ) is a probability distribution over the U i . This leads us to our first result.
Theorem : Any correctable code for a twirled channelΛ is a correctable code for the original channel Λ up to an aditional unitary correction.
Proof: Without loss of generality, consider Λ(ρ) = k A k ρA † k and a twirl with unitaries {U j } where U 1 = 1 1. Any unitary twirl is unitarily equivalent to a twirl that includes the identity, and this unitary equivalence leads to the aditional unitary correction. A set of Choi-Kraus operators forΛ is then {U † j A k U j }. The existence of a correctable code for H A under the action ofΛ, with recovery operations We now consider some specific twirls which are known to yield twirled channels which can be characterized efficiently via experiments.
Pauli Twirling -It has been demonstrated [4] that twirling a channel Λ by the Pauli group P n yields the effective channel Λ of the form In other words, the off-diagonal elements of χ are eliminated. Channels of this form are known as Pauli channels. From here onΛ will denote the result of Pauli twirling Λ, unless stated otherwise.
Pauli channels have a number of useful properties which facilitate the search for some types of correctable codes. However, the description of a general Pauli channel still requires an exponential number of parameters, and such parameters are not realistically accessible due to this exponential overhead. Instead, one can consider an additional twirl by the group Π n consisting of all qubit permutations. The channelΛ Π resulting from a combination of a P n twirl and a Π n twirl is what we call a permutation invariant Pauli (PIP) channel. Such channels can be written in terms of Choi-Kraus operators where w = (w x , w y , w z ) labels the number of the X, Y and Z Pauli operators, ν w labels the w x + w y + w z qubits over which P w,νw,iw acts non-trivially, and i w labels which single qubit Pauli operator act on each of the qubits. The number K n of different labels w needed to describe such a channel is K n ≡ 1 6 n 3 + n 2 + 11 6 n + 1, while for a fixed w there are K ν w = n wx+wy+wz different ν w , and for fixed w and ν w , there are K i νw = wx+wy+wz wx wy+wz wz different i w . Two equivalent descriptions of the channel (with the same number of parameters) are the Choi-Kraus decomposition and the diagonal representation. The Choi-Kraus decomposition (2) can be rewritten asΛ The M p w are trace-preserving channels which apply each of the P w,νw,iw for a given w with the same probability. The M p w form a basis for PIP channels. Note that, given some n-fold tensor product of Pauli operators P w,νw,iw , we haveΛ Π (P w,νw ,iw ) = λ w P w,νw,iw for some real constant λ w ∈ [−1, 1], since Pauli operators either commute or anti-commute. MoreoverΛ Π is self-dual, i.e.Λ Π =Λ † Π , a fact that follows directly from the definition of Pauli channels. Since the {P w,νw,iw } form an operator basis, it follows that the λ w are the eigenvalues ofΛ Π , with high degeneracy, as they depend only on w. Thus, Pauli channels are diagonalisable and Hermitian.
If we define |A B|ρ ≡ 1 2 n A tr(B † ρ) then the diagonal representation of the channelΛ Π in terms of its eigenopera- The diagonal description ofΛ Π allows for straighforward description of the composition of channels. For example, suppose two Pauli channelsΛ (1) Π andΛ (2) Π are be composed to yieldΛ Π . This simply translates to the multiplication of the corresponding eigenvalues for each of the two channels because all Pauli channels commute.
It is crucial to note that, because there is at most a polynomial number of different eigenvalues, they can be estimated efficiently by determining how a Pauli observable in a w class is scaled under the action of the twirled channel, as described in Ref. [5]. Thus, all the eigenvalues of a PIP channel can be estimated experimentally in a scalable manner.
Unitarily Correctable Subsystems -Let A and B be subsystems of a Hilbert space H = H A ⊗ H B ⊕ H K . Given some channel Λ : B(H) → B(H), we say that H A is a unitarily correctable subsystem [9] if there is a unitary recovery operation R acting on B(H) such that ∀σ A ∈ B(H A ) and That is, H A defines a correctable encoding for Λ that can be returned to its initial location within the system Hilbert space with a single unitary operation. The problem of finding unitarily correctable subsystems for a unital channel is equivalent to finding the structure of the commutant of the noise algebra of Λ † • Λ [9]. In terms of the Choi-Kraus operators {A k } for Λ, this "noise commutant" is defined as the set of operators that commute with the operators {A † k A j }. If Λ is unital and trace preserving, this commutant coincides with the fixed point set of Λ † • Λ (the set of operators which are invariant under the action of this composed channel) [8]. This result can be refined somewhat for diagonalisable channels.
Proposition 1 -Let Λ be a unital, diagonalisable and trace preserving channel with eigenvalues λ i and eigenoperators L i . Then, the noise commutant of Λ † • Λ is the space spanned by eigenoperators L i with eigenvalues |λ i | = 1.
Proof: Λ is unital and trace preserving, thus so is Λ † • Λ. Moreover, Λ is diagonalisable, so Λ † • Λ has eigenoperators L i with eigenvalues λ * i λ i = |λ i | 2 , where the λ i are the eigenvalues of Λ. Since Λ † • Λ is unital, its fixed point set and its noise commutant coincide, and both are given by the space spanned by the eigenoperators L i with |λ i | 2 = 1.
Pauli channels are unital channels, and since they are diagonalisable and Hermitian, these channels have a particularly simple fixed-point set structure. In particular, we immediatelly obtain the following result.
Corollary 1 -LetΛ be a Pauli channel. Then the noise commutant ofΛ † •Λ is the space spanned by the eigenoperators with eigenvalues ±1.
Before continuing, we discuss a special class of UCS codes considered in [11]. We say that a UCS code is unitarily noiseless (UNS) for Λ if it is a UCS of Λ n for all n ≥ 1, where Λ n is the channel Λ composed with itself n times. They are codes for which the recovery operation has the special form U = U A ⊗ R B , that is, a unitary acting only on the subsystem in which information is preserved, and an arbitrary quantum channel on subsystem B. Interestingly, the sets of UCS and UNS codes coincide for Pauli channels.
Corollary 2 -A UCS code of a Pauli channelΛ is also a UNS.
Proof: AsΛ is Hermitian, it commutes with its dualΛ † = Λ, and thus we have that Λ n † •Λ n = (Λ † •Λ) n . Since the eigenvalues ofΛ are real, this implies that the fixed point set ofΛ † •Λ is identical to the fixed point set of Λ n † •Λ n .
PIP channel parameter space -Considering the Liouville representation of the superoperators {M p w } and {M λ w }, it is easy to show that there is a linear invertible map Ω : R Kn → R Kn mapping the p w to the λ w . More explicitly, we have that where N (v, w) is the number of Pauli operators in the Kraus decomposition of an extremal channel (i.e. p v = 1 for some v) which anticommute with some Pauli operator corresponding to the equivalence class w [5]. General expressions for N (v, w) can be obtained by simple counting arguments, which can be computed efficiently. The fixed points ofΛ Π can be thought of as the observables that are conserved under the action ofΛ Π in the Heisenberg picture, asΛ Π is self-dual. Once the fixed points of these channels are determined, in order to determine possible encodings one needs to compute the possible algebras generated by these fixed points. Note that, because of the degeneracy of the eigenvalues of a PIP channel, the existence of a single weight class with eigenvalue 1 corresponds to a large number of Pauli operators which are fixed points of the channel. We now describe how this allows us to find correctable codes for aΛ Π .
Finding Correctable Codes -The identification of the fixed point set of a unital channel can be used to find a UCS using the general algorithm described in Ref. [8,9]. However, this algorithm requires the manipulation of exponentially large matrices, a problem shared with numerical algorithms used to search for more general codes [7]. Given the Pauli operators form an eigenbasis for PIP channels, the task of computing the algebra of conserved observables is relatively simpler than in the general case. One simply has to group the conserved Pauli observables into triplets of observables which satisfy the commutation relations for su (2). These commutation relations can be computed without writing the observables explicitly in a particular representation. By choosing the largest set S of mutually exclusive triplets which commute with each other, one implicitly describes how to encode a noiseless Hilbert space of dimension 2 |S| . Before discussing this algorithm, we point out the following result, which can be obtained by direct computation.
Proposition 2 -Given Pauli operators {P j , P k , P l } satisfying the commutation relations [P j , P k ] = 2i lǫ jkl P l , whereǫ jkl = ǫ jkl s l sj s k , ǫ jkl is the Levi-Civita symbol and s j , s k , s l ∈ {±1, ±i}, then {s j P j , s k P k , s l P l } obey the su(2) commutation relations.
It is clear that {s j P j , s k P k , s l P l } are unitarily related to {X, Y, Z}, as all Pauli operators have the same spectrum and Proposition 2 guarantees they have the same commutation relations. The unitary which performs the encoding is guaranteed to be in the Clifford group, since it maps a set of Pauli operators to another set of Pauli operators with the same commutation relations. Standard techniques can be applied to determine which Clifford group operations implement a desired encoding [12].
This leads to the following algorithm for finding a correctable encoding given the eigenvalues of the PIP channelΛ: (i) Enumerate the Pauli operators with eigenvalues 1 under the action ofΛ, and call thise set F . (ii) Choose a triplet of Pauli operators satisfying the commutation relations in Proposition 2 -if none can be found, the search is over. (iii) Remove this triplet from F , as well as all operators that do not commute with the triplet, and go back to step ii. The number of mutually exclusive triplets found in this manner corresponds to an allowable number of encoded qubits which can be protected from the action ofΛ Π .
Finding unitarily correctable subsystems is similarly simple. One can easily compute the conserved observables of the channelΛ † Π •Λ Π [9]. In the case of PIP channels, this corresponds to finding observables with eigenvalue ±1 for the channelsΛ Π , so that these observables have eigenvalue 1 for Λ † Π •Λ Π =Λ 2 Π . The same procedure described above can be applied to the ±1 eigenspace to find a correctable encoding.
Example 1 -Consider the 2 qubit PIP channel with Kraus operators proportial to {1 11 1, ZZ}. The Pauli operators with eigenvalue 1 are 1 11 1, XX, Y Y, ZZ, XY, Y X, and 1 1Z, Z1 1. Out of this set, {XX, XY, 1 1Z} satisfy the commutation relations, and no other triplets which commute with these can be found, so a single qubit can be encoded noiselessly through this channel.
Example 2 -Consider the 2 qubit PIP channel with Kraus operators proportional to {1 11 1, Y X, XY }. The eigenoperators with eigenvalue 1 are 1 11 1, XY, Y X, and ZZ. There are no triplets with the right commutation relations. The eigenoperators with eigenvalues −1 are 1 1Z, Z1 1, XX, Y Y . If we consider the ±1 eigenspace, we obtain the same eigenoperators with eigenvalue 1 as the previous example, and thus there exists a UCS consisting of a single qubit.
In the case of the previous examples, we want to map the generating set of Pauli operators {1 1X, 1 1Z} to the generating set {XX, 1 1Z}, which can be done by a controlled-NOT gate, where the second qubit is the control, and the first qubit is the target.
The question as to whether this algorithm can find all unitarily correctable encodings for a PIP channels remains open.
Verification of UCS -The conditions for error correction are known to be robust against perturbations [13], and bounds on the fidelity of the encoded states can be computed given complete information about Λ. As argued earlier, this cannot be done in a scalable manner. Moreover, our theorems apply to CP maps, while it is known that there are physical maps which are non-CP [14]. For these reasons, it is important to check what the fidelity of the encoding constructed forΛ Π is under the action of Λ. This can be done by twirling the encoded channel, and estimating its average gate fidelity with the identity channel. The estimate can be done efficiently, using a number of experiments which is logarithmic in the number of encoded qubits, as described in Ref. [5].
Discussion -In this paper we have shown that correctable encodings for a quantum operation can be found by searching for correctable encodings using the twirled version of that quantum operation. We investigated in detail the case of channels twirled by Pauli operators and qubit permutations, and demonstrated a simple scheme for identifying encodings with unitary recovery operations. Such twirled channels are important because they are described by a polynomial number of parameters which are experimentally accessible via a scalable protocol. The scheme does not require the manipulation of exponentially large matrices, and the performance of the constructed correctable code can be estimated experimentally in an efficient manner. Further work is needed to determine whether all unitarily correctable codes for PIP channels can be found through the scheme we described. Moreover, it would be interesting to investigate other twirls that yield more information about the channel which may be used to find more correctable codes.