#  Uncertainty relations
for the support of quantum states

Vincenzo Fiorentino and Stefan Weigert

(January 2023)

###### Abstract

Given a narrow signal over the real line, there is a limit to the localisation
of its Fourier transform. In spaces of prime dimensions, Tao derived a sharp
state-independent uncertainty relation which holds for the support sizes of a
pure qudit state in two bases related by a discrete Fourier transform. We
generalise Tao’s uncertainty relation to complete sets of mutually unbiased
bases in spaces of prime dimensions. The bound we obtain appears to be sharp
for dimension three only. Analytic and numerical results for prime dimensions
up to nineteen suggest that the bound cannot be saturated in general. For
prime dimensions two to seven we construct sharp bounds on the support sizes
in $(d+1)$ mutually unbiased bases and identify some of the states achieving
them.

Department of Mathematics, University of York

York YO10 5DD, United Kingdom

<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Support inequalities for a Fourier pair of bases
    2. 2.2 Mutually unbiased bases in prime dimensions
  3. 3 Support inequalities$\ldots$
    1. 3.1 $\ldots$ for arbitrary pairs of MU bases
    2. 3.2 $\ldots$ for complete sets of $(d+1)$ MU bases
  4. 4 Saturating support inequalities for MU bases
    1. 4.1 Constraints on saturating states
    2. 4.2 Dimension $d=3$
    3. 4.3 Dimensions $d=5$ and $d=7$
    4. 4.4 Numerical results for $5\leq d\leq 19$
    5. 4.5 Dimensions $d>19$
  5. 5 Sharp lower bounds
    1. 5.1 Dimension $d=3$
    2. 5.2 Dimension $d=5$
    3. 5.3 Dimension $d=7$
  6. 6 Summary and Conclusions
  7. 7 Appendix

##  1 Introduction

No quantum particle can reside in a state with both its position and momentum
distributions being localised arbitrarily well. For these incompatible
observables, Heisenberg’s uncertainty relation [1, 2] establishes a finite
lower bound for the product of their variances. This result relies on a
fundamental property of Fourier theory: a real (or complex) function with
_finite_ support on the real line has a Fourier transform which must be non-
zero almost everywhere [3]. It is, however, difficult to quantify the support
of functions on unbounded intervals. Using variances instead of the supports
of probability distributions circumvents this difficulty.

The situation is different for quantum systems with finite-dimensional Hilbert
spaces since the _support (size)_ of a pure state—defined as the number of
non-zero components in a given orthonormal basis—is always finite. A
computational basis state in $\mathbb{C}^{d}$, say, has support equal to one,
and the support of its (discrete) Fourier transform equals $d$ since all basis
states contribute. Thus, the _product_ of the support sizes equals $d$ which
turns out to be its smallest possible value [4].

The underlying product inequality has been generalised in a number of
directions [5, 6]. Tao derived an _additive_ inequality [7] which is valid in
spaces $\mathbb{C}^{d}$ of prime dimensions $d=p$: the _sum_ of the supports
of a state and its discrete Fourier transform is bounded from below by the
value $(p+1)$. This bound is sharp since a computational basis state and its
Fourier transform saturate it.

Support inequalities and their generalisations have found applications in
signal processing [8, 9], for example, and they can be used to identify non-
classical quantum states [10] whose _Kirkwood-Dirac quasiprobability
distribution_ [11, 12] is not a probability distribution. Such states provide
an advantage in quantum metrology [13] and play a role in weak measurements
[14, 15, 16] and contextuality [17].

Using the support size of a quantum state as a measure of uncertainty has an
unexpected—and previously unnoticed—operational advantage. Quantum supports
take a _finite_ set of integer values only, in stark contrast to other
measures. Variances of observables in a given state or its von Neumann entropy
take _real numbers_ as values which demands many measurements to determine
experimentally. However, a _finite_ number of measurements may already suffice
to determine the _exact_ support size of a quantum state. This situation
occurs whenever the state at hand has $(i)$ “full” support in the basis
considered and $(ii)$ each outcome has been registered at least once.
Conformity with a given support inequality may be verified by a _finite_
number of measurements as small as the bound itself. This property depends, of
course, on the assumption that outcomes with probability zero never occur;
limited detection efficiency does not invalidate the argument, however.

Variance-based uncertainty relations also exist for more than two observables
associated with multiple orthonormal bases [18, 19, 20, 21]: position and
momentum may be supplemented by a third continuous variable which is canonical
to each of them. The eigenbases of these three observables are mutually
unbiased and related by fractional Fourier transforms. The product of their
variances satisfies a _triple uncertainty relation_ [18]. Importantly, the
lower bound of this inequality does _not_ follow from the pair uncertainty
relations but must be determined independently. No quantum state exists which
satisfies all three pair uncertainty relations simultaneously. In a similar
vein, entropic uncertainty relations capture the incompatibility of up to
$(d+1)$ observables in finite-dimensional systems, linked to a complete set of
mutually unbiased bases known to exist in prime-power dimension [22, 23, 24].

The main goal of this paper is to extend Tao’s additive support uncertainty
relation to the case of more than two bases, inspired by the triple
uncertainty relation for continuous variables. The focus will be on prime-
dimensional spaces where $(p+1)$ mutually unbiased bases exist, known as
_complete sets_. The support sizes of a state in any pair of mutually unbiased
bases from such a set are expected to satisfy Tao’s bound but it is unlikely
that they will saturate all pair bounds simultaneously.

This paper is structured as follows. Sec. 2 sets up notation by briefly
describing known product and sum inequalities for the support of a vector, and
the properties of complete sets of MU bases are summarised. In Sec. 3, Tao’s
additive uncertainty relation for the support of quantum states is shown to
hold for any pair of mutually unbiased bases in the complete set considered,
and the generalised additive support inequality involving all $(p+1)$ mutually
unbiased bases is established as a direct consequence. According to Sec. 4 the
bounds provided by the generalised support inequality cannot be saturated for
prime dimensions $2\leq d\leq 19$, except $d=3$. Higher _achievable_ bounds
are derived in Sec. 5, for prime numbers up to $d=7$. In the last section, we
summarise and discuss the results obtained. The proofs of some lemmata are
relegated to an appendix.

##  2 Preliminaries

###  2.1 Support inequalities for a Fourier pair of bases

The _support_(_size_) of a Hilbert-space vector $\psi\in{\cal H}_{d}$ is given
by the number of its non-zero expansion coefficients $\psi_{v}=\langle
v|\psi\rangle$ in an orthonormal basis ${\cal
B}=\left\\{|v\rangle,v=0,1,\ldots,\,d-1\right\\}$,

$|\text{supp}(\psi,\mathcal{B})|=\\#(\psi_{v}\neq 0,v=0\ldots
d-1)\in\left\\{0\ldots\,d\right\\}\,.$ (1)

The only vector with vanishing support is the zero vector. Due to
normalisation, the support of a quantum state must be at least one, and the
maximum is achieved whenever the state $\psi$ is a linear combination of all
$d$ basis states. The support size of a state clearly depends on the chosen
basis. Formally, the support size can be obtained as a limit of the Rényi
entropy [25] of the probability distribution $\left\\{|\psi_{v}|^{2},v=0\ldots
d-1\right\\}$.

Thinking of the support size as the (improper) $L^{0}$-“norm” of $\psi$, we
will use the notation

$|\text{supp}(\psi,\mathcal{B})|=\|\psi\|_{\mathcal{B}}\,.$ (2)

The set of expansion coefficients $\left\\{\psi_{v},v=0\ldots d-1\right\\}$
has three obvious _support-conserving_ symmetries. The support size is
invariant $(i)$ under rephasing each expansion coefficient separately,

$||\psi||_{\mathcal{B}}=||R\psi||_{\mathcal{B}}\,,\qquad
R=\text{diag}(e^{i\tau_{0}},e^{i\tau_{1}},\ldots,e^{i\tau_{d-1}})\,,$ (3)

with real numbers $\tau_{v},v=0,\ldots,\,d-1$; $(ii)$ under permuting the
components of any state among themselves

$||\psi||_{\mathcal{B}}=||P\psi||_{\mathcal{B}}\,,\qquad P\in S_{d}\,,$ (4)

where $S_{d}$ is the permutation group acting on sets of $d$ elements; and
$(iii)$ under the complex conjugation of some (or all) of its components,

$||\psi||_{\mathcal{B}}=||K\psi||_{\mathcal{B}}\,,\qquad K=\prod_{\text{some
}v\in\left\\{0\ldots\,d-1\right\\}}K_{v}\,,$ (5)

where each operator $K_{v},v=0,\ldots,\,d-1$, maps one expansion coefficient
of the state $\psi$ in the basis $\mathcal{B}$ to its complex conjugate,
$K_{v}\psi_{v}=\psi_{v}^{*}$, and does not change the others. In the basis
$\mathcal{B}$, the permutations $P$ are represented by a matrix of order $d$
containing exactly one unit entry in each row and column; hence the unitary
invariances of rephasing and permuting coefficients are conveniently combined
into _monomial_ matrices $M\equiv RP$. The third invariance described by the
operators $K_{v}$ will play no role.

Given two distinct orthonormal bases ${\cal B}$ and ${\cal B}^{\prime}$ of
${\cal H}_{d}$, one may ask to which extent a state can be “localised” in both
of them. Clearly, the product of its support sizes in ${\cal B}$ and ${\cal
B}^{\prime}$ may take values between one and $d^{2}$. If the bases are related
by $\mathcal{B}^{\prime}=F\mathcal{B}$, where $F$ is the discrete Fourier
transform with matrix elements (in the $\mathcal{B}$-basis)

$F_{vv^{\prime}}=\frac{1}{\sqrt{d}}e^{-2\pi ivv^{\prime}/d}\qquad
v,v^{\prime}\in\left\\{0\ldots\,d-1\right\\}\,,$ (6)

then the product of the support sizes of a state $\psi$ and its Fourier
transform $\widetilde{\psi}=F^{\dagger}\psi$ is bounded from below [4],

$\|\psi\|_{\mathcal{B}}\,||\psi||_{\mathcal{B}^{\prime}}\geq d\,,$ (7)

where we use the fact that the support size of the Fourier transformed state
$\widetilde{\psi}$ in the basis $\mathcal{B}$ is equal to the support size of
the state $\psi$ in the basis $\mathcal{B}^{\prime}$, i.e.

$||\widetilde{\psi}||_{\mathcal{B}}=||F^{\dagger}\psi||_{\mathcal{B}}=||\psi||_{\mathcal{B}^{\prime}}\,.$
(8)

The inequality (7) represents a finite-dimensional equivalent of Heisenberg’s
uncertainty relation for position and momentum observables of a quantum
particle: quantum states localised in position, say, necessarily come with a
broad variance in momentum, the Fourier-transformed position observable.

For spaces ${\cal H}_{d}$ with _prime_ dimensions $d$, an _additive_
inequality for the supports of a quantum state in a pair of Fourier-related
bases is known [7],

$\|\psi\|_{\mathcal{B}}+||\psi||_{\mathcal{B}^{\prime}}\geq d+1\,,$ (9)

which is stronger than the multiplicative relation (7), as follows from the
inequality $d+1-x\geq d/x$, for $x\in[1,d]$. _In the terminology of_[10], any
two bases ${\cal B}$ and ${\cal B}^{\prime}$ are said to be _completely
incompatible_ if and only if the support sizes of the expansion coefficients
of any (non-zero) vector $\psi\in\mathcal{H}_{d}$ satisfy this bound.

The inequality (9) is a special case of a theorem valid for finite additive
Abelian groups $G$ with $|G|$ elements and trivial subgroups only which
necessitates the restriction to prime dimensions [7]. Consider a complex-
valued function $f:G\to\mathbb{C}$ and its transform
$\widetilde{f}:G\to\mathbb{C}$, defined by

