\cC_6 =& \Mg{\Eins  X  Z, X  Y  Y, X  Z  X, Y  \Eins  Z, Y  X  \Eins, Z  Y  X, Z  Z  Y},& s(\cC_6)= 1,\nonumber\\
\cC_7 =& \Mg{\Eins  Y  Z, X  \Eins  Z, X  Y  \Eins, Y  X  X, Y  Z  Y, Z  X  Y, Z  Z  X},& s(\cC_7)= 1,\nonumber\\
\cC_8 =& \Mg{\Eins  \Eins  X, \Eins  X  \Eins, \Eins  X  X, X  \Eins  \Eins, X  \Eins  X, X  X  \Eins, X  X  X},& s(\cC_8)= 3,\nonumber
\end{align}

where $\Eins$ abbreviates $\Eins_2$. The numbers
of decomposable systems for the classes are given by the separability counts. So the vector $\vec n$ in the case
of this set of MUBs is given by $\vec n_{1} = (3,0,6)^t$.[This set is commonly known as the standard set [40].] Other possible structures are $\vec n_{2} = (2,3,4)^t$,
$\vec n_{3} = (1,6,2)^t$ and $\vec n_{4} = (0,9,0)^t$ [75].To generate these structures, which do not have three totally-decomposable classes, we cannot use the already discussed
Fibonacci-based sets of Section <ref>. Therefore, we have to reduce the number of constraints, which are required
to produce the Fibonacci-based sets, in order to achieve a larger set of possible structures. For Fibonacci-based sets, we find a field structure:

The submatrices $G_j^z$ of the generators $\bar G_j = (G_j^z, \Eins_m)^t$ in standard form with $j \in \MgE{d}$ that are used to generate a complete set of cyclic
Fibonacci-based MUBs, form a representation of the finite field $\F_2^m$.

Considering the standard form (cf. Section <ref>) of the Fibonacci-based sets, we find the $2^m$ generators
$G_j = (F_{j+1}(B) F_{j}(B)^{-1}, \Eins_m)^t$. As $B$ has an irreducible characteristic polynomial of degree $m$
that generates a polynomial ring and $2^m$ different elements $F_{j+1}(B) F_{j}(B)^{-1}$ exist, the set of those elements
is a representation of a polynomial ring, in particular of the finite field $\F_2^m$.

To create cyclic sets of MUBs it is more comfortable to use homogeneous sets, as discussed in Section <ref>,
since their first basis is used to create the standard basis (cf. Section <ref>). In this case the generator
of the first group is given by $G_0 = (\Eins_m, 0_m)^t$. To diminish the first value of the vector $\vec n$ to two, by keeping
the homogeneity property, it is obvious that we loose the field property of Lemma <ref>. What we
get is an additive group of the values $G_j^z$ without the unity element $\Eins_m$ of the multiplication, thus, a class
of all Pauli-$Y$ operators as given by Equation (<ref>) is not included.
In this case, Condition (III) of Section <ref> is fulfilled if the expression $G_l^z + G_k^z$ is invertible
for  with $k \neq l$, but this element is again an element of the group. We can thus create this group
of matrices by a generating set, say w. l o. g. $H_k \in \GL{m}{\F_2} $ with $k \in \MgE{m}$ and

\begin{align}\label{eqn:standfor:group}
G_j^z = \sum_{k=1}^m h_k H_k,\quad \mathrm{for}\quad (h_1,\ldots,h_m) \in \F_2^m,
\end{align}

where all $G_j^z$ with $j\neq 0$ have to be invertible. Equation (<ref>) is equivalent to the
of Bandyopadhyay  <cit.>. Details will be discussed in Section <ref>.To obtain $n_1=1$, we need to exclude also the element $0_m$ which forms the class of Pauli-$X$ operators from the set of matrices
$G_j^z$ with $j \in \MgE{d}$. The highest set structure which fits is then a semigroup, which does not allow a generation as
in Equation (<ref>).Finally, we have to give up the homogeneity property to set $n_1=0$. To be able to prevent all fully-decomposable classes, we have
to change the generator $G_0$. In Section <ref> we discussed why $\bar G_0=(\Eins_m, G_0^x)^t$ is a good choice.
It is clear, that Condition (III) of Section <ref> has to be adapted minimally. Details of the inhomogeneous sets
will be discussed in Section <ref>.

§ HOMOGENEOUS SETS

The second class of cyclic MUBs we create in this work includes the class of Fibonacci-based MUBs
formally, but does not share completely their nice way of construction. This generalization is based on the
Conditions (I)–(III) of Section <ref>. As seen in Section <ref>, the entanglement properties of the bases within
a certain set of MUBs are different for this class of homogeneous sets. Experimentally, complete sets with
a reduced number of bases that measure properties of a fully entangled system, are to be preferred.As already stated in Section <ref>, the homogeneous sets can be build either from
generators with a field structure, as done for the Fibonacci-based MUBs, with an additive group structure
or an additive semigroup structure. The number of bases with a fully-decomposable structure is three, two
and one, respectively, in these cases. As the construction of Fibonacci-based MUBs is already solved,
we give a generalized solution in Section <ref>, which generates also
group-based sets. In Section <ref>, a first notion on the realization
of semigroup-based sets is presented.

§.§ Group-based sets

Considering the properties of the stabilizer matrix to generate a complete set of cyclic MUBs,
we use Conditions (1)–(3) of Section <ref>. We propose a generalized form
of the stabilizer matrix as in Section <ref> in order to implement an additive group structure of the matrices $G_j^z$ in the
standard form, that has solutions which avoid the field structure (cf. Equation (<ref>)). The
stabilizer matrix we propose is given by

\begin{align}\label{eqn:homosets:group:C}
C = \begin{pmatrix}B & R\\ R^{-1} & 0_m\end{pmatrix},
\end{align}

where the reduced stabilizer matrix $B \in M_m(\F_2)$ appears, but also an invertible matrix
$R \in \mathrm{GL}_m(\F_2)$. The powers of the stabilizer matrix,
as given by Equation (<ref>), are

\begin{align}
C^n =
\begin{pmatrix}
F_{n+1}(B) & F_n(B) R\\
R^{-1} F_n(B) & R^{-1} F_{n-1}(B) R
\end{pmatrix},
\end{align}

with $F_n(x)$ being the Fibonacci polynomial with index $n \in \N$, as defined in Equation (<ref>).
In standard formStandard form the generators $G_j$ of the classes $\cC_j$ (cf. Equation (<ref>)) look like

\begin{align}\label{eqn:homosets:group:standfor}
\bar G_0 = \begin{pmatrix}\Eins_m\\0_m\end{pmatrix}\quad\mathrm{and}\quad \bar G_j= \begin{pmatrix} F_{j+1}(B) F_j(B)^{-1} R\\\Eins_m\end{pmatrix},
\end{align}

thus, the field elements $G_j^z$ of Equation (<ref>) are multiplied by the
invertible matrix $R$. The new elements $G_j^z$ of Equation (<ref>) form an additive group which may be written by
a generating set as stated by Equation (<ref>).
We can define conditions which are similar to Conditions (i) and (ii') of Section <ref>.
Since those conditions emerge from Conditions (1)–(3) of Section <ref>, we can start our discussion there. As seen by
Equation (<ref>), the generators have the required form, thus, Condition (1) is fulfilled by construction.
For Condition (2), all elements $G_j^z$ with $j \in \MgE{d}$ and $d=2^m$ have to be symmetric. Those elements are given by the polynomials
$p_n(B)$, defined as $p_n(B) = F_{n+1}(B) F_n(B)^{-1}$ with $n \in \MgE{d}$, multiplied by the matrix $R$. By the following lemma the
number of matrices to be tested on their symmetry can be reduced dramatically to two.

For invertible matrices $A, B \in \GL{m}{K}$, all polynomials $p(A) \in K[x]$ multiplied with $B$ from the right are symmetric,
if and only if $B$ and $AB$ are symmetric.

Let $B$ and $AB$ be symmetric matrices. Then for any matrix $A^k B$ with $k \in \N$ there holds

\begin{align}
(A^k B)^t = B^t A^t (A^{k-1})^t = A B^t A^t (A^{k-2})^t = \ldots = A^k B.
\end{align}

Any polynomial in $A$ multiplied with $B$ is then a sum of symmetric matrices. But sums of symmetric matrices are again symmetric.
The converse is obvious, if we consider the cases $k=0$ and $k=1$, thus $\Eins_m B$ and $AB$.

Using Lemma <ref>, Condition (2) of Section <ref> is fulfilled, if and only if $R$ and $BR$ are symmetric.
Condition (3) is also correct, since the difference of two group elements leads again to a group element. If all three conditions
are fulfilled, the stabilizer matrix $C$ has to be symplectic, but as a precaution we can check this easily by using Corollary
<ref> of Appendix <ref>. The product $R (R^{-1})^t$ equals $\Eins_m$ as $R$ is
a symmetric matrix. $B^t R^{-1}$ is symmetric, since its transpose $(R^{-1})^t B$ is the product of a polynomial in $R$
(cf. Proposition <ref>) with the symmetric matrix $B$, therefore, we can apply Lemma <ref>.
To get a complete set of MUBs, the similarity of Equation (<ref>) with Equation (<ref>) indicates,
that the characteristic polynomial of $B$ has to have a Fibonacci index of $d+1$. Finally, we find the following conditions:

* $R$ and $B  R$ are symmetric.

* The characteristic polynomial of $B$ has Fibonacci index $d+1$.

The polynomials $p_n(B)$ have field structure, but multiplied by the matrix $R$ this structure disappears. Only an additive
group structure is left, as wanted. For $R = \Eins_m$ or more generally for $R = p_n(B) \neq 0_m$ with $n \in \MgE{d}$, we find
the Fibonacci-based sets. Thus, for appropriate values of $R \neq p_n(B)$ we find complete sets of cyclic MUBs that have exactly two bases with
a totally-decomposable structure, namely $\cC_0$ and $\cC_d$.According to Equation (<ref>), we find $126$ different pairs $(B,R)$ for a system of three qubits that have
a decomposition structure of the bases as given in [75], namely $\vec n = (2,3,4)^t$. One of the solutions is
given by

\begin{align}\label{eqn:homoset:group:C234}
B_{(2,3,4)} =
\begin{pmatrix}
0 & 1 & 1\\
0 & 0 & 1\\
1 & 0 & 0
\end{pmatrix}\quad\mathrm{and}\quad
R_{(2,3,4)} =
\begin{pmatrix}
0 & 0 & 1\\
0 & 1 & 0\\
1 & 0 & 0
\end{pmatrix}.
\end{align}

It is expected that most of the $126$ solutions can be transformed into each other with transformations that originate from simple
symmetry considerations. One of those transformations corresponds only to sets which are not related to the Fibonacci-based sets and was
indirectly discussed above. If we replace the matrix $R$ in the construction of Equation (<ref>) by the product
of a polynomial $p_l$ in $B$, with the old matrix $R$, we get

\begin{align}\label{eqn:homosets:group:Cfactor}
C = \begin{pmatrix}B & p_l(B) R\\ R^{-1} p_l(B)^{-1}  & 0_m\end{pmatrix},
\end{align}

with generators in standard form as

\begin{align}\label{eqn:homosets:group:standforfactor}
\bar G_0 = \begin{pmatrix}\Eins_m\\0_m\end{pmatrix}\quad\mathrm{and}\quad \bar G_j= \begin{pmatrix} F_{j+1}(B) F_j(B)^{-1} p_l(B) R\\\Eins_m\end{pmatrix}.
\end{align}

Since all polynomials in $B$ with maximal degree $m-1$ appear in the groups $\bar G_j$, the polynomial $p_l(B)$ with $l \in \MgE{d}$ permutes
the original generators $\bar G_j$. Since there are only $2^m-1$ non-zero polynomials with degree smaller than $m$, we found a symmetry to reduce
the solutions by a factor of $2^m-1$. In the case discussed above, we can divide $126$ by $2^3-1$ and get $18$. We would get cyclic MUBs with the
same entanglement properties by relabeling the different qubits, which lead to $m!$ permutation operators, in the case of three qubits to six
possible permutations. But it is not clear if this symmetry is uncorrelated with the symmetry that appears from multiplying the matrix $R$ with
a polynomial in $B$. A complete explanation of the appearance of $126$ solutions may be an interesting issue but is above the scope of this work.We list seven systems with a different decomposition structure for four-qubit systems in Appendix <ref>. Some of the sets
do not appear in the list given in [75]. This is in accordance to a statement in <cit.>, which claims
an incompleteness of the list of $16$ MUBs in the former article; the complete classification lists 34 sets [40].

§.§ Semigroup-based sets

In order to obtain complete sets of cyclic MUBs which contain only one class of operators that is fully separable into qubit systems, we need to find a
form of the stabilizer matrix $C$ which is even more general than the form of Section <ref> and is given by Equation
(<ref>). A hypothetical idea would be the following: To construct the Fibonacci sets of Section <ref>, the
stabilizer matrix $C \in M_{2m}(\F_2)$ was completely determined by the reduced stabilizer matrix $B \in M_m(\F_2)$, for the group-based sets of
Section <ref>, a second matrix $R \in \GL{m}{\F_2}$ became relevant. To construct semigroup-based sets we can imagine that
a third matrix will be relevant. Nevertheless, we have not been able to find an appropriate generalization of Equation (<ref>)
so far to reach this goal. Conversely, from a top-down point of view, we are able to construct at least some solutions within an obtainable computation
time: If we assume that the upper left submatrix of $C$ remains invertible, we find by the properties which are given by Corollary <ref>,
that for any symplectic matrix $C = \begin{pmatrix}s & t\\ u  & v\end{pmatrix}$, with $s,t,u,v \in M_m(K)$ and $s$ invertible, there holds

\begin{align}
v = (s^t)^{-1} (1+u^t t).
\end{align}

Thus, we should be able to construct the semigroup-based sets with the three matrices $s,t,u \in M_m(\F_2)$. A similar observation is possible by
assuming that $u$ is invertible, but does not lead to a logical generalization of the group-based sets, as we are not able to require a certain
value for the characteristic polynomial of $s$. A cyclic version of the corresponding three-qubit system in [75] is generated by

\begin{align}\label{eqn:homoset:semigroup:C162}
C_{(1,6,2)} =
\begin{pmatrix}
0 & 1 & 1 & 0 & 1 & 0\\
0 & 1 & 1 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 1\\
0 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}.
\end{align}

However, as a suitable form is not found yet, computational results based on these approaches and
Conditions (1)–(3) of Section <ref> are given in Appendix <ref>.

§ INHOMOGENEOUS SETS

The third and last class of cyclic MUBs that are discussed in this work does not contain any class
of operators that is fully separable into qubit systems in its decomposition structure which was introduced
in Section <ref>. Accordingly, these sets need to have a more general standard form
as given in Definition <ref>, thus, the generator $\bar G_0$ does not equal
$(\Eins_m, 0_m)^t$ as for the Fibonacci-based sets and the homogeneous sets in general. The approach we
choose in order to create an inhomogeneous set is the following: At first, a symplectic matrix $C_0 \in M_{2m}(\F_2)$ is
taken which produces a more general generator $\bar G_0$ from the matrix $(\Eins_m, 0_m)^t$. Secondly,
the ordinary symplectic stabilizer matrix $C$ is taken.If we take the generator $\bar G^{(h)}_0(\Eins_m, 0_m)^t$ of the homogeneous
sets, we can produce any generator $\bar G_0$ as

\begin{align}
\bar G_0 = C_0 \bar G^{(h)}_0 = \begin{pmatrix}\Eins_m & t\\ G_0^x & v\end{pmatrix} \begin{pmatrix} \Eins_m \\0_m \end{pmatrix} = \begin{pmatrix} \Eins_m \\G_0^x \end{pmatrix},
\end{align}

with $t,v \in M_m(\F_2)$, where $t$ and $v$ can be chosen according to fulfill the properties derived by
Corollary <ref> to let $C_0$ be symplectic. For the first of these
three properties, $G_0^x$ has to be symmetric, which has also be true in order to create a class of
commuting elements in $\cC_0$, corresponding to the derived Property (2) of Section <ref>.The following discussion gives a first idea of the construction of inhomogeneous sets. The results
can be seen as a proof-of-principle that legitimates the approach. In order to generate a class which
is not fully decomposable, we entangle two qubit systems with indices $i, j \in \Mg{1,m}, i\neq j$ by
setting $(G_0^x)_{i,j}=(G_0^x)_{j,i} = 1$, which has the expected effect, regarding the class generation
which is introduced by Equation (<ref>). Following then the ideas of Section <ref>,
we found some of the solutions for four-qubit systems and list them in Appendix <ref>.
A cyclic generator for the three-qubit system that equals the system which is generated in [75] is given by

\begin{align}\label{eqn:inhomoset:C090}
C_{(0,9,0)} =
\begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 1\\
1 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0
\end{pmatrix},
\end{align}

where the corresponding generator $G_0$ equals

\begin{align}\label{eqn:inhomoset:G090}
(G_0^x)_{(0,9,0)} =
\begin{pmatrix}
0 & 1 & 0\\
1 & 0 & 0\\
0 & 0 & 0
\end{pmatrix},
\end{align}

with $G_0=(\Eins_m, G_0^x)^t$.

