# An efficient high dimensional quantum Schur transform

Hari Krovi

Quantum Engineering and Computing, Physical Sciences and Systems, Raytheon BBN Technologies, Cambridge, MA

### Abstract

The Schur transform is a unitary operator that block diagonalizes the action of the symmetric and unitary groups on an $n$ fold tensor product $V^{\otimes n}$ of a vector space $V$ of dimension $d$. Bacon, Chuang and Harrow [5] gave a quantum algorithm for this transform that is polynomial in $n$, $d$ and $\log\epsilon^{-1}$, where $\epsilon$ is the precision. In a footnote in Harrow's thesis [18], a brief description of how to make the algorithm of [5] polynomial in $\log d$ is given using the unitary group representation theory (however, this has not been explained in detail anywhere). In this article, we present a quantum algorithm for the Schur transform that is polynomial in $n$, $\log d$ and $\log\epsilon^{-1}$ using a different approach. Specifically, we build this transform using the representation theory of the symmetric group and in this sense our technique can be considered a ''dual" algorithm to [5]. A novel feature of our algorithm is that we construct the quantum Fourier transform over the so called $\textit{permutation modules}$, which could have other applications.

### ► References

[1] Arne Alex, Matthias Kalus, Alan Huckleberry, and Jan von Delft. A numerical algorithm for the explicit calculation of su (n) and sl (n, c) clebsch–gordan coefficients. Journal of Mathematical Physics, 52 (2): 023507, 2011. 10.1063/​1.3521562.
https:/​/​doi.org/​10.1063/​1.3521562

[2] Robert Alicki, Slawomir Rudnicki, and Slawomir Sadowski. Symmetry properties of product states for the system of n n-level atoms. Journal of Mathematical Physics, 29: 1158–1162, 1988. 10.1063/​1.527958.
https:/​/​doi.org/​10.1063/​1.527958

[3] D Bacon. Decoherence, control, and symmetry in quantum computers. PhD thesis, University of California, Berkeley, 2001.

[4] Dave Bacon, Isaac L. Chuang, and Aram W. Harrow. Efficient quantum circuits for schur and clebsch-gordan transforms. Phys. Rev. Lett., 97: 170502, Oct 2006. 10.1103/​PhysRevLett.97.170502. URL http:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.97.170502.
https:/​/​doi.org/​10.1103/​PhysRevLett.97.170502

[5] Dave Bacon, Isaac L. Chuang, and Aram W. Harrow. The quantum schur and clebsch-gordan transforms: I. efficient qudit circuits. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pages 1235–1244, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics. ISBN 978-0-898716-24-5. URL http:/​/​dl.acm.org/​citation.cfm?id=1283383.1283516.
http:/​/​dl.acm.org/​citation.cfm?id=1283383.1283516

[6] Robert Beals. Quantum computation of fourier transforms over symmetric groups. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 48–53. ACM, 1997. 10.1145/​258533.258548.
https:/​/​doi.org/​10.1145/​258533.258548

[7] G Chiribella, Y. Yang, and C. Huang. Universal super-replication of unitary gates. Phys. Rev. Lett., 114 (120504), 2015. 10.1103/​PhysRevLett.114.120504.
https:/​/​doi.org/​10.1103/​PhysRevLett.114.120504

[8] Giulio Chiribella and Yuxiang Yang. Quantum superreplication of states and gates. Frontiers of Physics, 11 (3): 110304, 2016. 10.1007/​s11467-016-0556-7.
https:/​/​doi.org/​10.1007/​s11467-016-0556-7

[9] Matthias Christandl and Graeme Mitchison. The spectra of quantum states and the kronecker coefficients of the symmetric group. Communications in mathematical physics, 261 (3): 789–797, 2006. 10.1007/​s00220-005-1435-1.
https:/​/​doi.org/​10.1007/​s00220-005-1435-1

[10] Richard Dipper, Stephen Doty, and Jun Hu. Brauer algebras, symplectic schur algebras and schur-weyl duality. Transactions of the American Mathematical Society, 360 (1): 189–213, 2008. 10.1090/​S0002-9947-07-04179-7.
https:/​/​doi.org/​10.1090/​S0002-9947-07-04179-7

[11] William Fulton. Young tableaux: with applications to representation theory and geometry, volume 35. Cambridge University Press, 1997. 10.1017/​CBO9780511626241.
https:/​/​doi.org/​10.1017/​CBO9780511626241

[12] William Fulton and Joe Harris. Representation theory, volume 129. Springer Science and Business Media, 1991. 10.1007/​978-1-4612-0979-9.
https:/​/​doi.org/​10.1007/​978-1-4612-0979-9

[13] Israel M. Gelfand and Michael .L. Zetlin. Finite-dimensional representations of the group of unimodular matrices. Dokl. Akad. Nauk Ser. Fiz., 71: 825–828, 1950.

