Quantum convolutional code

Last updated February 18, 2020

Quantum block codes are useful in quantum computing and in quantum communications. The encoding circuit for a large block code typically has a high complexity although those for modern codes do have lower complexity.

Quantum convolutional coding theory offers a different paradigm for coding quantum information. The convolutional structure is useful for a quantum communication scenario where a sender possesses a stream of qubits to send to a receiver. The encoding circuit for a quantum convolutional code has a much lower complexity than an encoding circuit needed for a large block code. It also has a repetitive pattern so that the same physical devices or the same routines can manipulate the stream of quantum information.

Quantum convolutional stabilizer codes borrow heavily from the structure of their classical counterparts. Quantum convolutional codes are similar because some of the qubits feed back into a repeated encoding unitary and give the code a memory structure like that of a classical convolutional code. The quantum codes feature online encoding and decoding of qubits. This feature gives quantum convolutional codes both their low encoding and decoding complexity and their ability to correct a larger set of errors than a block code with similar parameters.

Definition

A quantum convolutional stabilizer code acts on a Hilbert space ${\mathcal {H}},$ which is a countably infinite tensor product of two-dimensional qubit Hilbert spaces indexed over integers ≥ 0 $\left\{{\mathcal {H}}_{i}\right\}_{i\in \mathbb {Z} ^{+}}$ :

{\mathcal {H}}={\displaystyle \bigotimes \limits _{i=0}^{\infty }}\ {\mathcal {H}}_{i}.

A sequence $\mathbf {A}$ of Pauli matrices $\left\{A_{i}\right\}_{i\in \mathbb {Z} ^{+}}$ , where

\mathbf {A} ={\displaystyle \bigotimes \limits _{i=0}^{\infty }}\ A_{i},

can act on states in ${\mathcal {H}}$ . Let $\Pi ^{\mathbb {Z} ^{+}}$ denote the set of all Pauli sequences. The support supp $\left(\mathbf {A} \right)$ of a Pauli sequence $\mathbf {A}$ is the set of indices of the entries in $\mathbf {A}$ that are not equal to the identity. The weight of a sequence $\mathbf {A}$ is the size $\left\vert {\text{supp}}\left(\mathbf {A} \right)\right\vert$ of its support. The delay del $\left(\mathbf {A} \right)$ of a sequence $\mathbf {A}$ is the smallest index for an entry not equal to the identity. The degree deg $\left(\mathbf {A} \right)$ of a sequence $\mathbf {A}$ is the largest index for an entry not equal to the identity. E.g., the following Pauli sequence

{\begin{array}{cccccccc}I&X&I&Y&Z&I&I&\cdots \end{array}},

has support $\left\{1,3,4\right\}$ , weight three, delay one, and degree four. A sequence has finite support if its weight is finite. Let $F(\Pi ^{\mathbb {Z} ^{+}})$ denote the set of Pauli sequences with finite support. The following definition for a quantum convolutional code utilizes the set $F(\Pi ^{\mathbb {Z} ^{+}})$ in its description.

A rate $k/n$ -convolutional stabilizer code with $0\leq k\leq n$ is a commuting set ${\mathcal {G}}$ of all $n$ -qubit shifts of a basic generator set ${\mathcal {G}}_{0}$ . The basic generator set ${\mathcal {G}}_{0}$ has $n-k$ Pauli sequences of finite support:

{\mathcal {G}}_{0}=\left\{\mathbf {G} _{i}\in F(\Pi ^{\mathbb {Z} ^{+}}):1\leq i\leq n-k\right\}.

The constraint length $\nu$ of the code is the maximum degree of the generators in ${\mathcal {G}}_{0}$ . A frame of the code consists of $n$ qubits.

A quantum convolutional code admits an equivalent definition in terms of the delay transform or $D$ -transform. The $D$ -transform captures shifts of the basic generator set ${\mathcal {G}}_{0}$ . Let us define the $n$ -qubit delay operator $D$ acting on any Pauli sequence $\mathbf {A} \in \Pi ^{\mathbb {Z} ^{+}}$ as follows:

D\left(\mathbf {A} \right)=I^{\otimes n}\otimes \mathbf {A.}

We can write $j$ repeated applications of $D$ as a power of $D$ :