§ UNITARY OPERATOR

So far, we have discussed different sets of cyclic MUBs in the view of a partition of the set
of Pauli operators, as introduced in Section <ref>. The corresponding stabilizer matrices
were introduced in Sections <ref>, <ref>, and <ref> and
serve as generators of the set of classes which partition the set of Pauli operators. But, for measuring
quantum states, we need to transform those matrices into unitary operators, in the fashion of Section
<ref>. This section starts by deriving that transformation and leads to a comfortable form
of the unitary operators which result from Fibonacci-based sets (Section <ref>).
Section <ref> recalls
the iterative construction of the Fermat sets of Section <ref> in order to derive again
an iterative construction of these MUBs, but this time on the level of unitary operators as published
in [84]. The section closes by discussing shortly the generation of the unitary operator in cases of a
more general stabilizer matrix (Section <ref>).For the derivation of the unitary operator we use the theory of the stabilizer formalismStabilizer formalism[
The theory of the stabilizer formalism was developed by Gottesman [34]. See also his Ph. D. thesis [35].], as could
have already been figured out by the definition of the stabilizer matrix $C \in M_{2m}(\F_p)$.
Within this theory, substitutes of the usual Pauli operators are
defined, namely the logical Pauli operatorsLogical Pauli operator. The usual Pauli operators
$\ZX(\vec a)$ were defined in Equation (<ref>). With $\vec z_k \in \F_p^{2m}$ being a vector
that has a one at position $k$ and zeros else and $\vec x_k \in \F_p^{2m}$ a vector with a one at position
$m+k$ and zeros else, we can define the physical operatorsPhysical operator, namely a unitary representation of $\F_p^{2m}$,
as $Z_k = \ZX(\vec z_k)$ and $X_k = \ZX(\vec x_k)$; using a stabilizer matrix $A$ results in the
logical operatorsLogical operator $\bar Z_k = \ZX(A \vec z_k)$ and $\bar X_k = \ZX(A \vec x_k)$ with $k \in \MgE{m}, m \in \N^*$
and $p$ prime. The physical  operators produce a local phase factor, whereas physical  operators induce
bit (or dit[A dit denotes a variable defined over $\Z_d$, generalizing a bit.]) flips. Therefore, the logical ground state $\ket{0}_\mathrm{L}$ is naturally defined as the joint
eigenstate of all logical  operators with eigenvalue $+1$. The other logical states can be derived by
applying bit (or dit) flips as

\begin{align}\label{eqn:unitop:jL}
\ket{j}_\mathrm{L} = \bar X_1^{j_1} \cdots \bar X_m^{j_m} \ket{0}_\mathrm{L},
\end{align}

with $\Mg{j_1, \ldots, j_m}$ being the bit (or dit) decomposition of $j \in \F_p^m$.
At first, we focus on the construction of the unitary operator that generates a Fibonacci-based
set of MUBs.

§.§ Fibonacci-based sets
In order to facilitate the following consideration, we use the inverse of the stabilizer matrix for the
Fibonacci-based sets (cf. Equation (<ref>)), which, in the case of qubits, is obviously given by

\begin{align}\label{eqn:unitop:C-1}
C^{-1} = \begin{pmatrix}0_m& \Eins_m\\ \Eins_m & B\end{pmatrix}.
\end{align}

This leads to the logical operators

\begin{align}
\bar Z_k = \ZX(C^{-1} \vec z_k)\quad \mathrm{and} \quad \bar X_k = \ZX(C^{-1} \vec x_k),
\end{align}

with $\bar Z_k = X_k$ for $k \in \MgE{m}$. Thus, the logical ground state is (up to a global phase) given by

\begin{align}\label{eqn:unitop:0L}
\ket{0}_\mathrm{L} = 2^{-m/2} \sum_{j \in \F_2^m} \ket{j}.
\end{align}

For the construction of a complete set of MUBs for a dimension of the Hilbert space which is a power of two,
the set of Pauli operators is partitioned into $d+1=2^m+1$ disjoint classes
of commuting operators (cf. Equation (<ref>)).
The common eigenbases of those classes are mutually unbiased, as shown by Bandyopadhyay  [7]. In
order to get a cyclic set, the transformation that brings a class $\cC_l$ with $l \in \MgN{d}$ of operators
to the class $\cC_{(l + 1)\;\mathrm{mod}\; (d+1)}$, has to be of multiplicative order $d+1$. By construction,
the class $\cC_0$ of the Fibonacci-based sets appears as

\begin{align}
\cC_0 = \Mg{ \ZX \begin{pmatrix} \vec a_z\\ \vec 0\end{pmatrix} \middle\vert \vec a_z \in \F_2^m \backslash \Mg{0}}.
\end{align}

For a complete set of cyclic MUBs there exists a unitary operator $U \in M_d(\C)$, such that
$U \cC_l U^\dagger = \cC_{(l+1) \;\mathrm{mod}\; (d+1)}$ and $U^{d+1} = \Eins_d$. With $\Eins_d$ being the common
eigenbasis of the operators of the class $\cC_0$, the columns of $U^l$ form the vectors of the eigenbases of $\cC_l$. Since $U$ maps
Pauli operators onto Pauli operators, it is called a Clifford unitary operatorClifford unitary operator.
Properties of these operators and their relation to symplectic matrices is given in Appendix <ref>.
As mentioned above, we will calculate the inverse of the unitary operator, thus $U^\dagger$. By definition,
the operator $U^\dagger$ transforms a physical state into the corresponding logical state, namely
$U^\dagger \ket{j} = \ket{j}_\mathrm{L}$ which yields with Equation (<ref>)

\begin{align}
U^\dagger \ket{j} = \EZ^{-\iE \Psi} \prod_{k=1}^m \ZX(C^{-1} \vec x_k)^{j_k} \ket{0}_\mathrm{L},
\end{align}

and with Equation (<ref>) finally

\begin{align}\label{eqn:unitop:Udaggerstart}
U^\dagger = 2^{-m/2} \EZ^{-\iE \Psi} \sum_{i,j\in \F_2^m}\prod_{k=1}^m \ZX(C^{-1} \vec x_k)^{j_k} \ketbra{i}{j}.
\end{align}

The global phase factor $\EZ^{-\iE \Psi}$ with $\Psi \in [0,2\pi)$ is fixed by assuming that $(U^\dagger)^{d+1} = \Eins_d$,
but the phases of the elements of the set of Pauli operators within a class $\cC_j$ are arbitrary. Thus, this global phase
factor does not follow from the stabilizer formalism.
To calculate the expression of Equation (<ref>), we plug in $C^{-1}$ in the form of Equation (<ref>)
with $B=(b_{ij})$. The general $k$-th factor looks like

\begin{align}
\ZX(C^{-1} \vec x_k) = \left( \bigotimes_{t=1}^{k-1} X^{b_{tk}} \right) \otimes (-\iE)^{b_{kk}} Z X^{b_{kk}} \otimes \left( \bigotimes_{t=k+1}^{m} X^{b_{tk}} \right).
\end{align}

Applying the product, we find for a single tensor factor of the qubit at position $k$ the term

\begin{align}
(-\iE)^{b_{kk} j_k} X^{b_{1k} j_1 + \ldots + b_{k-1,k} j_{k-1}} \cdot Z^{j_k} \cdot X^{X_{kk} j_k + \ldots + b_{mk} j_m},
\end{align}

that can, by shifting the operator $Z$ to the left, be rewritten as

\begin{align}
\iE^{b_{kk} j_k} (-1)^{b_{1k} j_1 j_k + \ldots + b_{kk} j_{k} j_k} Z^{j_k} \cdot X^{X_{1k} j_k + \ldots + b_{mk} j_m}.
\end{align}

To be able to write the tensor product in a short form, we define the abbreviations

\begin{align}\label{eqn:unitop:pj*X_j}
p^*_j :=& \iE^{\sum_{k=1}^m b_{kk} j_k} (-1)^{\sum_{k=1}^m b_{1k} j_1 j_k + \ldots + b_{kk} j_k j_k},\\
\tilde X_j :=& \bigotimes_{k=1}^{m} X^{b_{1k} j_1 + \ldots + b_{mk} j_m},
\end{align}

which lead to

\begin{align}
U^\dagger = 2^{-m/2} \EZ^{-\iE \Psi} \sum_{i,j \in \F_2^m} p^*_j \cdot \left( \bigotimes_{k=1}^m Z^{j_k} \right) \cdot \tilde X_j \ketbra{i}{j}.
\end{align}

Only the factor $\tilde X_j$ acts on $\sum_i \ket{i}$, but it has no argument in $i$ and keeps the sum invariant.
Therefore–summarized over $i$–it equals the unity operator and vanishes. The tensor product $\bigotimes_{k=1}^m Z^{j_k}$ can be
identified with $(-1)^{i\cdot j}$ that equals Sylvester's Hadamard matrix (cf. Equation <ref>). Thus we end up with the short form of $U^\dagger$

\begin{align}
U^{\dagger} = \EZ^{-\iE \Psi} H^{\otimes m} \cdot P^*,
\end{align}

the $m$-folded tensor product of the normalized Hadamard matrixHadamard matrix (cf. Equation (<ref>)) which is defined as

\begin{align}
\end{align}

and the diagonal phase systemPhase system matrix which is given by $P^*=\mathrm{diag}( (p^*_j)_{j \in \F_2^m} )$.
With $B$ being symmetric and the quadratic form

\begin{align}
\bra{j} B \ket{j} = \sum_{k,l=1}^m b_{kl} j_k j_l,
\end{align}

where $\bra{j} B \ket{j} \in \Z_4$ holds, as it is only taken as the power of a root of order four, we finally find

\begin{align}\label{eqn:unitop:pj*}
p^*_j = \iE^{\bra{j} B \ket{j}} (-1)^{\sum_{k=1}^m b_{kk} j_k}.
\end{align}

For the sake of completeness, the original unitary operator $U$ is accordingly given by

\begin{align}\label{eqn:unitop:U}
U = \EZ^{\iE \Psi} P \cdot H^{\otimes m},
\end{align}

with $P=\mathrm{diag}( (p_j)_{j \in \F_2^m} )$ and $p_j = (-\iE)^{\bra{j} B \ket{j}} (-1)^{\sum_{k=1}^m b_{kk} j_k}$.[
The additional minus sign comparing to the results of [53, 85] is due to the fact that we to construct $U$ here
and not $U^{\dagger}$, which does not matter in principle.] The
consideration of the unitary operators $U$ for the derived stabilizer matrices that follow from the matrices $A$ in Appendix
<ref> leads to an unproven conjecture.

[Spectrum of generators of MUBs]

The spectrum of a unitary operator $U$ that generates a complete set of MUBs is non-degenerate; it consists of all roots of
unity of order $d+1$ with a single exception.

It is clear, that the eigenvalues of $U$ have to be roots of unity of order $d+1$ in order to fulfill $U^{d+1}=\Eins_d$. But
$U$ is a $d \times d$ matrix, thus if it is non-degenerate, it has $d$ different eigenvalues. Multiplying a valid $U$ by
any root of unity of order $d+1$ will result again in a valid $U$. We are free to exclude the trivial root $1$ from the spectrum which results
in a spectrum that is symmetric to the real axis. In this case, the trace of $U$ is given by $\tr U = -1$. This way, we can
calculate the global phase $\EZ^{\iE \Psi}$ of $U$ by inserting Equation (<ref>) as

\begin{align}
\EZ^{\iE \Psi} = - \tr ( P^* H^{\otimes m}).
\end{align}

The consideration of derived unitary operators that generate a complete set of cyclic MUBs, where the eigenvalue $-1$ is
excluded from the spectrum, results again in a conjecture.

[Global phase of generators of MUBs]

The global phase of the generator $U$ in the form of Equation (<ref>) of a complete set of cyclic
MUBs, where the eigenvalue $+1$ is chosen to be excluded from the spectrum of $U$, provided Conjecture <ref> is true,

\begin{align}
\EZ^{\iE \Psi} =
\begin{cases}
\frac{-1 - \iE}{\sqrt{2}},&\mathrm{for}\;m\;\mathrm{odd},\\
\end{cases}
\end{align}

It is surprising that the global phase $\EZ^{\iE \Psi}$ seems to depend not on the stabilizer matrix $C$ at all, but only on the number
of qubits, thus, on the dimension $d=2^m$. Since by construction of the phase factors $p_j$ (cf. Equation (<ref>)),
the product $P \cdot H^{\otimes m}$ leads to a matrix with entries that are roots of unity of order four (and a global real normalization
factor), for even $m$ the unitary matrix $U$ has only roots of unity of order four as entries, whereas for odd $m$ it has only entries
that are principal roots of order eight (so not of order four). The complex conjugation of the phase factor in relation to the results
of [53] comes from the fact that here are operators $\ZX$ used, in [53] operators $X\!Z$, but $C$ looks the same.
As an advantage, the approach used here results in a symmetric arrangement of the classes $\cC_j$, for example $\cC_0$ consists only
of Pauli-$Z$ operators and $\cC_d$ of Pauli-$X$ operators.

§.§ Fermat sets
Fermat sets

In Section <ref> it was shown that for dimensions $d=2^{2^k}$ with $k \in \N$, a complete set of cyclic MUBs
can be build recursively, thus, using the complete set of cyclic MUBs from the next smaller dimension. This procedure in terms of
the stabilizer matrix $C$ was shown in Equation (<ref>). Considering the unitary matrix $U$ which results from
$C$ for Fibonacci-based sets as given by Equation (<ref>), we find an analogous recursive construction, but this
time in terms of $U$. And, comparably to the definition of $C_{2^k}$ of Equation (<ref>), we will refer to the
unitary operator $U$ of dimension $2^m$ with $m=2^k$ in the following as $U_{2^k}$.To simplify matters, we define the matrix $V$ by

\begin{align}
V = P \cdot \bar H^{\otimes m},
\end{align}

which has, compared to the unitary operator $U$ of Equation (<ref>), a factor of one for the global phase and with
the Hadamard matrixHadamard matrix as given in Equation <ref>, namely

\begin{align}
\bar H = \begin{pmatrix}
1 & 1\\ 1 & -1
\end{pmatrix},
\end{align}

no normalization factor. Thus, $V$ is not a unitary matrix, but $U$ can be derived from $V$ simply as $U = V / (-\tr V)$. To calculate
a matrix $V_m$ with a $B_m$ as discussed in Section <ref>, we have

\begin{align}\label{eqn:unitop:Vm}
V_{m} = \mathrm{diag}(((-\iE)^{\bra{i} B_m \ket{i}} (-1)^{\sum_{k=1}^m b_{kk} i_k})_{i \in \F_2^m}) \cdot \bar H^{\otimes m},
\end{align}

using Equation (<ref>). By Equation (<ref>), the only value on the diagonal of $B_{2^k}$ that does not vanish,
is $b_{11}$. We can therefore abbreviate Equation (<ref>) as

\begin{align}
V_{m} = \mathrm{diag}(((-\iE)^{\bra{i} B_{m} \ket{i}} (-1)^{i_1})_{i \in \F_2^m}) \cdot \bar H^{\otimes m}.
\end{align}

The same construction holds for $V_{2m}$; we may consider the new vector$i' = (i'_1, \ldots i'_{2m})^t \in \F_2^{2m}$ as
$i' = (i,j)^t = (i_1, \ldots, i_m, j_1, \ldots, j_m)^t \in \F_2^{2m}$, which leads to

\begin{align}\label{eqn:unitop:V2m}
V_{2m} = \mathrm{diag}(((-\iE)^{\bra{i,j} B_{2m} \ket{i,j}} (-1)^{i_1})_{i,j \in \F_2^m}) \cdot \bar H^{\otimes 2 m}.
\end{align}

The matrix element $\bra{i,j} B_{2m} \ket{i,j}$ with $B_{2m} = \begin{pmatrix} B_m & \Eins_m\\ \Eins_m & 0_m\end{pmatrix}$
equals $\bra{i} B_m \ket{i} + 2 ( i \cdot j )$,[It has to be taken care, that $2 ( i \cdot j ) \in \Z_4$
holds and does therefore not vanish, as it is part of the exponent of $-\iE$ in Equation (<ref>).] thus, we find for Equation (<ref>):

\begin{align}\label{eqn:unitop:V2mH}
V_{2m} = \mathrm{diag}(((-\iE)^{\bra{i} B_m \ket{i}} (-1)^{i_1} (-1)^{i\cdot j})_{i,j \in \F_2^m}) \cdot \bar H^{\otimes 2 m}.
\end{align}

The factor $(-1)^{i\cdot j}$ defines the $2^m \times 2^m$ dimensional Hadamard matrix $\bar H^{\otimes m}$, the same, that is used to
describe $V_m$. By definition, $i$ represents the lower bit half and $j$ the higher bit half of $i'$ as $i'=(i,j)^t$. We identify $i$ as the row index
and $j$ as the column index of $H^{\otimes m}$, the factors, namely $(-\iE)^{\bra{i} B_m \ket{i}} (-1)^{i_1}$ are invariant of $j$,
thus repeat for each $j$. The phase vector of $V_{2m}$ arises, by calculating $V_m$ and concatenating its column vectors such that

