Intuitively, $M(f_{0})$ acts as $\mathbb{1}\otimes\sigma_{x}$; $M(f_{2})$ acts
as $\sigma_{x}\otimes\mathbb{1}$; $M(g_{0})$ acts as
$\mathbb{1}\otimes\sigma_{z}$ and $M(g_{2})$ acts as
$\sigma_{z}\otimes\mathbb{1}$; and similarly on Bob’s side.

$|\psi\rangle$$|x_{0}\rangle$$|x_{0}\rangle$$QFT_{d}$$QFT_{d}$$O_{A}$$O_{B}$$QFT_{d}^{-1}$$QFT_{d}^{-1}$$U_{A}$$U_{B}$$|reuse\rangle$$|\tilde{\psi}\rangle^{EXT}$
Figure 1: The isometries $\Phi_{A,1}\otimes\Phi_{B,1}$.

The isometry $\Phi_{A,1}\otimes\Phi_{B,1}$ has the following steps:

  1. 1.

Append control register $|x_{0}\rangle_{A^{\prime}}$ on Alice’s side and
$|x_{0}\rangle_{B^{\prime}}$ on Bob’s side;

  2. 2.

Apply Quantum Fourier Transform ($QFT_{d}$) to Alice and Bob’s control
registers;

  3. 3.

Apply Controlled-$O_{A/B}$ operations (i.e. if the control register is in
state $|x_{k}\rangle_{A^{\prime}/B^{\prime}}$, apply $O_{A/B}^{k}$.);

  4. 4.

Apply inverse Quantum Fourier Transform ($QFT_{d}^{-1}$) to the control
registers;

  5. 5.

Apply Controlled-$U_{A/B}$ operations (i.e. If Alice’s control register is in
state $|x_{j}\rangle$, she applies $U_{A}^{\log_{r}(d-j)}$. If Bob’s control
register is in state $|x_{j}\rangle$, he applies $(U_{B})^{\log_{r}j}$).

Note that $|x_{0}\rangle$ is orthogonal to $W_{d-1}$, so
$\operatorname{span}\\{x_{j}\\}_{j=0}^{d-1}$ has dimension $d$.

$|reuse\rangle$$|0\rangle$$|0\rangle$$|0\rangle$$|0\rangle$$H$$H$$H$$H$$M(g_{2})$$N(g_{2})$$M(g_{0})$$N(g_{0})$$H$$H$$H$$H$$M(f_{2})$$N(f_{2})$$M(f_{0})$$N(f_{0})$$|junk\rangle$$|EPR\rangle^{\otimes
2}$ Figure 2: The isometries $\Phi_{A,2}\otimes\Phi_{B,2}$.

The second isometry is the standard isometry used in the self-testing result
of the Magic Square game [WBMS16]. The only thing to note is that the state
$|reuse\rangle$, which is on the same Hilbert space as $|\psi\rangle$ and
produced by $\Phi_{A,1}\otimes\Phi_{B,1}$, is the input state to
$\Phi_{A,2}\otimes\Phi_{B,2}$. In this sense, our isometry is a $2$-step
sequential procedure.

###### Proof of Theorem 6.17.

The proof takes two steps. We first show that

$\displaystyle\Phi_{A,1}\otimes\Phi_{B,1}(|\psi\rangle)\simeq_{O(d^{5/2}r^{d}\epsilon^{1/8})}\sqrt{d-1}|\psi_{1}\rangle\otimes\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}|x_{d-j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}.$
(92)

Then we show that there exists a state $|junk\rangle$ such that

$\displaystyle\Phi_{A,2}\otimes\Phi_{B,2}(\sqrt{d-1}|\psi_{1}\rangle)\simeq_{O(\sqrt{r}\sqrt{\epsilon})}|junk\rangle\otimes|\Sigma^{(2)}\rangle^{\otimes
2}.$ (93)

Combining the two equations above we get that

$\displaystyle\quad\Phi_{A,2}\otimes\Phi_{B,2}(\Phi_{A,1}\otimes\Phi_{B,1}(|\psi\rangle))$
$\displaystyle\simeq_{O(d^{5/2}r^{d}\epsilon^{1/8})}\left[\Phi_{A,2}\otimes\Phi_{B,2}(\sqrt{d-1}|\psi_{1}\rangle)\right]\otimes\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}|x_{d-j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}|junk\rangle\otimes|EPR\rangle^{\otimes
2}\otimes\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}|x_{d-j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}},$

where we use the fact that $\Phi_{A,2}\otimes\Phi_{B,2}$ only acts
nontrivially on the state $|\psi_{1}\rangle$. The state
$\sqrt{d-1}|\psi_{1}\rangle$ is the state $|reuse\rangle$ in the two figures.

Lemma 6.15 implies that
$\Phi_{A,1}\otimes\Phi_{B,1}(|\psi\rangle)\simeq_{O(dr^{d/2+1/4}\epsilon^{1/8})}\Phi_{A,1}\otimes\Phi_{B,1}(|\psi^{\prime}\rangle)$,
so we focus on how the isometry evolves $|\psi^{\prime}\rangle$. The evolution
is summarized below.

$\displaystyle\sum_{j=1}^{d-1}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle|x_{0}\rangle_{A^{\prime}}|x_{0}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{QFT_{d}}$
$\displaystyle\frac{1}{d}\sum_{k_{1},k_{2}=0}^{d-1}\sum_{j=1}^{d-1}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle|x_{k_{1}}\rangle_{A^{\prime}}|x_{k_{2}}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{\text{Controlled-}O_{A/B}}$
$\displaystyle\frac{1}{d}\sum_{k_{1},k_{2}=0}^{d-1}\sum_{j=1}^{d-1}O_{A}^{k_{1}}(U_{A}^{\dagger})^{\log_{r}j}O_{B}^{k_{2}}(U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle|x_{k_{1}}\rangle_{A^{\prime}}|x_{k_{2}}\rangle_{B^{\prime}}$
$\displaystyle\simeq_{O(d^{5/2}r^{d}\epsilon^{1/4})}$
$\displaystyle\frac{1}{d}\sum_{k_{1},k_{2}=0}^{d-1}\sum_{j=1}^{d-1}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}\omega_{d}^{(k_{2}-k_{1})j}|\psi_{1}\rangle|x_{k_{1}}\rangle_{A^{\prime}}|x_{k_{2}}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{QFT_{d}^{-1}}$
$\displaystyle\frac{1}{d^{2}}\sum_{l_{1},l_{2}=0}^{d-1}\sum_{k_{1},k_{2}=0}^{d-1}\sum_{j=1}^{d-1}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}\omega_{d}^{k_{1}(d-j-
l_{1})}\omega_{d}^{k_{2}(j-l_{2})}|\psi_{1}\rangle|x_{l_{1}}\rangle_{A^{\prime}}|x_{l_{2}}\rangle_{B^{\prime}}$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{d-1}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle|x_{d-j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{\text{Controlled-}U_{A/B}}$
$\displaystyle\sum_{j=1}^{d-1}U_{A}^{\log_{r}j}(U_{A}^{\dagger})^{\log_{r}j}U_{B}^{\log_{r}j}(U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle|x_{d-j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}$
$\displaystyle=$
$\displaystyle|\psi_{1}\rangle\otimes\sum_{j=1}^{d-1}|x_{d-j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}.$

When we analyze the effect of the controlled-$O_{A/B}$, we applied eqs. 83 and
82 repeatedly. In summary, we have shown that

$\displaystyle\Phi_{A,1}\otimes\Phi_{B,1}(|\psi\rangle)\simeq_{O(d^{5/2}r^{d}\epsilon^{1/8})}\left(\sqrt{d-1}|\psi_{1}\rangle\right)\otimes\left(\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}|x_{d-j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}\right),$
(94)

where we use the fact that $O(d^{5/2}r^{d}\epsilon^{1/8})$ dominates both
$O(dr^{d/2+1/4}\epsilon^{1/8})$ and $O(d^{5/2}r^{d}\epsilon^{1/4})$. The
relation
$\sqrt{d-1}\lVert|\psi_{1}\rangle\rVert\simeq_{O(\sqrt{d}r^{1/4}\epsilon^{1/4})}1$
is derived from the fact that
$\lVert|\psi_{1}\rangle\rVert^{2}\simeq_{O(\sqrt{r}\sqrt{\epsilon})}1/(d-1)$.

To prove eq. 93, we first recall that

$\displaystyle|\psi_{1}\rangle=\frac{1}{2}(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1}-iM_{n(r)+2}M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle.$

The other observation that we need is that

$\displaystyle\Phi_{A,2}\otimes\Phi_{B,2}(|\psi_{1}\rangle)$ $\displaystyle=$
$\displaystyle\frac{1}{16}\sum_{\boldsymbol{a},\boldsymbol{b}\in\\{0,1\\}^{4}}M(f_{0})^{a(4)}N(f_{0})^{b(4)}M(f_{2})^{a(3)}N(f_{2})^{b(3)}M(g_{0})^{a(2)}N(g_{0})^{b(2)}M(g_{2})^{a(1)}N(g_{2})^{b(1)}|\psi_{1}\rangle|\boldsymbol{a}\rangle_{A^{\prime\prime}}|\boldsymbol{b}\rangle_{B^{\prime\prime}}$

For simplicity we define

$\displaystyle
M^{\boldsymbol{a}}:=M(f_{0})^{a(4)}M(f_{2})^{a(3)}M(g_{0})^{a(2)}M(g_{2})^{a(1)}$
$\displaystyle
N^{\boldsymbol{b}}:=N(f_{0})^{b(4)}N(f_{2})^{b(3)}N(g_{0})^{b(2)}N(g_{2})^{b(1)}.$

Our goal is to use Proposition 6.16 to show that

$\displaystyle
M^{\boldsymbol{a}}|\psi_{1}\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}\frac{1}{2}(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1}-iM_{n(r)+2}M_{n(r)+1}^{0}+M_{n(r)+1}^{1})M^{\boldsymbol{a}}|\psi\rangle,$
(95)

for all $\boldsymbol{a}\in\\{0,1\\}^{4}$,

We show how to apply Proposition 6.16 to commute $M(g_{2})^{a(1)}$ through
$\frac{1}{2}(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1}\\\
-iM_{n(r)+2}M_{n(r)+1}^{0}+M_{n(r)+1}^{1})$ and then similar process can be
repeated for $M(g_{0})^{a(2)},M(f_{2})^{a(3)}$ and $M(f_{0})^{a(4)}$ using
Lemma 2.17,

$\displaystyle\quad
M(g_{2})^{a(1)}\frac{1}{2}(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1}-iM_{n(r)+2}M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}\frac{1}{2}[(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})M(g_{2})^{a(1)}-iM(g_{2})^{a(1)}M_{n(r)+2}N_{n(r)+1}]|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}\frac{1}{2}[(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})M(g_{2})^{a(1)}-iN_{n(r)+1}M_{n(r)+2}M(g_{2})^{a(1)}]|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}\frac{1}{2}[(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})M(g_{2})^{a(1)}-iM_{n(r)+2}M(g_{2})^{a(1)}M_{n(r)+1}]|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}\frac{1}{2}[(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})M(g_{2})^{a(1)}-iM_{n(r)+2}M_{n(r)+1}M(g_{2})^{a(1)}]|\psi\rangle$
$\displaystyle=\frac{1}{2}(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1}-iM_{n(r)+2}M_{n(r)+1}^{0}+M_{n(r)+1}^{1})M(g_{2})^{a(1)}|\psi\rangle.$

In summary, we have

$\displaystyle
M^{\boldsymbol{a}}N^{\boldsymbol{b}}|\psi_{1}\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}\frac{1}{2}(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1}-iM_{n(r)+2}M_{n(r)+1}^{0}+M_{n(r)+1}^{1})M^{\boldsymbol{a}}N^{\boldsymbol{b}}|\psi\rangle$
(96)

for all $\boldsymbol{a},\boldsymbol{b}\in\\{0,1\\}^{4}$, which implies that