D^{j}\left(\mathbf {A} \right)=I^{\otimes jn}\otimes \mathbf {A.}

Let $D^{j}\left({\mathcal {G}}_{0}\right)$ be the set of shifts of elements of ${\mathcal {G}}_{0}$ by $j$ . Then the full stabilizer ${\mathcal {G}}$ for the convolutional stabilizer code is

{\mathcal {G}}={\textstyle \bigcup \limits _{j\in \mathbb {Z} ^{+}}}D^{j}\left({\mathcal {G}}_{0}\right).

Operation

The operation of a convolutional stabilizer code is as follows. The protocol begins with the sender encoding a stream of qubits with an online encoding circuit such as that given in (Grassl and Roetteler 2006). The encoding circuit is online if it acts on a few blocks of qubits at a time. The sender transmits a set of qubits as soon as the first unitary finishes processing them. The receiver measures all the generators in ${\mathcal {G}}$ and corrects for errors as he receives the online encoded qubits. He finally decodes the encoded qubits with a decoding circuit. The qubits decoded from this convolutional procedure should be error free and ready for quantum computation at the receiving end.

A finite-depth circuit maps a Pauli sequence with finite weight to one with finite weight (Ollivier and Tillich 2004). It does not map a Pauli sequence with finite weight to one with infinite weight. This property is important because we do not want the decoding circuit to propagate uncorrected errors into the information qubit stream (Johannesson and Zigangirov 1999). A finite-depth decoding circuit corresponding to the stabilizer ${\mathcal {G}}$ exists by the algorithm given in (Grassl and Roetteler 2006).

Example

Forney et al. provided an example of a rate-1/3 quantum convolutional code by importing a particular classical quaternary convolutional code (Forney and Guha 2005). Grassl and Roetteler determined a noncatastrophic encoding circuit for Forney et al.'s rate-1/3 quantum convolutional code (Grassl and Roetteler 2006). The basic stabilizer and its first shift are as follows:

\cdots {\begin{array}{|ccc|ccc|ccc|ccc|ccc|}I&I&I&X&X&X&X&Z&Y&I&I&I&I&I&I\\I&I&I&Z&Z&Z&Z&Y&X&I&I&I&I&I&I\\I&I&I&I&I&I&X&X&X&X&Z&Y&I&I&I\\I&I&I&I&I&I&Z&Z&Z&Z&Y&X&I&I&I\\\end{array}}\cdots

The code consists of all three-qubit shifts of the above generators. The vertical bars are a visual aid to illustrate the three-qubit shifts of the basic generators. The code can correct for an arbitrary single-qubit error in every other frame.

Extensions

Wilde and Brun have integrated the theory of entanglement-assisted stabilizer codes and quantum convolutional codes in a series of articles (Wilde and Brun 2007a, 2007b, 2008, 2009) to form a theory of entanglement-assisted quantum convolutional coding. This theory supposes that a sender and receiver share noiseless bipartite entanglement that they can exploit for protecting a stream of quantum information.

(Wilde 2009), building on work of (Ollivier and Tillich 2004) and (Grassl and Roetteler 2006), also showed how to encode these codes with quantum shift register circuits, a natural extension of the theory of classical shift register circuits.

Related Research Articles

In mathematics convolution is a mathematical operation on two functions that produces a third function expressing how the shape of one is modified by the other. The term convolution refers to both the result function and to the process of computing it. It is defined as the integral of the product of the two functions after one is reversed and shifted.

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence. The DFT is therefore said to be a frequency domain representation of the original input sequence. If the original sequence spans all the non-zero values of a function, its DTFT is continuous, and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle.

In mathematics, a product is the result of multiplying, or an expression that identifies factors to be multiplied. Thus, for instance, 15 is the product of 3 and 5, and $is the product of and .$

In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.

Quantum error correction (QEC) is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is essential if one is to achieve fault-tolerant quantum computation that can deal not only with noise on stored quantum information, but also with faulty quantum gates, faulty quantum preparation, and faulty measurements.

In quantum information theory, a quantum channel is a communication channel which can transmit quantum information, as well as classical information. An example of quantum information is the state of a qubit. An example of classical information is a text document transmitted over the Internet.

