difficult to solve the linear equation. The linear equation is difficult to
solve if we can make one or more pairs of column or row of $C$ close to
parallel by elementary operations. However, by construction of incidence
matrix, no pairs of column or row of the incidence matrix are close to
parallel. Thus, we expect that the condition number of $C$ will not be large,
and hence we expect a smaller value of $\alpha_{G,p}$ than Prop. 3.5 in
general. For the specific graphs, we theoretically show this in the next
section.

###  J.2 Bound of $\alpha_{G,p}$ for Some Specific Graphs

In this section we give a constant bound of $\alpha_{G,p}$ for some specific
graphs. By this we can independently bound $\alpha_{G,p}$ of $m$.

Now, for the specific cases, we have the following.

######  Proposition J.1.

If a graph is complete or cyclic, then $\vvvert CC^{+}\vvvert_{p}\leq 4$ and
hence $\alpha_{G,p}\leq 4w_{\max}^{1/p}/w_{\min}^{1/p}$.

For these specific graphs, we can bound the $p$-resistance (Thm. 3.3) by a
constant. We now divide the proof into the complete case and the cyclic case.

####  J.2.1 Complete Case

First, we obtain the pseudoinverse of $C$ of a complete graph.

######  Lemma J.2.

For an incidence matrix $C^{\prime}$ for a complete graph,

$\displaystyle C^{{}^{\prime}+}=\frac{1}{n}C^{{}^{\prime}\top}$ (217)

###### Proof.

For a graph Laplacian $L$ of unweighted graph can be written as

$\displaystyle L$ $\displaystyle=nI-\mathbf{1}^{\top}\mathbf{1},$ (218)

and thus