$\widetilde{f}(v^{\prime})=\frac{1}{\sqrt{|G|}}\sum_{v\in
G}f(v)\overline{e(v,v^{\prime})}\,,$ (10)

where $e(v,v^{\prime})$ is a “bi-character” of $G$ satisfying
$e(v_{1}+v_{2},v^{\prime})=e(v_{1},v^{\prime})e(v_{2},v^{\prime})$ and an
analogous relation for its second argument. In the particular case of
$e(v,v^{\prime})=e^{-2\pi ivv^{\prime}/d}$, one obtains an inequality for the
supports of $f$ and $\widetilde{f}\equiv F^{\dagger}f$.

######  Theorem 1 (_Tao’s theorem_).

If $f:G\to\mathbb{C}$ is a non-zero function and the cardinality $|G|$ of the
group $G$ is prime, then

$|\text{\emph{supp}}(f)|+|\text{\emph{supp}}(\widetilde{f})|\geq|G|+1\,.$ (11)

Upon identifying $f\left(v\right)$ with $\langle v|\psi\rangle$ and
$\widetilde{f}(v^{\prime})$ with $\langle v^{\prime}|\psi\rangle$,
respectively, we obtain the inequality (9) relative to the bases ${\cal B}$
and $\mathcal{B}^{\prime}$ introduced via $F$ in Eq. (6).

The main ingredient of Tao’s proof is a fundamental property of the Fourier
matrix in prime dimensions [26, 27, 7] which dates back to the 1920s: all its
square submatrices are invertible.

######  Theorem 2 (_Chebotarëv’s theorem_).

If $d$ is prime, then all minors of the Fourier matrix $F$ in Eq. (6) are non-
zero.

The inequalities (7) and (9) involve a _pair_ of _mutually unbiased_ __ bases
of $\mathcal{H}_{d}$, namely the computational basis ${\cal B}$ and its
Fourier transform. We will now introduce larger sets of mutually unbiased
bases to formulate more general support inequalities. Not surprisingly,
Chebotarëv’s theorem must be generalised to other matrices which emerge when
establishing bounds on support sizes of quantum states in multiple bases (cf.
Sec. 3.1).

###  2.2 Mutually unbiased bases in prime dimensions

Two orthonormal bases of the space $\mathcal{H}_{d}=\mathbb{C}^{d}$ are said
to be mutually unbiased _(MU)_ if the inner products between any two states
(not of the same basis) have modulus $1/\sqrt{d}$. Then, to know the outcome
of a projective measurement performed in one basis implies complete
uncertainty about the outcome of a subsequent projective measurement performed
in the other.

When $d$ is a power of a prime number $p$, i.e. $d=p^{n}$, sets of $(d+1)$
mutually unbiased bases have been constructed [28, 29, 30, 31]. Such complete
sets are both maximal—in the sense that no additional MU basis can be added to
it—and tomographically complete _:___ the probability distributions of
outcomes in the $(d+1)$ bases uniquely encode an unknown quantum state. It is
an open problem whether complete sets of MU bases exist in composite
dimensions, $d\neq p^{n}$.

For $d=2$, the eigenstates of the Pauli operators $Z_{2}$, $X_{2}$ and
$X_{2}Z_{2}=-iY_{2}$ form a complete set which has a simple structure.
Representing the computational basis ${\cal B}_{0}$ by the identity matrix
$H_{0}=I_{\left(2\times 2\right)}$, the following two Hadamard matrices encode
the bases which are MU to ${\cal B}_{0}$,

$H_{1}=F=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\\
1&-1\end{bmatrix},\qquad\qquad
H_{2}=DF\quad\text{where}\;D=\begin{bmatrix}1&0\\\ 0&i\end{bmatrix}\,.$ (12)

If $d$ is an odd prime, the eigenstates of the $(d+1)$ generalised Pauli
operators $Z_{d}$, $X_{d}$, $X_{d}Z_{d}$, $X_{d}Z_{d}^{2}$, …,
$X_{d}Z_{d}^{d-1}$, represent a maximal set of MU bases. The $k$-th state of
the $j$-th basis is given by

$|\phi_{k}^{j}\rangle=\frac{1}{\sqrt{d}}\sum_{x=0}^{d-1}\omega^{-kx}\omega^{\left(j-1\right)x^{2}}|\phi_{x}^{0}\rangle\,,\qquad
j\in\left\\{1...\,d\right\\}\,,\quad k\in\left\\{0...\,d-1\right\\}\,,$ (13)

where the states $\left\\{|\phi_{x}^{0}\rangle\equiv|x\rangle,x=0\ldots
d-1\right\\}$ form the computational basis ${\cal B}_{0}$ and $\omega\equiv
e^{2i\pi/d}$ is a $d$-th root of the number $1$ [31]. For each value of $j$,
the equimodular expansion coefficients

$\left[H_{j}\right]_{xk}=\langle
x|\phi_{k}^{j}\rangle=\frac{1}{\sqrt{d}}\omega^{-kx}\omega^{\left(j-1\right)x^{2}}\,,\qquad
j\in\left\\{1...\,d\right\\},\,x,k\in\left\\{0...\,d-1\right\\}\,,$ (14)

define a _complex-valued Hadamard matrix_. These are unitary matrices since
their columns are given by the components (in the computational basis ${\cal
B}_{0}$) of $d$ orthogonal vectors. When combined with the computational basis
${\cal B}_{0}$, the states given in Eq. (13) form a complete set of MU bases
for Hilbert spaces of prime dimensions, which we will refer to as the
_standard_ set. In this paper, all MU bases will be taken from the standard
set.

The Hadamard matrix $H_{1}$ in (14) coincides with the discrete Fourier matrix
$F$ given in Eq. (6). The remaining Hadamard matrices $H_{j}$ map the
computational basis ${\cal B}_{0}$ of ${\cal H}_{d}$ to other orthonormal
bases denoted by ${\cal B}_{j}$. Adopting an active view of these
transformations, the state $\psi$ is mapped to the state
$H_{j}^{\dagger}\psi$. The relation between the supports of the state $\psi$
in $\mathcal{B}_{0}$ and the $j$-th MU basis $\mathcal{B}_{j}$ reads,

$||H_{j}^{\dagger}\psi||_{0}=||\psi||_{j}\,,$ (15)

abbreviating the notation introduced in (8), i.e.
$||\psi||_{\mathcal{B}_{j}}\equiv||\psi||_{j}$, $j\in\\{0\ldots d\\}$.

The columns of the $d$ Hadamard matrices $H_{j}$ in (14) are related in a
simple way to each other, namely by

$|\phi_{k}^{j}\rangle=D^{j-1}B^{k}|\phi_{0}^{1}\rangle\,,\qquad
j\in\left\\{1...\,d\right\\},\,k\in\left\\{0...\,d-1\right\\},$ (16)

with two diagonal $(d\times d)$ matrices $B$ and $D$; in other words, all
states of the complete set of MU bases can be generated easily from any given
state such as $|\phi_{0}^{1}\rangle$—except for the states of the
computational basis ${\cal B}_{0}$. Within each Hadamard matrix, the matrix
$B$ cyclically shifts a given column to the right,

$B|\phi_{k}^{j}\rangle=\begin{cases}|\phi_{k+1}^{j}\rangle\,,&k=0,\ldots,\,d-2\,,\\\
|\phi_{0}^{j}\rangle\,,&k=d-1\,;\end{cases}$ (17)

its entries are given by the components of the second column of the Fourier
matrix $F=H_{1}$,

$B=\text{diag}\left(1,\omega^{-1},\ldots,\omega^{-(d-1)}\right)\,,$ (18)

except for the factor $\sqrt{d}$.

The matrix $D$ is given by the components of the first column of the second
Hadamard matrix $H_{2}$, i.e.

$D=\text{diag}\left(1,\omega^{1},\ldots,\omega^{(d-1)^{2}}\right)\,,$ (19)

cyclically mapping a state of the $j$-th MU basis to the corresponding one of
the MU basis with label $(j+1)$,

$D|\phi_{k}^{j}\rangle=\begin{cases}|\phi_{k}^{j+1}\rangle\,,&j=1,\ldots,\,d-1\,,\\\
|\phi_{k}^{1}\rangle\,,&j=d\,.\end{cases}$ (20)

In terms of Hadamard matrices, this property reads

$DH_{j}=\begin{cases}H_{j+1}\,,&j=1,\ldots,\,d-1\,,\\\
H_{1}\,,&j=d\,.\end{cases}$ (21)

Writing $H_{j}=D^{j-1}H_{1}\equiv D^{j-1}F$, Chebotarëv’s __ theorem is seen
to imply that the minors of all Hadamard matrices $H_{j}$, $j=1\ldots d$, are
non-zero: the ranks of the minors of $F$ do not change upon multiplying their
rows with non-zero scalars. In view of Eq. (12), this generalisation is also
valid for the case of $d=2$.

##  3 Support inequalities$\ldots$

How well can one localise quantum states simultaneously in $(d+1)$ MU bases?
To answer this question, we need to minimise the support sizes of a state
relative to the complete set. In a first step, we now show that the support
sizes of a quantum state relative to any _pair_ of standard MU bases also
satisfy Tao’s bound (9). Second, by combining the resulting pair inequalities,
we establish a state-independent lower bound.

###  3.1 $\ldots$ for arbitrary pairs of MU bases

Tao’s result establishes—for a space of prime dimension $d$ supporting a
cyclic abelian group—a sharp inequality for the support sizes of a quantum
state and its Fourier transform. Most pairs of the MU bases introduced in Eq.
(13) are, however, not related by a Fourier transform. Nevertheless, Tao’s
bound also holds for the supports of the images of any quantum state generated
by two Hadamard matrices as we will show now.

######  Theorem 3.

Given any pair of distinct standard MU bases associated with matrices $H_{j}$
and $H_{k}$, $j,k\in\left\\{0\ldots\,d\right\\}$, the support sizes of a
quantum state $|\psi\rangle\in{\cal H}_{d}$ satisfy the state-independent
sharp bound,

$\|\psi\|_{j}+\|\psi\|_{k}\geq d+1\,,$ (22)

where $d$ is any prime number.

It is important to realise that Theorem 3 does not cover _arbitrary_ pairs of
MU bases in prime dimensions but only those defined in Eq. (14). Nevertheless,
all _pairs_ of MU bases in dimensions $d=2,3$ and $5$ are found to be
completely incompatible since in these dimensions _all_ Hadamard matrices are
equivalent to the Fourier matrix. Already for the next prime, $d=7$, other
types of Hadamard matrices exist [32].

###### Proof.

The case of dimension $d=2$ is straightforward. If a state
$|\psi\rangle\in{\cal H}_{2}$ has support one in one MU basis, it must have
support two in both other bases, due to being MU to their members. Thus, the
sum of the supports of any state in two bases must be at least three.

For odd primes $d,$we will consider two cases separately: either _$(i)$_ one
of the bases in Eq. (22) is the computational basis, so that $j=0$, say, or
_$(ii)$_ neither of them.

$(i)$ Defining the vector $\phi=D^{1-k}\psi$, we obtain

$\|\psi\|_{0}+\|\psi\|_{k}=\|\psi\|_{0}+\|H_{k}^{\dagger}\psi\|_{0}=\|\psi\|_{0}+\|F^{\dagger}D^{1-k}\psi\|_{0}=\|D^{k-1}\phi\|_{0}+\|F^{\dagger}\phi\|_{0}\,,$
(23)

recalling that $H_{k}=D^{k-1}F$ holds according to Eq. (21). Since $D$ is a
diagonal unitary hence a support-conserving unitary matrix (cf. (3)), we
obtain

$\|\psi\|_{0}+\|\psi\|_{k}=\|\phi\|_{0}+\|F^{\dagger}\phi\|_{0}\geq d+1\,,$
(24)

where Tao’s theorem was used in the last step.