$\displaystyle\Phi_{A,2}\otimes$
$\displaystyle\Phi_{B,2}(|\psi_{1}\rangle)\simeq_{O(\sqrt{r}\sqrt{\epsilon})}$
$\displaystyle\frac{1}{2}(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1}-iM_{n(r)+2}M_{n(r)+1}^{0}+M_{n(r)+1}^{1})(\Phi_{A,2}\otimes\Phi_{B,2}(|\psi\rangle).$

At this point we can apply Lemma C.$1$ of [WBMS16] to
$\Phi_{A,2}\otimes\Phi_{B,2}(|\psi\rangle)$ and conclude that

$\displaystyle\Phi_{A,2}\otimes\Phi_{B,2}(\sqrt{d-1}|\psi_{1}\rangle)\simeq_{O(\sqrt{d}\sqrt{r}\sqrt{\epsilon})}|junk\rangle\otimes|EPR\rangle^{\otimes
2},$ (97)

for some state $|junk\rangle$ whose norm can be deduced from the norm of
$|\psi_{1}\rangle$.

In the rest of the proof, we only show how $\Phi_{A,1}\otimes\Phi_{B,1}$ acts
on $O_{A}|\psi\rangle$ and $U_{A}|\psi\rangle$.

If the initial state is $O_{A}|\psi\rangle$, we first use the fact that
$\Phi_{A,1}\otimes\Phi_{B,1}(O_{A}|\psi\rangle)\simeq_{O(dr^{d/2+1/4}\epsilon^{1/8})}\Phi_{A,1}\otimes\Phi_{B,1}(O_{A}|\psi^{\prime}\rangle)$,
and then we calculate
$\Phi_{A,1}\otimes\Phi_{B,1}(O_{A}|\psi^{\prime}\rangle)$ as

$\displaystyle
O_{A}|\psi^{\prime}\rangle|x_{0}\rangle_{A^{\prime}}|x_{0}\rangle_{B^{\prime}}=$
$\displaystyle\sum_{j=1}^{d-1}O_{A}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle|x_{0}\rangle_{A^{\prime}}|x_{0}\rangle_{B^{\prime}}$
$\displaystyle\simeq_{O(\sqrt{d}r^{d}\epsilon^{1/4})}$
$\displaystyle\sum_{j=1}^{d-1}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}\omega_{d}^{-j}|\psi_{1}\rangle|x_{0}\rangle_{A^{\prime}}|x_{0}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{QFT_{d}}$
$\displaystyle\frac{1}{d}\sum_{j=1}^{d-1}\sum_{k_{1},k_{2}=0}^{d-1}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}\omega_{d}^{-j}|\psi_{1}\rangle|x_{k_{1}}\rangle_{A^{\prime}}|x_{k_{2}}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{\text{Controlled-}O_{A/B}}$
$\displaystyle\frac{1}{d}\sum_{j=1}^{d-1}\sum_{k_{1},k_{2}=0}^{d-1}O_{A}^{k_{1}}(U_{A}^{\dagger})^{\log_{r}j}O_{B}^{k_{2}}(U_{B}^{\dagger})^{\log_{r}j}\omega_{d}^{-j}|\psi_{1}\rangle|x_{k_{1}}\rangle_{A^{\prime}}|x_{k_{2}}\rangle_{B^{\prime}}$
$\displaystyle\simeq_{O(d^{5/2}r^{d}\epsilon^{1/4})}$
$\displaystyle\frac{1}{d}\sum_{k_{1},k_{2}=0}^{d-1}\sum_{j=1}^{d-1}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}\omega_{d}^{-j}\omega_{d}^{(k_{2}-k_{1})j}|\psi_{1}\rangle|x_{k_{1}}\rangle_{A^{\prime}}|x_{k_{2}}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{QFT_{d}^{-1}}$
$\displaystyle\sum_{j=1}^{d-1}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}\omega_{d}^{d-j}|\psi_{1}\rangle|x_{d-j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{\text{Controlled-}U_{A/B}}$
$\displaystyle\sqrt{d-1}|\psi_{1}\rangle\otimes\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}\omega_{d}^{d-j}|x_{d-j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}.$

The analysis for $\Phi_{A,1}\otimes\Phi_{B,1}(O_{B}|\psi\rangle)$ is very
similar.

If the initial state is $U_{A}|\psi\rangle$, we first use the fact that
$\Phi_{A,1}\otimes\Phi_{B,1}(U_{A}|\psi\rangle)\simeq_{O(dr^{d/2+1/4}\epsilon^{1/8})}\Phi_{A,1}\otimes\Phi_{B,1}(U_{A}|\psi^{\prime}\rangle)$,
and then we calculate
$\Phi_{A,1}\otimes\Phi_{B,1}(U_{A}|\psi^{\prime}\rangle)$.

$\displaystyle
U_{A}|\psi^{\prime}\rangle|x_{0}\rangle_{A^{\prime}}|x_{0}\rangle_{B^{\prime}}=$
$\displaystyle\sum_{j=1}^{d-1}U_{A}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle|x_{0}\rangle_{A^{\prime}}|x_{0}\rangle_{B^{\prime}}$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{d-1}(U_{A}^{\dagger})^{\log_{r}j-1}(U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle|x_{0}\rangle_{A^{\prime}}|x_{0}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{QFT_{d}}$
$\displaystyle\frac{1}{d}\sum_{j=1}^{d-1}\sum_{k_{1},k_{2}=0}^{d-1}(U_{A}^{\dagger})^{\log_{r}j-1}(U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle|x_{k_{1}}\rangle_{A^{\prime}}|x_{k_{2}}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{\text{Controlled-}O_{A/B}}$
$\displaystyle\frac{1}{d}\sum_{j=1}^{d-1}\sum_{k_{1},k_{2}=0}^{d-1}O_{A}^{k_{1}}(U_{A}^{\dagger})^{\log_{r}j-1}O_{B}^{k_{2}}(U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle|x_{k_{1}}\rangle_{A^{\prime}}|x_{k_{2}}\rangle_{B^{\prime}}$
$\displaystyle\simeq_{O(d^{5/2}r^{d}\epsilon^{1/4})}$
$\displaystyle\frac{1}{d}\sum_{k_{1},k_{2}=0}^{d-1}\sum_{j=1}^{d-1}(U_{A}^{\dagger})^{\log_{r}j-1}(U_{B}^{\dagger})^{\log_{r}j}\omega_{d}^{k_{2}j-k_{1}jr^{-1}}|\psi_{1}\rangle|x_{k_{1}}\rangle_{A^{\prime}}|x_{k_{2}}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{QFT_{d}^{-1}}$
$\displaystyle\sum_{j=1}^{d-1}(U_{A}^{\dagger})^{\log_{r}j-1}(U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle|x_{(d-j)r^{-1}}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{\text{Controlled-}U_{A/B}}$
$\displaystyle\sqrt{d-1}|\psi_{1}\rangle\otimes\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}|x_{(d-j)r^{-1}}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}},$

where we use the fact that $(d-j)r^{-1}\equiv d-jr^{-1}\pmod{d}$. The analysis
for $\Phi_{A,1}\otimes\Phi_{B,1}(U_{B}|\psi\rangle)$ is very similar. ∎

In the next two propositions, we show $\mathfrak{C}(d,r)$ can robustly self-
test $\tilde{O}_{1}$ and $\tilde{O}_{2}$ on Alice and Bob’s sides
respectively.

######  Proposition 6.19.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$. Then there exists an isometry
$\Phi^{\prime}_{A}\otimes\Phi^{\prime}_{B}=(\Phi_{A,2}\otimes\Phi_{B,2})(\Phi^{\prime}_{A,1}\otimes\Phi^{\prime}_{B,1})$
and a state $|junk^{\prime}\rangle$ such that
$\lVert|junk^{\prime}\rangle\rVert\simeq_{O(\sqrt{d}r^{1/4}\epsilon^{1/4})}1$
and

$\displaystyle\Phi^{\prime}_{A}\otimes\Phi^{\prime}_{B}(M_{1}|\psi\rangle)\simeq_{O(d^{5/2}r^{d}\epsilon^{1/8}))}|junk\rangle\otimes|EPR\rangle^{\otimes
2}\otimes\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}\omega_{d}^{j}|x_{j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}$
$\displaystyle\Phi^{\prime}_{A}\otimes\Phi^{\prime}_{B}(M_{2}|\psi\rangle)\simeq_{O(d^{5/2}r^{d}\epsilon^{1/8}))}|junk\rangle\otimes|EPR\rangle^{\otimes
2}\otimes\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}|x_{j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}.$

###### Proof.

Comparing to $(\Phi_{A,1}\otimes\Phi_{B,1})$, the only difference in
$(\Phi^{\prime}_{A,1}\otimes\Phi^{\prime}_{B,1})$ is in the
Controlled-$U_{A/B}$ step. In
$(\Phi^{\prime}_{A,1}\otimes\Phi^{\prime}_{B,1})$, when the control register
is in the state $|x_{j}\rangle$, both Alice and Bob will apply
$U_{A/B}^{\log_{r}j}$. Since this is the only difference, the proof focuses on
the effect of $(\Phi^{\prime}_{A,1}\otimes\Phi^{\prime}_{B,1})$.

Since
$\Phi_{A,1}\otimes\Phi_{B,1}(|\psi\rangle)\simeq_{O(dr^{d/2+1/4}\epsilon^{1/8})}\Phi_{A,1}\otimes\Phi_{B,1}(|\psi^{\prime}\rangle)$,
we focus on $M_{1}|\psi^{\prime}\rangle$ and $M_{2}|\psi^{\prime}\rangle$. By
Proposition 6.14, we know that

$\displaystyle M_{1}|\psi^{\prime}\rangle$
$\displaystyle=M_{1}M_{2}M_{2}|\psi^{\prime}\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}\sum_{j=1}^{d-1}O_{A}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}M_{2}|\psi_{1}\rangle$
$\displaystyle\simeq_{O(r^{d}\sqrt{r}\sqrt{\epsilon}\sqrt{d})}\sum_{j=1}^{d-1}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}\omega_{d}^{j}M_{2}|\psi_{1}\rangle,$

so we first calculate
$\Phi_{A,1}\otimes\Phi_{B,1}(M_{2}|\psi^{\prime}\rangle)$, which is

$\displaystyle\sum_{j=1}^{d-1}M_{2}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle|x_{0}\rangle_{A^{\prime}}|x_{0}\rangle_{B^{\prime}}$
$\displaystyle\simeq_{O(d^{2}\sqrt{r}\sqrt{\epsilon})}$
$\displaystyle\sum_{j=1}^{d-1}M_{2}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}M_{2}|\psi_{1}\rangle|x_{0}\rangle_{A^{\prime}}|x_{0}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{QFT_{d}}$
$\displaystyle\frac{1}{d}\sum_{k_{1},k_{2}=0}^{d-1}\sum_{j=1}^{d-1}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}M_{2}|\psi_{1}\rangle|x_{k_{1}}\rangle_{A^{\prime}}|x_{k_{2}}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{\text{Controlled-}O_{A/B}}$
$\displaystyle\frac{1}{d}\sum_{k_{1},k_{2}=0}^{d-1}\sum_{j=1}^{d-1}O_{A}^{k_{1}}(U_{A}^{\dagger})^{\log_{r}j}O_{B}^{k_{2}}(U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle|x_{k_{1}}\rangle_{A^{\prime}}|x_{k_{2}}\rangle_{B^{\prime}}$
$\displaystyle\simeq_{O(d^{5/2}r^{d}\epsilon^{1/4})}$
$\displaystyle\frac{1}{d}\sum_{k_{1},k_{2}=0}^{d-1}\sum_{j=1}^{d-1}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}\omega_{d}^{(k_{2}+k_{1})j}M_{2}|\psi_{1}\rangle|x_{k_{1}}\rangle_{A^{\prime}}|x_{k_{2}}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{QFT_{d}^{-1}}$
$\displaystyle\sum_{j=1}^{d-1}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}M_{2}|\psi_{1}\rangle|x_{j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}$
$\displaystyle\xrightarrow[]{\text{Controlled-}U_{A/B}}$
$\displaystyle\sum_{j=1}^{d-1}U_{A}^{\log_{r}j}(U_{A}^{\dagger})^{\log_{r}j}U_{B}^{\log_{r}j}(U_{B}^{\dagger})^{\log_{r}j}M_{2}|\psi_{1}\rangle|x_{j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}$
$\displaystyle=$ $\displaystyle
M_{2}|\psi_{1}\rangle\otimes\sum_{j=1}^{d-1}|x_{j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}.$

Then it is easy to see that

