Approximate quantum error-correcting code (AQECC)

Approximate quantum error-correcting code (AQECC)[1–7]

Description

Encodes quantum information so that it is possible to approximately recover that information from noise up to an error bound in recovery.

Many families of approximate block quantum codes become exact in the \(n\to\infty\) limit (see children). More generally, codes that become exact for some parameter values are called quasi exact [8].

Protection

Many of the state fidelity conditions that hold exactly for (exact) QECCs can be shown to hold up to some error \(\epsilon\) for approximate QECCs. Approximate correction has been formulated for certain types of correlated noise [9].

Entanglement fidelity

Let \(f(\rho_1,\rho_2)\) be the fidelity between quantum states. Let entanglement fidelity between channels \(\mathcal{N}\) and \(\mathcal{M}\) be defined as \begin{align} F_{\rho}(\mathcal{N},\mathcal{M}) =f((\mathcal{N}\otimes\mathrm{id})\ket{\psi}\bra{\psi},(\mathcal{M}\otimes\mathrm{id})\ket{\psi}\bra{\psi})~, \tag*{(1)}\end{align} where \(\ket{\psi}\) is a purification of the mixed state \(\rho\). The worst-case entanglement fidelity is then defined as \begin{align} F(\mathcal{N},\mathcal{M})=\min_{\rho} F_{\rho}(\mathcal{N},\mathcal{M})~. \tag*{(2)}\end{align}

Now, based on the Bures distance and worst case entanglement fidelity, we define \begin{align} d(\mathcal{N},\mathcal{M})=\sqrt{1-F(\mathcal{N},\mathcal{M})} \tag*{(3)}\end{align} as a measure of distance between quantum channels [6].

Given some encoding map \(\mathcal{U}\) and some noise channel \(\mathcal{E}\), the code described by \(\mathcal{U}\) is \(\epsilon\)-correctable if there exists some quantum channel \(\mathcal{D}\) such that \begin{align} d(\mathcal{D}\mathcal{E}\mathcal{U}(\rho),\rho)\leq \epsilon \tag*{(4)}\end{align} for all logical states \(\rho\) [6]. When \(\epsilon=0\) we can derive the standard Knill-Laflamme conditions [10].

Upper and lower bounds based on the average entanglement fidelity can be derived [6; Eq. (10)][11; Eqs. (138-139)][12; Eq. (139)]. Riemannian optimization techniques can be applied to optimized such quantities since the set of encoding maps \(U\) forms a Stiefel manifold [13].

Complementary channel formulation

Given a noise channel \(\mathcal{E}\), there exists a recovery channel \(\mathcal{D}\) such that \(F(\mathcal{D}\mathcal{E},\mathrm{id})=1-\epsilon\) iff there exists some \(\mathcal{D}'\) such that for complementary channel \(\mathcal{E}^C\), \(F(\mathcal{E}^C,\mathcal{D}')=1-\epsilon\) and \(D'(\rho)=\rho_0\) for some fixed \(\rho_0\). Note that \(F\) denotes worst case entanglement fidelity between channels.

We can generalize this by replacing \(\mathrm{id}\) with some channel \(M\). Given noise channel \(\mathcal{E}\), there exists a recovery channel \(\mathcal{D}\) such that \(F(\mathcal{D}\mathcal{E},\mathcal{M})=1-\epsilon\) iff there exists some \(\mathcal{D}'\) such that for complementary channel \(\mathcal{E}^C\), \(F(\mathcal{E}^C,\mathcal{D}'\mathcal{M}^C)=1-\epsilon\) [6].

Necessary and sufficient approximate error-correction conditions

Analogously to the Knill-Laflamme conditions for (exact) QECCs, there exist various formulations of necessary and sufficient conditions for approximate error correction to determine if some code is \(\epsilon\)-correctable under a noise channel.

