Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2111.05698

Mutually unbiased bases: polynomial optimization and symmetry

Sander Gribling, Sven C. Polak

Published Nov 10, 2021• 2 citations
arXivHTMLPDF

Abstract

A set of $k$ orthonormal bases of $\mathbb C^d$ is called mutually unbiased if $|\langle e,f\rangle |^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$.

DOI
10.48550/arxiv.2111.05698

Related papers

Mutually unbiased bases: polynomial optimization and symmetry

Sander Gribling, Sven C. Polak

A set of k orthonormal bases of Cd is called mutually unbiased if |⟨e,f⟩|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≤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 Sd and Sk .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 Sd≀Sk -module C([d]×[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 .

Quantum•Apr 30, 2024•6 citations

Mutually unbiased bases as a commuting polynomial optimisation problem

Mortimer, Luke

We consider the problem of mutually unbiased bases as a polynomial optimization problem over the reals. We heavily reduce it using known symmetries before exploring it using two methods, combining a number of optimization techniques. The first of these is a search for bases using Lagrange-multipliers that converges rapidly in case of MUB existence, whilst the second combines a hierarchy of semidefinite programs with branch-and-bound techniques to perform a global search. We demonstrate that such an algorithm would eventually solve the open question regarding dimension 6 with finite memory, although it still remains intractable. We explore the idea that to show the inexistence of bases, it suffices to search for orthonormal vector sets of certain smaller sizes, rather than full bases. We use our two methods to conjecture the minimum set sizes required to show infeasibility, proving it for dimensions 3. The fact that such sub-problems seem to also be infeasible heavily reduces the number of variables, by 66\% in the case of the open problem, potentially providing an large speedup for other algorithms and bringing them into the realm of tractability.

arXiv:2308.01879•Aug 3, 2023•1 citation

On mutually unbiased bases

Rahim Taghikhani

Two orthonormal bases in the complex space of dimension d, are said to be mutually unbiased if the square of the magnitude of the inner product of any vector from one basis with any vector in other basis is equal to the reciprocal of the dimension d. Mutually unbiased bases are used for optimal state determination of mixed quantum states. It is known that in any dimension d, the number of mutually unbiased bases is at most d+1. Ivanovic found a complete set of mutually unbiased bases for prime dimensions. His construction was generalized by Wootters and Fields for prime power dimensions. There is a strong connection between maximally commuting bases of orthogonal unitary matrices and mutually unbiased bases. Based on this connection, there exits a constructive proof of the existence of a complete set of mutually unbiased bases for prime power dimensions. This thesis is an exploration on construction of mutually unbiased bases.

•Aug 26, 2013•1 citation

Some attempts at proving the non-existence of a full set of mutually unbiased bases in dimension 6

Guo Chuan Thiang

Complete sets of mutually unbiased bases are only known to exist in prime-power dimensions. We will describe a few approaches to the problem proving the (non)-existence of four mutually unbiased bases in dimension 6. These will include the notions of Grassmannian distance, quadratic matrix programming, semidefinite relaxations to polynomial programming, as well as various tools from algebraic geometry.

arXiv:1012.3147•Dec 14, 2010•1 citation

ON MUTUALLY UNBIASED BASES

Thomas Durt, Berthold‐Georg Englert, Ingemar Bengtsson +1 more

Mutually unbiased bases for quantum degrees of freedom are central to all theoretical investigations and practical exploitations of complementary properties. Much is known about mutually unbiased bases, but there are also a fair number of important questions that have not been answered in full as yet. In particular, one can find maximal sets of N + 1 mutually unbiased bases in Hilbert spaces of prime-power dimension N = p M , with p prime and M a positive integer, and there is a continuum of mutually unbiased bases for a continuous degree of freedom, such as motion along a line. But not a single example of a maximal set is known if the dimension is another composite number (N = 6, 10, 12,…). In this review, we present a unified approach in which the basis states are labeled by numbers 0, 1, 2, …, N - 1 that are both elements of a Galois field and ordinary integers. This dual nature permits a compact systematic construction of maximal sets of mutually unbiased bases when they are known to exist but throws no light on the open existence problem in other cases. We show how to use the thus constructed mutually unbiased bases in quantum-informatics applications, including dense coding, teleportation, entanglement swapping, covariant cloning, and state tomography, all of which rely on an explicit set of maximally entangled states (generalizations of the familiar two–q-bit Bell states) that are related to the mutually unbiased bases. There is a link to the mathematics of finite affine planes. We also exploit the one-to-one correspondence between unbiased bases and the complex Hadamard matrices that turn the bases into each other. The ultimate hope, not yet fulfilled, is that open questions about mutually unbiased bases can be related to open questions about Hadamard matrices or affine planes, in particular the notorious existence problem for dimensions that are not a power of a prime. The Hadamard-matrix approach is instrumental in the very recent advance, surveyed here, of our understanding of the N = 6 situation. All evidence indicates that a maximal set of seven mutually unbiased bases does not exist — one can find no more than three pairwise unbiased bases — although there is currently no clear-cut demonstration of the case.

arXiv:1004.3348•International Journal of Quantum Information•Jun 1, 2010•727 citations

An infinite family of strongly unextendible mutually unbiased bases in $\mathbb{C}^{2^{2h}}$

Jonathan Jedwab, Lily Yen

A set of $b$ mutually unbiased bases (MUBs) in $\mathbb{C}^d$ (for $d > 1$) comprises $bd$ vectors in $\mathbb{C}^d$, partitioned into $b$ orthogonal bases for $\mathbb{C}^d$ such that the pairwise angle between all vectors from distinct bases is $\arccos(1/\sqrt{d})$. The largest number $μ(d)$ of MUBs that can exist in $\mathbb{C}^d$ is at most $d+1$, but constructions attaining this bound are known only when $d$ is a prime power. A set of $b$ MUBs in $\mathbb{C}^d$ that cannot be enlarged, even by the first vector of a potential $(b+1)$-th MUB, is called strongly unextendible. Until now, only one infinite family of dimensions $d$ containing $b(d)$ strongly unextendible MUBs in $\mathbb{C}^d$ satisfying $b(d) < μ(d)$ was known, this family, due to Szántó, is asymptotically "large" in the sense that $b(d)/μ(d) \to 1$ as $d \to \infty$. However, the existence of $2^{m-1}+1$ strongly unextendible MUBs in $\mathbb{C}^{2^m}$ for each integer $m > 1$ has been conjectured by Mandayam et al. We prove their conjecture for all even values of $m$, using only elementary linear algebra. The existence of this "small" new infinite family suggests, contrary to widespread belief, that $μ(d)$ for non-prime-powers $d$ might be significantly larger than the size of particular unextendible sets.

arXiv:1604.04797•Apr 16, 2016•1 citation
A set of kkk orthonormal bases of Cd\mathbb C^dCd is called mutually unbiased if ∣⟨e,f⟩∣2=1/d|\langle e,f\rangle |^2 = 1/d∣⟨e,f⟩∣2=1/d whenever eee and fff are basis vectors in distinct bases. A natural question is for which pairs (d,k)(d,k)(d,k) there exist~kkk mutually unbiased bases in dimension ddd. The (well-known) upper bound k≤d+1k \leq d+1k≤d+1 is attained when~ddd 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∗C^*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 SdS_dSd​ and SkS_kSk​. 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 Sd≀SkS_d \wr S_kSd​≀Sk​-module C([d]×[k])t\mathbb C^{([d]\times [k])^t}C([d]×[k])t into irreducible modules. We present numerical results for small d,kd,kd,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+2d+2d+2 mutually unbiased bases in dimensions~d=2,3,4,5,6,7,8d=2,3,4,5,6,7,8d=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 333 MUBs in dimension 666 requires polynomials of total degree at least~121212.
A set of k orthonormal bases of Cd is called mutually unbiased if |⟨e,f⟩|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≤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 Sd and Sk .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 Sd≀Sk -module C([d]×[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 .
We consider the problem of mutually unbiased bases as a polynomial optimization problem over the reals. We heavily reduce it using known symmetries before exploring it using two methods, combining a number of optimization techniques. The first of these is a search for bases using Lagrange-multipliers that converges rapidly in case of MUB existence, whilst the second combines a hierarchy of semidefinite programs with branch-and-bound techniques to perform a global search. We demonstrate that such an algorithm would eventually solve the open question regarding dimension 6 with finite memory, although it still remains intractable. We explore the idea that to show the inexistence of bases, it suffices to search for orthonormal vector sets of certain smaller sizes, rather than full bases. We use our two methods to conjecture the minimum set sizes required to show infeasibility, proving it for dimensions 3. The fact that such sub-problems seem to also be infeasible heavily reduces the number of variables, by 66\% in the case of the open problem, potentially providing an large speedup for other algorithms and bringing them into the realm of tractability.
Two orthonormal bases in the complex space of dimension d, are said to be mutually unbiased if the square of the magnitude of the inner product of any vector from one basis with any vector in other basis is equal to the reciprocal of the dimension d. Mutually unbiased bases are used for optimal state determination of mixed quantum states. It is known that in any dimension d, the number of mutually unbiased bases is at most d+1. Ivanovic found a complete set of mutually unbiased bases for prime dimensions. His construction was generalized by Wootters and Fields for prime power dimensions. There is a strong connection between maximally commuting bases of orthogonal unitary matrices and mutually unbiased bases. Based on this connection, there exits a constructive proof of the existence of a complete set of mutually unbiased bases for prime power dimensions. This thesis is an exploration on construction of mutually unbiased bases.
Mutually unbiased bases for quantum degrees of freedom are central to all theoretical investigations and practical exploitations of complementary properties. Much is known about mutually unbiased bases, but there are also a fair number of important questions that have not been answered in full as yet. In particular, one can find maximal sets of N + 1 mutually unbiased bases in Hilbert spaces of prime-power dimension N = p M , with p prime and M a positive integer, and there is a continuum of mutually unbiased bases for a continuous degree of freedom, such as motion along a line. But not a single example of a maximal set is known if the dimension is another composite number (N = 6, 10, 12,…). In this review, we present a unified approach in which the basis states are labeled by numbers 0, 1, 2, …, N - 1 that are both elements of a Galois field and ordinary integers. This dual nature permits a compact systematic construction of maximal sets of mutually unbiased bases when they are known to exist but throws no light on the open existence problem in other cases. We show how to use the thus constructed mutually unbiased bases in quantum-informatics applications, including dense coding, teleportation, entanglement swapping, covariant cloning, and state tomography, all of which rely on an explicit set of maximally entangled states (generalizations of the familiar two–q-bit Bell states) that are related to the mutually unbiased bases. There is a link to the mathematics of finite affine planes. We also exploit the one-to-one correspondence between unbiased bases and the complex Hadamard matrices that turn the bases into each other. The ultimate hope, not yet fulfilled, is that open questions about mutually unbiased bases can be related to open questions about Hadamard matrices or affine planes, in particular the notorious existence problem for dimensions that are not a power of a prime. The Hadamard-matrix approach is instrumental in the very recent advance, surveyed here, of our understanding of the N = 6 situation. All evidence indicates that a maximal set of seven mutually unbiased bases does not exist — one can find no more than three pairwise unbiased bases — although there is currently no clear-cut demonstration of the case.
An infinite family of strongly unextendible mutually unbiased bases in C22h\mathbb{C}^{2^{2h}}C22h
A set of bbb mutually unbiased bases (MUBs) in Cd\mathbb{C}^dCd (for d>1d > 1d>1) comprises bdbdbd vectors in Cd\mathbb{C}^dCd, partitioned into bbb orthogonal bases for Cd\mathbb{C}^dCd such that the pairwise angle between all vectors from distinct bases is arccos⁡(1/d)\arccos(1/\sqrt{d})arccos(1/d​). The largest number μ(d)μ(d)μ(d) of MUBs that can exist in Cd\mathbb{C}^dCd is at most d+1d+1d+1, but constructions attaining this bound are known only when ddd is a prime power. A set of bbb MUBs in Cd\mathbb{C}^dCd that cannot be enlarged, even by the first vector of a potential (b+1)(b+1)(b+1)-th MUB, is called strongly unextendible. Until now, only one infinite family of dimensions ddd containing b(d)b(d)b(d) strongly unextendible MUBs in Cd\mathbb{C}^dCd satisfying b(d)<μ(d)b(d) < μ(d)b(d)<μ(d) was known, this family, due to Szántó, is asymptotically "large" in the sense that b(d)/μ(d)→1b(d)/μ(d) \to 1b(d)/μ(d)→1 as d→∞d \to \inftyd→∞. However, the existence of 2m−1+12^{m-1}+12m−1+1 strongly unextendible MUBs in C2m\mathbb{C}^{2^m}C2m for each integer m>1m > 1m>1 has been conjectured by Mandayam et al. We prove their conjecture for all even values of mmm, using only elementary linear algebra. The existence of this "small" new infinite family suggests, contrary to widespread belief, that μ(d)μ(d)μ(d) for non-prime-powers ddd might be significantly larger than the size of particular unextendible sets.