$\displaystyle\Phi_{A,1}\otimes\Phi_{B,1}(M_{2}|\psi^{\prime}\rangle)\simeq_{O(r^{d}d^{5/2}\epsilon^{1/4})}M_{2}|\psi_{1}\rangle\otimes\sum_{j=1}^{d-1}\omega_{d}^{j}|x_{j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}},$

which completes the proof. ∎

######  Proposition 6.20.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$. Then there exists an isometry
$\Phi^{\prime\prime}_{A}\otimes\Phi^{\prime\prime}_{B}=(\Phi_{A,2}\otimes\Phi_{B,2})(\Phi^{\prime\prime}_{A,1}\otimes\Phi^{\prime\prime}_{B,1})$
and a state $|junk^{\prime}\rangle$ such that
$\lVert|junk^{\prime}\rangle\rVert\simeq_{O(\sqrt{d}r^{1/4}\epsilon^{1/4})}1$
and

$\displaystyle\Phi^{\prime\prime}_{A}\otimes\Phi^{\prime\prime}_{B}(N_{1}|\psi\rangle)\simeq_{O(d^{5/2}r^{d}\epsilon^{1/8}))}|junk^{\prime}\rangle\otimes|EPR\rangle^{\otimes
2}\otimes\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}\omega_{d}^{-j}|x_{j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}$
$\displaystyle\Phi^{\prime\prime}_{A}\otimes\Phi^{\prime\prime}_{B}(N_{2}|\psi\rangle)\simeq_{O(d^{5/2}r^{d}\epsilon^{1/8}))}|junk^{\prime}\rangle\otimes|EPR\rangle^{\otimes
2}\otimes\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}|x_{j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}.$

Since the proof is very similar to the proof of the previous proposition, we
omit the proof here. Instead, we just state the difference between
$(\Phi^{\prime\prime}_{A,1}\otimes\Phi^{\prime\prime}_{B,1})$ and
$(\Phi^{\prime}_{A,1}\otimes\Phi^{\prime}_{B,1})$. Once again, the difference
is in the Controlled-$U_{A/B}$ step. In
$(\Phi^{\prime\prime}_{A,1}\otimes\Phi^{\prime\prime}_{B,1})$, when the
control register is in the state $|x_{j}\rangle$, both lice and Bob will apply
$U_{A/B}^{\log_{r}(d-j)}$.

##  7 Conclusions

In summary, we identify a family of correlations with constant-sized input and
output alphabets that can be used to robustly self-test maximally entangled
states with unbounded local dimension. Before our work, the most efficient way
was to use $O(\log d)$-sized input and $O(\log\log d)$-sized output alphabets
to robustly self-test the maximally entangled state of dimension $d=2^{n}$
[NV18].

Our result gives us deeper understandings of the set of quantum correlations.
In previous works that proved the non-closeness of the set of quantum
correlations [Slo19, SV18], lower bounds of the entanglement required to
achieve certain correlations are identified. We discover a large family of
correlations such that we know exactly the entangled state required to achieve
each of the correlations in this family.

## Acknowledgment

The author is deeply grateful to his PhD advisor, Carl Miller, for the
enlightening discussions with him, his patient guidance and useful critiques
through this project. His original ideas about combining a linear system game
with a Bell inequality and characterizing prime numbers by their primitive
roots are invaluable to this work. He also helped the author with the design
of the extended weighted CHSH test and the editing of the draft.

## References

  * [AMP12] Antonio Acín, Serge Massar, and Stefano Pironio.  Randomness versus nonlocality and entanglement.  Physical review letters, 108(10):100402, 2012.  doi:10.1103/PhysRevLett.108.100402.
  * [Ara04] Padmanabhan K. Aravind.  Quantum mysteries revisited again.  American Journal of Physics, 72(10):1303–1307, 2004.  doi:10.1119/1.1773173.
  * [BP15] Cédric Bamps and Stefano Pironio.  Sum-of-squares decompositions for a family of Clauser-Horne-Shimony-Holt-like inequalities and their application to self-testing.  Physical Review A, 91(5):052111, 2015.  doi:10.1103/PhysRevA.91.052111.
  * [CGJV19] Andrea Coladangelo, Alex B Grilo, Stacey Jeffery, and Thomas Vidick.  Verifier-on-a-leash: new schemes for verifiable delegated quantum computation, with quasilinear resources.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 247–277. Springer, 2019.  doi:10.1007/978-3-030-17659-4_9.
  * [CGS17] Andrea Coladangelo, Koon Tong Goh, and Valerio Scarani.  All pure bipartite entangled states can be self-tested.  Nature communications, 8:15485, 2017.  doi:10.1038/ncomms15485.
  * [CHSH69] John F Clauser, Michael A Horne, Abner Shimony, and Richard A Holt.  Proposed experiment to test local hidden-variable theories.  Physical review letters, 23(15):880, 1969.  doi:10.1103/PhysRevLett.23.880.
  * [Col16] Andrea W Coladangelo.  Parallel self-testing of (tilted) EPR pairs via copies of (tilted) CHSH.  arXiv preprint arXiv:1609.03687, 2016.
  * [CS17a] Andrea Coladangelo and Jalex Stark.  Robust self-testing for linear constraint system games.  arXiv preprint arXiv:1709.09267, 2017.
  * [CS17b] Andrea Coladangelo and Jalex Stark.  Separation of finite and infinite-dimensional quantum correlations, with infinite question or answer sets.  arXiv preprint arXiv:1708.06522, 2017.
  * [DF04] David Steven Dummit and Richard M Foote.  Abstract algebra, volume 3.  Wiley Hoboken, 2004.
  * [FJVY19] Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen.  Quantum proof systems for iterated exponential time, and beyond.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 473–480. ACM, 2019.  doi:10.1145/3313276.3316343.
  * [FM18] Honghao Fu and Carl A Miller.  Local randomness: Examples and application.  Physical Review A, 97(3):032324, 2018.  doi:10.1103/PhysRevA.97.032324.
  * [Mur88] Maruti Ram Murty.  Artin’s conjecture for primitive roots.  The Mathematical Intelligencer, 10(4):59–67, 1988.  doi:10.1007/BF03023749.
  * [MY98] Dominic Mayers and Andrew Yao.  Quantum cryptography with imperfect apparatus.  In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), pages 503–509. IEEE, 1998.  doi:10.1109/SFCS.1998.743501.
  * [MYS12] Matthew McKague, Tzyh Haur Yang, and Valerio Scarani.  Robust self-testing of the singlet.  Journal of Physics A: Mathematical and Theoretical, 45(45):455304, 2012.  doi:10.1088/1751-8113/45/45/455304.
  * [NV17] Anand Natarajan and Thomas Vidick.  A quantum linearity test for robustly verifying entanglement.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1003–1015. ACM, 2017.  doi:10.1145/3055399.3055468.
  * [NV18] Anand Natarajan and Thomas Vidick.  Low-degree testing for quantum states, and a quantum entangled games ${PCP}$ for ${QMA}$.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 731–742. IEEE, 2018.  doi:10.1109/FOCS.2018.00075.
  * [NW19] Anand Natarajan and John Wright.  ${NEEXP}$ is Contained in ${MIP}^{\ast}$.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 510–518. IEEE, 2019.  doi:10.1109/FOCS.2019.00039.
  * [RUV13] Ben W Reichardt, Falk Unger, and Umesh Vazirani.  Classical command of quantum systems.  Nature, 496(7446):456, 2013.  doi:10.1038/nature12035.
  * [Slo19] William Slofstra.  The set of quantum correlations is not closed.  In Forum of Mathematics, Pi, volume 7. Cambridge University Press, 2019.  doi:10.1017/fmp.2018.3.
  * [SV18] William Slofstra and Thomas Vidick.  Entanglement in non-local games and the hyperlinear profile of groups.  In Annales Henri Poincaré, volume 19, pages 2979–3005. Springer, 2018.  doi:10.1007/s00023-018-0718-y.
  * [WBMS16] Xingyao Wu, Jean-Daniel Bancal, Matthew McKague, and Valerio Scarani.  Device-independent parallel self-testing of two singlets.  Physical Review A, 93(6):062121, 2016.  doi:10.1103/PhysRevA.93.062121.
  * [YN13] Tzyh Haur Yang and Miguel Navascués.  Robust self-testing of unknown quantum systems into any entangled two-qubit states.  Physical Review A, 87(5):050102, 2013.  doi:10.1103/PhysRevA.87.050102.

##  Appendix A The linear system of $LS(r)$

######  Definition A.1.

The linear system of $LS(r)$ has variables $x(s)$ for each $s\in S$, and
equations:

  * •

for each $1\leq i\leq r+5$:

$\displaystyle x(a_{i})+x(b_{i})+x(c_{i})=0$ $\displaystyle
x(a_{i})+x(f_{0})+x(d_{i})=0$ $\displaystyle x(b_{i})+x(f_{2})+x(p_{i,1})=0$
$\displaystyle x(p_{i,2})+x(p_{i,3})+x(p_{i,4})=0$ $\displaystyle
x(f_{0})+x(p_{i,3})+x(p_{i,4})=0$ $\displaystyle
x(c_{i})+x(p_{i,4})+x(p_{i,5})=0$ $\displaystyle
x(f_{1})+x(p_{i,2})+x(p_{i,3})=0;$

  * •

for each $\boldsymbol{c}=(i,j,k)\in C(r)$:

$\displaystyle x(h_{jk})+x(b_{j})+x(c_{k})=0$ $\displaystyle
x(d_{i})+x(q_{\boldsymbol{c},1})+x(f_{2})=0$ $\displaystyle
x(b_{j})+x(f_{2})+x(q_{\boldsymbol{c},2})=0$ $\displaystyle
x(q_{\boldsymbol{c},2})+x(q_{\boldsymbol{c},3})+x(q_{\boldsymbol{c},4})=0$
$\displaystyle x(d_{i})+x(q_{\boldsymbol{c},4})+x(q_{\boldsymbol{c},5})=0$
$\displaystyle x(c_{k})+x(q_{\boldsymbol{c},5})+x(q_{\boldsymbol{c},6})=0$
$\displaystyle
x(q_{\boldsymbol{c},1})+x(q_{\boldsymbol{c},3})+x(q_{\boldsymbol{c},6})=0;$

  * •

Magic Square equations:

$\displaystyle x(f_{0})+x(f_{1})+x(f_{2})=0$ $\displaystyle
x(g_{0})+x(g_{1})+x(g_{2})=0$ $\displaystyle x(m_{0})+x(m_{1})+x(m_{2})=0$
$\displaystyle x(f_{0})+x(g_{2})+x(m_{0})=0$ $\displaystyle
x(f_{2})+x(g_{0})+x(m_{1})=0$ $\displaystyle x(f_{1})+x(g_{1})+x(m_{2})=1.$

##  Appendix B A representation of $\Gamma$

In this section we give the full description of a representation of $\Gamma$,
$\Psi$, which is built upon representations of $\mathcal{P}_{0}$ and
$\mathcal{P}_{1}$. We need the representation $\Psi$ of $\Gamma$ to construct
the ideal strategy of $LS(r)$.

Recall the two Hilbert spaces $W_{d-1}$ and $W_{2}$ defined in eq. 19, which
are the carrier spaces of the representations given below, On the Hilbert
space $W_{2}$, we define

$\displaystyle X_{W_{2}}=|x_{1}\rangle\langle x_{2}|+|x_{2}\rangle\langle
x_{1}|$ $\displaystyle Y_{W_{2}}=i|x_{1}\rangle\langle
x_{2}|-i|x_{2}\rangle\langle x_{1}|$ $\displaystyle
Z_{W_{2}}=|x_{1}\rangle\langle x_{1}|-|x_{2}\rangle\langle x_{2}|,$

######  Definition B.1.

The representation, $\Psi_{0}$, of $\mathcal{P}_{0}$ on $W_{d-1}$ is defined
by

