Un-Weyl-ing the Clifford Hierarchy

Tefjol Pllaha; Narayanan Rengaswamy; Olav Tirkkonen; Robert Calderbank

doi:10.22331/q-2020-12-11-370

Un-Weyl-ing the Clifford Hierarchy

Tefjol Pllaha¹, Narayanan Rengaswamy², Olav Tirkkonen¹, and Robert Calderbank³

¹Department of Communications and Networking, Aalto University, Finland
²Department of Electrical and Computer Engineering, University of Arizona, Tucson, AZ, USA
³Department of Electrical and Computer Engineering, Duke University, NC, USA

Published:	2020-12-11, volume 4, page 370
Eprint:	arXiv:2006.14040v4
Doi:	https://doi.org/10.22331/q-2020-12-11-370
Citation:	Quantum 4, 370 (2020).

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

Abstract

The teleportation model of quantum computation introduced by Gottesman and Chuang (1999) motivated the development of the Clifford hierarchy. Despite its intrinsic value for quantum computing, the widespread use of magic state distillation, which is closely related to this model, emphasizes the importance of comprehending the hierarchy. There is currently a limited understanding of the structure of this hierarchy, apart from the case of diagonal unitaries (Cui et al., 2017; Rengaswamy et al. 2019). We explore the structure of the second and third levels of the hierarchy, the first level being the ubiquitous Pauli group, via the Weyl (i.e., Pauli) expansion of unitaries at these levels. In particular, we characterize the support of the standard Clifford operations on the Pauli group. Since conjugation of a Pauli by a third level unitary produces traceless Hermitian Cliffords, we characterize their Pauli support as well. Semi-Clifford unitaries are known to have ancilla savings in the teleportation model, and we explore their Pauli support via symplectic transvections. Finally, we show that, up to multiplication by a Clifford, every third level unitary commutes with at least one Pauli matrix. This can be used inductively to show that, up to a multiplication by a Clifford, every third level unitary is supported on a maximal commutative subgroup of the Pauli group. Additionally, it can be easily seen that the latter implies the generalized semi-Clifford conjecture, proven by Beigi and Shor (2010). We discuss potential applications in quantum error correction and the design of flag gadgets.

► BibTeX data