$\displaystyle L_{ij}=\left\\{\begin{array}[]{ll}n-1&\mathrm{if}\ i=j\\\
-1&\mathrm{if}\ i\neq j\end{array}\right..$ (221)

Also, we know that

$\displaystyle L=C^{{}^{\prime}\top}C^{\prime}.$ (222)

Now we consider the the vector $\mathbf{x}_{ij}\in\mathbb{R}^{n}$ as

$\displaystyle\mathbf{x}_{ij}^{\top}:=\underbrace{(0,\ldots,0,\overbrace{1}^{i\mathrm{th\
element}},0,\ldots,0,\overbrace{-1}^{j\mathrm{th\
element}},0,\ldots,0)}_{\mathrm{size}\ n}.$ (223)

Note that this $\mathbf{x}_{ij}$ is one row of the incidence matrix
$C^{\prime}$. Now we get

$\displaystyle(L\mathbf{x}_{ij})_{l}$
$\displaystyle=\left\\{\begin{array}[]{ll}(n-1)\times
1+(-1)\times(-1)=n&\mathrm{if}\ l=i\\\
1\times(-1)+(n-1)\times(-1)=-n&\mathrm{if}\ l=j\\\ (-1)\times
1+(-1)\times(-1)=0&\mathrm{otherwise}\end{array}\right.$ (227)
$\displaystyle=n(L\mathbf{x}_{ij})_{l}.$ (228)

Since $\mathbf{x}_{ij}$ is one column of the transpose of the incidence matrix
$\mathbf{C}^{{}^{\prime}\top}$,

$\displaystyle
LC=C^{{}^{\prime}\top}C^{\prime}C^{{}^{\prime}\top}=nC^{{}^{\prime}\top}\iff\left(\frac{1}{n}C^{{}^{\prime}\top}\right)C^{\prime}\left(\frac{1}{n}C^{{}^{\prime}\top}\right)=\frac{1}{n}C^{{}^{\prime}\top}$
(229)

Also,

$\displaystyle(LC)^{\top}=C^{{}^{\prime}}C^{{}^{\prime}\top}C^{{}^{\prime}}=nC^{{}^{\prime}}\iff
C^{{}^{\prime}}\left(\frac{1}{n}C^{{}^{\prime}\top}\right)C^{{}^{\prime}}=C^{{}^{\prime}}$
(230)

From Eq. (229) and Eq. (230), the matrix $1/nC^{\prime}$ satisfies the
definition of $C^{+}$, which leads to the claim. ∎

Note that $\vvvert CC^{+}\vvvert_{1}=\vvvert CC^{+}\vvvert_{\infty}$ due to
the symmetricity of $CC^{+}$.

$\displaystyle\vvvert CC^{+}\vvvert_{p}\leq\vvvert
CC^{+}\vvvert_{\infty}\leq\vvvert C\vvvert_{\infty}\vvvert
C^{+}\vvvert_{\infty}=4\frac{n+1}{n}\leq 4.$ (231)

####  J.2.2 Cyclic Case

In the cyclic graph, $m=n$, i.e., the number of vertices is equal to the
number of edges. Thus, the incidence matrix $C$ is square. However, in order
to avoid confusion, in the following we use $m$ and $n$. Now, we define the
incidence matrix $C\in\mathbb{R}^{m\times n}$of the cyclic graph as

$\displaystyle c_{i1}$
$\displaystyle=\left\\{\begin{array}[]{cc}-1&\mathrm{when}\ i=1\\\
1&\mathrm{when}\ i=2\\\ 0&\mathrm{otherwise}\end{array}\right.$ (235)
$\displaystyle c_{i2}$
$\displaystyle=\left\\{\begin{array}[]{cc}-1&\mathrm{when}\ i=1\\\
1&\mathrm{when}\ i=n\\\ 0&\mathrm{otherwise}\end{array}\right.$ (239)
$\displaystyle c_{ij}$
$\displaystyle=\left\\{\begin{array}[]{cc}-1&\mathrm{when}\ i=j-1\\\
1&\mathrm{when}\ i=j\\\ 0&\mathrm{otherwise\ for\
}\end{array}\right.\mathrm{for\ }j\geq 3.$ (243)

Before we explore $C^{+}$, we introduce cyclic shift operator of the vector.
Given the vector $\mathbf{a}$, the shift operator $(l)$ “cyclic shifts” the
element, as

$\displaystyle\mathbf{a}^{(l)}=(a_{n-l+1},a_{n-l+2},\ldots,a_{n},a_{1},\ldots,a_{n-l})^{\top}.$
(244)

Thus, $\mathbf{a}^{(0)}=\mathbf{a}$. Also, we define the reverse operator
$\mathrm{rev}$ for a vector $\mathbf{a}$ as

$\displaystyle\mathrm{rev}(\mathbf{a})=(a_{n},a_{n-1},\ldots,a_{1}).$ (245)

We also define the vector $\bm{\xi}\in\mathbb{R}^{n}$ as

$\displaystyle\bm{\xi}=(1/2-1/2n,1/2-3/2n,\ldots,1/2-(2i-1)/2n,\ldots,-1/2+1/n).$
(246)

Now, we define a matrix $B$ as

$\displaystyle B_{1\cdot}$ $\displaystyle=\bm{\xi}^{(1)}$ (247) $\displaystyle
B_{2\cdot}$
$\displaystyle=\mathrm{rev}(\bm{\xi}^{(0)})=\mathrm{rev}(\bm{\xi})$ (248)
$\displaystyle B_{j\cdot}$ $\displaystyle=\bm{\xi}^{(j-1)}\mathrm{for\ }j\geq
3,$ (249)

where $B_{i\cdot}$ denotes $i$-th column of $B$. We plot a heatmap of $C$ and
$B$ for the illustrative purpose.

(a) $C$

(b) $B=C^{+}$

(c) $CC^{+}$

Figure 7:  Heatmap plot for the matrices $C$, $B=C^{+}$ and $CC^{+}$ of the
cyclic graph for $n=20$.

Now we prove that $C^{+}=B$. To claim that, it is enough to prove that
$BC=I-\mathbf{1}^{\top}\mathbf{1}/n$ (Bapat, 2010). From the construction,

$\displaystyle(BC)_{ii}=\xi_{1}-\xi_{n}=1/2-1/2n-(-1/2-1/2n)=1-1/n.$ (250)

Also, when $i\neq j$,

$\displaystyle(BC)_{ij}$
$\displaystyle=\left\\{\begin{array}[]{ll}-\xi_{i-1}-\xi_{n-i+1}&\mathrm{when}\
\mathrm{when}\ j=1\\\ \xi^{(j)}_{i+1}-\xi^{(j)}_{i}&\mathrm{when}\
\mathrm{when}\ 2\leq j<n,\\\ \xi_{n-i+1}+\xi_{i+1}&\mathrm{when}\
\mathrm{when}\ j=n,\\\ \end{array}\right.$ (254) $\displaystyle=-1/n.$ (255)

Thus, we can say that $B=C^{+}$. By doing a similar computation, we get

$\displaystyle CC^{+}=\left\\{\begin{array}[]{cc}1-1/n&\mathrm{when}\ i=j\\\
1/n&\mathrm{when}\ i=2\mathrm{\ or\ }j=2,i\neq j\\\
-1/n&\mathrm{otherwise}\end{array}\right.$ (259)

We also plot a heatmap for $CC^{+}$ for the illustrative purpose in Fig. 7(c).
Thus, applying Lemma B.2, we get

$\displaystyle\vvvert CC^{+}\vvvert_{p}\leq\vvvert
CC^{+}\vvvert_{1}=\max_{i}\sum_{j=1}^{n}|(CC^{+})_{ij}|=2-1/n\leq 4.$ (260)

We leave a brief note for other concrete examples. Several attempts are made
to obtain the concrete form of $C^{+}$ for the specific graph (Azimi & Bapat,
2018; Azimi et al., 2019). However, due to their abstract ways to characterize
the graph such as distance or cut, we think that it is hard to immediately
obtain a non-trivial bound from these results. Also, $C^{+}$ for tree is
studied (Bapat, 1997). However, since we know the exact representation of
$p$-resistance for tree in Thm. 3.4, we do not have to discuss the tree case.

###  J.3 Additional Experiments for Bound of Approximation

This section discusses some additional experiments for bound of approximation
in Prop. 3.5. For the real datasets we confirmed that the approximation over
exact
$\|L^{+}\mathbf{e}_{i}-L^{+}\mathbf{e}_{j}\|_{G,q}^{q}/r_{G,p}^{1/(p-1)}(i,j)$
is far below the bound and its worst case, in Fig. 6. In this section, we
further investigate the $\alpha_{G,p}$ of the real datasets. Moreover, we
further investigate artificial dataset that the ratio is close to the worst
dataset, and we discuss why it happens.

####  J.3.1 Plot of $\vvvert CC^{+}\vvvert_{p}$.

As we discussed in Sec. I.3, since $\alpha_{G,p}=\vvvert
W^{1/p}CC^{+}W^{-1/p}\vvvert_{p}$ involves $p$ in the matrix as well as norm,
it is somewhat difficult to how $\alpha_{G,p}$ behaves by changing $p$. Thus,
we focus on the unweighted graph; we numerically investigate the unweighted
$\|CC^{+}\|_{p}$ that is a matrix norm evaluated in Eq. (212). We plot
$\|CC^{+}\|_{p}$ for wine, ion, and iris with the $\mu$ when $k$-medoids
performs the best in Fig. 8. We use the matrix $p$-norm estimation algorithm
proposed by (Higham, 1992). We plot $p\to 1$ and $p\to\infty$ as the exact
value. We remark on the estimation of the matrix norm by (Higham, 1992); let
$\xi$ be the output by the estimation of the matrix norm of $CC^{+}$, then
$\vvvert CC^{+}\vvvert_{p}/m^{|1/2-p|}\leq\xi\leq\vvvert CC^{+}\vvvert_{p}$.
We note that using Lemma B.2 and symmetricity of $CC^{+}$, we have

$\displaystyle\vvvert CC^{+}\vvvert_{p}\leq\vvvert CC^{+}\vvvert_{1}=\vvvert
CC^{+}\vvvert_{\infty},$ (261)

whose exact value is computable. Thus, although we need to use estimation
algorithm for $\vvvert CC^{+}\vvvert_{p}$, we can exactly compute the bound of
this norm.

Fig. 8 shows that $\|CC^{+}\|_{p}$ is far lower than the worst bound in Prop.
3.5. Moreover, Fig. 8 shows that the estimation algorithm proposed by Higham
(1992) outputs is reliable results on this problem since this follows theory
in terms of $\vvvert CC^{+}\vvvert_{p^{\prime}}\leq\vvvert CC^{+}\vvvert_{p}$
if $2<p^{\prime}<p$ or $p<p^{\prime}<2$, also Eq. (261). Also, even only
looking at $\vvvert CC^{+}\vvvert_{1}=\vvvert CC^{+}\vvvert_{\infty}$, which
is exactly computable the bound of $\vvvert CC^{+}\vvvert_{p}$, we have far
lower value than the worst bound, especially in larger $p$ where our
clustering algorithm works better.

Figure 8: Matrix norm $\|CC^{+}\|$ vs $p$.

Figure 9: The example where the approximated value is far lower than the exact
value. See J.3 for details.

Table 5:  The values of approximated $1$-Resistance for (a). The exact 1-resistance for this graph is $1/\delta$.  |  | $\zeta$
---|---|---
|  | 5 | 10 | 20 | 40 | 80
$\delta$ | 5 | 0.2 | 0.1 | 0.05 | 0.025 | 0.0125
10 | 0.2 | 0.1 | 0.05 | 0.025 | 0.0125
20 | 0.2 | 0.1 | 0.05 | 0.025 | 0.0125
40 | 0.2 | 0.1 | 0.05 | 0.025 | 0.0125
80 | 0.2 | 0.1 | 0.05 | 0.025 | 0.0125

Table 6:  The values of approximated $p$-Resistance for (b). The exact 1-resistance for this graph is $1/(\delta+1)$.  |  | $\zeta$
---|---|---
|  | 5 | 10 | 20 | 40 | 80
$\delta$ | 5 | 0.46 | 0.33 | 0.21 | 0.13 | 0.07
10 | 0.61 | 0.48 | 0.33 | 0.21 | 0.12
20 | 0.75 | 0.64 | 0.49 | 0.33 | 0.20
40 | 0.85 | 0.77 | 0.65 | 0.49 | 0.33
80 | 0.92 | 0.87 | 0.79 | 0.66 | 0.50

Table 7:  The values of $\vvvert CC^{+}\vvvert_{1}/m^{1/2}$ for the graph (a). If this value is close to 1, we have a looser bound.  |  | $\zeta$
---|---|---
|  | 5 | 10 | 20 | 40 | 80
$\delta$ | 5 | 0.51 | 0.33 | 0.23 | 0.16 | 0.11
10 | 0.41 | 0.27 | 0.19 | 0.13 | 0.09
20 | 0.31 | 0.2 | 0.14 | 0.1 | 0.07
40 | 0.23 | 0.15 | 0.1 | 0.07 | 0.05
80 | 0.16 | 0.11 | 0.07 | 0.05 | 0.04

Table 8:  The values of $\vvvert CC^{+}\vvvert_{1}/m^{1/2}$ for the graph (b). If this value is close to 1, we have a looser bound.  |  | $\zeta$
---|---|---
|  | 5 | 10 | 20 | 40 | 80
$\delta$ | 5 | 0.70 | 0.55 | 0.43 | 0.33 | 0.24
10 | 0.68 | 0.59 | 0.51 | 0.41 | 0.32
20 | 0.59 | 0.56 | 0.54 | 0.49 | 0.41
40 | 0.47 | 0.48 | 0.51 | 0.52 | 0.48
80 | 0.36 | 0.38 | 0.44 | 0.49 | 0.51

####  J.3.2 Example where Approximation is Far Lower than the Exact Value

Lastly, we discuss an example where the approximation is far lower than the
exact value and how this happens. We consider a graph depicted in Fig. 9.
First, we see a graph in Fig. 9 (a). To build this graph, first consider the
line graph, where the $\zeta$ vertices are in line. This graph is constructed
with $\delta$ lines of diameter $\zeta$ each lines start vertex is glued to
each other lines “start vertex” and similar to the “end vertices”. For Fig. 9
(b), we add one edge to the graph in Fig. 9 between the start vertex and end
vertex.

We now compare with approximation and the exact value of $1$-resistance
between the start vertex and end vertex. As we discussed in Sec. G, we compute
the exact $1$-resistance between $i$ and $j$ as the minimum cut’s inverse.
Thus, for (a) $r_{G,1}(\textrm{start},\textrm{end})=1/\delta$ and for (b) we
have $r_{G,1}(\textrm{start},\textrm{end})=1/(\delta+1)$. We then compute the
approximated values and $\vvvert CC^{+}\vvvert_{1}$ for Fig. 9. We give a
result in Tables 6–8. From Tables 6 and 6, we observe that we have a far less
accurate approximation for graph (b) than that for graph (a). In Tables 8 and
8, we observe that a far larger value of $\vvvert CC^{+}\vvvert_{1}$ for the
graph (b) than that for the graph (a). We also observe that comparing with
$\vvvert CC^{+}\vvvert_{1}$ of the graph constructed from the real dataset in
Fig. 8, we see a far larger value of $\vvvert CC^{+}\vvvert_{1}$ for the graph
(b). The larger value of $\vvvert CC^{+}\vvvert_{1}$ might be the reason why
the approximation of the $1$-resistance of graph (b) is far worse than the
graph (a).

We now discuss why $\vvvert CC^{+}\vvvert_{1}$ for graph (b) is far larger
than that for graph (a). We now revisit the condition number argument in Sec.
J.1. The condition number is the stableness of the linear equation of the
matrix. The stable linear equation is even if we add small value
$\mathbf{\epsilon}$ to the linear equation, i.e.,
$C\mathbf{x}=\mathbf{y}+\mathbf{\epsilon}$, the solution $\mathbf{x}$ is
almost unchanged. If we add perturbation on each edge in graph (a), the graph
can absorb the perturbation since each line graph is almost independent.
However, on the graph (b), each line graph becomes dependent due to the
additional edge. Moreover, the start and the end vertex are like “pivots” of
the graph. The perturbations might be widely spread over the graph by
connecting two pivots. By this spread, graph (b) becomes unstable, while graph
(a), where we do not connect the pivots is more stable. In Tables 10 and 10 we
see that graph (b) is far more unstable than graph (a).

Finally, we argue that we do not observe this phenomenon in the real setting.
In the example of graph (b), the unstableness comes from the sparse connection
over the graph and connection of the “pivots” over such a spares graph. In a
dense graph such as a complete graph, we saw far lower $\vvvert
CC^{+}\vvvert_{1}$ as we observe in Sec J.2. As we saw in the real dataset
case, we can assume that there is a denser connection over the graph, even
between the clusters.

Table 9:  The values of condition number $\vvvert C\vvvert_{1}\vvvert C^{+}\vvvert_{1}$ for (a).  |  | $\zeta$
---|---|---
|  | 5 | 10 | 20 | 40 | 80
$\delta$ | 5 | 20.4 | 45.2 | 95.1 | 195.1 | 395
10 | 40.4 | 90.2 | 190.1 | 390.1 | 790
20 | 80.4 | 180.2 | 380.1 | 780.1 | 1580
40 | 160.4 | 360.2 | 760.1 | 1560.1 | 3160
80 | 320.4 | 720.2 | 1520.1 | 3120.1 | 6320

Table 10:  The values of condition number $\vvvert C\vvvert_{1}\vvvert C^{+}\vvvert_{1}$ for (b).  |  | $\zeta$
---|---|---
|  | 5 | 10 | 20 | 40 | 80
$\delta$ | 5 | 24.4 | 49.7 | 101.8 | 219.3 | 457.7
10 | 51 | 136.7 | 346.2 | 812.8 | 1790
20 | 120.2 | 362.3 | 1035.1 | 2702.6 | 6432.7
40 | 266.2 | 871.6 | 2768.2 | 8119.5 | 21449
80 | 563.8 | 1943.9 | 6670.3 | 21713 | 64438

##  Appendix K On Difficulties of The Exact Solution

In this section, we briefly explain the difficulties to obtain the exact
solution of the resistance. Again, we consider the minimization problem Eq.
(21). The Lagrangian multiplier method gives Eq. (194) and Eq. (194). From Eq.
(194), the optimal solution $\mathbf{x}$ satisfies

$\displaystyle 0$
$\displaystyle=p\Delta_{p}\mathbf{x}-\lambda(\mathbf{e}_{i}-\mathbf{e}_{j})$
(262)

To solve this problem, we want to consider $\Delta_{p}^{+}$, which is
“generalized inverse” function $\Delta_{p}$, defined as

$\displaystyle\Delta_{p}^{+}(\Delta_{p}(\Delta_{p}^{+}(\mathbf{x})))=\Delta_{p}^{+}\mathbf{x}$
(263)

Recall that we can write as

$\displaystyle\Delta_{p}=C^{\top}Wf_{p-1}(C\mathbf{x}).$ (264)

For the convenience of notation, we write

$\displaystyle f_{\mathbf{w},p}=Wf_{p}(C\mathbf{x}).$ (265)

If there exists $\bm{\alpha}\in\operatorname*{Ker}(C)$ s.t.

$\displaystyle
f^{-1}_{\mathbf{w},p-1}(C^{+\top}\mathbf{x}-\bm{\alpha})\in\operatorname*{Im}(C),$
(266)

the $\Delta_{p}^{+}$ is given as

$\displaystyle\Delta_{p}^{+}(\mathbf{x}):=C^{+}f_{\mathbf{w},p-1}^{-1}(C^{+\top}\mathbf{x}-\bm{\alpha}),$
(267)

The reason is as follows. We get

$\displaystyle\Delta_{p}(\Delta_{p}^{+}(\mathbf{x}))$
$\displaystyle=C^{\top}f_{\mathbf{w},p-1}(CC^{+}f_{\mathbf{w},p-1}^{-1}(C^{+\top}\mathbf{x}-\bm{\alpha}))$
(268)
$\displaystyle=C^{\top}f_{\mathbf{w},p-1}(f_{\mathbf{w},p-1}^{-1}(C^{+\top}\mathbf{x}-\bm{\alpha}))$
(269) $\displaystyle=C^{\top}(C^{+\top}\mathbf{x}-\bm{\alpha}))$ (270)
$\displaystyle=C^{\top}C^{+\top}\mathbf{x}.$ (271)

The second line follows from the assumption that
$f_{\mathbf{w},p-1}^{-1}(C^{+\top}\mathbf{x}-\bm{\alpha})\in\operatorname*{Im}(C)$.
Thus,

$\displaystyle\Delta_{p}^{+}(\Delta_{p}(\Delta_{p}^{+}(\mathbf{x})))$
$\displaystyle=C^{+}f_{\mathbf{w},p-1}^{-1}(C^{+\top}C^{\top}C^{+\top}\mathbf{x}-\bm{\alpha})$
(272)
$\displaystyle=C^{+}f_{\mathbf{w},p-1}^{-1}(C^{+\top}\mathbf{x}-\bm{\alpha})$
(273) $\displaystyle=\Delta_{p}^{+}\mathbf{x}.$ (274)

From this property, if we substitute

$\displaystyle\mathbf{x}=\Delta^{+}_{p}\left(\frac{\lambda}{p}(\mathbf{e}_{i}-\mathbf{e}_{j})\right)$
(275)

the Eq. (262) satisfied. Therefore, the next question is what $\bm{\alpha}$
is. However, we do not know even if such $\bm{\alpha}$ satisfying Eq. (266)
exists or not.


$\displaystyle=S_{0}\frac{\mathbbm{1}^{A_{\\{1,\ldots,n\\}}^{IO}}}{d_{A_{\\{1,\ldots,n\\}}^{O}}}+\sum_{m=1}^{n}{}_{[1-A_{m}^{O}]}S_{m}\otimes\frac{\mathbbm{1}^{A_{\\{m+1,\ldots,n\\}}^{IO}}}{d_{A_{\\{m+1,\ldots,n\\}}^{O}}}$
$\displaystyle=S_{n}+\\!\sum_{m=1}^{n}\\!\Big{(}S_{m-1}\otimes\mathbbm{1}^{A_{m}^{I}}$
$\displaystyle\hskip
65.44133pt-\Tr_{A_{m}^{O}}S_{m}\\!\Big{)}\\!\otimes\frac{\\!\mathbbm{1}^{A_{m}^{O}A_{\\{m+1,\ldots,n\\}}^{IO}}\\!}{d_{A_{\\{m,\ldots,n\\}}^{O}}},$
(130)

is also an optimal solution (such that $S_{0}^{\prime}=S_{0}$), which
satisfies
$S_{n-1}^{\prime}\otimes\mathbbm{1}^{A_{n}^{I}}=\Tr_{A_{n}^{O}}S_{n}^{\prime}$
for $n=1,\ldots,N-1$ (as is easily checked using the first form for
$S_{n}^{\prime}$ given above), and
$S_{N-1}^{\prime}\otimes\mathbbm{1}^{A_{N}^{I}}\geq
S_{N-1}\otimes\mathbbm{1}^{A_{N}^{I}}\geq\Tr_{A_{N}^{O}}\Omega_{\theta}(h)$
(as is easily checked using the second expression for $S_{N-1}^{\prime}$,
using the constraints of Eq. (129) that the $S_{n}$’s satisfy).

To obtain the optimal QFI for the QC-FO class, it remains to insert the above
dual problem into Eq. (100). Using the Schur complement trick introduced
above, one can replace the quadratic (in $h$) constraint
$S_{N-1}\otimes\mathbbm{1}^{A_{N}^{I}}\geq\Tr_{A_{N}^{O}}\Omega_{\theta}(h)$
by the linear constraint

$\displaystyle{\mathbf{A}}_{\text{Schur},N}(S_{N-1},h)\geq 0,$ (131)

with ${\mathbf{A}}_{\text{Schur},N}$ as defined in Eq. (113). This thus turns
the calculation of the QFI into an SDP problem:

$\displaystyle J_{\theta}^{\textup{{QC-FO}}}(C_{\theta}^{\otimes N})$
$\displaystyle\begin{array}[]{rl}=\min_{h,{\cal S}}&S_{0}\\\\[5.69054pt]
\text{s.t.}&\left\\{\begin{array}[]{l}\forall\,n=1,\ldots,N-1,\\\ \quad
S_{n-1}\otimes\mathbbm{1}^{A_{n}^{I}}=\Tr_{A_{n}^{O}}S_{n},\\\\[5.69054pt]
{\mathbf{A}}_{\text{Schur},N}(S_{N-1},h)\geq 0.\end{array}\right.\end{array}$
(137)

As explained in Sec. B.1.8, the optimal process
$\tilde{W}^{\text{(opt)}}\in\Tr_{F}\textup{{QC-FO}}$ is recovered by solving
the primal problem of Eq. (118) after fixing the optimal value of
$h=h^{\text{(opt)}}$ obtained from Eq. (137) and adding the constraint that
${\mathbf{C}_{\theta}^{0}}{}^{\dagger}\tilde{W}^{T}\big{(}\dot{\mathbf{C}}_{\theta}^{0}-i\mathbf{C}_{\theta}^{0}h^{\text{(opt)}}\big{)}\in\mathbb{H}_{q}$,
as in Eq. (107)—and with $\tilde{W}=W_{(N)}\otimes\mathbbm{1}^{A_{N}^{O}}$
(cf. Eq. (30)).

The optimal process with fixed order $W^{\text{(opt)}}={|w\rangle\\!\langle
w|}\in\textup{{QC-FO}}$ is then obtained by purifying
$\tilde{W}^{\text{(opt)}}$.

####  B.2.2 SDP problems for the QC-CC and QC-QC classes

The derivation of the SDP problems for the QC-CC and QC-QC classes follows
very similar lines to those for the QC-FO class, given in the previous
subsection. We will not repeat everything; instead, we just present in the
following table how Eqs. (118) to (137) are to be modified for the two new
classes we considered in this paper.242424For clarification: in the QC-CC
case, $(k_{1},\ldots,k_{n})$ for $n=0$ is understood as the empty set,
$\emptyset$ (as e.g. in Eq. (LABEL:eq:S_QCCC): ${\cal S}=$
$\bigoplus_{n=0}^{N-1}\\!\bigoplus_{(k_{1},\ldots,k_{n})}\\!S_{(k_{1},\ldots,k_{n})}\\!=\\!S_{\emptyset}\\!\oplus\\!\bigoplus_{n=1}^{N-1}\\!\bigoplus_{(k_{1},\ldots,k_{n})}\\!S_{(k_{1},\ldots,k_{n})}$
). In the QC-QC case, $\mathcal{K}_{n}\setminus k_{n}$ is to be understood as
$\mathcal{K}_{n}\setminus\\{k_{n}\\}$.

QC-CC | QC-QC
---|---
Primal problem: (using Eq. (61)) $\displaystyle\max_{\tilde{W}\in\Tr_{F}\textup{{QC-CC}}}\ \Tr\left(\Omega_{\theta}(h)\,\tilde{W}\right)$ $\displaystyle=\max\ \Tr\left(\sum_{(k_{1},\ldots,k_{N})}\Big{(}\Tr_{A_{k_{N}}^{O}}\Omega_{\theta}(h)\Big{)}W_{(k_{1},\ldots,k_{N})}\right)$ $\displaystyle\quad\text{s.t.}\left\\{\\!\begin{array}[]{l}\sum_{k_{1}}\Tr W_{(k_{1})}=1,\\\\[5.69054pt] \forall\,n=1,\ldots,N-1,\ \forall\,(k_{1},\ldots,k_{n}),\\\\[2.84526pt] \qquad\sum_{k_{n+1}}\Tr_{\\!A_{k_{n+1}}^{I}}W_{(k_{1},\ldots,k_{n},k_{n+1})}\\\\[-2.84526pt] \hskip 91.04881pt=W_{(k_{1},\ldots,k_{n})}\otimes\mathbbm{1}^{A_{k_{n}}^{O}},\\\\[5.69054pt] \forall\,n=1,\ldots,N,\ \forall\,(k_{1},\ldots,k_{n}),\ W_{(k_{1},\ldots,k_{n})}\geq 0.\end{array}\right.$ (143) |  Primal problem: (using Eq. (71)) $\displaystyle\max_{\tilde{W}\in\Tr_{F}\textup{{QC-QC}}}\ \Tr\left(\Omega_{\theta}(h)\,\tilde{W}\right)$ $\displaystyle=\max\ \Tr\left(\sum_{k_{N}}\Big{(}\Tr_{A_{k_{N}}^{O}}\Omega_{\theta}(h)\Big{)}W_{({\cal N}\backslash k_{N},k_{N})}\right)$ $\displaystyle\quad\text{s.t.}\left\\{\\!\begin{array}[]{l}\sum_{k_{1}}\Tr W_{(\emptyset,k_{1})}=1,\\\\[5.69054pt] \forall\,n=1,\ldots,N-1,\ \forall\,{\cal K}_{n},\\\ \qquad\sum_{k_{n+1}\in{\cal N}\backslash{\cal K}_{n}}\Tr_{A_{k_{n+1}}^{I}}W_{({\cal K}_{n},k_{n+1})}\\\\[2.84526pt] \hskip 56.9055pt=\sum_{k_{n}\in{\cal K}_{n}}W_{({\cal K}_{n}\backslash k_{n},k_{n})}\otimes\mathbbm{1}^{A_{k_{n}}^{O}},\\\\[5.69054pt] \forall\,n=1,\ldots,N,\ \forall\,{\cal K}_{n-1},k_{n},\ W_{({\cal K}_{n-1},k_{n})}\geq 0.\end{array}\right.$ (149)
$\displaystyle{\cal W}$ $\displaystyle=\bigoplus_{n=1}^{N}\bigoplus_{(k_{1},\ldots,k_{n})}W_{(k_{1},\ldots,k_{n})},$ $\displaystyle{\cal A}$ $\displaystyle=\left(\bigoplus_{n=1}^{N-1}\bigoplus_{(k_{1},\ldots,k_{n})}\\!\\!\\!\\!\\!\mathbb{0}^{A_{\\{k_{1},\ldots,k_{n-1}\\}}^{IO}A_{k_{n}}^{I}}\\!\right)\\!\oplus\\!\\!\bigoplus_{(k_{1},\ldots,k_{N})}\\!\\!\\!\\!\Tr_{A_{k_{N}}^{O}}\\!\Omega_{\theta}(h),$ $\displaystyle\Phi({\cal W})$ $\displaystyle=\bigoplus_{n=0}^{N-1}\bigoplus_{(k_{1},\ldots,k_{n})}\Phi_{(k_{1},\ldots,k_{n})}({\cal W})$ with $\displaystyle\left\\{\begin{array}[]{l}\Phi_{\emptyset}({\cal W})=\sum_{k_{1}}\Tr W_{(k_{1})},\\\\[5.69054pt] \forall\,n=1,\ldots,N-1,\forall\,(k_{1},\ldots,k_{n}),\\\\[2.84526pt] \hskip 5.69054pt\Phi_{(k_{1},\ldots,k_{n})}({\cal W})=\sum_{k_{n+1}}\\!\Tr_{A_{k_{n+1}^{I}}}\\!\\!W_{(k_{1},\ldots,k_{n},k_{n+1})}\\\ \hskip 85.35826pt-W_{(k_{1},\ldots,k_{n})}\otimes\mathbbm{1}^{A_{k_{n}}^{O}},\end{array}\right.$ (154) $\displaystyle{\cal B}$ $\displaystyle=1\oplus\bigoplus_{n=1}^{N-1}\bigoplus_{(k_{1},\ldots,k_{n})}\mathbb{0}^{A_{\\{k_{1},\ldots,k_{n}\\}}^{IO}}.$ (155) |  $\displaystyle{\cal W}$ $\displaystyle=\bigoplus_{n=1}^{N}\bigoplus_{{\cal K}_{n-1},k_{n}}W_{{\cal K}_{n-1},k_{n}},$ $\displaystyle{\cal A}$ $\displaystyle=\left(\bigoplus_{n=1}^{N-1}\bigoplus_{{\cal K}_{n-1},k_{n}}\mathbb{0}^{A_{{\cal K}_{n-1}}^{IO}A_{k_{n}}^{I}}\right)\oplus\,\bigoplus_{k_{N}}\,\Tr_{A_{k_{N}}^{O}}\Omega_{\theta}(h),$ $\displaystyle\Phi({\cal W})$ $\displaystyle=\bigoplus_{n=0}^{N-1}\bigoplus_{{\cal K}_{n}}\Phi_{{\cal K}_{n}}({\cal W})$ with $\displaystyle\left\\{\begin{array}[]{l}\Phi_{\emptyset}({\cal W})=\sum_{k_{1}}\Tr W_{(\emptyset,k_{1})},\\\\[5.69054pt] \forall\,n=1,\ldots,N-1,\forall\,{\cal K}_{n},\\\\[2.84526pt] \quad\Phi_{{\cal K}_{n}}({\cal W})=\sum_{k_{n+1}\in\mathcal{N}\backslash\mathcal{K}_{n}}\Tr_{A_{k_{n+1}}^{I}}W_{(\mathcal{K}_{n},k_{n+1})}\\\ \hskip 71.13188pt-\sum_{k_{n}\in\mathcal{K}_{n}}W_{(\mathcal{K}_{n}\backslash k_{n},k_{n})}\otimes\mathbbm{1}^{A_{k_{n}}^{O}},\end{array}\right.$ (160) $\displaystyle{\cal B}$ $\displaystyle=1\oplus\bigoplus_{n=1}^{N-1}\bigoplus_{{\cal K}_{n}}\,\mathbb{0}^{A_{{\cal K}_{n}}^{IO}}.$ (161)
$\displaystyle{\cal S}$ $\displaystyle=\bigoplus_{n=0}^{N-1}\bigoplus_{(k_{1},\ldots,k_{n})}\\!\\!S_{(k_{1},\ldots,k_{n})}\quad\in\bigoplus_{n=0}^{N-1}\bigoplus_{(k_{1},\ldots,k_{n})}\\!\\!{\cal L}({\cal H}^{A_{\\{k_{1},\ldots,k_{n}\\}}^{IO}}).$ (162) |  $\displaystyle{\cal S}$ $\displaystyle=\bigoplus_{n=0}^{N-1}\bigoplus_{{\cal K}_{n}}S_{{\cal K}_{n}}\quad\in\bigoplus_{n=0}^{N-1}\bigoplus_{{\cal K}_{n}}{\cal L}({\cal H}^{A_{{\cal K}_{n}}^{IO}}).$ (163)
$\displaystyle\Phi^{\dagger}({\cal S})$ $\displaystyle=\bigoplus_{n=1}^{N}\bigoplus_{(k_{1},\ldots,k_{n})}(\Phi^{\dagger})_{(k_{1},\ldots,k_{n})}({\cal S})$ with $\displaystyle\left\\{\begin{array}[]{l}\forall\,n=1,\ldots,N-1,\forall\,(k_{1},\ldots,k_{n}),\\\ \quad(\Phi^{\dagger})_{(k_{1},\ldots,k_{n})}({\cal S})=S_{(k_{1},\ldots,k_{n-1})}\otimes\mathbbm{1}^{A_{k_{n}}^{I}}\\\ \hskip 99.58464pt-\Tr_{A_{k_{n}}^{O}}S_{(k_{1},\ldots,k_{n})},\\\\[5.69054pt] \forall\,(k_{1},\ldots,k_{N}),\\\ \quad(\Phi^{\dagger})_{(k_{1},\ldots,k_{N})}({\cal S})=S_{(k_{1},\ldots,k_{N-1})}\otimes\mathbbm{1}^{A_{k_{N}}^{I}}.\end{array}\right.$ (169) |  $\displaystyle\Phi^{\dagger}({\cal S})$ $\displaystyle=\bigoplus_{n=1}^{N}\bigoplus_{{\cal K}_{n-1},k_{n}}(\Phi^{\dagger})_{({\cal K}_{n-1},k_{n})}({\cal S})$ with $\displaystyle\left\\{\begin{array}[]{l}\forall\,n=1,\ldots,N-1,\forall\,{\cal K}_{n},\forall\,k_{n}\in{\cal K}_{n},\\\ \quad(\Phi^{\dagger})_{({\cal K}_{n}\backslash k_{n},k_{n})}({\cal S})=S_{{\cal K}_{n}\backslash k_{n}}\otimes\mathbbm{1}^{A_{k_{n}}^{I}}\\\ \hskip 113.81102pt-\Tr_{A_{k_{n}}^{O}}S_{{\cal K}_{n}},\\\\[5.69054pt] \forall\,k_{N},(\Phi^{\dagger})_{({\cal N}\backslash k_{N},k_{N})}({\cal S})=S_{{\cal N}\backslash k_{N}}\otimes\mathbbm{1}^{A_{k_{N}}^{I}}.\end{array}\right.$ (174)
Dual problem: $\displaystyle\begin{array}[]{rl}\min_{\cal S}&S_{\emptyset}\\\\[5.69054pt] \text{s.t.}&\left\\{\begin{array}[]{l}\forall\,n=1,\ldots,N-1,\forall\,(k_{1},\ldots,k_{n}),\\\ \quad S_{(k_{1},\ldots,k_{n-1})}\otimes\mathbbm{1}^{A_{k_{n}}^{I}}\geq\Tr_{A_{k_{n}}^{O}}S_{(k_{1},\ldots,k_{n})},\\\\[5.69054pt] \forall\,(k_{1},\ldots,k_{N}),\\\ \quad S_{(k_{1},\ldots,k_{N-1})}\otimes\mathbbm{1}^{A_{k_{N}}^{I}}\geq\Tr_{A_{k_{N}}^{O}}\Omega_{\theta}(h).\end{array}\right.\end{array}$ (181) To verify Slater’s condition for strong duality, one can consider ${\cal W}=\bigoplus_{n=1}^{N}\bigoplus_{(k_{1},\ldots,k_{n})}\frac{(N-n)!}{N!}\frac{\mathbbm{1}^{A_{\\{k_{1},\ldots,k_{n-1}\\}}^{IO}A_{k_{n}}^{I}}}{d_{A_{\\{k_{1},\ldots,k_{n}\\}}^{I}}}$, which satisfies $\Phi({\cal W})={\cal B}$ and ${\cal W}>0$. (Finding a Hermitian ${\cal S}$ such that $\Phi^{\dagger}({\cal S})\geq{\cal A}$ is rather trivial.) Furthermore, a very similar construction to that in Eq. (130) for the QC-FO case (essentially, replacing $S_{n}^{(\prime)}$ by $S_{(k_{1},\ldots,k_{n})}^{(\prime)}$ and taking the identity operators in the appropriate spaces) then shows that the first inequalities above can without loss of generality be replaced by equalities, $S_{(k_{1},\ldots,k_{n-1})}\otimes\mathbbm{1}^{A_{k_{n}}^{I}}=\Tr_{A_{k_{n}}^{O}}S_{(k_{1},\ldots,k_{n})}$. |  Dual problem: $\displaystyle\begin{array}[]{rl}\min_{\cal S}&S_{\emptyset}\\\\[5.69054pt] \text{s.t.}&\left\\{\begin{array}[]{l}\forall\,n=1,\ldots,N-1,\forall\,{\cal K}_{n},\forall\,k_{n}\in{\cal K}_{n},\\\ \hskip 34.1433ptS_{{\cal K}_{n}\backslash k_{n}}\otimes\mathbbm{1}^{A_{k_{n}}^{I}}\geq\Tr_{A_{k_{n}}^{O}}S_{{\cal K}_{n}},\\\\[5.69054pt] \forall\,k_{N},\ S_{{\cal N}\backslash k_{N}}\otimes\mathbbm{1}^{A_{k_{N}}^{I}}\geq\Tr_{A_{k_{N}}^{O}}\Omega_{\theta}(h).\end{array}\right.\end{array}$ (187) To verify Slater’s condition for strong duality, one can consider ${\cal W}=\bigoplus_{n=1}^{N}\bigoplus_{{\cal K}_{n-1},k_{n}}\frac{1}{n\binom{N}{n}}\frac{\mathbbm{1}^{A_{{\cal K}_{n-1}}^{IO}A_{k_{n}}^{I}}}{d_{A_{{\cal K}_{n-1}\cup\\{k_{n}\\}}^{I}}}$, which satisfies $\Phi({\cal W})={\cal B}$ and ${\cal W}>0$. (Finding a Hermitian ${\cal S}$ such that $\Phi^{\dagger}({\cal S})\geq{\cal A}$ is rather trivial.) (Note that the construction of Eq. (130) does not work here: except for the case $n=1$, the inequalities above can in general not be replaced by equalities.)
$S_{(k_{1},\ldots,k_{N-1})}\otimes\mathbbm{1}^{A_{k_{N}}^{I}}\geq\Tr_{A_{k_{N}}^{O}}\Omega_{\theta}(h)$ in Eq. (LABEL:eq:dual_QCCC_v1) above can be linearized into $\displaystyle{\mathbf{A}}_{\text{Schur},k_{N}}(S_{(k_{1},\ldots,k_{N-1})},h)\geq 0.$ (188) |  $S_{{\cal N}\backslash k_{N}}\otimes\mathbbm{1}^{A_{k_{N}}^{I}}\geq\Tr_{A_{k_{N}}^{O}}\Omega_{\theta}(h)$ in Eq. (LABEL:eq:dual_QCQC_v1) above can be linearized into $\displaystyle{\mathbf{A}}_{\text{Schur},k_{N}}(S_{{\cal N}\backslash k_{N}},h)\geq 0.$ (189)
Optimal QFI: $\displaystyle J_{\theta}^{\textup{{QC-CC}}}(C_{\theta}^{\otimes N})$ $\displaystyle\begin{array}[]{rl}\\!=\\!\\!&\min_{h,{\cal S}}\ S_{\emptyset}\\\\[5.69054pt] &\text{s.t.}\left\\{\\!\begin{array}[]{l}\forall\,n=1,\ldots,N-1,\forall\,(k_{1},\ldots,k_{n}),\\\ \qquad S_{(k_{1},\ldots,k_{n-1})}\otimes\mathbbm{1}^{A_{k_{n}}^{I}}=\Tr_{A_{k_{n}}^{O}}S_{(k_{1},\ldots,k_{n})},\\\\[5.69054pt] \forall\,(k_{1},\ldots,k_{N}),\,{\mathbf{A}}_{\text{Schur},k_{N}}(S_{(k_{1},\ldots,k_{N-1})},h)\geq 0.\end{array}\right.\end{array}$ (195) |  Optimal QFI: $\displaystyle J_{\theta}^{\textup{{QC-QC}}}(C_{\theta}^{\otimes N})$ $\displaystyle\begin{array}[]{rl}=&\min_{h,{\cal S}}\ S_{\emptyset}\\\\[5.69054pt] &\text{s.t.}\ \left\\{\begin{array}[]{l}\forall\,n=1,\ldots,N-1,\forall\,{\cal K}_{n},\forall\,k_{n}\in{\cal K}_{n},\\\ \hskip 34.1433ptS_{{\cal K}_{n}\backslash k_{n}}\otimes\mathbbm{1}^{A_{k_{n}}^{I}}\geq\Tr_{A_{k_{n}}^{O}}S_{{\cal K}_{n}},\\\\[5.69054pt] \forall\,k_{N},\ {\mathbf{A}}_{\text{Schur},k_{N}}(S_{{\cal N}\backslash k_{N}},h)\geq 0.\end{array}\right.\end{array}$ (201)
The optimal process $\tilde{W}^{\text{(opt)}}\in\Tr_{F}\textup{{QC-CC}}$ is recovered by solving Eq. (LABEL:eq:primal_QCCC) after fixing $h=h^{\text{(opt)}}$ obtained from Eq. (LABEL:eq:optim_QFI_QCCC) and adding the constraint that ${\mathbf{C}_{\theta}^{0}}{}^{\dagger}\tilde{W}^{T}\big{(}\dot{\mathbf{C}}_{\theta}^{0}-i\mathbf{C}_{\theta}^{0}h^{\text{(opt)}}\big{)}\in\mathbb{H}_{q}$, as in Eq. (107)—and with $\tilde{W}=\sum_{(k_{1},\ldots,k_{N})}W_{(N)}\otimes\mathbbm{1}^{A_{N}^{O}}$ (see Eq. (61)). Recall here that the purification $W^{\text{(opt)}}={|w\rangle\\!\langle w|}$ of $\tilde{W}^{\text{(opt)}}$ is however not guaranteed to be in QC-CC. |  The optimal process $\tilde{W}^{\text{(opt)}}\in\Tr_{F}\textup{{QC-QC}}$ is recovered by solving Eq. (LABEL:eq:primal_QCQC) after fixing $h=h^{\text{(opt)}}$ obtained from Eq. (LABEL:eq:optim_QFI_QCQC) and adding the constraint that ${\mathbf{C}_{\theta}^{0}}{}^{\dagger}\tilde{W}^{T}\big{(}\dot{\mathbf{C}}_{\theta}^{0}-i\mathbf{C}_{\theta}^{0}h^{\text{(opt)}}\big{)}\in\mathbb{H}_{q}$, as in Eq. (107)—and with $\tilde{W}=\sum_{k_{N}\in\mathcal{N}}W_{(\mathcal{N}\setminus k_{N},k_{N})}\otimes\mathbbm{1}^{A_{k_{N}}^{O}}$ (see Eq. (71)). The optimal process $W^{\text{(opt)}}={|w\rangle\\!\langle w|}\in\textup{{QC-QC}}$ is then obtained by purifying $\tilde{W}^{\text{(opt)}}$.

####  B.2.3 SDP problems for the QC-Par, QC-Sup and Gen classes

For completeness, let us briefly write the explicit SDP problems one needs to
consider for the remaining classes considered in this paper. These can be
obtained in a similar fashion to the previous ones, or as in Ref. [19] (up to
the difference mentioned in Footnote 21).

For the QC-Par class:

$\displaystyle\begin{array}[]{rl}J_{\theta}^{\textup{{QC-
Par}}}(C_{\theta}^{\otimes N})=&\min_{h,S_{0}}\ \ S_{0}\\\\[5.69054pt]
&\quad\text{s.t. }\ S_{0}\,\mathbbm{1}^{A_{\cal N}^{I}}\geq\Tr_{A_{\cal
N}^{O}}\Omega_{\theta}(h),\end{array}$ (204)

with $S_{0}\in\mathbb{R}$, and where the constraint can be linearized into

$\displaystyle{\mathbf{A}}_{\text{Schur}}(S_{0}\,\mathbbm{1}^{A_{\cal
N}^{I}},{\mathbf{C}}_{\cal N}(h))\geq 0$ (205)

with (similarly to Eq. (112), with clear enough notation)

$\displaystyle{\mathbf{C}}_{\cal N}(h)=2\Big{(}{\langle
j_{1},\ldots,j_{N}|}^{A_{1}^{O}\cdots
A_{N}^{O}}\big{(}{\dot{\mathbf{C}}_{\theta}^{0}}-i{\mathbf{C}_{\theta}^{0}}h\big{)}^{\\!*}\Big{)}_{j_{1},\ldots,j_{N}}.$
(206)

The optimal $\tilde{W}^{\text{(opt)}}\in\Tr_{F}\textup{{QC-Par}}$ (and
$W^{\text{(opt)}}={|w\rangle\\!\langle w|}\in\textup{{QC-Par}}$, after
purification) is recovered by solving Eq. (107), translating the constraint
$\tilde{W}\in\Tr_{F}\textup{{QC-Par}}$ into (see Eq. (22))

$\displaystyle\left\\{\begin{array}[]{l}\tilde{W}=W_{(I)}\otimes\mathbbm{1}^{A_{\cal
N}^{O}},\\\\[2.84526pt] \Tr W_{(I)}=1,\\\\[2.84526pt] W_{(I)}\geq
0.\end{array}\right.$ (210)

For the QC-Sup class:

$\displaystyle J_{\theta}^{\textup{{QC-Sup}}}(C_{\theta}^{\otimes N})$
$\displaystyle\begin{array}[]{rl}=&\min_{h,{\cal S}}\ S_{0}\\\\[5.69054pt]
&\text{s.t.}\ \forall\,\pi,\
\left\\{\begin{array}[]{l}S_{0}\,\mathbbm{1}^{A_{\pi(1)}^{I}}=\Tr_{A_{\pi(1)}^{O}}S_{(\pi,1)},\\\\[5.69054pt]
\forall\,n=2,\ldots,N-1,\\\ \quad
S_{(\pi,n-1)}\otimes\mathbbm{1}^{A_{\pi(n)}^{I}}=\Tr_{A_{\pi(n)}^{O}}S_{(\pi,n)},\\\\[5.69054pt]
S_{(\pi,N-1)}\otimes\mathbbm{1}^{A_{\pi(N)}^{I}}\geq\Tr_{A_{\pi(N)}^{O}}\Omega_{\theta}(h),\end{array}\right.\end{array}$
(217)

where the variables in the optimization (all encapsulated in ${\cal S}$, as
done previously) are taken to be $S_{0}\in\mathbb{R}$ and $S_{(\pi,n)}\in{\cal
L}({\cal H}^{A_{\\{\pi(1),\ldots,\pi(n)\\}}^{IO}})$ for all $\pi$ and
$n=1,\ldots,N-1$; and where the last constraints (for each $\pi$) can be
linearized into

$\displaystyle{\mathbf{A}}_{\text{Schur},\pi(N)}(S_{(\pi,N-1)},h)\geq 0.$
(218)

The optimal $\tilde{W}^{\text{(opt)}}\in\Tr_{F}\textup{{QC-Sup}}$ (and
$W^{\text{(opt)}}={|w\rangle\\!\langle w|}\in\textup{{QC-Sup}}$, after
purification) is recovered by solving Eq. (107), translating the constraint
$\tilde{W}\in\Tr_{F}\textup{{QC-Sup}}$ into (see Eq. (42), replacing
$q_{\pi}W_{\pi}$ by $\tilde{W}_{\pi}$)

$\displaystyle\left\\{\begin{array}[]{l}\tilde{W}=\sum_{\pi}\tilde{W}_{\pi},\\\\[2.84526pt]
\forall\,\pi,\tilde{W}_{\pi}\in\Tr_{F}(\text{{{QC-
FO}}}_{\pi}^{\propto}),\\\\[2.84526pt] \Tr\tilde{W}=d_{A_{\cal
N}^{O}},\end{array}\right.$ (222)

where $\textup{{QC-FO}}_{\pi}^{\propto}$ denotes the class of process matrices
that are proportional (with a nonnegative proportionality factor) to matrices
in $\textup{{QC-FO}}_{\pi}$, or more explicitly,

$\displaystyle\left\\{\begin{array}[]{l}\tilde{W}=\sum_{\pi}W_{(\pi,N)}\otimes\mathbbm{1}^{A_{\pi(N)}^{O}},\\\\[2.84526pt]
\sum_{\pi}\Tr W_{(\pi,1)}=1,\\\\[2.84526pt]
\forall\,\pi,\forall\,n=1,\ldots,N-1,\\\
\qquad\Tr_{A_{\pi(n+1)}^{I}}\\!W_{(\pi,n+1)}=W_{(\pi,n)}\otimes\mathbbm{1}^{A_{\pi(n)}^{O}},\\\\[2.84526pt]
\forall\,\pi,\forall\,n=1,\ldots,N,\ W_{(\pi,n)}\geq 0\end{array}\right.$
(228)

(with each $W_{(\pi,n)}\in{\cal L}({\cal
H}^{A_{\\{\pi(1),\ldots,\pi(n-1)\\}}^{IO}A_{\pi(n)}^{I}})$).

For the Gen class, finally:

$\displaystyle J_{\theta}^{\textup{{Gen}}}(C_{\theta}^{\otimes N})$
$\displaystyle\begin{array}[]{rl}=&\min_{h,S}\ \Tr[S]/d_{A_{\cal
N}^{I}}\\\\[5.69054pt] &\text{s.t.}\
\left\\{\begin{array}[]{l}\forall\,k=1,\ldots,N,\
{}_{[1-A_{k}^{I}]}\Tr_{A_{k}^{O}}S=0,\\\\[5.69054pt]
S\geq\Omega_{\theta}(h),\end{array}\right.\end{array}$ (233)

with $S\in{\cal L}({\cal H}^{A_{\cal N}^{IO}})$, and where the last constraint
can be linearized into

$\displaystyle{\mathbf{A}}_{\text{Schur}}(S,2(\dot{\mathbf{C}}_{\theta}^{0}-i\mathbf{C}_{\theta}^{0}h)^{*})\geq
0.$ (234)

The optimal $\tilde{W}^{\text{(opt)}}\in\Tr_{F}\textup{{Gen}}$ (and
$W^{\text{(opt)}}={|w\rangle\\!\langle w|}\in\textup{{Gen}}$, after
purification) is recovered by solving Eq. (107), translating the constraint
$\tilde{W}\in\Tr_{F}\textup{{Gen}}$ into (see Eq. (48))

$\displaystyle\left\\{\begin{array}[]{l}\forall\,\emptyset\subsetneq{\cal
K}\subseteq{\cal N},\ {}_{\prod_{k\in{\cal
K}}[1-A_{k}^{O}]}(\Tr_{A_{\mathcal{N}\setminus\mathcal{K}}^{IO}}\tilde{W})=0,\\\\[2.84526pt]
\Tr\tilde{W}=d_{A_{\cal N}^{O}},\\\\[2.84526pt] \tilde{W}\geq
0.\end{array}\right.$ (238)

###  B.3 On the importance of imposing Eq. (101)

To wrap up this appendix, let us clarify the need for imposing Eq. (101) when
reconstructing the optimal process (in step B.1.8 above).

Consider some continuous, real-valued function $f(h,w)$, defined over some
compact domains for $h$ and $w$. Fan’s minimax theorem [49] says that the
optimal values of the $\min_{h}\max_{w}$ and $\max_{w}\min_{h}$ optimization
problems coincide:

$\displaystyle\min_{h}\max_{w}f(h,w)=\max_{w}\min_{h}f(h,w).$ (239)

However, the solutions to both problems are in general not the same: a
solution to the $\min_{h}\max_{w}$ is not necessarily a solution to the
$\max_{w}\min_{h}$ problem.

Suppose that $(h^{\downarrow},w^{\downarrow})$ and
$(h^{\uparrow},w^{\uparrow})$ are solutions to the $\min_{h}\max_{w}$ and
$\max_{w}\min_{h}$ problems, respectively. Then one clearly has

$\displaystyle f(h^{\downarrow},w^{\downarrow})\geq
f(h^{\downarrow},w^{\uparrow})\geq f(h^{\uparrow},w^{\uparrow}),$ (240)

and from Eq. (239) it follows that both inequalities are in fact equalities
[19], so that $(h^{\downarrow},w^{\uparrow})$ is a solution to both the
$\min_{h}\max_{w}$ and $\max_{w}\min_{h}$ problems: it corresponds to a saddle
point.

Hence, once a solution $(h^{\downarrow},w^{\downarrow})$ of the
$\min_{h}\max_{w}$ problem is known, we know there exists a solution to the
$\max_{w}\min_{h}$ problem with $h=h^{\downarrow}=h^{\text{(opt)}}$. Simply
optimizing $w$ for this fixed value of $h$, however, is not enough, in
general, to identify such a solution $(h^{\text{(opt)}},w^{\text{(opt)}})$ to
the $\max_{w}\min_{h}$ problem. Indeed, it could be that several values of
$w$, other than the saddle point, give the same value of
$f(h^{\text{(opt)}},w)=f(h^{\text{(opt)}},w^{\text{(opt)}})$. Such a situation
is illustrated in Fig. 8.

Figure 8: Plot of the function $f(h,w)=h^{2}+2hw$, as an illustration of a
function that is convex in $h$ and concave (even linear) in $w$. $f(h,w)$ has
a saddle point for $(h^{\text{(opt)}},w^{\text{(opt)}})=(0,0)$. All points on
the red line, for $h=h^{\text{(opt)}}=0$, are solutions to the
$\min_{h}\max_{w}f(h,w)$ problem. However, when fixing $h=h^{\text{(opt)}}=0$
the function $f(h^{\text{(opt)}},w)$ becomes constant in $w$: the saddle
point, which is the only one that is also solution to the
$\max_{w}\min_{h}f(h,w)$ problem, can then only be found after imposing that
the derivative of $f(h,w)$ over $h$ must be null, i.e.,
$\partial_{h}f(h,w)|_{h=h^{\text{(opt)}}}=0$.

To make sure that one indeed finds a solution to the $\max_{w}\min_{h}$
problem when optimizing $w$ for the fixed $h=h^{\text{(opt)}}$, one thus needs
to also impose that for the optimal value of $w$, $h^{\text{(opt)}}$ is indeed
a solution to $\min_{h}f(w,h)$. This can be done by requiring that
$\partial_{h}f(h,w)|_{h=h^{\text{(opt)}}}=0$ (which is a defining property for
a saddle point). For the function $f$ we consider in this work, this
translates into Eq. (101).

The situation just depicted for a general (convex-concave) function $f(h,w)$
is indeed commonly encountered in the metrological context of our work. As a
simple example, consider for instance the case of $N=1$ qubit depolarizing
channel $\mathcal{D}_{\theta}$ as in Eq. (9). Since $N=1$, all the classes of
processes considered in this work coincide. Taking
$\\{{|C_{\theta,j}^{0}\rangle}\\}_{j=1}^{4}$ to be an eigendecomposition of
the Choi matrix of $\mathcal{D}_{\theta}$ (with eigenvectors in the degenerate
eigensubspace taken to be independent of $\theta$, except for their
normalization) and following the approach described above, we find
numerically, for all values of $\theta$, the optimal value of $h$ to be
$h^{\text{(opt)}}=0$.

Now, for this value one finds that
$\Tr_{A^{O}}\Omega_{\theta}(h^{\text{(opt)}})=\frac{3}{(1-\theta)(1+3\theta)}\mathbbm{1}^{A^{I}}$.
Since for all classes, $\tilde{W}$ is of the form
$\tilde{W}=\rho^{A^{I}}\otimes\mathbbm{1}^{A^{O}}$ with $\tr(\rho^{A^{I}})=1$,
one then finds that
$\Tr(\Omega_{\theta}(h^{\text{(opt)}})\,\tilde{W})=\frac{3}{(1-\theta)(1+3\theta)}$
is independent from $\tilde{W}$. While this indeed gives the correct value for
a single qubit depolarizing channel QFI (see Eq. (78)), clearly one could not
recover the optimal $\tilde{W}$ (or $\rho^{A^{I}}$) by directly optimizing
$\Tr(\Omega_{\theta}(h^{\text{(opt)}})\,\tilde{W})$. Imposing Eq. (101)
however, enforces $\rho^{A^{I}}$ to be the maximally mixed state
$\frac{\mathbbm{1}^{A^{I}}}{2}$, which indeed (after purification into a
maximally entangled 2-qubit state) gives the optimal QFI of the depolarizing
channel.252525Considering inputting half of a 2-qubit state
${|\psi_{\text{in}}\rangle}=\alpha{|0,0\rangle}+\beta{|1,1\rangle}$ into
$\mathcal{D}_{\theta}$, one finds (e.g., using Eq. (2)) the QFI of the 2-qubit
output state to be
$\frac{1+3\theta+8|\alpha|^{2}|\beta|^{2}}{(1-\theta^{2})(1+3\theta)}$. This
indeed clearly depends on the input state, and is optimal for a maximally
entangled state.

##  Appendix C Numerical results for the QFI of the composed rotation &
amplitude damping channels $\mathcal{A}_{\theta}$

We report in Tables 1 and 2, and in Figures 9 and 10, the optimal values of
the QFI obtained numerically (by solving the SDP) for the different classes,
in the case of $N=2$ and $N=3$ queries (respectively) to the composed rotation
& amplitude damping channel $\mathcal{A}_{\theta}$ defined in Eq. (81). As
mentioned in the main text, the QFI does not depend on the specific value of
$\theta$ for these channels. We recover the hierarchies obtained in Eqs. (82)
and (83), respectively.

$u$ | $J_{\theta}^{\textup{{QC-Par}}}(A_{\theta}^{\otimes 2})$ | $\\!\begin{array}[]{r}\\\\[-8.0pt] J_{\theta}^{\textup{{QC-FO}}}(A_{\theta}^{\otimes 2}),\\\\[2.84526pt] J_{\theta}^{\textup{{QC-CC}}}(A_{\theta}^{\otimes 2})\end{array}\\!$ | $\\!\begin{array}[]{r}\\\\[-8.0pt] J^{\textup{{QC-CC}}}_{\theta,\textup{purif}}(A_{\theta}^{\otimes 2}),\,J_{\theta}^{\textup{{QC-Sup}}}(A_{\theta}^{\otimes 2}),\\\\[2.84526pt] J_{\theta}^{\textup{{QC-QC}}}(A_{\theta}^{\otimes 2}),\,J_{\theta}^{\textup{{Gen}}}(A_{\theta}^{\otimes 2})\end{array}\\!$
---|---|---|---
0 | 4 | 4 | 4
0.1 | 3.5900 | 3.6477 | 3.6929
0.2 | 3.1605 | 3.2904 | 3.3709
0.3 | 2.7128 | 2.9273 | 3.0324
0.4 | 2.2500 | 2.5574 | 2.6760
0.5 | 1.7946 | 2.1793 | 2.2995
0.6 | 1.4314 | 1.7911 | 1.9005
0.7 | 1.1177 | 1.3900 | 1.4764
0.8 | 0.8117 | 0.9714 | 1.0240
0.9 | 0.4734 | 0.5260 | 0.5410
1 | 0 | 0 | 0
Table 1: QFI for $N=2$ uses of the composed rotation & amplitude damping
channel $\mathcal{A}_{\theta}$, for the different classes under consideration,
for $0\leq u\leq 1$ (and any fixed value of $\theta$). Notice that here
(except for $u=0$ and $u=1$) $J^{\textup{{QC-
CC}}}_{\theta,\textup{purif}}(A_{\theta}^{\otimes 2})$ is a strict upper bound
on $J^{\textup{{QC-CC}}}_{\theta}(A_{\theta}^{\otimes 2})$—which, in the case
of $N=2$, we know is equal to $J_{\theta}^{\textup{{QC-
FO}}}(A_{\theta}^{\otimes 2})$; cf. Eq. (76). Figure 9: QFI for $N=2$ uses of
the composed rotation & amplitude damping channel $\mathcal{A}_{\theta}$, as
in Table 1.

$u$ | $J_{\theta}^{\textup{{QC-Par}}}(A_{\theta}^{\\!\otimes 3})$ | $J_{\theta}^{\textup{{QC-FO}}}(A_{\theta}^{\\!\otimes 3})$ | $\\!\\!\begin{array}[]{r}\\\\[-8.0pt] J^{\textup{{QC-CC}}}_{\theta,\textup{purif}}(A_{\theta}^{\\!\otimes 3}),\\\\[2.84526pt] J_{\theta}^{\textup{{QC-Sup}}}(A_{\theta}^{\\!\otimes 3})\end{array}\\!\\!$ | $J_{\theta}^{\textup{{QC-QC}}}(A_{\theta}^{\\!\otimes 3})$ | $J_{\theta}^{\textup{{Gen}}}(A_{\theta}^{\\!\otimes 3})$
---|---|---|---|---|---
0 | 9 | 9 | 9 | 9 | 9
0.1 | 7.6366 | 7.9238 | 8.1848 | 8.1986 | 8.2001
0.2 | 6.2628 | 6.8951 | 7.3643 | 7.3741 | 7.3751
0.3 | 4.9111 | 5.9140 | 6.5231 | 6.5242 | 6.5242
0.4 | 3.8614 | 4.9797 | 5.6417 | 5.6461 | 5.6468
0.5 | 3.1082 | 4.0905 | 4.7247 | 4.7373 | 4.7431
0.6 | 2.4344 | 3.2427 | 3.7859 | 3.8048 | 3.8150
0.7 | 1.8217 | 2.4300 | 2.8317 | 2.8564 | 2.8698
0.8 | 1.2786 | 1.6412 | 1.8710 | 1.8957 | 1.9086
0.9 | 0.7255 | 0.8553 | 0.9177 | 0.9260 | 0.9299
1 | 0 | 0 | 0 | 0 | 0

Table 2: QFI for $N=3$ uses of the composed rotation & amplitude damping
channel $\mathcal{A}_{\theta}$, for the different classes under consideration,
for $0\leq u\leq 1$ (and any fixed value of $\theta$). Recall that
$J^{\textup{{QC-CC}}}_{\theta,\textup{purif}}(A_{\theta}^{\otimes 3})$ is only
an upper bound on $J^{\textup{{QC-CC}}}_{\theta}(A_{\theta}^{\otimes 3})$,
which our approach does not allow us to access directly; cf. Eq. (77). Figure
10: QFI for $N=3$ uses of the composed rotation & amplitude damping channel
$\mathcal{A}_{\theta}$, as in Table 2.

Recall that our SDPs allow us, for each class, to reconstruct the processes
that give the optimal values of the QFI. Except in the simplest cases262626For
instance, for $N=2$, for the class of parallel strategies QC-Par and for
$u\lesssim 0.45$, the SDP returns optimal processes of the form
$\tilde{W}=\Tr_{F}W=(a{|00\rangle\\!\langle 00|}+b{|11\rangle\\!\langle
11|})^{A_{1}^{I}A_{2}^{I}}\otimes\mathbbm{1}^{A_{1}^{O}A_{2}^{O}}$, for some
(nonnegative, $u$-dependent) values of $a,b$. These can be purified in the
form $W={|w\rangle\\!\langle w|}$ with
${|w\rangle}=(\sqrt{a}{|000\rangle}+\sqrt{b}{|111\rangle})^{A_{1}^{I}A_{2}^{I}F_{I}}\otimes|\mathbbm{1}\rangle\\!\rangle^{A_{1}^{O}F_{1}}\otimes|\mathbbm{1}\rangle\\!\rangle^{A_{2}^{O}F_{2}}$;
the QFI of the output state can then be calculated analytically, and optimized
(for some fixed $u$) over the values of $a,b$—which leads to $J^{\textup{{QC-
Par}}}(A_{\theta}^{\otimes 2})=\frac{4(1-u)^{2}}{(1-u/2)^{2}}$. For $u\gtrsim
0.45$ the optimal processes are found to be of the form
$\tilde{W}=\Tr_{F}W=(a{|00\rangle\\!\langle 00|}+b{|11\rangle\\!\langle
11|}+c{|01\rangle\\!\langle 01|}+c{|10\rangle\\!\langle
10|})^{A_{1}^{I}A_{2}^{I}}\otimes\mathbbm{1}^{A_{1}^{O}A_{2}^{O}}$, rather,
and expressing the corresponding optimal QFI analytically is already much more
involved. it is, however, difficult to gain much insight or intuition from the
form of the processes thus obtained numerically.

## References

  * Oreshkov  _et al._ [2012] O. Oreshkov, F. Costa, and Č. Brukner, Quantum correlations with no causal order, Nat. Commun. 3, 1092 (2012), arXiv:1105.4464 [quant-ph] .
  * Chiribella  _et al._ [2013] G. Chiribella, G. M. D’Ariano, P. Perinotti, and B. Valiron, Quantum computations without definite causal structure, Phys. Rev. A 88, 022318 (2013), arXiv:0912.0195 [quant-ph] .
  * Hardy [2005] L. Hardy, Probability theories with dynamic causal structure: a new framework for quantum gravity, arXiv:gr-qc/0509120 (2005).
  * Zych  _et al._ [2019] M. Zych, F. Costa, I. Pikovski, and Č. Brukner, Bell’s theorem for temporal order, Nat. Commun. 10, 3772 (2019), arXiv:1708.00248 [quant-ph] .
  * Chiribella [2012] G. Chiribella, Perfect discrimination of no-signalling channels via quantum superposition of causal structures, Phys. Rev. A 86, 040301(R) (2012), arXiv:1109.5154 [quant-ph] .
  * Ebler  _et al._ [2018] D. Ebler, S. Salek, and G. Chiribella, Enhanced communication with the assistance of indefinite causal order, Phys. Rev. Lett. 120, 120502 (2018), arXiv:1711.10165 [quant-ph] .
  * Feix  _et al._ [2015] A. Feix, M. Araújo, and Č. Brukner, Quantum superposition of the order of parties as a communication resource, Phys. Rev. A 92, 052326 (2015), arXiv:1508.07840 [quant-ph] .
  * Araújo  _et al._ [2015] M. Araújo, C. Branciard, F. Costa, A. Feix, C. Giarmatzi, and Č. Brukner, Witnessing causal nonseparability, New J. Phys. 17, 102001 (2015), arXiv:1506.03776 [quant-ph] .
  * Guérin  _et al._ [2016] P. A. Guérin, A. Feix, M. Araújo, and Č. Brukner, Exponential communication complexity advantage from quantum superposition of the direction of communication, Phys. Rev. Lett. 117, 100502 (2016), arXiv:1605.07372 [quant-ph] .
  * Chiribella  _et al._ [2021] G. Chiribella, M. Banik, S. S. Bhattacharya, T. Guha, M. Alimuddin, A. Roy, S. Saha, S. Agrawal, and G. Kar, Indefinite causal order enables perfect quantum communication with zero capacity channels, New J. Phys. 23, 033039 (2021), arXiv:1810.10457 [quant-ph] .
  * Mukhopadhyay  _et al._ [2018] C. Mukhopadhyay, M. K. Gupta, and A. K. Pati, Superposition of causal order as a metrological resource for quantum thermometry, arXiv:1812.07508 [quant-ph] (2018).
  * Frey [2019] M. Frey, Indefinite causal order aids quantum depolarizing channel identification, Quantum Inf. Process. 18, 96 (2019).
  * Zhao  _et al._ [2020] X. Zhao, Y. Yang, and G. Chiribella, Quantum metrology with indefinite causal order, Phys. Rev. Lett. 124, 190503 (2020), arXiv:1912.02449 [quant-ph] .
  * Frey [2021] M. Frey, Quantum network probing with indefinite routing, Quantum Inf. Process. 20, 13 (2021).
  * Altherr and Yang [2021] A. Altherr and Y. Yang, Quantum metrology for non-Markovian processes, Phys. Rev. Lett. 127, 060501 (2021), arXiv:2103.02619 [quant-ph] .
  * Chapeau-Blondeau [2021a] F. Chapeau-Blondeau, Noisy quantum metrology with the assistance of indefinite causal order, Phys. Rev. A 103, 032615 (2021a), arXiv:2104.06284 [quant-ph] .
  * Chapeau-Blondeau [2021b] F. Chapeau-Blondeau, Quantum parameter estimation on coherently superposed noisy channels, Phys. Rev. A 104, 032214 (2021b), arXiv:2110.06715 [quant-ph] .
  * Chapeau-Blondeau [2022] F. Chapeau-Blondeau, Indefinite causal order for quantum metrology with quantum thermal noise, Phys. Lett. A 447, 128300 (2022), arXiv:2211.01684 [quant-ph] .
  * Liu  _et al._ [2023] Q. Liu, Z. Hu, H. Yuan, and Y. Yang, Optimal strategies of quantum metrology with a strict hierarchy, Phys. Rev. Lett. 130, 070803 (2023), arXiv:2203.09758 [quant-ph] .
  * Chiribella and Zhao [2022] G. Chiribella and X. Zhao, Heisenberg-limited metrology with coherent control on the probes’ configuration, arXiv:2206.03052 [quant-ph] (2022).
  * Kurdziałek  _et al._ [2023] S. Kurdziałek, W. Gorecki, F. Albarelli, and R. Demkowicz-Dobrzański, Using adaptiveness and causal superpositions against noise in quantum metrology, Phys. Rev. Lett. 131, 090801 (2023), arXiv:2212.08106 [quant-ph] .
  * Goldberg  _et al._ [2023] A. Z. Goldberg, K. Heshami, and L. L. Sánchez-Soto, Evading noise in multiparameter quantum metrology with indefinite causal order, Phys. Rev. Research 5, 033198 (2023), arXiv:2309.07220 [quant-ph] .
  * Chapeau-Blondeau [2023] F. Chapeau-Blondeau, Indefinite causal order for quantum phase estimation with pauli noise, Fluct. Noise Lett. 22, 2350036 (2023), arXiv:2312.02832 [quant-ph] .
  * Braunstein and Caves [1994] S. L. Braunstein and C. M. Caves, Statistical distance and the geometry of quantum states, Phys. Rev. Lett. 72, 3439 (1994).
  * Braunstein  _et al._ [1996] S. L. Braunstein, C. M. Caves, and G. J. Milburn, Generalized uncertainty relations: Theory, examples, and Lorentz invariance, Annal. Phys. 247, 135 (1996), arXiv:quant-ph/9507004 .
  * Capela  _et al._ [2023] M. Capela, H. Verma, F. Costa, and L. C. Céleri, Reassessing thermodynamic advantage from indefinite causal order, Phys. Rev. A 107, 062208 (2023), arXiv:2208.03205 [quant-ph] .
  * Yin  _et al._ [2023] P. Yin, X. Zhao, Y. Yang, Y. Guo, W.-H. Zhang, G.-C. Li, Y.-J. Han, B.-H. Liu, J.-S. Xu, G. Chiribella, G. Chen, C.-F. Li, and G.-C. Guo, Experimental super-Heisenberg quantum metrology with indefinite gate order, arXiv:2303.17223 [quant-ph] (2023).
  * Rubino  _et al._ [2017] G. Rubino, L. A. Rozema, A. Feix, M. Araújo, J. M. Zeuner, L. M. Procopio, Č. Brukner, and P. Walther, Experimental verification of an indefinite causal order, Sci. Adv. 3, e1602589 (2017), arXiv:1608.01683 [quant-ph] .
  * Goswami  _et al._ [2018] K. Goswami, C. Giarmatzi, M. Kewming, F. Costa, C. Branciard, J. Romero, and A. G. White, Indefinite causal order in a quantum switch, Phys. Rev. Lett. 121, 090503 (2018), arXiv:1803.04302 [quant-ph] .
  * Wei  _et al._ [2019] K. Wei, N. Tischler, S.-R. Zhao, Y.-H. Li, J. M. Arrazola, Y. Liu, W. Zhang, H. Li, L. You, Z. Wang, Y.-A. Chen, B. C. Sanders, Q. Zhang, G. J. Pryde, F. Xu, and J.-W. Pan, Experimental quantum switching for exponentially superior quantum communication complexity, Phys. Rev. Lett. 122, 120504 (2019), arXiv:1810.10238 [quant-ph] .
  * Goswami  _et al._ [2020] K. Goswami, Y. Cao, G. A. Paz-Silva, J. Romero, and A. G. White, Increasing communication capacity via superposition of order, Phys. Rev. Research 2, 033292 (2020), arXiv:1807.07383 [quant-ph] .
  * Guo  _et al._ [2020] Y. Guo, X.-M. Hu, Z.-B. Hou, H. Cao, J.-M. Cui, B.-H. Liu, Y.-F. Huang, C.-F. Li, G.-C. Guo, and G. Chiribella, Experimental transmission of quantum information using a superposition of causal orders, Phys. Rev. Lett. 124, 030502 (2020), arXiv:1811.07526 [quant-ph] .
  * Rubino  _et al._ [2021a] G. Rubino, G. Manzano, and Č. Brukner, Quantum superposition of thermodynamic evolutions with opposing time’s arrows, Commun. Phys. 4, 251 (2021a), arXiv:2008.02818 [quant-ph] .
  * Rubino  _et al._ [2021b] G. Rubino, L. A. Rozema, D. Ebler, H. Kristjánsson, S. Salek, P. Allard Guérin, A. A. Abbott, C. Branciard, Č. Brukner, G. Chiribella, and P. Walther, Experimental quantum communication enhancement by superposing trajectories, Phys. Rev. Research 3, 013093 (2021b), arXiv:2007.05005 [quant-ph] .
  * Wechs  _et al._ [2021] J. Wechs, H. Dourdent, A. A. Abbott, and C. Branciard, Quantum circuits with classical versus quantum control of causal order, PRX Quantum 2, 030335 (2021), arXiv:2101.08796 [quant-ph] .
  * Helstrom [1967] C. W. Helstrom, Minimum mean-squared error of estimates in quantum statistics, Phys. Lett. A 25, 101 (1967).
  * Helstrom [1969] C. W. Helstrom, Quantum detection and estimation theory, J. Stat. Phys. 1, 231 (1969).
  * Paris [2009] M. G. Paris, Quantum estimation for quantum technology, Int. J. Quantum Inf. 7, 125 (2009), arXiv:0804.2981 [quant-ph] .
  * Fujiwara and Imai [2008] A. Fujiwara and H. Imai, A fibre bundle over manifolds of quantum channels and its application to quantum statistics, J. Phys. A: Math. Theor. 41, 255304 (2008).
  * Huang  _et al._ [2016] Z. Huang, C. Macchiavello, and L. Maccone, Usefulness of entanglement-assisted quantum metrology, Phys. Rev. A 94, 012101 (2016), arXiv:1603.03993 [quant-ph] .
  * Fujiwara [2001] A. Fujiwara, Quantum channel identification problem, Phys. Rev. A 63, 042304 (2001).
  * Fujiwara [2004] A. Fujiwara, Estimation of a generalized amplitude-damping channel, Phys. Rev. A 70, 012317 (2004).
  * Araújo  _et al._ [2017] M. Araújo, A. Feix, M. Navascués, and Č. Brukner, A purification postulate for quantum mechanics with indefinite causal order, Quantum 1, 10 (2017), arXiv:1611.08535 [quant-ph] .
  * Choi [1975] M.-D. Choi, Completely positive linear maps on complex matrices, Linear Algebra Appl. 10, 285 (1975).
  * Chiribella  _et al._ [2008] G. Chiribella, G. M. D’Ariano, and P. Perinotti, Quantum circuit architecture, Phys. Rev. Lett. 101, 060401 (2008), arXiv:0712.1325 [quant-ph] .
  * Chiribella  _et al._ [2009] G. Chiribella, G. M. D’Ariano, and P. Perinotti, Theoretical framework for quantum networks, Phys. Rev. A 80, 022339 (2009), arXiv:0904.4483 [quant-ph] .
  * Araújo  _et al._ [2014] M. Araújo, F. Costa, and Č. Brukner, Computational advantage from quantum-controlled ordering of gates, Phys. Rev. Lett. 113, 250402 (2014), arXiv:1401.8127 [quant-ph] .
  * Chiribella and Ebler [2016] G. Chiribella and D. Ebler, Optimal quantum networks and one-shot entropies, New J. Phys. 18, 093053 (2016), arXiv:1606.02394 [quant-ph] .
  * Fan [1953] K. Fan, Minimax theorems, Proc. Natl. Acad. Sci. USA 39, 42 (1953).
  * Gutoski and Watrous [2007] G. Gutoski and J. Watrous, Toward a general theory of quantum games, in  _Proceedings of the 39th Annual ACM Symposium on Theory of Computing_, STOC ’07 (2007) pp. 565–574, arXiv:quant-ph/0611234 .
  * Wechs  _et al._ [2019] J. Wechs, A. A. Abbott, and C. Branciard, On the definition and characterisation of multipartite causal (non)separability, New J. Phys. 21, 013027 (2019), arXiv:1807.10557 [quant-ph] .
  * Purves and Short [2021] T. Purves and A. J. Short, Quantum theory cannot violate a causal inequality, Phys. Rev. Lett. 127, 110402 (2021), arXiv:2101.09107 [quant-ph] .
  * Fujiwara and Imai [2003] A. Fujiwara and H. Imai, Quantum parameter estimation of a generalized Pauli channel, J. Phys. A: Math. Gen. 36, 8093 (2003).
  * Johnston  _et al._ [2016] N. Johnston, A. Cosentino, and V. Russo, QETLAB: QETLAB v0.9, Zenodo (2016).
  * Abbott  _et al._ [2023] A. A. Abbott, M. Mhalla, and P. Pocreau, Quantum query complexity of Boolean functions under indefinite causal order, arXiv:2307.10285 [quant-ph] (2023).
  * [56] R. Mothe, M. Grothus, A. A. Abbott, and C. Branciard, On correlations and quantum processes with dynamical causal orders, in preparation.
  * Hughston  _et al._ [1993] L. P. Hughston, R. Jozsa, and W. K. Wootters, A complete classification of quantum ensembles having a given density matrix, Phys. Lett. A 183, 14 (1993).
  * Watrous [2018] J. Watrous,  _The theory of quantum information_ (Cambridge university press, 2018).
  * Horn and Zhang [2005] R. A. Horn and F. Zhang, Basic properties of the Schur complement, in  _The Schur Complement and Its Applications_, edited by F. Zhang (Springer US, 2005).


# Local rules for fabricating allosteric networks

Nidhi Pashine<EMAIL_ADDRESS>Department of Physics, The University of
Chicago, Chicago IL, 60637, USA

###### Abstract

Mechanical properties of disordered networks can be significantly tailored by
modifying a small fraction of their bonds. This procedure has been used to
design and build mechanical metamaterials with a variety of responses. A long-
range ‘allosteric’ response, where a localized input strain at one site gives
rise to a localized output strain at a distant site, has been of particular
interest. This work presents a novel approach to incorporating allosteric
responses in experimental systems by pruning disordered networks in-situ.
Previous work has relied on computer simulations to design and predict the
response of such systems using a cost function where the response of the
entire network to each bond removal is used at each step to determine which
bond to prune. It is not feasible to follow such a design protocol in
experiments where one has access only to local response at each site. This
paper presents design algorithms that allow determination of what bonds to
prune based purely on the local stresses in the network without employing a
cost function; using only local information, allosteric networks are designed
in simulations and then built out of real materials. The results show that
some pruning strategies work better than others when translated into an
experimental system. A method is presented to measure local stresses
experimentally in disordered networks. This approach is then used to implement
pruning methods to design desired responses in-situ. Results from these
experiments confirm that the pruning methods are robust and work in a real
laboratory material.

##  I Introduction

Recent advances in the field of mechanical metamaterials have shown that
disordered networks are extremely tunable so that their mechanical response
can be altered dramatically by modifying a small number of edges or bonds
between nodes. This can be demonstrated in the Poisson’s ratio, $\nu$, which
is the negative of the ratio of the strain along the transverse axes to an
applied strain along a given axis. In an isotropic network material in $d$
dimensions, $\nu$ can be varied between the two theoretical limits, $\nu=-1$
(auxetic) and $\nu=+1/(d-1)$ (incompressible), by selectively removing a small
fraction of the network bonds goodrich2015principle ; hexner2018a ;
hexner2018b .

A more general property that can be incorporated into a disordered network is
a long-distance response, where applying an input strain at a local site in
the system creates an output strain at another distant localized site
rocks2017designing ; yan2017architecture ; tlusty2017 . This is referred to as
a mechanical ‘allosteric’ response because it is inspired by the property of
allostery in protein molecules.

Both allosteric and auxetic responses have been successfully designed and
incorporated into physical networks by pruning selected bonds
rocks2017designing ; reid2018auxetic . An important difference between auxetic
and allosteric response is that the Poisson’s ratio is a monotonic function of
the ratio of the shear, $G$, and bulk, $B$, moduli of a material. In a
disordered system, once contributions of every bond to the bulk and shear
moduli are known, it is straightforward to change its Poisson’s ratio by
pruning specific bonds.

On the other hand, in earlier works, allosteric systems have been designed by
removing bonds from a disordered network using a cost function. This protocol
succeeds well for designing materials with multiple targets controlled by a
single source using computer simulations rocks2017designing ; rocks2019 . A
cost function calculates the global response of the system due to the removal
of each bond individually in the network in order to decide what bonds need to
be pruned to minimize the difference from a desired response. Such a cost
function is difficult to interpret or quantify in terms of simple local
properties of the individual bonds in the network. This makes it difficult to
create such behavior in a network in situ so that the result can be achieved
without recourse to prior design on a computer.

This paper takes an alternate approach for designing a pruning protocol; the
aim is to use only local information encoded in the stresses on each bond due
to an externally applied strain. This would allow the creation of allosteric
responses in spring-network simulations by using only local information before
a bond is removed. This approach is a generalization of the one used to
incorporate auxetic response into networks goodrich2015principle . In that
case, the pruning was based on the local stresses in the bonds due to an
externally applied strain. In the case of allostery, the procedure is extended
to include the response to a set of separate, individually applied, strains
which are then combined. The results are then tested and validated in
experiments; I take the networks that were designed in simulations and build
them out of rubber sheets.

One problem encountered in using simulated networks to prune real materials is
that the simulations used, which have been of disordered central-spring
networks derived from jammed packings of spheres liu2010jamming , are overly
simplified models of the real materials. A physical system is more complicated
than such a spring network because it has forces other than those derived from
harmonic central-spring interactions. To circumvent this problem, I present an
experimental approach to measure the relative magnitude of stresses in
networks under any external strain and use it to prune the network systems in-
situ. This is done using photoelastic networks that are observed between pairs
of cross-polarizers. In this approach, no simulations are necessary for
determining which bonds to prune.

I find that experimental networks that are designed in simulations have a
drastically different response than ones that are pruned in-situ using
photoelastic stress measurements. In addition, the different local pruning
methods can produce different results in experiments even when they are
designed to give the same response in simulations. Taken together, this work
improves the understanding of the mechanisms that control allostery in
mechanical systems and opens up possibilities of building new and interesting
mechanical responses in real materials.

##  II Theoretical Approach

The random disordered spring networks are created in two dimensions, $2D$,
with periodic boundary conditions. These networks are derived from $2D$ jammed
packings of soft discs which are under force balance liu2010jamming ;
vanHecke_2015 ; Ohern . Each point of contact between the discs is replaced by
a harmonic spring that connects the centers of the two discs. The equilibrium
length of each spring is chosen to be the distance between the centers of the
discs. This ensures that the resultant network of nodes connected by bonds is
under zero stress in its ground state. The network coordination number, which
is the average number of bonds coming out of a node, is denoted by $Z$. In
order for such a network to be rigid, it needs to have an average $Z\geq
Z_{c}$, the critical coordination number. In $d$ dimensions, and excluding
finite-size effects, $Z_{c}=2d$; the $2D$ networks used here have $Z>Z_{c}=4$.

In order to incorporate a long distance ‘allosteric’ response between two
distant sites within a network, two pairs of nodes are picked at random as the
source and target respectively. These are separated by typically half of the
system size. One such network is shown in Fig. 1(a). In order to have an
allosteric interaction, there should be an output strain, $\epsilon_{T}$, at
the target pair of nodes when an input strain, $\epsilon_{S}$, is applied
between the two source nodes. The ratio of output to input strains is
$\eta\equiv\frac{\epsilon_{T}}{\epsilon_{S}}$. The aim is to incorporate an
allosteric response, with a desired value of $\eta$ in the network by removing
specific bonds from the network using a local pruning rule that uses only
information that is available prior to the pruning itself.

The general idea is to apply strains at both the input and output sites (in
some cases simultaneously and sometimes separately) to discover which bonds
should be removed in order to produce a stress at the target when the source
is activated. One might be tempted simply to minimize the energy for a
specific mechanical behavior. That is, one might consider removing the bonds
that are under highest stress when both the source and target are
simultaneously put under the desired strains. This, however, would nearly
always fail because the dominant energy for the strained system is often just
due to the strains of the source and target irrespective of whether the source
and target are applied simultaneously. In case of designing an allosteric
response, the goal is not merely to lower the energy for the input and output
strains, but to create an interaction between the source and target sites.
Thus, the source and target sites must communicate with each other. In order
to achieve this, one needs to identify specifically the bonds that facilitate
and the ones that hinder this allosteric response. By identifying and pruning
the right set of bonds, it is possible to minimize the interaction energy (not
just the total energy of distortion) of the input and output strains.

We apply a deformation to our system, $\epsilon^{k}$. This $\epsilon^{k}$
could be a single strain applied between two points in the system or a
combination of strains applied at various locations. Due to this applied
strain $\epsilon^{k}$, each bond in the system experiences some stress. The
stress in bond $j$ that appears due to $\epsilon^{k}$ is $S_{j}^{k}$. For
example, $S_{j}^{source}$ is defined as the stress in bond $j$ as a result of
a the input strain applied at the $source$.

Since all the calculations below are in the linear-response regime,

$S_{j}^{-k}=-S_{j}^{k};~{}~{}S_{j}^{k+l}=S_{j}^{k}+S_{j}^{l}$

One can calculate the energies in all the bonds of the network under any
applied deformation: The energy, $U_{j}^{k}$, in bond $j$ when it is under a
stress $S_{j}^{k}$ is:

$U_{j}^{k}=\frac{1}{2}S_{j}^{k}\gamma_{j}^{k}$ (1)

where $\gamma_{j}^{k}$ is the strain of the bond $j$ under applied external
strain $\epsilon^{k}$. Since the total energy of the network is simply the sum
of the energies of all the individual springs, the total energy stored in the
network under an applied strain $\epsilon^{k}$ is $U^{k}=\sum_{j}U^{k}_{j}$.

The modulus $M^{k}$ for any given deformation $\epsilon^{k}$ is defined as
$U^{k}=\frac{1}{2}M^{k}(\epsilon^{k})^{2}$. It can be decomposed into the
contributions of each bond: $M^{k}=\sum_{j}M^{k}_{j}$. $M_{j}^{k}$ is related
to $S_{j}^{k}$ as follows:

$U^{k}_{j}=\frac{1}{2}M_{j}^{k}(\epsilon^{k})^{2}=\frac{1}{2}S_{j}^{k}\gamma_{j}^{k}$
(2)

For a linear spring, $S_{j}$ and $\gamma_{j}$ only differ by a factor of the
spring constant. This gives the following:

$M_{j}^{k}\propto(S^{k}_{j})^{2}$ (3)

$M^{k}_{j}$ is the contribution of bond $j$ to $M^{k}$, where $M^{k}$ is the
modulus for the deformation $\epsilon^{k}$. In section IV it will be shown
that $M_{j}^{k}$ is a quantity that can be measured experimentally. Moreover,
it is easier to measure $M_{j}^{k}$ than to measure $S_{j}^{k}$ or
$\gamma_{j}^{k}$. Since the goal is to be able to prune the networks in
experiments, the pruning protocols presented below will be based on
measurements of $M_{j}^{k}$.

Figure 1: (a) A sample network with adjacent nodes chosen to be source and
target sites. (b) Results from pruning in simulations. Success rate of pruning
networks as a function of $|\eta|$. Networks pruned to lower the effective
moduli $M^{eff}=M^{link}(M^{target})^{3}$ (blue circles) have the highest
success rate, followed by $M^{link}M^{target}$ (black triangles), with
$M^{link}$ (red squares) being the least effective way to prune. (c) Average
fraction of bonds pruned as a function of $|\eta|$ for each of the three
$M^{eff}$ (d) Performance of experimental networks that were designed in
simulations to have $\eta\approx 1$. Plot shows the fraction of networks with
a response higher than $\eta^{*}$ as a function of $\eta^{*}$.

### Pruning algorithm

In order to incorporate an allosteric response, it is not particularly
important how much energy is required to move the $source$ nodes apart as long
as it results in an effect of the correct sign and magnitude at the $target$
site. Therefore, it is of little importance what are the individual values of
($S_{j}^{source}$) and ($S_{j}^{target}$); the important quantity is the
product of the two, ($S_{j}^{source}$)($S_{j}^{target}$). This term identifies
which bonds are most relevant to both $source$ and $target$ and pruning the
bonds with the largest $(S_{j}^{source}S_{j}^{target})$ helps create an
interaction between the $source$ and $target$ sites.

Consider applying the input strain at $source$ and output strain at $target$.
This is represented as $S^{s+t}$.

$S_{j}^{s+t}=S_{j}^{source}+S_{j}^{target}.$ (4)

Similarly, applying the input strain at $source$ and the negative of output
strain at $target$ is represented by $S^{s-t}$.

$S_{j}^{s-t}=S_{j}^{source}-S_{j}^{target}.$ (5)

The moduli $M_{j}$ can be expressed in terms of $S_{j}$:

$M_{j}^{s+t}\propto(S_{j}^{s+t})^{2}=(S_{j}^{source}+S_{j}^{target})^{2}$ (6)
$M_{j}^{s-t}\propto(S_{j}^{source}-S_{j}^{target})^{2}$ (7)

and

$M_{j}^{link}\equiv
M_{j}^{s+t}-M_{j}^{s-t}=4(S_{j}^{source})(S_{j}^{target}).$ (8)

Note that taking the difference of the in-phase and out-of-phase terms
produces the product of stresses due to applied strain at source and target
sites. This term, $M^{link}$, links the effects of strains at both source and
target and can be either positive or negative. One pruning protocol that would
create an allosteric interaction between the source and target would be to
prune those bonds in the network that have a maximum value of $M^{link}$.

Because $M_{j}^{link}=(S_{j}^{source})(S_{j}^{target})$ is symmetric between
source and target, the source and the target have been treated on an equal
footing. If this were the only criterion for pruning bonds, then the effect on
the target by activating the source would be the same as the effect on the
source by activating the target. Thus, such a criterion would produce
$\eta\approx 1$.

However in many situations it might be preferable to have $\eta\neq 1$. For
example one might want to create a strain at the target that is twice as large
as the strain at the source (i.e., $\eta=2$). This would require that the
symmetry between source and target be broken so that, for example, the target
nodes are easier to move than the source nodes. One effective way to break the
symmetry,is to bias the modulus by giving more weight to $S_{j}^{target}$ than
to $S_{j}^{source}$. One way to do this is to prune the bond with maximum
value of $(M_{j}^{link})(M_{j}^{target})^{n}$ where $n>0$.

These combinations of moduli are referred to as the effective modulus,
$M^{eff}$. In the results presented in the next section below there are three
examples:

  1. 1.

$(M^{eff,0})=M^{link}$,

  2. 2.

$(M^{eff,1})=M^{link}M^{target}$,

  3. 3.

$(M^{eff,3})=M^{link}(M^{target})^{3}$.

Our pruning algorithm is as follows:

  1. 1.

Calculate $M_{j}^{eff}$ for each bond $j$ in the network;

  2. 2.

Remove the bond with the maximum value of $M_{j}^{eff}$;

  3. 3.

Calculate the new value of $\eta$;

  4. 4.

Repeat until the desired value of $\eta$ is obtained.

By using effective moduli as the underlying quantity that controls a network’s
behavior, it is possible to incorporate responses in disordered networks using
local rules alone. The rest of this paper explores the efficacy of this
pruning approach using spring network simulations followed by an experimental
method to measure $M^{eff}$ in order to incorporate allosteric responses in-
situ in physical systems.

##  III Simulation results

In order to check the efficacy of these algorithms, I simulate the response of
networks as the protocols are applied. The simulations can be performed on
networks with periodic boundaries as well as ones with free boundaries. A free
boundary network is created by cropping out a circular section from a periodic
network. This often produces dangling bonds or zero modes which are eliminated
by removing the relevant bonds and nodes from the edges of the cropped
network. Since open boundary networks are easier to build in experiments, I
use these networks to compare the response between simulations and
experiments.

The simulation results shown here are performed on networks that have periodic
boundaries with $\sim 500$ particles and $\sim 1080$ bonds. Unpruned networks
have $\eta\approx 0.0$ on average between randomly chosen source and target
sites. Networks are pruned until the desired value of $\eta$ is reached or
until the process fails due to the creation of a zero mode in the system. $50$
different networks are pruned for both positive and negative values of $\eta$.
The networks used in these simulations have an average $\Delta
Z=Z-Z_{c}\approx 0.32$. This corresponds to an excess of $\sim 7\%$ bonds more
than necessary to maintain rigidity.

The success rate of each of the pruning methods is shown in Fig. 1(b). As one
might expect, if we prune for higher $|\eta|$, the success rate decreases. It
is clear from this data that using just $M^{link}$ to prune a network is not
the best strategy because, due to the symmetry between source and target, one
can prune only to a maximum of $|\eta|\approx 1$. Even this response can be
achieved only about half the time.

Biasing $M^{eff}$ towards the target improves the effectiveness of pruning
significantly; using $M^{eff,3}=(M^{link})(M^{target})^{3}$ makes it possible
to reach $|\eta|>1000$. However, it is important to note that these
calculations are performed in the linear-response regime of the network. Such
a very large $|\eta|$ implies that the source strain must be extremely small
in order for the target strain to be $1000$ times the source strain and still
be in the linear regime. This makes it highly impractical to measure such a
response in a laboratory system.

Fig. 1(c) shows the average fraction of bonds that need to be pruned as a
function of $\eta$. We see that $100\%$ of the networks fail after an average
of $\sim 6\%$ bonds are removed. This is when nearly all the excess bonds
above the rigidity threshold have been removed; therefore removing any
subsequent bond has a high probability of creating a zero-energy mode.

### Efficiency in Experiments

It is known from previous studies that linear spring simulations do not
capture all the material details of a real network reid2018auxetic ;
reid2019auxetic . There are other interactions, such as angle bending forces,
that are present in a real material. In order to test how well our pruning
algorithms translate to real networks, we design 2D networks with open
boundaries using the three mentioned protocols and then fabricate them in
experiments.

We took networks with free boundaries ranging between 110 and 150 particles in
size and pruned each of them using our three protocols. We stopped pruning
either once the network has achieved $\eta>1$ or once a zero mode is produced
so that the pruning process failed. Since not all of our algorithms have a
$100\%$ success rate, we chose 10 networks that could be pruned successfully
using the three effective moduli, $(M^{eff,0})$, $(M^{eff,1})$, and
$(M^{eff,3})$. For consistency, in all three cases the same set of source and
target nodes are used. For any given starting network, each protocol removes a
different set of bonds. I then laser cut 30 realizations of these networks (10
networks $\times$ 3 algorithms) and measured their responses in experiments.

Our networks were lasercut from $1.5mm$ thick sheets of silicone rubber with a
hardness of shore A70. The bonds were made thinner near the nodes to minimize
angle-bending interactions in the networks as was done in previous work
rocks2017designing . The ratio of the width of a bond to its average length is
1:6 with the bonds being half as wide near the nodes.

In order to measure the observed $\eta$ of these lasercut networks, an input
strain of $5\%$ is applied at the source and the output strain is measured at
the target site. Figure 1(d) shows the response of these networks. Since each
designed network has a slightly different value of $\eta$, we normalize our
experimental results, $\eta_{exp}$ by the value of $\eta$ produced in the
simulation, $\eta_{sim}$: $\eta^{*}={\eta_{exp}}/{\eta_{sim}}$ and plot it
along the abscissa. The ordinate shows the fraction of networks whose response
exceeds a given $\eta^{*}$. If our simulations were a perfect model for the
experimental systems, then the data in Fig. 1(d) would have been a horizontal
line at $1.0$.

This data is surprising because some algorithms have much better agreement
between experiments and simulations than others. Interestingly, Fig. 1(b)
shows that pruning with $M^{eff,0}=M^{link}$ works only about $50\%$ of the
time but when these networks are translated to experiments, they have a very
high success rate. On the other hand, $M^{eff,3}=M^{link}(M^{target})^{3}$
works very well in simulations but not in experiments. This suggests that the
disparity between experiments and simulations increases as the complexity of
the pruning algorithm increases. I hypothesize that the inclusion of
$(M^{target})^{n}$, increases the effect of the non-linear terms so that the
predictions from simulation are farther from our experimental results.

##  IV Pruning in-situ

Our results show that linear spring models do not work perfectly for designing
real materials. In order to see what is going on in the laboratory material,
we need a way to measure the stresses in a physical network. This section
presents experiments to measure the stress distribution in physical networks
and use that information to prune the networks in-situ.

### Setup

Figure 2: (a) Setup for visualizing stresses in photoelastic networks (b)
Sample image when the network has no external strain (c) Image of the same
network as in (b) with applied strains between adjacent node pairs circled in
yellow.

The stresses in a transparent material can be quantitatively detected by
measuring stress-induced birefringence hecht2002optics . The linear
polarization of a beam of light will not be affected as it passes through an
isotropic material; an analyzing polarizer with perpendicular orientation on
the exiting side of the material will block all the light. A photographic
image would be completely dark. However, if there are stresses in the
photoelastic material, the polarization axis of the light will be rotated
depending on the orientation of the stress with respect to the polarization
axis. The relative phase shift, $\Delta$ between two principal directions is
proportional to the difference in the two principal stresses hecht2002optics .

$\Delta\propto S_{1}-S_{2}$ (9)

If the stresses are small enough so that the rotation angle is small, the
analyzing polarizer will transmit the light in proportion to the stress. A
photographic image will be bright in those regions where the stress is large
and completely dark where there is no net stress.

Using circularly polarized light allows the magnitude of the stress to be
measured regardless of its orientation. The drawback of using circular
polarization is that circular polarizers are sensitive to the wavelength of
the light. Thus monochromatic light must be used.

In the experimental measurements of stresses reported here, the disordered
networks are made out of molded urethane rubber (Smooth-on Clear Flex™ 50)
with a shore hardness of A50. This material is highly sensitive to stresses
and allows measurement of stresses in the range of
$4$\mathrm{kPa}$-20$\mathrm{kPa}$$ in the current setup. The liquid urethane
material is poured into molds in the shape of the desired networks. The molds
are 3D printed in a soft rubber material with a shore hardness of A28. Before
each use, the molds were coated with a release agent (EaseRelease™ 200) to
ensure that the molded urethane networks are easy to remove from the molds.
The networks were cured in the mold at room temperature for a duration of 12
hours. After removal from the mold, they were cured for an additional 2-3 days
at room temperature to reduce the tackiness of the surfaces of the molded
networks.

A schematic of the experimental setup is shown in Fig. 2(a). Data is collected
by the camera at wavelength $\lambda=500\pm 10nm$. The initially unpolarized
white light is first polarized using a linear polarizer and then converted to
circular polarization using a quarter-wave plate for $\lambda=500nm$. The
light then passes through the sample. On the other side of the sample, another
quarter-wave plate converts the light back to linearly polarized light
followed by a linear polarizer that is oriented perpendicular to the
polarization of the initial light. The total stress at each point in the
material can be measured by the intensity of the light in the photographic
image.

Even after letting the molded photoelastic networks cure for a few days, their
surfaces are still tacky enough to stick to a glass or acrylic surface. This
produces extraneous stresses in the material that are unrelated to those
caused simply by placing strains at the source or target nodes. Additionally,
because of a high surface tension of the molding liquid, the top surface of
the network has a meniscus so that it is not completely flat. As a result, a
ray of light going through such a curved surface is reflected and refracted in
various directions and gives rise to unwanted signals in our data.

Both of these problems can be eliminated by submerging the networks in an
index-matched fluid. I used mineral oil with a refractive index of $1.47$,
which is very close to the refractive index of the photoelastic networks which
is $1.48$. Sample images from this setup with and without an applied strain
are shown in Fig. 2(b) and (c) respectively. The image in Fig. 2(b) shows that
when the network is under no stress, the image of the network in the camera is
dark and nearly undetectable. When an external strain is applied to the
network as shown in Fig. 2(c), different bonds in the network are stressed by
different amounts as a reaction to the input strain. These stressed regions
now appear as bright spots in our image.

The intensity of light, $I(x,y)$ at any point in the material $(x,y)$ is
related to the electric field, $E(x,y)$, and the phase shift, $\Delta(x,y)$:

$I(x,y)\propto E(x,y)^{2}\propto\sin(\Delta(x,y))^{2}\propto\sin(S(x,y))^{2}.$
(10)

As long as the input strain is sufficiently small, the resultant stresses are
in the regime where $\sin(S)\approx S$. In this limit, the brightness of a
bond is proportional to the square of stress. Hence, the intensity $I$
averaged over the length of bond $j$ is proportional to $M_{j}$ in Eq. 3.

### Experimental Results

Figure 3: Success rate of networks pruned in-situ as a function of $\eta$.
Following the same trend as the simulations, networks pruned to lower the
effective moduli $M^{eff}=M^{link}(M^{target})^{3}$ (blue circles) have the
highest success rate, followed by $M^{eff}=M^{link}M^{target}$ (black
triangles), and $M^{eff}=M^{link}$ (red squares).

I conduct the in-situ pruning experiments on photoelastic networks that are
between $110$ and $150$ nodes in size. The photoelastic networks are molded to
be 5mm thick with an average bond length of 12mm. The ratio of the width of a
bond to its average length is $1:4$ with the bonds being a third as wide near
the nodes than in their middle. This slight difference in geometry makes the
middle part of the bonds wider than in the experiments described above that
pruned bonds according to the algorithm based on simulation results. It
ensures that the effect of noise from the edges of photoelastic bonds is
minimized. In order to measure the response of these pruned networks, I remake
them in silicone rubber using the same specifications as in section III. This
is done to avoid any differences arising from the material properties while
comparing the response of designed and experimentally pruned networks.

In order to prune these networks, I take images where a strain is applied (i)
at the source and target in phase $(M^{s+t})$, (ii) out of phase $(M^{s-t})$,
and (iii) only at the target site $(M^{target})$. By computing combinations of
these images, I obtain a measure of the same three effective moduli as defined
in section II: $M^{eff}=M^{link}$, $M^{eff}=M^{link}M^{target}$, and
$M^{eff}=M^{link}(M^{target})^{3}$. The experiments were conducted on $10$
different networks for each $M^{eff}$. In each pruning step, I first calculate
$M^{eff}$ for all the bonds, remove the bond with maximum $M^{eff}$, and then
measure $\eta$ of the pruned network. As the bonds are pruned sequentially,
the signal-to-noise ratio drops steadily; when the signal is too low to be
reliable, the pruning is halted. The recorded $\eta$ for a particular sample
is the maximum $\eta$ that the network exhibits at any point during the
pruning process.

The results from in-situ pruning experiments are shown in Fig. 3. To some
extent, all pruning methods show an allosteric response. In particular, by
sequentially removing the bond with the largest value of
$M^{eff,3}=M^{link}(M^{target})^{3}$ at each step, networks can often be
successfully pruned to produce $\eta=1$. The three different pruning methods
have very different success rates. This was also seen in the simulation
results shown in Fig. 1(b). The results from the experiments and from the
simulations follow the same trend.

The same network design pruned to minimize the same $M^{eff}$ leads to the
removal of very different sets of bonds in simulations versus those pruned in
the photoelastic experiments. This is not surprising since the simulations
only considered central, harmonic springs, whereas the experiments had all the
interactions inherent in an elastic sheet such as angle-bending forces at each
node and non-linear stress/strain curves for all the bonds. However, it is
surprising that, compared to the experimental results shown in Fig. 1(d), the
trend for networks pruned in-situ is completely reversed. This suggests that
the simulation models are too simple to capture all the stresses in a real
material.

These results reinforce the conclusion that in order to make a physical system
with an allosteric response, a simplified model is not sufficient and it is
important to visualize and measure all the interactions in the system. Using
an experimental procedure to detect the stresses in physical networks, it is
possible to create allosteric networks in experiments with a high success
rate.

##  V Conclusions

The emphasis of this work has been to understand the local pruning rules that
control allosteric response in mechanical networks as well as to fabricate
these networks in real (physical) experimental systems. In order to create a
robust response, it is important to identify the relevant parameters that
govern allosteric behavior. The effective moduli introduced here are the bond-
level contributions to allostery. The simulations show that this approach is
very effective at designing allosteric responses with minimal computational
cost. In some cases, the results of these simulations can be directly
translated into experimental realizations. These local pruning rules are more
efficient than previous methods for incorporating allosteric behavior into
experimental systems rocks2017designing . Similar local pruning rules can also
be used to create more general responses such as multiple pairs of allosteric
source and target sites, or a single source site controlling multiple target
sites. As expected, when the complexity of the incorporated response
increases, the efficiency of such pruning algorithms goes down.

As expected, however, the simulations of networks connected by linear,
central-force springs do not capture all the details of a real material. In
order to create allosteric responses efficiently in experiments, it is
necessary to be able to measure stress distributions in the physical networks.
I have presented an experimental procedure to visualize and measure the
stresses in these systems and use them to prune the appropriate bonds in the
networks in-situ to achieve a desired response.

The experimental technique to measure local stresses provides a pathway for
modifying physical systems with more complex interactions. It would be
interesting to see if it can be used to create other mechanical responses,
such as auxetic behavior. This protocol can also be applied to other
disordered systems that are not based on spring networks. The pruning methods
explored here could be extended to 3D systems and to smaller length scales by
using stimuli responsive materials that can detect stresses in polymers at the
molecular level chen2020force ; deneke2020engineer .

Recent work has shown that stress-induced aging can be used to modify material
properties pashine2019directed . An externally imposed strain can direct the
evolution of a material and determine its mechanical response. Our
understanding of local pruning rules that control allostery in combination
with directed aging protocols can be very useful in designing allosteric
systems while eliminating the need to manipulate the material manually at the
microscopic level. Local learning rules, such as the ones presented here, are
also of interest in supervised learning of elastic and flow networks
stern2020supervised

In conclusion, local pruning rules that allow the manipulation of material
response combined with the ability to measure stress distributions in-situ,
enable the modification of materials that are more complex than the linear
spring networks that have been the focus of previous simulation studies. This
approach opens up novel ways to build mechanical metamaterials with a desired
function without relying on computer simulations.

##  VI Acknowledgements

I would like to thank Daniel Hexner, Andrea J. Liu, and Nachi Stern for
insightful discussions. I am deeply grateful to Sidney R. Nagel for his
advising and mentoring. I would also like to thank Cacey Stevens Bester for
information regarding photoelastic materials, and Robert Morton for help with
3D printing. This work was supported by the NSF MRSEC Program DMR-2011854 (for
experimental studies), the US Department of Energy, Office of Science, Basic
Energy Sciences, under Grant DE-SC0020972 (for theoretical model development)
and by the Simons Foundation for the collaboration “Cracking the Glass
Problem” Award 348125 (for simulations).

## References

  * [1] Carl P Goodrich, Andrea J Liu, and Sidney R Nagel.  The principle of independent bond-level response: Tuning by pruning to exploit disorder for global behavior.  Physical review letters, 114(22):225501, 2015.
  * [2] Daniel Hexner, Andrea J Liu, and Sidney R Nagel.  Role of local response in manipulating the elastic properties of disordered solids by bond removal.  Soft Matter, 14:312–318, 2018.
  * [3] Daniel Hexner, Andrea J Liu, and Sidney R Nagel.  Linking microscopic and macroscopic response in disordered solids.  Phys.. Rev. E, 97:063001, 2018.
  * [4] Jason W Rocks, Nidhi Pashine, Irmgard Bischofberger, Carl P Goodrich, Andrea J Liu, and Sidney R Nagel.  Designing allostery-inspired response in mechanical networks.  Proceedings of the National Academy of Sciences, 114(10):2520–2525, 2017.
  * [5] Le Yan, Riccardo Ravasio, Carolina Brito, and Matthieu Wyart.  Architecture and coevolution of allosteric materials.  Proceedings of the National Academy of Sciences, 114(10):2526–2531, 2017.
  * [6] Tsvi Tlusty, Albert Libchaber, and Jean-Pierre Eckmann.  Physical model of the genotype-to-phenotype map of proteins.  Phys.Rev. X, 7:021037, 2017.
  * [7] Daniel R Reid, Nidhi Pashine, Justin M Wozniak, Heinrich M Jaeger, Andrea J Liu, Sidney R Nagel, and Juan J de Pablo.  Auxetic metamaterials from disordered networks.  Proceedings of the National Academy of Sciences, 115(7):E1384–E1390, 2018.
  * [8] Jason W Rocks, Henrik Ronellenfitsch, Andrea J Liu, Sidney R Nagel, and Eleni Katifori.  Limits of multifunctionality in tunable networks.  Proceedings of the National Academy of Sciences, 116(7):2506–2511, 2019.
  * [9] Andrea J Liu and Sidney R Nagel.  The jamming transition and the marginally jammed solid.  Annu. Rev. Condens. Matter Phys., 1(1):347–369, 2010.
  * [10] Wouter G. Ellenbroek, Varda F. Hagh, Avishek Kumar, M. F. Thorpe, and Martin van Hecke.  Rigidity loss in disordered systems: Three scenarios.  Phys. Rev. Lett., 114:135501, 2015.
  * [11] Corey S. O’Hern, Leonardo E. Silbert, Andrea J. Liu, and Sidney R. Nagel.  Jamming at zero temperature and zero applied stress: The epitome of disorder.  Phys. Rev. E, 68:011306, 2003.
  * [12] Daniel R Reid, Nidhi Pashine, Alec S Bowen, Sidney R Nagel, and Juan J de Pablo.  Ideal isotropic auxetic networks from random networks.  Soft Matter, 15:8084–8091, 2019.
  * [13] Eugene Hecht.  Optics, 4e.  Addison-Wesley, 2002.
  * [14] Yinjun Chen, C Joshua Yeh, Yuan Qi, Rong Long, and Costantino Creton.  From force-responsive molecules to quantifying and mapping stresses in soft materials.  Science Advances, 6(20):eaaz5093, 2020.
  * [15] Naomi Deneke, Mitchell L Rencheck, and Chelsea Simone Davis.  An engineer’s introduction to mechanophores.  Soft Matter, 2020.
  * [16] Nidhi Pashine, Daniel Hexner, Andrea J Liu, and Sidney R Nagel.  Directed aging, memory, and nature’s greed.  Science advances, 5(12):eaax4215, 2019.
  * [17] Menachem Stern, Daniel Hexner, Jason W Rocks, and Andrea J Liu.  Supervised learning in physical networks: From machine learning to learning machines.  arXiv preprint arXiv:2011.03861, 2020.