[14] Richard D Gill and Serge Massar. State estimation for large ensembles. Physical Review A, 61 (4): 042312, 2000. 10.1103/​PhysRevA.61.042312.
https:/​/​doi.org/​10.1103/​PhysRevA.61.042312

[15] Roe Goodman and Nolan R Wallach. Representations and invariants of the classical groups, volume 68. Cambridge University Press, 2000. 10.1007/​978-0-387-79852-3.
https:/​/​doi.org/​10.1007/​978-0-387-79852-3

[16] J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory, 63 (9): 5628–5641, Sep. 2017. ISSN 0018-9448. 10.1109/​TIT.2017.2719044.
https:/​/​doi.org/​10.1109/​TIT.2017.2719044

[17] Tom Halverson and Arun Ram. q-rook monoid algebras, hecke algebras, and schur–weyl duality. Journal of Mathematical Sciences, 121 (3): 2419–2436, 2004. 10.1023/​B:JOTH.0000024623.99412.13.
https:/​/​doi.org/​10.1023/​B:JOTH.0000024623.99412.13

[18] Aram W. Harrow. Applications of coherent classical communication and the Schur transform to quantum information theory. PhD thesis, Massachusetts Institute of Technology, 2005. URL http:/​/​arxiv.org/​abs/​quant-ph/​0512255.
arXiv:quant-ph/0512255

[19] Vojtech Havlicek and Sergii Strelchuk. Quantum schur sampling circuits can be strongly simulated. Phys. Rev. Lett., 121 (060505), 2018. 10.1103/​PhysRevLett.121.060505.
https:/​/​doi.org/​10.1103/​PhysRevLett.121.060505

[20] Masahito Hayashi. Optimal sequence of quantum measurements in the sense of stein's lemma in quantum hypothesis testing. Journal of Physics A: Mathematical and General, 35 (50): 10759, 2002. 10.1088/​0305-4470/​35/​50/​307.
https:/​/​doi.org/​10.1088/​0305-4470/​35/​50/​307

[21] Masahito Hayashi and Keiji Matsumoto. Quantum universal variable-length source coding. Physical Review A, 66 (2): 22311, 2002a. 10.1103/​PhysRevA.66.022311.
https:/​/​doi.org/​10.1103/​PhysRevA.66.022311

[22] Masahito Hayashi and Keiji Matsumoto. Simple construction of quantum universal variable-length source coding. Quantum Information &amp; Computation, 2 (7): 519–529, 2002b. 10.1109/​ISIT.2003.1228476.
https:/​/​doi.org/​10.1109/​ISIT.2003.1228476

[23] James and Kerber. The Representation Theory of the Symmetric Group. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1984. 10.1017/​CBO9781107340732.
https:/​/​doi.org/​10.1017/​CBO9781107340732

[24] Julia Kempe, Dave Bacon, Daniel A Lidar, and K Birgitta Whaley. Theory of decoherence-free fault-tolerant universal quantum computation. Physical Review A, 63 (4): 042307, 2001. 10.1103/​PhysRevA.63.042307.
https:/​/​doi.org/​10.1103/​PhysRevA.63.042307

[25] Michael Keyl. Quantum state estimation and large deviations. Reviews in Mathematical Physics, 18 (01): 19–60, 2006. 10.1142/​S0129055X06002565.
https:/​/​doi.org/​10.1142/​S0129055X06002565

[26] Michael Keyl and Reinhard F Werner. Estimating the spectrum of a density operator. Physical Review A, 64 (5): 052311, 2001. 10.1103/​PhysRevA.64.052311.
https:/​/​doi.org/​10.1103/​PhysRevA.64.052311

[27] A Yu Kitaev. Quantum measurements and the abelian stabilizer problem. arXiv preprint quant-ph/​9511026, 1995.
arXiv:quant-ph/9511026

[28] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation, volume 47. American Mathematical Society Providence, 2002. 10.1090/​gsm/​047.
https:/​/​doi.org/​10.1090/​gsm/​047

[29] Emanuel Knill, Raymond Laflamme, and Lorenza Viola. Theory of quantum error correction for general noise. Physical Review Letters, 84 (11): 2525, 2000. 10.1103/​PhysRevLett.84.2525.
https:/​/​doi.org/​10.1103/​PhysRevLett.84.2525

[30] Robert Koenig and Graeme Mitchison. A most compendious and facile quantum de finetti theorem. Journal of Mathematical Physics, 50 (1): 012105, 2009. 10.1063/​1.3049751.
https:/​/​doi.org/​10.1063/​1.3049751

[31] Hari Krovi and Alexander Russell. Quantum fourier transforms and the complexity of link invariants for quantum doubles of finite groups. Communications in Mathematical Physics, 334 (2): 743–777, 2015. 10.1007/​s00220-014-2285-5.
https:/​/​doi.org/​10.1007/​s00220-014-2285-5