\begin{align}
\begin{pmatrix}p_1\\p_2\\\hdots\\ p_{2^{2m}}\end{pmatrix} = \begin{pmatrix}(\vec v_1)_m\\ (\vec v_2)_m\\ \hdots \\ ( \vec v_{2^m})_m\end{pmatrix},
\end{align}

where $(\vec v_k)_m$ is the $k$-th column vector of $V_m$. We will refer to the mapping of $V_m$ to the phase vector $P_{2m}$ of $V_{2m}$ as the
chop mapChop map $\cM$, i. e. $\cM(V_m) = P_{2m}$. This defines the recursion relation

\begin{align}\label{eqn:unitop:recursion}
V_{2m} = \mathrm{diag}( \cM( V_m ) )   \cdot \bar H^{\otimes 2 m}.
\end{align}

For $k=0$, thus $m=2^k=1$, we have with $B_1=(1)$:

\begin{align}
V_1 =&\;\mathrm{diag} ( (-\iE)^{0\cdot 1\cdot 0} (-1)^0, (-\iE)^{1\cdot 1\cdot 1} (-1)^1)  \cdot \begin{pmatrix}1&1\\1&-1\end{pmatrix}\\
=& \begin{pmatrix}1&1\\\iE&-\iE\end{pmatrix}\label{eqn:unitop:V1}.
\end{align}

This implies with $\cM(V_1) = ( 1, \iE, 1, -\iE)^t$:

\begin{align}
V_2 = \begin{pmatrix} 1 & 1& 1& 1\\ \iE & -\iE&\iE&-\iE\\1&1&-1&-1\\-\iE&\iE&\iE&-\iE\end{pmatrix},
\end{align}

and can be continued at least to $V_{2048}$ as checked in Appendix <ref>, and if Wiedemann's conjecture is true,
for all $V_{2^k}$ with $k \in \N$.To calculate the unitary operator $U_m$ as $U_m = V_m / (-\tr V_m)$, we need to analyze the matrix $V_m$
in detail. If $i\in \F_2$ represents the rows and $j \in \F_2$ the columns of $V_1$, we find with Equation (<ref>),

\begin{align}
(V_1)_{i,j} =
\begin{cases}
1 \cdot (-1)^{i\cdot j},&\mathrm{for}\; i\equiv 0\quad \mathrm{mod}\quad 2,\\
\,\iE \cdot (-1)^{i\cdot j},&\mathrm{for}\; i\equiv 1\quad \mathrm{mod}\quad 2.
\end{cases}
\end{align}

Taking Equation (<ref>) into account, $V_2$ reads as

\begin{align}
(V_2)_{i,j} =
\begin{cases}
1 \cdot (-1)^{i_1\cdot i_2 + i\cdot j},&\mathrm{for}\; i\equiv 0\quad \mathrm{mod}\quad 2,\\
\,\iE \cdot (-1)^{i_1\cdot i_2 + i\cdot j},&\mathrm{for}\; i\equiv 1\quad \mathrm{mod}\quad 2,
\end{cases}
\end{align}

with $i = \Mg{i_1, \ldots, i_m}$ in general. As seen above, the lengths of the vectors $i$ and
$j$ are one for $V_1$. For $V_2$ the vectors are two bit long, for $V_4$ four bit and so forth.
Using Equation (<ref>) in order to recognize Hadamard matrices in the construction of
$V_m$ recursively, we find

\begin{align}\label{eqn:unitop:Vmij}
(V_m)_{i,j} =
\begin{cases}
1 \cdot (-1)^{x},&\mathrm{for}\; i\equiv 0\quad \mathrm{mod}\quad 2,\\
\,\iE \cdot (-1)^{x},&\mathrm{for}\; i\equiv 1\quad \mathrm{mod}\quad 2,
\end{cases}
\end{align}

\begin{align}
x= i_1\cdot i_2 + (i_1,i_2)\cdot (i_3,i_4)^t + \ldots + (i_1,\ldots,i_{m/2})\cdot (i_{m/2+1},\ldots,i_{m})^t + i\cdot j.
\end{align}

The trace of $V_m$ is given by the sum of the diagonal values, where $j=i$ holds. We will calculate the
real and the imaginary part separately.For the real part of the trace of $V_m$, the first bit value of $i$ has to be zero, thus we find

\begin{align}
\mathcal{R}\Mg{\tr V_m} = \sum_{i\in \F_2^m, i_1=0} (V_m)_{i,i} = \sum_{i\in \F_2^m, i_1=0} (-1)^x,
\end{align}

with $x= 0\cdot i_2 + (0,i_2)\cdot (i_3,i_4)^t + \ldots + (0,i_2,\ldots,i_{m/2})\cdot (i_{m/2+1},\ldots,i_{m})^t + i\cdot i$.
We arrange the sum in pairs, where for one element of the pair $i_{m/2+1}=0$ holds and for the other element $i_{m/2+1}=1$. Since
$i_1=0$ holds for all terms in the sum, $x$ differs only in the last term for the two elements of a pair, where $i \cdot i$ gives the
Hamming weight of $i$, that differs by one for the different cases. So for one element of each pair, $x$ is an even number, for the
other element it is odd and as exponents of $-1$ can be taken modulo two, the expression $(-1)^0+(-1)^1=0$ is the sum of both
elements and equals zero. Since all elements can be paired this way, the real part of the trace of $V_m$ vanishes.For the imaginary part of the trace of $V_m$ the value of $i_1$ equals one, we find

\begin{align}
\mathcal{I}\Mg{\tr V_m} = \sum_{i\in \F_2^m, i_1=1} (V_m)_{i,i} = \sum_{i\in \F_2^m, i_1=1} (-1)^x,
\end{align}

with $x= 1\cdot i_2 + (1,i_2)\cdot (i_3,i_4)^t + \ldots + (1,i_2,\ldots,i_{m/2})\cdot (i_{m/2+1},\ldots,i_{m})^t + i\cdot i$.
We will consider two cases: For those elements $i$, where at least one of the bit values of $\Mg{i_2,\ldots, i_{m/2}}$ equals
zero, we can arrange the elements analogously in pairs as done for the real part. The second case treats all remaining
elements, namely those where all bit values of $\Mg{i_2,\ldots, i_{m/2}}$ equal one, which produces terms with

\begin{align}\label{eqn:unitop:x1111}
x= 1\cdot 1 + (1,1)\cdot (1,1)^t + \ldots + (1,\ldots,1)\cdot (i_{m/2+1},\ldots,i_{m})^t + i\cdot i.
\end{align}

For $m=1$, we have only one term and this adds $-1$ to the imaginary part. For $m=2$, the imaginary part equals
$\sum_{i_2=0}^1 (-1)^{1\cdot i_2 + (1,i_2)\cdot (1,i_2)^t}$ which leads to $-2$. For all $m>2$ we can use the following
observation: For each of the $2^{m/2}$ elements with $i=(1,\ldots,1,i_{m/2+1},\ldots, i_m)$ the two rightmost terms of
Equation (<ref>) give the same result modulo two, since the number of ones in the left part is even.
As $m$ is a power of two, all remaining terms without the first one result in powers of two and the first one equals
one. Therefore, the sum of all those elements provides a contribution of $-2^{m/2}$ to the imaginary part of the trace of $V_m$. Thus, we have

\begin{align}\label{eqn:unitop:trVm}
\tr V_m = - \iE 2^{m/2}.
\end{align}

Taking all results together, we finally find for the unitary operator $U_m$ which results for the Fermat-based sets,

\begin{align}
U_{2m} = -\iE 2^{-m} \mathrm{diag}( \cM( V_m ) )  \cdot \bar H^{\otimes 2 m}.
\end{align}

The difference of the operators to those given in [84] is due to the replacement of $X\!Z$ operators by $\ZX$ operators
which was motivated in Section <ref>. Using the results of this section may lead to a proof of Wiedemann's
conjecture by the analogy that was proven in Theorem <ref>. An idea is given in Appendix <ref>.

§.§ More general sets

The construction of a unitary operator that generates a complete set of cyclic MUBs which is based on a more general stabilizer
matrix, like those discussed in Sections <ref> and <ref> is possible in a similar way as was done
for the Fibonacci-based sets in Section <ref> by using the same steps. But, presumably, the resulting form will
not be decomposable as simple as in Equation (<ref>). The search for a nice construction form is beyond the scope of this work;
nevertheless, a physical implementation of general stabilizer matrices will be discussed in Section <ref>
that is more applicable than the representation as a unitary matrix with a simple construction.

§ GATE DECOMPOSITION

We have seen so far, that the construction of complete sets of cyclic MUBs for a Hilbert space of
dimension $d=2^m$ with $m \in \N^*$ is based on the construction of a stabilizer matrix (cf. Sections <ref>, <ref>, <ref>, and <ref>),
which can be represented as a unitary matrix (cf. Section <ref>). What still lacks
is the implementation of the individual bases into an experimental setup (e. g. a quantum computer).
A common general description of an implementation is the idea of a quantum circuitQuantum circuit.
This is a scheme, similar to a classical circuit, that gives a description of the behavior of a unitary
operation that can be seen as a recipe on how to implement the operation in quantum gates.
The challenge in deriving this circuit from the operation is to get a minimal number of those gates
where each gate acts on a minimal number of qubits.[An advantage of cyclic MUBs is that
a single circuit can be used to implement a complete set of MUBs, where for a non-cyclic set, $d+1$
different circuits have to be implemented, as was done e. g. by Klimov  [50].]
It was shown that single-qubit gates and two-qubit gates
produce a universal setUniversal set, which can be used to implement any unitary operation [26, 23, 57, 16].
It is important to mention that the application of gates in quantum circuits have to be read from left
to right, rather than the application of quantum operations on quantum states.
Within this section, we provide a simple generation of a quantum circuit for the Fibonacci-based sets of
Section <ref> and show the minimal form of this circuit in the case of the Fermat sets of Section <ref>.
Finally, an approach for constructing a quantum circuit from a more general stabilizer matrix is given.
A short discussion on performance and error optimizations closes this section.

§.§ Fibonacci-based sets

In the case of Fibonacci-based sets, it turns out that the construction of an appropriate quantum circuit
that implements the generator of a complete set of cyclic MUBs can be read out from the reduced
stabilizer matrix $B \in M_m(\F_2)$ as it was introduced in Equation (<ref>). But, honestly
speaking, this fact results from the direct construction of the unitary operator, as given by Equation (<ref>).
Since the global phase cannot be measured and is therefore irrelevant in the physical implementation, we have
to generate a quantum circuit for the operator

\begin{align}
U' = P \cdot H^{\otimes m}.
\end{align}

Obviously, the application of the Hadamard matrix $H^{\otimes m}$ can be done by applying $H$ to each of the
$m$ qubits individually. The phase system is given by $P = \mathrm{diag}((p_j)_{j \in \F_2^m})$, where the
binary representation of $j$ refers to a specific quantum state. The bit $j_k$ addresses then with $k \in \MgE{m}$
the qubit at position $k$. This phase system depicts directly the implementation into a quantum circuit. More precisely,
we can rewrite the phase factor as it was given in Equation (<ref>), where we find

\begin{align}
p_j =& (-\iE)^{\sum_{k,l=1}^m b_{kl} j_k j_l} (-1)^{\sum_{k=1}^m b_{kk} j_k}\nonumber\\
=& \prod_{k>l=1}^m \left((-1)^{j_k j_l}\right)^{b_{kl}} \cdot \prod_{k=1}^m \left(\iE^{ j_k}\right)^{b_{kk}}\label{eqn:gatedecomp:fibset:pj}.
\end{align}

The second term of Equation (<ref>) tells us, that a phase of $\iE$ is applied to the qubit with
index $k$, if it is in state $\ket{1}_k\bra{1}$ and $b_{kk}=1$; in the case $\ket{0}_k\bra{0}$ nothing happens. The first
term is only relevant in the case that the qubits with index $k$ and $l$ are in the state $\ket{1}_k\bra{1} \otimes \ket{1}_l\bra{1}$
(which means that $j_k = j_l=1$) and if $b_{kl}=1$. The described actions can be performed by the following elementary

* The single-qubit  gate acting on qubit $k$ which is defined as

\begin{align}
\texttt{Phase}_k(\EZ^{\iE\phi}) &= \ket{0}_k\bra{0} + \EZ^{\iE \phi} \ket{1}_k\bra{1},
\end{align}

and visualized as

[scale=1, transform shape]
operator = [draw,fill=white,minimum size=1.5em]
phase = [fill,shape=circle,minimum size=5pt,inner sep=0pt]
at (0,0) (q1) $\ket{\Psi}$;
[operator] (op1) at (2,0) $\EZ^{\iE\phi}$ edge [-] (q1);
at (4,0) (q1') $\ket{\Psi'}$ edge [-] (op1);

with phase $\phi \in [0,2\pi)$.

* The two-qubit controlled- gate

\begin{align}
\texttt{CPhase}_{s \rightarrow t}(\EZ^{\iE\phi}) &= \ket{0}_s\bra{0} \otimes \ket{0}_t\bra{0}
+ \ket{0}_s\bra{0} \otimes \ket{1}_t\bra{1} \nonumber\\
&\hspace{-1cm}+ \ket{1}_s\bra{1} \otimes \ket{0}_t\bra{0}
+ \EZ^{\iE\phi} \ket{1}_s\bra{1} \otimes \ket{1}_t\bra{1},
\end{align}

