# Optimal exact quantum algorithm for the promised element distinctness
problem

Guanzhong Li and Lvzhou Li
Institute of Quantum Computing and Computer Theory,
School of Computer Science and Engineering,
Sun Yat-sen University, Guangzhou 510006, China Email:
<EMAIL_ADDRESS><EMAIL_ADDRESS>(corresponding author)

###### Abstract

The element distinctness problem is to determine whether a string
$x=(x_{1},\ldots,x_{N})$ of $N$ elements contains two elements of the same
value (a.k.a colliding pair), for which Ambainis proposed an optimal quantum
algorithm. The idea behind Ambainis’ algorithm is to first reduce the problem
to the promised version in which $x$ is promised to contain at most one
colliding pair, and then design an algorithm $\mathcal{A}$ requiring
$O(N^{2/3})$ queries based on quantum walk search for the promise problem.
However, $\mathcal{A}$ is probabilistic and may fail to give the right answer.
We thus, in this work, design an exact quantum algorithm for the promise
problem which never errs and requires $O(N^{2/3})$ queries. This algorithm is
proved optimal. Technically, we modify the quantum walk search operator on
quasi-Johnson graph to have arbitrary phases, and then use Jordan’s lemma as
the analyzing tool to reduce the quantum walk search operator to the
generalized Grover’s operator. This allows us to utilize the recently proposed
fixed-axis-rotation (FXR) method for exact quantum search, and hence achieve
100% success.

##  1 Introduction

In the element distinctness problem, we are given a black box (oracle) $O_{x}$
that when queried index $i$ of the unknown string
$x=(x_{1},x_{2},\ldots,x_{N})\in[M]^{N}$, where $[M]=\\{1,2,\ldots,M\\}$ and
$M\geq N$, it outputs the value $x_{i}$. The task now is to determine whether
the string $x$ contains two equal items $x_{i}=x_{j}$ (called the colliding
pair), with as few queries to the index oracle $O_{x}$ as possible. The
problem is well-known both in classical and quantum computation. The classical
bounded-error query complexity (a.k.a decision tree complexity, see [1] for
more information) is shown to be $\Theta(N)$ by a trivial reduction from the
OR-problem [2]. In comparison, Ambainis proposed a $O(N^{2/3})$-query quantum
algorithm with bounded-error [3, 4]. The algorithm is also optimal: the
bounded-error quantum query complexity of the element distinctness problem has
previously been shown to be $\Omega(N^{2/3})$ [5, 6, 7] by the polynomial
method [8].

In [3, 4], Ambainis first designed a $O(N^{2/3})$-query quantum algorithm
$\mathcal{A}$ which solves the promised version in which $x$ contains at most
one colliding pair, by using quantum walk search on Johnson graph. He then
reduced the problem to this promised version, by sampling a sequence of
exponentially shrinking subsets to run $\mathcal{A}$. By showing the
probability that the sequence has a subset containing at most one colliding
pair is greater than $1/2$ and the overall query complexity is of the same
order, Ambainis successfully solved the element distinctness problem with
query complexity $O(N^{2/3})$. This two-stage process shows the promise
problem that the algorithm $\mathcal{A}$ solves is crucial, and we formalize
it in the following:

Problem 1: element distinctness problem with at most one colliding pair input:
index oracle $O_{x}$ hiding the unknown string
$x=(x_{1},x_{2},\ldots,x_{N})\in[M]^{N}$. promise: $x$ contains exactly one
colliding pair $x_{i}=x_{j}$ with $i\neq j$; or $x_{i}$s are distinct for
$i\in[N]$. output: index $(i,j)$ of the colliding pair $x_{i}=x_{j}$; or “all
distinct”.

In fact, $\mathcal{A}$ is a one-sided error algorithm: if the string $x$
contains a colliding pair $x_{i}=x_{j}$, then $\mathcal{A}$ might asserts that
$x$ is “all distinct”; but if elements in $x$ are all distinct, then
$\mathcal{A}$ won’t make a mistake. This inspires us to consider the question:
is there an exact quantum algorithm that solves Problem 1 with the same query
complexity $O(N^{2/3})$? In this paper, we answer the question affirmatively
by presenting Algorithm 1 in Section 2. We summarize our result as:

######  Theorem 1.

There exits an exact quantum algorithm that solves Problem 1 with query
complexity $O(N^{2/3})$.

The main steps of Algorithm 1 is as follows:

  1. 1.

Converting Problem 1 to quantum walk search on a quasi-Johnson graph $G$
(using the staggered model [9]). This is done in Section 2.1 similar to [10,
11], but we modify the quantum walk operator
$u:=U_{B}(\theta_{2})U_{A}(\theta_{1})$ and the operator $R_{T}(\alpha)$ which
marks the target vertices by multiplying them by the phase $e^{i\alpha}$, so
that the angle parameters $\theta_{1},\theta_{2},\alpha$ are no longer
restricted to $\pi$. The flexibility in setting these angle parameters offers
an opportunity to design an exact algorithm.

  2. 2.

Reducing quantum walk search on the whole graph $G$ to its $5$-dimensional
invariant subspace $\mathcal{H}_{0}$, by classifying the vertices of $G$, i.e.
$(r+1)$-sized subsets $(S,y)$ of string $x$’s indices $[N]$, into $5$ groups
according to the $5$ different cases in which subset $(S,y)$ intersect with
the colliding pair. This is presented in Section 3.1, where we also obtain the
expression of $U_{B}(\theta_{2})$ and $U_{A}(\theta_{1})$ in
$\mathcal{H}_{0}$.

  3. 3.

Reducing further the $5$-dimensional subspace of quantum walk search to the
$2$-dimensional qubit subspace
$\mathcal{H}_{1}:=\text{span}\\{\ket{\psi_{0}},\ket{T}\\}$. This part (shown
in Section 3.2) is the core of this paper with quite some technique, and we
elaborate it in the following steps:

    1. (i)

Based on Jordan’s Lemma [12], we decompose the quantum walk operator
$u=U_{B}(\theta_{2})U_{A}(\theta_{1})$ to the direct sum of a scalar-
multiplication in the $1$-dimensional invariant subspace spanned by initial
state $\ket{\psi_{0}}$, and two 3D-rotations on two different Bloch spheres
(two $2$-dimensional invariant subspaces).

    2. (ii)

Based on the special rotation angles $\phi_{1},\phi_{2}$ of the two
3D-rotations obtained in step (i), and the intuition of the minute hand (the
bigger angle $\phi_{2}$) catching up with the hour hand ($\phi_{1}$) on a
watch, we devise the equations [Eq. (12)] that the iteration number $ct_{2}$
of $u=U_{B}(\theta_{2})U_{A}(\theta_{1})$ and the two fixed angles
$\theta_{1},\theta_{2}$ therein should satisfy, so that the effect of
$u^{ct_{2}}$ on the two Bloch spheres both become the identity transformation.
The overall effect of $u^{ct_{2}}$ in $\mathcal{H}_{0}$ thus becomes a phase
rotation about the initial state: $e^{-i\beta\ket{\psi_{0}}\bra{\psi_{0}}}$,
where $\beta$ is some fixed angle to be determined in the next step.

    3. (iii)

With some detailed analysis (Lemma 2) on Eq. (12), we show that it posses
solutions $\theta_{1},\theta_{2}$ when $ct_{2}$ is set according to Eq. (11),
so that the intuition in step (ii) really works.

By step (ii), we have actually obtained the $2$-dimensional invariant subspace
$\mathcal{H}_{1}=\text{span}\\{\ket{\psi_{0}},\ket{T}\\}$ of the quantum walk
search iteration
$u^{ct_{2}}R_{T}(\alpha)=e^{-i\beta\ket{\psi_{0}}\bra{\psi_{0}}}e^{i\alpha\ket{T}\bra{T}}=:S_{r}(\beta)S_{o}(\alpha)$,
which is the generalized Grover’s iteration $G(\alpha,\beta)$.

  4. 4.

We use the fixed-axis-rotation (FXR) method [13], in Section 3.3, to obtain
the appropriate parameters $\alpha_{1},\alpha_{2}$ of rotation
$F_{xr,\beta}:=G(\alpha_{2},\beta)G(\alpha_{1},\beta)$ and its iteration
number $t_{1}$ [see Eqs. (13)-(15)], such that applying $F_{xr,\beta}^{t_{1}}$
to the initial state $\ket{\psi_{0}}$ produces precisely the target state
$\ket{T}$.

Problem 1 has also been studied by Portugal in [10, 11], where he improves the
success probability of Algorithm $\mathcal{A}$ from constant to
$1-O(N^{1/3})$, quickly approaching $1$, by careful analysis on the asymptotic
behaviours of eigenvalues and eigenvectors of the quantum walk iterations
$[(U_{B}(\pi)U_{A}(\pi))^{t_{2}}R_{T}(\pi)]^{t_{1}}$ when $N\to\infty$, and by
setting the optimal iteration numbers $t_{1},t_{2}$. However, asymptotic
behaviours are not enough to design an exact algorithm. Therefore in step 3 to
determine the effect of $u^{ct_{2}}$, we use Jordan’s Lemma [12] about common
invariant subspaces of two reflections instead. Note that in our case we
consider ‘reflections’ with partial phase $\theta\neq\pi$. Jordan’s Lemma has
been widely used in the literature, such as the spectral lemma of quantum walk
operator based on Markov chain [14], spectral decomposition of interpolated
quantum walk operator [15], and the qubitization technique in quantum singular
value transformation [16].

The promise in Problem 1 that there is at most one colliding pair is in some
sense necessary to design a fast and exact quantum algorithm, because without
any promise on the number of equal elements in $x$, the deterministic quantum
query complexity will be $\Omega(N)$. In fact, we can first reduce the problem
of calculating the Boolean function $OR(y),\ y\in\\{0,1\\}^{N}$ to the element
distinctness problem of a specific string $x\in\\{0,1,\ldots,N\\}^{N+1}$ such
that $x_{i}=(1-y_{i})i,\forall i\in[N]$ and $x_{N+1}=0$ [2]. Then $OR(y)=1$ if
and only if $x$ contains a colliding pair. This reduction tells us that the
query complexity of the element distinctness problem must be greater than that
of calculating the Boolean function $OR$. Secondly, the deterministic quantum
query complexity of calculating $OR$ on the domain $\\{0,1\\}^{N}$ is shown to
be $N$ by the polynomial method [8]. Therefore, any exact quantum algorithm
solving the element distinctness problem without any promise on the number of
colliding pairs must query the index oracle $O_{x}$ for $\Omega(N)$ times.

On the other hand, the deterministic quantum query complexity of Problem 1 is
$\Omega(N^{2/3})$, so that the $O(N^{2/3})$ in Theorem 1 is actually
$\Theta(N^{2/3})$! Note, however, that the aforementioned $\Omega(N^{2/3})$
bounded-error quantum query complexity of the general element distinctness
problem by the polynomial method does not imply the $\Omega(N^{2/3})$ lower
bound of Problem 1, because the promised version is easier than the general
version and thus the query lower bound smaller. Nevertheless, we can use the
adversary method instead, because the negative-weight adversary lower bound
[17] of the decision version of Problem 1 has been proved to be
$\Omega(N^{2/3})$ [18, 19]. For completeness, we describe the proof of the
$\Omega(N^{2/3})$ lower bound of Problem 1 in Section 3.4.

##  2 Description of the algorithm

In this section, we present an exact quantum algorithm for Problem 1 (see
Algorithm 1).

###  2.1 Converting to quantum walk search on quasi-Johnson graph

The quasi-Johnson graph $G$ underlying Algorithm 1 has vertex set
$V=\\{(S,y):S\in S_{r},\ y\in[N]\setminus S\\}$, where $S_{r}$ consists of all
the $r$-sized subsets of $[N]$. Index $y$ can be seen as the index to be
swapped into $S$ in one step of quantum walk. $r$ is set to be

$r=\lfloor N^{{2}/{3}}\rfloor.$ (1)