Necessary and sufficient conditions for approximate error correction can also be expressed in terms of complementary channels. Given some code defined by projector \(\Pi = U U^\dagger\), \(\Pi\) is \(\epsilon\)-correctable with respect to some noise channel \(\mathcal{E}\) if \begin{align} \Pi E_i^{\dagger}E_j \Pi =\lambda_{ij}\Pi +\Pi B_{ij}\Pi ~, \tag*{(5)}\end{align} where \(\Lambda(\rho)=\mathrm{Tr}(\rho)\sum_{ij} \lambda_{ij}|i\rangle\langle j|\) is a density operator, \begin{align} (\Lambda+B)(\rho)=\Lambda(\rho)+\sum_{ij}\mathrm{Tr}(\rho B_{ij})|i\rangle\langle j| \tag*{(6)}\end{align} is the output state of the complementary noise channel \(\mathcal{E}^C = \Lambda+B\), and the Bures distance \(d(\Lambda+B,\Lambda)\le\epsilon\) [6]. An alternative measure, the AQEC relative entropy, measures the relative entropy between \(\Lambda + B\) and \(\Lambda\) [14]. The non-correctable contributions \(B_{ij}\) can be arranged in a signature vector [15]. The Frobenius norm of the matrix \(B_{ij}\) bounds the difference between the two quantum weight enumerators [16].

In addition to the necessary and sufficient error correction conditions, there exist sufficient conditions for AQECCs. Given a noise channel \(\mathcal{U}(\rho)=\sum_{n} A_n \rho A_n^{\dagger}\) where \(\forall{n}\), \(A_n\) is a Kraus operator, and code projector \(\Pi \), express the following using polar decomposition, \(A_n \Pi =U_n \sqrt{\Pi A_n^{\dagger}A_n \Pi }\), and let \(p_n\) and \(p_n\lambda_n\) be the largest and smallest eigenvalues for \(\Pi A_n^{\dagger}A_n \Pi \). Then, we are guaranteed that if \begin{align}\Pi U_m^{\dagger}U_n \Pi =\delta_{mn} \Pi \land p_n(1-\lambda_n)\le O(f(\epsilon))\tag*{(7)}\end{align} we have a fidelity \(F \geq 1-O(f(\epsilon))\) after recovery [1].

If parts of the Knill-Laflamme conditions are violated, a deterministic recovery operation is not possible. However, a probabilistic recovery and a modified version of the conditions can still be constructed [17].

Universal subspace AQECCs and alpha-bits

Universal subspace approximate error correction is a type of approximate error correction that quantifies protection of information stored in (strict) subspaces of a logical space. See also formulations of error corrections for subsets that are not necessarily subspaces [18].

Given a subspace of a Hilbert space \(\mathsf{S}\) of dimension \(d\), noise channel \(\mathcal{E}\), and encoding \(\mathcal{U}\), we define the subspace as an \(\alpha\)-dit with error \(\epsilon\) if, for all subspaces \(\tilde{\mathsf{S}}\) of dimension less than or equal to \(d^{\alpha}+1\), there exists some channel \(\tilde{\mathcal{D}}\) such that \begin{align}||(\tilde{\mathcal{D}}\circ \mathcal{E}\circ \mathcal{U})|\psi\rangle-|\psi\rangle||_1\leq \epsilon\tag*{(8)}\end{align} for all \(|\psi\rangle\in \tilde{\mathsf{S}}\) [7].

Generalizing the notion of quantum information transmission and capacity of (exact) QECCs, one can achieve an \(\alpha\)-bit transmission rate \(r\) quantum channel \(\mathcal{E}\) iff, for sufficiently large \(d\) and \(n\), and for all \(\epsilon>0\), the channel \(\mathcal{E}^{\otimes n}\) is able to transmit \begin{align}\left\lceil \frac{n r}{\log(d)} \right\rceil\quad \textup{\(\alpha\)-dits}\tag*{(9)}\end{align} with total error \(\epsilon\) across those \(\alpha\)-dits. The \(\alpha\)-bit capacity \(Q\) of \(\mathcal{E}\) is defined as the supremum of achievable transmission rates [7].

Circuit complexity

Code space complexity: One can relate robustness of an approximate quantum code to the quantum circuit complexity [19–22] of creating states in the codespace. For a family of block codes, scaling as order \(O(k/n)\) of a code parameter called the subsystem variance characterizes the transition between code subspaces with low and high circuit complexity [23].