In quantum information theory, superdense coding is a quantum communication protocol to transmit two classical bits of information from a sender to a receiver, by sending only one qubit from Alice to Bob, under the assumption of Alice and Bob pre-sharing an entangled state. This protocol was first proposed by Bennett and Wiesner in 1992 and experimentally actualized in 1996 by Mattle, Weinfurter, Kwiat and Zeilinger using entangled photon pairs. By performing one of four quantum gate operations on the (entangled) qubit she possesses, Alice can prearrange the measurement Bob makes. After receiving Alice's qubit, operating on the pair and measuring both, Bob has two classical bits of information. If Alice and Bob do not already share entanglement before the protocol begins, then it is impossible to send two classical bits using 1 qubit, as this would violate Holevo's theorem.

LOCC Method in quantum computation and communication

LOCC, or local operations and classical communication, is a method in quantum information theory where a local (product) operation is performed on part of the system, and where the result of that operation is "communicated" classically to another part where usually another local operation is performed conditioned on the information received.

In physics, in the area of quantum information theory, a Greenberger–Horne–Zeilinger state is a certain type of entangled quantum state that involves at least three subsystems. It was first studied by Daniel Greenberger, Michael Horne and Anton Zeilinger in 1989. Extremely non-classical properties of the state have been observed.

In quantum computing, a graph state is a special type of multi-qubit state that can be represented by a graph. Each qubit is represented by a vertex of the graph, and there is an edge between every interacting pair of qubits. In particular, they are a convenient way of representing certain types of entangled states.

In physics and mathematics, the Pauli group $on 1 qubit is the 16-element matrix group consisting of the 2 \times 2 identity matrix and all of the Pauli matrices$

The theory of quantum error correction plays a prominent role in the practical realization and engineering of quantum computing and quantum communication devices. The first quantum error-correcting codes are strikingly similar to classical block codes in their operation and performance. Quantum error-correcting codes restore a noisy, decohered quantum state to a pure quantum state. A stabilizer quantum error-correcting code appends ancilla qubits to qubits that we want to protect. A unitary encoding circuit rotates the global state into a subspace of a larger Hilbert space. This highly entangled, encoded state corrects for local noisy errors. A quantum error-correcting code makes quantum computation and quantum communication practical by providing a way for a sender and receiver to simulate a noiseless qubit channel given a noisy qubit channel whose noise conforms to a particular error model.

In quantum information and quantum computing, a cluster state is a type of highly entangled state of multiple qubits. Cluster states are generated in lattices of qubits with Ising type interactions. A cluster C is a connected subset of a d-dimensional lattice, and a cluster state is a pure state of the qubits located on C. They are different from other types of entangled states such as GHZ states or W states in that it is more difficult to eliminate quantum entanglement in the case of cluster states. Another way of thinking of cluster states is as a particular instance of graph states, where the underlying graph is a connected subset of a d-dimensional lattice. Cluster states are especially useful in the context of the one-way quantum computer. For a comprehensible introduction to the topic see.

In quantum information science, the concurrence is a state invariant involving qubits.

A decoherence-free subspace (DFS) is a subspace of a quantum system's Hilbert space that is invariant to non-unitary dynamics. Alternatively stated, they are a small section of the system Hilbert space where the system is decoupled from the environment and thus its evolution is completely unitary. DFSs can also be characterized as a special class of quantum error correcting codes. In this representation they are passive error-preventing codes since these subspaces are encoded with information that (possibly) won't require any active stabilization methods. These subspaces prevent destructive environmental interactions by isolating quantum information. As such, they are an important subject in quantum computing, where (coherent) control of quantum systems is the desired goal. Decoherence creates problems in this regard by causing loss of coherence between the quantum states of a system and therefore the decay of their interference terms, thus leading to loss of information from the (open) quantum system to the surrounding environment. Since quantum computers cannot be isolated from their environment and information can be lost, the study of DFSs is important for the implementation of quantum computers into the real world.

Entanglement distillation is the transformation of N copies of an arbitrary entangled state $into some number of approximately pure Bell pairs, using only local operations and classical communication (LOCC).$

Learning with errors (LWE) is the computational problem of inferring a linear $-ary function over a finite ring from given samples some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus be useful in cryptography.$