$(ii)$ Now consider the case where the non-zero labels $j$ and $k$ differ from
each other. Defining the vector $\phi=H_{j}^{\dagger}\psi$, the sum of the
support sizes can be written as

$\|\psi\|_{j}+\|\psi\|_{k}=\|H_{j}^{\dagger}\psi\|_{0}+\|H_{k}^{\dagger}\psi\|_{0}=\|\phi\|_{0}+\|H_{k}^{\dagger}H_{j}\phi\|_{0}\,.$
(25)

The product $H_{k}^{\dagger}H_{j}$ of two distinct Hadamard matrices is, in
fact, always equal to another Hadamard matrix $H_{t}^{\dagger}$, $t\neq 0$, up
to a monomial matrix $M(j,k)$; this result is the content of Lemma 3.1 stated
directly after the proof. As the matrix $M(j,k)$ is support-conserving (cf.
Eqs. (3) and (4)) for all states of the space $\mathcal{H}_{d}$, we find

$\|\phi\|_{0}+\|M(j,k)H_{t}^{\dagger}\phi\|_{0}=\|\phi\|_{0}+\|H_{t}^{\dagger}\phi\|_{0}\geq
d+1\,,$ (26)

where (24) of Part $(i)$ has been used in the final step. ∎

The proof just relies on dissolving products of the Hadamard matrices $H_{j}$
which encode a complete set of MU bases. Clearly, products of the form
$H_{k}^{\dagger}H_{j}$, $j\neq k$, are Hadamard matrices since their matrix
elements, being overlaps of MU vectors, have modulus $1/\sqrt{d}$,

$\left[H_{k}^{\dagger}H_{j}\right]_{\ell\ell^{\prime}}=\langle\phi_{\ell}^{k}|\phi_{\ell^{\prime}}^{j}\rangle\,.$
(27)

When $d=2$, one finds explicitly that $H_{1}^{\dagger}H_{2}=MH_{2}^{\dagger}$
and $H_{2}^{\dagger}H_{1}=M^{\prime}H_{2}^{\dagger}$, with monomial matrices
$M$ and $M^{\prime}$. In other words, the phases of the matrix elements (27)
coincide with those of the adjoint of another transition matrix after
permuting and rephasing its rows. This property actually holds for any prime
dimension.

lemproductHadamardlemma

Let $d$ be an odd prime and $j,k\in\left\\{1\ldots\,d\right\\}$ with $j\neq
k$. Then

$H_{k}^{\dagger}H_{j}=M(j,k)H_{t}^{\dagger}$ (28)

for a monomial matrix $M(j,k)$ if and only if
$t=1+\chi\in\left\\{1,\ldots,d\right\\}$ where the integer $\chi$ satisfies
$4\left(j-k\right)\chi=1\mod d$.

###### Proof.

See Appendix. ∎

Furthermore, Lemma 3.1 allows us to generalise Chebotarëv’s theorem to the
product matrices $H_{k}^{\dagger}H_{j}$, for distinct indices $j$ and $k$.

[]corCheboThmHadamard

If $d$ is prime, then all minors of the Hadamard matrices
$H_{k}^{\dagger}H_{j}$, $j,k\in\\{0\ldots d\\}$ and $j\neq k$, are non-zero.

###### Proof.

Let $d$ be an odd prime. Any $H_{t}$, $t\in\\{1\ldots d\\}$, has only non-zero
minors, as was mentioned after Eq. (21), as do the adjoints $H_{t}^{\dagger}$.
Therefore, the claim holds if one of the labels $j,k$, is zero. For both
$j,k\neq 0$, Lemma 3.1 applies. Since rephasing and permuting the rows of a
matrix do not change the rank of any submatrix, we can conclude that the
matrices $H_{k}^{\dagger}H_{j}$, $j,k\neq 0$ and $j\neq k$ also have non-zero
minors only.

In dimension $d=2$, the result follows from inspecting the products
$H_{1}^{\dagger}H_{2}=MH_{2}^{\dagger}$ and
$H_{2}^{\dagger}H_{1}=M^{\prime}H_{2}^{\dagger}$. ∎

According to Corollary 3.1 the vectors formed by the columns (or rows) of all
square submatrices of the Hadamard matrices $H_{k}^{\dagger}H_{j}$, $j\neq k$,
are linearly independent. What is more, up to $d$ vectors taken from any two
MU bases are linearly independent.

[]corlinearindepcorollary

Given a complete standard set of MU bases in the space $\mathcal{H}_{d}$ of
prime dimension $d$, up to $d$ vectors taken from any two MU bases are
linearly independent.

###### Proof.

See Appendix. ∎

Theorem 3 also demonstrates that all pairs of MU bases taken from the complete
standard set in prime dimension are completely __ incompatible _, in the sense
of Sec._ 2.1. This statement is stronger than the results of [7, 10] since the
bases we consider are not necessarily related by the Fourier matrix $F$.

###  3.2 $\ldots$ for complete sets of $(d+1)$ MU bases

Let us denote the sum of the numbers of non-zero expansion coefficients of a
state $\psi\in\mathcal{H}_{d}$ in a complete standard set of MU bases by

${\cal S}(d)=||\psi||_{0}+||\psi||_{1}+\dots+||\psi||_{d}\,.$ (29)

Then, the inequalities (22) imply that the overall support size
$\mathcal{S}(d)$ cannot fall below a certain threshold. This is a central
result of our paper.

######  Theorem 4.

For any prime $d$, the overall support ${\cal S}(d)$ of a quantum state
$|\psi\rangle\in{\cal H}_{d}$ in a complete standard set of MU bases satisfies
the additive state-independent bound

${\cal S}(d)\geq\frac{\left(d+1\right)^{2}}{2}\equiv T(d)\,.$ (30)

###### Proof.

Write down $(d+1)$ copies of the support inequality (22) with indices
$(j,j+1)$, $j=0,\ldots\,d-1$, and $(d,0)$, respectively. Adding them up, the
right-hand-sides of (22) give $(d+1)^{2}$, and since each term
$||\psi||_{j}\equiv\|H_{j}^{\dagger}\psi\|_{0}$, $j=0,\ldots,\,d$, occurs
twice on the left, one obtains the inequality (30). ∎

An alternative proof treats all pair supports equally: write down (22) for all
$d(d+1)$ distinct pairs of indices $(j,k)$ and consider the sum of the
supports. After removing common factors, the bound (30) on ${\cal S}(d)$
follows.

Support inequalities other than Eqs. (22) and (30) exist. They may involve any
number between two and $(d+1)$ MU bases. For example, picking the first three
MU bases and combining the associated pair inequalities from (22) leads to the
additive “triple support inequality”,

${\cal
S}(d;3)\equiv\|\psi\|_{0}+\|F^{\dagger}\psi\|_{0}+\|H_{2}^{\dagger}\psi\|_{0}\geq\frac{3}{2}(d+1)\,.$
(31)

Clearly, this inequality cannot be saturated for dimension $d=2$ because the
overall support ${\cal S}(2)$ of a state is always an integer number. Taking
only two possible values, the smallest achievable value of the triple support
size ${\cal S}(2;3)\equiv{\cal S}(2)$ equals $T_{s}(2)=5$; here and in the
following, _achievable_ —or _sharp_ —bounds of $\mathcal{S}(d)$ are denoted by
$T_{s}(d)$.

The lower bound on the triple uncertainty relation for continuous variables
[18], derived similarly by combining pair uncertainty relations, can also not
be reached. Theorem 4 is not constructive, hence it is not obvious whether the
case of $d=2$ represents an exception or whether the inequalities (30) are
never sharp. In the next section we will first derive some general results
about multiple-support inequalities, followed by a closer look at dimensions
$3\leq d\leq 19$.

##  4 Saturating support inequalities for MU bases

To saturate the bound of the inequality (30) means to identify states that
minimise all support pair relations simultaneously. We present a number of
rigorous results for prime dimensions $d\leq 7$. Numerical methods are then
used to determine whether the generalised inequality can be saturated for
dimensions up to $d=19$.

###  4.1 Constraints on saturating states

Our first general result is a necessary and sufficient condition that the
support inequality (30) involving a complete set of $(d+1)$ MU bases be
saturated.

######  Theorem 5 (Equal support sizes).

The additive support inequality for a complete standard set of MU bases (30)
is saturated by a state $\psi\in{\cal H}_{d}$ if and only if it has the same
support in all $(d+1)$ MU bases, i.e.

$||\psi||_{j}=\frac{d+1}{2}\,,\qquad j\in\left\\{0...\,d\right\\}\,,$ (32)

where $d$ is an odd prime.

###### Proof.

Substituting the values (32) into (30) directly produces the lower bound.

For the converse, we show that the supports must have the values given in (32)
if equality holds in Eq. (30). Noting that the support of any state
$\psi\in{\cal H}_{d}$ ranges from $1$ to $d$, i.e.

$\|\psi\|_{0}=\frac{d+1}{2}\pm\Delta\,,\qquad\Delta\in\left\\{0,1,\ldots,\,\frac{1}{2}(d-1)\right\\}\,,$
(33)

we will proceed by exhausting all its values in the computational basis
$\mathcal{B}_{0}$. It turns out that the the minimum in (30) cannot be reached
if the support is either $(i)$ smaller or $(ii)$ larger than $(d+1)/2$,
leaving $(iii)$ the values in (32) as the only option.

$(i)$ If $\|\psi\|_{0}=\left(d+1\right)/2-\Delta$, $\Delta>0$, then (22)
implies that $\|\psi\|_{j}\geq\left(d+1\right)/2+\Delta$,
$j=\left\\{1\ldots\,d\right\\}$. Hence, the sum of the supports in all $(d+1)$
MU bases equals

$\displaystyle\mathcal{S}(d)=\sum_{j=0}^{d}\|\psi\|_{j}$
$\displaystyle\geq\frac{d+1}{2}-\Delta+d\left(\frac{d+1}{2}+\Delta\right)$
(34) $\displaystyle\geq\frac{(d+1)^{2}}{2}+(d-1)\Delta>\frac{(d+1)^{2}}{2}\,.$

Therefore, the inequality cannot be saturated by a state which has support
smaller than $\left(d+1\right)/2$ in the basis $\mathcal{B}_{0}$.

$(ii)$ Assume that $\|\psi\|_{0}=\left(d+1\right)/2+\Delta$, $\Delta>0$.
Clearly, the lower bound of the sum in Eq. (30) can only be reached if the
support of the state $\psi$ is smaller than $(d+1)/2$ in at least one of the
MU bases, $\|\psi\|_{j^{*}}<\left(d+1\right)/2$,
$j^{*}\in\left\\{1\ldots\,d\right\\}$, say. Repeating the argument from $(i)$
relative to the MU basis $\mathcal{B}_{j^{*}}$ instead of $\mathcal{B}_{0}$
implies that the inequality (30) cannot be saturated.

$(iii)$ If $\|\psi\|_{0}=\left(d+1\right)/2$ then (22) implies that
$\|\psi\|_{j}\geq\left(d+1\right)/2$, $j=\left\\{1\ldots\,d\right\\}$.
However, given these bounds, the minimum of $\mathcal{S}(d)$ in (30) can be
achieved only if the support of the state $\psi\in{\cal H}_{d}$ takes the
value $\left(d+1\right)/2$ in all other MU bases as well. ∎

The second general result states that a specific $d$-th root of unity can
appear at most _twice_ in the columns of the Hadamard matrices $H_{j}$,
$j=2\ldots d$, given in (14). The proof of another necessary–but not
sufficient–condition for saturating the generalised inequality (30) will rely
on this limit of the occurrences of roots. The property also applies to
$H_{1}=F$ where each root appears exactly once in every column, as is seen by
inspecting (6).

[Frequency of roots]lemfrequencyofroots

