#  Maximum-order complexity and $2$-adic complexity

Zhiru Chen1, Zhixiong Chen2, Jakob Obrovsky3 and Arne Winterhof3

1 State Key Laboratory of Information Security,
Institute of Information Engineering,
Chinese Academy of Sciences, Beijing, China
2 Fujian Key Laboratory of Financial Information Processing,
Putian University, Putian, Fujian 351100, P. R. China
3 Johann Radon Institute for Computational and Applied Mathematics,
Austrian Academy of Sciences, Linz, Austria

###### Abstract

The $2$-adic complexity has been well-analyzed in the periodic case. However,
we are not aware of any theoretical results on the $N$th $2$-adic complexity
of any promising candidate for a pseudorandom sequence of finite length $N$ or
results on a part of the  period of length $N$ of a periodic sequence,
respectively. Here we introduce the first method for this aperiodic case. More
precisely, we study the relation between $N$th maximum-order complexity and
$N$th $2$-adic complexity of binary sequences and prove a lower bound on the
$N$th $2$-adic complexity in terms of the $N$th maximum-order complexity. Then
any known lower bound on the $N$th maximum-order complexity implies a lower
bound on the $N$th $2$-adic complexity of the same order of magnitude. In the
periodic case, one can prove a slightly better result. The latter bound is
sharp which is illustrated by the maximum-order complexity of
$\ell$-sequences. The idea of the proof helps us to characterize the maximum-
order complexity of periodic sequences in terms of the unique rational number
defined by the sequence. We also show that a periodic sequence of maximal
maximum-order complexity must be also of maximal $2$-adic complexity.

Dedicated to the memory of Kai-Uwe Schmidt (1978-2023)

Keywords. Pseudorandom sequences, maximum-order complexity, $2$-adic
complexity, $\ell$-sequences

2020 MSC: Primary: 94A55; Secondary: 11T71, 94A05, 94A60

##  1 Introduction

Pseudorandom sequences are generated by deterministic algorithms and are not
random at all. However, both from an academic point of view as well as from a
cryptographic point of view they should have as many desirable features of
randomness as possible, that is, they should not be distinguishable from a
’truly’ random sequence. These desirable features and thus the
pseudorandomness of binary sequences can be analyzed via several measures of
pseudorandomness such as the maximum-order complexity and the $2$-adic
complexity, see for example the recent survey [35]. We recall the definitions
of the $N$th maximum-order complexity and the $N$th $2$-adic complexity.

For a positive integer $N$, the _$N$ th maximum-order complexity_ (or _$N$ th
nonlinear complexity_) $M(\mathcal{S},N)$ of a binary sequence
$\mathcal{S}=(s_{n})_{n\geq 0}$ over the two-element field
$\mathbb{F}_{2}=\\{0,1\\}$ is defined as the smallest positive integer
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}m}$
such that there is a polynomial
$f(X_{1},\ldots,X_{m})\in\mathbb{F}_{2}[X_{1},\ldots,X_{m}]$ with

$s_{i+m}=f(s_{i},s_{i+1},\ldots,s_{i+m-1})\quad\mbox{ for }0\leq i\leq N-m-1,$

see [1, 12, 10, 11, 14, 21, 22, 23, 25, 26, 31, 36]. We set
$M(\mathcal{S},N)=0$ if $s_{0}=s_{1}=\ldots=s_{N-2}=s_{N-1}$, that is
$s_{i}=s_{0}$ for $0\leq i\leq N-1$, and $M(\mathcal{S},N)=N-1$ if
$s_{0}=s_{1}=\ldots=s_{N-2}\neq s_{N-1}$, that is $s_{i+N-1}=s_{i}+1$, $i=0$.

The sequence $(M(\mathcal{S},N))_{N\geq 1}$ is referred to as the _maximum-
order complexity profile_ (or _nonlinear complexity profile_) of
$\mathcal{S}$. If $\mathcal{S}$ is $T$-periodic,  that is, $s_{n+T}=s_{n}$ for
$n\geq 0$, we have $M(\mathcal{S},N)=M(\mathcal{S},2T-1)$ for $N\geq 2T$. This
number is called the _maximum-order complexity_ (or _nonlinear complexity_) of
$\mathcal{S}$ and it is denoted by $M(\mathcal{S})$.  In other words, the
maximum-order complexity is the length of a shortest (possibly nonlinear)
feedback shift register. It is well-known that $M(\mathcal{S})\leq T-1$.

In particular, restricting only to the homogeneous polynomials
$f(X_{1},\ldots,X_{m})$ of degree one leads to the notion of the _$N$ th
linear complexity_ $L(\mathcal{S},N)$, the _linear complexity_
$L(\mathcal{S})=L(\mathcal{S},2T)\leq T$ and the _linear complexity profile_
$(L(\mathcal{S},N))_{N\geq 1}$ of $\mathcal{S}$, respectively. See the list of
surveys [16, 20, 34]. The $N$th maximum-order complexity as well as the $N$th
linear complexity are measures for the unpredictability of a sequence and thus
its suitability in cryptography.

The $2$-adic complexity introduced by Goresky and Klapper [5, 13] is closely
related to the length of a shortest feedback with carry shift register (FCSR)
which generates the sequence. The theory of $2$-adic complexity has been very
well developed for the periodic case. More precisely, any $T$-periodic binary
sequence $\mathcal{S}=(s_{n})_{n\geq 0}$ uniquely corresponds to the rational
number

$\sum\limits_{n=0}^{\infty}s_{n}2^{n}=-\frac{\sum_{n=0}^{T-1}s_{n}2^{n}}{2^{T}-1}=-\frac{A}{q},$
(1)

where $0\leq A\leq q$, $\gcd(A,q)=1$ and

$q=\frac{2^{T}-1}{\gcd\left(2^{T}-1,\sum_{n=0}^{T-1}s_{n}2^{n}\right)},$

which is called the (minimal) _connection integer_ of $\mathcal{S}$ [5]. Then
the _$2$ -adic complexity_ of $\mathcal{S}$, denoted by
$\Phi_{2}(\mathcal{S})$, is the binary logarithm $\log_{2}(q)$ of $q$.

In the aperiodic case, the _$N$ th $2$-adic complexity_, denoted by
$\Phi_{2}(\mathcal{S},N)$, is the binary logarithm of

$\min\left\\{\max\\{|f|,|q|\\}:f,q\in\mathbb{Z},q\mbox{ odd
},q\sum_{n=0}^{N-1}s_{n}2^{n}\equiv f\pmod{2^{N}}\right\\},$

see [5, p.328] or [35].  It is trivial that
$\Phi_{2}(\mathcal{S},N)\leq\Phi_{2}(\mathcal{S},N+1)$ for $N\geq 1$. The
average behavior of the $2$-adic complexity and some asymptotic behavior of
the $N$th $2$-adic complexity (more generally of the $d$-adic complexity of
$d$-ary sequences, $d\geq 2$) are considered in Chapter 18.2 and Chapter 18.5
of [5], respectively.

However, it seems that there are no results known on the relation between the
$N$th $2$-adic complexity and other complexity measures. Moreover, in contrast
to the periodic case no results are known on the $N$th $2$-adic complexity of
any attractive candidate for a pseudorandom sequence,  that is a sequence with
some (proved) desirable features and no known undesirable feature of
pseudorandomness. Here we introduce the first theoretic method to study the
aperiodic case, more precisely, we transfer  some known results on the $N$th
maximum-order complexity to the $N$th $2$-adic complexity. This leads to the
main contribution of this work, that is, we will prove in Sections 2 and 3 the
following inequalities

$M(\mathcal{S},N)\leq\left\lceil\Phi_{2}(\mathcal{S},N)\right\rceil+1,\quad
N\geq 1,$

in the non-periodic case and

$M(\mathcal{S})\leq\lceil\Phi_{2}(\mathcal{S})\rceil$ (2)

if $\mathcal{S}$ is periodic, where $\left\lceil x\right\rceil$ is the
smallest integer $\geq x$. The first inequality also implies a relation
between the correlation measure of order $k$ and the $2$-adic complexity, see
Corollary 1. Below we will also use $\left\lfloor x\right\rfloor$ for the
largest integer $\leq x$. We apply these bounds to several sequences including
the Thue-Morse sequence along squares and the Legendre sequence. In addition,
in the periodic case the idea of the proof of Eq.(2) leads to a
characterization of the maximum-order complexity in terms of the rational
number $-A/q$ defined by (1), which is stated in Subsection 4.1. As a
consequence, we prove in Subsection 4.2 the maximality of the maximum-order
complexity of binary $\ell$-sequences , which are those sequences for which
the connection integer $q$ is a power of an odd prime such that $2$ is a
primitive root modulo $q$, see [5, Chapter 13]. The result indicates that the
bound in Eq.(2) is sharp. In Section 4.3 we show that any periodic sequence
with maximal maximum-order complexity has also maximal $2$-adic complexity.

We will use the notation $f(N)=\mathcal{O}(g(N))$ if $|f(N)|\leq cg(N)$ for
some constant $c>0$ and $f(N)=o(g(N))$ if
$\lim\limits_{N\rightarrow\infty}\frac{f(N)}{g(N)}=0$. Sometimes we also use
$f(N)\ll g(N)$ and $g(N)\gg f(N)$ instead of $f(N)=\mathcal{O}(g(N))$.

##  2 $N$th Maximum-order complexity and $N$th $2$-adic complexity

In this section we prove a relation between the $N$th maximum-order complexity
$M(\mathcal{S},N)$ and the $N$th $2$-adic complexity $\Phi_{2}(\mathcal{S},N)$
and apply it to several prominent sequences.

######  Theorem 1.

Let $\mathcal{S}=(s_{n})_{n\geq 0}$ be a binary sequence. Then we have

$M(\mathcal{S},N)\leq\left\lceil\Phi_{2}(\mathcal{S},N)\right\rceil+1$

for $N\geq 1$.

Proof. Since otherwise the result is trivial we may assume

$M(\mathcal{S},N)\geq 2$

and put $m=M(\mathcal{S},N)-1$. Then there exist $i,j$ with

$0\leq i<j\leq N-1-m$ (3)

and

$(s_{i},s_{i+1},\ldots,s_{i+m-1})=(s_{j},s_{j+1},\ldots,s_{j+m-1}),\quad
s_{i+m}\not=s_{j+m},$ (4)

by [11, Prop. 1], see also [27, Thm. 2].

Put

$S(2)=\sum_{n=0}^{N-1}s_{n}2^{n}$

and for $0\leq k<N$

$S_{k}(2)=\sum_{n=0}^{N-1-k}s_{n+k}2^{n}=2^{-k}\left(S(2)-\sum_{n=0}^{k-1}s_{n}2^{n}\right).$

Then we have for $i,j$ with $0\leq i<j\leq N-1-m$ chosen above to satisfy (4),

$S_{i}(2)\equiv\sum_{n=0}^{m}s_{n+i}2^{n}\equiv S_{j}(2)+2^{m}\pmod{2^{m+1}}$

and thus

$\displaystyle 2^{j-i}\left(S(2)-\sum_{n=0}^{i-1}s_{n}2^{n}\right)$
$\displaystyle\equiv$ $\displaystyle 2^{j}S_{i}(2)\equiv
2^{j}S_{j}(2)+2^{m+j}$ (5) $\displaystyle\equiv$ $\displaystyle
S(2)-\sum_{n=0}^{j-1}s_{n}2^{n}+2^{m+j}\pmod{2^{m+j+1}}.$