Rate

An extension of the BPT bound to approximate codes is done in Ref. [24].

Encoding

Given a decoder, an encoding that yields the optimal entanglement fidelity can be obtained by solving a semi-definite program [3,25–27]).Variational quantum circuit encoder [28].

Decoding

Given an encoding and a noise channel, a decoder that yields the optimal entanglement fidelity can be obtained by solving a semi-definite program [3,25–27]. This optimal decoder is robust to unexpected variations in the noise channel [29].The decoupling approach a.k.a. the Uhlmann decoder [30–32].Quantum machine-learning based decoders such as quantum convolutional neural networks [33] and quantum autoencoders [34].The Leung recovery map [35] for a noise channel whose Kraus operators \(E_j\) yield a diagonal QEC matrix, \(c_{ij}\propto\delta_{ij}\), has Kraus operators \(\Pi V_j^{\dagger}\), where \(\Pi\) is the codespace projection, and where \(V_j\) is the unitary from the polar decomposition of \(E_j \Pi\). This is the recovery used in the proof of the Knill-Laflamme conditions [36; Thm. 10.1].The Cafaro recovery map [37] can be obtained for noise Kraus operators if there exists a basis of error words with respect to which the uncorrectable piece in the Knill-Laflamme conditions is diagonal; see Ref. [38]. The map recovers information perfectly for strictly correctable noise.The Petz recovery map a.k.a. the transpose map [39–41], a quantum channel determined by the codespace and noise channel, yields an infidelity of recovery that is at most twice away from the infidelity of the best possible recovery [42]. The fidelity can be expressed exactly as a function of the Knill-Laflamme conditions [43; Thm. 1], and it can be used to derive a generalization of the Knill-Laflamme conditions for approximate QECCs [44]. Satisfaction of the Knill-Laflamme conditions is sufficient but not necessary for the Petz recovery map to be the optimal recovery, and a necessary and sufficient condition has been derived [45]. The infidelity of a modified Petz recovery map under erasure can be bounded using the conditional mutual information [24,46,47]. In the case of topological codes, the Petz infidelity is related to the topological entanglement entropy [48]. Modifications include the Petz-like decoder [49].The Yoshida-Kitaev decoder for the Hayden-Preskill protocol [50] can be extended to general QECCs [49].

Notes

See review [51].

Parent

Approximate operator-algebra QECC

Children

Squeezed cat code — Squeezing of coherent states allows for approximate protection against a single photon loss.
Matrix-model code — Matrix-model codes approximately protect against gauge-invariant errors in the large-mode limit.
Squeezed fock-state code — The squeezed Fock-state code approximately protects against loss and dephasing errors, becoming exact in the \(r\to\infty\) limit.
Amplitude-damping (AD) code — Protection against AD noise is typically approximate because the tensor product of Kraus operators with all \(\ell=0\) is typically corrected only up to some order in \(\gamma\) [1,52].
\(U(d)\)-covariant approximate erasure code
W-state code — The W-state code approximately protects against a single erasure while allowing for a universal transversal set of gates.
Quantum error-correcting code (QECC) — QAECCs correcting a noise channel exactly reduce to QECCs.
Conformal-field theory (CFT) code
SYK code — SYK codes are approximately error correcting in that they satisfy certain error-correction conditions based on mutual information [53].
Circuit-to-Hamiltonian approximate code
Eigenstate thermalization hypothesis (ETH) code — ETH codes approximately protect against erasures in the thermodynamic limit.
Neural network code
Singleton-bound approaching AQECC
Magnon code — Magnon codes approximately protect against erasures in the thermodynamic limit.
Valence-bond-solid (VBS) code — VBS codes approximately protect against erasures in the thermodynamic limit.
Landau-level spin code — The Landau-level spin code approximately protects against rotational errors.

Cousins