Let $d$ be prime and consider the states $|\phi_{k}^{j}\rangle$,
$j=2,\ldots,\,d$, in Eq.__(13) forming the bases $\mathcal{B}_{j}$ which are
MU to both the identity and the Fourier matrix. Any $d$-th root $\omega^{n}$,
$n\in\\{0\ldots d\\}$, figures at most twice among the numbers
$\sqrt{d}\langle x|\phi_{k}^{j}\rangle$, $x\in\left\\{0\ldots\>d-1\right\\}$.

###### Proof.

We need to determine the number of solutions of the equation
$\omega^{-kx+\left(j-1\right)x^{2}}=\omega^{n}$ which becomes
$\left(j-1\right)x^{2}-kx-n\mod d=0$ upon taking the logarithm and
rearranging. Since $j\neq 1$, the equation is quadratic for each $n$ and there
can be at most two integer solutions for the unknown $x$. The extension to the
special case of $d=2$ is trivial. ∎

According to Theorem 5, a state saturating (30) must have $(d-1)/2$ vanishing
expansion coefficients in each MU basis of the standard set, in any odd prime
dimension. A third general result is that there are constraints on the
distributions of these zeroes when expanded in the MU bases of a complete set.

To spell out these constraints, let us introduce the zero distributions
$\mathcal{Z}^{j}$ of a state $\psi\in{\cal H}_{d}$ which list the indices of
the vanishing expansion coefficients in the $\left(d+1\right)$ bases of the
complete set,

$\mathcal{Z}^{j}=\left\\{\kappa\in\left\\{0\ldots\,d-1\right\\}:\langle\phi_{\kappa}^{j}|\psi\rangle=0\right\\}\,,\qquad
j=0,\ldots,\,d\,.$ (35)

Using the relation
$\langle\phi_{\kappa}^{j}|\psi\rangle=\langle\phi_{\kappa}^{0}|H_{j}^{\dagger}|\psi\rangle$,
one can also think of $\mathcal{Z}^{j}$ as the set of vanishing coefficients
of the state $H_{j}^{\dagger}|\psi\rangle$ in the computational basis.

Two zero distributions of vectors in the same Hilbert space are said to be
compatible _,___ $\mathcal{Z}\sim\mathcal{Z}^{\prime}$, if they are equal up
to a cyclic shift. In other words, two compatible distributions
$\mathcal{Z}=\left\\{\kappa_{1},\kappa_{2},...,\kappa_{\delta}\right\\}$ and
$\mathcal{Z}^{\prime}=\left\\{\kappa_{1}^{\prime},\kappa_{2}^{\prime},...,\kappa_{\delta}^{\prime}\right\\}$
must have the same number $\delta$ of elements and the mapping
$\kappa_{i}\mapsto\kappa_{i}+\mu\,\mod d$ for some fixed integer $\mu$ must be
a bijection from $\mathcal{Z}$ to $\mathcal{Z}^{\prime}$. Compatibility of
zero distributions is an equivalence relation between classes of $d$ elements.

The extension of Chebotarëv’s Theorem shown in Sec. 3.1 and Lemma 4.1 imply a
constraint on zero distributions for all prime dimensions $d>3$. This property
will be used in Sec. 4.3 to prove that the support inequality (30) _cannot_ be
saturated in dimensions $d=5$ and $d=7$.

######  Theorem 6.

Let $d>3$ be prime and $\psi\in\mathcal{H}_{d}$ be a state with $(d-1)/2$
expansion coefficients vanishing in the computational basis and in two more
standard MU bases, i.e.

$\|\psi\|_{0}=\|\psi\|_{j_{1}}=\|\psi\|_{j_{2}}=\frac{d+1}{2}\,,\qquad
j_{1}>j_{2}\neq 0\,.$ (36)

Then the zero distributions associated with the vectors
$H_{j_{1}}^{\dagger}|\psi\rangle$ and $H_{j_{2}}^{\dagger}|\psi\rangle$,
respectively, are incompatible.

###### Proof.

Since the state $\psi$ has $d_{-}\equiv(d-1)/2$ vanishing components in three
bases with labels $j=0,j_{1},j_{2}$, it satisfies $3d_{-}$ conditions,

$\displaystyle\langle\phi_{\kappa_{1}^{0}}^{0}|\psi\rangle$
$\displaystyle=\langle\phi_{\kappa_{2}^{0}}^{0}|\psi\rangle=\ldots=0\,,\qquad\mathcal{Z}^{0}=\left\\{\kappa_{1}^{0},\kappa_{2}^{0},\ldots,\kappa_{d_{-}}^{0}\right\\}\,,$
$\displaystyle\langle\phi_{\kappa_{1}^{1}}^{j_{1}}|\psi\rangle$
$\displaystyle=\langle\phi_{\kappa_{2}^{1}}^{j_{1}}|\psi\rangle=\ldots=0\,,\qquad\mathcal{Z}^{j_{1}}=\left\\{\kappa_{1}^{1},\kappa_{2}^{1},\ldots,\kappa_{d_{-}}^{1}\right\\}\,,$
(37) $\displaystyle\langle\phi_{\kappa_{1}^{2}}^{j_{2}}|\psi\rangle$
$\displaystyle=\langle\phi_{\kappa_{2}^{2}}^{j_{2}}|\psi\rangle=\ldots=0\,,\qquad\mathcal{Z}^{j_{2}}=\left\\{\kappa_{1}^{2},\kappa_{2}^{2},\ldots,\kappa_{d_{-}}^{2}\right\\}\,.$

We proceed by contradiction. To assume that the zero distributions
$\mathcal{Z}^{j_{1}}$ and $\mathcal{Z}^{j_{2}}$ _are_ compatible means that
they are related by a cyclic shift by some integer $\mu\in\\{0\ldots d-1\\}$.
In particular, we can arrange the elements in the two sets such that

$\kappa_{i}^{2}=\kappa_{i}^{1}+\mu\quad\text{mod}\,d\qquad\text{for all}\quad
i\in\left\\{1\ldots d_{-}\right\\}.$ (38)

Then, according to Eq. (16), the corresponding states must be related by
powers of the matrices $D$ and $B$,

$|\phi_{\kappa_{i}^{2}}^{j_{2}}\rangle=D^{j_{2}-1}B^{\kappa_{i}^{2}}|\phi_{0}^{1}\rangle=D^{j_{2}-1}B^{\kappa_{i}^{2}}D^{-j_{1}+1}B^{-\kappa_{i}^{1}}|\phi_{\kappa_{i}^{1}}^{j_{1}}\rangle=D^{j_{2}-j_{1}}B^{\mu}|\phi_{\kappa_{i}^{1}}^{j_{1}}\rangle\,,$
(39)

where we have used the fact that $D$ and $B$ commute. Defining
$V_{\mu}^{\dagger}=D^{j_{2}-j_{1}}B^{\mu}$, the third set of conditions in
(37) turns into

$\langle\phi_{\kappa_{i}^{2}}^{j_{2}}|\psi\rangle=\langle\phi_{\kappa_{i}^{1}}^{j_{1}}|V_{\mu}\psi\rangle=0\qquad\text{for
all}\quad i\in\left\\{1\ldots d_{-}\right\\}.$ (40)

Since $V_{\mu}$ is diagonal in the computational basis, we have

$\langle\phi_{\kappa_{i}^{0}}^{0}|\psi\rangle=\langle\phi_{\kappa_{i}^{0}}^{0}|V_{\mu}\psi\rangle=0\qquad\text{for
all}\quad i\in\left\\{1\ldots d_{-}\right\\}\,,$ (41)

which means that $\mathcal{Z}^{0}$ and $\mathcal{Z}^{j_{1}}$ are zero
distributions for the pair of vectors $\psi$ and $V_{\mu}\psi$. In other
words, these two states are both orthogonal to the same set of
$2d_{-}=\left(d-1\right)$ vectors

$\left\\{\phi_{\kappa_{1}^{0}}^{0},\ldots,\phi_{\kappa_{d_{-}}^{0}}^{0},\phi_{\kappa_{1}^{1}}^{j_{1}},\ldots,\phi_{\kappa_{d_{-}}^{1}}^{j_{1}}\right\\},$
(42)

stemming from the computational basis $\mathcal{B}_{0}$ and the basis
$\mathcal{B}_{j_{1}}$. According to Corollary 3.1, this is a set of $(d-1)$
linearly independent vectors so that only one unique ray in $\mathcal{H}_{d}$
can exist that is orthogonal to all of them. Therefore, the vectors $\psi$ and
$V_{\mu}\psi$ must be collinear, i.e. $V_{\mu}\psi=\lambda\psi$ for some non-
zero scalar $\lambda\in\mathbb{C}$.

Since $V_{\mu}=D^{j_{1}-j_{2}}B^{-\mu}$ is diagonal in $\mathcal{B}_{0}$, the
computational basis states are eigenvectors of $V_{\mu}$. By assumption, the
state $\psi$ has $d_{+}\equiv\left(d+1\right)/2$ non-zero coefficients in this
basis. Thus, the state $\psi$ will be an eigenvector of the unitary $V_{\mu}$
only if $\lambda$ is an eigenvalue with multiplicity of $d_{+}$ (at least).
However, this is impossible for prime dimensions $d>3$: the non-zero matrix
elements on the diagonal of $V_{\mu}$ coincide with the components of the
vector$\sqrt{d}|\phi_{-\mu}^{j_{1}-j_{2}+1}\rangle$ in the computational basis
but for $j_{1}>j_{2}\neq 0\,\left(\text{mod}\,d\right)$ no more than two of
the components may coincide according to Lemma 4.1. Thus, at most two of the
eigenvalues of $V_{\mu}$ can coincide. No contradiction arises for dimension
$d=3$ where $\psi$ has exactly two non-vanishing coefficients in the
computational basis. ∎

###  4.2 Dimension $d=3$

To prove that the bound (30) can be achieved in the space $\mathcal{H}_{3}$,
we exhibit the states which minimise the support inequality.

######  Theorem 7.

The state $\psi$ saturates the generalised support inequality (30) in
dimension $d=3$ if and only if it is one of the following nine (non-
normalised) qutrit states,

$\begin{pmatrix}1\\\ -\omega^{m}\\\ 0\end{pmatrix}\,,\quad\begin{pmatrix}1\\\
0\\\ -\omega^{m}\end{pmatrix}\,,\quad\begin{pmatrix}0\\\ 1\\\
-\omega^{m}\end{pmatrix}\,,\qquad m\in\left\\{0,1,2\right\\}\,,$ (43)

with $\omega\equiv e^{2i\pi/3}$ being a third root of unity.

###### Proof.

Theorem 5 implies that a state $\psi$ saturates Eq. (30) w.r.t. a complete
standard set of MU bases if and only if it has support two in each of them,
i.e. $||\psi||_{j}\equiv\|H_{j}^{\dagger}\psi\|_{0}=2$, $j=0\ldots 3$. First,
we assume that the third component of a candidate state vanishes in the
computational basis, i.e. $\psi=\begin{pmatrix}a,&b,&0\end{pmatrix}^{T}$, with
non-zero complex numbers $a$ and $b$. Applying the matrices $H_{j}^{\dagger}$,
$j=1,2,3$, to it, we find four vectors,

$\left(\begin{array}[]{c}a\\\ b\\\
0\end{array}\right)\,,\left(\begin{array}[]{c}a+b\\\ a+\omega b\\\
a+\omega^{2}b\end{array}\right)\,,\left(\begin{array}[]{c}a+\omega^{2}b\\\
a+b\\\ a+\omega b\end{array}\right)\,,\left(\begin{array}[]{c}a+\omega b\\\
a+\omega^{2}b\\\ a+b\end{array}\right)\,.$ (44)

The components of the last three vectors agree, except for permutations.
Hence, support size two can occur in three different ways: one component of
each vector vanishes if