In the theory of quantum communication, the entanglement-assisted stabilizer formalism is a method for protecting quantum information with the help of entanglement shared between a sender and receiver before they transmit quantum data over a quantum communication channel. It extends the standard stabilizer formalism by including shared entanglement . The advantage of entanglement-assisted stabilizer codes is that the sender can exploit the error-correcting properties of an arbitrary set of Pauli operators. The sender's Pauli operators do not necessarily have to form an Abelian subgroup of the Pauli group $over qubits. The sender can make clever use of her shared ebits so that the global stabilizer is Abelian and thus forms a valid quantum error-correcting code.$

In the theory of quantum communication, the quantum capacity is the highest rate at which quantum information can be communicated over many independent uses of a noisy quantum channel from a sender to a receiver. It is also equal to the highest rate at which entanglement can be generated over the channel, and forward classical communication cannot improve it. The quantum capacity theorem is important for the theory of quantum error correction, and more broadly for the theory of quantum computation. The theorem giving a lower bound on the quantum capacity of any channel is colloquially known as the LSD theorem, after the authors Lloyd, Shor, and Devetak who proved it with increasing standards of rigor.

The KLM scheme or KLM protocol is an implementation of linear optical quantum computing (LOQC), developed in 2000 by Knill, Laflamme and Milburn. This protocol makes it possible to create universal quantum computers solely with linear optical tools. The KLM protocol uses linear optical elements, single photon sources and photon detectors as resources to construct a quantum computation scheme involving only ancilla resources, quantum teleportations and error corrections.

References

H. Ollivier and J.-P. Tillich, “Description of a quantum convolutional code,” Phys. Rev. Lett., vol. 91, no. 17, p. 177902, Oct 2003. Available at https://arxiv.org/abs/quant-ph/0304189
H. Ollivier and J.-P. Tillich, “Quantum convolutional codes: fundamentals.” Available at https://arxiv.org/abs/quant-ph/0401134
G. David Forney and S. Guha, “Simple rate-1/3 convolutional and tail-biting quantum error-correcting codes,” in IEEE International Symposium on Information Theory, 2005. Available at https://arxiv.org/abs/quant-ph/0501099
G. D. Forney, M. Grassl, and S. Guha, “Convolutional and tail-biting quantum error-correcting codes,” IEEE Trans. Inf. Theory, vol. 53, pp. 865–880, 2007. Available at https://arxiv.org/abs/quant-ph/0511016
M. Grassl and M. Roetteler, “Quantum convolutional codes: Encoders and structural properties,” in Forty-Fourth Annual Allerton Conference, 2006. Available at http://www.csl.illinois.edu/allerton/archives/allerton06/PDFs/papers/0285.pdf%5B%5D
M. Grassl and M. Roetteler, “Noncatastrophic encoders and encoder inverses for quantum convolutional codes,” in IEEE International Symposium on Information Theory (quant-ph/0602129), 2006. Available at https://arxiv.org/abs/quant-ph/0602129
R. Johannesson and K. S. Zigangirov, Fundamentals of Convolutional Coding. Wiley-IEEE Press, 1999.
Mark M. Wilde, Hari Krovi, and Todd A. Brun. (2007a) Convolutional Entanglement Distillation. Available at https://arxiv.org/abs/0708.3699
Mark M. Wilde and Todd A. Brun. (2007b) Entanglement-assisted quantum convolutional coding. Available at https://arxiv.org/abs/0712.2223
Mark M. Wilde and Todd A. Brun. Quantum Convolutional Coding with Shared Entanglement: General Structure. Available at https://arxiv.org/abs/0807.3803
Mark M. Wilde. Quantum Coding with Entanglement. Ph.D. Dissertation, University of Southern California, August 2008. Available at https://arxiv.org/abs/0806.4214
Mark M. Wilde and Todd A. Brun. "Extra shared entanglement reduces memory demand in quantum convolutional coding." Phys. Rev. A 79, 032313 (2009). Available at https://arxiv.org/abs/0812.4449
Mark M. Wilde. "Quantum-shift-register circuits." Physical Review A 79, 062325 (2009). Available at https://arxiv.org/abs/0903.3894