Draft:Quantum Tanner code
 | Review waiting, please be patient.
This may take 5 weeks or more, since drafts are reviewed in no specific order. There are 2,572 pending submissions waiting for review.
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
Reviewer tools
|
A quantum Tanner code is a quantum error-correcting code obtained by adapting the Tanner-code construction to a two-dimensional expander complex. Anthony Leverrier and Gilles Zémor introduced quantum Tanner codes in 2022.[1] With suitable local codes and expansion conditions, they form asymptotically good quantum low-density parity-check (qLDPC) codes.
Background
[edit]In a classical Tanner code, a long code is specified by a graph and a short local code. Code symbols are associated with graph edges and each vertex imposes the constraints of the local code on its incident edges. Classical expander codes use this construction on spectral expander graphs.
Quantum Tanner codes replace the graph by a left–right Cayley square complex. The squares of the complex carry qubits. Two graphs derived from the same complex are equipped with classical Tanner codes that determine the X- and Z-type constraints of a CSS code. A dual-containment condition on the local codes ensures that the X and Z stabilizers commute.[1]
Parameters
[edit]The construction uses robust local tensor codes together with expansion of the square complex. Leverrier and Zémor proved that appropriate choices give code families with constant encoding rate and minimum distance linear in the number of physical qubits.[1] Thus both the rate and relative distance remain bounded away from zero as the block length grows.
Quantum Tanner codes are closely related to the asymptotically good lifted-product codes of Panteleev and Kalachev. Their construction also shares ingredients with the classical locally testable codes constructed from left–right Cayley complexes.[1][2]
Decoding
[edit]Leverrier and Zémor subsequently introduced sequential and parallel decoders for quantum Tanner codes. Under the expansion and robustness assumptions used in the construction, the algorithms correct adversarial errors whose weight is a constant fraction of the block length. The sequential algorithm runs in linear time and the parallel version in logarithmic time.[3] Related decoding methods also apply to expander lifted-product codes.[4]
See also
[edit]- 1 2 3 4 Leverrier, Anthony; Zémor, Gilles (2022). "Quantum Tanner Codes". 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). pp. 872–883. arXiv:2202.13641. doi:10.1109/FOCS54457.2022.00117.
- ↑ "Theory of error-correcting codes: fundamental results to go towards the quantum computer". Inria. 28 October 2022. Retrieved 2 September 2026.
- ↑ Leverrier, Anthony; Zémor, Gilles (2023). "Decoding Quantum Tanner Codes". IEEE Transactions on Information Theory. 69 (8): 5100–5115. arXiv:2208.05537. doi:10.1109/TIT.2023.3267945.
- ↑ Leverrier, Anthony; Zémor, Gilles (2024). "Efficient Decoding up to a Constant Fraction of the Code Length for Asymptotically Good Quantum Codes". ACM Transactions on Algorithms. arXiv:2206.07571. doi:10.1145/3663763.