$b=-\omega^{m}a\,,\qquad m\in\left\\{0,1,2\right\\}\,,$ (45)

holds for some value of $m$. After removing an irrelevant phase, we obtain the
first three vectors given in Eq. (43). Second, repeating this argument for
initial vectors of the form $\psi=\begin{pmatrix}a,&0,&b\end{pmatrix}^{T}$ and
$\psi=\begin{pmatrix}0,&a,&b\end{pmatrix}^{T}$, respectively, leads to the
remaining six vectors in (43).

Having exhausted all three-component vectors in the computational basis with
support two, we have shown that the nine vectors in (43) are the only states
saturating the support inequality (30) for $d=3$. ∎

###  4.3 Dimensions $d=5$ and $d=7$

We will show that it is impossible to reach the lower bound of the support
inequality (30) in dimensions $d=5$ and $d=7$. The proof relies on a property
of the zero distributions of the vectors $H_{j}^{\dagger}\psi$, $j=0\ldots d$,
which were introduced in Sec. 4.1.

######  Theorem 8.

The additive support uncertainty relation (30) cannot be saturated in
dimensions $d=5$ and $d=7$.

###### Proof.

Let $\mathcal{Z}_{n}^{d}$ be the set of the zero distributions with $n$ zeroes
among the computational-basis coefficients of qudit states in the Hilbert
space $\mathcal{H}_{d}$. These distributions are determined by choosing $n$
out of $d$ indices; hence, there are $|\mathcal{Z}_{n}^{d}|=\binom{d}{n}$ such
sets. Recalling that _compatible_ sets of zero distributions form equivalence
classes, obtained from rigidly shifting a given one, only
$|\mathcal{Z}_{n}^{d}/\sim|=\binom{d}{n}/d$ _inequivalent_ zero distributions
exist.

According to Theorem 5, a state $|\psi\rangle\in\mathcal{H}_{d}$ saturating
(30) for $d>3$, must have $n=(d-1)/2$ zeroes in each basis. In addition, a
saturating state requires the existence of at least $d$ _incompatible_ zero
distributions as Theorem 6 does not allow compatible zero distributions for
more than two bases. In other words, the inequality
$|\mathcal{Z}_{(d-1)/2}^{d}/\sim|\geq d$ must hold. Clearly, this does not
happen for $d=5$ and $d=7$ since $|\mathcal{Z}_{2}^{5}/\sim|=2<5$ and
$|\mathcal{Z}_{3}^{7}/\sim|=5<7$ , respectively. When $d\geq 11,$ however, the
inequality is satisfied, with $|\mathcal{Z}_{5}^{11}/\sim|=42>11$, for
example. ∎

###  4.4 Numerical results for $5\leq d\leq 19$

For prime numbers $d$ greater than seven, more than $d$ incompatible zero
distributions exist which removes the bottleneck we exploited to prove Theorem
8. In the absence of an analytic handle on the problem, we will use numerical
means to check whether the bound imposed by (30) can be reached for dimensions
larger than $d=7$.

A saturating state necessarily has $(d-1)/2$ zeroes in each MU basis. Thus, if
one picks two distinct MU bases with labels
$j_{1},j_{2}\in\left\\{0\ldots\,d\right\\}$, say, with corresponding zero
distributions $\mathcal{Z}^{j_{1}}$ and $\mathcal{Z}^{j_{2}}$, the state will
have vanishing scalar products with a total of $(d-1)$ states which—in view of
Corollary 3.1—are known to be linearly independent. Consequently, there is a
_unique_ ray $\psi^{\perp}\in\mathcal{H}_{d}$ associated with any two zero
distributions of the type considered. If the support size of the states
$\psi^{\perp}$ generated in this way (i.e. for all possible choices of initial
zero distributions $\mathcal{Z}^{j_{1}}$ and $\mathcal{Z}^{j_{2}}$) is always
larger than $(d+1)/2$ in some third MU basis, then the support inequality (30)
cannot be saturated: if no state with support size $(d+1)/2$ in _three_ MU
bases exists, then no state with support size $(d+1)/2$ in _$(d+1)$ _MU bases
will exist. Since only a finite number of zero distributions needs to be
checked for a given dimension $d$, this approach actually represents an
_algorithm_ to check whether the lower bound can be reached.

Running the program for prime numbers with $5\leq d\leq 19$ means to check an
exponentially increasing number of cases. On a standard PC, the program ran
about a second for $d=5$ and $d=7$ while it took about a week for $d=17$. No
state has been found which would display $(d-1)/2$ zeroes in three MU bases.
For dimensions $d=5$ and $d=7$, this result is stronger than that of Sec. 4.3
since the non-existence of a state with two and three zeroes, respectively, is
sufficient to derive Theorem 8, but not _vice versa_. Due to the exponential
increase in the number of zero distributions, dimensions larger than $d=19$
were out of of reach.

###  4.5 Dimensions $d>19$

To satisfy the additive support inequality (30) relative to $(d+1)$ MU bases,
a state needs to satisfy more than one pair relation (22) simultaneously which
seems unlikely. It is all the more surprising that for dimension $d=3$ the
bound $T(3)=8$ is actually sharp, i.e. $T_{s}(3)=T(3)$. Our results for prime
dimensions up to $d=19$ suggest that this case is exceptional.

We conjecture that _the generalised uncertainty relation ( 30) in prime
dimensions can only be saturated when $d=3$. _Here is a plausibility argument
to support this view. Assume that a saturating state $\psi\in\mathcal{H}_{d}$
exists for some prime dimension $d\geq 3$. According to Theorem 5, the state
must be orthogonal to exactly $\left(d-1\right)/2$ vectors from each of the
$\left(d+1\right)$ MU bases. Corollary 3.1 implies that orthogonality with
respect to just two such sets—i.e. $\left(d-1\right)$ vectors—already
determines a unique state. Therefore, the remaining $\left(d-1\right)^{2}/2$
vectors (one set of $(d-1)/2$ vectors is associated with each of the $(d-1)$
MU bases not yet considered) must all lie in the same
$\left(d-1\right)$-dimensional subspace orthogonal to the state $\psi$. This
is known to happen for $d=3$ but seems hard to satisfy for larger dimensions.

##  5 Sharp lower bounds

According to the results presented in Sec. 4, no states exist which would
saturate the lower bounds (30) for the support sizes in dimensions up to
$d=19$, with the exception of $d=3$. The focus of this section will be on
identifying achievable bounds.

###  5.1 Dimension $d=3$

Theorem 7 in Sec. 4.2 displays the states which achieve the lower bound (30)
in dimension $d=3$. In other words, the bound for the overall support of
qutrit states $\psi$ is sharp, $\mathcal{S}(3)\geq 8$, where
$\mathcal{S}\left(d\right)\equiv\sum_{j=0}^{d}\|\psi\|_{j}$ for
$\psi\in\mathcal{H}_{d}$.

###  5.2 Dimension $d=5$

Theorem 8 shows that, for any state $\psi\in\mathcal{H}_{5}$, the overall
support of the states $H_{j}^{\dagger}\psi$, $j=\left\\{0\ldots d\right\\}$,
must satisfy $\mathcal{S}(5)>18$. In this section, we will prove a sharp lower
bound, namely $\mathcal{S}(5)\geq 22\equiv T_{s}(5)$.

To begin, we generalise Lemma 4.1 which will be necessary for the proof of
Lemma 5.2.

lemidenticalentries

Let $d$ be an odd prime and $\omega\equiv e^{\frac{2i\pi}{d}}$. Consider two
states
$|\phi_{k_{1}}^{j_{1}}\rangle,|\phi_{k_{2}}^{j_{2}}\rangle\in\mathcal{H}_{d}$
taken from different standard MU bases, $j_{1},j_{2}\neq 0$, and let
$\left\\{|x\rangle\right\\}$ be the computational basis. Then there can be at
most two values of $x\in\left\\{0\ldots d-1\right\\}$ such that

$\langle x|\phi_{k_{1}}^{j_{1}}\rangle=\omega^{n}\langle
x|\phi_{k_{2}}^{j_{2}}\rangle$ (46)

for the same value of $n\in\left\\{0...d-1\right\\}$. If two different states
are taken from the same basis, $j_{1}=j_{2}$, then the equation has exactly
one solution for each value of $n$.

###### Proof.

See Appendix. ∎

Now consider a state with two vanishing expansion coefficients in both the
computational basis and a second basis of the complete set. It turns out that
such a state can have only non-zero coefficients in the remaining four bases,
resulting in a total support size of 26.

lemrestrictionfivedim

If the support of a state $\psi\in\mathcal{H}_{5}$ equals three in both the
computational basis and another standard MU basis with label $j\neq 0$, i.e.
$\|\psi\|_{0}=\|\psi\|_{j}=3$, then its support size in each of the remaining
four bases equals five, $\|\psi\|_{j^{\prime}}=5$, with $j^{\prime}\neq 0,j$.

###### Proof.

The proof, given in Appendix, uses Corollary 3.1 and Lemma 5.2. ∎

This result allows us to determine a sharp bound $T_{s}(5)$ for the support
size $\mathcal{S}(5)$.

######  Theorem 9.

Given a state $\psi\in\mathcal{H}_{5}$, the sharp bound on its overall support
size $\mathcal{S}(5)$ in a complete standard set of MU bases is given by
$T_{s}(5)=22$.

###### Proof.

To construct the bound, we go through all possible values of the support size
of the state $\psi$ in the computational basis, i.e.
$\|\psi\|_{0}\in\left\\{1\ldots\,5\right\\}$.

For $\|\psi\|_{0}=1$, the pair inequalities (22) imply that the state $\psi$
must have full support in all other five MU bases, i.e. $\|\psi\|_{j\neq
0}=5$. Hence, the overall support of a computational basis state is given by
$\mathcal{S}(5)=26$.

For $\|\psi\|_{0}=2$, the pair inequalities (22) imply that the state $\psi$
can have at most one zero in each of the other five MU bases, i.e.
$\|\psi\|_{j\neq 0}=4$. Hence, the overall support of $\psi$ is given by
$\mathcal{S}(5)=22$. All 300 states of the form

$|\psi\rangle=\frac{1}{\sqrt{2}}\left(|\phi_{k_{1}}^{j}\rangle-\omega^{n}|\phi_{k_{2}}^{j}\rangle\right),\qquad
j\in\left\\{0\ldots 5\right\\},\quad k_{1},k_{2},n\in\left\\{0\ldots
4\right\\},\quad k_{1}\neq k_{2}\,.$ (47)

achieve this bound. More generally, for primes $d>3$, there are

$\left(d+1\right)d\binom{2}{d}=\frac{1}{2}\left(d^{2}-1\right)d^{2}$ (48)

such states as $j$ takes $(d+1)$ values, $n$ takes $d$ values and there are
$\binom{2}{d}$ different pairs of $k_{1}$ and $k_{2}$. The three-dimensional
case is an exception, as demonstrated by Theorem 7.

For $\|\psi\|_{0}=3$, the pair inequalities (22) rule out a support size lower
than three in any basis from the set. We apply Lemma 5.2: the support size of
$\psi$ can equal three in only one other MU basis while the state must have
full support in the others, leading to $\mathcal{S}(5)=26$. It is also
possible to have $\|\psi\|_{j}=4$ in all bases but the first one, i.e. for
$j\neq 0$. In this case seven expansion coefficients would vanish over the
complete set, resulting in an overall support size of $\mathcal{S}(5)=23$.
This bound is larger than the one already obtained for the case of
$\|\psi\|_{0}=2$.

If $\|\psi\|_{0}=4$ and all other support sizes are also equal to four, the
resulting overall support of $\mathcal{S}(5)=24$ is again larger that the
previous bound of $\mathcal{S}(5)=22$ obtained for $\|\psi\|_{0}=2$. To
improve on the value of $\mathcal{S}(5)=24$, at least one of the other norms
must fall below four, i.e. $1\leq||\psi||_{j^{*}}\leq 3$ for some $j^{*}\neq
0$. This assumption, however, sends us back to one of the cases already
discussed: we formally map $j^{*}\mapsto 0$ and repeat the arguments given for
$1\leq||\psi||_{0}\leq 3$.