$\displaystyle\Psi_{0}(a_{1})=$
$\displaystyle\sum_{j=1}^{(d-1)/2}\omega_{d}^{j}|x_{j}\rangle\langle
x_{d-j}|+\omega_{d}^{-j}|x_{d-j}\rangle\langle x_{j}|$
$\displaystyle\Psi_{0}(a_{2})=$
$\displaystyle\sum_{j=1}^{d-1}|x_{j}\rangle\langle x_{d-j}|$
$\displaystyle\Psi_{0}(a_{3})=$ $\displaystyle|u_{0}\rangle\langle
u_{0}|+\omega_{d-1}^{(d-1)/2}|u_{(d-1)/2}\rangle\langle u_{(d-1)/2}|$
$\displaystyle+$
$\displaystyle\sum_{k=1}^{(d-3)/2}\left(\omega_{d-1}^{k}|u_{k}\rangle\langle
u_{d-1-k}|+\omega_{d-1}^{-k}|x_{d-1-k}\rangle\langle x_{k}|\right)$
$\displaystyle\Psi_{0}(a_{4})=$ $\displaystyle|u_{0}\rangle\langle
u_{0}|+|u_{(d-1)/2}\rangle\langle u_{(d-1)/2}|$ $\displaystyle+$
$\displaystyle\sum_{k=1}^{(d-3)/2}\left(|u_{d-1-k}\rangle\langle
u_{k}|+|u_{k}\rangle\langle u_{d-1-k}|\right),$

The representation of the rest of the generators can be constructed from
$\Psi_{0}(a_{1})$, $\Psi_{0}(a_{2})$, $\Psi_{0}(a_{3})$ and $\Psi_{0}(a_{4})$
following the defining conjugacy relations in $\mathcal{P}_{0}$.

We can check that

$\displaystyle\Psi_{0}(a_{1}a_{2})=\sum_{j=0}^{d-2}\omega_{d}^{r^{j}}|x_{r^{j}}\rangle\langle
x_{r^{j}}|=\tilde{O}$
$\displaystyle\Psi_{0}(a_{3}a_{4})=\sum_{j=0}^{d-2}|x_{r^{j-1}}\rangle\langle
x_{r^{j}}|=\tilde{U},$

where $\tilde{O}$ and $\tilde{U}$ are defined in eqs. 20 and 21. We can also
check that the representation $\Psi_{0}$ satisfies the relations that
$\Psi_{0}(a_{3}a_{4})\Psi_{0}(a_{2})\Psi_{0}(a_{4}a_{3})=\Psi_{0}(a_{2})$ by
first observing that

$\displaystyle\Psi_{0}(a_{3})\Psi_{0}(a_{4})=\sum_{j=0}^{d-2}|x_{r^{j-1}}\rangle\langle
x_{r^{j}}|.$

Then we can calculate

$\displaystyle\Psi_{0}(a_{3})\Psi_{0}(a_{4})\Psi_{0}(a_{2})\Psi_{0}(a_{4})\Psi_{0}(a_{3})$
$\displaystyle=$
$\displaystyle\sum_{j=0}^{(d-3)/2}\Psi_{0}(a_{3})\Psi_{0}(a_{4})(|x_{r^{j}}\rangle\langle
x_{r^{d-1-j}}|+|x_{r^{d-1-j}}\rangle\langle
x_{r^{j}}|)\Psi_{0}(a_{4})\Psi_{0}(a_{3})$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{(d-3)/2}|x_{r^{j-1}}\rangle\langle
x_{r^{d-2-j}}|+|x_{r^{d-2-j}}\rangle\langle x_{r^{j-1}}|$ $\displaystyle=$
$\displaystyle\Psi_{0}(a_{2}).$

Next, following the proof of Lemma $29$ of [Slo19], we construct a
representation of $\mathcal{P}_{1}$.

######  Definition B.2.

The representation $\Psi_{1}$ of $\mathcal{P}_{1}$ on $W_{2}\otimes W_{d-1}$
is defined by

  * •

for $f_{0}$

$\displaystyle\Psi_{1}(f_{0})=X_{W_{2}}\otimes\mathbb{1}_{W_{d-1}};$

  * •

for $i=1\dots r+5$,

$\displaystyle\Psi_{1}(a_{i})=\mathbb{1}_{W_{2}}\otimes\Psi_{0}(a_{i})$
$\displaystyle\Psi_{1}(b_{i})=|x_{1}\rangle\langle
x_{1}|\otimes\Psi_{0}(a_{i})+|x_{2}\rangle\langle
x_{2}|\otimes\mathbb{1}_{W_{d-1}}$
$\displaystyle\Psi_{1}(c_{i})=|x_{1}\rangle\langle
x_{1}|\otimes\mathbb{1}_{W_{d-1}}+|x_{2}\rangle\langle
x_{2}|\otimes\Psi_{0}(a_{i})$
$\displaystyle\Psi_{1}(d_{i})=X_{W_{2}}\otimes\Psi_{0}(a_{i});$

  * •

for $(i,j,k)\in C(r)$,

$\displaystyle\Psi_{1}(h_{jk})=|x_{1}\rangle\langle
x_{1}|\otimes\Psi_{0}(a_{j})+|x_{2}\rangle\langle
x_{2}|\otimes\Psi_{0}(a_{k}).$

Finally, we follow the proof of Proposition $27$ of [Slo19] to construct the
representation $\Psi$ of $\Gamma$.

######  Definition B.3.

The representation $\Psi$ of $\Gamma$ on $W_{2}\otimes W_{2}\otimes W_{d-1}$
is defined by:

  * •

for $s\in\\{a_{i},b_{i},c_{i},d_{i}\\}_{i=1}^{r+5}$,

$\displaystyle\Psi(s)=\mathbb{1}_{W_{2}}\otimes\Psi_{1}(s);$

  * •

for $f_{i}$, $g_{i}$, $m_{i}$ with $i=0,1,2$ and $J$

$\displaystyle\Psi(f_{0})=\mathbb{1}\otimes
X_{W_{2}}\otimes\mathbb{1}_{W_{d-1}}$
$\displaystyle\Psi(f_{1})=X_{W_{2}}\otimes
X_{W_{2}}\otimes\mathbb{1}_{W_{d-1}}$
$\displaystyle\Psi(f_{2})=X_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{d-1}}$
$\displaystyle\Psi(g_{0})=\mathbb{1}\otimes
Z_{W_{2}}\otimes\mathbb{1}_{W_{d-1}}$
$\displaystyle\Psi(g_{1})=Z_{W_{2}}\otimes
Z_{W_{2}}\otimes\mathbb{1}_{W_{d-1}}$
$\displaystyle\Psi(g_{2})=Z_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{d-1}}$
$\displaystyle\Psi(m_{0})=Z_{W_{2}}\otimes
X_{W_{2}}\otimes\mathbb{1}_{W_{d-1}}$
$\displaystyle\Psi(m_{1})=X_{W_{2}}\otimes
Z_{W_{2}}\otimes\mathbb{1}_{W_{d-1}}$
$\displaystyle\Psi(m_{2})=Y_{W_{2}}\otimes
Y_{W_{2}}\otimes\mathbb{1}_{W_{d-1}}$
$\displaystyle\Psi(J)=-\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{d-1}};$

  * •

for the generators involved in $R_{i}$ with $1\leq i\leq r+5$ :

$\displaystyle\Psi(p_{i,1})$ $\displaystyle=X_{W_{2}}\otimes\Psi_{1}(b_{i})$
$\displaystyle\Psi(p_{i,2})$ $\displaystyle=|x_{1}\rangle\langle
x_{2}|\otimes\Psi_{1}(b_{i}f_{0})+|x_{2}\rangle\langle
x_{1}|\otimes\Psi_{1}(f_{0}b_{i})$ $\displaystyle\Psi(p_{i,3})$
$\displaystyle=|x_{1}\rangle\langle
x_{1}|\otimes\Psi_{1}(b_{i}f_{0}b_{i})+|x_{2}\rangle\langle
x_{2}|\otimes\Psi_{1}(f_{0})$ $\displaystyle\Psi(p_{i,4})$
$\displaystyle=|x_{1}\rangle\langle
x_{1}|\otimes\Psi_{1}(b_{i}c_{i})+|x_{2}\rangle\langle
x_{2}|\otimes\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{d-1}}$
$\displaystyle\Psi(p_{i,5})$ $\displaystyle=|x_{1}\rangle\langle
x_{1}|\otimes\Psi_{1}(b_{i})+|x_{2}\rangle\langle
x_{2}|\otimes\Psi_{1}(c_{i});$

  * •

for the generators involved in $R_{\boldsymbol{c}}$ with
$\boldsymbol{c}=(i,j,k)\in C(r)$:

$\displaystyle\Psi(q_{\boldsymbol{c},1})$
$\displaystyle=X_{W_{2}}\otimes\Psi_{1}(d_{i})$
$\displaystyle\Psi(q_{\boldsymbol{c},2})$
$\displaystyle=X_{W_{2}}\otimes\Psi_{1}(b_{j})$
$\displaystyle\Psi(q_{\boldsymbol{c},3})$ $\displaystyle=|x_{1}\rangle\langle
x_{2}|\otimes\Psi_{1}(b_{j}d_{i})+|x_{2}\rangle\langle
x_{1}|\otimes\Psi_{1}(d_{i}b_{j})$ $\displaystyle\Psi(q_{\boldsymbol{c},4})$
$\displaystyle=|x_{1}\rangle\langle
x_{1}|\otimes\Psi_{1}(b_{j}d_{i}b_{j})+|x_{2}\rangle\langle
x_{2}|\otimes\Psi_{1}(d_{i})$ $\displaystyle\Psi(q_{\boldsymbol{c},5})$
$\displaystyle=|x_{1}\rangle\langle
x_{1}|\otimes\Psi_{1}(b_{j}c_{k})+|x_{2}\rangle\langle
x_{2}|\otimes\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{d-1}}$
$\displaystyle\Psi(q_{\boldsymbol{c},6})$ $\displaystyle=|x_{1}\rangle\langle
x_{1}|\otimes\Psi_{1}(b_{j})+|x_{2}\rangle\langle
x_{2}|\otimes\Psi_{1}(c_{k}).$

The validation of $\Psi_{1}$ and $\Psi$ were done in the proofs of Lemma $29$
and Proposition $27$ in [Slo19].

##  Appendix C The proof of Theorem 4.1

This proof follows the same line of argument in Appendix A of [BP15]. We first
find two sum-of-square decompositions of
$2\sqrt{\alpha^{2}+1}\mathbb{1}-\mathcal{I}_{\alpha}$, where
$\mathcal{I}_{\alpha}$ is expressed in terms of $\\{M_{x}\\}$ and
$\\{N_{y}\\}$. The decompositions allow us to determine some key relations
between Alice and Bob’s observables and their shared state, which will be used
to draw the conclusion.

###### Proof.

The first step is to find a sum-of-square decomposition of the following Bell
expression

$\displaystyle\bar{\mathcal{I}}_{\alpha}=2\sqrt{\alpha^{2}+1}\mathbb{1}-\mathcal{I}_{\alpha}=\frac{2}{\sin(\mu)}\mathbb{1}-\frac{\cos(\mu)}{\sin(\mu)}(M_{1}N_{1}+M_{1}N_{2})-M_{2}N_{1}+M_{2}N_{2}.$
(98)

With the notation $c:=\cos(\mu)$, $s:=\sin(\mu)$, we define

$\displaystyle Z_{A}:=M_{1}$ $\displaystyle X_{A}:=M_{2}$ $\displaystyle
Z_{B}:=\frac{N_{1}+N_{2}}{2c}$ $\displaystyle X_{B}:=\frac{N_{1}-N_{2}}{2s}.$

The two SOS decompositions that we use are

$\displaystyle\bar{\mathcal{I}}_{\alpha}=\frac{s\bar{\mathcal{I}}_{\alpha}^{2}+4sc^{2}(Z_{A}X_{B}+X_{A}Z_{B})^{2}}{4},$
(99)
$\displaystyle\bar{\mathcal{I}}_{\alpha}=\frac{c^{2}}{s}(Z_{A}-Z_{B})^{2}+s(X_{A}-X_{B})^{2}.$
(100)

The verification is omitted here. From the SOS decomposition, we can prove
eqs. 26, 27, 28, 29, 30 and 31.

We first define

$\displaystyle S_{1}=\frac{\sqrt{s}}{2}\bar{\mathcal{I}}_{\alpha},$
$\displaystyle S_{2}=\sqrt{s}c(Z_{A}X_{B}+X_{A}Z_{B}),$ $\displaystyle
S_{3}=\frac{c}{\sqrt{s}}(Z_{A}-Z_{B}),$ $\displaystyle
S_{4}=\sqrt{s}(X_{A}-X_{B})$

then

$\displaystyle\bar{\mathcal{I}}_{\alpha}=S_{1}^{2}+S_{2}^{2}=S_{3}^{2}+S_{4}^{2}.$
(101)