An edge in $G$ connects two different vertices $(S,y)$ and
$(S^{\prime},y^{\prime})$ if and only if $S=S^{\prime}$ or
$S\cup\\{y\\}=S^{\prime}\cup\\{y^{\prime}\\}$. Note that
$|V|=\binom{N}{r}(N-r)$, which is not equal to $\binom{N}{r+1}$. Thus $G$ is
not a real Johnson graph, whose edges connect two vertices, i.e. $(r+1)$-sized
subsets, if and only if they differ in exactly one element.

Every vertex is equipped with $r+1$ slots of size $M$ to store the item values
in string $x$ corresponding to the index set $S\cup\\{y\\}$. Thus the basis of
the two working registers is of the following form:

$\ket{S,y}\otimes\ket{x^{\prime}_{1},x^{\prime}_{2},\ldots,x^{\prime}_{r+1}}.$

Suppose we store the value $x^{\prime}_{i}$ with $m$ qubits ($2^{m}\geq M$).
Then the effect of the index oracle $O_{x}$ is

$O_{x}\ket{i}\ket{b}=\ket{i}\ket{b\oplus x_{i}},$ (2)

where $i\in[N]$ is the querying index, and $\oplus$ is bit-wise XOR on $m$
qubits. Thus $O^{2}=I$.

As vertex basis $\ket{S,y}\in\mathbb{C}^{\binom{N}{r}}\otimes\mathbb{C}^{N-r}$
encodes the index set $S\cup\\{y\\}$, we will need a quantum subroutine
$\mathcal{P}$ to obtain the ascending index sequence
$(i_{1},i_{2},\ldots,i_{r})$ corresponding to $S$, and the true index
$\bar{y}\in[N]$ corresponding to $y$, so as to query the index oracle $O_{x}$.
To be more precise,

$\mathcal{P}:\ket{S,y}\otimes\ket{b_{1}}\cdots\ket{b_{r}}\ket{b^{\prime}}\mapsto\ket{S,y}\otimes\ket{b_{1}\oplus
i_{1}}\cdots\ket{b_{r}\oplus i_{r}}\ket{b^{\prime}\oplus\bar{y}}.$ (3)

Note that $\mathcal{P}^{2}=I$. The decoding procedure $\mathcal{P}$ might take
a lot of space, but as we are only considering query complexity, this is not a
problem.

The edge set of graph $G$ is actually determined by the two local diffusion
operator $U_{A}(\theta_{1})$ and $U_{B}(\theta_{2})$, as the edges indicate
the transiting restriction among vertices in a step of quantum walk
$u=U_{B}(\theta_{2})U_{A}(\theta_{1})$. Operator $U_{A}(\theta_{1})$ is
defined as

$U_{A}(\theta_{1})=I-(1-e^{i\theta_{1}})\sum_{S\in
S_{r}}\ket{A_{S}}\bra{A_{S}},$ (4)

where

$\ket{A_{S}}=\frac{1}{\sqrt{N-r}}\sum_{y\in[N]\setminus y}\ket{S,y}$ (5)

is an equal-superposition of the clique $A_{S}=\\{(S,y)\in V:y\in[N]\setminus
S\\}$ determined by $S$. Note that $|A_{s}|=N-r$ and there are $\binom{N}{r}$
cliques of this kind. From the definition of $U_{A}(\theta_{1})$, we know that
it transits a vertex to a superposition of vertices in the same clique, but
never to vertex in other clique. Therefore, $U_{A}(\theta_{1})$ corresponds to
applying Grover diffusion operator in every clique $A_{S}$.

The other diffusion operator $U_{B}(\theta_{2})$ is the combined effect of
steps 3.(b).(ii)-(iv) in Algorithm 1 on the first register. The operator
$U_{B}^{\text{EXT}}(\theta_{2})$ in step 3.(b).(iii) is a bit complicated, and
is defined as

$U_{B}^{\text{EXT}}(\theta_{2})=I-(1-e^{i\theta_{2}})\sum_{(x_{1}^{\prime},\ldots,x_{r+1}^{\prime})}\sum_{[S,y]}\ket{B_{[S,y]}^{(x_{1}^{\prime},\ldots,x_{r+1}^{\prime})}}\bra{B_{[S,y]}^{(x_{1}^{\prime},\ldots,x_{r+1}^{\prime})}},$
(6)

where the first sum is over all the possible string
$(x_{1}^{\prime},\ldots,x_{r+1}^{\prime})\in[M]^{r+1}$, and the second sum is
over all the representatives $[S,y]$ of clique
$B_{[S,y]}=\\{(S^{\prime},y^{\prime}):\\{y^{\prime}\\}\cup
S^{\prime}=\\{y\\}\cup S\\}$. Note that $|B_{[S,y]}|=r+1$ and there are
$\binom{N}{r+1}$ of this kind. The state
$\ket{B_{[S,y]}^{(x_{1}^{\prime},\ldots,x_{r+1}^{\prime})}}$ is determined by
$[S,y]$ and $(x_{1}^{\prime},\ldots,x_{r+1}^{\prime})$, and is defined as

$\ket{B_{[S,y]}^{x_{1}^{\prime},\ldots,x_{r+1}^{\prime}}}=\frac{1}{\sqrt{r+1}}\sum_{y^{\prime}\in
S\cup\\{y\\}}\ket{S\cup\\{y\\}\setminus\\{y^{\prime}\\},y^{\prime}}\ket{\pi(x_{1}^{\prime}),\ldots,\pi(x_{r+1}^{\prime})},$
(7)

where the permutation $\pi$ on the second register is related to the
permutation of indices in the first register. This relation is best
illustrated by an example: suppose $[S,y]=[\\{1,4\\},3]$, then

$\ket{B_{[S,y]}^{(x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime})}}=\frac{1}{\sqrt{3}}\Big{(}\ket{\\{1,4\\},3}\ket{x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime}}+\ket{\\{3,4\\},1}\ket{x_{3}^{\prime},x_{2}^{\prime},x_{1}^{\prime}}+\ket{\\{1,3\\},4}\ket{x_{1}^{\prime},x_{3}^{\prime},x_{2}^{\prime}}\Big{)}.$
(8)

Compared to the first term in Eq. (8), the third term exchanged the index $4$
and $3$. Therefore $\pi$ exchanges the corresponding $x_{2}^{\prime}$ and
$x_{3}^{\prime}$ in the second register. The second term is obtained in a
similar fashion. Although the indices in $S$ are unordered, we regard them to
be in the ascending order so that
$\ket{B_{[S,y]}^{x_{1}^{\prime},\ldots,x_{r+1}^{\prime}}}$ is well-defined.
For example, $x_{3}^{\prime}$ in the second term of Eq. (8) is related to
index $3$ but not $4$. Combining this and the ascending order of the output
sequence of $\mathcal{P}$, we know that during the whole procedure of
Algorithm 1, $\ket{x_{i_{1}},\ldots,x_{i_{r}}}$ in the second register as the
subset of $x=(x_{1},\ldots,x_{N})$ is always related to the ascending index
sequence $(i_{1},\ldots,i_{r})$ of $\ket{S}$ in the first register. Thus we
can omit the second register when analyzing the algorithm. Moreover, in the
final measurement of Algorithm 1, the two registers will collapse to the
entangled state $\ket{S,y}\ket{x_{i_{1}},\ldots,x_{i_{r}}}$. Therefore, we can
obtain indices of the colliding pair without further quires. Thus we have
shown, the combined effect of steps 3.(b).(ii)-(iv) in Algorithm 1 can be seen
as the following operator acting on the first register.

$U_{B}(\theta_{2})=I-(1-e^{i\theta_{2}})\sum_{[S,y]}\ket{B_{[S,y]}}\bra{B_{[S,y]}},$
(9)

where

$\ket{B_{[S,y]}}=\frac{1}{\sqrt{r+1}}\sum_{y^{\prime}\in
S\cup\\{y\\}}\ket{S\cup\\{y\\}\setminus\\{y^{\prime}\\},y^{\prime}}.$ (10)

The marked vertices $(S,y)$ of graph $G$ are those containing the colliding
pair’s indices $(i_{1},i_{2})$ in $S$, and the related marking operator
$R_{T}(\alpha)$ multiplies
$\ket{S,y}\ket{x^{\prime}_{1},\ldots,x^{\prime}_{r},0}$ by $e^{i\alpha}$ if
the second register contains the colliding pair. Note that $R_{T}(\alpha)$ may
be time consuming, but it does not need to query the index oracle $O_{x}$.

An example of the quasi-Johnson graph when $N=5,r=2$ and $(1,3)$ being the
indices of the colliding pair in $x=(x_{1},\ldots,x_{5})$ is shown in Fig. 1.
It gives us a visual impression of what the quasi-Johnson graph $G$ with its
two kinds of cliques $A_{S}$ and $B_{[S,y]}$ would look like.

Figure 1: The quasi-Johnson graph $G$ when $N=5$ and $|S|=r=2$. Note that
$\binom{N}{r}(N-r)=\binom{N}{r+1}(r+1)=10\times 3$, so that the two types of
cliques $A_{S}$ and $B_{[S,y]}$ are of the same size $3$ and of the same
quantity $10$. The vertex $(S,y)=(\\{1,2\\},3)$ in $G$, for example, is
represented by the blue circle with shorthand “$12,3$” inside. The cliques
$A_{S}$ are represented by equilateral triangles with red dotted edges. The
cliques $B_{[S,y]}$ are represented by shaded gray triangles with black solid
edges, $4$ of them are equilateral and the other $6$ triangles are obtuse.
Suppose $(1,3)$ is the indices of the colliding pair in
$x=(x_{1},\ldots,x_{5})$. Then the three nodes in the upper right corner with
bold numbers “13” inside are the marked vertices.

If we denote the equal-superposition of all the marked vertices by $\ket{T}$,
and the equal-superposition of all vertices by
$\ket{\psi_{0}}:=\frac{1}{\sqrt{|V|}}\sum_{(S,y)\in V}\ket{S,y}$, then the
goal of quantum walk search on quasi-Johnson graph $G$ is to transform
$\ket{\psi_{0}}$ to $\ket{T}$ by applying an appropriate sequence consists of
$U_{A}(\theta_{1}),U_{B}(\theta_{2})$ and $R_{T}(\alpha)$.

Input: index oracle $O_{x}$ given in Problem 1 [effect shown in Eq. (2)]

Output: indices $(i_{1},i_{2})$ of the colliding pair; or “all distinct”.

Procedure :

1

2

  1. 1.

Prepare the equal-superposition of all vertices
$\ket{\psi_{0}}=\frac{1}{\sqrt{|V|}}\sum_{(S,y)\in V}\ket{S,y}$ in the first
register.

  2. 2.

Call decoding procedure $\mathcal{P}$ on $\ket{\psi_{0}}$ to obtain the
ascending index sequence $(i_{1},\ldots,i_{r})$ of $S$, and query $O_{x}$ for
$r$ times to obtain $\frac{1}{\sqrt{|V|}}\sum_{(S,y)\in
V}\ket{S,y}\ket{x_{i_{1}},\ldots,x_{i_{r}},0}$. Then apply $\mathcal{P}$ again
to erase the ancillary register storing the index sequence.

  3. 3.

Iterate the following steps for $t_{1}$ times:

    1. (a)

Apply the marking operator $R_{T}(\alpha_{1})$ which multiplies
$\ket{S,y}\ket{x^{\prime}_{1},\ldots,x^{\prime}_{r},0}$ by $e^{i\alpha_{1}}$
if the second register contains the colliding pair.

    2. (b)

Iterate the following steps for $ct_{2}$ times:

      1. (i)

Apply $U_{A}(\theta_{1})$ [see Eq. (4)] to the first register.

      2. (ii)

Call $\mathcal{P}$ on $\ket{S,y}$ to obtain $\bar{y}$, and query $O_{x}$ with
$\bar{y}$, storing the answer in the last slot of the second register
$\ket{x^{\prime}_{r+1}}$. Then apply $\mathcal{P}$ again to erase the
ancillary register storing the index sequence.

      3. (iii)

Apply $U_{B}^{\text{EXT}}(\theta_{2})$ [see Eq. (6)] on the two working
registers.

      4. (iv)

Repeat step (ii) to set $\ket{x^{\prime}_{r+1}}$ back to $\ket{0}$.

    3. (c)