Similarly, full support in all six MU bases cannot beat any of the bounds
given so far. Improving on the value of $\mathcal{S}(5)=30$ is only possible
by decreasing some of the support sizes, so that we will end up in one of the
previously discussed cases. Having considered all support sizes of a state in
a basis, we have exhausted all possibilities and conclude that the bound on
the overall support of a state $\psi\in\mathcal{H}_{5}$ in six MU bases is
indeed given by $T_{s}(5)=22$. ∎

###  5.3 Dimension $d=7$

Our aim is to identify states which minimise the overall support
$\mathcal{S}(7)=\sum_{j=0}^{7}\|\psi\|_{j}$. To determine the sharp bound for
$d=7$, we will proceed as in the previous section. However, since no
equivalent to Lemma 5.2 is known, we will partly rely on numerical results.

For $\|\psi\|_{0}=1$, the pair inequalities (22) imply that the state $\psi$
must have full support in all other seven MU bases,$\|\psi\|_{j\neq 0}=7$.
Hence, the overall support of $\psi$ is given by $\mathcal{S}(7)=50$.

For $\|\psi\|_{0}=2$, the pair inequalities (22) imply that the state $\psi$
can have at most one zero in each of the other seven MU bases, i.e.
$\|\psi\|_{j\neq 0}=6$. Hence, the overall support of $\psi$ is given by
$\mathcal{S}(7)=44$, achieved by states of the form

$|\psi\rangle=\frac{1}{\sqrt{2}}\left(|\phi_{k_{1}}^{j}\rangle-\omega^{n}|\phi_{k_{2}}^{j}\rangle\right),\qquad
j\in\left\\{0\ldots 7\right\\},\quad k_{1},k_{2},n\in\left\\{0\ldots
6\right\\},\quad k_{1}\neq k_{2}\,.$ (49)

According to Eq. (48), there are 1176 such states.

For $\|\psi\|_{0}=3$, the smallest possible value of $\mathcal{S}(7)$
compatible with the pair inequalities is $\mathcal{S}(7)=38$, as the states in
the other bases must have support size at least five each, i.e.
$\|\psi\|_{j\neq 0}=5$. However, no state achieving this bound has been found
(numerically). The computations show that a state with support sizes three and
five in two MU bases must have full support in the remaining six MU bases so
that $\mathcal{S}(7)=50$. Assuming support size six in all but the first MU
basis, the overall support would be $\mathcal{S}(7)=45$ which is higher than
the bound of $\mathcal{S}(7)=44$ achievable for $\|\psi\|_{0}=2$ .

Given a support size of four in the first MU basis, $\|\psi\|_{0}=4$, not all
other support sizes can be equal to four according to Theorem 8. One case
corresponds a state having support size four in the first and one other MU
basis. It is possible to (numerically) construct states for which the
remaining six supports sizes must be equal to six, leading to
$\mathcal{S}(7)=44$. We neither know analytic expressions for these states nor
their total number. The other scenario compatible with $\|\psi\|_{0}=4$
corresponds to the remaining seven support sizes each equalling five,
i.e.$\|\psi\|_{j\neq 0}=5$, leading to $\mathcal{S}(7)=39$ but we have
obtained no evidence for a state achieving this value.

Assume now that $\|\psi\|_{0}=5$ and that the support of $\psi$ in the other
MU bases is also at least five (we exclude all cases with $||\psi||_{j^{*}}<5$
for some $j^{*}\neq 0$ since—upon relabeling the MU bases—they have
effectively already been considered). An overall support of
$\mathcal{S}(7)=40$ results, below the previously obtained value of
$\mathcal{S}(7)=44$ for $\|\psi\|_{0}=2$. Numerically searching for states
achieving this bound, we find that pairs of states with support size five in
two MU bases exist but no triples, ruling out the value $\mathcal{S}(7)=40$.
Assuming support size five in two bases and at least six in the remaining six
MU bases leads to a higher support size, $\mathcal{S}(7)=46$.

Starting out with a support size of $\|\psi\|_{0}>5$, no smaller lower bound
will exist if all other support sizes take a value of at least six as
$\mathcal{S}(7)\geq 48$ follows immediately. If not all support sizes take a
value of at least six we are being sent back to a previously discussed case.
Thus, we have established the sharp bound of $T_{s}(7)=44$ on the overall
support of seven-component vectors in eight MU bases, partly relying on
numerics.

##  6 Summary and Conclusions

Tao’s uncertainty relation provides a lower bound on the sum of the support
sizes of a state $\psi\in\mathcal{H}_{d}$ in the standard basis and its
Fourier transform, for prime dimensions $d$. By generalising the bound to
arbitrary pairs of mutually unbiased bases (cf. Theorem 3), we show in Theorem
4 that the sum of the support sizes of a state $\psi$ in a complete standard
set of $\left(d+1\right)$ MU bases cannot fall below $T(d)\equiv(d+1)^{2}/2$.
The bound is found to be sharp for $d=3$, and proofs were given that it cannot
be saturated for dimensions $d=2$, $5$ and $7$. Numerical results indicate
that no states exist which achieve the bound for prime numbers up to $d\leq
19$. Table 1 summarises these results. We conjecture that the inequality is
saturated in dimension $d=3$ only.

$d$ | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19
---|---|---|---|---|---|---|---|---
$T(d)$ | 9/2 | 8 | 18 | 32 | 72 | 98 | 162 | 200
$T(d)$ achievable? | $\times$ | $\checkmark$ | $\times$ | $\times$ | $(\times)$ | $(\times)$ | $(\times)$ | $(\times)$
$T_{s}(d)$ | 5 | 8 | 22 | (44) | ? | ? | ? | ?
Table 1: Lower and sharp bounds $T(d)$ and $T_{s}(d)$, respectively, on the
support sizes of states $\psi\in\mathcal{H}_{d}$ when expanded in the complete
standard set of $(d+1)$ MU bases, for small prime dimensions (numerical
results in parentheses).

Tao’s pair support inequality has been used to identify _KD-nonclassical_
states, i.e. states whose Kirkwood-Dirac quasiprobability distribution has
negative or complex contributions [10]. Given two orthonormal bases of a
finite-dimensional space $\mathcal{H}_{d},d\in\mathbb{N},$ with no common
elements, a state $\psi$ is found to be KD-nonclassical if the sum of its
support sizes in these bases is greater than $\left(d+1\right)$. KD-
classicality is readily generalised to complete sets of MU bases instead of
pairs only. In this context, the results of Sec. 4 mean that no states exist
which are KD-classical with respect to the standard set of $(d+1)$ MU bases in
small prime dimensions. When $d=3$, the claim follows by directly computing
the complex KD distributions of the nine minimal uncertainty states of Eq.
(43).

The uncertainty of quantum states involving more than two MU bases has been
studied before. Building on a result for a pair of mutually unbiased
observables [33], entropic uncertainty relations have been found which involve
$(d+1)$ MU bases [22, 23]. Similarly, Heisenberg’s uncertainty relation for
continuous variables has a counterpart based on _three_ observables satisfying
the canonical commutation relation pairwise [18]. Often, the generalisations
are straightforward but the resulting inequalities tend not to be achievable.
Sharp bounds and the minimising states are usually difficult to find (see e.g.
[34, 19] and the review [35]). In this respect, the additive inequality
proposed here is no exception.

Support uncertainty relations for multiple MU bases have many interesting
features. As for the pair inequalities, a _finite_ number of measurements can
be sufficient to confirm that a quantum state satisfies a specific bound. The
minimum number of required measurements is simply given by the value of the
relevant bound, be it sharp or not: it is sufficient that $T(d)$ different
outcomes be registered when measurements in the MU bases are performed on the
state $\psi$. This property also ensures that KD-nonclassicality may sometimes
be detected with a finite number of measurements.

Furthermore, the lower bounds of support inequalities neither depend on the
state considered nor on the value of Planck’s constant. The absence of $\hbar$
as a parameter suggests that no support inequalities for continuous variables
will emerge in the limit of systems with ever larger dimensions $d$. The
maximal support size of a quantum state grows without bound and, therefore,
does not approach a well-defined quantitative measure for uncertainty.
Finally, we would like to point out that determining bounds on support sizes
is technically difficult since they are basis-dependent quantities.

Establishing sharp bounds for dimensions $d\geq 11$ remains an open question
which will require new insights since numerical approaches become unfeasible
with increasing dimensions. Other directions of future work will be to study
support uncertainty relations for smaller sets of MU bases such as triples,
for example. The simplification stems from the considerably smaller number of
parameters in comparison to complete MU sets. Preliminary analytical and
numerical results for small prime dimensions $3\leq d\leq 19$ suggest that no
state can saturate the bound $T(d;3)$ on the triple uncertainty relation (31)
for $d\neq 3$.

######  Acknowledgement.

VF would like to thank the WW Smith fund at the University of York for
financial support. The existence of an alternative proof of Lemma 3.1
mentioned in the Appendix has kindly been pointed out by a referee.