The fact that the quantum strategy
$(|\psi\rangle,\\{M_{x}\\}_{x=1,2},\\{N_{y}\\}_{y=1,2}$ achieves that
$\langle\bar{\mathcal{I}}_{\alpha}\rangle\leq\epsilon$ implies that

$\displaystyle\langle\psi|S_{i}^{2}|\psi\rangle\leq\epsilon,$

and equivalently,

$\displaystyle\lVert S_{i}|\psi\rangle\rVert\leq\sqrt{\epsilon}$

for $i=1,2,3,4$. From the definitions of $S_{i}$’s, we can get that

$\displaystyle\lVert(X_{A}Z_{B}+X_{B}Z_{A})|\psi\rangle\rVert\leq\frac{1}{c\sqrt{s}}\sqrt{\epsilon}$
(102)
$\displaystyle\lVert(Z_{A}-Z_{B})|\psi\rangle\rVert\leq\frac{\sqrt{s}}{c}\sqrt{\epsilon}$
(103)
$\displaystyle\lVert(X_{A}-X_{B})|\psi\rangle\rVert\leq\frac{1}{\sqrt{s}}\sqrt{\epsilon},$
(104)

which proves eqs. 26 and 27. Equations 102 and 103 give us that

$\displaystyle\lVert[Z_{A}(\mathbb{1}+X_{B})-(\mathbb{1}-X_{A})Z_{B}]|\psi\rangle\rVert\leq\lVert(X_{A}Z_{B}+X_{B}Z_{A})|\psi\rangle\rVert+\lVert(Z_{A}-Z_{B})|\psi\rangle\rVert\leq\frac{s+1}{c\sqrt{s}}\sqrt{\epsilon},$

which proves eq. 28. Similarly, eqs. 102 and 104 give us that

$\displaystyle\lVert[X_{A}(\mathbb{1}+Z_{B})-X_{B}(\mathbb{1}-Z_{A})]|\psi\rangle\rVert\leq\frac{c+1}{c\sqrt{s}}\sqrt{\epsilon},$

which proves eq. 29. Since
$Z_{A}X_{A}+X_{A}Z_{A}=\frac{S_{2}}{c\sqrt{s}}+\frac{\sqrt{s}\tilde{X}_{A}S_{3}}{c}+\frac{\tilde{Z}_{A}S_{4}}{\sqrt{s}}$,
we can deduce that

$\displaystyle\lVert(Z_{A}X_{A}+X_{A}Z_{A})|\psi\rangle\rVert\leq\frac{1+c+s}{c\sqrt{s}}\sqrt{\epsilon},$

as in eq. 30. To prove eq. 31, we switch to the approximate relation form and
derive that

$\displaystyle X_{A}Z_{A}|\psi\rangle$
$\displaystyle\simeq_{\frac{1+c+s}{c\sqrt{s}}\sqrt{\epsilon}}-Z_{A}X_{A}|\psi\rangle$
(105)
$\displaystyle\simeq_{\frac{\sqrt{s}}{c}\sqrt{\epsilon}}-Z_{A}X_{B}|\psi\rangle$
(106)
$\displaystyle\simeq_{\frac{1}{s^{3/2}}\sqrt{\epsilon}}-X_{B}Z_{B}|\psi\rangle,$
(107)

where in the last line we use the fact $\lVert X_{B}\rVert\leq 1/s$.

Now we introduce the isometries $\Phi_{A}$ and $\Phi_{B}$ mentioned in the
theorem. They are the same as the ones used in [BP15]. To construct $\Phi_{A}$
and $\Phi_{B}$ we need to regularize $Z_{B}$ and $X_{B}$ to make sure the
corresponding operations are unitary in the isometries. We define
$Z_{B}^{\ast}$ to be the operator obtained from $Z_{B}$ by changing all the
$0$-eigenvalues to $1$, then we define

$\displaystyle Z_{B}^{\prime}:=Z_{B}^{\ast}|Z_{B}^{\ast}|^{-1},$

where $|Z_{B}^{\ast}|$ is obtained from $Z_{B}^{\ast}$ by replacing all
negative eigenvalues by its absolute value. In a similar way, we define
$X_{B}^{\ast}$ and $X_{B}^{\prime}$. On Alice’s side, since $Z_{A}$ and
$X_{A}$ are unitaries already, we define $Z_{A}^{\prime}:=Z_{A}$ and
$X_{A}^{\prime}=X_{A}$. The isometries are illustrated in the figure below.

$|\tilde{\psi}\rangle$$|0\rangle$$|0\rangle$HH$Z_{A}^{\prime}$$Z_{B}^{\prime}$HH$X_{A}^{\prime}$$X_{B}^{\prime}$$|aux\rangle$$\frac{|00\rangle+|11\rangle}{\sqrt{2}}$
Figure 3: The isometries $\Phi_{A}$ and $\Phi_{B}$.

To bound
$e_{xy}:=\lVert(\Phi_{A}\otimes\Phi_{B})(\tilde{M}_{x}\otimes\tilde{N}_{y})|\tilde{\psi}\rangle-|junk\rangle\otimes(M_{x}\otimes
N_{y})|\Sigma^{(2)}\rangle\rVert$, there are some intermediate steps. Since
the derivations are the same as in [BP15], we only record the key relations
here.

$\displaystyle\lVert(Z_{B}^{\prime}-Z_{B})|\tilde{\psi}\rangle\rVert\leq\frac{\sqrt{s}}{c}\sqrt{\epsilon},$
$\displaystyle\lVert(Z_{B}^{\prime}-Z_{A}^{\prime})|\tilde{\psi}\rangle\rVert\leq
2\frac{\sqrt{s}}{c}\sqrt{\epsilon},$
$\displaystyle\lVert(X_{B}^{\prime}-X_{B})|\tilde{\psi}\rangle\rVert\leq\frac{c+1}{s^{3/2}}\sqrt{\epsilon}:=\delta_{1}\sqrt{\epsilon},$
$\displaystyle\lVert(X_{B}^{\prime}Z_{B}^{\prime}+Z_{B}^{\prime}X_{B}^{\prime})|\tilde{\psi}\rangle\rVert\leq[\frac{2\sqrt{s}}{c}+\frac{2}{\sqrt{s}}+2\delta_{1}+(\sqrt{2}+\frac{1}{c})(2\frac{\sqrt{s}}{c}+\frac{1+c+s}{c\sqrt{s}})]\sqrt{\epsilon}:=\delta_{2}\sqrt{\epsilon}.$

Then we can calculate that

$\displaystyle e_{00}=e_{10}=2\delta_{2}\sqrt{\epsilon}$ $\displaystyle
e_{20}=2(\frac{1+c+s}{c\sqrt{s}}+\delta_{2})\sqrt{\epsilon}$ $\displaystyle
e_{01}=e_{02}=e_{11}=e_{12}=[\sqrt{s}+s(2\frac{1+c+s}{c\sqrt{s}}+\delta_{1})+2\delta_{2}]\sqrt{\epsilon}$
$\displaystyle
e_{21}=e_{22}=[2\frac{1+c+s}{c\sqrt{s}}+\sqrt{s}+s(2\frac{1+c+s}{c\sqrt{s}}+\delta_{1})+2\delta_{2}]\sqrt{\epsilon},$

so an upper bound of the error is that

$\displaystyle e_{xy}\in
O((\frac{1}{c^{2}s^{1/2}}+\frac{1}{s^{3/2}})\sqrt{\epsilon})\quad\quad\forall
x,y\in\\{0,1,2\\}.$ (108)

∎


# EmProx: Neural Network Performance Estimation
For Neural Architecture Search

G.G.H. Franken Eindhoven University of Technology  P. Singh Eindhoven
University of Technology  J. Vanschoren Eindhoven University of Technology

###### Abstract

Common Neural Architecture Search methods generate large amounts of candidate
architectures that need training in order to assess their performance and find
an optimal architecture. To minimize the search time we use different
performance estimation strategies. The effectiveness of such strategies varies
in terms of accuracy and fit and query time. This study proposes a new method,
EmProx Score (Embedding Proximity Score). Similar to Neural Architecture
Optimization (NAO), this method maps candidate architectures to a continuous
embedding space using an encoder-decoder framework. The performance of
candidates is then estimated using _weighted kNN_ based on the embedding
vectors of architectures of which the performance is known. Performance
estimations of this method are comparable to the MLP performance predictor
used in NAO in terms of accuracy, while being nearly nine times faster to
train compared to NAO. Benchmarking against other performance estimation
strategies currently used shows similar to better accuracy, while being five
up to eighty times faster.

Code is made publicly available on
GitHub111https://github.com/GideonFr/EmProx.

##  1 Introduction

Neural architecture search (NAS) is the science of automatically designing
novel neural network architectures for a specific task. The NAS problem is
described as follows in White et al., (2021): given architectures $a$ from
search space $\mathcal{A}$, find the optimal architecture $a^{*}$ as
$a^{*}=\operatorname*{arg\,min}_{a\in\mathcal{A}}f(a)$, where $f$ denotes the
validation error of architecture $a$ on a fixed dataset for a fixed number of
epochs $\mathit{E}$. However, evaluating $f(a)$ requires significant
computational resources. Hence, performance predictor $f^{\prime}$ is
leveraged, defined as any function that predicts $f(a)$ without fully training
$a$. Evaluating $f^{\prime}$ should take significantly less time than
evaluating $f$ and desirably $\\{f^{\prime}(a)\mid a\in\mathcal{A}\\}$ has a
high correlation with $\\{f(a)\mid a\in\mathcal{A}\\}$

We propose a new performance predictor $f^{\prime}$ called EmProx Score
(Embedding Proximity Score) as a faster alternative for Neural Architecture
Optimization (NAO) (Luo et al.,, 2018). Similar to NAO, EmProx uses an
encoder-decoder framework to map candidate architectures to a continuous
embedding space. However, instead of training an multi-layer perceptron (MLP)
on the embedding vectors to predict the accuracy of a candidate, EmProx uses
_weighted k-nearest neighbors_ on the embedding vectors. As such, EmProx
estimates the performance of the query architecture based on the distance and
accuracy of its nearest neighbors in the embedding space, which can be
computed efficiently.

In the remainder of this paper, we first describe background and related work
in Section 2. Section 3 describes the EmProx procedure in more detail, and
Section 4 discusses implementation and evaluation details. Section 5 evaluates
this method against a wide range of alternative approaches, and Section 6
concludes.

##  2 Related work

NAS methods consist of three components: the search space, the search
strategy/(optimizer) and the performance estimation strategy (Elsken et al.,,
2018). Figure 1 shows how these components relate to each other.

###  2.1 Differentiable architecture search

The search space describes the way architectures are defined and what
architectures can be discovered. A commonly used approach is a cell search
space, in which small networks (cells) are learned which are then repeated in
a macro-architecture. This discrete search space can also be made continuous
by defining a zero-shot architecture, a super-network consisting of all
possible operations, and then applying continuous relaxation, adding a
continuous meta-parameter for every possible option, as is done in DARTS (Liu
et al.,, 2018).

---
Figure 1: The three components of a Neural Architecture Search algorithm. The
search space defines the model architectures that can be discovered. The
search strategy selects architectures from the search space to evaluate. To
evaluate an architecture, a performance estimation strategy is used. Usually,
this strategy returns the expected architecture’s accuracy to the search
strategy to further guide the architecture search.

The search strategy defines how the search space is explored to select
candidate architectures, usually leveraging performance estimations of
previous candidates to select more promising candidates. Common strategies
include evolutionary algorithms (Real et al.,, 2017) and reinforcement
learning methods (Baker et al.,, 2016). Gradient-based techniques can also be
used: DARTS leverages weight sharing, optimizing both the meta-parameters and
the model weights at the same time using bilevel optimization, thus evaluating
multiple architectures simultaneously. While this is very efficient, the
downside is that many performance estimation strategies are not applicable to
DARTS.

###  2.2 Neural Architecture Optimization

A solution to this problem is offered by Neural Architecture Optimization
(NAO), by Luo et al., (2018). It maps a neural network architecture $x$ to an
embedding space using an encoder-decoder model, as shown in Figure 2. The
output of the encoder is a continuous feature vector $e_{x}$ (i.e., an
embedding), that captures the semantics of the architecture that served as
input for the encoder. A performance predictor (NAO uses an MLP) then uses the
embedding $e_{x}$ to predict the architecture’s accuracy. The output of the
performance predictor is then maximized using gradient ascent to find
$e_{x}^{\prime}$, the embedding of an improved architecture $x^{\prime}$. To
get architecture $x^{\prime}$, the decoder maps $e_{x}^{\prime}$ back to the
discrete space. This framework, using a performance predictor in a continuous
search space, allows NAO to perform gradient-based search in the embedding
space quickly. An important limitation of NAO is that the performance
predictor (MLP) first needs to be trained, which is a practical bottleneck.
This study, as described in detail in section 3, proposes a modification of
NAO that uses a performance estimation strategy that makes the MLP redundant.

---
Figure 2: The NAO framework. Architecture $x$ is mapped to a continuous
embedding space by the encoder. Using its embedding $e_{x}$ and predictor $f$,
its performance is predicted. Then the performance of $e_{x}$ is optimized
into $e_{x}^{\prime}$ by maximizing the output of predictor $f$ using gradient
ascent. To get the improved architecture $x^{\prime}$, the decoder maps
$e_{x}^{\prime}$ to the discrete space. From Luo et al., (2018).

###  2.3 Performance estimation strategies

Performance estimation strategies, or performance predictors, were developed
since it is often infeasible in NAS to train every candidate architecture from
scratch. NAO uses an MLP, but many alternatives exist. These are often divided
into the following categories: 1) lower fidelity estimates, 2) learning curve
extrapolation, 3) weight inheritance and 4) one-shot models/weight sharing.
The first method reduces training times by training for fewer epochs, a subset
of the data, downscaled models etc. The second method aims to extrapolate
performance from a few epochs of training. In the third method, models are not
trained from scratch, but initialized by inheriting weights from a parent
model. The fourth category, used in DARTS, trains only a single large one-shot
model, using the loss of the current one-shot model itself to optimize both
the meta-parameters and model weights. Next to these methods, surrogate models
can also be used to predict the performance of candidate pipelines. While NAO
uses an MLP, we will leverage _weighted kNN_ as a surrogate model.

