Mutually Unbiased Bases: Polynomial Optimization And Symmetry

Republished By Plato

Followers: 0

Department of Econometrics and Operations Research, Tilburg University, Tilburg, The Netherlands

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

Abstract

A set of $k$ orthonormal bases of $mathbb C^d$ is called mutually unbiased if $|langle e,frangle |^2 = 1/d$ whenever $e$ and $f$ are basis vectors in distinct bases. A natural question is for which pairs $(d,k)$ there exist $k$ mutually unbiased bases in dimension $d$. The (well-known) upper bound $k leq d+1$ is attained when $d$ is a power of a prime. For all other dimensions it is an open problem whether the bound can be attained. Navascués, Pironio, and Acín showed how to reformulate the existence question in terms of the existence of a certain $C^*$-algebra. This naturally leads to a noncommutative polynomial optimization problem and an associated hierarchy of semidefinite programs. The problem has a symmetry coming from the wreath product of $S_d$ and $S_k$.
We exploit this symmetry (analytically) to reduce the size of the semidefinite programs making them (numerically) tractable. A key step is a novel explicit decomposition of the $S_d wr S_k$-module $mathbb C^{([d]times [k])^t}$ into irreducible modules. We present numerical results for small $d,k$ and low levels of the hierarchy. In particular, we obtain sum-of-squares proofs for the (well-known) fact that there do not exist $d+2$ mutually unbiased bases in dimensions $d=2,3,4,5,6,7,8$. Moreover, our numerical results indicate that a sum-of-squares refutation, in the above-mentioned framework, of the existence of more than $3$ MUBs in dimension $6$ requires polynomials of total degree at least $12$.

► BibTeX data