[32] Keiji Matsumoto and Masahito Hayashi. Universal distortion-free entanglement concentration. Physical Review A, 75 (6): 062338, 2007. 10.1103/​PhysRevA.98.032326.
https:/​/​doi.org/​10.1103/​PhysRevA.98.032326

[33] Cristopher Moore, Daniel Rockmore, and Alexander Russell. Generic quantum fourier transforms. ACM Transactions on Algorithms (TALG), 2 (4): 707–723, 2006. 10.1145/​1198513.1198525.
https:/​/​doi.org/​10.1145/​1198513.1198525

[34] Ryan O'Donnell and John Wright. Quantum spectrum testing. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 529–538, New York, NY, USA, 2015. ACM. ISBN 978-1-4503-3536-2. 10.1145/​2746539.2746582. URL http:/​/​doi.acm.org/​10.1145/​2746539.2746582.
https:/​/​doi.org/​10.1145/​2746539.2746582

[35] Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 899–912, New York, NY, USA, 2016. ACM. ISBN 978-1-4503-4132-5. 10.1145/​2897518.2897544. URL http:/​/​doi.acm.org/​10.1145/​2897518.2897544.
https:/​/​doi.org/​10.1145/​2897518.2897544

[36] Bruce Sagan. The symmetric group: representations, combinatorial algorithms, and symmetric functions, volume 203. Springer Science &amp; Business Media, 2013. 10.1007/​978-1-4757-6804-6.
https:/​/​doi.org/​10.1007/​978-1-4757-6804-6

[37] Jean-Pierre Serre. Linear representations of finite groups, translated from the second french edition by leonard l. scott. Graduate Texts in Mathematics, 42, 1977. 10.1007/​978-1-4684-9458-7.
https:/​/​doi.org/​10.1007/​978-1-4684-9458-7

[38] Richard P Stanley. Enumerative Combinatorics, volume 1. Cambridge University Press, 2011. 10.1017/​CBO9781139058520.
https:/​/​doi.org/​10.1017/​CBO9781139058520

[39] G Vidal, JI Latorre, P Pascual, and Rolf Tarrach. Optimal minimal measurements of mixed states. Physical Review A, 60 (1): 126, 1999. 10.1103/​PhysRevA.60.126.
https:/​/​doi.org/​10.1103/​PhysRevA.60.126

[40] N. Ja. Vilenkin and A. U. Klimyk. Representation of Lie Groups and Special Functions: Volume 3: Classical and Quantum Groups and Special Functions, volume 3. Springer Science and Business Media, 2013. 10.1007/​978-94-017-2881-2.
https:/​/​doi.org/​10.1007/​978-94-017-2881-2

[41] Yuxiang Yang, Giulio Chiribella, and Masahito Hayashi. Optimal compression for identically prepared qubit states. Phys. Rev. Lett, 117 (090502), 2016. 10.1103/​PhysRevLett.117.090502.
https:/​/​doi.org/​10.1103/​PhysRevLett.117.090502

[42] Paolo Zanardi and Mario Rasetti. Error avoiding quantum codes. Modern Physics Letters B, 11 (25): 1085–1093, 1997. 10.1142/​S0217984997001304.
https:/​/​doi.org/​10.1142/​S0217984997001304

### Cited by

[1] Sam McArdle, "Learning from Physics Experiments with Quantum Computers: Applications in Muon Spectroscopy", PRX Quantum 2 2, 020349 (2021).

[2] Gael Sentís, Alex Monràs, Ramon Muñoz-Tapia, John Calsamiglia, and Emilio Bagan, "Unsupervised Classification of Quantum Data", Physical Review X 9 4, 041029 (2019).

[3] Vojtěch Havlíček, Sergii Strelchuk, and Kristan Temme, "Classical algorithm for quantum SU(2) Schur sampling", Physical Review A 99 6, 062336 (2019).

[4] Yuxiang Yang and Masahito Hayashi, "Representation Matching For Remote Quantum Computing", PRX Quantum 2 2, 020327 (2021).

[5] M. Fanizza, M. Rosati, M. Skotiniotis, J. Calsamiglia, and V. Giovannetti, "Beyond the Swap Test: Optimal Estimation of Quantum State Overlap", Physical Review Letters 124 6, 060503 (2020).

[6] Gabriel Dufour, Tobias Brünner, Alberto Rodríguez, and Andreas Buchleitner, "Many-body interference in bosonic dynamics", New Journal of Physics 22 10, 103006 (2020).

[7] Marco Fanizza, Raffaele Salvia, and Vittorio Giovannetti, "Testing identity of collections of quantum states: sample complexity analysis", arXiv:2103.14511.

[8] Pooja Siwach and Denis Lacroix, "Filtering states with total spin on a quantum computer", arXiv:2106.10867.

The above citations are from Crossref's cited-by service (last updated successfully 2021-10-27 19:29:45) and SAO/NASA ADS (last updated successfully 2021-10-27 19:29:52). The list may be incomplete as not all publishers provide suitable and complete citation data.