Quantum convolutional code

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 [math]\displaystyle{ \mathcal{H}, }[/math] which is a countably infinite tensor product of two-dimensional qubit Hilbert spaces indexed over integers ≥ 0 [math]\displaystyle{ \left\{ \mathcal{H}_{i}\right\} _{i\in\mathbb{Z}^{+}} }[/math]:

[math]\displaystyle{ \mathcal{H}= {\displaystyle\bigotimes\limits_{i=0}^{\infty}} \ \mathcal{H}_{i}. }[/math]

A sequence [math]\displaystyle{ \mathbf{A} }[/math] of Pauli matrices [math]\displaystyle{ \left\{ A_{i}\right\} _{i\in\mathbb{Z}^{+}} }[/math], where

[math]\displaystyle{ \mathbf{A}= {\displaystyle\bigotimes\limits_{i=0}^{\infty}} \ A_{i}, }[/math]

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

[math]\displaystyle{ \begin{array} [c]{cccccccc} I & X & I & Y & Z & I & I & \cdots \end{array} , }[/math]

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

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

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

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

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

[math]\displaystyle{ D\left( \mathbf{A}\right) =I^{\otimes n}\otimes\mathbf{A.} }[/math]

We can write [math]\displaystyle{ j }[/math] repeated applications of [math]\displaystyle{ D }[/math] as a power of [math]\displaystyle{ D }[/math]:

[math]\displaystyle{ D^{j}\left( \mathbf{A}\right) =I^{\otimes jn}\otimes\mathbf{A.} }[/math]

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

[math]\displaystyle{ \mathcal{G}= {\textstyle\bigcup\limits_{j\in\mathbb{Z}^{+}}} D^{j}\left( \mathcal{G}_{0}\right) . }[/math]

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 [math]\displaystyle{ \mathcal{G} }[/math] 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 [math]\displaystyle{ \mathcal{G} }[/math] 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:

[math]\displaystyle{ \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 }[/math]

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.

References

• Ollivier, Harold; Tillich, Jean-Pierre (2003). "Description of a Quantum Convolutional Code". Physical Review Letters 91 (17): 177902. doi:10.1103/PhysRevLett.91.177902. PMID 14611378. Bibcode: 2003PhRvL..91q7902O. 
• Ollivier, H.; Tillich, J. -P. (2004). Quantum convolutional codes: Fundamentals. Bibcode: 2004quant.ph..1134O. 
• Forney, G. David (2005). "Simple rate-1/3 convolutional and tail-biting quantum error-correcting codes". Proceedings. International Symposium on Information Theory, 2005. ISIT 2005. pp. 1028–1032. doi:10.1109/ISIT.2005.1523495. ISBN 0-7803-9151-9. 
• David Forney, G. David; Grassl, Markus; Guha, Saikat (2007). "Convolutional and Tail-Biting Quantum Error-Correcting Codes". IEEE Transactions on Information Theory 53 (3): 865–880. doi:10.1109/TIT.2006.890698. 
• 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
• Grassl, Markus; Rotteler, Martin (2006). "Non-catastrophic Encoders and Encoder Inverses for Quantum Convolutional Codes". 2006 IEEE International Symposium on Information Theory. pp. 1109–1113. doi:10.1109/ISIT.2006.261956. ISBN 1-4244-0505-X. 
• R. Johannesson and K. S. Zigangirov, Fundamentals of Convolutional Coding. Wiley-IEEE Press, 1999.
• Wilde, Mark M.; Krovi, Hari; Brun, Todd A. (2010). "Convolutional entanglement distillation". 2010 IEEE International Symposium on Information Theory. pp. 2657–2661. doi:10.1109/ISIT.2010.5513666. ISBN 978-1-4244-7892-7. 
• Wilde, Mark M.; Brun, Todd A. (2010). "Entanglement-assisted quantum convolutional coding". Physical Review A 81 (4): 042333. doi:10.1103/PhysRevA.81.042333. Bibcode: 2010PhRvA..81d2333W. 
• Wilde, Mark M.; Brun, Todd A. (2010). "Quantum convolutional coding with shared entanglement: General structure". Quantum Information Processing 9 (5): 509–540. doi:10.1007/s11128-010-0179-9. 
• Wilde, Mark M. (2008). Quantum Coding with Entanglement. 
• Wilde, Mark M.; Brun, Todd A. (2009). "Extra shared entanglement reduces memory demand in quantum convolutional coding". Physical Review A 79 (3): 032313. doi:10.1103/PhysRevA.79.032313. Bibcode: 2009PhRvA..79c2313W. 
• Wilde, Mark M. (2009). "Quantum-shift-register circuits". Physical Review A 79 (6): 062325. doi:10.1103/PhysRevA.79.062325. Bibcode: 2009PhRvA..79f2325W. 

Further reading

Publications

• Houshmand, Monireh; Wilde, Mark M. (2013). "Recursive Quantum Convolutional Encoders are Catastrophic: A Simple Proof". IEEE Transactions on Information Theory 59 (10): 6724–6731. doi:10.1109/TIT.2013.2272932. 
• Lai, Ching-Yi; Hsieh, Min-Hsiu; Lu, Hsiao-Feng (2016). "On the Mac Williams Identity for Classical and Quantum Convolutional Codes". IEEE Transactions on Communications 64 (8): 3148–3159. doi:10.1109/TCOMM.2016.2585641. 
• Poulin, David; Tillich, Jean-Pierre; Ollivier, Harold (2007). Quantum serial turbo-codes. 
• Djordjevic, Ivan (2012). Quantum information processing and quantum error correction: an engineering approach.. Academic press. ISBN 9780123854919. 
• Brun, Todd A. (2013). Lidar, Daniel A.. ed. Quantum error correction.. Cambridge University Press. ISBN 9780521897877.