##  3 Methods

EmProx uses an encoder-decoder framework to map candidate architectures to a
continuous embedding space. It then estimates the performance of any new
architecture based on the distance and accuracy of its nearest neighbors,
previously evaluated candidate architectures, in the embedding space. The
justification for this method is as follows. NAO creates embeddings of
candidate architectures to guide the search and predicts the performance of
candidates using an MLP on the embeddings. Training this MLP adds a
significant time cost to the search, and would be redundant if we can predict
the performance of architectures based one the embeddings in a simpler way.
Our proposed method does exactly that: using the embeddings and the accuracy
of other architectures the performance of candidates is predicted using kNN,
which does not need any training, making the MLP redundant and thus lowering
the time cost of the framework. Figure 3 shows the framework of EmProx and the
remainder of this section describes this in more detail.

---
Figure 3: The EmProx framework. During training, architectures $a$ encoded as
a sequence are mapped to embedding space $\epsilon$ using encoder $EC$ to
create continuous architecture embeddings $e_{a}$. Consequently, they are
mapped back to the discrete space, their original form $a$, by decoder $DC$ to
be able to learn informative embeddings. During inference, the $k$
architectures with known validation accuracy that are the closest to each
respective candidate architecture are used to estimate the accuracy of the
candidate as weighted average using inverse distance weighting. In the image
an example is shown with $k=2$.

###  3.1 Learning the embedding

Neural network architectures can be represented as a directed acyclic graph.
Such graphs can be represented as an adjacency matrix, as shown in Figure 4.
Rows and columns represent operations such as convolutions and pooling layers
and the values inside the adjacency matrix indicate the existence of a
connection between operations in the graph. Consequently, the adjacency matrix
can be shown as a sequence, such that a whole architecture can be encoded as a
sequence.

---
Figure 4: (a) the way layers and operations in a neural network are connected
and (b) the representation as an adjacency matrix and vector.

This sequence, describing architecture $a$, serves as input for the framework.
At training time, encoder $EC$ maps architecture $a$ to the continuous
embedding space $\mathcal{E}$, denoted as $EC:\mathcal{A}\mapsto\mathcal{E}$.
Then for all $a\in\mathcal{A}$ we have $e_{a}=EC(a)$, the embedding of
architecture $a$. Given the high dimensionality of the embedding space, the
embedding vectors are normalized. Then the decoder $DC$ maps $e_{a}$ back to
its original architecture $a$, denoted as $DC:\mathcal{E}\mapsto\mathcal{A}$.
During training, the negative log likelihood loss between the original input
and the output of the decoder is minimized. At inference time, to create
embedding vectors for the query architectures, the sequences $a$ describing
their architectures are fed to encoder $EC$ only.

Both the encoder and decoder consist of a single LSTM layer with a hidden
dimension of 128, resulting in an embedding dimension of 128. This dimension
was established empirically in the experiments described in section 5. As in
the original NAO paper, to better enable the decoder to reconstruct the input,
an attention mechanism is used.

###  3.2 Performance estimation

We hypothesize that the encoder-decoder framework maps similar architectures
with similar performance closely to each other in the embedding space, such
that performance of a new architecture can be inferred from architectures in
its vicinity in the embedding space. This is capitalized on as follows. During
inference, we have two sets of architectures: one set containing architectures
with known accuracy $\mathcal{A}_{known}$ and one set of architectures with
unknown accuracy $\mathcal{A}_{unknown}$ for which we want to predict the
performance. Both sets are mapped to the embedding space by encoder $EC$ such
that we get two new sets. One set containing the embeddings of architectures
with known accuracies $E_{\mathcal{A}_{known}}=\\{EC(a)\mid
a\in\mathcal{A}_{known}\\}$ and one set of which we want to predict accuracies
$E_{\mathcal{A}_{unknown}}=\\{EC(a)\mid a\in\mathcal{A}_{unknown}\\}$.

We then calculate the distance between all elements in these two sets
$\\{g(E_{\mathcal{A}_{known}}\times E_{\mathcal{A}_{unknown}})\\}$. Here, $g$
denotes the Euclidean distance function, which can be used given that the
embedding vectors are normalized. Subsequently, we place the $k$ closest
neighboring architectures to each $a\in\mathcal{A}_{unknown}$ in set $N_{a}$.
Here, $k$ is a hyperparameter to be chosen later. Then for all
$a\in\mathcal{A}_{unknown}$ and neighboring architectures $i=1,...,k$ in
$N_{a}$ we calculate the weight $w_{i}$ based on inverse distance weighting.
This is defined as $w_{i}=\frac{1}{g(e_{a},e_{i})}$. Lastly, the predicted
accuracy $\hat{s}_{a}$ of architecture $a$ is calculated as the weighted
average of the accuracies $s_{i}$ of neighbors $i=1,...,k$:
$\hat{s}_{a}=\frac{\sum_{i=1}^{k}w_{i}(\mathbf{x})s_{i}}{\sum_{i=1}^{k}w_{i}(\mathbf{x})}$.

Figure 5 shows a plot of the learned embeddings, where tSNE was used to reduce
the dimensionality to 2. The colors, ranging from red (bad) to green (good),
indicate the accuracy of the embedded architectures. As can be seen by the red
dotted clusters, several groups of badly performing architectures are grouped
together, indicating that the encoder-decoder framework indeed maps similar
performing architectures closely to each other in the embedding space.

---
Figure 5: 2D plot of the learned architecture embeddings $e_{a}$ after
reducing the embedding dimesionality to 2 using tSNE. Colors indicate the
accuracy of the respective embedded NAS-Bench-201 architectures on the CIFAR10
dataset. The plot shows groups of architectures with similar performance close
to each other, which shows that performance of candidate architectures can be
estimated from architectures that lie close by in embedding space

##  4 Implementation and Evaluation

To lower the computational barriers for NAS research, Ying et al., (2019)
composed NAS-Bench 101, a dataset consisting of 423k unique neural network
architectures and their performance evaluated on the CIFAR-10 dataset. This
allows for benchmarking NAS algorithms without the necessity to train
candidate models from scratch. Likewise, NAS-Bench-201 (Dong and Yang,, 2020)
operates on a cell-based search space, NAS-Bench-301 (Siems et al.,, 2020) on
DARTS, and NAS-Bench-360 (Tu et al.,, 2021), on a more diverse set of tasks
than CIFAR and Imagenet classification. The strategy proposed in this study is
evaluated on NAS-Bench-201 in order to allow the most fair comparison with the
strategies evaluated in White et al., (2021) using NASlib.

NASLib Ruchte et al., (2020) is a modular framework that implemented many
state-of-the-art NAS methods and building blocks like search spaces, search
strategies and performance estimation strategies that can be used with only a
few lines of code. White et al., (2021) added a total of 31 different neural
architecture performance predictor methods to the NASLib framework, and
compared them on NAS-Bench-201 with respect to initialization time, query time
and performance.

We evaluate how well our and other performance estimation strategies can
predict the actual accuracy of a candidate model in terms of RMSE, MAE and
Pearson’s correlation coefficient, Spearman’s Rho, and Kendall Tau. Based on
Pearson and Spearman, White et al., (2021) found that the best methods were
Early Stopping (on validation accuracy), GCN (Wen et al.,, 2019), Jacobian
Covariance (Mellor et al.,, 2020), LcSVR (Baker et al.,, 2017), SoTL-E (Ru et
al.,, 2020), SemiNAS (Luo et al.,, 2020) and XGBoost (Chen and Guestrin,,
2016). However, not all of these methods could be compared to ours in a fair
way. For instance, Early Stopping is not model-based and could hence not be
compared in terms of fit time. Others, such as GCN, far exceeded our resource
limitations, which made the comparison infeasible as well as less informative
given our focus on efficiency and previously published benchmarks. Hence, to
give a fair overview of competitors we chose to benchmark against NAO,
SemiNAS, XGBoost and BANANAS (White et al.,, 2019) and an MLP.

To allow a direct comparison, we implemented our method as an addition to
NASLib and evaluated it on NAS-Bench-201 architectures in the same manner as
in White et al., (2021), as explained in section 5.

For training and testing, the evaluation framework that is used randomly
samples architectures from NAS-Bench-201 until a training set of 121 and a
test set of 100 architectures are sampled (random sampling could technically
lead to data leakage, though this risk is deemed negligible due to the size of
NAS-Bench and the impact of a single architecture being in both the train and
test set). This means that 121, a value taken from White et al., (2021),
architectures are used to learn the embeddings.

##  5 Empirical Evaluation

We implemented EmProx in NASLib and experiments were performed using the same
framework as White et al., (2021) 222Available at
https://github.com/automl/naslib. This ensured a fair comparison to other
performance estimation strategies implemented in NASLib. In the experiments,
the performance predictors of NAO, SemiNAS, XGBoost, BANANAS (White et al.,,
2019) and an MLP were tasked with estimating the performance of NAS-Bench-201
architectures on the CIFAR-10 dataset. In NAS-Bench, the architectures and
their validation accuracies are stored. This allowed us to evaluate the
performance of the predictors without having to train all architectures on the
CIFAR-10 dataset from scratch. As a result, no GPU was required and all
experiments have been performed on a single Intel Xeon E5-2698v4 CPU.