Note that $\Phi_{2}(\mathcal{S},N)\geq\Phi_{2}(\mathcal{S},m+j+1)$ by (3) and
assume

$\Phi_{2}(\mathcal{S},m+j+1)=c$

for some $c\geq 0$, that is, there are integers $q$ and $h$, where $q$ is odd,
with

$\max\\{|h|,|q|\\}=2^{c}$ (6)

and

$\displaystyle qS(2)\equiv h\pmod{2^{m+j+1}}.$ (7)

With (5) multiplied by $q$ and (7), we get

$2^{j-i}\left(h-q\sum_{n=0}^{i-1}s_{n}2^{n}\right)\equiv
h-q\sum_{n=0}^{j-1}s_{n}2^{n}+2^{m+j}\pmod{2^{m+j+1}},$

that is

$2^{m+j}\equiv(2^{j-i}-1)h+q\left(\sum_{n=0}^{j-1}s_{n}2^{n}-\sum_{n=0}^{i-1}s_{n}2^{n+j-i}\right)\pmod{2^{m+j+1}}.$

Since

$\left|\sum_{n=0}^{j-1}s_{n}2^{n}-\sum_{n=0}^{i-1}s_{n}2^{n+j-i}\right|\leq\max\left\\{\sum_{n=0}^{j-1}2^{n},\sum_{n=0}^{i-1}2^{n+j-i}\right\\}=2^{j}-1$

and by (6) the right hand side is of absolute value at most

$2^{c+1}(2^{j}-1),$

which is not possible if $c\leq m-1$. Hence, we get

$\left\lceil\Phi_{2}(\mathcal{S},N)\right\rceil{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\geq\Phi_{2}(\mathcal{S},N)}\geq
c>m-1=M(\mathcal{S},N)-2$

and the result follows.  Note that we cannot deduce
$\Phi_{2}(\mathcal{S},N)\geq M(\mathcal{S},N)-1$ since
$\Phi_{2}(\mathcal{S},N)$ may be no integer. ∎

According to Theorem 1, a lower bound on $M(\mathcal{S},N)$ implies a lower
bound on $\Phi_{2}(\mathcal{S},N)$. Below we state several classes of
sequences with known lower bounds on the $N$th maximum-order complexity which
can now be interpreted as lower bounds on the $N$th $2$-adic complexity as
well.

Pattern sequences (along squares/polynomial values):
For a positive integer $k$, the pattern sequence ${\cal P}_{k}=(p_{n})_{n\geq
0}$ over ${\mathbb{F}}_{2}$ is defined by