Apply the marking operator $R_{T}(\alpha_{2})$ with a different angle
$\alpha_{2}$.

    4. (d)

Repeat step (b).

  4. 4.

Measure the two working registers in computational basis, and based on the
outcome $S$ and $(x_{i_{1}^{\prime}},\ldots,x_{i_{r}^{\prime}})$, obtain
indices $(i_{1},i_{2})$ of the colliding pair; or output “all distinct” if
$(x_{i_{1}^{\prime}},\ldots,x_{i_{r}^{\prime}})$ are all distinct.

3p.s. The $6$ parameters
$t_{1},\alpha_{1},\alpha_{2},ct_{2},\theta_{1},\theta_{2}$ is set according to
Eqs. (11)-(2.2).

Algorithm 1 Exact quantum algorithm for Problem 1

###  2.2 Parameters in the algorithm

Algorithm 1 contains $6$ parameters
$\alpha_{1},\alpha_{2},\theta_{1},\theta_{2},t_{1},c\cdot t_{2}$ to be set
below. We justify their values in the next section. The iteration number of
the inner loop [step 3.(b)] is

$c\cdot t_{2}=10\cdot\lceil\frac{\pi}{2}\sqrt{r}\rceil.$ (11)

The rotation parameters $\theta_{1},\theta_{2}$ in the inner loop are
solutions to the following equations:

$\cos\phi_{1}=-\cos(1-\frac{2}{c})\frac{\pi}{t_{2}},\quad\cos\phi_{2}=-\cos\frac{\pi}{t_{2}},$
(12)

where
$\cos\phi_{i}=\cos\frac{\theta_{1}+\theta_{2}}{2}+2\sin\frac{\theta_{1}}{2}\sin\frac{\theta_{2}}{2}\,\lambda_{i}$,
and $\lambda_{i}=\frac{i(N+1-i)}{(N-r)(r+1)}$. Let $\beta:=-(c\cdot
t_{2}\frac{\theta_{1}+\theta_{2}}{2}\mod 2\pi)$,
$\lambda=\frac{r(r-1)}{N(N-1)}$, and
$\phi_{0}:=|4\arcsin(\sqrt{\lambda}\sin\frac{\beta}{2})\mod[-\frac{\pi}{2},\frac{\pi}{2}]|$,
where the notation “$x\mod[-\frac{\pi}{2},\frac{\pi}{2}]$” means adding $x$
with an appropriate integer multiples $l$ of $\pi$, such that
$x+l\pi\in[-\frac{\pi}{2},\frac{\pi}{2}]$. Then the iteration number of the
outer loop [step 3] is

$t_{1}=\lceil\frac{\pi}{\phi_{0}}\rceil.$ (13)

The angle parameters $\alpha_{1},\alpha_{2}$ in the outer loop are solutions
to the following equations:

$\displaystyle 0$
$\displaystyle=1-2\lambda\frac{\tan(t_{1}\phi)}{\sin\phi}(-\sin\frac{\alpha_{1}}{2}\cos\frac{\alpha_{2}}{2}\sin\beta+2\sin\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}\sin^{2}\frac{\beta}{2}(1-2\lambda)),$
(14) $\displaystyle 0$
$\displaystyle=-(1-2\lambda)\sin\beta\tan\frac{\alpha_{1}}{2}\tan\frac{\alpha_{2}}{2}+\cos\beta\tan\frac{\alpha_{1}}{2}+(2\lambda+(1-2\lambda)\cos\beta)\tan\frac{\alpha_{2}}{2}+\sin\beta,$
(15)

where $\phi$ satisfies

$\displaystyle\cos{\phi}$
$\displaystyle=\cos(\frac{\alpha_{1}+\alpha_{2}}{2}+\beta)+2\lambda(\sin\frac{\alpha_{1}+\alpha_{2}}{2}\sin\beta-4\sin\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}\sin^{2}\frac{\beta}{2})$
$\displaystyle\qquad+8\lambda^{2}\sin\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}\sin^{2}\frac{\beta}{2}.$
(16)

##  3 Analysis of the algorithm

We first analyze the query complexity of Algorithm 1. From Eq. (13), the
iteration number $t_{1}$ of the outer loop is related to angle $\beta/2$. Note
that $\frac{\beta}{2}$ tends to a constant which is irrelevant to $N$ when
$N\to\infty$ from Eq. (38). Therefore, the inner loop is iterated for
$2t_{1}\in O(N/r)$ times. As the inner loop queries $O_{x}$ for $2ct_{2}\in
O(\sqrt{r})$ times, and the preparation of $\ket{\psi_{0}}$ needs $r$ queries,
the total query complexity is $O(N/\sqrt{r}+r)=O(N^{2/3})$ by Eq. (1).

We now analyze the correctness of Algorithm 1. Note that $\ket{\psi_{0}}$
remains unchanged when the items of $x$ are all distinct, because
$R_{T}(\alpha)$ now becomes the identity operator $I$, and $\ket{\psi_{0}}$ is
invariant under $U_{A}(\theta_{1})$ and $U_{B}(\theta_{2})$. Hence, Algorithm
1 is correct for this case. We thus assume that $x$ contains a single
colliding pair in the following three subsections.

###  3.1 Reducing to $5$-dimensional subspace

The reduced $5$-dimensional subspace $\mathcal{H}_{0}$ is spanned by five
equal-superpositions of the vertices in five different groups:
$\eta_{0}^{0},\eta_{0}^{1},\eta_{1}^{0},\eta_{1}^{1},\eta_{2}^{0}$, where
$\eta_{l}^{j}=\\{(S,y)\in V:|S\cap K|=l,\,|\\{y\\}\cap K|=j\\}$. That is, we
group the vertices of $G$ into five different groups by the $5$ different
situations that $(S,y)$ intersects with indices $\\{i_{1},i_{2}\\}=:K$ of the
colliding pair. The size of each groups, by basic combinatorics, is

$|\eta_{l}^{0}|=\binom{k}{l}\binom{N-k}{r-l}(N-r-(k-l)),\quad|\eta_{l}^{1}|=\binom{k}{l}\binom{N-k}{r-l}(k-l),$
(17)

where $k=2$ is the size of $K$. We denote by $\ket{T}$ the target state
$\ket{\eta_{2}^{0}}$, as all vertices in this group contains indices
$\\{i_{1},i_{2}\\}$ of the colliding pair. Clearly
$\ket{\psi_{0}}\in\mathcal{H}_{0}$, and the square root of the proportion of
targets to all vertices is

$\braket{T}{\psi_{0}}=\sqrt{\frac{r(r-1)}{N(N-1)}}.$ (18)

We now show that the effect of step 3.(b) of Algorithm 1 in $\mathcal{H}_{0}$
is

$u=U_{B}(\theta_{2})U_{A}(\theta_{1})=(I-(1-e^{i\theta_{2}})BB^{\dagger})\cdot(I-(1-e^{i\theta_{1}})AA^{\dagger}),$
(19)

where

$A\circ A=\begin{bmatrix}{1-\frac{2}{N-r}}&0&0\\\ {\frac{2}{N-r}}&0&0\\\
0&{1-\frac{1}{N-r}}&0\\\ 0&{\frac{1}{N-r}}&0\\\ 0&0&1\end{bmatrix},\quad
B\circ B=\begin{bmatrix}1&0&0\\\ 0&\frac{1}{r+1}&0\\\ 0&1-\frac{1}{r+1}&0\\\
0&0&\frac{2}{r+1}\\\ 0&0&1-\frac{2}{r+1}\end{bmatrix}.$ (20)

The notation $\circ$ here is the Hadamard (element-wise) product. We use it
because the square root notation $\sqrt{*}$ takes up too much space.

Proof (Calculation): Consider
$U_{A}(\theta_{1})=I-(1-e^{i\theta_{1}})\sum_{S\in
S_{r}}\ket{A_{S}}\bra{A_{S}}$ first. Recall from Eq. (5) that
$\ket{A_{S}}=\frac{1}{\sqrt{N-r}}\sum_{y\in[N]\setminus y}\ket{S,y}$ is
determined by $S$. Thus $\braket{A_{S}}{\eta_{l}^{j}}\neq 0$ only if $|S\cap
K|=l$, where $l\in\\{0,1,2\\}$. To determine its value, note that $\ket{S,y}$
in $\ket{\eta_{l}^{j}}$ has to have the same $S$ as that of $A_{S}$ to produce
nonzero inner-product. Therefore, we have

$\displaystyle\braket{A_{S}}{\eta_{l}^{j}}$
$\displaystyle=\frac{\delta_{|S\cap
K|,l}}{\sqrt{N-r}\sqrt{|\eta_{l}^{j}|}}\times\begin{cases}N-r-(k-l),&j=0\\\
k-l,&j=1\end{cases}$ (21) $\displaystyle=\frac{\delta_{|S\cap
K|,l}}{\sqrt{N-r}\sqrt{\binom{k}{l}\binom{N-k}{r-l}}}\times\begin{cases}\sqrt{N-r-(k-l)},&j=0\\\
\sqrt{k-l},&j=1\end{cases}.$ (22)

We now consider the sum $\sum_{S\in
S_{r}}\braket{\eta_{l^{\prime}}^{j^{\prime}}}{A_{S}}\braket{A_{S}}{\eta_{l}^{j}}$.
Note that it’s nonzero only if $l=l^{\prime}$, and thus the sum now reduces to
be over those $S\in S_{r}$ that satisfy $|S\cap K|=l$. There are
$\binom{k}{l}\binom{N-k}{r-l}$ of this kind, cancelling the denominator in Eq.
(22). Hence, the effect of $U_{A}(\theta_{1})$ in its invariant subspace
$\\{\ket{\eta_{l}^{0}},\ket{\eta_{l}^{1}}\\}$ is

$I-(1-e^{i\theta_{1}})\begin{bmatrix}\sqrt{1-\frac{k-l}{N-r}}\\\
\sqrt{\frac{k-l}{N-r}}\end{bmatrix}\begin{bmatrix}\sqrt{1-\frac{k-l}{N-r}},&\sqrt{\frac{k-l}{N-r}}\end{bmatrix},$
(23)

which degenerates to the scalar multiplication
$e^{i\theta_{1}}\ket{\eta_{k}^{0}}\bra{\eta_{k}^{0}}$ when $l=k$. The effect
of $U_{A}(\theta_{1})$ in $\mathcal{H}_{0}$ as shown in Eq. (31) now follows
easily. The effect of $U_{B}(\theta_{2})$ can be determined in a similar
fashion. $\blacksquare$

The effect of $R_{T}(\alpha)$ in
$\mathcal{H}_{0}=\text{span}\\{\ket{\eta_{0}^{0}},\ket{\eta_{0}^{1}},\ket{\eta_{1}^{0}},\ket{\eta_{1}^{1}},\ket{\eta_{2}^{0}}\\}$
that appeared in step 3.(a) and 3.(c) of Algorithm 1 is obviously

$R_{T}(\alpha)=\text{diag}\left([1,1,1,1,e^{i\alpha}]\right).$ (24)

Now the goal of Algorithm 1, in a nutshell, is to achieve the following
equation

$1=\bra{T}\big{(}u^{c\,t_{2}}R_{T}(\alpha_{2})\cdot
u^{c\,t_{2}}R_{T}(\alpha_{1})\big{)}^{t_{1}}\ket{\psi_{0}},$ (25)

by appropriately setting the parameters therein.

###  3.2 Constructing phase rotation about the initial state

In this subsection, we show how to construct the following phase rotation
$R_{\psi_{0}}(\beta)$ about the initial state $\ket{\psi_{0}}$, by iterating
the quantum walk operator $u=U_{B}(\theta_{2})U_{A}(\theta_{1})$ for $c\cdot
t_{2}$ times.

$R_{\psi_{0}}(\beta):=I-(1-e^{i\beta})\ket{\psi_{0}}\bra{\psi_{0}}$ (26)

We first justify the values of $\theta_{1},\theta_{2}$ and $c\cdot t_{2}$ as
shown respectively in Eq. (12) and Eq. (11) by the following lemma.

######  Lemma 1.