Topological code — In the case of topological codes, the Petz infidelity is related to the topological entanglement entropy [48].
Renormalization group (RG) cat code — RG cat codes approximately protect against displacements that represent ultraviolet coherent operators.
Numerically optimized bosonic code — Numerically optimized codes arising from optimization routines are often approximate QECCs.
Qudit-into-oscillator code — Approximate QEC techniques of finding the entanglement fidelity can be adapted to bosonic codes with a finite-dimensional codespace [54].
Square-lattice GKP code — Square-lattice GKP codes approximately protect against photon loss [54–56].
Gottesman-Kitaev-Preskill (GKP) code — Approximate error-correction offered by GKP codes yields achievable rates that are a constant away from the capacity of Guassian loss channels [56–59].
Covariant block quantum code — Normalizable constructions of infinite-dimensional \(G\)-covariant codes for continuous \(G\) are approximately error-correcting.
Holographic code — Universal subspace approximate error correction is used to model black holes [60].
Quantum low-weight check (QLWC) code — A family of approximate non-stabilizer QLWC codes with linear distance and rate has been constructed [61] using unary codes that arise from the Feynman-Kitaev clock construction [62].
Local Haar-random circuit qubit code
Approximate secret-sharing code — Secret-sharing codes approximately correct errors on up to \(\lfloor (n-1)/2 \rfloor\) errors.

References