with control qubit $s$, target qubit $t$ and phase $\phi \in [0,2\pi)$. For a two-qubit state
$\ket{\Psi_s, \Psi_t}$, the  gate induces in general a transformation
$\ket{\Psi_s, \Psi_t} \rightarrow \ket{\Psi_s, \Psi'_t}$ and is visualized by the following

[scale=1, transform shape]
operator = [draw,fill=white,minimum size=1.5em]
phase = [fill,shape=circle,minimum size=5pt,inner sep=0pt]
at (0,0) (q1) $\ket{\Psi_s}$;
at (0,-1) (q2) $\ket{\Psi_t}$;
[phase] (p1) at (2,0)  edge [-] (q1);
[operator] (op1) at (2,-1) $\EZ^{\iE\phi}$ edge [-] (q2);
at (4,0) (q1') $\ket{\Psi_s}$ edge [-] (p1);
at (4,-1) (q2') $\ket{\Psi'_t}$ edge [-] (op1);
[-] (p1) – (op1);

We can use these two gates to implement the phase factor of Equation (<ref>),
namely by identifying the gates from the reduced stabilizer matrix $B$ as:

* For $b_{kk} = 1$, apply $\texttt{Phase}_k(\iE)$.

* For $b_{kl} = 1$ and $k>l$, apply $\texttt{CPhase}_{k \rightarrow l}(-1)$.

As an example, a possible reduced stabilizer matrix that can be used to generate a complete system of cyclic MUBs for a
quantum system of four qubits, is given by the recursive construction of Equation (<ref>) with

\begin{align}
B_{2^2} = \begin{pmatrix}1&1&1&0\\1&0&0&1\\1&0&0&0\\0&1&0&0\end{pmatrix}.
\end{align}

[scale=0.8, transform shape]

operator = [draw,fill=white,minimum size=1.5em]
phase = [fill,shape=circle,minimum size=5pt,inner sep=0pt]
surround = [fill=black!10,thick,draw=black,rounded corners=2mm]

at (1,0) (q1) ;
at (1,-1) (q2) ;
at (1,-2) (q3) ;
at (1,-3) (q4) ;

[operator] (op11) at (2,0) $H$ edge [-] (q1);
[operator] (op21) at (2,-1) $H$ edge [-] (q2);
[operator] (op31) at (2,-2) $H$ edge [-] (q3);
[operator] (op41) at (2,-3) $H$ edge [-] (q4);

[phase] (op22) at (3,-1)  edge [-] (op21);
[operator] (op42) at (3,-3) $-1$ edge [-] (op41);
[-] (op22) – (op42);

[phase] (op12) at (4,0)  edge [-] (op11);
[operator] (op32) at (4,-2) $-1$ edge [-] (op31);
[-] (op12) – (op32);

[phase] (op13) at (5,0)  edge [-] (op12);
[operator] (op23) at (5,-1) $-1$ edge [-] (op22);
[-] (op13) – (op23);

[operator] (op14) at (6,0) $\iE$ edge [-] (op13);

[-] (op14) – (7,0);
[-] (op23) – (7,-1);
[-] (op32) – (7,-2);
[-] (op42) – (7,-3);

[decorate,decoration=brace,thick] (7.3,0.2) to
node[midway,right] (bracketR) $\;\;= U'_{2^2}$
[decorate,decoration=brace,thick, rotate=180] (-0.8,3.2) to
node[midway,left,rotate=180] (bracketL)

[surround] (background) [fit = (op11) (op42) (bracketL) (bracketR)] ;

Quantum circuit for the generator $U'_{2^2}$ of a complete set of cyclic MUBs for a four qubit system.

Following the results given above, this solution results in one  gate, three  gates and
four  gates, as depicted in
Figure <ref>. Accordingly, in the case of the recursive construction of Fermat sets
given by Equation (<ref>), the implementation of the generator of a complete set of cyclic MUBs
for $m$ qubits needs one  gate, $m-1$  gates and $m$  gates, which
is optimal in the number of two-qubit gates.[As the bases of a complete set of cyclic MUBs for an $m$ qubit system measure the complete
state of this system, a possible quantum circuit should link all qubits together, which can be done by controlled gates.
If not all qubits were linked together, then only information on subsystems could be measured. Consequently, if for controlled gates
only two qubit gates are used, the minimum number of these gates is $m-1$.]
In the case of the Fibonacci-based sets in the Form of Equation (<ref>), an implementation would need
not more than $\lceil m/2 \rceil + 5$  gates, $(\lceil m/2 \rceil^2 - \lceil m/2 \rceil)/2 + 10$
gates and $m$  gates for $m \in \MgE{600}$ as can be seen in Appendix <ref>.
This does not seem to be optimal at all. Also the proposed method to find a symmetric companion matrix (cf. Conjecture <ref>)
does not seem to be capable to solve this problem optimally. Therefore, further investigations on how to reduce the number
of non-vanishing entries of the reduced stabilizer matrices are essential in order to reduce the number of gates needed.

§.§ Homogeneous sets

To implement homogeneous sets into quantum circuits we cannot use similar methods as for the Fibonacci-based sets as long
as no construction of the unitary matrix is given in an analogous form to that of Equations (<ref>) and (<ref>).
Therefore, we will introduce a method that is capable to generate the quantum circuit
of nearly any matrix $C \in M_{2m}(\F_2)$ that is symplectic. At first, symplectic representations of different quantum gates will
be discussed; thereafter, it will be shown how a large set of symplectic matrices with entries in $\F_2$ can be decomposed into a
product of symplectic matrices in order to become directly implementable by corresponding quantum gates. Quantum circuits
derived by this method for the homogeneous sets which are discussed, are shown in Appendices <ref> and <ref>.Let us define an arbitrary symplectic matrix $C \in M_{2m}(\F_2)$ in block-matrix form as

\begin{align}\label{eqn:gatedecomp:homo:C}
C = \begin{pmatrix} s & t \\u & v \end{pmatrix},
\end{align}

with submatrices $s, t, u, v \in M_m(\F_2)$. As stated in Appendix <ref>, elements of the Clifford group
are automorphisms of the set of Pauli operators. By their group property, these elements are invertible, so also their
representation as symplectic matrices. Therefore, any symplectic matrix has full rank, thus, the row vectors within
the submatrix $(u,v)^t$ are linearly independent. For the group-based sets defined by Equation (<ref>)
this fact can be seen also in the stabilizer matrix directly, since $v:=0_m$ and $u:=R^{-1}$ is invertible. The same holds
for the submatrix $(s,u)$, but is not that obvious. According to this
observation, it is in general possible to obtain by elementary row and column operations a transformed matrix where the submatrix
$u$ is invertible. Within this section, we limit the consideration only to those cases where $u$ is invertible.
To apply these necessary operations and to implement the resulting matrix, different
quantum gates have to be considered.By the construction of the classes $\cC_j$ with $j \in \MgN{d}$ as given in Equation (<ref>), each
class consists of Pauli operators. The matrix $C$ then realizes by its symplecticity property that the set of a certain
class of Pauli operators is transformed to another set of operators, i. e. the next class. Therefore, a circuit of
quantum gates which represents the matrix $C$ has to implement transformations of a set of Pauli operators to another
set. As we can see the whole circuit as the product of basic transformations (i. e. the quantum gates), the implication
of each quantum gate can be analyzed by the consideration of its truth table of Pauli operators. To explain the idea, we
analyze the  gate as an example:The Hadamard operator is defined by Equation (<ref>) as

\begin{align}
H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix};\quad \mathrm{with} \quad H^{\dagger} = H,
\end{align}

it acts on the Pauli operators $X,Y$ and $Z$, which are listed in Appendix <ref>, as $H X H^{\dagger} = Z$,
$H Y H^{\dagger} = -Y$ and $H Z H^{\dagger} = X$. To construct a complete set
of cyclic MUBs, the eigenbases of the classes $\cC_j$ are relevant, but the phases of the elements are not relevant. A quantum
gate, represented as a symplectic matrix $C_\texttt{H}$, that implements the Hadamard operator, should then act on the
Pauli operators for a single qubit, represented as elements of the finite field $\F_2^2$, as

\begin{align}
C_\texttt{H} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix},
\quad C_\texttt{H} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix},\quad\mathrm{and}\quad
C_\texttt{H} \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \end{pmatrix}.
\end{align}

Obviously, any symplectic matrix will set the zero vector to the zero vector, which is in accordance to the unitary representation
given above. The representation of the Hadamard operator as a symplectic matrix is finally given by

\begin{align}
C_\texttt{H} = \begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix},
\end{align}

with the corresponding visual representation as the  gate.

[scale=1, transform shape]
operator = [draw,fill=white,minimum size=1.5em]
phase = [fill,shape=circle,minimum size=5pt,inner sep=0pt]
at (1,0) (q1) ;
[operator] (op1) at (2,0) $\texttt{H}$ edge [-] (q1);
at (3,0) (q1')  edge [-] (op1);

This gate acts only on a single qubit, so the unitary operator on a multi-qubit system with $m$ qubits that applies a
Hadamard gate on the $i$-th qubit, is given by

\begin{align}\label{eqn:gatedecomp:homo:UHi}
U^{(i)}_{\texttt{H}} = \left( \bigotimes_{l=1}^{i-1} \Eins_2 \right) \otimes H \otimes \left( \bigotimes_{l=i+1}^{m} \Eins_2 \right),
\end{align}

its representation as a symplectic matrix $C^{(i)}_{\texttt{H}} = \left(c_\texttt{H}^{(i)}\right)_{kl}$ has entries

\begin{align}\label{eqn:gatedecomp:homo:cHikl}
\left(c_\texttt{H}^{(i)}\right)_{kl} =
\begin{cases}
\delta_{kl} & \quad\mathrm{for}\quad k,l \notin \Mg{i,m+i},\\
1-\delta_{kl} & \quad\mathrm{for}\quad k, l \in \Mg{i,m+i}.
\end{cases}
\end{align}

Another single-qubit gate is the  gate, that was already mentioned in Section <ref>, but we will
again concentrate on the  gate, with a phase of $\pm \iE$.[It turns out, that a phase of $+\iE$ leads to
the same result as a phase of $-\iE$, if we do only concentrate on equivalence classes of Pauli operators, thus ignoring additional phases.]
The unitary matrix of the  gate is given by

\begin{align}
U_{\texttt{P}_{\pm \iE}} = \begin{pmatrix} 1 & 0 \\ 0 & \pm \iE \end{pmatrix},
\end{align}

and can be represented by the symplectic matrix

\begin{align}
C_{\texttt{P}_{\pm \iE}} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix},
\end{align}

with the following visual representation.