By setting the parameters $\theta_{1},\theta_{2}$ in
$u=U_{B}(\theta_{2})U_{A}(\theta_{1})$ and $c\cdot t_{2}$ according to Eq.
(12) and Eq. (11) respectively, the effect of $u^{ct_{2}}$ in
$\mathcal{H}_{0}$ is the following:

$I-(1-e^{i\,ct_{2}\frac{\theta_{1}+\theta_{2}}{2}})\ket{\psi_{0}}\bra{\psi_{0}}.$
(27)

Attention: Eq. (27) is defined in the subspace $\mathcal{H}_{0}$, but not in
the whole space spanned by all the vertices of $G$. In fact, to construct Eq.
(27) in the whole space, we claim that one must iterate $u$ for at least $r$
times rather than $ct_{2}\in O(\sqrt{r})$ times: if $S_{1}\cup\\{y_{1}\\}$ and
$S_{2}\cup\\{y_{2}\\}$ are disjoint (this is possible, since $|S|=r=N^{2/3}\ll
N$), then one needs to iterate $u$ for at least $r$ times in order to
‘transform’ $\ket{\psi}$ to $\ket{\varphi}$. ‘Transform’ here means that after
$\ket{\psi}$ is changed to some superposition, $\ket{\varphi}$ appears in this
superposition. This is because $U_{A}(\theta_{1})$ and $U_{B}(\theta_{2})$ are
diffusion operators within clique $A_{S}$ and $B_{[S,y]}$ respectively. Thus a
step of quantum walk $u=U_{B}(\theta_{2})U_{A}(\theta_{1})$ will only update
one index in $S$ for a fixed $(S,y)$. Eq. (27) defined in the whole space can
certainly ‘transform’ $\ket{\psi}$ to $\ket{\varphi}$ in one step, and thus
the claim follows.

###### Proof.

Similar to the spectral lemma in [14], we first perform singular value
decomposition on the discriminant matrix $D:=A^{\dagger}B$ of order $3$ as
$D=WSV^{\dagger}=\sum_{i=0}^{2}\lambda_{i}\ket{w_{i}}\bra{v_{i}}$. The square
$\lambda_{i}^{2}$ of the $3$ singular values are

$\left[1,\ \left(1-\frac{1}{N-r}\right)\left(1-\frac{1}{r+1}\right),\
\left(1-\frac{2}{N-r}\right)\left(1-\frac{2}{r+1}\right)\right]=:[\cos^{2}\frac{\gamma_{0}}{2},\cos^{2}\frac{\gamma_{1}}{2},\cos^{2}\frac{\gamma_{2}}{2}].$
(28)

Then we have the following two key equations, which lies at the heart of
Jordan’s lemma [12]:

$\displaystyle\Pi_{A}\cdot
B\ket{v_{i}}:=AA^{\dagger}B\ket{v_{i}}=AD\ket{v_{i}}=\cos\frac{\gamma_{i}}{2}\cdot
A\ket{w_{i}},$ (29) $\displaystyle\Pi_{B}\cdot
A\ket{w_{i}}:=BB^{\dagger}A\ket{w_{i}}=B(\bra{w_{i}}D)^{\dagger}=\cos\frac{\gamma_{i}}{2}\cdot
B\ket{v_{i}}.$ (30)

It can be verified that $A\ket{w_{0}}=B\ket{v_{0}}=\ket{\psi_{0}}$. Thus we
obtain the three common invariant subspaces $\\{\ket{\psi_{0}}\\}$,
$\text{span}\\{A\ket{w_{1}},B\ket{v_{1}}\\}$ and
$\text{span}\\{A\ket{w_{2}},B\ket{v_{2}}\\}$ of

$u=(I-(1-e^{i\theta_{2}})\Pi_{B})\cdot(I-(1-e^{i\theta_{1}})\Pi_{A}).$ (31)

The effect of $u$ in the subspace $\text{span}\\{A\ket{w_{i}},B\ket{v_{i}}\\}$
($2$-dimensional space) is the composition of two 3D-rotations: a rotation
about $A\ket{w}$ by angle $-\theta_{1}$, followed by a rotation about
$B\ket{w}$ by $-\theta_{2}$, and the angle between the two rotation axes is
$\gamma_{i}$. We articulate this in the following. As
$\bra{w_{i}}A^{\dagger}B\ket{v_{i}}=\cos\gamma_{i}/2$, we might as well let
$B\ket{v_{i}}=\cos\gamma_{i}/2\ A\ket{w_{i}}+\sin\gamma_{i}/2\
A\ket{w_{i}}^{\perp}$, where $A\ket{w_{i}}^{\perp}$ is perpendicular to
$A\ket{w_{i}}$ and lies in the same qubit space. Simple calculation shows that
the effect of $U_{A}(\theta_{1})$ on the orthonormal basis
$\\{A\ket{w_{i}},A\ket{w_{i}}^{\perp}\\}$ is

$U_{A}(\theta_{1})=\begin{bmatrix}e^{i\theta_{1}}&0\\\
0&1\end{bmatrix}=e^{i\theta_{1}/2}R_{Aw_{i}}(-\theta_{1}/2).$ (32)

The notation

$R_{\vec{n}}(\phi):=\cos\phi I-i\sin\phi\,\vec{n}\cdot\vec{\sigma}$ (33)

represents a rotation on the Bloch sphere about axis $\vec{n}$ by angle
$2\phi$ obeying the right-handed rule, and
$\vec{n}\cdot\vec{\sigma}:=n_{x}X+n_{y}Y+n_{z}Z$, where $X,Y,Z$ are the three
Pauli matrices. $U_{A}(\theta_{1})$ thus represents a rotation about
$Aw_{i}=[0,0,1]$ by angle $-\theta_{1}$. Similarly, the effect of
$U_{B}(\theta_{2})$ on the orthonormal basis
$\\{A\ket{w_{i}},A\ket{w_{i}}^{\perp}\\}$ is

$U_{B}(\theta_{2})=\begin{bmatrix}1-(1-e^{i\theta_{2}})\cos^{2}\frac{\gamma}{2}&-(1-e^{i\theta_{2}})\sin\frac{\gamma}{2}\cos\frac{\gamma}{2}\\\
-(1-e^{i\theta_{2}})\sin\frac{\gamma}{2}\cos\frac{\gamma}{2}&1-(1-e^{i\theta_{2}})\sin^{2}\frac{\gamma}{2}\end{bmatrix}=e^{i\theta_{2}/2}R_{Bv_{i}}(-\theta_{2}/2),$
(34)

which represents a rotation about $Bv_{i}=[\sin\gamma_{i},0,\cos\gamma_{i}]$
by angle $-\theta_{2}$. Thus the angle between the two rotation axes $Aw_{i}$
and $Bv_{i}$ is $\gamma_{i}$.

By the composition lemma of two rotations (Exercise 4.15 in [21]), the effect
of $u$ (shown in Eq. (31)) in the subspace
$\text{span}\\{A\ket{w_{i}},B\ket{v_{i}}\\}$ as the composition of two
rotations is another rotation
$e^{i\frac{\theta_{1}+\theta_{2}}{2}}R_{\vec{n}}(\phi_{i})$, whose rotation
angle $\phi_{i}$ satisfies:

$\cos\phi_{i}=\cos\frac{\theta_{1}+\theta_{2}}{2}+2\sin\frac{\theta_{1}}{2}\sin\frac{\theta_{2}}{2}\,\lambda_{i},$
(35)

where $\lambda_{i}:=\sin^{2}\frac{\gamma_{i}}{2}=\frac{i(N+1-i)}{(N-r)(r+1)}$.
Note that Eq. (12) is equivalent to

$\phi_{1}=\pi\pm(1-\frac{2}{c})\frac{\pi}{t_{2}},\quad\phi_{2}=\pi\pm\frac{\pi}{t_{2}}.$
(36)

Therefore $ct_{2}\phi_{i}\equiv 0\mod 2\pi$ ( $c=10$ is even). From the
composition lemma of two rotations and mathematical induction, we have

$R_{\vec{n}}^{k}(\phi)=R_{\vec{n}}(k\phi).$ (37)

Note that $R_{\vec{n}}(\phi)=I$ when $\phi\equiv 0\mod 2\pi$. Hence, the
effect of $u^{ct_{2}}$ on the three invariant subspace $\\{\ket{\psi_{0}}\\}$,
$\text{span}\\{A\ket{w_{1}},A\ket{w_{1}}^{\perp}\\}$ and
$\text{span}\\{A\ket{w_{2}},A\ket{w_{2}}^{\perp}\\}$, up to the irrelevant
global phase $e^{i\,ct_{2}\frac{\theta_{1}+\theta_{2}}{2}}$, are
$e^{i\,ct_{2}\frac{\theta_{1}+\theta_{2}}{2}}I,\ I$ and $I$, respectively.
This completes the proof of Lemma 1. ∎

The intuition behind Eq. (36) can be interpreted as the minute hand
($\phi_{2}$) catching up with the hour hand ($\phi_{1}$) on a watch
[considering the case that ‘$\pm$’ is ‘$+$’ in Eq. (36)]. As $\cos\phi_{i}$ is
linear in $\lambda_{i}$, the rotation angle $\phi_{i}$ will never be equal
since $\lambda_{1}$ and $\lambda_{2}$ differs. We let the difference between
$\phi_{1}$ and $\phi_{2}$ to be $\frac{2\pi}{ct_{2}}$, and let the difference
between $\phi_{2}$ and $\pi$ to be $\frac{\pi}{t_{2}}$, so that after $ct_{2}$
iterations, $\phi_{1}$ is slower than $\phi_{2}$ for an entire cycle, and
$\phi_{2}$ is faster than $\pi$ for $c/2$ cycle. Hence, $ct_{2}\phi_{i}\equiv
0\mod 2\pi$ as desired. More importantly, setting iteration number $ct_{2}$
according to Eq. (11) guarantees that the equations (36) about
$\theta_{1},\theta_{2}$ have a solution. This is shown in the following lemma.

######  Lemma 2.

When $N\geq 5,c=10$, and $t_{2}\geq\frac{\pi}{2}\sqrt{r}$, there exist
solutions $\theta_{1},\theta_{2}$ to Eq. (12). One of the solutions satisfies
$\frac{\theta_{1}+\theta_{2}}{2}=\pi-d\frac{\pi}{t_{2}}$, where the
intermediate variable $d$ has two properties: $cd\pi$ is not an integer
multiple of $2\pi$; and when $N\to\infty$,
$d\to\sqrt{c^{2}-8(c-1)}/c=\sqrt{7}/5$. This solution can be obtained by
solving Eq. (48) first for $d$, and then substitute it into Eq. (49) to obtain
$\theta_{1}$, and finally let $\theta_{2}=2(\pi-d\pi/t_{2})-\theta_{1}$.

###### Proof.

See Appendix A. ∎

According to Lemma 2, when $N\to\infty$, the effect of $u^{ct_{2}}$ multiplies
$\ket{\psi_{0}}$ by a relative phase

$e^{-cdi\pi}=e^{-2\sqrt{7}i\pi}\approx e^{-1.29i\pi},$ (38)

and the claim that $cd\pi$ is not an integer multiple of $2\pi$ guarantees
$u^{ct_{2}}\neq I$.

###  3.3 Exact quantum search with arbitrarily given phase rotation

In this subsection, we will transform the initial state $\ket{\psi_{0}}$ to
$\ket{T}$ in $\mathcal{H}_{0}$ by appropriately setting the angle $\alpha$ in
$R_{T}(\alpha)$, with the help of the FXR method [13].

Let $\beta=-(c\cdot t_{2}\frac{\theta_{1}+\theta_{2}}{2}\mod 2\pi)=(cd\pi\mod
2\pi)$, then by Eq. (24) and Lemma 1, the effect of $R_{T}(\alpha)$ and
$u^{ct_{2}}$ in $\mathcal{H}_{0}$ are

$I-(1-e^{i\alpha})\ket{T}\bra{T}=:S_{o}(\alpha),\quad
I-(1-e^{-i\beta})\ket{\psi_{0}}\bra{\psi_{0}}=:S_{r}(\beta),$ (39)