[1]: D. W. Leung et al., “Approximate quantum error correction can lead to better codes”, Physical Review A 56, 2567 (1997) arXiv:quant-ph/9704002 DOI
[2]: A. Y. Kitaev, “Quantum computations: algorithms and error correction”, Russian Mathematical Surveys 52, 1191 (1997) DOI
[3]: M. Reimpell and R. F. Werner, “Iterative Optimization of Quantum Error Correcting Codes”, Physical Review Letters 94, (2005) arXiv:quant-ph/0307138 DOI
[4]: C. Crepeau, D. Gottesman, and A. Smith, “Approximate Quantum Error-Correcting Codes and Secret Sharing Schemes”, (2005) arXiv:quant-ph/0503139
[5]: C. Bény, “Conditions for the approximate correction of algebras”, (2009) arXiv:0907.4207
[6]: C. Bény and O. Oreshkov, “General Conditions for Approximate Quantum Error Correction and Near-Optimal Recovery Channels”, Physical Review Letters 104, (2010) arXiv:0907.5391 DOI
[7]: P. Hayden and G. Penington, “Approximate Quantum Error Correction Revisited: Introducing the Alpha-Bit”, Communications in Mathematical Physics 374, 369 (2020) arXiv:1706.09434 DOI
[8]: D.-S. Wang et al., “Theory of quasi-exact fault-tolerant quantum computing and valence-bond-solid codes”, New Journal of Physics 24, 023019 (2022) arXiv:2105.14777 DOI
[9]: A. Ben-Aroya and A. Ta-Shma, “Approximate quantum error correction for correlated noise”, (2009) arXiv:0909.1466
[10]: C. Bény, “Perturbative Quantum Error Correction”, Physical Review Letters 107, (2011) arXiv:1102.3809 DOI
[11]: J. Tyson, “Two-sided bounds on minimum-error quantum measurement, on the reversibility of quantum dynamics, and on maximum overlap using directional iterates”, Journal of Mathematical Physics 51, (2010) arXiv:0907.3386 DOI
[12]: C. Bény and O. Oreshkov, “Approximate simulation of quantum channels”, Physical Review A 84, (2011) arXiv:1103.0649 DOI
[13]: M. Casanova, K. Ohki, and F. Ticozzi, “Finding Quantum Codes via Riemannian Optimization”, (2024) arXiv:2407.08423
[14]: Y. Zhao and D. E. Liu, “Extracting Error Thresholds through the Framework of Approximate Quantum Error Correction Condition”, (2023) arXiv:2312.16991
[15]: M. Du et al., “Characterizing Quantum Codes via the Coefficients in Knill-Laflamme Conditions”, (2024) arXiv:2410.07983
[16]: Y. Ouyang and C.-Y. Lai, “Linear Programming Bounds for Approximate Quantum Error Correction Over Arbitrary Quantum Channels”, IEEE Transactions on Information Theory 68, 5234 (2022) arXiv:2108.04434 DOI
[17]: S. Dutta, A. Jain, and P. Mandayam, “Smallest quantum codes for amplitude damping noise”, (2024) arXiv:2410.00155
[18]: M. Reichert et al., “Nonlinear quantum error correction”, Physical Review A 105, (2022) arXiv:2112.01858 DOI
[19]: X.-G. Wen, “Topological Order: From Long-Range Entangled Quantum Matter to a Unified Origin of Light and Electrons”, ISRN Condensed Matter Physics 2013, 1 (2013) arXiv:1210.1281 DOI
[20]: L. Susskind, “Computational Complexity and Black Hole Horizons”, (2014) arXiv:1402.5674
[21]: M. H. Freedman and M. B. Hastings, “Quantum Systems on Non-\(k\)-Hyperfinite Complexes: A Generalization of Classical Statistical Mechanics on Expander Graphs”, (2013) arXiv:1301.1363
[22]: S. Aaronson, “The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes”, (2016) arXiv:1607.05256
[23]: J. Yi et al., “Complexity and order in approximate quantum error-correcting codes”, Nature Physics (2024) arXiv:2310.04710 DOI
[24]: S. T. Flammia et al., “Limits on the storage of quantum information in a volume of space”, Quantum 1, 4 (2017) arXiv:1610.06169 DOI
[25]: K. Audenaert and B. De Moor, “Optimizing completely positive maps using semidefinite programming”, Physical Review A 65, (2002) arXiv:quant-ph/0109155 DOI
[26]: A. S. Fletcher, “Channel-Adapted Quantum Error Correction”, (2007) arXiv:0706.3400
[27]: A. S. Fletcher, P. W. Shor, and M. Z. Win, “Structured near-optimal channel-adapted quantum error correction”, Physical Review A 77, (2008) arXiv:0708.3658 DOI
[28]: C. Cao et al., “Quantum variational learning for quantum error-correcting codes”, Quantum 6, 828 (2022) arXiv:2204.03560 DOI
[29]: G. Balló and P. Gurin, “Robustness of channel-adapted quantum error correction”, Physical Review A 80, (2009) arXiv:0905.3838 DOI
[30]: P. Hayden et al., “A Decoupling Approach to the Quantum Capacity”, Open Systems & Information Dynamics 15, 7 (2008) arXiv:quant-ph/0702005 DOI
[31]: F. Dupuis, “The decoupling approach to quantum information theory”, (2010) arXiv:1004.1641
[32]: F. Dupuis et al., “One-Shot Decoupling”, Communications in Mathematical Physics 328, 251 (2014) arXiv:1012.6044 DOI
[33]: I. Cong, S. Choi, and M. D. Lukin, “Quantum convolutional neural networks”, Nature Physics 15, 1273 (2019) arXiv:1810.03787 DOI
[34]: D. F. Locher, L. Cardarelli, and M. Müller, “Quantum Error Correction with Quantum Autoencoders”, Quantum 7, 942 (2023) arXiv:2202.00555 DOI
[35]: D. W. Leung et al., “Approximate quantum error correction can lead to better codes”, Physical Review A 56, 2567 (1997) DOI
[36]: M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2012) DOI
[37]: C. Cafaro and P. van Loock, “Approximate quantum error correction for generalized amplitude-damping errors”, Physical Review A 89, (2014) arXiv:1308.4582 DOI
[38]: S. Dutta, D. Biswas, and P. Mandayam, “Noise-adapted qudit codes for amplitude-damping noise”, (2024) arXiv:2406.02444
[39]: D. Petz, “Sufficient subalgebras and the relative entropy of states of a von Neumann algebra”, Communications in Mathematical Physics 105, 123 (1986) DOI
[40]: D. PETZ, “SUFFICIENCY OF CHANNELS OVER VON NEUMANN ALGEBRAS”, The Quarterly Journal of Mathematics 39, 97 (1988) DOI
[41]: H. Kwon and M. S. Kim, “Fluctuation Theorems for a Quantum Channel”, Physical Review X 9, (2019) arXiv:1810.03150 DOI
[42]: H. Barnum and E. Knill, “Reversing quantum dynamics with near-optimal quantum and classical fidelity”, (2000) arXiv:quant-ph/0004088
[43]: G. Zheng et al., “Near-Optimal Performance of Quantum Error Correction Codes”, Physical Review Letters 132, (2024) arXiv:2401.02022 DOI
[44]: H. K. Ng and P. Mandayam, “Simple approach to approximate quantum error correction based on the transpose channel”, Physical Review A 81, (2010) arXiv:0909.0931 DOI
[45]: B. Li et al., “Optimality Condition for the Transpose Channel”, (2024) arXiv:2410.23622
[46]: O. Fawzi and R. Renner, “Quantum Conditional Mutual Information and Approximate Markov Chains”, Communications in Mathematical Physics 340, 575 (2015) arXiv:1410.0664 DOI
[47]: M. Junge et al., “Universal Recovery Maps and Approximate Sufficiency of Quantum Relative Entropy”, Annales Henri Poincaré 19, 2955 (2018) arXiv:1509.07127 DOI
[48]: Y. Hu and Y. Zou, “Petz map recovery for long-range entangled quantum many-body states”, (2024) arXiv:2408.00857
[49]: T. Utsumi and Y. Nakata, “Explicit decoders using fixed-point amplitude amplification based on QSVT”, (2024) arXiv:2405.06051
[50]: B. Yoshida and A. Kitaev, “Efficient decoding for the Hayden-Preskill protocol”, (2017) arXiv:1710.03363
[51]: A. Jayashankar and P. Mandayam, “Quantum Error Correction: Noise-adapted Techniques and Applications”, (2022) arXiv:2208.00365
[52]: I. L. Chuang, D. W. Leung, and Y. Yamamoto, “Bosonic quantum codes for amplitude damping”, Physical Review A 56, 1114 (1997) DOI
[53]: G. Bentsen, P. Nguyen, and B. Swingle, “Approximate Quantum Codes From Long Wormholes”, Quantum 8, 1439 (2024) arXiv:2310.07770 DOI
[54]: V. V. Albert et al., “Performance and structure of single-mode bosonic codes”, Physical Review A 97, (2018) arXiv:1708.05010 DOI
[55]: B. M. Terhal and D. Weigand, “Encoding a qubit into a cavity mode in circuit QED using phase estimation”, Physical Review A 93, (2016) arXiv:1506.05033 DOI
[56]: K. Noh, V. V. Albert, and L. Jiang, “Quantum Capacity Bounds of Gaussian Thermal Loss Channels and Achievable Rates With Gottesman-Kitaev-Preskill Codes”, IEEE Transactions on Information Theory 65, 2563 (2019) arXiv:1801.07271 DOI
[57]: J. Harrington and J. Preskill, “Achievable rates for the Gaussian quantum channel”, Physical Review A 64, (2001) arXiv:quant-ph/0105058 DOI
[58]: K. Sharma et al., “Bounding the energy-constrained quantum and private capacities of phase-insensitive bosonic Gaussian channels”, New Journal of Physics 20, 063025 (2018) arXiv:1708.07257 DOI
[59]: M. Rosati, A. Mari, and V. Giovannetti, “Narrow bounds for the quantum capacity of thermal attenuators”, Nature Communications 9, (2018) arXiv:1801.04731 DOI
[60]: P. Hayden and G. Penington, “Learning the Alpha-bits of black holes”, Journal of High Energy Physics 2019, (2019) arXiv:1807.06041 DOI
[61]: C. Nirkhe, U. Vazirani, and H. Yuen, “Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States”, (2018) arXiv:1802.07419 DOI
[62]: A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation (American Mathematical Society, 2002) DOI

Page edit log

Milan Tenn (2023-07-25) — most recent
Victor V. Albert (2023-07-24)
Milan Tenn (2023-07-19)
Milan Tenn (2023-07-11)
Milan Tenn (2023-07-03)
Milan Tenn (2023-06-28)
Milan Tenn (2023-06-22)
Milan Tenn (2023-06-20)
Victor V. Albert (2022-08-12)
Philippe Faist (2022-07-15)
Victor V. Albert (2021-12-05)
Manasi Shingane (2021-12-05)

Cite as:

“Approximate quantum error-correcting code (AQECC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/approximate_qecc

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/properties/approximate_qecc.yml.