An efficient high dimensional quantum Schur transform

Hari Krovi

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

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


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.

► BibTeX data

► 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.

[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.

[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:/​/​​doi/​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:/​/​​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.

[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.

[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.

[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.

[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.

[11] William Fulton. Young tableaux: with applications to representation theory and geometry, volume 35. Cambridge University Press, 1997. 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.

[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.

[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.

[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.

[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.

[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:/​/​​abs/​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.

[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.

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

[22] Masahito Hayashi and Keiji Matsumoto. Simple construction of quantum universal variable-length source coding. Quantum Information & Computation, 2 (7): 519–529, 2002b. 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.

[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.

[25] Michael Keyl. Quantum state estimation and large deviations. Reviews in Mathematical Physics, 18 (01): 19–60, 2006. 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.

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

[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.

[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.

[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.

[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.

[32] Keiji Matsumoto and Masahito Hayashi. Universal distortion-free entanglement concentration. Physical Review A, 75 (6): 062338, 2007. 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.

[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:/​/​​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:/​/​​10.1145/​2897518.2897544.

[36] Bruce Sagan. The symmetric group: representations, combinatorial algorithms, and symmetric functions, volume 203. Springer Science & Business Media, 2013. 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.

[38] Richard P Stanley. Enumerative Combinatorics, volume 1. Cambridge University Press, 2011. 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.

[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.

[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.

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

Cited by

[1] 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).

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

[3] 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).

[4] 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).

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

The above citations are from Crossref's cited-by service (last updated successfully 2021-04-21 18:14:00) and SAO/NASA ADS (last updated successfully 2021-04-21 18:14:01). The list may be incomplete as not all publishers provide suitable and complete citation data.