Counting stabiliser codes for arbitrary dimension

Tanmay Singal1, Che Chiang2, Eugene Hsu3, Eunsang Kim4, Hsi-Sheng Goan2,5,6, and Min-Hsiu Hsieh7

1Institute of Physics, Faculty of Physics, Astronomy and Informatics, Nicolaus Copernicus University, Grudziadzka 5/7, 87-100 Toruń, Poland
2Department of Physics and Center for Theoretical Physics, National Taiwan University, Taipei 10617, Taiwan
3Quantum information center, Chung Yuan Christian University, No. 200, Zhongbei Rd., Zhongli Dist., Taoyuan City 320314, Taiwan
4Department of mathematical Data Science, Hanyang University, Ansan, Gyeonggi-do, 15588, Korea
5Center for Quantum Science and Engineering, National Taiwan University, Taipei 10617, Taiwan
6Physics Division, National Center for Theoretical Sciences, Taipei, 10617, Taiwan
7Hon Hai Quantum Computing Research Center, Taipei, Taiwan

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

In this work, we compute the number of $[[n,k]]_d$ stabilizer codes made up of $d$-dimensional qudits, for arbitrary positive integers $d$. In a seminal work by Gross [23] the number of $[[n,k]]_d$ stabilizer codes was computed for the case when $d$ is a prime (or the power of a prime, i.e., $d=p^m$, but when the qudits are Galois-qudits). The proof in [23] is inapplicable to the non-prime case. For our proof, we introduce a group structure to $[[n,k]]_d$ codes, and use this in conjunction with the Chinese remainder theorem to count the number of $[[n,k]]_d$ codes. Our work overlaps with [23] when $d$ is a prime and in this case our results match exactly, but the results differ for the more generic case. Despite that, the overall order of magnitude of the number of stabilizer codes scales agnostic of whether the dimension is prime or non-prime. This is surprising since the method employed to count the number of stabilizer states (or more generally stabilizer codes) depends on whether $d$ is prime or not. The cardinality of stabilizer states, which was so far known only for the prime-dimensional case (and the Galois qudit prime-power dimensional case) plays an important role as a quantifier in many topics in quantum computing. Salient among these are the resource theory of magic, design theory, de Finetti theorem for stabilizer states, the study and optimisation of the classical simulability of Clifford circuits, the study of quantum contextuality of small-dimensional systems and the study of Wigner-functions. Our work makes available this quantifier for the generic case, and thus is an important step needed to place results for quantum computing with non-prime dimensional quantum systems on the same pedestal as prime-dimensional systems.

► BibTeX data

► References

[1] Mixed-state entanglement and quantum error correction, Bennett C. H., DiVincenzo D. P., Smolin J. A., and Wootters W. K.; Phys. Rev. A 54, 3824 (1996).
https:/​/​doi.org/​10.1103/​PhysRevA.54.3824

[2] Quantum data hiding, D. P. DiVincenzo, D. W. Leung and B. M. Terhal, IEEE Transactions on Information Theory, vol. 48, no. 3, pp. 580-598, March 2002.
https:/​/​doi.org/​10.1109/​18.985948

[3] Randomized benchmarking of quantum gates, Knill E., Leibfried D., R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland Phys. Rev. A 77, 012307 (2008).
https:/​/​doi.org/​10.1103/​PhysRevA.77.012307

[4] Scalable and Robust Randomized Benchmarking of Quantum Processes, Magesan E., Gambetta J. M., Emerson J., Phys. Rev. Lett. 106, 180504 (2011).
https:/​/​doi.org/​10.1103/​PhysRevLett.106.180504

[5] The Heisenberg Representation of Quantum Computers, Gottesmann D., preprint at: arXiv:quant-ph/​9807006. Journal reference: Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics, eds. S. P. Corney, R. Delbourgo, and P. D. Jarvis, pp. 32-43 (Cambridge, MA, International Press, 1999).
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​9807006
arXiv:quant-ph/9807006

[6] Improved simulation of stabilizer circuits, Scott Aaronson and Daniel Gottesman, Phys. Rev. A 70, 052328 (2004).
https:/​/​doi.org/​10.1103/​PhysRevA.70.052328

[7] The question was raised on twitter, and the ensuing discussion, and the answer may be obtained on this link. A twitter account may be required to access the twitter thread.
https:/​/​twitter.com/​markusheinrich_/​status/​1589523953143664642

[8] New techniques for bounding stabilizer rank, Benjamin Lovitz and Vincent Steffan'', Quantum 6, 692 (2022).
https:/​/​doi.org/​10.22331/​q-2022-04-20-692