respectively. Recall from Eq. (18) that
$\braket{T}{\psi_{0}}=\sqrt{\frac{r(r-1)}{N(N-1)}}=:\sqrt{\lambda}$. Thus we
might as well let
$\ket{\psi_{0}}=\sqrt{1-\lambda}\ket{R}+\sqrt{\lambda}\ket{T}$, where
$\ket{R}\in\text{span}\\{\ket{T},\ket{\psi_{0}}\\}$ and is perpendicular to
$\ket{T}$. We denote by $\mathcal{H}_{1}:=\text{span}\\{\ket{R},\ket{T}\\}$
the $2$-dimensional invariant subspace of
$u^{ct_{2}}R_{T}(\alpha)=S_{r}(\beta)S_{o}(\alpha)$. Note that
$S_{r}(\beta)S_{o}(\alpha)$ is the generalized Grover’s operator
$G(\alpha,\beta)$, where $S_{o}$ is the ‘oracle’ operator, and $S_{r}$ is the
diffusion operator.

Just as the calculation step of Theorem 2 in [13], by repeatedly using the
composition lemma of two rotations, we find that the effect of

$F_{xr,\beta}:=G(\alpha_{2},\beta)G(\alpha_{1},\beta),$ (40)

which is now the effect of one iteration of the outer loop (step 3 in
Algorithm 1), is a rotation
$e^{i(\frac{\alpha_{1}+\alpha_{2}}{2}-\beta)}R_{\vec{n}}(\phi)$ on the Bloch
sphere of $\mathcal{H}_{1}$. The rotation angle $\phi$ satisfies Eq. (2.2),
and the axis $\vec{n}$ are as follows:

$\displaystyle\sin\phi\,n_{x}$
$\displaystyle=2\sqrt{\lambda(1-\lambda)}(\cos\frac{\alpha_{1}}{2}\cos\frac{\alpha_{2}}{2}\sin\beta-2(1-2\lambda)\cos\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}\sin^{2}\frac{\beta}{2}),$
(41) $\displaystyle\sin\phi\,n_{y}$
$\displaystyle=2\sqrt{\lambda(1-\lambda)}(-\sin\frac{\alpha_{1}}{2}\cos\frac{\alpha_{2}}{2}\sin\beta+2(1-2\lambda)\sin\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}\sin^{2}\frac{\beta}{2}),$
(42) $\displaystyle\sin\phi\,n_{z}$
$\displaystyle=\sin\frac{\alpha_{1}}{2}\cos\frac{\alpha_{2}}{2}\cos\beta+\cos\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}$
$\displaystyle\qquad+(1-2\lambda)\cos\frac{\alpha_{1}+\alpha_{2}}{2}\sin\beta-2(1-2\lambda)^{2}\cos\frac{\alpha_{1}}{2}\sin\frac{\alpha_{2}}{2}\sin^{2}\frac{\beta}{2}.$
(43)

Transforming $\ket{\psi_{0}}$ to $\ket{T}$ in $\mathcal{H}_{1}$ is then
equivalent to the equation $0=\bra{R}R^{k}_{\vec{n}}(\phi)\ket{\psi_{0}}$. By
setting the equation’s real and imaginary part both to be zero, and with the
help of Eq. (37), we obtain the equations that parameters
$(k=t_{1},\alpha_{1},\alpha_{2})$ need to satisfy:

$\displaystyle 0$
$\displaystyle=\sqrt{1-\lambda}\cos{k\phi}-\sqrt{\lambda}\sin{k\phi}\ n_{y},$
(real 1) $\displaystyle 0$ $\displaystyle=\sqrt{1-\lambda}\
n_{z}+\sqrt{\lambda}\ n_{x}.$ (im 1)

Substituting Eqs. (41)-(43) into the above two equations then leads to Eqs.
(14),(15).

Let
$\phi_{0}=|4\arcsin(\sqrt{\lambda}\sin\frac{\beta}{2})\mod[-\frac{\pi}{2},\frac{\pi}{2}]|$,
then Theorem 2 in [13] shows that the above equations possess a solution when
$k>\pi/\phi_{0}$. This explains the value of $t_{1}$ shown in Eq. (13).

###  3.4 Query lower bound

######  Lemma 3.

The deterministic quantum query complexity of Problem 1 is $\Omega(N^{2/3})$.

###### Proof.

The easier decision problem of Problem 1, i.e. to determine whether elements
in $(x_{1},x_{2},\ldots,x_{N})\in[M]^{N}$ are all distinct, is in fact the
evaluation of partial Boolean function $f:\mathcal{D}\to\\{0,1\\}$, whose
domain $\mathcal{D}\subseteq[M]^{N}$ consists of two parts:
$f^{-1}(1)=\\{x\in[M]^{N}:x\ \text{contains a single colliding pair}\\}$, and
$f^{-1}(0)=\\{x\in[M]^{N}:\text{elements in}\ x\ \text{are all distinct}\\}$.
We therefore need only to show that the deterministic quantum query complexity
of evaluating $f$ is $\Omega(N^{2/3})$. Let $Q_{\epsilon}(f)$ be the bounded-
error quantum query complexity of evaluating $f$. Bounded-error means to
output the correct answer with probability $1-\epsilon$, where
$0\leq\epsilon<1/2$. According to Theorem 2 in [17],

$Q_{\epsilon}(f)\geq\frac{1-2\sqrt{\epsilon(1-\epsilon)}}{2}\text{ADV}^{\pm}(f),$
(44)

where $\text{ADV}^{\pm}(f)$ is the negative-weight adversary lower bound of
$f$. Hence, by letting $\epsilon=0$, we know that the deterministic quantum
query complexity of evaluating $f$ is at least $\text{ADV}^{\pm}(f)/2$. The
definition of $\text{ADV}^{\pm}(f)$ is

$\text{ADV}^{\pm}(f)=\max_{\Gamma\in\mathcal{M}}\frac{||\Gamma||}{\max_{i\in[n]}||\Gamma\circ\Delta_{i}||},$
(45)

where $\mathcal{M}$ are the set of all the nonzero real matrices, whose row
indices composed of elements in $f^{-1}(1)$, and whose column indices composed
of elements in $f^{-1}(0)$; element $(x,y)$ in the $0-1$ matrix
$\Delta_{i}\in\mathcal{M}$ equals $1$ if and only if $x_{i}\neq y_{i}$;
notation $\circ$ is the Hadamard product, and $||\cdot||$ is the spectral
norm.

It has been shown respectively in [18] and [19] that when $M=\Omega(N^{2})$
and $M=N$, the lower bound of $\text{ADV}^{\pm}(f)$ are both
$\Omega(N^{2/3})$. The proof in [19] does not follow the idea in [18] of
emending the adversary matrix $\Gamma$ into some bigger matrix related to the
Hamming association scheme, and therefore it breaks the restriction of
$M=\Omega(N^{2})$. It’s also said in [19] that its proof can be generalized to
any $M\geq N$, thus the deterministic quantum query complexity of Problem 1 is
$\Omega(N^{2/3})$. ∎

##  4 Conclusion and future work

In this paper, we have designed an exact quantum algorithm with query
complexity $\Theta(N^{2/3})$ that solves the promised element distinctness
problem with at most one colliding pair. The algorithm utilize Jordan’s lemma
about common invariant subspaces, and the recently proposed FXR method for
exact quantum search with arbitrary phase rotations, so as to achieve
certainty of success. In contrast, previous algorithms based on the analysis
of asymptotic behaviours of eigenvalues of quantum walk search could not
achieve 100% success. Whether the idea in this paper could be applied to other
quantum walk search problem is a possible direction for future research.

## References

  * [1] Harry Buhrman and Ronald de Wolf.  Complexity measures and decision tree complexity: a survey.  Theoretical Computer Science, 288(1):21–43, 2002.  Complexity and Logic.
  * [2] Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, and Ronald de Wolf.  Quantum algorithms for element distinctness.  SIAM Journal on Computing, 34(6):1324–1330, 2005.
  * [3] A. Ambainis.  Quantum walk algorithm for element distinctness.  In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 22–31, 2004.
  * [4] Andris Ambainis.  Quantum walk algorithm for element distinctness.  SIAM Journal on Computing, 37(1):210–239, 2007.
  * [5] Yaoyun Shi.  Quantum lower bounds for the collision and the element distinctness problems.  In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 513–519, 2002.
  * [6] Scott Aaronson and Yaoyun Shi.  Quantum lower bounds for the collision and the element distinctness problems.  J. ACM, 51(4):595–605, jul 2004.
  * [7] Andris Ambainis.  Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range.  Theory of Computing, 1(3):37–46, 2005.
  * [8] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald De Wolf.  Quantum lower bounds by polynomials.  Journal of the ACM (JACM), 48(4):778–797, 2001.
  * [9] Renato Portugal.  Staggered quantum walks on graphs.  Phys. Rev. A, 93:062335, Jun 2016.
  * [10] Renato Portugal.  Element distinctness revisited.  Quantum Information Processing, 17(7):163, May 2018.
  * [11] Renato Portugal.  Element Distinctness, pages 201–221.  Springer International Publishing, Cham, 2018.
  * [12] Camille Jordan.  Essai sur la géométrie à $n$ dimensions.  Bulletin de la Société Mathématique de France, 3:103–174, 1875\.
  * [13] Guanzhong Li and Lvzhou Li.  Quantum exact search with adjustable parameters and its applications.  https://arxiv.org/abs/2210.12644, 2022.
  * [14] M. Szegedy.  Quantum speed-up of markov chain based algorithms.  In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 32–41, 2004.
  * [15] Hari Krovi, Frédéric Magniez, Maris Ozols, and Jérémie Roland.  Quantum walks can find a marked element on any graph.  Algorithmica, 74(2):851–907, Feb 2016.
  * [16] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.  Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 193–204, New York, NY, USA, 2019. Association for Computing Machinery.
  * [17] Peter Hoyer, Troy Lee, and Robert Spalek.  Negative weights make adversaries stronger.  In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 526–535, 2007.
  * [18] Aleksandrs Belovs.  Adversary lower bound for element distinctness.  arXiv preprint arXiv:1204.5074, 2012.
  * [19] Ansis Rosmanis.  Quantum adversary lower bound for element distinctness with small range.  Chicago Journal of Theoretical Computer Science, 4:2014, 2014.
  * [20] David Lee.  A recurrence relation problem from the eigenvalue of a special tridiagonal matrix.  https://mathoverflow.net/questions/428331/a-recurrence-relation-problem-from-the-eigenvalue-of-a-special-tridiagonal-matri.
  * [21] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, 2010.

##  Appendix A Proof of Lemma 2

We first rearrange Eq. (12) into a form that is easier to analyze the
existence of solutions. Subtracting the first equation of Eq. (12) by the
second equation, and substituting the expression of $\cos\phi_{i}$ into them,
we obtain

$2\sin\frac{\theta_{1}}{2}\sin\frac{\theta_{2}}{2}\Delta=\delta_{c},\quad
2\sin\frac{\theta_{1}}{2}\sin\frac{\theta_{2}}{2}\,\lambda_{2}=\cos\left(\pi-\frac{\theta_{1}+\theta_{2}}{2}\right)-\cos\frac{\pi}{t_{2}},$
(46)

where $\Delta=\lambda_{2}-\lambda_{1}=\frac{N-2}{(N-r)(r+1)}$, and
$\delta_{c}=\cos((1-2/c)\pi/t_{2})-\cos(\pi/t_{2})$. We then introduce the
intermediate variable $d$ satisfying:

$\pi-\frac{\theta_{1}+\theta_{2}}{2}=d\frac{\pi}{t_{2}}.$ (47)

Substituting (Eq.1) of Eq. (46) by the division of (Eq.2)/(Eq.1), and dividing
both sides of (Eq.2) by $\lambda_{2}$, we have the following equations about
$d$ and $\theta_{1}$:

$\displaystyle\frac{\cos(d\frac{\pi}{t_{2}})-\cos(\frac{\pi}{t_{2}})}{\cos((1-\frac{2}{c})\frac{\pi}{t_{2}})-\cos(\frac{\pi}{t_{2}})}$
$\displaystyle=2(1+\frac{1}{N-2}),$ (48)
$\displaystyle\cos(d\frac{\pi}{t_{2}})-\cos(d\frac{\pi}{t_{2}}+\theta_{1})$
$\displaystyle=\frac{1}{\lambda_{2}}\left(\cos(d\frac{\pi}{t_{2}})-\cos(\frac{\pi}{t_{2}})\right),$
(49)