## References

  * [1] W. Heisenberg. Über den anschaulichen Inhalt der quantentheoretischen Kinematik und Mechanik. _Zeitschrift für Physik_ , 43(3): 172-198, 1927.
  * [2] E.H. Kennard. Zur Quantenmechanik einfacher Bewegungstypen. _Zeitschrift für Physik_ , 44(4):326-352, 1927.
  * [3] G.B. Folland and A. Sitaram. The Uncertainty Principle: A Mathematical Survey. _Journal of Fourier Analysis and Applications_ , 3(3):207-238, 1997.
  * [4] D.L. Donoho and P.B. Stark. Uncertainty Principles and Signal Recovery. SIAM _Journal on Applied Mathematics_ , 49(3):906-931, 1989.
  * [5] R. Meshulam. An Uncertainty Inequality for Groups of Order $pq$. _European Journal of Combinatorics_ , 13(5):401-407, 1992.
  * [6] A. Wigderson and Y. Wigderson. The Uncertainty Principle: Variations on a Theme. _Bulletin of the American Mathematical Society_ , 58(2):225-261, 2021.
  * [7] T. Tao. An Uncertainty Principle for Cyclic Groups of Prime Order. _Mathematical Research Letters_ , 12(1):121-127, 2005.
  * [8] E.J. Candes, J. Romberg, and T. Tao. Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information. IEEE _Transactions on Information Theory_ , 52(2):489-509, 2006.
  * [9] E.J. Candes and J. Romberg. Quantitative Robust Uncertainty Principles and Optimally Sparse Decompositions. _Foundations of Computational Mathematics_ , 6(2):227-254, 2006.
  * [10] S. De Bièvre. Complete Incompatibility, Support Uncertainty, and Kirkwood-Dirac Nonclassicality. Physical Review Letters, 127(19):190404, 2021.
  * [11] J.G. Kirkwood. Quantum Statistics of Almost Classical Assemblies. _Physical Review,_ 44(1):31-37, 1933\.
  * [12] P.A.M. Dirac. On the Analogy Between Classical and Quantum Mechanics. _Reviews of Modern Physics_ , 17(2):195-199, 1945.
  * [13] D.R.M. Arvidsson-Shukur, N.Y. Halpern, H.V. Lepage, A.A. Lasek, C.H.W. Barnes, and S. Lloyd. Quantum Advantage in Postselected Metrology. _Nature Communications_ , 11(1):3775, 2020.
  * [14] H.F. Hofmann. On the Role of Complex Phases in the Quantum Statistics of Weak Measurements. _New Journal of Physics_ , 13(10):103009, 2011.
  * [15] J. Dressel and A.N. Jordan. Significance of the Imaginary Part of the Weak Value. _Physical Review_ A, 85(1):012107, 2012.
  * [16] D.R.M. Arvidsson-Shukur, J.C. Drori, and N.Y. Halpern. Conditions Tighter than Noncommutation Needed for Nonclassicality. _Journal of Physics A: Mathematical and Theoretical_ , 54(28):284001, 2021.
  * [17] R. Kunjwal, M. Lostaglio, and M.F. Pusey. Anomalous Weak Values and Contextuality: Robustness, Tightness, and Imaginary Parts. _Physical Review_ A, 100(4):042116, 2019.
  * [18] S. Kechrimparis and S. Weigert. Heisenberg Uncertainty Relation for Three Canonical Observables. Physical Review A, 90(6):062118, 2014.
  * [19] S. Kechrimparis and S. Weigert. Geometry of Uncertainty Relations for Linear Combinations of Position and Momentum. _Journal of Physics A: Mathematical and Theoretical_ , 51(2):025303, 2017.
  * [20] V.V. Dodonov, E.V. Kurmyshev, and V.I. Man’ko. Generalized Uncertainty Relation and Correlated Coherent States. _Physics Letters_ A, 79(2):150-152, 1980.
  * [21] V.V. Dodonov. Variance Uncertainty Relations without Covariances for Three and Four Observables. _Physical Review_ A, 97(2):022105, 2018.
  * [22] I.D. Ivanović. An Inequality for the Sum of Entropies of Unbiased Quantum Measurements. _Journal of Physics A: Mathematical and General_ , 25(7):L363-L364, 1992.
  * [23] J. Sánchez. Entropic Uncertainty and Certainty relations for Complementary Observables. _Physics Letters_ A, 173(3):233-239, 1993.
  * [24] M.A. Ballester and S. Wehner. Entropic Uncertainty Relations and Locking: Tight bounds for Mutually Unbiased Bases. _Physical Review_ A, 75(2):022319, 2007.
  * [25] A. Rényi. On measures of entropy and information. _Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability_ , 1:547-561, 1961.
  * [26] P. Stevenhagen and H.W. Lenstra. Chebotarëv and his Density Theorem. _The Mathematical Intelligencer_ , 18(2):26-37, 1996.
  * [27] P.E. Frenkel. Simple Proof of Chebotarëv’s theorem on Roots of Unity. arXiv:math/0312398, 2004.
  * [28] I.D. Ivanović. Geometrical Description of Quantal State Determination. _Journal of Physics A. Mathematical and General_ , 14(12):3241-3245, 1981.
  * [29] W.K. Wootters and B.D. Fields. Optimal State-Determination by Mutually Unbiased Measurements. _Annals of Physics_ , 191(2):363-381, 1989.
  * [30] S. Bandyopadhyay, P.O. Boykin, V. Roychowdhury, and F. Vatan. A New Proof for the Existence of Mutually Unbiased Bases. _Algorithmica_ , 34(4):512-528, 2002.
  * [31] T. Durt. About Mutually Unbiased Bases in Even and Odd Prime Power Dimensions. _Journal of Physics A. Mathematical and General_ , 38(23):5267-5283, 2005.
  * [32] W. Bruzda, W. Tadej, and K. Życzkowski. Catalogue of Complex Hadamard Matrices. Available online at https://chaos.if.uj.edu.pl/~karol/hadamard/, 2006\.
  * [33] H. Maassen and J.B.M. Uffink. Generalized Entropic Uncertainty Relations. _Physical Review Letters_ , 60(12):1103-1106, 1988.
  * [34] S. Wu, S. Yu, and K. Mølmer. Entropic Uncertainty Relation for Mutually Unbiased Bases. _Physical Review_ A, 79(2):022104, 2009.
  * [35] S. Wehner and A. Winter. Entropic Uncertainty Relations — A Survey. _New Journal of Physics_ , 12(2):025009, 2010.
  * [36] B.C. Berndt, K.S. Williams, and R.J. Evans. _Gauss and Jacobi Sums_. Wiley, 1998.
  * [37] M. Neuhauser. An explicit construction of the metaplectic representation over a finite field. _Journal of Lie Theory_ , 12(1):15-30, 2002.

##  7 Appendix

We present proofs of Lemma 3.1, Corollary 3.1 and Lemmata 5.2 and 5.2, in this
order.

*

###### Proof.

Using Eqs. (14), we calculate the matrix elements of the product
$H_{k}^{\dagger}H_{j}$, with $j,k\neq 0$ and $j\neq k$,

$\left[H_{k}^{\dagger}H_{j}\right]_{\ell\ell^{\prime}}=\langle\phi_{\ell}^{k}|\phi_{\ell^{\prime}}^{j}\rangle=\frac{1}{\sqrt{d}}G_{d}(j-k,\ell-\ell^{\prime})\,,$
(50)

with the generalised Gauss sum [36]

$G_{d}(j,\ell)=\frac{1}{\sqrt{d}}\sum_{x=0}^{d-1}\omega^{jx^{2}+\ell x}\,.$
(51)

Using
$1=\omega^{\left(\ell-\ell^{\prime}\right)^{2}\chi}\omega^{-\left(\ell-\ell^{\prime}\right)^{2}\chi}$
in (50) and letting $\chi$ be an integer satisfying
$4\left(j-k\right)\chi\equiv 1\,\mod d$, we obtain a standard Gauss sum
$G_{d}\left(j-k,0\right)$ with known closed form. Explicitly, for $j\neq k$,
we obtain

$\displaystyle G_{d}(j-k,\ell-\ell^{\prime})$
$\displaystyle=\omega^{-\left(\ell-\ell^{\prime}\right)^{2}\chi}\frac{1}{\sqrt{d}}\sum_{x}\omega^{\left(j-k\right)x^{2}+\left(\ell-\ell^{\prime}\right)x}\omega^{\left(\ell-\ell^{\prime}\right)^{2}\chi}$
$\displaystyle=\omega^{-\left(\ell-\ell^{\prime}\right)^{2}\chi}\frac{1}{\sqrt{d}}\sum_{x}\omega^{\left(j-k\right)\left[x+\overline{2}\overline{\left(j-k\right)}\left(\ell-\ell^{\prime}\right)\right]^{2}}$
$\displaystyle=\omega^{-\left(\ell-\ell^{\prime}\right)^{2}\chi}\left[\frac{1}{\sqrt{d}}\sum_{x}\omega^{\left(j-k\right)x^{2}}\right]=\omega^{-\left(\ell-\ell^{\prime}\right)^{2}\chi}G_{d}\left(j-k,0\right)$
$\displaystyle=\omega^{-\left(\ell-\ell^{\prime}\right)^{2}\chi}\left(\frac{j-k}{d}\right)\varepsilon_{d}\,,$
(52)

where $\bar{a}$ denotes the multiplicative inverse of $a$, $\bar{a}a\equiv 1$
mod $d$, while $\left(\frac{a}{b}\right)$ denotes the Jacobi symbol of the
integers $a$ and $b$, and

$\varepsilon_{d}=\begin{cases}1&\text{if}\;d\equiv 1\,\mod 4\,,\\\
i&\text{if}\;d\equiv 3\,\mod 4\,.\end{cases}$ (53)

The sum $G_{d}\left(j-k,\ell-\ell^{\prime}\right)$ in (52) reduces to a phase
factor as it should since the components of the matrix $H_{k}^{\dagger}H_{j}$
are given by the overlap of states stemming from different MU bases.

Combining (50) and (14), we now determine the elements of the matrix $V\equiv
H_{k}^{\dagger}H_{j}H_{t}$ for arbitrary $t\neq 0$:

$V_{\ell\ell^{\prime}}=\sum_{\ell^{\prime\prime}=0}^{d-1}\langle\phi_{\ell}^{k}|\phi_{\ell^{\prime\prime}}^{j}\rangle\langle\ell^{\prime\prime}|\phi_{\ell^{\prime}}^{t}\rangle=\frac{1}{d}\sum_{\ell^{\prime\prime}=0}^{d-1}G_{d}(j-k,\ell-\ell^{\prime\prime})\,\omega^{-\ell^{\prime}\ell^{\prime\prime}+\left(t-1\right)\ell^{\prime\prime}{}^{2}}\,.$
(54)

We can simplify this expression by substituting (52) into it, to find

$\displaystyle V_{\ell\ell^{\prime}}$
$\displaystyle=\frac{1}{d}\left(\frac{j-k}{d}\right)\varepsilon_{d}\,\sum_{\ell^{\prime\prime}=0}^{d-1}\omega^{-\left(\ell-\ell^{\prime\prime}\right)^{2}\chi}\,\omega^{-\ell^{\prime}\ell^{\prime\prime}+\left(t-1\right)\ell^{\prime\prime}{}^{2}}$
(55)
$\displaystyle=\frac{1}{d}\left(\frac{j-k}{d}\right)\varepsilon_{d}\,\omega^{-\ell^{2}\chi}\sum_{\ell^{\prime\prime}=0}^{d-1}\omega^{\left(t-1-\chi\right)\ell^{\prime\prime}{}^{2}+\left(2\ell\chi-\ell^{\prime}\right)\ell^{\prime\prime}}\,.$

Letting $t=1+\chi$, we obtain sums over all $d$-th roots of one which vanish
unless the exponents of $\omega$ vanish,

$\sum_{\ell^{\prime\prime}=0}^{d-1}\omega^{\left(2\ell\chi-\ell^{\prime}\right)\ell^{\prime\prime}}=\begin{cases}d&\text{if}\quad\ell^{\prime}=2\ell\chi\mod
d\,,\\\ 0&\text{otherwise}\,.\end{cases}$ (56)

Thus, for this value of $t$, the matrix elements of $V$ take the form

$V_{\ell\ell^{\prime}}=\begin{cases}\left(\frac{j-k}{d}\right)\varepsilon_{d}\,\omega^{-\ell^{2}\chi}&\text{if}\quad\ell^{\prime}=2\ell\chi\mod
d\,,\\\ 0&\text{otherwise}\,,\end{cases}$ (57)

so that the only non-zero elements of the matrix $V$ are those with indices
$\left(\ell,2\ell\chi\mod d\right)$. Each row $\ell$ has exactly one non-zero
entry and the map $\ell\mapsto 2\ell\chi\mod d$ constitutes a permutation of
the elements of $\left\\{0\ldots\,d-1\right\\}$ since $d$ is a prime number
and $2\chi\neq 0\,\mod d$. (Assume this was not the case, i.e. $2\chi x\,\mod
d=2\chi y\,\mod d$ for some $x,y\in\left\\{0\ldots\,d-1\right\\}$, $x\neq y$.
Then $2\chi\left(x-y\right)=nd$ for some integer $n$ which is never the case
whenever $d$ is prime and $\chi\neq 0$ mod $d$.) As a consequence, each column
will also display exactly one non-zero entry.

Therefore, the product $V$ of three Hadamard matrices is equal to a monomial
matrix $M(j,k)$ if $t=1+\chi$, i.e.

$H_{k}^{\dagger}H_{j}=M(j,k)H_{1+\chi}^{\dagger}\,.$ (58)

We complete the proof by showing that the matrix $V=H_{k}^{\dagger}H_{j}H_{t}$
is _not_ monomial for any other value of $t$. For $t\neq 1+\chi$, the sum on
the right-hand side of (55) represents another generalised Gauss sum so that

$V_{\ell\ell^{\prime}}=\frac{1}{\sqrt{d}}\left(\frac{j-k}{d}\right)\varepsilon_{d}\,\omega^{-\ell^{2}\chi}G_{d}\left(t-1-\chi,2\ell\chi-\ell^{\prime}\right)$
(59)

with
$G_{d}\left(t-1-\chi,2\ell\chi-\ell^{\prime}\right)=\sqrt{d}\langle\phi_{2\ell\chi}^{1+\chi}|\phi_{\ell^{\prime}}^{t}\rangle$.
We can now substitute the expression (52) and obtain

