On combinatorial constructions of mutually unbiased bases (MUBs) with approximations/ Ajeet Kumar

Thesis (Ph.D.)- Indian statistical Institute, 2024

Includes concluding remarks

Background --
MUBs and Hadamard matrices -- Challenges in composite (but non prime power) dimensions -- Basics of Resolvable Block Design -- Mutually Orthogonal Latin Square (MOLS) -- References to some Mathematical Tools -- Brief review of known constructions of Approximate MUBs --
On Approximate Real MUBs in Square Dimensions -- Resolvable Block Designs in Construction of Approximate Real MUBs that are Sparse -- Almost Perfect MUBs -- Further Constructions of AMUBs for Non-prime power Composite Dimensions -- A Heuristic Framework to search for Approximate MUBs

Guided by Prof. Subhamoy Maitra

Construction of Mutually Unbiased Bases (MUBs) is a very challenging combinatorial prob-
lem in the domain of quantum information theory with several long standing open questions.

In the language of quantum information theory, two orthonormal bases in the d-dimensional
complex Hilbert space C
d
, {|e1⟩, . . . |ed⟩} and {|f1⟩, . . . |fd⟩} are called Mutually Unbiased

if we have

|⟨ei
|fj ⟩| =
1
√
d
, ∀i, j ∈ {1, 2, . . . , d}.

Similarly, some r orthonormal bases are called Mutually Unbiased Bases (MUBs) if they
are pairwise Mutually Unbiased. Reaching the upper bound on this r is believed to be an
extremely challenging problem for more than half a century. Because of the difficulties to
construct significantly large number of MUBs, the problem is relaxed and the concept of
Approximate Mutually Unbiased Bases (AMUBs) had been introduced by Klappenecker,
R ̈otteler, Shparlinski and Winterhof in 2005. In this case the inner product of two vectors
drawn from two different bases is relaxed, instead of being exactly √
1
d
.

In the initial contribution of our thesis, we provide a method to construct upto (√
d + 1)

many AMUBs in dimension d = q
2
, where q is a positive integer. In particular, when d

is of the form (4x)

2 where x is a prime, we obtain (
√
d
4 + 1) many Approximate Mutually
Unbiased Bases (ARMUBs) such that for any two vectors v1, v2 belonging to different bases,
|⟨v1|v2⟩| ≤ √
4
d
.

The above results are then improved as well as generalized significantly with several
constructions exploiting the more involved combinatorial structures such as Resolvable Block
Designs (RBDs). We first explain the generic idea of our strategy in relating the RBDs
with MUBs/ARMUBs, which are sparse (the basis vectors have small number of non-zero
co-ordinates). To be specific, we present an infinite family of ⌈
√
d⌉ many ARMUBs for
dimension d = q(q + 1), where q ≡ 3 mod 4 and it is a prime power, such that for any two
vectors v1, v2 belonging to different bases, | ⟨v1|v2⟩ | < √
2
d
. We also analyze certain specific

cases, such as d = sq2

, where q is a prime power and sq ≡ 0 mod 4.

We continue to improve our results in this direction and formalize the definition of ap-
proximate MUBs with more restrictions. We propose the concept of Almost Perfect MUBs

(APMUB), where we restrict the absolute value of inner product | ⟨v1|v2⟩ | to be two-valued,
one being zero and the other ≤
1+O(d−λ)
√
d
, such that λ > 0 and the numerator 1+O(d
−λ
) ≤ 2.
We show that for a general composite dimension d = k × s, k, s ∈ N, with k ≤ s ≤ 4k,
one can construct at least N(s) + 1 many APMUBs, where N(s) is the number of Mutually
Orthogonal Latin Squares (MOLS) of order s. Even when restricted to R
d
, we can construct

similar number of real APMUBs, whenever real Hadamard matrix of order k can be con-
structed. Further, if s = q, where q power of prime, we have N(q) = q − 1, which enable us to construct q ∼ O(
√
d) many APMUBs. More appropriate and novel combinatorial
designs are presented in this regard which extend this to composite dimension of the form
d = (q − e)(q + f), e, f ∈ N, with 0 ≤ f ≤ e and q some power of prime. We also show that
our result has important implications towards Bi-angular vectors.
With the understanding of APMUBs, we revisit a larger class of AMUBs, and improve
the results further in terms of larger classes for composites that are not prime powers, and
for both real and complex. The technique is more generalized in terms of exploring novel
instances of RBDs that provide improved results.
Finally a heuristic framework is presented to search for AMUBs with significantly good
parameters and experimental outcomes of the computer programs are studied. Given a
non-prime dimension d, we note the closest prime d

′ > d and form d

′ + 1 MUBs through
the existing methods. Then our proposed idea considers two parts. First we apply basis
reduction techniques (that are well studied in Machine Learning literature) in obtaining
the initial solutions. Then we exploit the steepest ascent kind of search to improve the
results further. The efficacy of our technique is shown through construction of AMUBs in
dimensions d = 6, 10, 46 from d

′ = 7, 11 and 47 respectively. From a more generic view,
this approach considers approximately solving a challenging (where efficient deterministic

algorithms are not known) mathematical problem in discrete domain through state-of-the-
art heuristic ideas.
To summarize, in this thesis we exploit several involved combinatorial techniques in a
disciplined manner and also a heuristic to construct approximate MUBs.