@article{Pllaha2020unweylingclifford,
  doi = {10.22331/q-2020-12-11-370},
  url = {https://doi.org/10.22331/q-2020-12-11-370},
  title = {Un-{W}eyl-ing the {C}lifford {H}ierarchy},
  author = {Pllaha, Tefjol and Rengaswamy, Narayanan and Tirkkonen, Olav and Calderbank, Robert},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {370},
  month = dec,
  year = {2020}
}

► References

[1] Salman Beigi and Peter W. Shor. $\mathcal{C}_3$, semi-Clifford and generalized semi-Clifford operations. Quantum Info. Comput., 10 (1): 41–59, January 2010. URL http://arxiv.org/abs/0810.5108.
arXiv:0810.5108

[2] P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani Roychowdhury, and Farrokh Vatan. On universal and fault-tolerant quantum computing: A novel basis and a new constructive proof of universality for Shor's basis. page 486, USA, 1999. IEEE Computer Society. https://doi.org/10.1109/SFFCS.1999.814621.
https://doi.org/10.1109/SFFCS.1999.814621

[3] Sergey Bravyi and Jeongwan Haah. Magic-state distillation with low overhead. Phys. Rev. A, 86 (5): 052329, 2012. https://doi.org/10.1103/PhysRevA.86.052329.
https://doi.org/10.1103/PhysRevA.86.052329

[4] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A, 71: 022316, Feb 2005. https://doi.org/10.1103/PhysRevA.71.022316.
https://doi.org/10.1103/PhysRevA.71.022316

[5] Robert A. Calderbank, Stephen Howard, Sina Jafarpour, and Jeremy Kent. Sparse approximation and compressed sensing using the Reed-Muller sieve. Technical Report, Princeton University, TR-888-10, 2010. URL https://www.cs.princeton.edu/research/techreps/TR-888-10.
https://www.cs.princeton.edu/research/techreps/TR-888-10

[6] Robert A. Calderbank, Peter J. Cameron, William M. Kantor, and Jaap J. Seidel. $\mathbb{Z}_4$-Kerdock codes, orthogonal spreads, and extremal Euclidean line-sets. Proceedings of the London Mathematical Society, 75 (2): 436–480, 1997. https://doi.org/10.1112/S0024611597000403.
https://doi.org/10.1112/S0024611597000403

[7] Robert A. Calderbank, Eric M. Rains, Peter W. Shor, and Neil J. A. Sloane. Quantum error correction via codes over ${\rm GF}(4)$. IEEE Trans. Inform. Theory, 44 (4): 1369–1387, 1998. https://doi.org/10.1109/18.681315.
https://doi.org/10.1109/18.681315

[8] Robert A. Calderbank, Stephen Howard, and Sina Jafarpour. Construction of a large class of matrices satisfying a statistical isometry property. In IEEE Journal of Selected Topics in Signal Processing, Special Issue on Compressive Sensing, volume 4, pages 358–374, 2010. https://doi.org/10.1109/JSTSP.2010.2043161.
https://doi.org/10.1109/JSTSP.2010.2043161

[9] David Callan. The generation of $\mbox{\rm Sp}({\mathbb F}_2)$ by transvections. J. Algebra, 42 (2): 378–390, 1976. https://doi.org/10.1016/0021-8693(76)90105-8.
https://doi.org/10.1016/0021-8693(76)90105-8

[10] Christopher Chamberland and Michael E. Beverland. Flag fault-tolerant error correction with arbitrary distance codes. Quantum, 2: 53, 2018. https://doi.org/10.22331/q-2019-05-20-143.
https://doi.org/10.22331/q-2019-05-20-143

[11] Rui Chao and Ben W Reichardt. Quantum Error Correction with Only Two Extra Qubits. Phys. Rev. Lett., 121 (5): 050502, 2018a. https://doi.org/10.1103/PhysRevLett.121.050502.
https://doi.org/10.1103/PhysRevLett.121.050502

[12] Rui Chao and Ben W Reichardt. Fault-tolerant quantum computation with few qubits. npj Quantum Inf., 4 (1): 42, 2018b. https://doi.org/10.1038/s41534-018-0085-z.
https://doi.org/10.1038/s41534-018-0085-z

[13] Rui Chao and Ben W. Reichardt. Flag fault-tolerant error correction for any stabilizer code. PRX Quantum, 1: 010302, Sep 2020. https://doi.org/10.1103/PRXQuantum.1.010302.
https://doi.org/10.1103/PRXQuantum.1.010302

[14] Shawn X. Cui, Daniel Gottesman, and Anirudh Krishna. Diagonal gates in the Clifford hierarchy. Phys. Rev. A, 95: 012329, Jan 2017. https://doi.org/10.1103/PhysRevA.95.012329.
https://doi.org/10.1103/PhysRevA.95.012329

[15] Kathleen S. Gibbons, Matthew J. Hoffman, and William K. Wootters. Discrete phase space based on finite fields. Phys. Rev. A, 70: 062101, Dec 2004. https://doi.org/10.1103/PhysRevA.70.062101.
https://doi.org/10.1103/PhysRevA.70.062101

[16] Daniel Gottesman. Stabilizer codes and quantum error correction. PhD thesis, California Institute of Technology, 1997. https://doi.org/10.7907/rzr7-dt72.
https://doi.org/10.7907/rzr7-dt72

[17] Daniel Gottesman and Isaac L. Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402 (6760): 390–393, 1999. https://doi.org/10.1038/46503.
https://doi.org/10.1038/46503

[18] David Gross. Hudson’s theorem for finite-dimensional quantum systems. Journal of Mathematical Physics, 47 (12): 122107, 2006. https://doi.org/10.1063/1.2393152.
https://doi.org/10.1063/1.2393152

[19] David Gross and Maarten Van den Nest. The LU-LC conjecture, diagonal local operations and quadratic forms over GF(2). Quantum Inf. Comput., 8 (3-4): 263–281, 2007. URL http://arxiv.org/abs/0707.4000.
arXiv:0707.4000

[20] Robert Koenig and John A. Smolin. How to efficiently select an arbitrary Clifford group element. J. Math. Phys., 55 (12): 122202, Dec 2014. https://doi.org/10.1063/1.4903507.
https://doi.org/10.1063/1.4903507

[21] Florence J. MacWilliams and Neil J. A. Sloane. The theory of error-correcting codes, volume 16. Elsevier, 1977.

[22] Dmitri Maslov and Martin Roetteler. Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations. IEEE Transactions on Information Theory, 64 (7): 4729–4738, 2018. https://doi.org/10.1109/TIT.2018.2825602.
https://doi.org/10.1109/TIT.2018.2825602

[23] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, Cambridge, 2000.

[24] Onorato T. O'Meara. Symplectic groups, volume 16 of Mathematical Surveys. American Mathematical Society, Providence, R.I., 1978.

[25] Tefjol Pllaha, Olav Tirkkonen, and Robert A. Calderbank. Reconstruction of multi-user binary subspace chirps. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 531–536, 2020. https://doi.org/10.1109/ISIT44484.2020.9174412.
https://doi.org/10.1109/ISIT44484.2020.9174412

[26] Narayanan Rengaswamy, Robert A. Calderbank, Henry D. Pfister, and Swanand Kadhe. Synthesis of logical Clifford operators via symplectic geometry. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 791–795, 2018. https://doi.org/10.1109/ISIT.2018.8437652.
https://doi.org/10.1109/ISIT.2018.8437652

[27] Narayanan Rengaswamy, Robert Calderbank, Michael Newman, and Henry D. Pfister. On Optimality of CSS Codes for Transversal $T$. arXiv preprint arXiv:1910.09333, 2019a. URL http://arxiv.org/abs/1910.09333.
arXiv:1910.09333

[28] Narayanan Rengaswamy, Robert Calderbank, and Henry D. Pfister. Unifying the Clifford hierarchy via symmetric matrices over rings. Phys. Rev. A, 100 (2): 022304, 2019b. https://doi.org/10.1103/PhysRevA.100.022304.
https://doi.org/10.1103/PhysRevA.100.022304

[29] Narayanan Rengaswamy, Robert Calderbank, Michael Newman, and Henry D. Pfister. Classical coding problem from transversal t gates. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 1891–1896, 2020. https://doi.org/10.1109/ISIT44484.2020.9174408.
https://doi.org/10.1109/ISIT44484.2020.9174408

[30] Theerapat Tansuwannont, Christopher Chamberland, and Debbie Leung. Flag fault-tolerant error correction, measurement, and quantum computation for cyclic Calderbank-Shor-Steane codes. Phys. Rev. A, 101 (1): 012342, 2020. https://doi.org/10.1103/PhysRevA.101.012342.
https://doi.org/10.1103/PhysRevA.101.012342

[31] Victor Veitch, S A Hamed Mousavian, Daniel Gottesman, and Joseph Emerson. The resource theory of stabilizer quantum computation. New Journal of Physics, 16 (1): 013009, jan 2014. https://doi.org/10.1088/1367-2630/16/1/013009.
https://doi.org/10.1088/1367-2630/16/1/013009

[32] Eugene Wigner. On the quantum correction for thermodynamic equilibrium. Phys. Rev., 40: 749–759, Jun 1932. https://doi.org/10.1103/PhysRev.40.749.
https://doi.org/10.1103/PhysRev.40.749

[33] William K. Wootters. Picturing qubits in phase space. IBM Journal of Research and Development, 48 (1): 99–110, 2004. https://doi.org/10.1147/rd.481.0099.
https://doi.org/10.1147/rd.481.0099

[34] Bei Zeng. Quantum operations and codes beyond the Stabilizer-Clifford framework. PhD thesis, Massachusetts Institute of Technology, 2009. URL http://hdl.handle.net/1721.1/53235.
http://hdl.handle.net/1721.1/53235

[35] Bei Zeng, Xie Chen, and Isaac L. Chuang. Semi-Clifford operations, structure of $\mathcal{C}_{k}$ hierarchy, and gate complexity for fault-tolerant quantum computation. Phys. Rev. A, 77: 042313, Apr 2008. https://doi.org/10.1103/PhysRevA.77.042313.
https://doi.org/10.1103/PhysRevA.77.042313

[36] Xinlan Zhou, Debbie W. Leung, and Isaac L. Chuang. Methodology for quantum logic gate construction. Phys. Rev. A, 62: 052316, Oct 2000. 10.1103/PhysRevA.62.052316.
https://doi.org/10.1103/PhysRevA.62.052316

Cited by

[1] Tefjol Pllaha, Kalle Volanto, and Olav Tirkkonen, 2021 IEEE Global Communications Conference (GLOBECOM) 01 (2021) ISBN:978-1-7281-8104-2.

[2] Aritra Das and Barry C. Sanders, "Blind quantum factorization of 21", Physical Review A 106 1, 012421 (2022).

[3] Jingzhen Hu, Qingzhong Liang, and Robert Calderbank, "Designing the Quantum Channels Induced by Diagonal Gates", Quantum 6, 802 (2022).

[4] Lia Yeh, Companion Proceedings of the 7th International Conference on the Art, Science, and Engineering of Programming 90 (2023) ISBN:9798400707551.

[5] Nadish de Silva, "Efficient quantum gate teleportation in higher dimensions", Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 477 2251, 20200865 (2021).

[6] Tefjol Pllaha, Olav Tirkkonen, and Robert Calderbank, "Binary Subspace Chirps", IEEE Transactions on Information Theory 68 12, 7735 (2022).

[7] Matteo Allaix, Yuxiang Lu, Yuhang Yao, Tefjol Pllaha, Camilla Hollanti, and Syed Jafar, GLOBECOM 2023 - 2023 IEEE Global Communications Conference 5457 (2023) ISBN:979-8-3503-1090-0.

[8] Dripto M. Debroy and Kenneth R. Brown, "Extended flag gadgets for low-overhead circuit verification", Physical Review A 102 5, 052409 (2020).

[9] Lia Yeh, "Scaling W state circuits in the qudit Clifford hierarchy", arXiv:2304.12504, (2023).

[10] Joshua Cudby and Sergii Strelchuk, "Learning Gaussian Operations and the Matchgate Hierarchy", arXiv:2407.12649, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-08-07 04:48:59) and SAO/NASA ADS (last updated successfully 2024-08-07 04:49:00). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.