$p_{n}=\left\\{\begin{array}[]{cl}p_{\lfloor n/2\rfloor}+1,&\mbox{if
}n\equiv-1\pmod{2^{k}},\\\ p_{\lfloor
n/2\rfloor},&\mbox{otherwise},\end{array}\right.\quad n=1,2,\ldots$

with initial value $p_{0}=0$. Equivalently, $p_{n}$ is the parity of the
number of occurrences of the all one pattern of length $k$ in the binary
expansion of $n$. For $k=1$ we get the _Thue-Morse sequence_ ${\cal
T}=(t_{n})_{n\geq 0}$ and for $k=2$ the Rudin-Shapiro sequence ${\cal
R}=(r_{n})_{n\geq 0}$.

We get

$\left\lceil\Phi_{2}(\mathcal{T},N)\right\rceil\geq\frac{N}{5},\quad N\geq 4,$

and

$\left\lceil\Phi_{2}(\mathcal{P}_{k},N)\right\rceil\geq\frac{N}{6},\quad N\geq
2^{k+3}-7,\quad k\geq 2,$

from the lower bounds on the maximum-order complexity in [29]. Note that
despite of a large $N$th maximum-order complexity and a large $N$th $2$-adic
complexity, the pattern sequences ${\cal P}_{k}$ are highly predictable which
can be measured in terms of a very small expansion complexity and a very large
autocorrelation, see for example [17]. However, subsequences along polynomial
values still keep the former desirable features but lose the latter
undesirable ones.

For the Thue-Morse sequence along squares ${\cal
T}^{\prime}=(t_{n^{2}})_{n\geq 0}$ and the pattern sequence along squares
${\cal P}^{\prime}_{k}=(p_{n^{2}})_{n\geq 0}$, we get

$\left\lceil\Phi_{2}(\mathcal{T}^{\prime},N)\right\rceil\geq\sqrt{\frac{2N}{5}}-1,$

and

$\left\lceil\Phi_{2}(\mathcal{P}^{\prime}_{k},N)\right\rceil\geq\sqrt{\frac{N}{8}}-1,\quad
N\geq 2^{2k+2},\quad k\geq 2,$

from the bounds in [30].

For $k\geq 1$ and the pattern sequence along polynomial values of $f(X)$,
${\cal P}^{\prime\prime}_{k}=(p_{f(n)})_{n\geq 0}$, where
$f(X)\in\mathbb{Z}[X]$ is a monic polynomial of degree $d\geq 2$ with
$f(n)\geq 0$ for $n\geq 0$, we get
$\Phi_{2}(\mathcal{P}^{\prime\prime}_{k},N)\gg N^{1/d}$, where the implied
constants depend on $f(X)$ and $k$, see [24].

Sequence of the sum of digits in Zeckendorf base:
Let $F_{0}=0,F_{1}=1$ and $F_{i+2}=F_{i+1}+F_{i}$ for all $i\geq 0$, which
forms the Fibonacci sequence. Each integer $n\geq 0$ can be represented
uniquely by

$n=\sum_{i\geq 0}\varepsilon_{i}(n)F_{i+2},$

with $\varepsilon_{i}(n)\in\\{0,1\\}$ and
$\varepsilon_{i}(n)\varepsilon_{i+1}(n)=0$ for all $i\geq 0$. Then the
_Zeckendorf base sum of digits function_ is defined by

$s_{Z}(n)=\sum_{i\geq 0}\varepsilon_{i}(n),~{}~{}n\geq 0.$

For the binary sequence of the Zeckendorf base sum of digits function ${\cal
U}=(u_{n})_{n\geq 0}$ with $u_{n}=s_{Z}(n)\bmod 2$ and the binary sequence
along polynomial values of the Zeckendorf base sum of digits function ${\cal
U}^{\prime}=(u_{f(n)})_{n\geq 0}$ with $u_{f(n)}=s_{Z}(f(n))\bmod 2$, where
$f(x)\in\mathbb{Z}[x]$ is a monic polynomial of degree $d\geq 2$ with
$f(n)\geq 0$ for $n\geq 0$, we get $\Phi_{2}(\mathcal{U},N)\gg N$ and
$\Phi_{2}(\mathcal{U}^{\prime},N)\gg N^{1/(2d)}$, see [9].

For the Thue-Morse sequence, the Rudin-Shapiro sequence (both along the values
of $f(X)\in\\{X,X^{2},X^{3},X^{4}\\}$) and the binary sequence of the
Zeckendorf base sum of digits function , we calculated the $N$th $2$-adic
complexity up to $N=1\,000\,000$ which leads in all cases to the conjecture
that $\Phi_{2}(\mathcal{S},N)=\frac{N}{2}+\mathcal{O}(\log N)$.

We can also combine Theorem 1 and [1, Theorem 5] to get a lower bound on the
$N$th $2$-adic complexity in terms of the $N$th correlation measure
$C_{2}({\cal S},N)$ of order $2$ introduced by Mauduit and Sárközy [15]. More
precisely, for $k\geq 2$ the $N$th correlation measure $C_{k}({\cal S},N)$ of
order $k$ of $\mathcal{S}=(s_{n})_{n\geq 0}$ is

$C_{k}({\cal
S},N)=\max_{U,D}\left|\sum_{i=0}^{U-1}(-1)^{s_{i+d_{1}}+s_{i+d_{2}}+\ldots+s_{i+d_{k}}}\right|,$

where the maximum is taken over all $D=(d_{1},d_{2},\ldots,d_{k})$ and $U$
such that $0\leq d_{1}<d_{2}<\cdots<d_{k}\leq N-U$. Then we have

$C_{2}(\mathcal{S},N)\geq N-2^{M({\cal S},N)}+1$

and the following result follows.

######  Corollary 1.

Let $\mathcal{S}=(s_{n})_{n\geq 0}$ be a binary sequence. Then we have

$\left\lceil\Phi_{2}({\cal S},N)\right\rceil\geq\log_{2}\left(N+1-C_{2}({\cal
S},N)\right)-1.$

In particular, if $C_{2}({\cal S},N)=o(N)$, then we have

$\left\lceil\Phi_{2}({\cal S},N)\right\rceil\geq\log_{2}(N)-1+o(1).$

As an example we apply this relation to the Legendre sequence (along
polynomial values):
For an odd prime $p$ and a squarefree polynomial $f(X)\in\mathbb{F}_{p}[X]$ of
degree $d$, the $p$-periodic Legendre sequence $\mathcal{L}=(\ell_{n})_{n\geq
0}$ along the values of $f(X)$ is defined by

$\ell_{n}=\left\\{\begin{array}[]{cl}1,&\mbox{if
}\left(\frac{f(n)}{p}\right)=1,\\\ 0,&\mbox{otherwise},\end{array}\right.\quad
n\geq 0,$

where $\left(\frac{\cdot}{p}\right)$ is the Legendre symbol. By [15] we have

$C_{2}(\mathcal{L},N)\ll dp^{1/2}\log p,\quad 1\leq N\leq p.$

and get

$\Phi_{2}(\mathcal{L},N)\geq\log_{2}(\min\\{N,p\\})-1+o(1)\quad\mbox{if
}dp^{1/2}\log p=o(N).$

For the Legendre sequence with $f(X)=X$, it is conjectured that
$\Phi_{2}(\mathcal{L},N)=\min\\{N/2,\Phi_{2}(\mathcal{L})\\}+\mathcal{O}(\log
N)$, which we tested for all primes $p<50\,000$, where
$\Phi_{2}(\mathcal{L})=\log_{2}(2^{p}-1)$, see [7, Theorem 2], [37, Theorem 3]
and [8].

##  3 A relation between maximum-order complexity and $2$-adic complexity for
periodic sequences

Now we turn to consider the case of periodic sequences. First we prove the
following result, which is similar to the corresponding result for the
maximum-order complexity of a $T$-periodic sequence $\mathcal{S}$,
$M(\mathcal{S})=M(\mathcal{S},2T-1)$.

######  Lemma 1.

Let $\mathcal{S}=(s_{n})_{n\geq 0}$ be a binary sequence of period $T$. Then
the $2$-adic complexity $\Phi_{2}(\mathcal{S})$ satisfies

$\Phi_{2}(\mathcal{S})=\Phi_{2}(\mathcal{S},2T+1)=\Phi_{2}(\mathcal{S},N)$

for any $N>2T$.

Proof. Let $\mathcal{S}$ correspond to the rational number

$\sum\limits_{n=0}^{\infty}s_{n}2^{n}=-\frac{\sum_{n=0}^{T-1}s_{n}2^{n}}{2^{T}-1}=-\frac{f}{q},$

with $0\leq f\leq q$ and $\gcd(f,q)=1$. It is clear that $q<2^{T}$ and $q$ is
odd.

Assume $N>2T$ and that there are integers $\widetilde{f}$ and odd
$\widetilde{q}$ with

$\max\\{|\widetilde{f}|,|\widetilde{q}|\\}<q<2^{T}$

and

$\widetilde{q}\sum_{n=0}^{N-1}s_{n}2^{n}\equiv\widetilde{f}\pmod{2^{N}}.$

We obtain

$-\frac{f}{q}\equiv\frac{\widetilde{f}}{\widetilde{q}}\pmod{2^{N}},\mbox{ that
is, }-\widetilde{q}f\equiv q\widetilde{f}\pmod{2^{N}}.$

Since $|q\widetilde{f}+\widetilde{q}f|<2^{2T+1}\leq 2^{N}$, we derive
$\widetilde{q}f+q\widetilde{f}=0$. This leads to $q|\widetilde{q}$, which is
impossible due to the assumption $|\widetilde{q}|<q$. Thus we get
$\Phi_{2}(\mathcal{S},N)=\log_{2}(q)=\Phi_{2}(\mathcal{S})$ for $N>2T$, which
completes the proof. ∎

Note that we may have $\Phi_{2}(\mathcal{S},2T)<\Phi_{2}(\mathcal{S})$. For
example, consider the $5$-periodic sequence starting with $(0,1,0,0,1)$ which
is the binary expansion of $18$. Since $\gcd(2^{5}-1,18)=1$ we get
$\Phi_{2}(\mathcal{S})=\log_{2}(31)$. However, we have

$19\cdot 18\cdot(1+2^{5})\equiv 22\pmod{2^{10}},$

may take $q=19$ and $f=22$ and thus get

$\Phi_{2}(\mathcal{S},10)\leq\log_{2}(22)<\Phi_{2}(\mathcal{S}).$

So Theorem 1 and Lemma 1 indicate

$\displaystyle M(\mathcal{S})$ $\displaystyle=$ $\displaystyle
M(\mathcal{S},2T-1)$ $\displaystyle\leq$
$\displaystyle\left\lceil\Phi_{2}(\mathcal{S},2T-1)\right\rceil+1\leq\left\lceil\Phi_{2}(\mathcal{S},2T+1)\right\rceil+1=\left\lceil\Phi_{2}(\mathcal{S})\right\rceil+1.$

Below we prove a slightly stricter bound in another way (for the periodic
case).

######  Theorem 2.

Let $\mathcal{S}=(s_{n})_{n\geq 0}$ be a binary sequence of period $T$. Then
we have

$M(\mathcal{S})\leq\left\lceil\Phi_{2}(\mathcal{S})\right\rceil.$

Proof. According to [26, Prop. 2], we will compute the minimum integer $k$,
which equals to the maximum-order complexity $M(\mathcal{S})$, such that all
($T$ many) subsequences of length $k$:

$(s_{0},s_{1},\ldots,s_{k-1}),~{}~{}(s_{1},s_{2},\ldots,s_{k}),\ldots,(s_{T-1},s_{0},\ldots,s_{k-2})$

are distinct.

Let

$\sum\limits_{n=0}^{\infty}s_{n}2^{n}=-\frac{\sum_{n=0}^{T-1}s_{n}2^{n}}{2^{T}-1}=-\frac{f}{q},$

with $0\leq f\leq q$ and $\gcd(f,q)=1$. Then
$\Phi_{2}(\mathcal{S})=\log_{2}(q)$. Below we prove the statement in terms of
$\log_{2}(q)$.

If $T=1$, that is, $\mathcal{S}$ is constant, we derive $q=1$ and
$M(\mathcal{S})=0=\log_{2}(1)=\Phi_{2}(\mathcal{S})$.

Below we suppose $T\geq 2$ and in this case we have $0<f<q$. Now we assume
that $T>\left\lceil\log_{2}(q)\right\rceil$, since otherwise the result is
trivial by

$\lceil\log_{2}(T)\rceil\leq M(\mathcal{S})<T,$

see [11, Prop. 2]. For $0\leq\tau<T$, suppose that the cyclic (left)
$\tau$-shift of $\mathcal{S}$, denoted by $\mathcal{S}^{(\tau)}$, corresponds
to the rational number $-\frac{h_{\tau}}{q}$ with $0<h_{\tau}<q$ and
$\gcd(h_{\tau},q)=1$. It is clear that $h_{0}=f$. Among these $T$ many shift
sequences, we count the ones with the same beginning $N$ terms.

If $\mathcal{S}^{(i)}$ (associated to $-\frac{h_{i}}{q}$) and
$\mathcal{S}^{(j)}$ (associated to $-\frac{h_{j}}{q}$) are with the same
beginning $N$ terms, we have

$-\frac{h_{i}}{q}\equiv-\frac{h_{j}}{q}\pmod{2^{N}},$

which holds if and only if $h_{i}\equiv h_{j}\pmod{2^{N}}$, since
$q|(2^{T}-1)$.

Let $2^{m-1}<q<2^{m}$ for some positive integer $m$, so
$m=\left\lceil\log_{2}(q)\right\rceil$. If we choose $N=m$, we will find that
$h_{i}\equiv h_{j}\pmod{2^{m}}$ if and only if $h_{i}=h_{j}$ since
$0<h_{i},h_{j}<q<2^{m}$. It means that the beginning $m$ terms of
$-\frac{h_{i}}{q}$ are different from the ones of $-\frac{h_{j}}{q}$ for all
$0\leq i<j<T$. Then we derive that any subsequences
$(s_{i},s_{i+1},\ldots,s_{i+m-1})$ of length $m$ for $0\leq i<T$ are distinct,
and hence $M(\mathcal{S})\leq m=\left\lceil\log_{2}(q)\right\rceil$. Finally,
together with the notion of the $2$-adic complexity, we get
$M(\mathcal{S})\leq\left\lceil\Phi_{2}(\mathcal{S})\right\rceil$ directly. ∎

As far as we know, these are the first results on the relation between the
maximum-order complexity and the $2$-adic complexity. It disproves a claim by
Goresky and Klapper “If a sequence is generated by an FCSR with nonnegative
memory, then its $N$-adic span is no greater than its maximum order
complexity” in [5, p.329]. For the requirement of nonnegative memory, see [5,
Prop.4.7.1].

We remark that it is also important to consider the _symmetric $2$-adic
complexity_ of $\mathcal{S}$, which is the minimum of the $2$-adic
complexities of $\mathcal{S}$ and $\mathcal{S}^{rev}$, where
$\mathcal{S}^{rev}$ is the sequence formed by reversing each period of
$\mathcal{S}$, see [5, Sect. 16.2], since $\Phi_{2}(\mathcal{S}^{rev})$ may be
substantially smaller than $\Phi_{2}(\mathcal{S})$. By Theorem 2 we have
$M(\mathcal{S}^{rev})\leq\left\lceil\Phi_{2}(\mathcal{S}^{rev})\right\rceil$.
By [26, Prop.2] it is clear that $M(\mathcal{S}^{rev})=M(\mathcal{S})$ and so

$M(\mathcal{S})\leq\min(\left\lceil\Phi_{2}(\mathcal{S})\right\rceil,\left\lceil\Phi_{2}(\mathcal{S}^{rev})\right\rceil).$

##  4 Maximum-order complexity of periodic sequences

###  4.1 A characterization of the maximum-order complexity

The idea in the proof of Theorem 2 helps us to characterize the maximum-order
complexity of periodic sequences.

######  Theorem 3.

Let $\mathcal{S}=(s_{n})_{n\geq 0}$ be a binary sequence of period $T(\geq
2)$. If

$\sum_{n=0}^{\infty}s_{n}2^{n}=-A/q\quad\mbox{with }0<A<q\mbox{ and
}\gcd(A,q)=1$

and

$D_{A}=\\{0\leq u<q:u\equiv A\cdot 2^{n}\pmod{q},0\leq n<T\\},$

then $M(\mathcal{S})=N$ if and only if $N$ is the least integer such that

$u\not\equiv v\pmod{2^{N}}$

for any different $u,v\in D_{A}$.

Proof.  Suppose that $\mathcal{S}^{(\tau)}$, the (left) $\tau$-shift of
$\mathcal{S}$ for $0\leq\tau<T$, corresponds to the rational number
$-\frac{A^{(\tau)}}{q}$. We see that $A^{(\tau)}\equiv A2^{T-\tau}\pmod{q}$
and hence $D_{A}=\\{A^{(\tau)}:0\leq\tau<T\\}$.

For $N\geq 1$, the first $N$ elements of $\mathcal{S}^{(i)}$ are the same as
the ones of $\mathcal{S}^{(j)}$ for $0\leq i<j<T$ if and only if

$-\frac{A^{(i)}}{q}\equiv-\frac{A^{(j)}}{q}\pmod{2^{N}},$

which holds if and only if $A^{(i)}\equiv A^{(j)}\pmod{2^{N}}$, since $q$ is
odd.  This means that for $u,v\in D_{A}$, if $u\not\equiv v\pmod{2^{N}}$, we
derive that the first $N$ elements of $-u/q$ are different from the ones of
$-v/q$, which completes the proof. ∎

The set $\langle 2\rangle=\\{0\leq u<q:u=2^{n}\pmod{q},0\leq n<T\\}$ generated
by $2$ modulo $q$ is a sub-group of
$\mathbb{Z}_{q}^{*}=\\{0<u<q:\gcd(u,q)=1\\}$ under integer multiplication
modulo $q$. Thus according to Theorem 3, to analyze the maximum-order
complexity of periodic sequences, one only needs to consider the partition

$\mathbb{Z}_{q}^{*}=g_{1}\langle 2\rangle\cup g_{2}\langle
2\rangle\cup\cdots\cup g_{\varphi(q)/T}\langle 2\rangle,$

a union of co-sets of $\langle 2\rangle$, where $g_{i}\langle
2\rangle=\\{g_{i}u\pmod{q}:u\in\langle 2\rangle\\}\subseteq\mathbb{Z}_{q}^{*}$
for $1\leq i\leq\varphi(q)/T$. We note that $D_{A}$ in Theorem 3 is a co-set
of $\langle 2\rangle$.

###  4.2 Maximum-order complexity of $\ell$-sequences

As a consequence, we consider the case when $D_{A}=\mathbb{Z}_{q}^{*}$. We
find that $2$ modulo $q$ is primitive and hence $\mathcal{S}$ is an
$\ell$-sequence in this case. In particular, $q$ has to be a power of an odd
prime. The following theorem will indicate that the bound in Theorem 2 is
sharp.

######  Lemma 2.

Suppose that $q=p^{r}$ the power of an odd prime for $r\geq 1$ and $2$ modulo
$q$ is primitive. If $q$ is of the form $2^{k}+1$ for some integer $k\geq 1$,
then the possible value $q$ is in $\\{3,5,9\\}$.

Proof. It is clear that

$q=\left\\{\begin{array}[]{cl}3,&\mbox{ if }k=1,\\\ 5,&\mbox{ if }k=2,\\\
3^{2},&\mbox{ if }k=3,\end{array}\right.$

which satisfies all other assumptions in the lemma. Now we consider the case
$k\geq 4$ (and hence $q\geq 17$).

If $r=1$, that is, $q$ is an odd prime, we get

$\left(\frac{2}{q}\right)=-1=(-1)^{(q^{2}-1)/8},$

since $2$ modulo $q$ is primitive, where $\left(\frac{\cdot}{\cdot}\right)$ is
the Legendre symbol. We derive $q\equiv\pm 3\pmod{8}$, which contradicts
$q=2^{k}+1\equiv 1\pmod{8}$.

If $r\geq 2$, we see that

$2^{k}\equiv-1\pmod{q}~{}~{}\mbox{ and }2^{\varphi(q)/2}\equiv-1\pmod{q},$

the latter holds due to $2$ modulo $q$ being primitive. Hence
$k=c\varphi(q)/2$ for some odd positive integer $c\geq 1$.

We see that $2$ modulo $p^{\ell}$ is primitive for all $1\leq\ell\leq r$ due
to $2$ modulo $q$ being primitive again. So we have
$2^{\varphi(p^{r-1})/2}\equiv-1\pmod{p^{r-1}}$ and write

$2^{p^{r-2}(p-1)/2}=wp^{r-1}-1$

for some positive integer $w\geq 1$. We compute

$q=2^{k}+1=2^{c\varphi(q)/2}+1=(2^{p^{r-2}(p-1)/2})^{cp}+1=(wp^{r-1}-1)^{cp}+1.$

Together with $wp^{r-1}-1=wp^{1/3}p^{r-4/3}-1>p^{r-4/3}$ and $cp(r-4/3)\geq
3(r-4/3)=r+(2r-4)\geq r$ (since $q\geq 17$ and $r\geq 2$), we derive

$(wp^{r-1}-1)^{cp}+1>(p^{r-4/3})^{cp}+1>p^{r}=q,$

a contradiction.

Putting everything together, we see that only $q\in\\{3,5,9\\}$ satisfies the
requirements. ∎

######  Theorem 4.

Let $\mathcal{S}=(s_{n})_{n\geq 0}$ be a binary $\ell$-sequence with (minimal)
connection integer $q(\geq 3)$, which is an odd prime power. Then the maximum-
order complexity $M(\mathcal{S})$ of $\mathcal{S}$ satisfies

$M(\mathcal{S})=\left\\{\begin{array}[]{ll}\left\lfloor\log_{2}(q)\right\rfloor,&\mbox{if
}q\in\\{3,5,9\\},\\\
\left\lceil\log_{2}(q)\right\rceil,&\mbox{otherwise}.\end{array}\right.$

Proof. We assume that $\mathcal{S}$ is an $\ell$-sequence defined by Eq.(8)
with some integer $A$. Since 2 modulo $q$ is primitive, we see that
$D_{A}=\mathbb{Z}_{q}^{*}$ defined in Theorem 3.

  * •

If $q=3$, we see that the $\ell$-sequence $\mathcal{S}=(10)$ or $(01)$, whose
period is $2$. We check that
$M(\mathcal{S})=1=\left\lfloor\log_{2}(q)\right\rfloor$ by [26, Prop. 2].

Below we consider the case of $q\geq 5$. Let $2^{m-1}<q<2^{m}$ for some
positive integer $m\geq 3$.

  * •

If $q=2^{m-1}+1$, we find that $x\leq q-1=2^{m-1}$ for any $x\in D_{A}$ and
hence all $x\in D_{A}$ modulo $2^{m-1}$ are distinct. However, we have
$1+2^{m-2}\neq 1$ since $m\geq 3$ and

$1+2^{m-2}\equiv 1\pmod{2^{m-2}}.$

We remark that both $1$ and $1+2^{m-2}$ are in $\mathbb{Z}_{q}^{*}(=D_{A})$.
So by Theorem 3 we derive that
$M(\mathcal{S})=m-1=\left\lfloor\log_{2}(q)\right\rfloor$. Furthermore, we
have $q=5$ if $m=3$ and $q=9$ if $m=4$. But if $m\geq 5$, no such $q$ exists
by Lemma 2.

  * •

If $q>2^{m-1}+1$, we find that $q-1>2^{m-1}$ and all $x\in D_{A}$ modulo
$2^{m}$ are distinct. However, we have $1+2^{m-1}\neq 1$ and $2+2^{m-1}\neq 2$
since $m\geq 3$ and

$1+2^{m-1}\equiv 1\pmod{2^{m-1}}\mbox{ and }2+2^{m-1}\equiv 2\pmod{2^{m-1}}.$

We remark that either both $1$ and $1+2^{m-1}$ or both $2$ and $2+2^{m-1}$ are
in $\mathbb{Z}_{q}^{*}(=D_{A})$ 111We need to prove either
$\gcd(1+2^{m-1},q)=1$ or $\gcd(2+2^{m-1},q)=1$. Let $q=p^{r}$, an odd prime-
power. If $p|(1+2^{m-1})$, then $p\nmid(2+2^{m-1})$.. So by Theorem 3 we
derive that $M(\mathcal{S})=m=\left\lceil\log_{2}(q)\right\rceil$. ∎

We list some examples of $\ell$-sequences in Table 1.

$2^{m-1}<q<2^{m}$ | $T=\varphi(q)$ | $\left\lceil\log_{2}(q)\right\rceil$ | $M(\mathcal{S})$ | Remarks
---|---|---|---|---
$2<q=3<2^{2}$ | $2$ | $2$ | $1$ | $M(\mathcal{S})=\left\lfloor\log_{2}(q)\right\rfloor$
$2^{3}<q=3^{2}<2^{4}$ | $6$ | $4$ | $3$ | $M(\mathcal{S})=\left\lfloor\log_{2}(q)\right\rfloor$
$2^{4}<q=3^{3}<2^{5}$ | $18$ | $5$ | $5$ |
$2^{2}<q=5<2^{3}$ | $4$ | $3$ | $2$ | $M(\mathcal{S})=\left\lfloor\log_{2}(q)\right\rfloor$
$2^{9}<q=5^{4}<2^{10}$ | $500$ | $10$ | $10$ |
$2^{4}<q=19<2^{5}$ | $18$ | $5$ | $5$ |
$2^{8}<q=19^{2}<2^{9}$ | $342$ | $9$ | $9$ |
$2^{12}<q=19^{3}<2^{13}$ | $6498$ | $13$ | $13$ |
Table 1: $M(\mathcal{S})$ of binary $\ell$-sequence $\mathcal{S}$ with
connection integer $q$

For non-$\ell$-sequences, we have a different phenomenon, see examples in
Table 2.

$2^{m-1}<q<2^{m}$ | $T=\mathrm{ord}_{q}(2)\neq\varphi(q)$ | $\left\lceil\log_{2}(q)\right\rceil$ | $M(\mathcal{S})\in$
---|---|---|---
$2^{5}<q=51<2^{6}$ | $8$ | $6$ | $\\{4,5\\}$
$2^{5}<q=63<2^{6}$ | $6$ | $6$ | $\\{3,4,5\\}$
$2^{6}<q=65<2^{7}$ | $12$ | $7$ | $\\{4,6\\}$
$2^{6}<q=93<2^{7}$ | $10$ | $7$ | $\\{4,5,6\\}$
$2^{7}<q=217<2^{8}$ | $15$ | $8$ | $\\{5,6,7,8\\}$
Table 2: $M(\mathcal{S})$ of $\mathcal{S}$ with $s_{n}=(A2^{-n}\bmod{q})\bmod
2$ for different $A$

###  4.3 Binary sequences $\mathcal{S}$ of period $T$ with
$M(\mathcal{S})=T-1$

Binary sequences $\mathcal{S}$ of period $T$ with $M(\mathcal{S})=T-1$ were
considered before in [25, 26, 23, 31]. Now we look at them in another way.
Suppose that $\mathcal{S}$ corresponds to the rational number $\frac{A}{q}$
with $-q<A<0$ and $\gcd(A,q)=1$. Then by [5, Thm. 4.5.2], $\mathcal{S}$ can be
defined by

$s_{n}=(A2^{-n}\bmod q)\bmod 2,~{}~{}~{}n\geq 0.$ (8)

Below we list some examples of $\mathcal{S}$ with $M(\mathcal{S})=T-1$.

  * •

If we choose $q=31(=2^{5}-1)$ in Eq.(8), we produce $\mathcal{S}=(11000)$ with
period $T=5$ if $A=3$ and check $M(\mathcal{S})=3(<T-1)$. While if $A=5$ we
produce $\mathcal{S}=(10100)$ and check $M(\mathcal{S})=4(=T-1)$.

  * •

If we choose $q=127(=2^{7}-1)$ and $A=37$ in Eq.(8), we produce
$\mathcal{S}=(1010010)$ with period $T=7$. We check that
$M(\mathcal{S})=6(=T-1)$.

  * •

If we choose $q=255(=2^{8}-1)$ and $A=173$ in Eq.(8), we produce
$\mathcal{S}=(10110101)$ with period $T=8$. We check that
$M(\mathcal{S})=7(=T-1)$.

For such $\mathcal{S}$,  by Theorem 2 we see that
$\lceil\Phi_{2}(\mathcal{S})\rceil\geq T-1$ and so

$\Phi_{2}(\mathcal{S})\in\left\\{\log_{2}\left(\frac{2^{T}-1}{3}\right),~{}\log_{2}\left(2^{T}-1\right)\right\\}.$

However, we prove that their $2$-adic complexity is maximal.

######  Theorem 5.

Let $\mathcal{S}=(s_{n})_{n\geq 0}$ be a binary sequence of period $T\geq 2$.
If $M(\mathcal{S})=T-1$, then the $2$-adic complexity of $\mathcal{S}$ is also
maximal, that is, $\Phi_{2}(\mathcal{S})=\log_{2}(2^{T}-1)$.

Proof. Since the maximum-order complexity is the same for every shift of
$\mathcal{S}$, we may assume that there exists an integer
$d\in\\{1,\ldots,T-1\\}$ such that

$\displaystyle s_{i}$ $\displaystyle=s_{i+d}\quad\text{for }0\leq i\leq T-3,$
$\displaystyle s_{i}$ $\displaystyle=1-s_{i+d}\quad\text{for
}i\in\\{T-2,T-1\\},$

see Equation (2) in [31, Sect.III, A, p.6190]. We have $\gcd(d,T)=1$ by [31,
Prop. 1] and hence $e=d^{-1}\pmod{T}$ exists.

Using the two equations above, we can check that

$s_{id-1}=1-s_{T-1}\mbox{ for }1\leq i\leq
T-e,~{}~{}~{}s_{jd-2}=1-s_{T-2}\mbox{ for }1\leq j\leq e.$

We also have

$s_{(T-e)d-1}=s_{T-2},\quad s_{ed-2}=s_{T-1}\quad\mbox{and}\quad
s_{T-1}=1-s_{T-2}.$

We note that

$\\{id-1\pmod{T}:1\leq i\leq T-e\\}\cup\\{jd-2\pmod{T}:1\leq j\leq
e\\}=\\{0,1,\ldots,T-1\\}.$

In the case $(s_{T-2},s_{T-1})=(0,1)$ we get

$S(2)\equiv\sum_{j=1}^{e}2^{jd-2}\equiv 2^{d-2}(2^{d}-1)^{-1}(2^{ed}-1)\equiv
2^{d-2}(2^{d}-1)^{-1}\pmod{2^{T}-1},$

where we used

$ed\equiv 1\pmod{T}\quad\mbox{and thus}\quad 2^{ed}\equiv 2\pmod{2^{T}-1}$

in the last step, from which we derive

$\gcd(S(2),2^{T}-1)=1.$

The case $(s_{T-2},s_{T-1})=(1,0)$ can be treated in a similar way.

Hence the connection integer of $\mathcal{S}$ is $2^{T}-1$ and the $2$-adic
complexity of $\mathcal{S}$ is maximal, which completes the proof. ∎

For sequences $\mathcal{S}$ with $M(\mathcal{S})=T-2$, which are characterized
in [36], the 2-adic complexity is however not necessarily maximal anymore. For
example for the sequence $\mathcal{S}$ starting with $(0,0,1,0,0,1,0,0)$ of
period $T=8$, we have $M(\mathcal{S})=T-2$ but
$\Phi_{2}(\mathcal{S})=\log_{2}(\frac{2^{T}-1}{3})$.

##  5 Final remarks and conclusions

We have discussed the relationship between the maximum-order complexity and
the $2$-adic complexity for any binary sequence.  More precisely, the $2$-adic
complexity is at least of the order of magnitude of the maximum-order
complexity. If the order of magnitude of the maximum-order complexity is
maximal, then our bound is essentially tight. However, for a typical sequence
the maximum-order complexity is much smaller than the $2$-adic complexity.

There is another complexity measure called the expansion complexity introduced
by Diem [2]. Let $G(x)=\sum_{i\geq 0}s_{i}x^{i}$ be the generating function of
$\mathcal{S}=(s_{n})_{n\geq 0}$, which is viewed as a formal power series over
$\mathbb{F}_{2}$. The $N$th expansion complexity $E({\cal S},N)$ is $0$ if
$s_{0}=\ldots=s_{N-1}=0$ and otherwise the least total degree of a nonzero
polynomial $h(x,y)\in\mathbb{F}_{2}[x,y]$ with

$h(x,G(x))\equiv 0\bmod x^{N}.$

Note that $E({\cal S},N)$ depends only on the first $N$ terms of ${\cal S}$
and it has an expected value of order of magnitude $N^{1/2}$, see [3, Theorem
2]. The sequence $(E(\mathcal{S},N))_{N\geq 1}$ is referred to as the
_expansion complexity profile_ of $\mathcal{S}$. The value

$E({\cal S})=\sup_{N\geq 1}E({\cal S},N)$

is the _expansion complexity_ of $\mathcal{S}$, see [3, 4, 6] for more details
on the expansion complexity of sequences.

Another measure of pseudorandomness, the _rational complexity_ $R({\cal S},N)$
(resp. $R(\cal S)$ in the periodic case), was introduced and studied in [33]
dealing with so-called F$\mathbb{Q}$SRs instead of LFSRs (linear complexity)
or FCSRs ($2$-adic complexity).

Finally, we  give a list of the relationships between five complexities. For
periodic sequences $\mathcal{S}$, we have

  * •

$M(\mathcal{S})\leq L(\mathcal{S})=E(\mathcal{S})-1$.

  * •

$M(\mathcal{S})\leq\left\lceil\Phi_{2}(\mathcal{S})\right\rceil$ (our result).

  * •

The linear complexity and the $2$-adic complexity complement each other. For
example, for a binary $m$-sequence $\mathcal{M}=(m_{n})_{n\geq 0}$ of period
$T=2^{r}-1$, that is,

$m_{n}={\rm Tr}(g^{n})=\sum_{j=0}^{r-1}g^{2^{j}n},\quad n\geq 0,$

where $g$ is a primitive element of $\mathbb{F}_{2^{r}}$ and Tr is the
absolute trace of $\mathbb{F}_{2^{r}}$, we see that $L(\mathcal{M})=r$, which
is minimal for any sequence of least period $2^{r}-1$, but
$\Phi_{2}(\mathcal{M})=\log_{2}(2^{T}-1)$, which is the maximum, see [32]. For
a binary $\ell$-sequence $\mathcal{S}$ with minimal connection integer $q$ of
period $T=\varphi(q)$, where $\varphi$ is Euler’s totient function, we see
that $L(\mathcal{S})\leq(q+1)/2$, the bound of which is sharp, for example if
$p$ and $q=2p+1$ are primes with 2 being primitive modulo $p$ and modulo $q$
respectively, then the linear complexity is $L(\mathcal{S})=(q+1)/2~{}(=p+1)$
[28]. But $\Phi_{2}(\mathcal{S})=\log_{2}(q)$, which is small.

  * •

$R(\mathcal{S})=\Phi_{2}(\mathcal{S}^{rev})$ by [33, Theorem 13].

  * •

$M(\mathcal{S})\leq\left\lceil\Phi_{2}(\mathcal{S}^{rev})\right\rceil$.

In the aperiodic case, we have the  following relationships between the  $N$th
complexities for $\mathcal{S}$:

  * •

$M(\mathcal{S},N)\leq L(\mathcal{S},N)$. Hence  a large $N$th maximum-order
complexity implies a large $N$th linear complexity. However,
$M(\mathcal{S},N)$ should not be too large since otherwise the correlation
measure of order $2$ is large, see [17]. In particular, the expected value of
$M(\mathcal{S},N)$ is of order of magnitude $\log(N)$ [11] and the expected
value of $L(\mathcal{S},N)$ is $\frac{N}{2}+\mathcal{O}(1)$ [19].

  * •

$E(\mathcal{S},N)\leq L(\mathcal{S},N)+1$. In fact it was proved in [18] that

$E({\cal S},N)\leq\min\\{L({\cal S},N)+1,N+2-L({\cal S},N)\\}.$

  * •

$M(\mathcal{S},N)\leq\left\lceil\Phi_{2}(\mathcal{S},N)\right\rceil+1$ (our
result).

  * •

The $N$th expansion complexity and the $N$th maximum-order complexity
complement each other. We note that the expected value of $M(\mathcal{S},N)$
is of order of magnitude $\log(N)$ and $E({\cal S},N)$ has an expected value
of order of magnitude $N^{1/2}$. However, the pattern sequences
$\mathcal{P}_{k}$ of length $k$ including the Thue-Morse sequence
$\mathcal{T}$ (see notions in Section 2) have bounded expansion complexity,
that is $E(\mathcal{P}_{k},N)\leq 2^{k}+3$ for $k\geq 1$, see [17]. While the
maximum-order complexity is of the largest possible order of magnitude $N$,
that is $M(\mathcal{T},N)>N/5$ for $N>5$ and $M(\mathcal{P}_{k},N)>N/6$ for
$N\geq 2^{k+3}-7$ if $k\geq 2$, see [29].

  * •

[33] provides examples that rational complexity, $2$-adic complexity and
linear complexity complement each other. More precisely, in these examples
each two of these measures are close to the expected value whereas the third
one is much smaller and only one of these three measures detects the non-
randomness.

## References

  * [1] Z. Chen, A. Gómez, D. Gómez-Pérez, A. Tirkel. Correlation measure, linear complexity and maximum order complexity for families of binary sequences. Finite Fields Appl. 78: 101977 (2022)
  * [2] C. Diem. On the use of expansion series for stream ciphers. LMS J. Comput. Math. 15: 326-340 (2012)
  * [3] D. Gómez-Pérez, L. Mérai. Algebraic dependence in generating functions and expansion complexity. Adv. Math. Commun. 14(2): 307-318 (2020)
  * [4] D. Gómez-Pérez, L. Mérai, H. Niederreiter. On the expansion complexity of sequences over finite fields. IEEE Trans. Inform. Theory 64(6): 4228-4232 (2018)
  * [5] M. Goresky, A. Klapper. Algebraic Shift Register Sequences. Cambridge University Press, Cambridge (2012)
  * [6] R. Hofer and A. Winterhof. Linear complexity and expansion complexity of some number theoretic sequences. In: Arithmetics in Finite Fields-WAIFI2016. Lect. Notes Comput. Sci. 10064, 67-74, Springer-Verlag, Cham (2017)
  * [7] R. Hofer and A. Winterhof. On the $2$-adic complexity of the two-prime generator. IEEE Trans. Inform. Theory 64(8): 5957–5960 (2018)
  * [8] H. Hu. Comments on ‘A new method to compute the $2$-adic complexity of binary sequences’. IEEE Trans. Inform. Theory 60(9): 5803–5804 (2014)
  * [9] D. Jamet, P. Popoli, T. Stoll. Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences. Cryptogr. Commun. 13(5): 791-814 (2021)
  * [10] C. J. A. Jansen. Investigations on nonlinear streamcipher systems: construction and evaluation methods. Ph.D. dissertation, Technical University of Delft, Delft (1989)
  * [11] C. J. A. Jansen, D. E. Boekee. The shortest feedback shift register that can generate a given sequence. In G. Brassard (Ed.): Advances in Cryptology–CRYPTO’89, Lect. Notes Comput. Sci. 435: 90-99, Springer-Verlag, Berlin Heidelberg (1990)
  * [12] C. J. A. Jansen. The maximum order complexity of sequence ensembles. In D.W. Davies (Ed.): Advances in Cryptology - EUROCRYPT’91, Lect. Notes Comput. Sci. 547: 153-159, Springer-Verlag, Berlin Heidelberg (1991)
  * [13] A. Klapper, M. Goresky. Feedback shift registers, $2$-adic span and combiners with memory. J. Cryptol. 10(2): 111-147 (1997)
  * [14] K. Limniotis, N. Kolokotronis, N. Kalouptsidis. On the nonlinear complexity and Lempel-Ziv complexity of finite length sequences. IEEE Trans. Inform. Theory 53(11): 4293-4302 (2007)
  * [15] C. Mauduit, A. Sárközy. On finite pseudorandom binary sequences I: measure of pseudorandomness, the Legendre symbol. Acta Arith. 82(4): 365-377 (1997)
  * [16] W. Meidl, A. Winterhof. Linear complexity of sequences and multisequences. In: G. L. Mullen, D. Panario (eds.): Handbook of Finite Fields, 324-336, CRC Press, Boca Raton, FL (2013)
  * [17] L. Mérai, A. Winterhof. Pseudorandom sequences derived from automatic sequences. Cryptogr. Commun. 14(4): 783-815 (2022)
  * [18] L. Mérai, H. Niederreiter, A. Winterhof. Expansion complexity and linear complexity of sequences over finite fields. Cryptogr. Commun. 9(4): 501-509 (2017)
  * [19] H. Niederreiter. The probabilistic theory of linear complexity. In: Advances in Cryptology — EUROCRYPT’88, Lecture Notes in Comput. Sci. 330: 191-209, Springer-Verlag, Berlin Heidelberg (1988)
  * [20] H. Niederreiter. Linear complexity and related complexity measures for sequences. In: T. Johansson, S. Maitra (eds.): Progress in Cryptology - INDOCRYPT 2003, Lect. Notes Comput. Sci. 2904: 1-17, Springer-Verlag, Berlin Heidelberg (2003)
  * [21] H. Niederreiter, C. Xing. Sequences with high nonlinear complexity. IEEE Trans. Inform. Theory 60(10): 6696-6701 (2014)
  * [22] G. Petrides, J. Mykkeltveit. On the classification of periodic binary sequences into nonlinear complexity classes. In: G. Gong, T. Helleseth, H. Song, K. Yang(eds) Sequences and Their Applications – SETA 2006, Lect. Notes Comput. Sci. 4086: 209-222, Springer-Verlag, Berlin Heidelberg (2006)
  * [23] G. Petrides, J. Mykkeltveit. Composition of recursions and nonlinear complexity of periodic binary sequences. Des. Codes Cryptogr. 49(1-3): 251-264 (2008)
  * [24] P. Popoli. On the maximum order complexity of Thue-Morse and Rudin-Shapiro sequences along polynomial values. Unif. Distrib. Theory 15(2): 9-22 (2020)
  * [25] P. Rizomiliotis. On the design of binary sequences with maximum nonlinear span. In: Proc. Int’l Symp. Inform. Theory-ISIT2005, 469-473, IEEE Xplore (2005)
  * [26] P. Rizomiliotis. Constructing periodic binary sequences with maximum nonlinear span. IEEE Trans. Inform. Theory 52(9): 4257-4261 (2006)
  * [27] P. Rizomiliotis, N. Kalouptsidis: Results on the nonlinear span of binary sequences. IEEE Trans. Inform. Theory 51(4): 1555-1563 (2005)
  * [28] C. Seo, S. Lee, Y. Sung, K. Han, S. Kim. A lower bound on the linear span of an FCSR. IEEE Trans. Inform. Theory 46(2): 691-693 (2000)
  * [29] Z. Sun, A. Winterhof. On the maximum order complexity of the Thue-Morse and Rudin-Shapiro sequence. Unif. Distrib. Theory 14(2): 33-42 (2019)
  * [30] Z. Sun, A. Winterhof. On the maximum order complexity of subsequences of the Thue-Morse and Rudin-Shapiro sequence along squares. Int. J. Comput. Math. Comput. Syst. Theory 4(1): 30-36 (2019)
  * [31] Z. Sun, X. Zeng, C. Li, T. Helleseth. Investigations on periodic sequences with maximum nonlinear complexity. IEEE Trans. Inform. Theory 63(10): 6188-6198 (2017)
  * [32] T. Tian, W.-F. Qi. $2$-adic complexity of binary $m$-sequences. IEEE Trans. Inform. Theory 56(1): 450-454 (2010)
  * [33] M. Vielhaber, M.d.P. Canales Chacón, S. Jara Ceballos. Rational complexity of binary sequences, F$\mathbb{Q}$SRs, and pseudo-ultrametric continued fractions in $\mathbb{R}$. Cryptogr. Commun. 14(2): 433-457 (2022)
  * [34] A. Winterhof. Linear complexity and related complexity measures. In: I. Woungang (ed.): Selected Topics in Information and Coding Theory, 3-40, World Scientific, Singapore (2010)
  * [35] A. Winterhof. Pseudorandom binary sequences: quality measures and number theoretic constructions. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. DOI:10.1587/transfun.2023SDI0001 (to appear) (2023)
  * [36] Z. Xiao, X. Zeng, C. Li, Y. Jiang. Binary sequences with period $N$ and nonlinear complexity $N-2$. Cryptogr. Commun. 11(4): 735-757 (2019)
  * [37] H. Xiong, L. Qu, and C. Li. A new method to compute the $2$-adic complexity of binary sequences. IEEE Trans. Inform. Theory 60(4): 2399-2406 (2014)


11institutetext:  Warsaw University of Technology, Pl. Politechniki 1, 00-661
Warsaw, Poland 22institutetext: Institute of Theoretical and Applied
Informatics, Polish Academy of Sciences, Bałtycka 5, 44-100 Gliwice, Poland
33institutetext: Faculty of Physics, Astronomy and Applied Computer Science,
Jagiellonian University, 30-348 Kraków, Poland

# Post-Error Correction for Quantum Annealing Processor using Reinforcement
Learning

Tomasz Śmierzchalski 1122 Łukasz Pawela 22 Zbigniew Puchała 2233 Tomasz
Trzcinski 11 Bartłomiej Gardas 22

###### Abstract

Finding the ground state of the Ising spin-glass is an important and
challenging problem (NP-hard, in fact) in condensed matter physics. However,
its applications spread far beyond physic due to its deep relation to various
combinatorial optimization problems, such as travelling salesman or protein
folding. Sophisticated and promising new methods for solving Ising instances
rely on quantum resources. In particular, quantum annealing is a quantum
computation paradigm, that is especially well suited for Quadratic
Unconstrained Binary Optimization (QUBO). Nevertheless, commercially available
quantum annealers (i.e., D-Wave) are prone to various errors, and their
ability to find low energetic states (corresponding to solutions of superior
quality) is limited. This naturally calls for a post-processing procedure to
correct errors (capable of lowering the energy found by the annealer). As a
proof-of-concept, this work combines the recent ideas revolving around the
DIRAC architecture with the Chimera topology and applies them in a real-world
setting as an error-correcting scheme for quantum annealers. Our preliminary
results show how to correct states output by quantum annealers using
reinforcement learning. Such an approach exhibits excellent scalability, as it
can be trained on small instances and deployed for large ones. However, its
performance on the chimera graph is still inferior to a typical algorithm one
could incorporate in this context, e.g., simulated annealing.

###### Keywords:

Quantum error correction Quantum Annealing Deep reinforcement learning Graph
neural networks.

##  1 Introduction

Many complex and significant optimization problems (such as all of Karp’s 21
NP-complete problems [18], the travelling salesman problem [17], the protein
folding problem [3], financial portfolio management [26]) can be mapped into
the problem of finding the ground state of the Ising spin-glass. Sophisticated
and promising new methods for solving Ising instances rely on quantum
computation, particularly quantum annealing.

Quantum annealing is a form of quantum computing particularly well-tailored
for optimization [13, 27]. It is closely related to adiabatic quantum
computation [19], a paradigm of universal quantum computation which relies on
the adiabatic theorem [14] to perform calculations. It is equivalent (up to
polynomial overhead) to the better-known gate model of quantum computation
[19]. Nevertheless, commercially available quantum annealers (i.e., D-Wave)
are prone to various errors, and their ability to find low energetic states is
limited.

Inspired by the recently proposed deep reinforcement learning method for
finding spin glass ground states [8], here, we propose a new post-processing
error correction schema for quantum annealers called Simulated Annealing with
Reinforcement (SAwR). In this procedure, we combine deep reinforcement
learning with simulated annealing. We employ a graph neural network to encode
the Ising instance into an ensemble of low-dimensional vectors used for
reinforcement learning. The agent learns a strategy for improving (finding a
lower energy state) solutions given by the physical quantum annealer. The
process of finding the lower energy state involves ”flipping” spins one by one
according to the learned strategy and recording the energy state after each
step. The solution is defined as the lowest energy state found during this
procedure. In Simulated Annealing with Reinforcement, we start with simulated
annealing and, at low temperature, we replace the Metropolis-Hasting criterion
with a single pass of spin flipping procedure.

Unlike recent error-correcting schema [24, 25, 30] we do not utilize multiple
physical qubits for representing single logical qubits. This approach allows
for a far greater size of problems to which our method applies. However, the
performance of SAwR is still inferior to a typical algorithm one could
incorporate in this context, such as simulated annealing. Nevertheless, using
reinforcement learning for post-error correction is still an open and
promising avenue of research.

Figure 1: Overview of our method, arrows represent subsequent steps. First, we
define the Ising instance by providing couplings strength and biases (external
magnetic field strength). Then we obtain the proposed solution from a quantum
annealer. Here, it is represented by a single Chimera unit cell rendered as a
graph. Black nodes represent spin value $\sigma_{i}=-1$ and white nodes
represent spin value $\sigma_{i}=1$. Edges represent couplings between spins.
In the next step, we encode such an instance using a graph neural network into
the matrix of encodings, where each row corresponds to the embedding of a
vertex. Then this matrix is passed through a decoder to obtain Q-values of
actions associated with each vertex. The spin flipping procedure involves
”flipping” spins one by one according to Q-Values, starting from the highest
and recording the energy state after each step. The solution is defined as the
lowest energy state found during this procedure.

##  2 Ising Spin Glass and Quantum Annealing

###  2.1 Quantum Annealing in D-Wave

The Ising problem is defined on some arbitrary simple graph $G$. An Ising
Hamiltonian is given by:

$H_{\text{Ising}}(\sigma)=\sum_{\langle i,j\rangle\in
G}J_{i,j}\sigma_{i}\sigma_{j}+\sum_{i}h_{i}\sigma_{i},$ (1)

where $\sigma_{i}\in\\{+1,-1\\}$ denotes the $i$-th Ising spin,
$\sigma=\\{\sigma_{1},\ldots,\sigma_{n}\\}$ is the vector representation of a
spin configuration. $\langle i,j\rangle$ denotes neighbours in graph $G$,
$J_{i,j}$ strength of interaction (coupling coefficient) between $i$-th and
$j$-th spin. $h_{i}$ is external magnetic field (bias) affecting $i$-th spin.
The goal is to find spin configuration, called ground state,

$\sigma^{*}=\operatorname*{arg\,min}_{\sigma}\,H_{\text{Ising}}(\sigma).$ (2)

such that energy of $H_{\text{Ising}}$ is minimal. This is an NP-hard problem.
Quantum annealing is a method for finding the ground state of (1). This is
done by adiabatic evolution from the initial Hamiltonian $H_{X}$ of the
Transverse-field Ising model to the final Hamiltonian $H_{\text{Ising}}$. The
Hamiltonian of this process is described by

$\mathcal{H}(t)=A(t)H_{X}+B(t)H_{\text{Ising}},$ (3)

where $H_{X}=\sum_{i}\hat{\sigma_{i}}^{x}$ and $\hat{\sigma_{i}}^{x}$ is the
standard Pauli $X$ matrix acting on the $i$-th qubit. The function $A(t)$
decreases monotonically to zero, while $B(t)$ increases monotonically from
zero, with $t\in[0,t_{f}]$, where $t_{f}$ denotes total time of anneal [11,
27]. For a closed system, the adiabatic theorem guarantees that if the initial
state is the ground state, then the final state will be arbitrarily close to
the ground state, provided all technical requirements are met [14]. In
summary, the systems start with a set of qubits, each in a superposition state
of $-1$ and $1$. By annealing, the system collapses into the classical state
that represents the minimum energy state of the problem, or one very close to
it.

The D-Wave 2000Q is a psychical realization of the quantum annealing
algorithm. Sadly, the idealized conditions of the adiabatic theorem are nearly
impossible to be realized in a physical device. In such an open system, there
is inevitable thermal noise which may cause decoherence [7]. Furthermore, due
to technical limitations, those device suffers from programming control errors
on the $h_{i}$ and $J_{i,j}$ terms, which can unintentionally cause the
annealer to evolve according to the wrong Hamiltonian [1].

###  2.2 D-Wave 2000Q

At the heart of every D-wave quantum annealer lies the Quantum Processing Unit
(QPU), which is a lattice of interconnected qubits. While its physical details
are beyond the scope of this paper111Interested reader may find details in [4]
and [12] , it is necessary to mention some technical details. In QPU, qubits
can be thought of as loops being ”oriented” vertically or horizontally (see
figure 2) and connected to each other via devices called couplers. How qubits
and couplers are interconnected is described by QPU topology.

As of the time of writing, there are two available architectures of D-Wave
quantum annealers, namely 2000Q with Chimera topology deployed in 2017 and
Advantage with Pegasus topology deployed in 2020. Third, called Advantage 2
with Zephyr topology [2] is stated to release in 2023-2024 [5]. In this work,
we will focus on the 2000Q device and Chimera topology.

Figure 2: Qubits are represented as horizontal and vertical loops. This
graphic shows three coupled unit cells with eight qubits each. Green dots
represent internal couplers connecting qubits inside the unit cell, while blue
bars represent external couplers connecting different unit cells.

####  2.2.1 Chimera Topology

The basic building block of Chimera topology is a set of connected qubits
called a unit cell. Each unit cell consists of four horizontal qubits
connected to four vertical qubits via couplers which form bipartite
connectivity as seen in figure 3. Unit cells are tiled vertically and
horizontally with adjacent qubits connected, creating a lattice of sparsely
connected qubits.

It is conceptually valuable to categorize couplers into _internal couplers_
which connect intersecting (orthogonal) qubits and _external couplers_ which
connect colinear pairs of qubits (that is, pairs of qubits that lie in the
same row or column). The notation $C_{n}$ describes the Chimera grid composed
of $n\times n$ coupled unit cells, consisting of $8n^{2}$ qubits. D-Wave 2000Q
device is equipped with $C_{16}$ QPU, with more than 2000 qubits [6].

32107654 (a) Unit cell rendered as column

01234567 (b) Unit cell rendered as cross

Figure 3: Different renderings of Chimera unit cell as graph. Nodes represent
qubits and edges represent internal couplers.

##  3 Results

###  3.1 Reinforcement Learning Formulation

We will consider standard reinforcement learning setting defined as Markov
Decision Process [29] where an agent interacts with an environment over a
number of discrete time steps $t=0,1,\ldots,T$. At each time step $t$, the
agent receives a state $s_{t}$ and selects an action $a_{t}$ from some set of
possible actions $\mathcal{A}$ according to its policy $\pi$, where $\pi$ is a
mapping from set of states $\mathcal{S}$ to set of actions $\mathcal{A}$. In
return, the agent receives a scalar reward $r_{t}$ and moves to next state
$s_{t+1}$. The process continues until the agent reaches a terminal state
$s_{T}$ after which the process restarts. We call one pass of such process an
episode. The return at time step $t$, denoted
$R_{t}=\sum_{k=0}^{T-t}\gamma^{k}r_{t+k}$ is defined as sum of rewards that
agent will receive for rest of the episode discounted by discount factor
$\gamma\in(0,1]$. The goal of the agent is to maximize the expected return
from each state $s_{t}$.

We will start by defining state, action, and reward in the context of the
Ising spin-glass model.

  * •

State: a state $s$ represents the observed spin glass instance, including both
the spin configuration $\sigma$, the coupling strengths $\\{J_{ij}\\}$ and
values of external magnetic field $\\{h_{i}\\}$.

  * •

Action: an action $a^{(i)}$ means to flip spin $i$. By flipping spin we mean
changing is value to opposite. For example, after agent performs action
$a^{(i)}$, spin $\sigma_{i}=1$ becomes $\sigma_{i}=-1$. Agent can flip each
spin once.

  * •

Reward: the reward $r(s_{t};a^{(i)}_{t};s_{t+1})$ is defined as the energy
change after flipping spin $i$ from state $s_{t}$ to a new state $s_{t+1}$.

Starting at $t=0$, an agent flips one spin during each time step, which moves
him to the next state (different spin configuration). The terminal state
$s_{T}$ is met when the agent has flipped each spin. The solution is defined
as spin configuration $\sigma$ corresponding lowest energy state found during
this procedure.

An action-value function $Q^{\pi}(s,a)=\mathbb{E}(R_{t}\leavevmode\nobreak\
|\leavevmode\nobreak\ s_{t}=s,\leavevmode\nobreak\ a_{t}=a)$ is the expected
return for selecting action $a$ in state $s$ and following policy $\pi$. The
value $Q^{\pi}(s,a)$ is often called $Q$-value of action $a$ in state $s$. The
optimal action-value function $Q^{*}(s,a)=\max_{\pi}Q^{\pi}(s,a)$ which gives
the maximum action value for state $s$ and action $a$ achievable by any
policy. As learning optimal action-value function is in practice infeasible,
We seek to learn function approximator $Q(s,a;\Theta)\approx Q^{*}(s,a)$ where
$\Theta$ is set of learnable model parameters. We denote policy used in such
aproximation as $\pi_{\Theta}$.

Figure 4: Overview of single episode. To simplify, we show it on a single
Chimera unit cell. White nodes represent $\sigma_{i}=1$ and black nodes
represent $\sigma_{i}=-1$ We start in some state $s_{0}$ and one by one we
flip spins until all spins are flipped. The solution is defined as spin
configuration $\sigma^{*}$ corresponding lowest energy state found during this
procedure.

###  3.2 Model Architecture

Our model architecture is inspired by DIRAC (Deep reinforcement learning for
spIn-glass gRound-stAte Calculation), an Encoder-Decoder architecture
introduced in [8]. It exploits the fact that the Ising spin-glass instance is
wholly described by the underlying graph. In this view, couplings $J_{i,j}$
become edge weights, external magnetic field $h_{i}$ and spin $\sigma_{i}$
become node weights. Employing DIRAC is a two-step process. At first, it
encodes the whole spin-glass instance such that every node is embedded into a
low-dimensional vector, and then the decoder leverages those embeddings to
calculate the $Q$-value of every possible action. Then, the agent chooses the
action with the highest $Q$-value. In the next sections, We will describe
those steps in detail.

####  3.2.1 Encoding

As described above, the Ising spin-glass instance can be described in the
language of graph theory. It allows Us to employ graph neural networks [10,
9], which are neural networks designed to take graphs as inputs. We use
modified SGNN (Spin Glass Neural Network) [8] to obtain node embedding. To
capture the coupling strengths and external field strengths (i.e., edge
weights $J_{i,j}$ and node weights $h_{i}$), which are crucial to determining
the spin glass ground states, SGNN performs two updates at each layer,
specifically, the edge-centric update and the node-centric update,
respectively.

Lets $z_{(i,j)}$ denote embedding of edge $(i,j)$ and $z_{(i)}$ embedding of
node $i$. The edge-centric update aggregates embedding vectors from from its
adjacent nodes (i.e. for edge $(i,j)$ this update aggregate emmbedings
$z_{(i)}$ and $z_{(j)}$), and then concatenates it with self-embedding
$z_{(i,j)}$. Vector obtained in this way is then subject to non-linear
transformation (ex. ReLU$(x)=\max(0,x)$). Mathematically it can be described
by following equation

$z_{(i,j)}^{k+1}=\text{ReLU}(\gamma_{\theta}(z_{(i,j)}^{k})\oplus\phi_{\theta}(z_{(i)}^{k}+z_{(j)}^{k})),$
(4)

where $z_{(i,j)}^{k}$ denotes encoding of edge $(i,j)$ obtained after $k$
layers. Similary $z_{(i)}^{k}$ denotes encoding of node $i$ obtained after $k$
layers, $\gamma_{\theta}$ and $\phi_{\theta}$ are some differentiable
functions (ex. feed-foward neural networks) whih demends on set of paramethers
$\theta$. Symbol $\oplus$ is used to denote concatenation operation.

The node-centric update is defined in similar fashion. It aggregates embedding
of adjacent edges, and then concatenates it with self-embedding $z_{(i)}$.
Later we transform this concatenated vector to obtain final embedding. Using
notation from equation 4, final result is following:

$z_{(i)}^{k+1}=\text{ReLU}(\phi_{\theta}(z_{(i)}^{k})\oplus\gamma_{\theta}(\text{E}_{i}^{k})),$
(5) $\text{E}_{i}^{k}=\sum_{j}z_{(i,j)}^{k}.$ (6)

Edge features are initialized as edge weights $\\{J_{i,j}\\}$. It is not
trivial to find adequate node features, as node weights $\\{h_{i}\\}$ and
spins ${\sigma_{i}}$ are not enough.

It is worth noting that both those operations are message passing schema [10].
Edge-centric update aggregate information about adjacent nodes of edge and
edge itself and sends it as a ”message” to this edge. Similarly, node-centric
update aggregate information about edges adjacent to the node and the node
itself. In those edges are also encoded information about neighbouring nodes.

We also included pooling layers not presented in the original design. We
reasoned that after concatenation, vectors start becoming quite big, so we
employ pooling layers to not only reduce the model size but also preserve the
most essential parts of every vector.

As every node is a potential candidate for action, we call the final encoding
of node $i$ its action embedding and denote it as $Z_{i}$. To represent the
whole Chimera (state of our environment), we use state embedding, denoted as
$Z_{s}$, which is the sum over all node embedding vectors, which is a
straightforward but empirically effective way for graph-level encoding [15].

####  3.2.2 Decoding

Once all action embeddings $Z_{i}$ and state embedding $Z_{s}$ are computed in
the encoding stage, the decoder will leverage these representations to compute
approximated state-action value function $Q(s,a;\Theta)$ which predicts the
expected future rewards of taking action $a$ in state $s$, and following the
policy $\pi_{\Theta}$ till the end. Specifically, we concatenate the
embeddings of state and action and use it as decoder input. In principle, any
decoder architecture may be used. Here, we use a standard feed-forward neural
network. Formally, the decoding process can be written as:

$Q(s,a^{(i)};\Theta)=\psi_{\Theta}(Z_{s}\oplus Z_{i}),$ (7)

where $\psi_{\Theta}$ is a dense feed-forward neural network.

###  3.3 Training

We train our model on randomly generated Chimera instances. We found that the
minimal viable size of the training instance is $C_{3}$ (as a reminder,
$C_{3}$ is Chimera architecture with nine unit cells arranged into a $3\times
3$ grid, which gives us 72 spins). Smaller instances lack couplings between
clusters, crucial in full Chimera, which leads to poor performance. We
generate $\\{J_{i,j}\\}$ and $\\{h_{i}\\}$ from normal distribution
$\mathcal{N}(0,1)$ and starting spin configuration $\sigma$ from uniform
distribution. To introduce low-energy instances, we employed the following
pre-processing procedure. For each generated instance, with probability
$p=10\%$, we perform standard simulated annealing before passing the instance
through SGNN.

We seek to learn approximation of optimal action-value function
$Q(a,s;\Theta)$, so as reinforcement learning algorithm we used standard
n-step deep $Q$ learning [23, 20] with memory replay buffer. During episode we
collect sequence of states action and rewards
$\tau=(s_{0},a_{0},r_{0},\ldots,s_{T-1},a_{T-1},r_{T-1},s_{T})$ with terminal
state as final element. From those we construct $n$-step transitions
$\tau^{n}_{t}=(s_{t},a_{t},r_{t,t+n},s_{t+n})$ which we collect in memory
replay buffer $\mathcal{B}$. Here
$r_{t,t+n}=\sum_{k=0}^{k=n}\gamma^{k}r_{t+k}$ is return after $n$-steps.

###  3.4 Simulated Annealing with Reinforcement

Simulated annealing with reinforcement (SAwR) combines machine learning and
classical optimization algorithm. Simulated annealing (SA) takes its name from
a process in metallurgy involving heating a material and then slowly lowering
the temperature to decrease defects, thus minimizing the system energy. In SA,
we start in some state $s$ and in each step, we move to a randomly chosen
neighboring state $s^{\prime}$. If a move lowers energy $E(s)$ of the system,
we accept it. If it doesn’t, we use the so-called the Metropolis-Hasting
criterion.

$\mathbb{P}(\text{accept}\,s^{\prime}\leavevmode\nobreak\
|\leavevmode\nobreak\ s)=\min(1,e^{-\beta\Delta E}),$ (8)

where $\Delta E=E(s^{\prime})-E(s)$ and $\beta$ denotes inverse temperature
$1/T$. In our case, the move is defined as a single-spin flip. Simulated
annealing tends to accept all possible moves at high temperatures (i.e., lower
$\beta$). However, it likely accepts only those moves that lower the energy at
low temperatures.

Our idea is to reinforce random sampling with a trained model. It means that
at low temperatures, instead of using the Metropolis-Hasting criterion, we
perform a single pass of the DIRAC episode.

##  4 Experiments

We collected data from the D-Wave 2000Q device using default parameters
(number of samplings, annealing time, etc.). We have generated 500 random
instances of sizes $C_{4}$, $C_{8}$, $C_{12}$ and $C_{16}$, corresponding to
systems of sizes 128, 512, 1152 and 2048 spins respectively. We used identical
distributions to training instances, so $\\{J_{i,j}\\}$ and $\\{h_{i}\\}$ was
generated from normal distribution $\mathcal{N}(0,1)$ and starting spin
configuration $\sigma$ from uniform distribution. We then used quantum
annealing to obtain the low energy states of generated instances.

We have used three methods - standard simulated annealing, a single pass of
spin-flipping procedure and simulated annealing with reinforcement. Results
are shown in figures 5(a) and 5(b).

We tested for two metrics: the probability of finding lower energy states and
the mean value of an improvement over starting energy state. To compute the
probability for each Chimera size, we started with proposed solutions obtained
from quantum annealer and tried to lower them using different tested methods.
Then we counted those instances for which a lower energy state was found. We
define the value of the improvement as the difference between starting energy
state and the lowest energy state found by the tested method in abstract units
of energy.

Simulated annealing with reinforcement achieved lower probabilities of finding
a lower energy state. Although the difference between SAwR and traditional
simulated annealing is slight, its consistency across all sizes suggests that
it is systemic rather than random noise. The single pass of the spin-flipping
procedure was the order of magnitude worse, reaching approximately $1\%$
success rate.

It is interesting that, on average, SAwR was able to find a better low energy
state than simulated annealing, but still, the difference is not significant.

(a) The probability of finding a lower energy state was computed over 500
random instances for each Chimera size. Here we decided to omit results for a
single pass of the spin flipping procedure because its results were the order
of magnitude worse, making the figure hard to read.

(b) Mean value of the improvement. We define the value of the improvement as
the difference between starting energy state and the lowest energy state found
by the tested method in abstract units of energy. The mean was computed over
all instances where the method could find improvement

Figure 5: Results of our experiments for tested metrics. By model, we define a
single pass of the spin flipping procedure. SAwR denotes simulated annealing
with reinforcement.

##  5 Discussion and Further Work

The real-life Chimera graph is a much more complex problem than the regular
lattice employed in [8], which may be the reason for poor performance.
However, we managed to replicate the excellent scaling of DIRAC. We trained
our model on relatively small instances and employed it for large ones. We did
not observe significant differences in performance relative to the size of the
system. Much more work is needed because more complex architectures are
deployed (Pegasus, Zephyr) by D-wave systems.

One possible avenue of research is changes in architecture. Right now goals of
the encoder and decoder are quite different. The encoder tries to encode
information while the decoder leverages them for reinforcement learning.
Training them both at the same time might be difficult. One option is to
divorce them from a single architecture. For example, we may use graph
autoencoder [16, 22] to train the encoder. Then for the reinforcement learning
part, we would use an already trained encoder and train only the neural
network responsible for approximating the action-value function.

Another option is to use different reinforcement learning algorithms.
Asynchronous methods have been shown to consistently beat their synchronous
counterparts, especially asynchronous advantage actor-critic [21], but
asynchronous Sarsa or Q-learning also look promising. Methods based on Monte
Carlo tree search inspired by AlphaZero [28] also seems promising. It has
shown excellent performance on tasks involving large search space (ex. Chess,
Go).

## Acknowledgments

This research was supported by the Foundation for Polish Science (FNP) under
grant number TEAM NET POIR.04.04.00-00-17C1/18-00 (LP, ZP, and BG). TS
acknowledges support from the National Science Centre (NCN), Poland, under
SONATA BIS 10 project number 2020/38/E/ST3/00269. This research was partially
funded by National Science Centre, Poland (grant no 2020/39/ B/ST6/01511 and
2018/31/N/ST6/02374) and Foundation for Polish Science (grant no
POIR.04.04.00-00-14DE/ 18-00 carried out within the Team-Net program co-
financed by the European Union under the European Regional Development Fund).
For the purpose of Open Access, the author has applied a CC-BY public
copyright license to any Author Accepted Manuscript (AAM) version arising from
this submission.

## References

  * [1] Ayanzadeh, R., Dorband, J.E., Halem, M., Finin, T.: Post-quantum error-correction for quantum annealers. Preprint at https://arxiv.org/abs/2010.00115 (2020)
  * [2] Boothby, K., King, A.D., Raymond, J.: Zephyr Topology of D-Wave Quantum Processors. Tech. rep., D-Wave Systems Inc. (2021)
  * [3] Bryngelson, J.D., Wolynes, P.G.: Spin glasses and the statistical mechanics of protein folding. Proceedings of the National Academy of Sciences of the United States of America 84(21), 7524–7528 (1987). https://doi.org/10.1073/pnas.84.21.7524
  * [4] Bunyk, P.I., et al.: Architectural considerations in the design of a superconducting quantum annealing processor. IEEE Transactions on Applied Superconductivity 24(4), 1–10 (2014). https://doi.org/10.1109/TASC.2014.2318294
  * [5] D-Wave Systems: The d-wave clarity roadmap (2021), https://www.dwavesys.com/media/xvjpraig/clarity-roadmap_digital_v2.pdf, visited 2022-01-26
  * [6] D-Wave Systems: Getting Started with D-Wave Solvers (2021), visited 2022-02-15
  * [7] Deng, Q., Averin, D.V., Amin, M.H., Smith, P.: Decoherence induced deformation of the ground state in adiabatic quantum computation. Scientific reports 3(1), 1–6 (2013). https://doi.org/10.1038/srep01479
  * [8] Fan, C., et al.: Finding spin glass ground states through deep reinforcement learning. Preprint at https://arxiv.org/abs/2109.14411 (2021)
  * [9] Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., Dahl, G.E.: Neural Message Passing for Quantum Chemistry. In: Precup, D., Teh, Y.W. (eds.) Proceedings of the 34th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 70, pp. 1263–1272. PMLR (2017)
  * [10] Hamilton, W.L.: Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning 14(3), 1–159 (2020). https://doi.org/10.2200/S01045ED1V01Y202009AIM046
  * [11] Jansen, S., Ruskai, M.B., Seiler, R.: Bounds for the adiabatic approximation with applications to quantum computation. Journal of Mathematical Physics 48(10), 102111 (2007). https://doi.org/10.1063/1.2798382
  * [12] Johnson, M., et al.: Quantum annealing with manufactured spins. Nature 473, 194–8 (2011). https://doi.org/10.1038/nature10012
  * [13] Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse ising model. Phys. Rev. E 58, 5355–5363 (1998). https://doi.org/10.1103/PhysRevE.58.5355
  * [14] Kato, T.: On the adiabatic theorem of quantum mechanics. Journal of the Physical Society of Japan 5(6), 435–439 (1950). https://doi.org/10.1143/JPSJ.5.435
  * [15] Khalil, E., Dai, H., Zhang, Y., Dilkina, B., Song, L.: Learning Combinatorial Optimization Algorithms over Graphs. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems. vol. 30. Curran Associates, Inc. (2017)
  * [16] Kipf, T.N., Welling, M.: Variational graph auto-encoders. Preprint at https://arxiv.org/abs/1611.07308 (2016)
  * [17] Kirkpatrick, S., Toulouse, G.: Configuration space analysis of travelling salesman problems. Journal de Physique 46(8), 1277–1292 (1985). https://doi.org/10.1051/jphys:019850046080127700
  * [18] Lucas, A.: Ising formulations of many np problems. Frontiers in Physics 2, 5 (02 2014). https://doi.org/10.3389/fphy.2014.00005
  * [19] McGeoch, C.C.: Adiabatic quantum computation and quantum annealing: Theory and practice. Synthesis Lectures on Quantum Computing 5(2), 1–93 (2014)
  * [20] Mnih, V., et al.: Playing atari with deep reinforcement learning. Preprint at https://arxiv.org/abs/1312.5602 (2013)
  * [21] Mnih, V., et al.: Asynchronous methods for deep reinforcement learning. In: International conference on machine learning. pp. 1928–1937. PMLR (2016)
  * [22] Pan, S., Hu, R., Long, G., Jiang, J., Yao, L., Zhang, C.: Adversarially regularized graph autoencoder for graph embedding. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. p. 2609–2615. AAAI Press (2018). https://doi.org/10.24963/ijcai.2018/362
  * [23] Peng, J., Williams, R.J.: Incremental multi-step q-learning. In: Machine Learning Proceedings 1994, pp. 226–232. Elsevier (1994). https://doi.org/10.1016/B978-1-55860-335-6.50035-0
  * [24] Pudenz, K.L., Albash, T., Lidar, D.A.: Error-corrected quantum annealing with hundreds of qubits. Nature communications 5(1), 1–10 (2014). https://doi.org/10.1038/ncomms4243
  * [25] Pudenz, K.L., Albash, T., Lidar, D.A.: Quantum annealing correction for random ising problems. Phys. Rev. A 91, 042302 (Apr 2015). https://doi.org/10.1103/PhysRevA.91.042302
  * [26] Rosenberg, G., Haghnegahdar, P., Goddard, P., Carr, P., Wu, K., De Prado, M.L.: Solving the optimal trading trajectory problem using a quantum annealer. IEEE Journal of Selected Topics in Signal Processing 10(6), 1053–1060 (2016). https://doi.org/10.1109/JSTSP.2016.2574703
  * [27] Santoro, G.E., Martoňák, R., Tosatti, E., Car, R.: Theory of quantum annealing of an ising spin glass. Science 295(5564), 2427–2430 (2002). https://doi.org/10.1126/science.1068774
  * [28] Silver, D., et al.: A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science 362(6419), 1140–1144 (2018). https://doi.org/10.1126/science.aar6404
  * [29] Sutton, R.S., Barto, A.G.: Reinforcement learning: An introduction. MIT press (2018). https://doi.org/10.1007/978-1-4615-3618-5
  * [30] Vinci, W., Albash, T., Paz-Silva, G., Hen, I., Lidar, D.A.: Quantum annealing correction with minor embedding. Phys. Rev. A 92 (2015). https://doi.org/10.1103/PhysRevA.92.042310