Haar-random code[1][2][3][4]

Description

Haar-random codewords are generated in a process involving averaging over unitary operations distributed accoding to the Haar measure. Haar-random codes are used to prove statements about the capacity of a quantum channel to transmit quantum information [5], but encoding and decoding in such \(n\)-qubit codes quickly becomes impractical as \(n\to\infty\).

There are different approaches to create Haar-random codewords. In the construction of Ref. [2], codewords are produced by performing a unitarily covariant projective measurement on a typical subspace of a tensor-power state. Reference [2] showed that the capacity of a noisy quantum channel can be achieved by encoding in such Haar-random codes. In particular, Haar-random codes achieve perfect transmission in the \(n\to\infty\)) limit by proving that the encoded information becomes decoupled from the environment. This is a necessary and sufficient condition for successful decoding since measurements of the environment should never reveal the encoded information [6].

Intuitively, coupling with the environment can be decreased by projecting the system onto a random codespace. The more qubits that are randomly discarded, the more the codespace is decoupled from the environment. One may ask what is the least amount of qubits that can be discarded, i.e. the largest remaining codespace, that still achieves decoupling. It can be shown through the decoupling inequality [7] that the largest possible dimension of the random codespace that achieves arbitrarily large decoupling is exponential in the coherent information of the channel. Therefore, there exist codes that can transmit information with rate equal to the coherent information. Furthermore, these codes can be constructed with high probability by performing a Haar-random isometry embedding a \(k\)-dimensional logical subspace into an \(n\)-dimensional physical space, where \(k/n\) is equal to the coherent information. Such an isometry can be produced by QR decomposition of a Gaussian random matrix [8].

Protection

Random code achieve the capacity of any noisy quantum channel.

Rate

The rate of the code is equal to the coherent information of the channel (i.e. the quantum channel capacity).

Parent

Cousin

  • Local Haar-random circuit code — Approximating the random projections through \(t\)-designs is necessary in order to make the protocol practical. Replacing with random Clifford gates is especially convenient since the Clifford group forms a unitary 2-design and produces stabilizer codes.

Zoo code information

Internal code ID: haar_random

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: haar_random

Cite as:
“Haar-random code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/haar_random
BibTeX:
@incollection{eczoo_haar_random, title={Haar-random code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/haar_random} }
Permanent link:
https://errorcorrectionzoo.org/c/haar_random

References

[1]
Peter W. Shor, The quantum channel capacity and coherent information, 2002 (obtained from the MSRI Workshop on Quantum Computation website).
[2]
P. Hayden et al., “A Decoupling Approach to the Quantum Capacity”, Open Systems & Information Dynamics 15, 7 (2008). DOI; quant-ph/0702005
[3]
I. Devetak, “The private classical capacity and quantum capacity of a quantum channel”. quant-ph/0304127
[4]
Rochus Klesse, “A random-coding based proof for the quantum coding theorem”. 0712.2558
[5]
M. M. Wilde, “Preface to the Second Edition”, Quantum Information Theory xi. DOI; 1106.1445
[6]
B. Schumacher and M. A. Nielsen, “Quantum data processing and error correction”, Physical Review A 54, 2629 (1996). DOI; quant-ph/9604022
[7]
M. Horodecki, J. Oppenheim, and A. Winter, “Quantum State Merging and Negative Information”, Communications in Mathematical Physics 269, 107 (2006). DOI; quant-ph/0512247
[8]
G. W. Stewart, “The Efficient Generation of Random Orthogonal Matrices with an Application to Condition Estimators”, SIAM Journal on Numerical Analysis 17, 403 (1980). DOI

Cite as:

“Haar-random code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/haar_random

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/quantum/qubits/haar_random.yml.