[9] Quantum systems with finite Hilbert space, A Vourdas 2004 Rep. Prog. Phys. 67 267.
https:/​/​doi.org/​10.1088/​0034-4885/​67/​3/​R03

[10] Kitaev's $\mathbb{Z}_{d}$-code threshold estimates, Duclos-Cianci G., and Poulin D., Phys. Rev. A 87, 062338 (2013).
https:/​/​doi.org/​10.1103/​PhysRevA.87.062338

[11] Fast decoders for qudit topological codes, Anwar H., Brown B. J., Campbell E. T., and Browne D. E., New J. Phys. 16 063038 (2014).
https:/​/​doi.org/​10.1088/​1367-2630/​16/​6/​063038

[12] Magic-State Distillation in All Prime Dimensions Using Quantum Reed-Muller Codes, Campbell E .T, Anwar H., and Browne D. E., Phys. Rev. X 2, 041021 (2012).
https:/​/​doi.org/​10.1103/​PhysRevX.2.041021

[13] Enhanced Fault-Tolerant Quantum Computing in $d$-Level Systems, Campbell E. T., Phys. Rev. Lett. 113, 230501 (2014).
https:/​/​doi.org/​10.1103/​PhysRevLett.113.230501

[14] Towards Low Overhead Magic State Distillation, Krishna A., and Tillich J. P., Phys. Rev. Lett. 123, 070507 (2019).
https:/​/​doi.org/​10.1103/​PhysRevLett.123.070507

[15] A quantum compiler for qudits of prime dimension greater than $3$, Heyfron L. E. and Campbell E. T., arxiv:1902.05634 (2019).
https:/​/​doi.org/​10.48550/​arXiv.1902.05634
arXiv:1902.05634

[16] Quantum computation with realistic magic-state factories, O'Gorman J., and Campbell E. T., Phys. Rev. A 95, 032338 (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.95.032338

[17] “Galois-qudit code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.
https:/​/​errorcorrectionzoo.org/​c/​galois_into_galois

[18] ``Modular-qudit stabilizer code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.
https:/​/​errorcorrectionzoo.org/​c/​qudit_stabilizer

[19] H. Weyl, ``Theory of Groups and Quantum Mechanics", Dutton, New York, (1932).

[20] Unitary Operator Basis, J. Schwinger, PNAS 46, 570 (1960).
https:/​/​doi.org/​10.1073/​pnas.46.4.570

[21] Symmetric informationally complete–positive operator valued measures and the extended Clifford group, D. M. Appleby, J. Math. Phys. 46, 052107 (2005).
https:/​/​doi.org/​10.1063/​1.1896384

[22] Stabilizer states and Clifford operations for systems of arbitrary dimensions and modular arithmetic, E. Hostens, J. Dehaene, and B. De Moor, Phys. Rev. A 71, 042315 (2005).
https:/​/​doi.org/​10.1103/​PhysRevA.71.042315

[23] Hudson’s theorem for finite-dimensional quantum systems, D. Gross , J. Math. Phys. 47, 122107 (2006).
https:/​/​doi.org/​10.1063/​1.2393152

[24] Qudit surface codes and gauge theory with finite cyclic groups, S. S. Bullock and G. K. Brennen, 2007 J. Phys. A: Math. Theor. 40 3481.
https:/​/​doi.org/​10.1088/​1751-8113/​40/​13/​013

[25] Homological error correction: Classical and quantum codes, Bombin H., and Martin-Delgado M. A., J. Math. Phys. 48, 052105 (2007).
https:/​/​doi.org/​10.1063/​1.2731356

[26] The monomial representations of the Clifford group, Appleby D. M., Bengtsson I., Brierley S., Grassl M., Gross D., and Larsson J., Quantum Information and Computation, Vol.12 No.5 & 6, 2012.
https:/​/​doi.org/​10.26421/​QIC12.5-6-3

[27] Standard form of qudit stabilizer groups, Gheorghiu V., Phys. Lett. A, Vol 378, No. 5–6, P 505-509, (2014).
https:/​/​doi.org/​10.1016/​j.physleta.2013.12.009

[28] Geometry of Quantum States. An Introduction to Quantum Entanglement, Bengtsson I., and Życzkowski K., 2nd Edition Cambridge: Cambridge University Press.
https:/​/​doi.org/​10.1017/​9781139207010

[29] ``Algebra", Artin, M., Algebra, second ed., Prentice Hall, Boston, MA, 2011. ISBN 0321998030, 9780321998033. See Chapter 14, ``Linearly Algebra on a Ring''.