Method | Regression metrics | Correlation coefficients | Time metrics (s)
---|---|---|---
| MAE | RMSE | Pearson | Spearman | Kendall | Fit time | Query time
EmProx ($k=10$) | 4.4027 $\pm$ 1.0269 | 10.7163 $\pm$ 2.9690 | 0.4771 $\pm$ 0.1497 | 0.7304 $\pm$ 0.0645 | 0.5453 $\pm$ 0.0537 | 6.4498 $\pm$ 0.9846 | 0.0009 $\pm$ 0.0008
EmProx ($k=60$) | 4.5264 $\pm$ 0.9625 | 10.7953 $\pm$ 3.1221 | 0.5044 $\pm$ 0.0963 | 0.7332 $\pm$ 0.0865 | 0.5468 $\pm$ 0.0718 | 7.2310 $\pm$ 1.0598 | 0.0032 $\pm$ 0.0004
NAO | 4.7336 $\pm$ 1.0260 | 10.9394 $\pm$ 2.8279 | 0.4512 $\pm$ 0.1335 | 0.7131 $\pm$ 0.0657 | 0.5279 $\pm$ 0.0608 | 54.1674 $\pm$ 0.3493 | 0.0026 $\pm$ 0.0002
SemiNAS | 4.0283 $\pm$ 0.8023 | 10.1222 $\pm$ 2.2704 | 0.5307 $\pm$ 0.1604 | 0.7677 $\pm$ 0.0568 | 0.5822 $\pm$ 0.0564 | 152.2268 $\pm$ 42.5809 | 0.0012 $\pm$ 0.0007
XGB | 5.3989 $\pm$ 1.3110 | 12.2955 $\pm$ 3.5906 | 0.4008 $\pm$ 0.2224 | 0.6466 $\pm$ 0.0597 | 0.4719 $\pm$ 0.0476 | 31.6526 $\pm$ 3.9272 | 0.0004 $\pm$ 0.0001
BANANAS | 7.3007 $\pm$ 1.1988 | 12.2760 $\pm$ 2.0153 | 0.3793 $\pm$ 0.1937 | 0.4169 $\pm$ 0.0959 | 0.2910 $\pm$ 0.0653 | 507.3936 $\pm$ 13.87 | 0.0002 $\pm$ 0.0001
MLP | 6.8584 $\pm$ 1.6152 | 11.3592 $\pm$ 2.2580 | 0.4417 $\pm$ 0.1142 | 0.5298 $\pm$ 0.0996 | 0.3759 $\pm$ 0.0777 | 471.7508 $\pm$ 6.2376 | $<$0.0001 $\pm$ $<$0.0001

Table 1: Experiment results on the CIFAR10 dataset with NAS-Bench-201
architectures, averaged over 20 trials. Above are the results of the method
proposed in this study, below are several methods evaluated in White et al.,
(2021). Underlined are the best results of EmProx and the best results among
the other predictors for ease of comparison. As can be seen, EmProx scores
competitively regarding regression and correlation coefficients and scores
much better regarding fit time.

As part of the experiments, a grid search was performed to find the dimension
of the hidden layer (i.e. embedding dimension) and EmProx hyperparameter $k$.
The results of this grid search can be found in the Appendix. Other model and
training parameters were left unchanged and taken from White et al., (2021)
and the paper of NAO by Luo et al., (2018).

The results of the performance predictors were expressed in terms of
regression metrics MAE and RMSE between the predicted candidate architecture
accuracy and the validation accuracy from NAS-Bench. Additionally, it has to
be noted that in many NAS algorithms the exact predicted performance is not of
importance, rather than the rank of a certain architecture among other
candidates, since only the most promising architectures are trained. This is
incorporated in the experiments by including correlation-based performance
measures Pearson, Spearman and Kendall’s Tau on the predicted and validation
accuracies. Furthermore, since ultimately the goal of performance predictors
is to speed up the search, fit time and query time are included as measures.
For EmProx the fit time includes the learning of the embeddings and the query
time the creation of the embedding for a query architecture and the
performance estimation. The hyperparameter search was conducted to explore the
sensitivity and performance of the method towards its hyperparameters and is
hence not included in the fit time.

From the grid search it was found that a hidden layer dimension (i.e.
embedding dimension) of 32 yielded the best results. Regarding the number of
neighbors $k$, it was found that $k=10$ led to the best results in terms of
the MAE, RMSE and fit time. For the rank and correlation coefficients, $k=60$
reached slightly better results. The result on the CIFAR10 dataset using Nas-
Bench-201 architectures can be found in Table 1, alongside with the results of
high-performing performance predictors from White et al., (2021) for
comparison. All results have been averaged out over 20 trials.

Compared with the performance predictor of NAO, of which EmProx is a
modification, EmProx outperforms NAO on all metrics. This was to be expected
for the fit time since EmProx does not need to train the MLP that NAO uses for
the performance prediction. The fact that it also outperforms NAO in terms of
the regression metrics and correlation coefficients counts as empirical
evidence that the method proposed in this study is viable. Regarding the
regression and correlation coefficients, SemiNAS yields better results.
However, this comes at the cost of the fit time; EmProx is over 20 times
faster than SemiNAS. Compared to the second-fastest method, XGBoost, Emprox is
still around 5 times faster and performs better on both regression metrics as
well as correlation coefficients.

To further validate the performance of EmProx, additional experiments have
been conducted. Table 2 shows the results of performance prediction of NAS-
Bench-201 architectures on the CIFAR100 dataset. This dataset is more
complicated than CIFAR10. On the regression metrics and correlation
coefficients our method again scores slightly worse than the best predictor
from the previous experiments, SemiNAS. However, while on this complicated
dataset the fit time of SemiNAS is becoming infeasibly high, EmProx is still
outstandingly fast.

Another experiment has been conducted on the DARTS search space. Averaged over
twenty trials, EmProx had a RMSE of 0.6652 $\pm$ 0.0694 and a Pearson
correlation of 0.4537 $\pm$ 0.0822 with a fit time of 146.1185 $\pm$ 6.9496.
These results could not be compared to SemiNAS, since SemiNAS exceeded our
resource limitation of 24 hours of CPU time.

These additional experiments indicate generalization of the findings that our
method scores competitively on regression metrics and correlation coefficients
with an immensely lower fit time.

Method | Regression metrics | Correlation coefficients | Time metrics (s)
---|---|---|---
| MAE | RMSE | Pearson | Spearman | Kendall | Fit time | Query time
EmProx ($k=60$) | 5.1859 $\pm$ 0.8155 | 9.914$\pm$ 2.3226 | 0.6212 $\pm$ 0.0792 | 0.7772 $\pm$ 0.0490 | 0.5877 $\pm$ 0.0427 | 16.1493 $\pm$ 0.6764 | 0.0043 $\pm$ 0.0014
SemiNAS | 4.5925 $\pm$ 0.5693 | 9.0315 $\pm$ 1.5319 | 0.6469 $\pm$ 0.1034 | 0.7990 $\pm$ 0.0428 | 0.6124 $\pm$ 0.0418 | 1309.1343 $\pm$ 53.1245 | 0.0108 $\pm$ 0.0049

Table 2: Experiment results on the CIFAR100 dataset with NAS-Bench-201
architectures, averaged over 20 trials. Compared to the best performer in
earlier experiments, SemiNAS, our method again scores slightly worse on
regression metrics and correlation coefficients, but the fit time is a
fraction.

##  6 Conclusion

In this study we proposed EmProx, a cheaper and faster method to perform
performance estimation during neural architecture search. In the empirical
results EmProx was approximately nine times faster than NAO and up to eighty
times faster than alternatives, while yielding similarly good predictions
according to various regression metrics and correlation coefficients. It also
opens up a new area of performance predictors based on proximity in
architecture embeddings.

##  7 Limitations and Broader Impact Statement

Research on NAS serves the larger societal goal of making machine learning
more accessible, and this work specifically speeds up NAS methods, making them
more widely applicable. A potential negative impact is found in the
consequences of this accessibility; it makes it easier to put machine learning
to misuse.

The results in this study could be improved by better shaping the embedding
space, for example by using a variational autoencoder or by adding an extra
component in loss the function that promotes architectures with similar
performance to be mapped closeby in the embedding space.

Despite realistic experiments, the proposed method has not been tested as part
of a full NAO search. This could further prove the viability of EmProx.
Additionally, it has to be noted that EmProx is inherently dependent on the
training data, since it bases its predictions directly on the performance of
training architectures. Hence, further research should show how sensitive the
performance of EmProx is towards the training size. To further show robustness
of the method, experiments with resource limits could be conducted, as has
been done extensively by White et al., (2021). Also, currently embeddings are
learned from 121 architectures. There is an interesting trade-off between
embedding quality and fit time as a result of this choice of number of
architectures that could further be explored. Lastly, it would be interesting
to see how well the performance of this method generalizes to more complex
datasets such as CIFAR-100 or ImageNet and more complex search spaces like
NAS-Bench301.

## References

  * Baker et al., (2016) Baker, B., Gupta, O., Naik, N., and Raskar, R. (2016).  Designing neural network architectures using reinforcement learning.  CoRR, abs/1611.02167.
  * Baker et al., (2017) Baker, B., Gupta, O., Raskar, R., and Naik, N. (2017).  Practical neural network performance prediction for early stopping.  CoRR, abs/1705.10823.
  * Chen and Guestrin, (2016) Chen, T. and Guestrin, C. (2016).  Xgboost: A scalable tree boosting system.  CoRR, abs/1603.02754.
  * Dong and Yang, (2020) Dong, X. and Yang, Y. (2020).  Nas-bench-201: Extending the scope of reproducible neural architecture search.  CoRR, abs/2001.00326.
  * Elsken et al., (2018) Elsken, T., Metzen, J. H., and Hutter, F. (2018).  Neural Architecture Search: A Survey.  Journal of Machine Learning Research, 20.
  * Liu et al., (2018) Liu, H., Simonyan, K., and Yang, Y. (2018).  DARTS: Differentiable Architecture Search.  7th International Conference on Learning Representations, ICLR 2019.
  * Luo et al., (2020) Luo, R., Tan, X., Wang, R., Qin, T., Chen, E., and Liu, T. (2020).  Semi-supervised neural architecture search.  CoRR, abs/2002.10389.
  * Luo et al., (2018) Luo, R., Tian, F., Qin, T., Chen, E., and Liu, T. Y. (2018).  Neural architecture optimization.  In Advances in Neural Information Processing Systems, volume 2018-Decem, pages 7816–7827. Neural information processing systems foundation.
  * Mellor et al., (2020) Mellor, J., Turner, J., Storkey, A. J., and Crowley, E. J. (2020).  Neural architecture search without training.  CoRR, abs/2006.04647.
  * Real et al., (2017) Real, E., Moore, S., Selle, A., Saxena, S., Suematsu, Y. L., Le, Q. V., and Kurakin, A. (2017).  Large-scale evolution of image classifiers.  CoRR, abs/1703.01041.
  * Ru et al., (2020) Ru, B., Lyle, C., Schut, L., Fil, M., van der Wilk, M., and Gal, Y. (2020).  Speedy Performance Estimation for Neural Architecture Search.
  * Ruchte et al., (2020) Ruchte, M., Zela, A., Siems, J., Grabocka, J., and Hutter, F. (2020).  Naslib: A modular and flexible neural architecture search library.  https://github.com/automl/NASLib.
  * Siems et al., (2020) Siems, J., Zimmer, L., Zela, A., Lukasik, J., Keuper, M., and Hutter, F. (2020).  Nas-bench-301 and the case for surrogate benchmarks for neural architecture search.  CoRR, abs/2008.09777.
  * Tu et al., (2021) Tu, R., Khodak, M., Roberts, N., and Talwalkar, A. (2021).  NAS-Bench-360: Benchmarking Diverse Tasks for Neural Architecture Search.
  * Wen et al., (2019) Wen, W., Liu, H., Li, H., Chen, Y., Bender, G., and Kindermans, P. (2019).  Neural predictor for neural architecture search.  CoRR, abs/1912.00848.
  * White et al., (2019) White, C., Neiswanger, W., and Savani, Y. (2019).  BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search.
  * White et al., (2021) White, C., Zela, A., Ru, B., Liu, Y., Hutter, F., and Ai, A. (2021).  How Powerful are Performance Predictors in Neural Architecture Search?
  * Ying et al., (2019) Ying, C., Klein, A., Real, E., Christiansen, E., Murphy, K., and Hutter, F. (2019).  Nas-bench-101: Towards reproducible neural architecture search.  CoRR, abs/1902.09635.

## Appendix

###  7.1 Hyperparameter search

For hyperparameter tuning, a gridsearch was performed on the number of
neighbors $k=[3,10,60]$ and the dimension of the embedding $d=[16,32,64,128]$.
These specific values for $k$ are the result of earlier exploratory analysis.
The results can be found in table 3. By no means this grid search aimed to
find the most optimal configuration of EmProx. It merely served as an
exploration of the performance of the method and its sensitivity towards its
hyperparameters.

