An efficient high dimensional quantum Schur transform

Hari Krovi

doi:10.22331/q-2019-02-14-122

An efficient high dimensional quantum Schur transform

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

Published:	2019-02-14, volume 3, page 122
Eprint:	arXiv:1804.00055v2
Doi:	https://doi.org/10.22331/q-2019-02-14-122
Citation:	Quantum 3, 122 (2019).

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

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.

► BibTeX data

@article{Krovi2019efficienthigh,
  doi = {10.22331/q-2019-02-14-122},
  url = {https://doi.org/10.22331/q-2019-02-14-122},
  title = {An efficient high dimensional quantum {S}chur transform},
  author = {Krovi, Hari},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {3},
  pages = {122},
  month = feb,
  year = {2019}
}

► 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 & 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 & 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] Satoshi Yoshida, Akihito Soeda, and Mio Murao, "Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly", Physical Review Letters 131 12, 120602 (2023).

[2] Marco Fanizza, Michalis Skotiniotis, John Calsamiglia, Ramon Muñoz-Tapia, and Gael Sentís, "Universal algorithms for quantum data learning", Europhysics Letters 140 2, 28001 (2022).

[3] Pooja Siwach and Denis Lacroix, "Filtering states with total spin on a quantum computer", Physical Review A 104 6, 062435 (2021).

[4] Denis Lacroix, Edgar Andres Ruiz Guzman, and Pooja Siwach, "Symmetry breaking/symmetry preserving circuits and symmetry restoration on quantum computers", The European Physical Journal A 59 1, 3 (2023).

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

[6] Marco Fanizza, Raffaele Salvia, and Vittorio Giovannetti, "Testing identity of collections of quantum states: sample complexity analysis", Quantum 7, 1105 (2023).

[7] Han Zheng, Zimu Li, Junyu Liu, Sergii Strelchuk, and Risi Kondor, "Speeding Up Learning Quantum States Through Group Equivariant Convolutional Quantum Ansätze", PRX Quantum 4 2, 020327 (2023).

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

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

[10] Zachary P. Bradshaw, Margarite L. LaBorde, and Mark M. Wilde, "Cycle index polynomials and generalized quantum separability tests", Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 479 2274, 20220733 (2023).

[11] Yuxiang Yang, Yin Mo, Joseph M. Renes, Giulio Chiribella, and Mischa P. Woods, "Optimal universal quantum error correction via bounded reference frames", Physical Review Research 4 2, 023107 (2022).

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

[13] Marco Fanizza, Christoph Hirche, and John Calsamiglia, "Ultimate Limits for Quickest Quantum Change-Point Detection", Physical Review Letters 131 2, 020602 (2023).

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

[15] Satoshi Yoshida, Akihito Soeda, and Mio Murao, "Universal construction of decoders from encoding black boxes", Quantum 7, 957 (2023).

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

[17] Dmitry Grinko and Maris Ozols, "Linear programming with unitary-equivariant constraints", arXiv:2207.05713, (2022).

[18] Dmitry Grinko, Adam Burchardt, and Maris Ozols, "Gelfand-Tsetlin basis for partially transposed permutations, with applications to quantum information", arXiv:2310.02252, (2023).

[19] Quynh T. Nguyen, "The mixed Schur transform: efficient quantum circuit and applications", arXiv:2310.01613, (2023).

[20] Harry Buhrman, Noah Linden, Laura Mančinska, Ashley Montanaro, and Maris Ozols, "Quantum majority vote", arXiv:2211.11729, (2022).

[21] Han Zheng, Christopher Kang, Gokul Subramanian Ravi, Hanrui Wang, Kanav Setia, Frederic T. Chong, and Junyu Liu, "SnCQA: A hardware-efficient equivariant quantum convolutional circuit architecture", arXiv:2211.12711, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2023-11-29 01:02:19) and SAO/NASA ADS (last updated successfully 2023-11-29 01:02:20). 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.