$V_{\ell\ell^{\prime}}=\frac{1}{\sqrt{d}}\varepsilon_{d}^{2}\left(\frac{j-k}{d}\right)\left(\frac{t-1-\chi}{d}\right)\omega^{-\ell^{2}\chi}\omega^{-(2\ell\chi-\ell^{\prime})^{2}\widetilde{\chi}}$
(60)

where $\widetilde{\chi}\in\left\\{1\ldots\,d\right\\}$ is an integer
satisfying $4\left(t-1-\chi\right)\widetilde{\chi}=1\mod d$. Hence, the matrix
elements $V_{\ell\ell^{\prime}}$ are all non-zero confirming that the matrix
$V$ is not monomial unless $t=1+\chi$. ∎

An alternative, shorter proof of Lemma 3.1 can be given by representing the
Hadamard matrices $H_{j}$ as $2\times 2$ matrices in
$\text{{SL}}(2,\mathbb{Z}/d\mathbb{Z})$ (cf. [37]).

*

###### Proof.

Construct a matrix $M$ of order $d\times\left(d_{1}+d_{2}\right)$ from any
$\left(d_{1}+d_{2}\right)\leq d$ column vectors—expressed in the computational
basis—from the two MU bases $\mathcal{B}_{j_{1}}$ and $\mathcal{B}_{j_{2}}$.
Then left-multiply $M$ by $H_{j_{1}}^{\dagger}$. Since $\langle
x|H_{j_{1}}^{\dagger}|\phi_{k}^{j_{1}}\rangle=\langle x|k\rangle$, the first
$d_{1}$ columns will be elements of the computational basis, while the
remaining $d_{2}$ columns will be taken from $H_{j_{1}}^{\dagger}H_{j_{2}}$
since $\langle x|H_{j_{1}}^{\dagger}|\phi_{k}^{j_{2}}\rangle=\langle
x|H_{j_{1}}^{\dagger}H_{j_{2}}|k\rangle$. By swapping rows appropriately via a
permutation operator $P$ which does not change linear independence of column
vectors, the top left square can be mapped to the $d_{1}$-dimensional
identity. For example, if we consider $d=5$ and $d_{1}=d_{2}=2$, we obtain a
$5\times 4$ matrix,

$PH_{j_{1}}^{\dagger}M=\left(\begin{array}[]{cc|cc}1&0&\ast&\ast\\\ 0&1&*&*\\\
\hline\cr 0&0&\ast&\ast\\\ 0&0&\ast&\ast\\\ 0&0&*&*\end{array}\right)\,,$ (61)

where the asterisks refer to the elements of $H_{j_{1}}^{\dagger}H_{j_{2}}$.

The $\left(d_{1}+d_{2}\right)\leq d$ vectors are linearly dependent only if
$M$ does not have full rank, i.e. $\text{rank}\left(M\right)<d_{1}+d_{2}$.
Since $PH_{j_{1}}^{\dagger}$ is unitary, it follows that
$\text{rank}\left(PH_{j_{1}}^{\dagger}M\right)<d_{1}+d_{2}$. Given the form of
the matrix (61), the bottom-right part of $PH_{j_{1}}^{\dagger}M$ must contain
a $\left(d_{2}\times d_{2}\right)$ submatrix with vanishing determinant.
However, this is prohibited by Corollary 3.1 which ensures for all prime
numbers $d$ that $H_{j_{1}}^{\dagger}H_{j_{2}}$ has non-vanishing minors if
$j_{1}\neq j_{2}$. Thus, all $(d_{1}+d_{2})$ column vectors of $M$ must be
linearly independent. ∎

*

###### Proof.

By substituting (13) into (46) and taking the logarithm, one obtains
$ax^{2}+bx-n=0\>\text{mod}\,d$ where $a=j_{1}-j_{2}$ and $b=k_{2}-k_{1}$. This
quadratic equation can have no more than two integer solutions. Thus, at most
two components of the states $|\phi_{k_{1}}^{j_{1}}\rangle$ and
$|\phi_{k_{2}}^{j_{2}}\rangle$ can be identical in the computational basis, up
to multiplication by $\omega^{n}$. If $j_{1}=j_{2}$, then $a=0$ and the
equation is linear with a single solution for each value of $n$. ∎

*

###### Proof.

Four scalar products with the state $\psi$ vanish,

$\langle x_{1}|\psi\rangle=\langle
y_{1}|\psi\rangle=\langle\phi_{x_{2}}^{j}|\psi\rangle=\langle\phi_{y_{2}}^{j}|\psi\rangle=0\,,$
(62)

two for each of the bases. Hence, the zero distributions of the states $\psi$
and $H_{j}^{\dagger}\psi$, are given by
$\mathcal{Z}^{0}=\left\\{x_{1},y_{1}\right\\}$ and
$\mathcal{Z}^{j}=\left\\{x_{2},y_{2}\right\\}$ respectively, with four integer
numbers $x_{1},\ldots,y_{2}\in\\{0\ldots 4\\}$. Now suppose that there is a
third MU basis $\mathcal{B}_{j^{\prime}}$, different from both
$\mathcal{B}_{0}$ and $\mathcal{B}_{j}$, in which the state $\psi$ does _not_
have full support. In other words, there is at least one vanishing scalar
product, $\langle\phi_{x_{3}}^{j^{\prime}}|\psi\rangle=0$, say, where
$x_{3}\in\\{0\ldots 4\\}$. Expressing the components of the five vectors
$|x_{1}\rangle$, $|y_{1}\rangle$, $|\phi_{x_{2}}^{j}\rangle$,
$|\phi_{y_{2}}^{j}\rangle$, $|\phi_{x_{3}}^{j^{\prime}}\rangle$ with respect
to the computational basis and arranging them into a $5\times 5$ matrix, we
find, after permuting the rows and rephasing the last three vectors,

$M=\frac{1}{\sqrt{5}}\left(\begin{array}[]{ccccc}\sqrt{5}&0&*&*&*\\\
0&\sqrt{5}&*&*&*\\\ 0&0&1&1&1\\\ 0&0&\omega^{a}&\omega^{c}&\omega^{e}\\\
0&0&\omega^{b}&\omega^{d}&\omega^{f}\end{array}\right)\,,\qquad
a,\ldots,f\in\\{0\ldots 4\\}\,.$ (63)

Being elements of the Hadamard matrices $H_{j}$ and $H_{j^{\prime}}$, the
entries of the last three columns are powers of $\omega$, a fifth root of one.
Corollary 3.1 ensures the linear independence of the first four vectors.

If the determinant of $M$ does not vanish, $\det M\neq 0,$ then the five
column vectors forming it are linearly _independent_ , thus spanning
$\mathcal{H}_{5}$. However, the only state being orthogonal to all of
$\mathcal{H}_{5}$ is $\psi=0$ which does not represent a quantum state. Thus,
for an acceptable state $\psi$ producing the given five vanishing expansion
coefficients, the five vectors involved must be linearly _dependent_ , i.e.
$\det M=0$. Consequently, the determinant of the bottom right $3\times 3$
matrix of $M$ must vanish,

$\Delta\equiv\det\left(\begin{array}[]{ccc}1&1&1\\\
\omega^{a}&\omega^{c}&\omega^{e}\\\
\omega^{b}&\omega^{d}&\omega^{f}\end{array}\right)=\omega^{a+d}+\omega^{e+b}+\omega^{c+f}-\omega^{c+b}-\omega^{e+d}-\omega^{a+f}=0\,.$
(64)

Each of the six terms in this expression is a power of a fifth root $\omega$
of unity, hence non-zero. It is well known that the set
$\left\\{\omega^{n}\,|\,n=0,...,3\right\\}$ is linearly independent over the
rational numbers $\mathbb{Q}$. As a consequence, every non-zero complex number
that is expressible as a linear combination (over $\mathbb{Q}$) of these roots
of unity has a unique expression. Since
$\omega^{4}=-1-\omega-\omega^{2}-\omega^{3}$, it must follow that the only
decomposition of zero over $\mathbb{Q}$ in terms of fifth roots of $1$ is
$0=q\left(1+\omega+\omega^{2}+\omega^{3}+\omega^{4}\right)$, with some
rational number $q\in\mathbb{Q}$. In other words, for the sum to vanish all
five roots must be multiplied to the same rational coefficient.

We distinguish two cases: either $q\neq 0$ or $q=0$. Since (64) involves six
terms with coefficients $\pm 1$, we conclude that the case of $q\neq 0$ cannot
be realised: it is impossible to get all five roots to appear with the same
non-zero coefficient. For example, let $(a+d)=(e+b)\mod 5$, then Eq. (64)
reduces to

$\Delta=2\omega^{a+d}+\omega^{c+f}-\omega^{c+b}-\omega^{e+d}-\omega^{a+f}$
(65)

Since all roots must appear, the exponents in (65) are all different. However,
the coefficients are not equal throughout and the sum cannot vanish. A similar
argument holds for any other equality between exponents.

The case of $q=0$ must therefore apply: the determinant $\Delta$ vanishes if
and only if the six terms in Eq. (64) cancel each other in pairs, i.e. the the
powers of $\omega$ must occur an even number of times, and with an equal
number of positive and negative coefficients. Hence, the first term in (64) is
necessarily paired up with one of the powers with a negative coefficient
leading. Three cases arise which we will consider separately.

$(i)$ For the first and the fourth term to cancel, we must have
$(a+d)=(c+b)\mod 5\,,$ or

$(a-b)=(c-d)\mod 5\,,$ (66)

relating the expansion coefficients of two vectors of the _same_ basis, namely
$|\phi_{x_{2}}^{j}\rangle$ and $|\phi_{y_{2}}^{j}\rangle$. Consequently, the
third and fourth column vectors in the matrix $M$ in (63) have (at least) two
equal entries in identical positions, up to an irrelevant common phase factor.
This would result in a vanishing $2\times 2$ submatrix of $H_{j}$
contradicting Corollary 3.1 (and Lemma 5.2). Thus the determinant $\Delta$
cannot vanish in this case.

$(ii)$ For the first and the fifth term to cancel, we must have
$(a+d)=(e+d)\mod 5\,,$ or

$a=e\,\mod 5\,,$ (67)

relating the expansion coefficients of two vectors of _different_ bases,
namely $|\phi_{x_{2}}^{j}\rangle$ and $|\phi_{x_{3}}^{j^{\prime}}\rangle$.
Corollary 3.1 does not apply to this case. We do know, however, that the
fourth term in the sum (64) must pair up with either the second or the third
term of the sum in (64). In the first case, we find $(c+b)=(e+b)\mod 5\,,$or

$c=e\,\mod 5\,.$ (68)

Given the constraint (67), we we obtain the identity

$a=c\,\mod 5\,,$ (69)

again relating the expansion coefficients of two vectors of the _same_ basis,
namely $|\phi_{x_{2}}^{j}\rangle$ and $|\phi_{y_{2}}^{j}\rangle$. As in the
Case $(i)$, a contradiction to Corollary 3.1 arises.

In the second case, we pair up terms three and four of the sum (64), leading
to the identity $(c+b)=(c+f)\mod 5$, or

$b=f\,\mod 5\,.$ (70)

Together with Eq. (67), it follows that the last three elements of the third
and and fifth columns of $M$ are identical. However, according to Lemma 5.2,
two vectors stemming from two different bases MU to the computational basis
can have at most two identical components.

$(iii)$: Assuming that the first and the sixth term of the sum (64) cancel
again leads to a contradiction along the lines of the argument considered in
Case $(ii).$

Thus, we are forced to conclude that the determinant $\Delta$ cannot not
vanish for any $j^{\prime}\neq 0,j$ and any $x_{3}$, which implies that the
state $\psi$ must have full support. ∎