[30] D. Gottesman, Stabilizer Codes and Quantum Error Correction, Ph.D. thesis (CalTech).
arXiv:quant-ph/9705052

[31] M. Newman, ``Integral Matrices", Academic Press 1972.

[32] The General Linear Group over a Ring Han, J.-C., (2006). Bull. Korean Math. Soc. 43(3), 619–626 See Corollary 2.8 and 2.9.
http:/​/​koreascience.or.kr/​article/​JAKO200634741588239.page

[33] Algebra, Lang S., 3rd edition, Graduate Texts in Mathematics, Springer New York, NY See Theorem 2.1 and Corollary 2.2.
https:/​/​doi.org/​10.1007/​978-1-4613-0041-0

[34] A Classical Introduction to Modern Number Theory, Ireland K., and Rosen, M., Graduate Texts in Mathematics, 84 (2nd ed.), p.35. Springer (1990).
https:/​/​doi.org/​10.1007/​978-1-4757-2103-4

[35] Introductory Lectures on Rings and Modules, Beachy J, London Mathematical Society Student Texts. Cambridge: Cambridge University Press (1999). See Theorem 1.2.7 (The fundamental homomorphism theorem) on p.27.
https:/​/​doi.org/​10.1017/​CBO9781139173315

[36] Classical Groups and Geometric Algebra, Grove L. C., Graduate Studies in Mathematics) (1st ed.), American Mathematical Society, 2001. Theorem 3.12, p. 27.
https:/​/​doi.org/​10.1090/​gsm/​039

[37] Quantum Computation and Quantum Information: 10th Anniversary Edition, Nielsen, M., & Chuang, I., Cambridge: Cambridge University Press See chapter 10 ``Quantum error correction".
https:/​/​doi.org/​10.1017/​CBO9780511976667

[38] Poulain D., Optimal and efficient decoding of concatenated quantum block codes, Poulain D., Phys. Rev. A 74, 052333 (2006).
https:/​/​doi.org/​10.1103/​PhysRevA.74.052333

[39] Is there a formula for the size of Symplectic group defined over a ring $Z/​p^k Z$?, S. Carnahan.
https:/​/​mathoverflow.net/​q/​87951

[40] Order of $GL(n,\mathbb{Z}/​m \mathbb{Z})$, Vaidyanathan P.
https:/​/​math.stackexchange.com/​q/​2044571

[41] Introduction to analytic number theory, Apostol, Tom M., Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, (1976).
https:/​/​doi.org/​10.1007/​978-1-4757-5579-4

[42] What is a $q$-series?, Baruah N. D. , Berndt B. C., Cooper S. , Huber T., and Schlosser M. J., Ramanujan Rediscovered: Proceedings of a Conference on Elliptic Functions, Partitions, and q-Series in memory of K. Venkatachaliengar: Bangalore, 1-5 June, 2009, eds., Ramanujan Mathematical Society, Mysore, 2010, pp. 31-51.

[43] Estimation de la fonction de Tchebychef $\Theta$ sur le k-ième nombre premier et grandes valeurs de la fonction $\omega(n)$ nombre de diviseurs premiers de $n$, Robin, G., Acta Arithmetica 42 367-389, (1983).
https:/​/​doi.org/​10.4064/​aa-42-4-367-389

[44] Modular arithmetic before C.F. Gauss: Systematizations and discussions on remainder problems in 18th-century Germany, Bullynck M., Historia Mathematica, Vol. 36, Issue 1, 2009.
https:/​/​doi.org/​10.1016/​j.hm.2008.08.009

[45] Negative quasi-probability as a resource for quantum computation, Veitch V., Ferrie C., Gross D., and Emerson J., New J. Phys. 14 113011 (2012).
https:/​/​doi.org/​10.1088/​1367-2630/​14/​11/​113011

[46] The resource theory of stabilizer quantum computation, Veitch V., Mousavian S. A. H., Gottesman D., and Emerson J., New J. Phys. 16 013009 (2014).
https:/​/​doi.org/​10.1088/​1367-2630/​16/​1/​013009

[47] Application of a Resource Theory for Magic States to Fault-Tolerant Quantum Computing, Howard, M. and Campbell, E., Phys. Rev. Lett. 118, 090501 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.118.090501

[48] Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities", Pashayan H., Wallman J. J., and Bartlett S. D., Phys. Rev. Lett. 115, 070501 (2015).
https:/​/​doi.org/​10.1103/​PhysRevLett.115.070501