[scale=1, transform shape]
operator = [draw,fill=white,minimum size=1.5em]
phase = [fill,shape=circle,minimum size=5pt,inner sep=0pt]
at (1,0) (q1) ;
[operator] (op1) at (2,0) $\iE$ edge [-] (q1);
at (3,0) (q1')  edge [-] (op1);

The multi-qubit operators can be built in a similar fashion as for the  gate which are given by Equations
(<ref>) and (<ref>) and yield in the representation as a symplectic matrix,
acting on the $i$-th qubit,

\begin{align}\label{eqn:gatedecomp:homo:cPikl}
\left(c^{(i)}_{\texttt{P}_{\pm \iE}}\right)_{kl} = \delta_{kl} + \delta_{ki} \delta_{l (m+i)}.
\end{align}

As a next step, we consider controlled two-qubit gates
like the  gate that was already introduced in Section <ref>. For these gates, an operation is applied
to the target qubit if and only if the state of the control qubit equals $\ket{1}$. Here, we concentrate on
the  gate and the  gate. The unitary operator of the  gate, which is equivalent to
a  gate, is given by

\begin{align}
U^{(1,2)}_{\texttt{CNot}} = \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\end{pmatrix}.
\end{align}

The symplectic representation derived from the truth table of Pauli operators of this operation is given by

\begin{align}
C^{(1,2)}_{\texttt{CNot}} = \begin{pmatrix} 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 1\end{pmatrix},
\end{align}

and has also a visual representation.

[scale=1, transform shape]
not = [draw,fill=white,shape=circle, minimum size=1.5em]
phase = [fill,shape=circle,minimum size=5pt,inner sep=0pt]
at (1,0) (q1) ;
at (1,-1) (q2) ;
[phase] (p1) at (2,0)  edge [-] (q1);
(2,-1) node[draw,circle, minimum size=1.1em] ;
[-] (p1) – (2,-1cm-.551em);
at (3,0) (q1')  edge [-] (p1);
at (3,-1) (q2')  edge [-] (q2);
[-] (p1) – (op1);

The multi-qubit operator for a  gate with control qubit $c$ and target qubit $t$, represented as a symplectic matrix,
is given by

\begin{align}\label{eqn:gatedecomp:homo:cnotmulti}
\left(c^{(c,t)}_{\texttt{CNot}}\right)_{kl} = \delta_{kl} + \delta_{kc} \delta_{lt} + \delta_{k(t+m)} \delta_{l(c+m)}.
\end{align}

The last gate we want to consider is the  gate, which is a special version of the  gate, with a
fixed phase factor of $-1$. We will denote this gate by  in the following. Its unitary representation is given by

\begin{align}
U^{(1,2)}_{\texttt{CZ}} = \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & -1\end{pmatrix},
\end{align}

and its symplectic representation by

\begin{align}
C^{(1,2)}_{\texttt{CZ}} = \begin{pmatrix} 1 & 0 & 0 & 1\\ 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\end{pmatrix}.
\end{align}

The visualization of the  gate is the following circuit.

[scale=1, transform shape]
operator = [draw,fill=white,minimum size=1.5em]
phase = [fill,shape=circle,minimum size=5pt,inner sep=0pt]
at (1,0) (q1) ;
at (1,-1) (q2) ;
[phase] (p1) at (2,0)  edge [-] (q1);
[operator] (op1) at (2,-1) $Z$ edge [-] (q2);
at (3,0) (q1')  edge [-] (p1);
at (3,-1) (q2')  edge [-] (op1);
[-] (p1) – (op1);

Within a multi-qubit environment, the symplectic representation of the  gate with control qubit named $c$
and target qubit $t$ is accordingly given by

\begin{align}\label{eqn:gatedecomp:homo:czmulti}
\left(c^{(c,t)}_{\texttt{CZ}}\right)_{kl} = \delta_{kl} + \delta_{kc} \delta_{l(t+m)} + \delta_{kt} \delta_{l(c+m)}.
\end{align}

Armed with all those gates we can implement any stabilizer matrix $C \in M_{2m}(\F_2)$ in the form of Equation
(<ref>) with $u$ invertible by a quantum circuit. The
process we suggest is realized in two parts. In the first part, the stabilizer matrix is transformed into a special
form by symplectic operations such that $u$ is mapped to $\Eins_m$, in the second part, this form can be written as a product of symplectic matrices
that can be implemented directly.

Any symplectic matrix $C \in M_{2m}(\F_2)$ in the form of Equation (<ref>) with $u$ invertible, can be transformed by applying  operations
in the form of Equation (<ref>) from the left in order to obtain a symplectic matrix in the form

\begin{align}\label{eqn:gatedecomp:homo:C'}
C' = \begin{pmatrix}s'&t'\\\Eins_m&v'\end{pmatrix}.
\end{align}

If $u$ is an invertible matrix, it can be diagonalized by the Gaussian elimination, that uses elementary row or column operations.
By multiplying a  operation in the manner of Equation (<ref>) from the left to the
symplectic matrix $C$, within the block of the submatrix $u$, the row which has the index of the control qubit is added and stored
to the row which has the index of the target qubit. Two rows $i,j$ of $u$ can be swapped by applying
$C^{(i,j)}_{\texttt{CNot}} C^{(j,i)}_{\texttt{CNot}} C^{(i,j)}_{\texttt{CNot}}$, as the elements of $u$ have characteristic two.
Therefore, all elementary row operations can be realized with  operations.[The third operation, namely the multiplication
of any row with a non-zero scalar, is given by the identity operation in $\F_2$, as no non-zero element exists besides $1$.]

The transformation may also be realized by multiplying  operations from the right which induces elementary column operations, respectively.Lemma <ref> leads implicitly to the following corollary:

Two quantum gates which have representations as symplectic matrices in the form

\begin{align}
C_1= \begin{pmatrix} \Eins_m & a_1\\ 0_m & \Eins_m \end{pmatrix}\quad\mathrm{and}\quad C_2= \begin{pmatrix} \Eins_m & a_2\\ 0_m & \Eins_m \end{pmatrix},
\end{align}

with $a_1, a_2 \in M_m(\F_2)$, commute.

The application of $C_1$ to $C_2$ (or vice versa) gives

\begin{align}
C_1 C_2 = \begin{pmatrix} \Eins_m & a_1+a_2\\ 0_m & \Eins_m \end{pmatrix}.
\end{align}

Therefore, the  gates and the  gates commute.

The resulting matrix of Lemma <ref> can be decomposed into a product of matrices that can be used to read off the required
gates,  gates and  gates directly.

Any symplectic matrix $C \in M_{2m}(\F_2)$ in the form of Equation (<ref>), can be factorized in matrices that describe the product
of  gates,  gates, and an $m$-folded tensor product of the Hadamard matrix as

\begin{align}\label{eqn:gatedecomp:homo:decomp}
C' = \begin{pmatrix}s'&t'\\ \Eins_m&v'\end{pmatrix} =
\begin{pmatrix}\Eins_m & s'\\ 0_m & \Eins_m\end{pmatrix} \begin{pmatrix}0_m &\Eins_m\\ \Eins_m & 0_m\end{pmatrix} \begin{pmatrix}\Eins_m & v'\\ 0_m & \Eins_m\end{pmatrix},
\end{align}

which implies $t'=\Eins_m+s'v'$.

Corollary <ref> of Appendix <ref> states the conditions on $C'$ to be a symplectic matrix. From the first condition
follows, that $s'$ has to be symmetric. From the last condition follows then with $u'=\Eins_m$ that $t'=\Eins_m+s'v'$. Inserting $t'$ into the second condition
shows finally, that also $v'$ has to be symmetric.The given equation appears naturally, where the middle term corresponds to Hadamard operations given by Equation (<ref>). The remaining
two terms can be created using Corollary <ref> the following way:
Each non-zero element on the diagonal of $s'$ and $v'$, respectively, refers to a  gate, as can be seen from Equation (<ref>).
As $s'$ and $v'$ are symmetric matrices, their off-diagonal, non-zero elements refer to  gates, according to Equation (<ref>).

To implement $s'$ and $v'$, at most $2m$  gates and at most $m^2 - m$  gates are needed. The form derived by Equation
(<ref>) requires exactly $m$  gates. An upper bound to realize the Gaussian elimination as discussed in Lemma
<ref> is the implementation of $m^2$ different  gates, as any $m$-bit vector can be build by maximally $m$
operations within the set of $m$ linearly independent vectors. For $v'=0_m$ follows $t' = \Eins_m$, thus a Fibonacci-based set. The quantum
circuit which appears then by applying Lemma <ref> is the same as the one given by Figure <ref>.Results of the semigroup sets (cf. Appendix <ref>) indicate, that the sets of MUBs can be limited to sets which have an invertible $m \times m$ submatrix in the
upper right corner (i. e. the matrix $t$ of Equation (<ref>) is invertible). If this is not the case, one may find a set of quantum
gates that realizes an appropriate transformation. Implementations of complete sets of MUBs for three qubit systems are shown by Figure <ref>
and Figure <ref>; quantum circuits for four qubit systems are listed in Appendices <ref> and <ref>.

[scale=0.8, transform shape]
operator = [draw,fill=white,minimum size=1.5em]
phase = [fill,shape=circle,minimum size=5pt,inner sep=0pt]
surround = [fill=black!10,thick,draw=black,rounded corners=2mm]

at (1,0) (q1) ;
at (1,-1) (q2) ;
at (1,-2) (q3) ;

[phase] (p0) at (2,-2)  edge [-] (q3);
(2,0) node[draw,circle, minimum size=1.1em] ;
[-] (p0) – (2,0cm+.551em);

[phase] (p1) at (3,0)  edge [-] (q1);
(3,-2) node[draw,circle, minimum size=1.1em] ;
[-] (p1) – (3,-2cm-.551em);

[phase] (p2) at (4,-2)  edge [-] (p0);
(4,0) node[draw,circle, minimum size=1.1em] ;
[-] (p2) – (4,0cm+.551em);

[operator] (p3) at (5,0) $\iE$ edge [-] (p1);
[operator] (p4) at (5,-2) $\iE$ edge [-] (p2);

[phase] (p5) at (6,-1)  edge [-] (q2);
[operator] (p6) at (6,-2) $-1$ edge [-] (p4);
[-] (p5) – (p6);

[operator] (p7) at (7,0) $H$ edge [-] (p3);
[operator] (p8) at (7,-1) $H$ edge [-] (p5);
[operator] (p9) at (7,-2) $H$ edge [-] (p6);

[-] (p7) – (8,0);
[-] (p8) – (8,-1);
[-] (p9) – (8,-2);

[decorate,decoration=brace,thick] (8.3,0.2) to node[midway,right] (bracketR) $\;\;=C_{(2,3,4)}$ (8.3,-2.2);
[surround] (background) [fit = (bracketL) (p7) (p9) (bracketR)] ;

Quantum circuit for the generator $C_{(2,3,4)}$ of Equation (<ref>) of a complete, homogeneous set of group-based cyclic MUBs for a three qubit system.

[scale=0.8, transform shape]
operator = [draw,fill=white,minimum size=1.5em]
phase = [fill,shape=circle,minimum size=5pt,inner sep=0pt]
surround = [fill=black!10,thick,draw=black,rounded corners=2mm]

at (1,0) (q1) ;
at (1,-1) (q2) ;
at (1,-2) (q3) ;

[phase] (p0) at (2,-2)  edge [-] (q3);
(2,0) node[draw,circle, minimum size=1.1em] ;
[-] (p0) – (2,0cm+.551em);

[phase] (p1) at (3,0)  edge [-] (q1);
(3,-2) node[draw,circle, minimum size=1.1em] ;
[-] (p1) – (3,-2cm-.551em);

[phase] (p2) at (4,-2)  edge [-] (p0);
(4,0) node[draw,circle, minimum size=1.1em] ;
[-] (p2) – (4,0cm+.551em);

[operator] (p3) at (5,-1) $\iE$ edge [-] (q2);
[operator] (p4) at (5,-2) $\iE$ edge [-] (p2);

[phase] (p5) at (6,-1)  edge [-] (p3);
[operator] (p6) at (6,-2) $-1$ edge [-] (p4);
[-] (p5) – (p6);

[operator] (p7) at (7,0) $H$ edge [-] (p1);
[operator] (p8) at (7,-1) $H$ edge [-] (p5);
[operator] (p9) at (7,-2) $H$ edge [-] (p6);

[operator] (p11) at (8,-1) $\iE$ edge [-] (p8);
[operator] (p12) at (8,-2) $\iE$ edge [-] (p9);

[-] (p7) – (9,0);
[-] (p11) – (9,-1);
[-] (p12) – (9,-2);

[decorate,decoration=brace,thick] (9.3,0.2) to node[midway,right] (bracketR) $\;\;=C_{(1,6,2)}$ (9.3,-2.2);
[surround] (background) [fit = (bracketL) (p7) (p9) (bracketR)] ;

Quantum circuit for the generator $C_{(1,6,2)}$ of Equation (<ref>) of a complete, homogeneous set of semigroup-based cyclic MUBs for a three qubit system.

§.§ Inhomogeneous sets

Quantum circuits for inhomogeneous sets can in principle be built in the same way as discussed for the homogeneous sets in the former section.
But these sets do not include the standard basis as shown in Section <ref>, i. e. the generator $G_0$
of the first class $\cC_0$ is not given by $G'_0=(\Eins_m,0_m)^t$; in standard form it reads $\bar G_0 = (\Eins_m,G_0^x)^t$ (cf. Equation (<ref>)).
Any symplectic matrix $C_0$ that transforms the generator $G'_0$ to the generator $\bar G_0$ can be taken to implement the
quantum circuit which produces the class $\cC_0$. In order to generate a class with commuting elements, $G_0^x$ has to be a symmetric matrix (cf. <cit.>).
The symplectic transformation $C_0 G'_0 = \bar G_0$ equals

\begin{align}
C_0 = \begin{pmatrix} \Eins_m & 0_m\\ G_0^x & \Eins_m \end{pmatrix},
\end{align}

and can be rewritten using  gates similarly to Lemma <ref> as

\begin{align}
C_0 = \begin{pmatrix}0_m &\Eins_m\\ \Eins_m & 0_m\end{pmatrix} \begin{pmatrix} \Eins_m & G_0^x\\ 0_m & \Eins_m \end{pmatrix} \begin{pmatrix}0_m &\Eins_m\\ \Eins_m & 0_m\end{pmatrix}.
\end{align}

The quantum circuit is then given by a  gate on each individual qubit (to implement the rightmost matrix),
followed by  gates on each diagonal non-zero value of $G_0^x$ and  gates on each off-diagonal, upper triangular
value of $G_0^x$, as done for Lemma <ref> (to implement the matrix in the middle) and again
gates on each individual qubit (to implement the leftmost matrix). Since the application of two consecutively applied
Hadamard operations is the unity operation, we can omit  gates on those qubits, that are involved neither in any
nor in any  gate.Resulting quantum circuits for complete sets of MUBs on systems with four qubits are given in Appendix <ref>, the quantum circuit for
the three-qubit system which is generated by $C_{(0,9,0)}$ of Equation (<ref>) is shown in Figure <ref>.

[scale=0.6, transform shape]
operator = [draw,fill=white,minimum size=1.5em]
phase = [fill,shape=circle,minimum size=5pt,inner sep=0pt]
surround = [fill=black!10,thick,draw=black,rounded corners=2mm]

at (1,0) (q1) ;
at (1,-1) (q2) ;
at (1,-2) (q3) ;

[phase] (p0) at (2,-1)  edge [-] (q2);
(2,0) node[draw,circle, minimum size=1.1em] ;
[-] (p0) – (2,0cm+.551em);

[phase] (p1) at (3,0)  edge [-] (q1);
(3,-1) node[draw,circle, minimum size=1.1em] ;
[-] (p1) – (3,-1cm-.551em);

[phase] (p2) at (4,-1)  edge [-] (p0);
(4,0) node[draw,circle, minimum size=1.1em] ;
[-] (p2) – (4,0cm+.551em);

[phase] (p3) at (5,-2)  edge [-] (q3);
(5,-1) node[draw,circle, minimum size=1.1em] ;
[-] (p3) – (5,-1cm+.551em);

[phase] (p4) at (6,-1)  edge [-] (p2);
(6,-2) node[draw,circle, minimum size=1.1em] ;
[-] (p4) – (6,-2cm-.551em);

[phase] (p5) at (7,-2)  edge [-] (p3);
(7,-1) node[draw,circle, minimum size=1.1em] ;
[-] (p5) – (7,-1cm+.551em);

[operator] (p6) at (8,0) $\iE$ edge [-] (p1);

[operator] (p7) at (9,0) $H$ edge [-] (p6);
[operator] (p8) at (9,-1) $H$ edge [-] (p4);
[operator] (p9) at (9,-2) $H$ edge [-] (p5);

[-] (p7) – (10,0);
[-] (p8) – (10,-1);
[-] (p9) – (10,-2);

at (14,0) (qq1) ;
at (14,-1) (qq2) ;
at (14,-2) (qq3) ;

[operator] (qp0) at (15,0) $H$ edge [-] (qq1);
[operator] (qp1) at (15,-1) $H$ edge [-] (qq2);

[phase] (qp4) at (16,0)  edge [-] (qp0);
[operator] (qp5) at (16,-1) $-1$ edge [-] (qp1);
[-] (qp4) – (qp5);

[operator] (qp6) at (17,0) $H$ edge [-] (qp4);
[operator] (qp7) at (17,-1) $H$ edge [-] (qp5);

[-] (qp6) – (18,0);
[-] (qp7) – (18,-1);
[-] (qq3) – (18,-2);

[decorate,decoration=brace,thick] (10.3,0.2) to node[midway,right] (bracketR) $\;\;=C_{(0,9,0)}$ (10.3,-2.2);
[decorate,decoration=brace,thick] (18.3,0.2) to node[midway,right] (bracketR2) $\;\;=G^{(x)}_{(0,9,0)}$ (18.3,-2.2);
[surround] (background) [fit = (bracketL) (p7) (p9) (bracketR)] ;
at (17,-1.02cm) [surround,minimum width=6.5cm,minimum height=2.8cm] (background) ;

Quantum circuit for the generator $C_{(0,9,0)}$ of Equation (<ref>) and the lower submatrix of the corresponding generator
of the class $\cC_0$, namely $G_{(0,9,0)}$ of Equation (<ref>), of a complete, inhomogeneous set of cyclic MUBs for a three qubit system.

§.§ Practical implementation

For a practical implementation of a complete set of cyclic MUBs, a quantum circuit like the example of Figure <ref>
would be able to transform a quantum state
by an operation that shifts one of the $d+1$ mutually unbiased bases to the next. Thus, after this process, variables that
are complementary to the former ones, could be measured in the computational basis. To be able to measure in a specific
basis of these $d+1$ different bases, the quantum circuit has to be used several times, in order to achieve the desired set of variables.
In average, this would cause $d/2$ applications of the quantum circuit. Consequently, for a large number of bases, namely a high dimension
$d$ of the Hilbert space, we propose to decompose the index of the bases binary and create for each power of two an individual
circuit. This raises the size of the experimental setup, but reduces the number of gates which are used in average to create
a specific basis.To give an example, for a dimension $d=2^{10}$, a complete set of MUBs has $1025$ different bases. Following the suggestion,
there would be ten different quantum circuits, thus any basis can be reached by using five of them in average. This is
a huge improvement over using $512$ times the same circuit in average if only the generator of the cyclic set of MUBs is implemented.Depending on the dimension, it could also be favored to decompose the index to any other number system; fortunately, all those
approaches can be realized by using the powers of the stabilizer matrix.

CHAPTER: EQUIVALENCE OF MUTUALLY UNBIASED BASES

A set of mutually unbiased bases defines a set of bases, where the absolute value of the overlap
of all pairs of vectors that are taken from two different bases within the set is constant
and equals $d^{-1/2}$, where $d$ is the dimension of the corresponding Hilbert space $\cH = \C^d$,
as was seen in Definition <ref>. From this definition it does not make any sense
to take the ordering of the bases into account, as well as the ordering of the basis vectors of any
basis. Also the multiplication of any basis vector with a phase factor preserves the mutual
unbiasedness which is finally even invariant under any unitary transformation which is applied to the whole set of bases.
By choosing a unitary transformation which is the inverse of any unitary operator $\cB_j$ of the set, this basis
becomes the standard basis, thus, each set of MUBs we find, can be transformed into a set that includes
the standard basis. We sum up these naturally appearing arguments to define the equivalence
of different sets of MUBs.
[Equivalence of mutually unbiased bases]

Two sets of mutually unbiased bases, namely $\fS = \Mg{\cB_0, \ldots, \cB_{r-1}}$ and$\fS' = \Mg{\cB'_0, \ldots, \cB'_{r-1}}$ with $r \in \N^*$, are said to be equivalent, if there holds

\begin{align}
\cB'_j = U \cB_{\pi(j)} W_j,
\end{align}

with a unitary matrix $U \in M_d(\C)$, a permutation $\pi$ on $\MgN{r-1}$ and monomial matrices[A
monomial matrix is defined to be a square matrix which has in every row and every column exactly one entry
that differs from zero.] $W_j$
that are given by the product of a permutation matrix and a diagonal phase matrix, for $j \in \MgN{r-1}$.

It has to be kept in mind that this definition of equivalence does not distinguish between the different
sets of cyclic MUBs, that were discussed in Sections <ref>, <ref> and <ref>.
Their equivalence in a Hilbert space of dimension $d=2^3$ was shown already in [75]. To
distinguish those sets, the consideration of the entanglement properties is essential, as discussed
in Section <ref>.Nevertheless, on this mathematical level of equivalence, different sets were discussed in the literature [20, 38, 48].
It is still an open problem how many inequivalent sets exist and how they are related.
Within the following section, we will discuss the equivalence of sets of MUBs which are based on
the construction of Bandyopadhyay  [7] and compare them with other constructions.
The construction of the Fibonacci-based sets of MUBs allows us to construct a set of operators that realize
permutations of the bases which is shown in the subsequent section.

§ HEISENBERG GROUP PARTITION SETS

To analyze the equivalence of sets of MUBs which are based on the construction of Bandyopadhyay ,
we can use their construction principles in order to simplify the comparison of two different sets. Following
the explanation given in Section <ref>, each element $U_j$ of the set of MUBs $\fS$ which is
generated by the powers of a unitary matrix $U$ as $\fS = \gen{U}$, is given by the set of common eigenvectors
of a corresponding class of Pauli operators $\cC_j$ (cf. Equation (<ref>)) with $j \in \MgN{r-1}$
and $r \in \N^*$. For a complete set of MUBs we have $r=d+1$. By the construction of Equation (<ref>),
a class $\cC_j$ is a set of elements $\ZX( \vec a )$ of the set of Pauli operators.
Analogously to the set of unitary matrices, we can define the set $\fC = \Mg{\cC_0, \ldots, \cC_{r-1}}$ of
classes $\cC_j$, that defines a complete set of MUBs, but without determining the order of the basis vectors or
their phase within a single class. To define equivalence on this level, there is no need for matrices $W_j$ as
introduced by Definition <ref>. We can formulate the following lemma:

Two sets of MUBs which are characterized by $\fC = \Mg{\cC_0, \ldots, \cC_{r-1}}$ and$\fC' = \Mg{\cC'_0, \ldots, \cC'_{r-1}}$
are equivalent, if there holds

\begin{align}
\cC'_j = U \cC_{\pi(j)} U^{\dagger},
\end{align}

with a unitary matrix $U \in \C^d$, a permutation $\pi$ on $\MgN{r-1}$, and $r \in \N^*$.

Starting with the Definition <ref> on the equivalence of MUBs, the matrices $W_j$ do not
play any role if we observe sets of Pauli operators $\cC_j$ and $\cC'_{\pi(j)}$ that do neither have any ordering
nor keep any phase. The equivalence has to be formulated the given way, since in the definition, we transform an
eigenvector $v$ as $Uv$; so, considering $v$ is an eigenvector of a matrix $A$, then $U v$ is an eigenvector
of $U A U^{\dagger}$.

As the classes of both sets $\fC$ and $\fC'$ contain only Pauli operators, the unitary transformation $U$ has to be
an element of the Clifford group (cf. Appendix <ref>), that maps by definition Pauli operators onto
Pauli operators. A certain class $\cC_j$ can be written in terms of a $2m \times (d-1)$-matrix, where each column
represents a Pauli operator, namely one of the vectors $\vec a$ given in Equation (<ref>). It can be
seen within that formula, that the $d-1$ elements can be generated by the (non-unique) so-called $2m \times m$ generator
matrix $G_j$, thus $\cC_j = \gen{G_j}$.[Normally, the symbol $\gen{A}$ refers to the set, which is generated by
the powers of $A$. Adopting the abstract meaning of this symbol, the expression $\gen{G_j}$ refers to a generation
which is specified by Equation (<ref>).]
Consequently, equivalence of two sets $\fC$ and $\fC'$ is given, if
and only if

\begin{align}\label{eqn:equiv:bandy:gen}
\gen{G'_j} = f \gen{G_{\pi(j)}} Q_j,
\end{align}

with a symplectic matrix $f$ (that maps Pauli operators onto Pauli operators), a permutation $Q_j$ and a permutation $\pi$ on
$\MgN{d}$. In the case, we write the
generators in standard form as discussed in Section <ref>, the generators $G_j$ and $G'_j$ become
unique. Then the permutation matrix $Q_j$ can be set to unity, thus neglected. For the transformation matrix
$f$ we are free to assume the block-matrix form

\begin{align}
f = \begin{pmatrix}s&t\\u&v\end{pmatrix}.
\end{align}

As it is shown by Corollary <ref>, this matrix is symplectic if and only if
$s^t u$ and $t^t v$ are symmetric and $v^t s - t^t u = \Eins_m$. With the methods introduced so far, we are able to
prove the equivalence of all Fibonacci-based complete sets of MUBs for a specific dimension $d=2^m$ with $m \in \N^*$.

§.§ Fibonacci-based sets

To construct a Fibonacci-based set, we have to follow simply the  that were given in Section <ref>.
It turns out, that neither the choice of the reduced stabilizer matrix $B$ is unique, nor the polynomial with
Fibonacci index $d+1$. Within this section we will show, that all Fibonacci-based sets which are based on the same
polynomial, are equivalent, independent of the choice of $B$. In a second step it is shown, that also a different
choice of the polynomial will create an equivalent set of cyclic MUBs.

Applying the generator of a set to all elements rotates this set, so we can choose $\pi(0) = 0$ for Equation
(<ref>), which implies $\gen{G_0} = \gen{G'_0}$ and in standard form $\bar G_0 = \bar G'_0$.
According to the construction of the Fibonacci-based sets, this generator is given

\begin{align}
G_0 = \begin{pmatrix}\Eins_m \\0_m\end{pmatrix},
\end{align}

which can also be seen in the derivation of the standard form in Equation (<ref>).
Thus, the choice for the permutation $\pi$ maps the class of Pauli-$Z$ operators of the set $\fC$ to the class
of Pauli-$Z$ operators of the set $\fC'$. Using Equation (<ref>),
we have to demand that $u=0_m$; to keep $f$ symplectic, we need to set $v=(s^t)^{-1}$. If both sets represent complete
sets of MUBs, we can represent their generators in standard form, where the elements $G^z_j$ as given in Equation (<ref>)
form a matrix representation of the finite field $\F_2^m$; the same holds true for the elements $G'^z_j$. We can
formulate a lemma on equivalent MUBs:

The choice of different reduced stabilizer matrices $B \in M_m(\F_2)$ with the same characteristic polynomial that has
Fibonacci index $2^m+1$ in the construction of Fibonacci-based MUBs leads to equivalent sets.

Two reduced stabilizer matrices $B, B' \in M_m(\F_2)$, which have to be symmetric according to Condition (i),
formulated in Section <ref>, are related as $B' = s B s^t$ with an orthogonal matrix $s \in M_m(\F_2)$, i. e.
$s^{-1} = s^t$. If we
set the transformation matrix as

\begin{align}
f = \begin{pmatrix}s&0_m\\0_m&s\end{pmatrix},
\end{align}

this matrix is symplectic. Applied to the generators of the classes $\cC_j$ of $\fC$ in standard form, we get $f \bar G_j = (s p_j(B), s)^t$,
where $p_j(B)$ is the polynomial $F_{j+1}(B) (F_{j}(B))^{-1}$.
As seen by Corollary <ref>, the transformed generators can be multiplied from the right by any invertible, block-diagonal matrix,
in particular also by $f^{-1}$. This leads to $f \bar G_j f^{-1} = (s p_j(B) s^t, \Eins_m)^t \equiv \bar G'_j$, the generators
of the classes of the set $\fC'$, in standard form. The case of $j=0$ can be shown the same way.

We can use this lemma to give a general theorem on the equivalence of Fibonacci-based sets.

All Fibonacci-based complete sets of MUBs are equivalent.

It was shown by Lemma <ref>, that all reduced stabilizer matrices with the same characteristic polynomial with Fibonacci
index $d+1$ result in equivalent sets of MUBs. In the case that the two stabilizer matrices $B$ and $B'$ have different characteristic polynomials
$p$ and $p'$, respectively, with Fibonacci index $d+1$, we can use the following consideration: In general, the two different irreducible polynomials
have degree $m$ and are defined over the ground field $\F_2$. We pick a pair of their roots, namely $\beta$ and $\beta'$, respectively. The adjunction of $\beta$
to $\F_2$ results in the field $\F_2(\beta) \cong \F_2[x]/p \F_2[x] \cong \F_{2^m}$, a similar consideration holds for $\beta'$. But as both extensions are Galois extensions,
the elements in $\F_2(\beta)$ and in $\F_2(\beta')$ are equivalent up to a permutation <cit.>. The elements of those fields appear
in the Pauli-$Z$ part of the generators in standard form (cf. Equation (<ref>)), thus both roots result in the same set of generators.
If we chose a symmetric matrix $B \in M_m(\F_2)$ to represent the root $\beta$, we have the freedom shown in Lemma <ref>,
where the minimal polynomial of $B$ equals the minimal polynomial of $\beta$.

In other words, Theorem <ref> shows, that the minimal polynomials of different elements
of the finite field $\F_{2^m}$ are possible minimal polynomials of a polynomial ring $\F_2[x]$ which is congruent
to the field itself; the chosen element only needs to have a minimal polynomial with degree $m$ (which is irreducible by definition).

§.§ (In-)Homogeneous sets

To show the equivalence of all sets which are based on the construction of Bandyopadhyay  in a similar fashion as for the Fibonacci-based sets,
further investigations are essential and exceed the scope of this work. As already stated above, it was shown in [75]
that all discussed sets in Hilbert space dimension $d=2^3$ are equivalent and the equivalence of different sets in higher dimensions
was indicated. Considerations in the fashion of Section <ref> would also lead to explicit transformations between
the different sets. In a first step, one may prove the equivalence of homogeneous sets with an additive group structure in the $Z$ component
of the class generators to Fibonacci-based sets and in a second step their equivalence with sets that possess only an additive semi-group
structure (cf. Sections <ref> and <ref>). As inhomogeneous sets do not contain
the standard basis, they are by Definition <ref> always equivalent to sets with a standard
basis, where a unitary operation for an arbitrary basis of this set exists, that transforms this set into a homogeneous set.

§.§ Different constructions

We can relate the Fibonacci-based sets to different constructions by following the discussion given in [7]: Theorem 4.4
introduces a construction that is equivalent to the standard form of homogeneous sets (cf. Equation (<ref>)).
In Section 4.3 the construction is limited to sets with an additive group structure (cf. Equation (<ref>)). Finally, at
the end of this section, the group structure is fixed in a way to obtain a field structure. Bandyopadhyay  took this
construction from the Wootters and Fields construction [90], indicating their equivalence.[In fact, the similarity
of the phase factor in Equation (<ref>) and Equation (<ref>) is a strong evidence of this equivalence.]
Godsil and Roy [38] relate these sets also with the sets constructed by Klappenecker and Rötteler
[51] and again to those of Bandyopadhyay .

§ CLASS-PERMUTATION OPERATORS

Starting with the definition of equivalence given by Definition <ref>, the
question arises whether the permutation $\pi$ on the indexing of the different bases can be
realized by a symplectic transformation. In the case of Fibonacci-based sets we discovered a set
of operators that seems to be capable to implement the set of permutations by a set of symplectic
transformations. We call this set the set of class-permutation operators
Class-permutation operators. The construction is quite intuitive, to follow the ideas, we
start with the definition of the first class-permutation operator $A_1$, that can be deduced from
the generator of a Fibonacci-based set in the form of Equation (<ref>) as

\begin{align}
A_1 = \begin{pmatrix}\Eins_m & B \\ 0_m & \Eins_m\end{pmatrix},
\end{align}

with the same reduced stabilizer matrix $B \in M_m(\F_2)$. Since the generator $G_j$ with $j \in \MgN{d}$
of any class is given by Equation (<ref>), the application of $A_1$ to this class generator leads

\begin{align}
A_1 G_j =& \begin{pmatrix}\Eins_m & B \\ 0_m & \Eins_m\end{pmatrix} \begin{pmatrix} F_{j+1} (B)\\ F_{j}(B)\end{pmatrix}
= \begin{pmatrix} F_{j+1} (B) + B F_{j}(B) \\ F_j(B)\end{pmatrix} = \begin{pmatrix} F_{j-1} (B) \\ F_j(B)\end{pmatrix}.
\end{align}

Using Lemma <ref>, we finally find

\begin{align}
A_1 G_j = \begin{pmatrix} F_{d+1-j+1} (B) \\ F_{d+1-j}(B)\end{pmatrix} \equiv G_{d+1-j},
\end{align}

with $d=2^m$. The first class-permutation operator $A_1$ inverts therefore the ordering of the classes $\cC_j$,
where $G_0 \rightarrow G_{d+1} \equiv G_0$ keeps its position. The symplecticity of the operator $A_1$
is obvious and can easily be checked with the help of Corollary <ref>.
In this fashion, we may construct further class-permutation operators as

\begin{align}
A'_l = \begin{pmatrix} F_l(B) & F_{l+1}(B)\\ 0_m & F_l(B) \end{pmatrix},
\end{align}

with $l \in \MgE{d}$, where in this case the properties of Corollary <ref>
are not fulfilled. To obtain a set of symplectic operators we multiply this set from the right by a
block-diagonal matrix $A^{\times}_l$ and get

\begin{align}
A_l := A'_l \cdot A^{\times}_l &= \begin{pmatrix} F_l(B) & F_{l+1}(B)\\ 0_m & F_l(B) \end{pmatrix} \begin{pmatrix} (F_l(B))^{-1} & 0_m\\ 0_m & (F_l(B))^{-1} \end{pmatrix}\\
&= \begin{pmatrix} \Eins_m & F_{l+1}(B) (F_l(B))^{-1}\\ 0_m & \Eins_m \end{pmatrix}.
\end{align}

By Proposition <ref> the mentioned polynomials in $B$ exist; we also like to point out the striking similarity of
these operators with the generator matrices in standard formStandard form given by Equation (<ref>).
If we apply these class-permutation operators to an arbitrary generator in standard form, we get for $A_l\cdot \bar G_0 = \bar G_0$ and for $j \neq 0$,

\begin{align}\label{eqn:equiv:classperm:fibperm}
A_l \cdot \bar G_j = \begin{pmatrix} F_{j+1}(B) (F_j(B))^{-1} + F_{l+1}(B) (F_l(B))^{-1}\\ \Eins_m \end{pmatrix}.
\end{align}

Thus, the operator $A_l$ adds a fixed polynomial of $B$ to the Pauli-$Z$ operator part of the generator $G_j$ in standard
form. As the set of all generator matrices contains all polynomials in $B$, the operator $A_l$ permutes these generators
according to fundamental finite field theory. Since we have $d$ different such class-permutation operators $A_l$, we realize all
basic permutations which are possible this way. Finally, the set of elements of a field is invariant under the addition of any
of its elements, so we can change the position of an arbitrary generator to any new position with this set of transformations.
But it is not clear if all permutations $\pi$ on $\MgE{d}$ can be realized. If so, the permutations can be expanded on the
set $\MgN{d}$ by adding the MUB generator $C$ to the set of permutation operators, since it permutes the classes cyclically, namely

\begin{align}
C \cdot G_j = G_{(j+1) \; \mathrm{mod} \; (d+1)}.
\end{align}

For general homogeneous sets of MUBs, an appropriate set of class-permutation operators can be constructed by naturally expanding
Equation (<ref>) for homogeneous sets, which results in the set of operators

\begin{align}
A_l^{\mathrm{hom}} := \begin{pmatrix} \Eins_m & F_{l+1}(B) (F_l(B))^{-1} R\\ 0_m & \Eins_m \end{pmatrix},
\end{align}

and leads to the same effective permutations as for the Fibonacci-based sets.

CHAPTER: CONCLUSIONS AND FURTHER WORK

Mutually unbiased bases (MUBs) find their applications in the fields of quantum state estimation
and quantum key distribution. By their relation to mathematical objects like orthogonal Latin squares,
symplectic spreads and many more, considerations result in immediate effects in these neighboring fields. Many (even fundamental) questions
on MUBs are still unsolved. The most famous are the question of the existence of a set with more than three MUBs in dimension six
(and how large sets may be in all other non-prime power dimensions), as well as the number of inequivalent sets in general.What we treat in this work is the problem of explicitly
constructing cyclic mutually unbiased bases in a straightforward way. Those bases have advantages in theoretical tasks as well as in experimental
implementations. They provide also a reduced formulation of a concrete set of MUBs. It turns out that the introduced Fibonacci-based sets have
nice properties and are related to well-known algebraic questions and may solve some of them if a construction for the symmetric companion matrix is found.
Generalizations indicate the potential of this approach and produce sets with different entanglement properties which can be observed in the
standard form. A relation to an open conjecture given by Wiedemann 1988 in finite field theory is discovered and serves a realization of this conjecture which may
lead to a proof, as well as a recursive construction of cyclic MUBs in an infinite subset of the dimensions. Most fortunately, such
a construction is not only found in terms of finite field theory, which can be used immediately for a discussed
implementation in quantum circuits, but also in terms of unitary matrices. The algorithmical formulation of an implementation strategy that may be suitable for all MUBs based on the
investigations of this work generalizes these observations and leads to feasible implementations. Approaches to prove the conjecture of Wiedemann, a
positive test of this conjecture for $k \in \MgE{11}$ in dimensions $d=2^{2^k}$ (which is limited by the largest known prime-number factorization of Fermat numbers)
and resulting cyclic MUBs for the Fibonacci-based sets for
dimensions $d=2^m$ with $m=\MgE{600}$ complete the considerations. The examination of the construction schemes relates the discussed MUBs
to known constructions on the level of equivalence of the measurement behavior.Obviously, several questions remain open, but lead with possible generalizations of the derived results to promising future investigations. At first,
it seems to be possible to construct a symmetric companion matrix in order to generate the cyclic MUBs directly from the algebraic results. For more
general sets, the derivation of a relation between the entanglement properties and the form of the stabilizer matrix would be valuable. The equivalence
transformations between all sets would show their equivalence and be useful in order to observe the transformations of their properties. Indications
on generalizations of the Fermat-based sets and the use of the doubling scheme for MUBs over the field of real numbers, should be followed.
Considerations for odd-prime power dimensions will probably lead to somehow different constructions as they refer to finite fields with an odd characteristic
(that behave entirely different comparing with an even characteristic), but would again expand the dimensions where sets of MUBs with a reduced
set of generators can be created. Finally, it would be nice to know if the derived methods can be used in a similar way to construct inequivalent sets
of MUBs by replacing the set of Pauli operators with different sets.

Quantum public-key encryption

CHAPTER: INTRODUCTION

The foundation for the field of quantum cryptography was laid in the early seventies of the last century,
when Wiesner had his prospective ideas on quantum money that cannot be counterfeited, based on a physical
uncertainty principle (and the fact, that an unknown quantum state cannot be cloned perfectly [95]).
Shortly after this work appeared in 1983[The manuscript by Wiesner on quantum money was
rejected by different journals and finally presented at a conference [91].], the field emerged with
the quantum key distribution (QKD) protocol of Bennett and Brassard [4] which is
used for symmetric encryption schemes. Different modifications of this protocol were discussed
[28, 11] and different security proofs were given later [61, 56, 82, 33].
[A more detailed discussion on the development of symmetric QKD protocols is given in
Part <ref> in Section <ref>.] With the new millennium, the potential benefit of the
properties of quantum physics was also discussed for further cryptographic primitives.
Examples are quantum digital signatures [29], quantum fingerprinting [8] and
quantum direct communication [14]. Another primitive is referred to as
quantum public-key encryption (QPKE) (see [69]), which will be of interest here.[
Many propositions for such a scheme were given [49, 43, 47, 67].]In contrast to the QKD, the aim of this scheme is to reduce the number of keys needed in a network with a
large number of parties which want to exchange secret information pairwise. To implement a QKD protocol in a network where all parties should be able to communicate
securely, the total number of keys scales quadratically with the number of parties, where in the QPKE scheme this
number scales linearly.[A different approach, where QKD protocols are used, implements a key-distribution center
(KDC), which is a trusted third party, but obviously also an attractive target.]The discussion in this Part of the work is based on a scheme given by Nikolopoulos [67] which achieves its security
from so-called quantum one-way functions (qOWF). At first, we will redraw within this chapter the protocol
itself. In Chapter <ref>, a detailed analysis of the security of this protocol against a powerful individual
attack is given as well as an idea to enhance the security against attacks by a noisy preprocessing method. The
investigations will be summarized finally in Chapter <ref>.

§ SINGLE-QUBIT-ROTATION PROTOCOL

A proposition for a QPKE protocol was given by Nikolopoulos in 2008 [67]Niko08E which can be
described in a nice way and therefore used to calculate the robustness against different
attacks and easily expanded with preprocessing steps, error performance and so on. The
security of the protocol is based on a quantum one-way functionQuantum one-way function.
Alice chooses a classical private key randomly and uses the mentioned function in order to
create as much public keys–which are given as qubit strings–as wanted (and proved to
be secure against certain classes of attacks). A party Bob, which wants to send a message to Alice, can apply for such a key and
perform a determined transformation on each qubit depending on the corresponding bit value
of the message and send it back. As Alice knows by the public key the initial states
of the qubits, she is able to extract the information Bob encrypted. We will sketch in this
section the basic properties of this protocol; a more substantial security analysis will be given in
Sections <ref> and <ref>.The protocol starts by creating a classical private key which is the integer string
$\key = (k_1, \ldots, k_N)$ with $N \in \N^*$ and uses a security parameter $n \in \N^*$, .
The key generation part of the protocol is the following:

* Take a (public) random positive integer $n \gg 1$.

* Generate a (private) random integer string $\key = (k_1, \ldots, k_N)$ with $N \in \N^*$, where each
integer is individually chosen randomly and independently from $\Z_{2^n}$.

* Prepare $T' \in \N^*$ copies of the (public) $N$-qubit public-key state from the private key $\textbf k$ as

\begin{align}\label{eqn:georgios:genPK}
\ket{\Psi_{\key}(\theta_n)} = \bigotimes_{j=1}^N \ket{\psi_{k_j} (\theta_n)},
\end{align}

\begin{align}\label{eqn:georgios:PKsingle}
\ket{\psi_{k_j} (\theta_n)} = \cos \left(\frac{k_j \theta_n}{2}\right) \ket{0_z} + \sin \left(\frac{k_j \theta_n}{2}\right) \ket{1_z},
\end{align}

where $\ket{0_z}$ and $\ket{1_z}$ refer to the eigenstates of the Pauli operator $\sigma_z$.

An appropriate lower limit on the value of $n$ depends on the number of
provided public keys; it will be derived in Section <ref>.

A copy of the public key
$\ket{\Psi_{\key}(\theta_n)}$ is simply given by the tensor product of $N$ individual public key qubits
$\ket{\psi_{k_j} (\theta_n)}$. Any such qubit can be represented as a Bloch vectorBloch vector
(cf. Appendix <ref>)

\begin{align}\label{eqn:georgios:bloch}
\bm R_j(\theta_n) = \cos ( k_j \theta_n) \sigma_z + \sin ( k_j \theta_n) \sigma_x,
\end{align}

with the Pauli operators $\sigma_z$ and $\sigma_x$. Therefore, each chosen bit of the private key $k_j$
results in a qubit that is in the state $\ket{\psi_{k_j} (\theta_n)}$, where the protocol defines the
angles to be equidistant and determined by

\begin{align}
\theta_n := \pi/2^{n-1}.
\end{align}

In other words, the public key is a representation of the private key, where each integer $k_j$ is represented by
the angle $\pi/2^{n-1}$ and implemented as a rotation of a qubit within the $z$-$x$-plane of the Bloch sphere as
can be seen in Figure <ref>. This mapping is also called a quantum one-way function,
where the probability is large to generate the quantum state from the private key and the probability is low
to reconstruct the private key perfectly from a single copy of the quantum state of the public key, if the initial
transformation is unknown.

[scale=0.85, transform shape]
[thick] (0,0) circle (3cm);

at (0,3.5) |0_x⟩;
at (0,-3.5) |1_x⟩;
at (3.5,0) |0_z⟩;
at (-3.5,0) |1_z⟩;

∠in 22.5, 45, ..., 360
[dashed, black, -latex] (0,0) – (xyz polar cs:angle=∠, radius=3);
[blue] (0,0) – (13mm, 0mm) arc (0:22.5:13mm) – cycle;
(10:11mm) node $\theta_n$;

For $n=4$, a single private key bit has one of $16$ different values, which is transformed into one of these $16$ equidistant
states of the corresponding public-key qubit within the  of the Bloch sphere.

Alice sends the copies of the public key directly to parties like Bob that want to send encrypted messages back to Alice.
Alice does not delegate the distribution to a so-called
key distribution center (KDC).[Such a KDC which
distributes public keys has to be unconditionally trusted.]
Bob may use one of those keys in order to encrypt a message
$\bm{m}$ which has a length of at most $N$ bits. For simplicity and w. l. o. g. we consider a message which
is exactly $N$ bit long, thus $\bm{m} = (m_1, \ldots, m_N)$.The encryption of the protocol is defined as
For each bit $m_j$ of the message with $j \in \MgE{N}$, apply the operator $\mathcal{E}_{m_j}$ to the qubit
$\ket{\psi_{k_j} (\theta_n)}$ of the public key, where this operator is given by

\begin{align}
\mathcal{E}_{m_j} = \mathcal{R}_y (m_j \pi),
\end{align}

with $\mathcal{R}_y(\alpha) = \EZ^{-\iE \alpha/2 \sigma_y}$ being a rotation around the $\sigma_y$-axis of the
Bloch sphere. A rotation is therefore applied to the original public key state, if the corresponding bit value of
the message is one and the original state is left untouched if the value equals zero, resulting in the (quantum) cipher

\begin{align}\label{eqn:georgios:cipher}
\ket{\bm X_{\bm k, \bm m} ( \theta_n)} = \bigotimes_{j=1}^N \mathcal{E}_{m_j} \ket{\psi_{k_j}(\theta_n)} = \bigotimes_{j=1}^N \ket{\chi_{k_j,m_j} (\theta_n)}.
\end{align}

In the last step, this cipher state is sent by Bob back to Alice who is able to undo the initial rotations and measure in
the Pauli-$\sigma_z$ basis. This part of the protocol reads as:

* Undo the initial rotations on the cipher state of Equation (<ref>):

\begin{align}
\ket{\bm M_{\bm m}} = \bigotimes_{j=1}^N \mathcal{R}_y^{-1} (k_j \theta_n) \ket{X_{k_j}(\theta_n)} = \bigotimes_{j=1}^N \ket{M_{m_j}}.
\end{align}

* Measure each qubit of the resulting state in the eigenbasis of the Pauli-$\sigma_z$ operator to
extract the sent message.

Finally, Alice has received the classical message from Bob.But conversely, if the cipher state is leaked to the
eavesdropper Eve, she may measure each qubit in a random basis and obtain already by this simple attack the correct
bit value of each message bit with a probability of $3/4$. To avoid similar attacks, Nikolopoulos introduced a second security

\begin{align}\label{eqn:georgios:s}
s \in \N^*.
\end{align}

In this generalization, each message bit $m_j$ is encoded first into an $s$-bit codeword $\bm w_j$ and subsequently
encrypted into $s$ qubits of the public key. Therefore, the public key needs to have at least $s$ times the length of
the message, again we concentrate for simplicity on the case that this ratio is given exactly. The codeword is chosen as follows:
If the message bit $m_j$ is zero, take a codeword $\bm w_j$ of length $s$ randomly from the set of codewords with even parity.
Appropriately, if the message bit $m_j$ equals zero, the codeword is randomly chosen from the set of codewords with odd parity.
In principle, the message is only extended by this procedure, so we can use the already defined steps of the protocol by applying the

\begin{align}\label{eqn:georgios:word}
m_j \rightarrow \bm{w}_j.
\end{align}

Nikolopoulos derived an upper bound [67], that limits the number of public keys Alice can distribute by keeping the
security of the private key against a powerful individual attack which is of interest in Section <ref>.
Discussions on a chosen-plaintext attack, a forward-search attack (cf. also [66]) and a
chosen-ciphertext were given by Nikolopoulos [67]. A very general attack on the private key as well as a powerful and more
direct attack on the encoded message by using the information of all distributed keys will be discussed in Chapter <ref>,
and leads to a limit for the number of public keys which may be distributed in order to achieve a certain security.

CHAPTER: SECURITY ANALYSIS

For the QPKE protocol presented in Section <ref>, different attacks were already
discussed by Nikolopolous and Ioannou [67, 66], but do not always benefit from the complete set
of available public keys. The aim of this chapter is to take advantage of the complete set and to
derive the strength of practical attacks. In Section <ref>, preliminary considerations will
be discussed.  For an asymmetric protocol, it is clear that the
security of the private key is the most important goal in order to guarantee the secrecy of the
communicated messages, as if it is broken, all messages which use that key will be leaked. In
Section <ref>, this security will be discussed. Direct attacks on the message will be investigated
subsequently in Section <ref>, where it will be shown that a certain individual attack[Individual
attacks denote attacks where the transmitted quantum systems are measured individually. Collective attacks denote attacks where
information about the quantum systems is collected, e. g. by entangling them to ancilla systems and measuring them after the protocol
is finished and information of post-processing protocols can be taken into account.] possesses
an almost equal strength as collective attacks.[The ideas discussed in those sections were published
in 2012 [81].]
Finally, in Section <ref>, a potential extension of the protocol will be considered
which uses a noisy-preprocessing step in order to reduce the information an eavesdropper may leak.
Obviously, this step influences considerably the setup of the scheme, but it is in principle a
generalization which takes partly the effect of noise into account.

§ PRELIMINARY CONSIDERATIONS

All values which refer to security issues of the protocol will be considered in the following in the case of a single run
of the protocol, meaning the information of a single bit which is transmitted. For reasons of simplicity, we will
omit the index $j$ which refers to the specific bit, in the following. In some cases, averages of quantities
will be taken into account, but in principle a message has a finite length and ensuring the security of a single
bit is a stronger constraint.To visualize this difference, let us compare the conditional probability of success of an eavesdropping strategy in both cases.
Within a single run of the protocol, values for the key $\key$ and the codeword $\word$ as defined in
Equations (<ref>) and (<ref>) are fixed, which lead to a mean probability of success
[Probabilities which are denoted in the following in general by $P(\suc \vert X)$, refer to the probability for an attacker
to eavesdrop successfully, given the event $X$. The abbreviation ““, meaning “success“, is chosen for a better readability.]
by averaging over all possible keys, namely

\begin{align}
\bar P (\suc \vert \word) = \sum_{\key} P(\key) P(\suc \vert \key, \word) = \frac{1}{2^{nN}} \sum_{\key} P ( \suc \vert \key, \word),
\end{align}

where the keys are uniformly distributed over the set $\Mg{0,1}^{nN}$. Additionally, an optimal eavesdropping strategy has to be symmetric
with respect to the codewords, as the value for a one-bit message is given by $m \in \Mg{0,1}$ with equal probability
and the conditional probability of obtaining the codeword $\word$ is $P(\word \vert m) = 2^{-(s-1)}$ (cf. Equation (<ref>)).
Thus the probability of any codeword to occur is given by

\begin{align}
P(\word) = \sum_m P(\word \vert m) / 2 = 2^{-s}.
\end{align}

§ SECURITY OF THE PRIVATE KEY

As given by the third step of the key generation part of the protocol which is introduced in Section <ref>,
$T'$ copies of the public key exist. According to Eve's chosen strategy, she may use for practical reasons $\tau < T'$ copies of the
public key.[If Eve wants to attack a message, already one key is consumed for the encryption; if her aim is to attack the
key, she may in principle use all $T'$ copies of the public key, but this knowledge does not help her to gain any profitably information.]
Obviously, she can obtain those keys directly from Alice, as they are publicly available. Without measuring
the state of these copies, she holds a priori a mixed quantum state, given by

\begin{align}
\rho_{\mathrm{prior}}^{(\tau)} =& \frac{1}{2^n} \sum_{k'=0}^{2^n-1} \left( \ketbra{\psi_{k'} (\theta_n)}{\psi_{k'} (\theta_n)} \right)^{\otimes \tau}\\
=& \frac{1}{2^n} \sum_{k'=0}^{2^n-1} \left( \ketbra{\bm{\phi}_{k'}^{(\tau)} (\theta_n)}{\bm{\phi}_{k'}^{(\tau)} (\theta_n)} \right),\label{eqn:prelim:rhoprior}
\end{align}

where we have abbreviated the $\tau$-qubit state as $\ket{\bm{\phi}_{k'}^{(\tau)} (\theta_n)} := \ket{\psi_{k'} (\theta_n)}^{\otimes \tau}$.
To bring Equation (<ref>) into a nice form, we can take advantage of the following consideration:
A possible basis for a single qubit is given by the set $\Mg{ \ket{0_z}, \ket{1_z} }$ of states, which are eigenstates of the Pauli-$\sigma_z$
operator. If we treat a tensor product of $\tau$ single qubits, the basis vectors are consequently given by the set

\begin{align}\label{eqn:privkey:basisi}
\Mg{\ket{i}: i \in \Z_{2^\tau}},
\end{align}

where $\ket{i}$ represents an eigenstate of the $\tau$-folded tensor product of Pauli-$\sigma_z$ operators $\sigma_z^{\otimes \tau}$.
Eve knows from the construction of the protocol, that these $\tau$ copies of the qubit (which individually represent the public key) are equal.
The state $\ket{\bm{\phi}_{k'}^{(\tau)} (\theta_n)}$ is therefore invariant under a permutation of the copies. Thus, a decomposition of that
state in the basis defined by Equation (<ref>) will have equal parameters in those terms, where the number of ones in the
string $i$ coincides. The state $\ket{\bm{\phi}_{k'}^{(\tau)} (\theta_n)}$ can then be represented by the basis

\begin{align}
\ket{l} = \left( \sum_{i=1}^{2^\tau} \delta_{l,H(i)} \ket{i} \right) /\sqrt{\binom{\tau}{l}},
\end{align}

where the Hamming weightHamming weight $H(i)$ is the number of ones in the string $i$. These
$\tau +1$ different states $\ket{l}$ (with $l \in \MgN{\tau}$) refer to subspaces of the $2^{\tau}$ dimensional Hilbert space.We can use this basis in order to reformulate the state of Equation (<ref>) with

\begin{align}
\ket{\bm{\phi}_{k'}^{(\tau)} (\theta_n)} = \sum_{l=0}^{\tau} \sqrt{\binom{\tau}{l}} f_{\tau,l} (k' \theta_n) \ket{l},
\end{align}

\begin{align}
f_{\tau,l} ( k' \theta_n) = \left( \cos \left(\frac{k' \theta_n}{2}\right) \right)^{\tau-l} \left( \sin \left(\frac{k' \theta_n}{2}\right) \right)^{l}.
\end{align}

Introducing the coefficients $C_{l,l'}$ with

\begin{align}
C_{l,l'} = \frac{1}{2^n} \sqrt{\binom{\tau}{l}\binom{\tau}{l'}} \sum_{k'=0}^{2^n-1} f_{\tau,l}(k' \theta_n) f^*_{\tau,l'}(k' \theta_n),
\end{align}

leads finally to

\begin{align}\label{eqn:privkey:rhopriorll}
\rho_{\mathrm{prior}}^{(\tau)} = \sum_{l,l'=0}^{\tau} C_{l,l'} \ketbra{l}{l'}.
\end{align}

We can use this form of the a priori state Eve may hold, in order to obtain an upper bound on the amount of information about the private key,
Eve may extract from the state $\rho_{\mathrm{prior}}^{(\tau)}$. Therefore, we need the Holevo quantityHolevo quantity $\chi$ which limits
the average amount of information $I_{\mathrm{av}}$ that can be extracted from an unknown state $\rho$. It is given by

\begin{align}
\chi = S(\rho) - \sum_k p_k S(\rho_k) \geq I_{\mathrm{av}},
\end{align}

where $S(\rho)$ denotes the usual von-Neumann entropy of a state $\rho$, where the system is in a mixed state with states $\rho_k$ and corresponding
probabilities $p_k$.[Discussions, derivations, and proofs on quantities of quantum information theory can be found in the book of
Nielsen and Chuang [65].] As seen in Equation (<ref>),
the $\tau$-qubit state $\rho_{\mathrm{prior}}^{(\tau)}$ can be expressed in terms of a $\tau+1$ dimensional Hilbert space, therefore, its von-Neumann
entropy is again upper bounded as[Simulations suggest that the eigenvalues of Equation (<ref>) are given by $\lambda_i = 2^{-\tau} \binom{\tau}{i}$.
Then $\rho_{\mathrm{prior}}^{(\tau)}$ would be the entropy of a binomial distribution with mean $\tau/2$ and variance $\tau/4$ and upper bounded by the
Gaussian distribution; this would lead to a lower upper bound of $I_{\mathrm{av}}$,
namely, $I_{\mathrm{av}} \leq S(\rho_{\mathrm{prior}}^{(\tau)}) \leq \frac{1}{2} \log_2 \tau + \frac{1}{2}\log_2 (\pi \EZ /2)$.]

\begin{align}
I_{\mathrm{av}} \leq \chi \leq S(\rho_{\mathrm{prior}}^{(\tau)}) \leq \log_2 (\tau+1).
\end{align}

By the construction of the private key and the resulting public key as given in Section <ref>, the state of the public key is in one
of $2^n$ different states, which means that this key is secure, as long as the information Eve may gain from her measurements is much smaller
than the number of bits which describe the information, namely, as long as

\begin{align}
n \gg \log_2 (\tau+1)
\end{align}

holds. As in principle $T'$ copies of the public key exist and at least one is consumed to encrypt a message, this limit reads in terms of $T'=\tau+1$ as

\begin{align}\label{eqn:privkey:nlimit}
n \gg \log_2 (T').
\end{align}

With the help of this limitation, the security of the private key can be guaranteed. Nevertheless, direct attacks on the message
are possible and will be discussed in Section <ref>.

§ SECURITY OF A MESSAGE

The security of the sent message in the protocol of Nikolopoulos relies essentially on the
security of the private key that can be guaranteed according to the
limitations given in Equation (<ref>). Thus, if the private key can be reconstructed
perfectly, a potential eavesdropper Eve may use this information in order to obtain messages which are
sent with this key. But as the mentioned limitation should be achieved by construction, the optimal
strategy for Eve may be different. Instead of recovering the private key perfectly, she may recover the
key approximately. As the private key is in one-to-one correspondence to the public key, we can easily
discuss this issue in terms of the public key. Let us assume first that
Eve manages to receive $T'-1$ copies of the public key as well as an encrypted message which uses
the same key. Since the integers of the corresponding private key are chosen individually
and uniformly distributed, we are free to consider a single-bit message.The strategy of Eve is
then to estimate the state of the public-key qubits, by taking into account that each qubit is prepared in
a state which lies on the $z$-$x$ plane of the Bloch sphere (cf. Appendix <ref>). The security parameter $s$, which was
introduced in Equation (<ref>), requires an $s$-bit codeword, which encodes
a bit of the message and is subsequently encrypted into $s$ qubits of the public key. At first, we will
consider Eve's attack on a single qubit, which encodes only a single bit of the codeword $\word$ and finally
generalize this approach on the complete ciphertext of the codeword. As already seen in Part <ref>
of this work, an optimal choice to estimate an unknown state with a minimal number of single-qubit measurements
is realized by using mutually unbiased basesMutually unbiased bases. Taking the limitation to the $z$-$x$ plane of the
Bloch sphere into account, Eve's best measurement strategy is to use the eigenbases of the Pauli-$\sigma_z$ and
Pauli-$\sigma_x$ operators equally often. To simplify matters, we assume that the number of distributed
keys is given by

\begin{align}
T' = 2 T + 1.
\end{align}

This results in an estimation of the public key and defines an estimation of the basis that was used to
encrypt the message. If Eve uses this basis estimation to measure the ciphertext, the fidelity of the
basis which results from the private key and the estimation of the bases gives the success probability of
Eve's attack.Eve can apply the two different experiments (measuring in the eigenbasis of the Pauli-$\sigma_z$ or the
Pauli-$\sigma_x$ operator, respectively) and will receive either the measurement outcome zero or one.
This outcome depends in average on the expectation value which is given by testing $\ket{0_z}$ on the single-qubit state
$\ket{\psi_{k} (\theta_n)}$, that is introduced in Equation (<ref>), namely

\begin{align}
\braket{\psi_{k} (\theta_n)}{0_z}\braket{0_z}{\psi_{k} (\theta_n)},
\end{align}

which yields the probability

\begin{align}\label{eqn:message:p0z}
p_0^{(z)}(k) = \cos^2 \left(\frac{k \theta_n}{2}\right),
\end{align}

to measure a zero in the eigenbasis of the $\sigma_z$ operator. To measure a zero in the eigenbasis of the
$\sigma_x$ operator, we find accordingly

\begin{align}\label{eqn:message:p0x}
p_0^{(x)}(k) = \cos^2 \left(\frac{\pi}{4}-\frac{k \theta_n}{2}\right).
\end{align}

In both cases, the probabilities to measure a one are obviously given by $p_1^{(z)}(k) = 1 -p_0^{(z)}(k)$ and
$p_1^{(x)}(k) = 1 -p_0^{(x)}(k)$, respectively. If we denote the number of outcomes of a zero in the eigenbasis
of the $\sigma_z$ operator, by $T_0^{(z)}$ and the number of outcomes of a zero in the eigenbasis of the
$\sigma_x$ operator, by $T_0^{(x)}$, Eve's attack leads to one out of $(T+1)^2$ ordered pairs $\left(T_0^{(z)}, T_0^{(x)}\right)$.

§.§ Information about the public key

In a first step, this special attack yields information about the public key (and therefore about the private key).
The a posteriori probability for Eve to guess a certain bit value $k'$ with the help of the
ordered pair $\left(T_0^{(z)}, T_0^{(x)}\right)$ is given by Bayes law as

\begin{align}\label{eqn:message:aposteriori}
p(k' \vert T_0^{(z)}, T_0^{(x)}) = \frac{p(T_0^{(z)}, T_0^{(x)}\vert k')}{2^n p(T_0^{(z)}, T_0^{(x)})}.
\end{align}

To calculate the a priori probability of the right hand side of this expression, we can use the quantities
defined in Equation (<ref>) and (<ref>), keeping in mind all possible permutations
of the measurement outcomes, which leads to

\begin{align}\label{eqn:message:apriori}
p(T_0^{(z)}, T_0^{(x)}\vert k') = \prod_{b \in \Mg{z,x}} \binom{T}{T_0^{(b)}} \left( p_0^{(b)}(k') \right)^{T_0^{(b)}} \left( p_1^{(b)}(k') \right)^{T-T_0^{(b)}}.
\end{align}

The probability for Eve to obtain a certain ordered pair $\left(T_0^{(z)}, T_0^{(x)}\right)$ independently of the private-key state
is given by the sum of the a priory probability over all possible values of $k'$, namely

\begin{align}
p(T_0^{(z)}, T_0^{(x)}) = \frac{1}{2^n} \sum_{k'=0}^{2^n-1} p(T_0^{(z)}, T_0^{(x)}\vert k').
\end{align}

The information which Eve can accumulate in average by evaluating the discussed measurement outcome is given by
the difference of the Shannon entropies before and after the measurements, thus,

\begin{align}
I_{\mathrm{av}} =& H_{\mathrm{prior}} - \langle H_{\mathrm{post}} \rangle\\
=& n + \sum_{T_0^{(z)}, T_0^{(x)}} p(T_0^{(z)}, T_0^{(x)}) \sum_{k'=0}^{2^n-1} p(k' \vert T_0^{(z)}, T_0^{(x)}) \log_2 p(k' \vert T_0^{(z)}, T_0^{(x)}).
\end{align}

As the a priori state is uniformly distributed and can be described by $n$ bits, the corresponding a priori
entropy is given by $n$.

§.§ Information about the message

Alternatively, the measurement outcome $\left(T_0^{(z)}, T_0^{(x)}\right)$ can be used by Alice to estimate the public-key state.
With the help of the a posteriori probability, that a certain value $k$ may have been the private key, as it
was introduced in Equation (<ref>), we can formulate the a posteriori state which Eve has
after the measurement, taking all possible values for $k$ into account. This $\tau$-qubit state is given by

\begin{align}
\rho_{\mathrm{post}}^{(\tau)}(T_0^{(z)}, T_0^{(x)}) = \sum_{k'=0}^{2^n-1} p(k' \vert T_0^{(z)}, T_0^{(x)}) \ketbra{\bm{\phi}_{k'}^{(\tau)} (\theta_n)}{\bm{\phi}_{k'}^{(\tau)} (\theta_n)}.
\end{align}

Although Eve intercepted $\tau$ raw copies of the public key, she is only interested in a single-qubit state, which can be
obtained by tracing out $\tau-1$ states and results in

\begin{align}
\rho_{\mathrm{post}}^{(1)}(T_0^{(z)}, T_0^{(x)}) = \sum_{k'=0}^{2^n-1} p(k' \vert T_0^{(z)}, T_0^{(x)}) \ketbra{\psi_{k'} (\theta_n)}{\psi_{k'} (\theta_n)}.
\end{align}

Analogously to Equation (<ref>) we can represent the single-qubit a posteriori state by the Bloch vector (cf. Equation <ref>)

\begin{align}
\tilde {\bm R} = \sum_{k'=0}^{2^n-1} p(k' \vert T_0^{(z)}, T_0^{(x)}) (\cos (k' \theta_n) \sigma_z + \sin (k' \theta_n) \sigma_x),
\end{align}

where this vector represents in general a mixed state and has therefore a length which is given by $\vert \tilde{\bm R} \vert \leq 1$.In principle, we may compare this estimated Bloch vector now with the original Bloch vector and calculate the probability that both
coincide. However, we have to call back into mind, that a single bit is encoded by an $s$-bit codeword $\word$ and subsequently encrypted
into $s$ qubits defining the security parameter that was formulated in Equation (<ref>). Following this construction, the first
step is to calculate the probability that Eve correctly estimates the bit $w_j$ of the codeword $\word = \Mg{1,\ldots, s}$, which is given

\begin{align}
P(\suc \vert w_j,k, T_0^{(z)}, T_0^{(x)}) = \cos^2 (\Omega_j/2),
\end{align}

where $\Omega_j$ denotes the angle between the two Bloch vectors $\tilde{\bm R_j}$ and ${\bm R_j}$ and the index $j$ refers to
the qubit that encrypts the bit $w_j$. Solving this approach leads to the expression

\begin{align}
P(\suc \vert w_j,k, T_0^{(z)}, T_0^{(x)}) = \frac{1}{2} + \frac{\tilde{\bm R_j} \cdot \bm R_j}{2 \vert \tilde{\bm R_j} \vert},
\end{align}

with the scalar product

\begin{align}
\tilde{\bm R_j} \cdot \bm R_j = \sum_{k'=0}^{2^n-1} p(k' \vert T_0^{(z)}, T_0^{(x)}) \cos ((k' -k) \theta_n).
\end{align}

The ordered pair $\left(T_0^{(z)}, T_0^{(x)}\right)$ is an output of the measurements by Eve which is not observed by Alice. A more
meaningful quantity is therefore given by

Conditional probability $P(\suc\vert w_j,k)$ that Eve successfully attacks the public key for $n=10$ and different values of $T$.

\begin{align}
P(\suc \vert w_j, k) = \sum_{T_0^{(z)}, T_0^{(x)}} P(\suc, w_j,k, T_0^{(z)}, T_0^{(x)}) p(T_0^{(z)}, T_0^{(x)} \vert k)
\end{align}

and visualized in Figure <ref> for different values of $T$. Plotted against the key value $\key$, the
probability shows an oscillatory behavior around its mean value, with decreasing amplitude for a larger number of available copies.
The mean value can be calculated as

\begin{align}\label{eqn:message:psuc_wj}
\bar P (\suc \vert w_j) = \frac{1}{2^n} \sum_{k=0}^{2^n-1} P(\suc \vert w_j, k)
\end{align}

and scales for $T>1$ like

\begin{align}\label{eqn:message:psuc_wj_bound}
\bar P (\suc \vert w_j) \lesssim 1 - \frac{1}{6T},
\end{align}

which is given together with the optimal probability that is discussed below, in Figure <ref>.

Conditional probability $\bar P (\suc \vert w_j)$ that Eve successfully attacks the message for $n=10$ for the discussed attack,
the asymptotic behavior of this attack and the optimal collective attack [24], plotted against $T$.

The comparison with the optimal probability of successfully estimating the prepared state which takes advantage of
a collective measurement method (and is therefore harder to get implemented) shows the good performance of this approach,
where this optimal probability is given by [24]

\begin{align}
\bar P_{\mathrm{opt}} (\suc \vert w_j) = \frac{1}{2}+ \frac{1}{2^{2T+1}} \sum_{i=0}^{2T-1}\sqrt{\binom{2T}{i} \binom{2T}{i+1}},
\end{align}

and scales as

\begin{align}
\bar P_{\mathrm{opt}} (\suc \vert w_j) \sim 1- \frac{1}{8T}.
\end{align}

Even this scaling can be reached by measurements on individual qubits, as it was shown by Bagan  [6] with
an attack which is similar to the discussed one. Contrary to the attack given in [66], the probability of success does
not depend on the value $w_j$ and can be implemented using only measurement devices instead of the more complicated quantum
operations which are used in the mentioned approach.Hence, we are well prepared to discuss the final step of this attack, namely considering the probability of correctly guessing
the message bit $m$. As seen in Section <ref>, the bit $m$ is encoded into the parity of an $s$-bit codeword $\bm w$,
where all appropriate codewords are equally probable. As seen in Equation (<ref>), Eve has a certain probability
for each bit of the codeword to succeed. But even though, namely in cases where Eve fails an even number of times to predict the
correct value of a bit $w_j$ of the codeword, the parity she gets results in the same and therefore correct message bit $m$. Additionally,
as we have already seen in Figure <ref>, the amplitude of the oscillation of the success probability becomes
negligible for large values of $T$, at least it is an order of magnitude smaller than the mean. Therefore, we
will not gain a much better notion by observing the mean value of the success probability, as it should be comparable to the results
within a single-run experiment. Following the structure of the codeword, Eve has a mean probability of success, given a certain codeword
and a certain message bit,

\begin{align}\label{eqn:message:pssuc_mw}
\bar P_s (\suc \vert m, \word) = \sum_{\substack{\alpha = 0,\\\mathrm{even}}}^s \binom{s}{\alpha} (1-\bar P(\suc \vert w_j))^{\alpha} (\bar P(\suc \vert w_j))^{s-\alpha},
\end{align}

where $\alpha$ denotes the number of incorrectly estimated bits of the codeword. Since this value does not depend on the message
bit and all codewords have the same probability, we finally find

\begin{align}
\bar P_s (\suc) = \bar P_s (\suc \vert m, \word).
\end{align}

Within Figure <ref> we show the behavior of this probability for different values of $T$ against the security parameter $s$.

Conditional probability $\bar P_s (\suc \vert m, \word)$ that Eve successfully attacks the message for $n=10$ and different values of $T$,
plotted against the security parameter $s$. The solid lines refer to the exact results of Equation (<ref>) and the dashed lines to the
upper bound given by Equation (<ref>).

As expected, this parameter produces a monotonic decrease in the success probability of Eve and can be tightly upper bounded with the help
of the following lemma that can be used in order to generalize Equation (<ref>).

If the probability (or an upper bound) of successfully eavesdropping a single-bit message encoded by a codeword of length $s=1$ is given by

\begin{align}\label{eqn:message:q1}
Q^{(1)} = \frac{1}{2} + \frac{\lambda}{2},
\end{align}

with $\lambda \in \C$, the corresponding quantity for a single-bit message, encoded by an $s$-bit codeword, such that
the parity of the codeword equals the message bit and all possible codewords are equally probable, is given by

\begin{align}\label{eqn:message:qs}
Q^{(s)} = \frac{1}{2} + \frac{\lambda^s}{2}.
\end{align}

As an even number of wrong results in the attack leads to a correct estimate of the parity of the codeword which represents the sent message, a
generalization of Equation (<ref>) to a codeword of length $s$ is given by

\begin{align}
Q^{(s)} = \sum_{\substack{\alpha = 0,\\\mathrm{even}}}^s  \binom{s}{\alpha} ( 1- Q^{(1)})^{\alpha} ( Q^{(1)})^{s-\alpha}.
\end{align}

Alternatively, this generalization can also be written iteratively as

\begin{align}
Q^{(s)} =  Q^{(1)}Q^{(s-1)} + (1-Q^{(1)})(1-Q^{(s-1)}).
\end{align}

If for $Q^{(1)}$ Equation (<ref>) holds and we assume that also Equation (<ref>) is given, we find
for $Q^{(s+1)}$, using the iterative construction,

\begin{align}
Q^{(s+1)} =& \left( \frac{1}{2} + \frac{1}{2} \right) \left( \frac{1}{2} + \frac{\lambda^s}{2} \right) + \left( \frac{1}{2} - \frac{1}{2} \right) \left( \frac{1}{2} - \frac{\lambda^s}{2} \right)\\
=& \left( \frac{1}{2} + \frac{\lambda^{s+1}}{2} \right),
\end{align}

which completes the induction and provides the expected result.

If we set $Q^{(1)}$ to the value of Equation (<ref>), we can use Lemma <ref>
with $\lambda = 1- 1/(3T)$ and get finally a generalized upper bound for the correct guessing of the message[The message is encoded to the
parity of an $s$-bit codeword as introduced in Section <ref>.] by

\begin{align}\label{eqn:message:pssuc_mw_bound}
Q^{(s)} := \tilde P_s (\suc) = \frac{1}{2} + \frac{1}{2} \left( 1- \frac{1}{3T} \right)^s.
\end{align}

Finally, to achieve a security against the introduced attack, we have to show that for any small positive
value $\varepsilon \in (0,1/2]$, we find a finite value of the security parameter $s$, such that the probability
of successfully estimating goes below the sum of the probability of randomly guessing with that value.
This notion of security is also known as asymptotic security
Asymptotic security. Thus, to find a security parameter which fulfills $\bar P_s (\suc) < 1/2 + \varepsilon$,
we find, using Equation (<ref>),

\begin{align}
s > \frac{1+\log_2 \varepsilon}{\log_2 \left(1- \frac{1}{3T} \right)},
\end{align}

which is also fulfilled if there holds

\begin{align}\label{eqn:message:slimitbound}
s > 3T (1+\log_2 \varepsilon).
\end{align}

This easily implementable attack is stronger than the forward-search attackForward-search attack which was already discussed in the
original work of the protocol [67, 66] and uses complicated quantum operations as Fourier transformations
and permutations on large sets of qubits. Similarly to Equation (<ref>), an upper bound
for its probability of successfully eavesdropping (which does not vary from run to run) is given by [66]

\begin{align}\label{eqn:message:sFSlimit}
\tilde P_s^{\mathrm{FS}} (\suc) = \frac{1}{2} + \frac{1}{2} \left( 1- \frac{1}{2T} \right)^s.
\end{align}

The success probability of that attack leads to a lower bound for the security parameter in the notion of Equation (<ref>) as

\begin{align}\label{eqn:message:sFSlimitbound}
s^{\mathrm{FS}} > 2T (1+\log_2 \varepsilon),
\end{align}

and differs only by a factor of $2/3$ with the new investigated attack.[The differences of Equations (<ref>) and
(<ref>) with their counterparts in [66] are due to the fact that within the attack discussed here, $T$ is defined to refer
to the half of the number of keys which are used in order to attack the encrypted message. The missing factor of two in <cit.>, comparing
to Equation (<ref>), is based on a misprint.]

§ NOISY PREPROCESSING

In order to increase the robustness of the protocol discussed in Section <ref> against
various attacks like those investigated in Sections <ref> and <ref> and
potentially others, we show in the following exemplarily the behavior of a modified protocol against
two simple attacks. Conversely to the original key-generation Step <ref> of the protocol,
we assume that the states are not taken from the $z$-$x$-plane of the Bloch sphere. One may think of
an affine plane which would imply states on a certain degree of latitude, areas on the surface which are
limited by two degrees of latitude, or even the complete surface of the sphere. Obviously, as we like
to leave the measurement process untouched, post-processing (namely error correction) steps will
be obligatory. Even within the original protocol they have to be added in order to get a practical implementation,
as errors in quantum states will always occur. Possibly, the introduced steps may help in order to model
the influence of errors in the original protocol. Nevertheless, as this consideration is based on two simple attacks,
the results can only be seen as limited, but indicate the positive behavior and motivate a subsequent

§.§ Single-key test attack

The first attack we use in order to compare a notion of the security of the original protocol with the
security of the modified protocol is in principle a single-copy version of the attack, which was discussed
in Section <ref> and published in the same work [81]. If Eve intercepts a ciphertext and
a corresponding copy of the public key, she can attack the message bitwise by a simple experiment. For each
bit of the codeword $\word$ as introduced in Section <ref>, she measures both corresponding
qubits in the same, but in principle arbitrary basis within the $z$-$x$-plane, which leads to a success probability similar to that of
Equation (<ref>). As rotations of the measurement axis around the $\sigma_y$ axis lead only to a constant term in the
argument of the $\cos^2$ and the possible states are arranged symmetrically with even probabilities, the success
probability is independent of the chosen axis for a random chosen public key bit, so we will take the $\sigma_z$ axis
and have

\begin{align}\label{eqn:prepro:p0}
p_0(k) = \cos^2 \left(\frac{ k \theta_n}{2} \right),
\end{align}