@article{Gribling2024mutuallyunbiased, doi = {10.22331/q-2024-04-30-1318}, url = {https://doi.org/10.22331/q-2024-04-30-1318}, title = {Mutually unbiased bases: polynomial optimization and symmetry}, author = {Gribling, Sander and Polak, Sven}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1318}, month = apr, year = {2024} }

► References

[1] E.A. Aguilar, J.J. Borkała, P. Mironowicz, and M. Pawłowski. Connections between mutually unbiased bases and quantum random access codes. Phys. Rev. Lett., 121:050501, Jul 2018. arXiv:1709.04898v2. doi:10.1103/PhysRevLett.121.050501.
https://doi.org/10.1103/PhysRevLett.121.050501
arXiv:1709.04898v2

[2] C. H. Bennett and G. Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, pages 175–179, 1984. doi:10.1016/j.tcs.2014.05.025.
https://doi.org/10.1016/j.tcs.2014.05.025

[3] I. Bengtsson, W. Bruzda, A. Ericsson, J-A. Larsson, W. Tadej, and K. Życzkowski. Mutually unbiased bases and hadamard matrices of order six. Journal of Mathematical Physics, 48(5):052106, 2007. doi:10.1063/1.2716990.
https://doi.org/10.1063/1.2716990

[4] S. Burgdorf, K. Cafuta, I. Klep, and J. Povh. The tracial moment problem and trace-optimization of polynomials. Mathematical Programming, 137(1):557–578, 2013. doi:10.1007/s10107-011-0505-8.
https://doi.org/10.1007/s10107-011-0505-8

[5] C. Bachoc, D.C. Gijswijt, A. Schrijver, and F. Vallentin. Invariant semidefinite programs. In M. F. Anjos and J. B. Lasserre, editors, Handbook on Semidefinite, Conic and Polynomial Optimization, pages 219–269. Springer, 2012. doi:10.1007/978-1-4614-0769-0_9.
https://doi.org/10.1007/978-1-4614-0769-0_9

[6] B. Blackadar. Operator Algebras: Theory of $C^*$-Algebras and Von Neumann Algebras. Encyclopaedia of Mathematical Sciences. Springer, 2006. doi:10.1007/3-540-28517-2.
https://doi.org/10.1007/3-540-28517-2

[7] R. H. Bruck and H. J. Ryser. The nonexistence of certain finite projective planes. Canadian Journal of Mathematics, 1(1):88–93, 1949. doi:10.4153/CJM-1949-009-2.
https://doi.org/10.4153/CJM-1949-009-2

[8] G. Blekherman and C. Riener. Symmetric nonnegative forms and sums of squares. Discrete & Computational Geometry, 65:764–799, 2021. doi:10.1007/s00454-020-00208-w.
https://doi.org/10.1007/s00454-020-00208-w

[9] C. Bachoc and F. Vallentin. New upper bounds for kissing numbers from semidefinite programming. Journal of the American Mathematical Society, 21:909–924, 2008. doi:10.1090/S0894-0347-07-00589-9.
https://doi.org/10.1090/S0894-0347-07-00589-9

[10] S. Brierley and S. Weigert. Constructing mutually unbiased bases in dimension six. Phys. Rev. A, 79:052316, May 2009. doi:10.1103/PhysRevA.79.052316.
https://doi.org/10.1103/PhysRevA.79.052316

[11] S. Brierley and S. Weigert. Mutually unbiased bases and semi-definite programming. Journal of Physics: Conference Series, 254, 2010. doi:10.1088/1742-6596/254/1/012008.
https://doi.org/10.1088/1742-6596/254/1/012008

[12] T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli. Representation Theory and Harmonic Analysis of Wreath Products of Finite Groups. London Mathematical Society Lecture Note Series (410). Cambridge University Press, 2013. doi:10.1017/CBO9781107279087.
https://doi.org/10.1017/CBO9781107279087

[13] J. Chuang and K.M. Tan. Representations of wreath products of algebras. Mathematical Proceedings of the Cambridge Philosophical Society, 135(3):395–411, 2003. doi:10.1017/S0305004103006984.
https://doi.org/10.1017/S0305004103006984

[14] P. Delsarte. An algebraic approach to the association schemes of coding theory. Philips Research Reports Supplements, 10, 1973.

[15] A. Fässler and E. Stiefel. Group Theoretical Methods and Their Applications. Birkhäuser, Basel, 1992. doi:10.1007/978-1-4612-0395-7.
https://doi.org/10.1007/978-1-4612-0395-7

[16] D.C. Gijswijt. Block diagonalization for algebra’s associated with block codes. arXiv:0910.4515, 2009. doi:10.48550/arXiv.0910.4515.
https://doi.org/10.48550/arXiv.0910.4515
arXiv:0910.4515

[17] K. Gatermann and P.A. Parrilo. Symmetry groups, semidefinite programs, and sums of squares. Journal of Pure and Applied Algebra, 192(1–3):9–128, 2004. doi:10.1016/j.jpaa.2003.12.011.
https://doi.org/10.1016/j.jpaa.2003.12.011

[18] M. Grassl. On SIC-POVMs and MUBs in Dimension 6. In Proceedings ERATO Conference on Quantum Information Science 2004 (EQIS 2004), pages 60–61, 2004. doi:10.48550/arXiv.quant-ph/0406175.
https://doi.org/10.48550/arXiv.quant-ph/0406175
arXiv:quant-ph/0406175

[19] R. Green. Some properties of Specht modules for the wreath product of symmetric groups. PhD thesis, University of Kent, 2019. URL: https://kar.kent.ac.uk/74164/.
https://kar.kent.ac.uk/74164/

[20] Paweł Horodecki, Łukasz Rudnicki, and Karol Życzkowski. Five open problems in quantum information theory. PRX Quantum, 3:010101, Mar 2022. doi:10.1103/PRXQuantum.3.010101.
https://doi.org/10.1103/PRXQuantum.3.010101

[21] I.D. Ivanović. Geometrical description of quantal state determination. Journal of Physics A: Mathematical and General, 14(12):3241–3245, 1981. doi:10.1088/0305-4470/14/12/019.
https://doi.org/10.1088/0305-4470/14/12/019

[22] E. de Klerk, C. Dobre, and D.V. Pasechnik. Numerical block diagonalization of matrix $*$-algebras with application to semidefinite programming. Mathematical Programming, 129:91, 2011. doi:10.1007/s10107-011-0461-3.
https://doi.org/10.1007/s10107-011-0461-3

[23] A. Kerber. Representations of Permutation Groups I. Lecture Notes in Mathematics. Springer-Verlag, 1971. doi:10.1007/BFb0067943.
https://doi.org/10.1007/BFb0067943

[24] I. Klep and J. Povh. Constrained trace-optimization of polynomials in freely noncommuting variables. Journal of Global Optimization, 64(2):325–348, 2016. doi:10.1007/s10898-015-0308-1.
https://doi.org/10.1007/s10898-015-0308-1

[25] E. de Klerk, D. Pasechnik, and A. Schrijver. Reductions of symmetric semidefinite programs using the regular $ast$-representation. Mathematical Programming, 109:613–624, 2007. doi:10.1007/s10107-006-0039-7.
https://doi.org/10.1007/s10107-006-0039-7

[26] E. de Klerk, D.V. Pasechnik, and R. Sotirov. On semidefinite programming relaxations of the traveling salesman problem. SIAM Journal on Optimization, 19(4):1559–1573, 2009. doi:10.1137/070711141.
https://doi.org/10.1137/070711141

[27] E. de Klerk and R. Sotirov. Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Mathematical Programming, 122(2):225–246, 2010. doi:10.1007/s10107-008-0246-5.
https://doi.org/10.1007/s10107-008-0246-5

[28] J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11(3):796–817, 2001. doi:10.1137/S1052623400366802.
https://doi.org/10.1137/S1052623400366802

[29] J. B. Lasserre. Moments, Positive Polynomials and Their Applications. Imperial College Press, 2009. doi:10.1142/p665.
https://doi.org/10.1142/p665

[30] M. Laurent. Sums of squares, moment matrices and optimization over polynomials. In M. Putinar and S. Sullivant, editors, Emerging Applications of Algebraic Geometry, pages 157–270. Springer, 2009. doi:10.1007/978-0-387-09686-5_7.
https://doi.org/10.1007/978-0-387-09686-5_7

[31] B. Litjens, S. Polak, and A. Schrijver. Semidefinite bounds for nonbinary codes based on quadruples. Designs, Codes and Cryptography, 84:87–100, 2017. doi:10.1007/s10623-016-0216-5.
https://doi.org/10.1007/s10623-016-0216-5

[32] I.G. MacDonald. Polynomial functors and wreath products. Journal of Pure and Applied Algebra, 18(2):173–204, 1980. doi:10.1016/0022-4049(80)90128-0.
https://doi.org/10.1016/0022-4049(80)90128-0

[33] K. Murota, Y. Kanno, M. Kojima, and S. Kojima. A numerical algorithm for block-diagonal decomposition of matrix ${*}$-algebras with application to semidefinite programming. Japan Journal of Industrial and Applied Mathematics, 27:125–160, 2010. doi:10.1007/s13160-010-0006-9.
https://doi.org/10.1007/s13160-010-0006-9

[34] M. Nakata. A numerical evaluation of highly accurate multiple-precision arithmetic version of semidefinite programming solver: SDPA-GMP, -QD and -DD. In 2010 IEEE International Symposium on Computer-Aided Control System Design, pages 29–34, 2010. doi:10.1109/CACSD.2010.5612693.
https://doi.org/10.1109/CACSD.2010.5612693

[35] M. Navascués, S. Pironio, and A. Acín. SDP relaxations for non-commutative polynomial optimization. In M. F. Anjos and J. B. Lasserre, editors, Handbook on Semidefinite, Conic and Polynomial Optimization, pages 601–634. Springer, 2012. doi:10.1007/978-1-4614-0769-0 21.
https://doi.org/10.1007/978-1-4614-0769-0%2021

[36] M. Navascués and T. Vértesi. Bounding the set of finite dimensional quantum correlations. Phys. Rev. Lett., 115:020501, Jul 2015. doi:10.1103/PhysRevLett.115.020501.
https://doi.org/10.1103/PhysRevLett.115.020501

[37] P. A. Parrilo. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, Caltech, 2000. doi:10.7907/2K6Y-CH43.
https://doi.org/10.7907/2K6Y-CH43

[38] S. Pironio, M. Navascués, and A. Acín. Convergent relaxations of polynomial optimization problems with noncommuting variables. SIAM Journal on Optimization, 20(5):2157–2180, 2010. doi:10.1137/090760155.
https://doi.org/10.1137/090760155

[39] S.C. Polak. New Methods in Coding Theory: Error-Correcting Codes and the Shannon Capacity. PhD thesis, University of Amsterdam, 2019. URL: https://hdl.handle.net/11245.1/393eb25b-c1ba-4c6f-89e8-c439a97358b6.
https://hdl.handle.net/11245.1/393eb25b-c1ba-4c6f-89e8-c439a97358b6

[40] D. Rosset, F. Montealegre-Mora, and JD Bancal. RepLAB: A Computational/Numerical Approach to Representation Theory. In M.B. Paranjape, R. MacKenzie, Z. Thomova, P. Winternitz, and W. Witczak-Krempa, editors, Quantum Theory and Symmetries, CRM Series in Mathematical Physics. Springer, 2021. doi:10.1007/978-3-030-55777-5_60.
https://doi.org/10.1007/978-3-030-55777-5_60

[41] C. Riener, T. Theobald, L. Jansson Andrén, and J.B. Lasserre. Exploiting symmetry in sdp-relaxations for polynomial optimization. Mathematics of Operations Research, 38:122–141, 2013. doi:10.1287/moor.1120.0558.
https://doi.org/10.1287/moor.1120.0558

[42] B.E. Sagan. The symmetric group, volume 203 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 2001. doi:10.1007/978-1-4757-6804-6.
https://doi.org/10.1007/978-1-4757-6804-6

[43] A. Schrijver. A comparison of the Delsarte and Lovász bounds. IEEE Transactions on Information Theory, 25(4):425–429, 1979. doi:10.1109/TIT.1979.1056072.
https://doi.org/10.1109/TIT.1979.1056072

[44] A. Schrijver. New code upper bounds from the terwilliger algebra and semidefinite programming. IEEE Transactions on Information Theory, 51(8):2859–2866, 2005. doi:10.1109/TIT.2005.851748.
https://doi.org/10.1109/TIT.2005.851748

[45] C. Spengler, M. Huber, S. Brierley, T. Adaktylos, and B.C. Hiesmayr. Entanglement detection via mutually unbiased bases. Phys. Rev. A, 86:022311, Aug 2012. doi:10.1103/PhysRevA.86.022311.
https://doi.org/10.1103/PhysRevA.86.022311

[46] Gaston Tarry. Le probléme des 36 officiers. Compte Rendu de l’Association Francaise pour l’Avancement des Sciences, 2:170–203, 1901.

[47] P. Wocjan and T. Beth. New construction of mutually unbiased bases in square dimensions. Quantum Inf. Comput., 5(2):93–101, 2005. doi:10.26421/QIC5.2-1.
https://doi.org/10.26421/QIC5.2-1

[48] M. Weiner. A gap for the maximum number of mutually unbiased bases. Proceedings of the American Mathematical Society, 141(6):1963–1969, 2013. doi:10.1090/S0002-9939-2013-11487-5.
https://doi.org/10.1090/S0002-9939-2013-11487-5

[49] W.K. Wootters and B.D. Fields. Optimal state-determination by mutually unbiased measurements. Annals of Physics, 191(2):363 – 381, 1989. doi:10.1016/0003-4916(89)90322-9.
https://doi.org/10.1016/0003-4916(89)90322-9

[50] W.K. Wootters. Quantum Measurements and Finite Geometry. Found Phys, 36:112–126, 2006. doi:10.1007/s10701-005-9008-x.
https://doi.org/10.1007/s10701-005-9008-x

[51] M. Yamashita, K. Fujisawa, M. Fukuda, K. Kobayashi, K. Nakata, and M. Nakata. Latest developments in the SDPA Family for solving large-scale SDPs. In M. F. Anjos and J. B. Lasserre, editors, Handbook on Semidefinite, Conic and Polynomial Optimization, pages 687–714. Springer, 2012. doi:10.1007/978-1-4614-0769-0_24.
https://doi.org/10.1007/978-1-4614-0769-0_24

[52] G. Zauner. Quantendesigns: Grundzüge einer nichtkommutativen Designtheorie. PhD thesis, University of Vienna, 1999. Also published as Quantum designs: foundations of a noncommutative design theory, International Journal of Quantum Information 09(01):445–507, 2011. doi:10.1142/S0219749911006776.
https://doi.org/10.1142/S0219749911006776

Cited by

[1] Yeow Meng Chee, Hoang Ta, and Van Khu Vu, “Efficient Approximation of Quantum Channel Fidelity Exploiting Symmetry”, arXiv:2308.15884, (2023).

[2] Maria Prat Colomer, Luke Mortimer, Irénée Frérot, Máté Farkas, and Antonio Acín, “Three numerical approaches to find mutually unbiased bases using Bell inequalities”, arXiv:2203.09429, (2022).

[3] Luke Mortimer, “Mutually unbiased bases as a commuting polynomial optimisation problem”, arXiv:2308.01879, (2023).

[4] Ojas Parekh, “Synergies Between Operations Research and Quantum Information Science”, arXiv:2301.05554, (2023).

[5] Travis B. Russell, “A synchronous NPA hierarchy with applications”, arXiv:2105.01555, (2021).

[6] Afonso S. Bandeira, Nikolaus Doppelbauer, and Dmitriy Kunisky, “Dual bounds for the positive definite functions approach to mutually unbiased bases”, arXiv:2202.13259, (2022).

[7] Maria Prat Colomer, Luke Mortimer, Irénée Frérot, Máté Farkas, and Antonio Acín, “Three numerical approaches to find mutually unbiased bases using Bell inequalities”, Quantum 6, 778 (2022).

The above citations are from SAO/NASA ADS (last updated successfully 2024-05-05 11:38:41). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2024-05-05 11:38:40).

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.

SEO Powered Content & PR Distribution. Get Amplified Today.
PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
Source: https://quantum-journal.org/papers/q-2024-04-30-1318/

Time Stamp: April 30, 2024

Time Stamp: Nov 10, 2022

Mutually unbiased bases: polynomial optimization and symmetry

Republished By Plato

Abstract

► BibTeX data

► References

Cited by

More from Quantum Journal

Quantum-enhanced differential atom interferometers and clocks with spin-squeezing swapping

Cooperative quantum information erasure

The quartic Blochnium: an anharmonic quasicharge superconducting qubit

Fast Stabiliser Simulation with Quadratic Form Expansions

Post-selection-free preparation of high-quality physical qubits

Quantum state preparation via engineered ancilla resetting

Quantum Alchemy and Universal Orthogonality Catastrophe in One-Dimensional Anyons

General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory

Efficient variational synthesis of quantum circuits with coherent multi-start optimization

Correlations in typicality and an affirmative solution to the exact catalytic entropy conjecture

About Us

Vertical Search & Ai

Platform

Stay Connected

Account