[49] Robustness of Magic and Symmetries of the stabilizer Polytope, Heinrich, M. and Gross, D. Quantum 3, 132 (2019).
https:/​/​doi.org/​10.22331/​q-2019-04-08-132

[50] Detecting Magic States via Characteristic Functions, Dai, H., Fu, S. & Luo, S., Int J Theor Phys 61, 35 (2022).
https:/​/​doi.org/​10.1007/​s10773-022-05027-8

[51] Comparative Study of Sampling-Based Simulation Costs of Noisy Quantum Circuits, Shigeo Hakkaku and Keisuke Fujii, Phys. Rev. Applied 15, 064027 – Published 10 June 2021.
https:/​/​doi.org/​10.1103/​PhysRevApplied.15.064027

[52] Stim: a fast stabilizer circuit simulator, Gidney C., Quantum 5, 497 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-06-497

[53] Qubit stabilizer states are complex projective 3-designs Kueng R. and Gross D., Preprint available at arXiv:1510.02767.
https:/​/​doi.org/​10.48550/​arXiv.1510.02767
arXiv:1510.02767

[54] Schur–Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations, Gross, D., Nezami, S. and Walter, M., Commun. Math. Phys. 385, 1325–1393 (2021).
https:/​/​doi.org/​10.1007/​s00220-021-04118-7

[55] One-and-a-Half Quantum de Finetti Theorems, Christandl M., König R., Mitchison G. & Renner R., Commun. Math. Phys. 273, 473–498 (2007).
https:/​/​doi.org/​10.1007/​s00220-007-0189-3

[56] Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations, Maslov D. & Roetteler M., IEEE Transactions on Information Theory, vol. 64, no. 7, pp. 4729-4738, (2018).
https:/​/​doi.org/​10.1109/​TIT.2018.2825602

[57] Enumerating all bilocal Clifford distillation protocols through symmetry reduction, Jansen S., Goodenough K., de Bone S., Gijswijt D., & Elkouss D., Quantum 6, 715 (2022).
https:/​/​doi.org/​10.22331/​q-2022-05-19-715

[58] Counting Points in $\mathrm{Sp}\left(2n,\mathbb{F}_q\right)/​$Maximal Parabolic Subgroup, Hanlon G., 18.7w04 (Seminar in Algebra and Number Theory) Handouts, 15th from the top.
https:/​/​math.mit.edu/​~dav/​704handouts.html

[59] In Hanlon2005, a computational error is made in the RHS of the equation which is just below Eq. (7): the RHS should be $q^{\frac{k(k-1)}{2}} \Pi_{i=1}^{\mathbf{k}} \left( q^i - 1 \right)$. This computational error also seeps into the bottom-most expression for $M$ on page (3): an additional factor of $q^k-1$ should be there in the denominator on the RHS. Adjusting for this error, the expressions for $M$ on the bottom of page (3) in Hanlon2005, and $\mathrm{Iso}(n,m,d)$ in Theorem (20) in Gross2006 are equal.

[60] Quantum Contextuality with Stabilizer States, Howard M., Brennan, E., Vala, J., Entropy 15, 2340-2362 (2013).
https:/​/​doi.org/​10.3390/​e15062340

[61] Classical codes in quantum state space, Howard M., J. Phys. A: Math. Theor. 48 495303 (2015).
https:/​/​doi.org/​10.1088/​1751-8113/​48/​49/​495303

[62] Optimal verification of stabilizer states, Dangniam N., Han Y.-G., Zhu H., Phys. Rev. Research 2, 043323 (2020).
https:/​/​doi.org/​10.1103/​PhysRevResearch.2.043323

[63] The axiomatic and the operational approaches to resource theories of magic do not coincide, Heimendahl A., Heinrich M., and Gross D., arXiv:2011.11651.
https:/​/​doi.org/​10.48550/​arXiv.2011.11651
arXiv:2011.11651

[64] Wigner distributions for finite-state systems without redundant phase-point operators, Chaturvedi S., Mukunda N., and Simon R., J. Phys. A: Math. Theor. 43 075302 (2010).
https:/​/​doi.org/​10.1088/​1751-8113/​43/​7/​075302

[65] user0, Reply on math.stackechange to query about embedding an $n$-tuple of $\mathbb{Z}_{d}$ into an invertible $n \times n$ matrix $A$.
https:/​/​math.stackexchange.com/​users/​389981/​user0

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2024-02-26 04:57:11). On SAO/NASA ADS no data on citing works was found (last attempt 2024-02-26 04:57:11).