where we have used the identity
$2\sin\frac{\theta_{1}}{2}\sin\frac{\theta_{2}}{2}=\cos(d\frac{\pi}{t_{2}})-\cos(d\frac{\pi}{t_{2}}+\theta_{1})$.
As stated in Lemma 2, when $ct_{2}$ is fixed, by solving the first equation we
obtain $d$. Substituting it into the second equation and solving it gives us
$\theta_{1}$. Then by Eq. (47) we obtain $\theta_{2}$.

We now show that when $N\geq 5$ and $c=10$, there exists solution $d$ to Eq.
(48), and $cd\pi$ is not an integer multiple of $2\pi$. For $\eta_{0}^{0}$
[see Eq. (17)] to be nonempty, we require $r<N-2$, and thus $N\geqslant 5$. In
the first three cases of $N=5,6,7$, the solutions to Eq. (48) are $d\approx
0.30,0.38,0.42$, so $10d\pi$ is not an integer multiple of $2\pi$. When $N\geq
8$, the RHS of Eq. (48) varies in $(2,\frac{7}{3}]$. By the intermediate value
theorem of continuous function, we only need to show that the LHS of Eq. (48)
as a continuous function of $d\in(0.4,0.6)$ contains the closed interval
$[2,\frac{7}{3}]$ in its codomain. Then there exists solution $d$ to Eq. (48),
and $cd\cdot\pi\in(4\pi,6\pi)$ is not an integer multiple of $2\pi$. From
$c=10$ we know that the LHS of Eq. (48) becomes:

$h(d,x):=\frac{\cos(dx)-\cos(x)}{\cos(0.8x)-\cos(x)},$

where $x:=\frac{\pi}{t_{2}}\in(0,\frac{\pi}{2})$. When $d=0.6$, we have
$x-dx=2(x-0.8x)$. As $\cos(x)$ is convex and monotone decreasing on interval
$(0,\frac{\pi}{2})$, we have $h(0.6,x)<2$. When $d=0.4$, from the following
Lemma 4, we know $h(0.4,x)>\lim_{x\to
0}h(0.4,x)=\frac{1-0.4^{2}}{1-0.8^{2}}=7/3$. Thus $h(d,x)$ as a function of
$d\in(0.4,0.6)$, i.e. the LHS of Eq. (48), contains $[2,\frac{7}{3}]$ in its
codomain.

######  Lemma 4.

When $0<a<b<1,\,0<x<\frac{\pi}{2}$, function
$h(x)=\frac{\cos(ax)-\cos(x)}{\cos(bx)-\cos(x)}$ is monotone increasing, and
$\lim_{x\to 0}h(x)=\frac{1-a^{2}}{1-b^{2}}$.

###### Proof.

Denote the numerator and denominator of $h$ by $f$ and $g$. The numerator of
$h^{\prime}(x)$ is $z:=f^{\prime}g-g^{\prime}f$, and $z(0)=0$. Substituting
$f^{\prime\prime}=-a^{2}\cos(ax)+\cos(x)$ and
$g^{\prime\prime}=-b^{2}\cos(bx)+\cos(x)$ into
$z^{\prime}=f^{\prime\prime}g-g^{\prime\prime}f$, we have
$z^{\prime}=(b^{2}-a^{2})\cos(ax)\cos(bx)+(1-b^{2})\cos(x)\cos(bx)+(a^{2}+1)\cos(ax)\cos(x)>0$.
Hence, $z(x)>z(0)=0$ and therefore $h(x)$ is monotone increasing. By
L’Hopital’s rule, we know that
$h(x)\to\frac{f^{\prime\prime}}{g^{\prime\prime}}=\frac{1-a^{2}}{1-b^{2}}$,
when $x\to 0$. ∎

We now consider the limit of solution $d$ to Eq. (48), when $N\to\infty$.
First note that $x=\frac{\pi}{t_{2}}<\frac{2}{\sqrt{r}}\to 0$, as it’s assumed
that $t_{2}\geq\frac{\pi}{2}\sqrt{r}$. From the Taylor expansion
$\cos(x)=1-\frac{1}{2}x^{2}+o(x^{4})$, we know

$h(d,x)=\frac{1-d^{2}+o(x^{2})}{1-(1-2/c)^{2}+o(x^{2})}\to\frac{1-d^{2}}{1-(1-2/c)^{2}}.$
(50)

Combining $RHS\to 2$ when $N\to\infty$, we know the solution $d$ to Eq. (48)
satisfies $\frac{1-d^{2}}{1-(1-2/c)^{2}}\to 2$. Hence,
$d\to\sqrt{c^{2}-8(c-1)}/c$.