| Regression metrics | Correlation coefficients | Time metrics (s)
---|---|---|---
k | d | MAE | RMSE | Pearson | Spearman | Kendall | Fit time | Query time
3 | 16 | 5.0856 | 11.7021 | 0.3918 | 0.6134 | 0.4416 | 8.6227 | 0.0006
3 | 32 | 4.7855 | 11.4074 | 0.4003 | 0.6834 | 0.4968 | 6.4858 | 0.0007
3 | 64 | 4.9680 | 11.5436 | 0.3924 | 0.6656 | 0.4863 | 7.4364 | 0.0008
3 | 128 | 4.9231 | 11.5629 | 0.4136 | 0.6805 | 0.5011 | 26.0462 | 0.0034
10 | 16 | 4.7314 | 11.0031 | 0.4614 | 0.6744 | 0.4966 | 6.1812 | 0.0008
10 | 32 | 4.4027 | 10.7163 | 0.4771 | 0.7304 | 0.5453 | 6.4498 | 0.0009
10 | 64 | 4.6388 | 10.7278 | 0.4667 | 0.6991 | 0.5178 | 7.3694 | 0.0010
10 | 128 | 4.6323 | 10.8578 | 0.4551 | 0.7200 | 0.5331 | 26.0007 | 0.0044
60 | 16 | 4.7076 | 11.0466 | 0.4808 | 0.7095 | 0.5246 | 6.5411 | 0.0032
60 | 32 | 4.5265 | 10.7953 | 0.5044 | 0.7332 | 0.5468 | 7.2310 | 0.0032
60 | 64 | 4.7681 | 10.9440 | 0.4809 | 0.7083 | 0.5247 | 8.4264 | 0.0035
60 | 128 | 4.6267 | 10.8773 | 0.4779 | 0.7209 | 0.5369 | 17.2969 | 0.0053
Table 3: Gridsearch results over parameters $k$, the number of neighbors to
base the performance estimation on, and $d$, the dimension of the hidden
layer/embedding. Results are averaged over 20 trials.


11institutetext: School of Computer Science, University College Dublin,
Dublin, Ireland 11email<EMAIL_ADDRESS>
# Using Multi-Agent MicroServices (MAMS) for Agent Based Modelling

Martynas Jagutis  Sean Russell  Rem W. Collier

###### Abstract

This paper demonstrates the use of the Multi-Agent MicroServices (MAMS)
architectural style through a case study based around the development of a
prototype traffic simulation in which agents model a population of individuals
who travel from home to work and vice versa by car.

###### Keywords:

Multi-Agent Systems Microservices Traffic Simulation

##  1 Introduction

Multi-Agent MicroServices (MAMS) [3] is an architectural style for deploying
Multi-Agent Systems (MAS) within Microservices architecture. This has been
achieved by introducing of a specific kind of agent, known as a MAMS Agent,
that has an associated body that consists of a set of web resources that are
accessible through REpresentational State Transfer (REST). MAMS agents act
like an interface agent for a microservice. Collectively, their bodies form a
REST interface that external microservices can use to interact with the MAS
via the MAMS agents. Within a microservice, MAMS agents are able to interact
with non-MAMS agents through traditional agent communication mechanisms.

MAMS has been applied to a number of problem domains, including: decision
support tools [2], building management [9] and digital twins for smart
agriculture [7]. Additionally, a prototype framework for implementing MAMS
applications [10] has been developed, built on a combination of CArtAgO [11]
and the ASTRA programming language [5]. The source code for the framework and
a number of example applications can be found on
Gitlab111https://gitlab.com/mams-ucd/.

This paper illustrates a potential use of MAMS and microservices in Agent
Based Modelling (ABM) [1]. The basic idea is to decompose the environment part
of an ABM into a set of web resources. For example, a road network can be
decomposed into street and junction resources. Each resource is a kind of
"micro-environment" that agents can inhabit and interact with. They are
created and accessed through specially designed environment microservices.
Inter-resource relationships are modelled based on the URL associated with
each resource. A second set of microservices are used to implement the agent
part of the ABM by leveraging the MAMS architectural style.

##  2 Overview of Prototype

The scenario demonstrated in this paper is a simple traffic simulation
scenario in which agents model a population of individuals who travel from
home to work and vice versa by car. The environment for this scenario is
decomposed into four types of resource: home resources, work resources and the
street and junction resources that model the road network. These resources are
implemented through three sub-environment microservices. The design of the
street and junction resources is based on best practices drawn from
established traffic simulators such as MATSim [12] and SUMO [8].

Figure 1 illustrates the set of microservices, implemented using Java and
Spring Boot222https://spring.io, that underpin the prototype. This includes
three sub-environment microservices described above. The Road Network service
is the most complex of the three and is underpinned by the Neo4J
database333https://neo4j.com/ which maintains a graph of the constituent
streets and junctions. The Home and Work services provide a minimal model that
includes access to the current time and a single activity (e.g. Watch TV or
Work). A Clock Service provides a discrete time model for the simulation; a
Traffic Lights Service implements an algorithm to control traffic lights in
the Road Network and a Management Service supports the configuration and
execution of a simulation run. Finally, the Driver Service implements the
agent part of the system which is described next.

Figure 1: Overview of Simulation Architecture

To connect to the simulation, MAMS Agents must register with an environment
microservice based on the resource they wish to interact with. The
microservice can reject the request, but if accepted, it creates an agent body
resource444This is not the same as the MAMS body described above. The
environment state is passed to the agent using a HTTP PUT Request to a webhook
associated with the MAMS agents body. Agents submit actions using a HTTP PUT
Request to the agents body on the environment microservice. The environment
microservice tracks which resource an agent is associated with. When an agent
moves to another resource (e.g. moving from a junction to a street), the
microservice registers the change. If the agent moves to a resource that is
located on a different microservice, its body is transferred to the new
microservice via a HTTP POST Request. Further details can be found in [6] and
the source code is available on Gitlab555https://gitlab.com/mams-
ucd/examples/microservice_traffic_simulator.

##  3 Using MAMS to implement agent behaviours

This section focuses on the implementation of the Driver Service using the
MAMS prototype that has been developed for the ASTRA agent programming
language. A simplified version of the driver agent implementation used in the
demo is shown in Figure 2. The overall behaviour begins with the handling of
the `!updatedObject(...)` goal in the second rule. The argument of this goal
is a Java object that represents the environment state. The plan part of the
plan rule defines two sub-goals `!decide(...)` and `!act(...)` which must be
achieved in sequence. The last two rules in the program highlight two possible
sub-plans for achieving the `!decide(...)` goal. The agent will choose only
one of these options based on the current state of the environment. For
example, the last rule requires that the vehicle controlled by the agent be
stopped. This is expressed by the `isStopped(...)` belief. This belief is
evaluated based on the second of the inference rules at the top of the code
snippet, which are denoted by the `inference` keyword. The `ObjectAccess`
module provides a generic mechanism for the agent to query the internal state
of Java objects. In this case it retrieves the value of the `vehicleSpeed`
field of the `EnvironmentState` object. The selection conditions are expressed
by the context part which appears after the colon (:) and before the opening
brace ({) of the plan. The `!act(..)` goal sends the chosen action to the
server using the low level `!put(...)` goal provided by the MAMS
implementation.

⬇

agent Driver extends mams.PassiveMAMSAgent {

module ObjectAccess oa;

inference atIntersection(EnvironmentState state) :-

oa.isFalse(state, "atIntersection") &

oa.getInt(state, "vehicleSpeed") > 0;

inference isStopped(EnvironmentState state) :-

oa.getInt(state, "vehicleSpeed") > 0;

rule +!main(list args) {

MAMSAgent::!init();

MAMSAgent::!created("base");

PassiveMAMSAgent::

!itemResource("notifications", "EnvironmentState");

}

rule +!updatedObject(EnvironmentState state) {

!decide(state, oa.getString(state, "type"), string action);

!act(state, action);

}

rule +!act(EnvironmentState state, string action) {

!put(oa.valueAsString(state, "webhook"),

"{␣'action':'"+action"'}", HttpResponse response);

if (!httpUtils.hasCode(response, 200)) system.fail();

}

rule +!decide(EnvironmentState state, "traffic", string action)

: time(t) & atIntersection(state) {

action = "move";

}

rule +!decide(EnvironmentState state, "traffic", string action)

: time(t) & isStopped(state) & canAccelerate(state) {

action = "accelerate";

}

}

Figure 2: ASTRA-MAMS Implementation

MAMS is visible in two parts of the example code. The latter place is in the
rule associated with the `!act(...)` goal where the `!put(...)` goal is
adopted to submit the action to the server. The representation actually sent
to the simulation has been simplified for readability. The former place where
MAMS is visible is in the rule that handles the `!main(...)` goal. The goals
specified in this rule connect the agent to the MAMS infrastructure and create
a resource that is exposed on the web under the `/{agent-name}/notification`
URL. The simulation service sends the environment state to the agent in the
same way; by updating this resource using a PUT request. Upon the processing
of a new PUT request, the underlying MAMS infrastructure generates the
`updatedObject(...)` goal to trigger a response from the agent.

##  4 Conclusions

This paper presents an early prototype of an novel approach to Agent Based
Modelling (ABM) using a combination of microservices and the Multi-Agent
MicroServices (MAMS) architectural style. The prototype presented is a traffic
simulation scenario that decomposes the environment into four types of web
resource that are hosted across three microservices. Each resource acts as a
"micro-environment". Agents interact with a resource by registering a "body"
with the corresponding microservice, indicating which resource they wish to be
associated with. Hypermedia links are used to relate resources to one another,
for example, a junction resource in the road network can be linked to a home
or work resource. A key part of the approach is the design of mechanisms to
allow agents to transition between web resources which can be achieved either
internally or via a HTTP POST request.

A number of shortcomings and opportunities were identified during its
evaluation [6]. The most interesting opportunity is the potential use of the
linked data structure to create decentralised knowledge graphs that capture
global knowledge of the simulation environment. Such knowledge could be
consumed by individual agents and used in concert with local contextual
knowledge of their environment to offer improved decision making capabilities.
Details of this proposed approach can be found in [4].

## References

  * [1] Abar, S., Theodoropoulos, G.K., Lemarinier, P., O’Hare, G.M.: Agent based modelling and simulation tools: A review of the state-of-art software. Computer Science Review 24, 13–33 (2017)
  * [2] Carneiro, J., Andrade, R., Alves, P., Conceição, L., Novais, P., Marreiros, G.: A consensus-based group decision support system using a multi-agent microservices approach. In: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. pp. 2098–2100 (2020)
  * [3] Collier, R., O’Neill, E., Lillis, D., O’Hare, G.: Mams: Multi-agent microservices. In: Companion Proceedings of The 2019 World Wide Web Conference. pp. 655–662. ACM (2019)
  * [4] Collier, R., Russell, S., Ghanadbashi, S., Golpayegani, F.: Towards the use of hypermedia mas and microservices for web scale agent-based simulation. SN Computer Science 3(6), 510 (2022)
  * [5] Collier, R.W., Russell, S., Lillis, D.: Reflecting on agent programming with agentspeak (l). In: International Conference on Principles and Practice of Multi-Agent Systems. pp. 351–366. Springer (2015)
  * [6] Jagutis, M., Russell, S., Collier, R.: Simulating traffic with agents, microservices & rest. In: 15th International Symposium on Intelligent Distributed Computing (IDC2023) (2022)
  * [7] Kalyani, Y., Collier, R.: Towards a new architecture: Multi-agent based cloud-fog-edge computing and digital twin for smart agriculture. In: Intelligent Distributed Computing XV, pp. 111–117. Springer (2023)
  * [8] Lopez, P.A., Behrisch, M., Bieker-Walz, L., Erdmann, J., Flötteröd, Y.P., Hilbrich, R., Lücken, L., Rummel, J., Wagner, P., Wießner, E.: Microscopic traffic simulation using sumo. In: 2018 21st international conference on intelligent transportation systems (ITSC). pp. 2575–2582. IEEE (2018)
  * [9] O’Neill, E., Beaumont, K., Bermeo, N.V., Collier, R.: Building management using the semantic web and hypermedia agents (2021)
  * [10] O’Neill, E., Lillis, D., O’Hare, G., W Collier, R.: Delivering multi-agent microservices using cartago. In: International Workshop on Engineering Multi-Agent Systems. pp. 1–20. Springer (2020)
  * [11] Ricci, A., Viroli, M., Omicini, A.: Cartago: A framework for prototyping artifact-based environments in mas. In: International Workshop on Environments for Multi-Agent Systems. pp. 67–86. Springer (2006)
  * [12] W Axhausen, K., Horni, A., Nagel, K.: The multi-agent transport simulation MATSim. Ubiquity Press (2016)