Finally we show that when $N\geq 5$, $t_{2}\geq\frac{\pi}{2}\sqrt{r}$ and
$d\in(0,1)$ (proved above), there exists solution $\theta_{1}$ to Eq. (49).
Because $d\in(0,1)$, we have that the RHS
$\in(0,1/\lambda_{2}(1-\cos(\pi/t_{2}))$. The LHS is a continuous function of
$\theta_{1}$, and its codomain contains the closed interval $[0,1]$. Thus by
continuity, we only need to guarantee $1\geq 1/\lambda_{2}(1-\cos(\pi/t_{2}))$
then there exists solution $\theta_{1}$ to Eq. (49). When $N\geq 6$, it is
easy to verify $\frac{r}{2}>\frac{(N-r)(r+2)}{2(N-1)}=1/\lambda_{2}$. So we
only need to ensure that $1\geq\frac{r}{2}(1-\cos(\pi/t_{2}))$. As
$1-\cos(x)\leqslant\frac{1}{2}x^{2}$, we only need to ensure that
$1>\frac{r\pi^{2}}{4t_{2}^{2}}$, which is

$t_{2}\geq\frac{\pi}{2}\sqrt{r}.$ (51)

When $N=5$, we have $r=2$, hence $1/\lambda_{2}=9/8$. Thus we require
$1\geq\frac{9}{8}\frac{1}{2}\frac{\pi^{2}}{t_{2}^{2}}$, which is equivalent to
$t_{2}\geq\frac{3}{4}\pi$. This is the same requirement as
$t_{2}\geq\frac{\pi}{2}\sqrt{r}$ since $t_{2}$ is an integer. From the above
two cases, we conclude that when $N\geq 5$, $d\in(0,1)$ and
$t_{2}\geq\frac{\pi}{2}\sqrt{r}$, there exists solution $\theta_{1}$ to Eq.
(49).


11institutetext: Applied Statistics Unit, Indian Statistical Institute,
203, B.T. Road, Kolkata-700108, INDIA.
11email<EMAIL_ADDRESS>
# On the Counting of Involutory MDS Matrices

Susanta Samanta  0000-0003-4643-5117

###### Abstract

The optimal branch number of MDS matrices has established their prominence in
the design of diffusion layers for various block ciphers and hash functions.
Consequently, several matrix structures have been proposed for designing MDS
matrices, including Hadamard and circulant matrices. In this paper, we first
provide the count of Hadamard MDS matrices of order $4$ over the field
$\mathbb{F}_{2^{r}}$. Subsequently, we present the counts of order $2$ MDS
matrices and order $2$ involutory MDS matrices over the field
$\mathbb{F}_{2^{r}}$. Finally, leveraging these counts of order $2$ matrices,
we derive an upper bound for the number of all involutory MDS matrices of
order $4$ over $\mathbb{F}_{2^{r}}$.

###### Keywords:

Involutory matrix Hadamard matrix Diffusion Layer MDS matrix.

##  1 Introduction

Claude Shannon, in his paper “Communication Theory of Secrecy Systems” [6],
introduced the concepts of confusion and diffusion, which play a significant
role in the design of symmetric key cryptographic primitives. The concept of
confusion aims to create a statistical relationship between the ciphertext and
message that is too intricate for an attacker to exploit. This is accomplished
through the use of nonlinear functions such as Sboxes and Boolean functions.
Diffusion, on the other hand, ensures that each bit of the message and secret
key influences a significant number of bits in the ciphertext, and over
several rounds, all output bits depend on every input bit.

Optimal diffusion layers can be achieved by employing MDS matrices with the
highest branch numbers. As a result, various matrix structures have been
suggested for the designing of MDS matrices, including Hadamard and circulant
matrices. A concise survey on the various theories on the construction of MDS
matrices is provided in [3]. In the context of lightweight cryptographic
primitives, the adoption of involutory matrices allows for the implementation
of both encryption and decryption operations using identical circuitry,
thereby resulting in an equivalent implementation cost for both processes. So,
it is of special interest to find efficient MDS matrices which are also
involutory.

However, obtaining efficiently implementable involutory MDS matrices is a
challenging task. Moreover, an exhaustive search for involutory MDS matrices
over the finite field of higher order is not suitable due to the vast search
space. A concise overview of the different constructions of MDS matrices,
considering whether they possess the involutory property, is available in [3].
In 2019, Güzel et al. [4] demonstrated that there are
$(2^{r}-1)^{2}(2^{r}-2)(2^{r}-4)$ involutory MDS matrices of size $3\times 3$
over the finite field $\mathbb{F}_{2^{r}}$. However, $4$ and $8$ are the most
commonly used diffusion layer matrix sizes in the literature.

One of the most noteworthy advantages of Hadamard matrices lies in their
capability to facilitate the construction of involutory matrices. If the
matrix elements are selected such that the first row sums to one, the
resultant matrix attains involutory properties [3]. Due to this advantageous
characteristic, several block ciphers, such as Anubis [1], Khazad [2] and
CLEFIA [7], have incorporated Hadamard involutory MDS matrices into their
diffusion layers.

In this paper, the primary focus is to enumerate Hadamard MDS matrices of
order $4$ within the field $\mathbb{F}_{2^{r}}$ and propose a conjecture
regarding the count of involutory Hadamard MDS matrices of order $4$ in the
same field. Subsequently, we provide counts for both order $2$ MDS matrices
and order $2$ involutory MDS matrices in the field $\mathbb{F}_{2^{r}}$.
Finally, by leveraging these counts of order $2$ matrices, we establish an
upper limit for the number of all involutory MDS matrices of order $4$ over
$\mathbb{F}_{2^{r}}$.

##  2 Definition and Preliminaries

Let $\mathbb{F}_{2}=\\{0,1\\}$ be the finite field of two elements,
$\mathbb{F}_{2^{r}}$ be the finite field of $2^{r}$ elements and
$\FF_{2^{r}}^{\star}$ be the multiplicative group of $\FF_{2^{r}}$. The set of
vectors of length $n$ with entries from the finite field $\mathbb{F}_{2^{r}}$
is denoted by $\mathbb{F}_{2^{r}}^{n}$.

A matrix $D$ of order $n$ is said to be diagonal if $(D)_{i,j}=0$ for $i\neq
j$. Using the notation $d_{i}=(D)_{i,i}$, the diagonal matrix $D$ can be
represented as $\operatorname{diag}(d_{1},d_{2},\ldots,d_{n})$. It is evident
that the determinant of $D$ is given by $\det(D)=\prod_{i=1}^{n}d_{i}$.
Therefore, the diagonal matrix $D$ is nonsingular over $\mathbb{F}_{2^{r}}$ if
and only if $d_{i}\neq 0$ for $1\leq i\leq n$.

An MDS matrix offers diffusion properties that find practical applications in
the field of cryptography. This concept originates from coding theory,
specifically from the realm of maximum distance separable (MDS) codes. An
$[n,k,d]$ code is MDS if it meets the singleton bound $d=n-k+1$.

###### Theorem 2.1

[5, page 321] An $[n,k,d]$ code $C$ with generator matrix
$G=[I\leavevmode\nobreak\ |\leavevmode\nobreak\ M]$, where $M$ is a
$k\times(n-k)$ matrix, is MDS if and only if every square submatrix (formed
from any $i$ rows and any $i$ columns, for any $i=1,2,\ldots,min\\{k,n-k\\}$)
of $M$ is nonsingular.

###### Definition 1

A matrix $M$ of order $n$ is said to be an MDS matrix if
$[I\leavevmode\nobreak\ |\leavevmode\nobreak\ M]$ is a generator matrix of a
$[2n,n]$ MDS code.

Another way to define an MDS matrix is as follows.

###### Fact 1

A square matrix $M$ is an MDS matrix if and only if every square submatrices
of $M$ are nonsingular.

One of the elementary row operations on matrices is multiplying a row of a
matrix by a nonzero scalar. MDS property remains invariant under such
operations. Thus, we have the following result regarding MDS matrices.

###### Lemma 1

[3] Let $M$ be an MDS matrix, then for any nonsingular diagonal matrices
$D_{1}$ and $D_{2}$, $D_{1}MD_{2}$ will also be an MDS matrix.

Using involutory diffusion matrices is more beneficial for implementation
since it allows the same module to be utilized in both encryption and
decryption phases.

###### Definition 2

An involutory matrix is defined as a square matrix $M$ that fulfills the
condition $M^{2}=I$ or, equivalently, $M=M^{-1}$.

Therefore, based on Lemma 1, we can deduce the following result.

###### Corollary 1

For any nonsingular diagonal matrix $D$, the matrix $DMD^{-1}$ is an
involutory MDS matrix if and only if $M$ is also an involutory MDS matrix.

###### Definition 3

A matrix $M$ of size $2^{n}\times 2^{n}$ in the field $\mathbb{F}_{2^{r}}$ is
called a Finite Field Hadamard matrix, or simply a Hadamard matrix, if it can
be represented in the following form:

M= $\begin{bmatrix}U&V\\\ V&U\end{bmatrix}$

where the submatrices $U$ and $V$ are also Hadamard matrices.

For example, a $2^{2}\times 2^{2}$ Hadamard matrix is:

$\displaystyle M=\begin{bmatrix}a_{1}&a_{2}&a_{3}&a_{4}\\\
a_{2}&a_{1}&a_{4}&a_{3}\\\ a_{3}&a_{4}&a_{1}&a_{2}\\\
a_{4}&a_{3}&a_{2}&a_{1}\end{bmatrix}.$

Note that Hadamard matrices are symmetric and can be represented by their
first row. For simplicity, we will denote a Hadamard matrix with the first row
as $a_{1},a_{2},\ldots,a_{n}$ as
$\operatorname{Hada}(a_{1},a_{2},\ldots,a_{n})$. Also, it is worth noting that
if $a_{1}+a_{2}+\cdots+a_{n}=1$, then the Hadamard matrix will be involutory
[3, page 8].

##  3 Enumeration of $4\times 4$ Hadamard MDS matrices

In this section, we enumerate $4\times 4$ Hadamard MDS matrices, including
involutory Hadamard MDS matrices, over the finite field $\mathbb{F}_{2^{r}}$.
First, we present the conditions that the Hadamard matrix
$\operatorname{Hada}(a,b,c,d)$ must satisfy to be considered an MDS matrix.

###### Lemma 2

The Hadamard matrix $\operatorname{Hada}(a,b,c,d)$ over $\mathbb{F}_{2^{r}}$
is MDS if and only if the tuple $(a,b,c,d)\in\mathbb{F}_{2^{r}}^{4}$ satisfies
the conditions: (i) $a,b,c,d\in\mathbb{F}_{2^{r}}^{\star}$, (ii) $a\neq b\neq
c\neq d$, (iii) $d\neq a^{-1}bc$, (iv) $d\neq ab^{-1}c$, (v) $d\neq abc^{-1}$,
and (vi) $d\neq a+b+c$.

###### Proof

The set of minors of $M=\operatorname{Hada}(a,b,c,d)$ is given by:

$\\{a\mathchar 44\relax\penalty 0b\mathchar 44\relax\penalty 0c\mathchar
44\relax\penalty 0d\mathchar 44\relax\penalty 0a^{2}+b^{2}\mathchar
44\relax\penalty 0bc+ad\mathchar 44\relax\penalty 0ac+bd\mathchar
44\relax\penalty 0c^{2}+d^{2}\mathchar 44\relax\penalty 0a^{2}+c^{2}\mathchar
44\relax\penalty 0ab+cd\mathchar 44\relax\penalty 0b^{2}+d^{2}\mathchar
44\relax\penalty 0a^{2}+d^{2}\mathchar 44\relax\penalty 0b^{2}+c^{2}\mathchar
44\relax\penalty 0a^{3}+ab^{2}+ac^{2}+ad^{2}\mathchar 44\relax\penalty
0a^{2}b+b^{3}+bc^{2}+bd^{2}\mathchar 44\relax\penalty
0a^{2}c+b^{2}c+c^{3}+cd^{2}\mathchar 44\relax\penalty
0a^{2}d+b^{2}d+c^{2}d+d^{3}\mathchar 44\relax\penalty
0a^{4}+b^{4}+c^{4}+d^{4}\\}$.

These minors have factors given by:

$T=\\{a\mathchar 44\relax\penalty 0b\mathchar 44\relax\penalty 0c\mathchar
44\relax\penalty 0d\mathchar 44\relax\penalty 0a+b\mathchar 44\relax\penalty
0bc+ad\mathchar 44\relax\penalty 0ac+bd\mathchar 44\relax\penalty
0c+d\mathchar 44\relax\penalty 0a+c\mathchar 44\relax\penalty 0ab+cd\mathchar
44\relax\penalty 0b+d\mathchar 44\relax\penalty 0a+d\mathchar 44\relax\penalty
0b+c\mathchar 44\relax\penalty 0a+b+c+d\\}.$

Therefore, $M$ is an MDS matrix if and only if each element in the set $T$ is
nonzero. This condition is satisfied if and only if
$(a,b,c,d)\in\mathbb{F}_{2^{r}}^{4}$ satisfies the conditions: (i)
$a,b,c,d\in\mathbb{F}_{2^{r}}^{\star}$, (ii) $a\neq b\neq c\neq d$, (iii)
$d\neq a^{-1}bc$, (iv) $d\neq ab^{-1}c$, (v) $d\neq abc^{-1}$, and (vi) $d\neq
a+b+c$. This completes the proof. ∎

###### Theorem 3.1

The count of $4\times 4$ Hadamard MDS matrices over the finite field
$\mathbb{F}_{2^{r}}$ is given by $(2^{r}-1)(2^{r}-2)(2^{r}-4)(2^{r}-7)$.

###### Proof

According to Lemma 2, the number of $4\times 4$ Hadamard MDS matrices over
$\mathbb{F}_{2^{r}}$ is equal to the cardinality of the set $S$, defined as:

$S=\\{(a\mathchar 44\relax\penalty 0b\mathchar 44\relax\penalty 0c\mathchar
44\relax\penalty 0d)\in(\mathbb{F}_{2^{r}}^{\star})^{4}:\leavevmode\nobreak\
a\neq b\neq c\neq d\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\ d\neq
a^{-1}bc\mathchar 44\relax\penalty 0\leavevmode\nobreak\ d\neq
ab^{-1}c\mathchar 44\relax\penalty 0\leavevmode\nobreak\ d\neq
abc^{-1}\mathchar 44\relax\penalty 0\leavevmode\nobreak\ d\neq a+b+c\\}$.

Since $a\in\mathbb{F}_{2^{r}}^{\star}$, there are $2^{r}-1$ possible choices
for $a$. Furthermore, with $b\in\mathbb{F}_{2^{r}}^{\star}$ and $a\neq b$,
there are $2^{r}-2$ possible choices for $b$. Similarly, for $c$, there are
$2^{r}-3$ possible choices.

Now, we will demonstrate that
$a^{-1}bc\not\in\set{b,c,ab^{-1}c,abc^{-1},a+b+c}$ for any choice of $a,b$ and
$c$.

Case 1: $a^{-1}bc=b$.
In this case, $a^{-1}bc=b$, which implies $a=c$. However, this contradicts our
assumptions.

Case 2: $a^{-1}bc=c$.
In this case, $a^{-1}bc=c$, which implies $a=b$, and this is a contradiction.

Case 3: $a^{-1}bc=ab^{-1}c$.
Now,

$\displaystyle a^{-1}bc=ab^{-1}c$ $\displaystyle\implies a^{2}=b^{2}$
$\displaystyle\implies a=b\leavevmode\nobreak\ [\text{Since characteristic
of}\leavevmode\nobreak\ \mathbb{F}_{2^{r}}\leavevmode\nobreak\
\text{is}\leavevmode\nobreak\ 2],$

which is a contradiction.

Case 4: $a^{-1}bc=abc^{-1}$.
Now,

$\displaystyle a^{-1}bc=abc^{-1}$ $\displaystyle\implies a^{2}=c^{2}$
$\displaystyle\implies a=c\leavevmode\nobreak\ [\text{Since characteristic
of}\leavevmode\nobreak\ \mathbb{F}_{2^{r}}\leavevmode\nobreak\
\text{is}\leavevmode\nobreak\ 2],$

which is a contradiction.

Case 5: $a^{-1}bc=ab^{-1}c$.
Now,

$\displaystyle a^{-1}bc=a+b+c$ $\displaystyle\implies a^{2}+ab+ac=bc$
$\displaystyle\implies(a+b)(a+c)=0$ $\displaystyle\implies
a=b\leavevmode\nobreak\ \text{or}\leavevmode\nobreak\ a=c.$

This again leads to a contradiction.

Therefore, we have $a^{-1}bc\not\in\set{b,c,ab^{-1}c,abc^{-1},a+b+c}$.

However, when $c=a^{2}b^{-1}$ (which is not equal to $a$ and not equal to
$b$), we have $a^{-1}bc=a$. In this case, there are $2^{r}-7$ choices for $d$.
For any other choices of $a,b$ and $c$, there are $2^{r}-8$.

Similarly, we can show the following:

  1. (i)

$ab^{-1}c\not\in\set{a,c,a^{-1}bc,abc^{-1},a+b+c}$ and when $c=b^{2}a^{-1}$
(which is not equal to $a$ and not equal to $b$), we have $ab^{-1}c=b$. In
this case, there are $2^{r}-7$ choices for $d$. For any other choices of $a,b$
and $c$, there are $2^{r}-8$.

  2. (ii)

$abc^{-1}\not\in\set{a,b,a^{-1}bc,ab^{-1}c,a+b+c}$. Since, the characteristic
of $\mathbb{F}_{2^{r}}$ is 2, $x\mapsto x^{2}$ is an isomorphism over
$\mathbb{F}_{2^{r}}$. Hence, there exist a unique element
$\alpha\in\mathbb{F}_{2^{r}}$ such that $\alpha^{2}=ab$. Now for $c=\alpha$
(which is not equal to $a$ and not equal to $b$), we have $abc^{-1}=c$. In
this case, there are $2^{r}-7$ choices for $d$. For any other choices of $a,b$
and $c$, there are $2^{r}-8$.

  3. (iii)

$a+b+c\notin\set{a,b,c,a^{-1}bc,ab^{-1}c,abc^{-1}}$. However, $a+b+c$ may
equal zero, and when $c=a+b$, we have $a+b+c=0$. In this case, there are
$2^{r}-7$ choices for $d$. For any other combinations of $a$, $b$, and $c$,
there are $2^{r}-8$ choices.

Therefore, there are $4$ choices of $c$ for which $d$ has $2^{r}-7$ choices,
whereas for any of the remaining $2^{r}-7$ choices of $c$, $d$ has $2^{r}-8$
choices. Hence, we have

$\displaystyle|S|$
$\displaystyle=(2^{r}-1)(2^{r}-2)[4.(2^{r}-7)+(2^{r}-7)(2^{r}-8)]$
$\displaystyle=(2^{r}-1)(2^{r}-2)(2^{r}-7)(4+2^{r}-8)$
$\displaystyle=(2^{r}-1)(2^{r}-2)(2^{r}-4)(2^{r}-7).$

Hence, the number of $4\times 4$ Hadamard MDS matrices over the finite field
$\mathbb{F}_{2^{r}}$ is equal to $(2^{r}-1)(2^{r}-2)(2^{r}-4)(2^{r}-7)$.∎

It is worth noting that the Hadamard matrix $\operatorname{Hada}(a,b,c,d)$
over $\mathbb{F}_{2^{r}}$ achieves involutory property if and only if the
condition $a+b+c+d=1$ is satisfied. Therefore, $\operatorname{Hada}(a,b,c,d)$
is an involutory MDS matrix if and only if it satisfies the following
conditions:

(i) $a,b,c,d\in\mathbb{F}_{2^{r}}^{\star}$, (ii) $a\neq b\neq c\neq d$, (iii)
$d\neq a^{-1}bc$, (iv) $d\neq ab^{-1}c$, (v) $d\neq abc^{-1}$, (vi) $d\neq
a+b+c$, and (vii) $d=a+b+c+1$.

Therefore, the number of $4\times 4$ involutory Hadamard MDS matrices over
$\mathbb{F}_{2^{r}}$ is equal to the cardinality of the set $T$, defined as:

$T=\\{(a\mathchar 44\relax\penalty 0b\mathchar 44\relax\penalty 0c\mathchar
44\relax\penalty 0d)\in(\mathbb{F}_{2^{r}}^{\star})^{4}:\leavevmode\nobreak\
d=a+b+c+1\mathchar 44\relax\penalty 0\text{and}\leavevmode\nobreak\ a\neq
b\neq c\neq d\mathchar 44\relax\penalty 0\leavevmode\nobreak\ d\neq
a^{-1}bc\mathchar 44\relax\penalty 0\leavevmode\nobreak\ d\neq
ab^{-1}c\mathchar 44\relax\penalty 0\leavevmode\nobreak\ d\neq abc^{-1}\\}$.

###### Conjecture 1

The count of $4\times 4$ involutory Hadamard MDS matrices over the finite
field $\mathbb{F}_{2^{r}}$ is given by $(2^{r}-2)(2^{r}-4)(2^{r}-7)$.

We have empirically verified this conjecture for various finite fields
$\mathbb{F}_{2^{r}}$ with $3\leq r\leq 7$. However, a proof of its validity is
currently lacking.

##  4 $2n\times 2n$ involutory MDS matrices

In this section, we first present a general form for all $2n\times 2n$
involutory MDS matrices over $\mathbb{F}_{2^{r}}$. Then, we determine the
exact count of $2\times 2$ MDS and involutory MDS matrices over
$\mathbb{F}_{2^{r}}$. Using these counts, we establish an upper bound for the
enumeration of all $4\times 4$ involutory MDS matrices over
$\mathbb{F}_{2^{r}}$.

###### Lemma 3

Let $M=\begin{bmatrix}A_{1}&A_{2}\\\ A_{3}&A_{4}\end{bmatrix}$ be a $2n\times
2n$ involutory MDS matrix, where $A_{i}$ are $n\times n$ matrices. Then $M$
can be expressed in the form $M=DHD^{-1}$, where
$H=\begin{bmatrix}A_{1}&I_{n}+A_{1}\\\ I_{n}+A_{1}&A_{1}\end{bmatrix}$ and $D$
is the block diagonal matrix
$\operatorname{diag}(I_{n},A_{3}(I_{n}+A_{1})^{-1})$.

###### Proof

Since $M$ is involutory we have

$\displaystyle A_{1}^{2}+A_{2}A_{3}=I_{n},$ $\displaystyle
A_{1}A_{2}+A_{2}A_{4}=\mathbf{0},$ $\displaystyle
A_{3}A_{1}+A_{4}A_{3}=\mathbf{0},$ $\displaystyle A_{3}A_{2}+A_{4}^{2}=I_{n}.$
$\displaystyle\implies$ $\displaystyle A_{2}=(I_{n}+A_{1}^{2})A_{3}^{-1}$
$\displaystyle A_{4}=A_{3}A_{1}A_{3}^{-1}.$

Now, as $M$ is an MDS matrix, it cannot contain any zero entries. Hence, we
must have $A_{1}\neq I_{n}$. Therefore, $M$ can be expressed as:

$\displaystyle M$
$\displaystyle=\begin{bmatrix}A_{1}&(I_{n}+A_{1}^{2})A_{3}^{-1}\\\
A_{3}&A_{3}A_{1}A_{3}^{-1}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}I_{n}&\mathbf{0}\\\
\mathbf{0}&A_{3}(I_{n}+A_{1})^{-1}\end{bmatrix}\begin{bmatrix}A_{1}&I_{n}+A_{1}\\\
I_{n}+A_{1}&A_{1}\end{bmatrix}\begin{bmatrix}I_{n}&\mathbf{0}\\\
\mathbf{0}&(I_{n}+A_{1})A_{3}^{-1}\end{bmatrix}$ $\displaystyle=DHD^{-1},$

where $H$ is the block matrix $\begin{bmatrix}A_{1}&I_{n}+A_{1}\\\
I_{n}+A_{1}&A_{1}\end{bmatrix}$ and $D$ is the block diagonal matrix
$\operatorname{diag}(I_{n},A_{3}(I_{n}+A_{1})^{-1})$.∎

###### Lemma 4

The count of $2\times 2$ MDS matrices over the finite field
$\mathbb{F}_{2^{r}}$ is given by $(2^{r}-1)^{3}(2^{r}-3)$.

###### Proof

Let $M=\begin{bmatrix}a&b\\\ c&d\end{bmatrix}$ be an MDS matrix over
$\mathbb{F}_{2^{r}}$. Note that $a$, $b$, $c$, and $d$ all belong to the
nonzero elements of the finite field $\mathbb{F}_{2^{r}}$. Also,
$\det(M)=ad+bc$ must be nonzero. This implies that $d\neq a^{-1}bc$.
Consequently, each of the values $a$, $b$, and $c$ can be chosen from
$2^{r}-1$ possibilities, as they are drawn from the nonzero elements of
$\mathbb{F}_{2^{r}}$. On the other hand, $d$ can be selected from $2^{r}-2$
possibilities because it cannot be equal to $a^{-1}bc$. Hence, the total
number of $2\times 2$ MDS matrices can be calculated as
$(2^{r}-1)^{3}(2^{r}-2)$.∎

###### Lemma 5

The count of $2\times 2$ involutory MDS matrices over the finite field
$\mathbb{F}_{2^{r}}$ is given by $(2^{r}-1)(2^{r}-2)$.

###### Proof

According to Lemma 3, any $2\times 2$ involutory MDS matrix $M$ can be
represented as $M=DHD^{-1}$, where $H$ is the $2\times 2$ Hadamard matrix
$\operatorname{Hada}(\alpha,1+\alpha)$, and $D$ is a nonsingular diagonal
matrix $\operatorname{diag}(1,(1+\alpha)\beta^{-1})$, with
$\alpha,\beta\in\mathbb{F}_{2^{r}}^{\star}$. Also, from Corollary 1, we can
say that $M$ is an involutory MDS if and only if $H$ is an involutory MDS.

Regarding $H$, there are $2^{r}-2$ possible choices since
$\alpha\not\in\set{0,1}$. On the other hand, $D$ provides $2^{r}-1$ options.
Therefore, the total number of $2\times 2$ involutory MDS matrices is
$(2^{r}-1)(2^{r}-2)$.∎

In Conjecture 1, we provide the count of $4\times 4$ involutory Hadamard MDS
matrices. Next, we establish an upper bound for the enumeration of all
$4\times 4$ involutory MDS matrices.

###### Theorem 4.1

The number of $4\times 4$ involutory MDS matrices over the finite field
$\mathbb{F}_{2^{r}}$ is upper bounded by
$2^{r}(2^{r}-1)^{3}(2^{r}-2)^{2}(2^{r}-3)(2^{r}-4)$.

###### Proof

From Lemma 3, we can deduce that any $4\times 4$ involutory MDS matrix $M$ can
be expressed as:

$\displaystyle M=\begin{bmatrix}A_{1}&(I_{n}+A_{1}^{2})A_{3}^{-1}\\\
A_{3}&A_{3}A_{1}A_{3}^{-1}\end{bmatrix},$

where both $A_{1}$ and $A_{3}$ are $2\times 2$ MDS matrices. Additionally,
$A_{1}$ cannot be an involutory matrix. Therefore, by considering both Lemma 4
and Lemma 5, we can conclude that $A_{1}$ has a total of
$(2^{r}-1)^{3}(2^{r}-2)-(2^{r}-1)(2^{r}-2)=2^{r}(2^{r}-1)(2^{r}-2)^{2}$
possible choices.

Each row of $A_{3}$ must be linearly independent with the rows of $A_{1}$.
Since $A_{3}$ is a $2\times 2$ MDS matrix, there are $(2^{r}-1)(2^{r}-3)$
possible choices for the first row of $A_{3}$ and $(2^{r}-1)(2^{r}-4)$
possible choices for the second row. Thus, $A_{3}$ has a total of
$(2^{r}-1)^{2}(2^{r}-3)(2^{r}-4)$ possible choices. Hence, the number of
$4\times 4$ involutory MDS matrices over the finite field $\mathbb{F}_{2^{r}}$
is upper bounded by $2^{r}(2^{r}-1)^{3}(2^{r}-2)^{2}(2^{r}-3)(2^{r}-4)$.∎

It is essential to emphasize that the upper bound we have derived in Theorem
4.1 is not a precise one. This is because our calculation only considers cases
involving $2\times 2$ submatrices constructed from $A_{1}$ and $A_{3}$. To
achieve a more precise bound, it is necessary to examine the other $2\times 2$
submatrices as well as all $3\times 3$ submatrices. However, currently, we are
unable to exclude these potential cases from our analysis.

Also, as stated in Lemma 3, we can represent any $4\times 4$ involutory MDS
matrix $M$ as $M=DHD^{-1}$, where $H$ is a $4\times 4$ involutory matrix.
However, it is important to note that in this context, $D$ is not a standard
diagonal matrix but rather a diagonal block matrix. Consequently, unlike Lemma
5 for $2\times 2$ involutory MDS matrices, we cannot directly apply Corollary
1 to assert that $M$ is MDS if and only if $H$ is MDS. Furthermore,
considering the specific form of $H$, it cannot be considered an MDS matrix.

##  5 Conclusion

This paper has concentrated on two main objectives. First, we have enumerated
Hadamard MDS matrices with an order of 4 within the field $\mathbb{F}_{2^{r}}$
and proposed a conjecture regarding the count of involutory Hadamard MDS
matrices over the same field. Additionally, we have established an upper limit
for the number of involutory MDS matrices with an order of 4 over
$\mathbb{F}_{2^{r}}$. However, it is important to note that the upper bound we
have calculated is not a precise one. Consequently, determining the exact
count of $4\times 4$ involutory MDS matrices or achieving a tighter bound is a
potential avenue for future research.

## References

  * [1] Paulo S.L.M. Barreto and Vincent Rijmen.  The ANUBIS Block Cipher.  Submission to the NESSIE Project, 2000., 2000.
  * [2] Paulo S.L.M. Barreto and Vincent Rijmen.  The KHAZAD Legacy-Level Block Cipher.  Submission to the NESSIE Project, 2000., 2000.
  * [3] Kishan Chand Gupta, Sumit Kumar Pandey, Indranil Ghosh Ray, and Susanta Samanta.  Cryptographically significant MDS matrices over finite fields: A brief survey and some generalized results.  Advances in Mathematics of Communications, 13(4):779–843, 2019\.
  * [4] Gülsüm Gözde Güzel, Muharrem Tolga Sakallı, Sedat Akleylek, Vincent Rijmen, and Yasemin Çengellenmiş.  A new matrix form to generate all $3\times 3$ involutory MDS matrices over $\mathbb{F}_{2^{m}}$.  Information Processing Letters, 147:61–68, 2019.
  * [5] F.J. MacWilliams and N.J.A. Sloane.  The Theory of Error Correcting Codes.  North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
  * [6] C. E. Shannon.  Communication theory of secrecy systems.  The Bell System Technical Journal, 28(4):656–715, 1949.
  * [7] Taizo Shirai, Kyoji Shibutani, Toru Akishita, Shiho Moriai, and Tetsu Iwata.  The 128-bit Blockcipher CLEFIA (Extended Abstract).  In Alex Biryukov, editor, Fast Software Encryption, pages 181–195, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.