Now fix a time partition with large $N$, by the second line of (6.7), we see
that

$\displaystyle\int_{0}^{T}\eta_{t}\widetilde{\cal
Y}(dt,0)\approx\sum_{i=0}^{N-1}\big{[}\widetilde{\cal
Y}(t_{i+1},0)-\widetilde{\cal
Y}(t_{i},0)\big{]}\eta_{t_{i}}=\sum_{i=0}^{N-1}\mathbb{E}\Big{[}\big{[}{\cal
Y}_{t_{i+1}}-{\cal Y}_{t_{i}}\big{]}\eta_{t_{i}}\Big{]}$
$\displaystyle\quad=\sum_{i=0}^{N-1}\mathbb{E}\Big{[}\big{[}{\cal
Y}_{t_{i+1}}-{\cal Y}_{t_{i}}\big{]}\big{[}{\cal
X}_{t_{i}}-\int_{0}^{t_{i}}\int_{0}^{s}{\cal
X}_{r}~{}\check{b}(t_{i},s,dr)ds-\int_{0}^{t_{i}}\int_{0}^{s}{\cal
X}_{r}~{}\check{\sigma}(t_{i},s,dr)dW_{s}\big{]}\Big{]}$
$\displaystyle\quad=\sum_{i=0}^{N-1}\mathbb{E}\Big{[}\big{[}{\cal
Y}_{t_{i+1}}-{\cal Y}_{t_{i}}\big{]}{\cal X}_{t_{i}}-\big{[}{\cal
Y}(t_{i+1},t_{i})-{\cal Y}(t_{i},t_{i})\big{]}$
$\displaystyle\qquad\qquad\quad\times\big{[}\int_{0}^{t_{i}}\int_{0}^{s}{\cal
X}_{r}~{}\check{b}(t_{i},s,dr)ds+\int_{0}^{t_{i}}\int_{0}^{s}{\cal
X}_{r}~{}\check{\sigma}(t_{i},s,dr)dW_{s}\big{]}\Big{]}$
$\displaystyle\quad=\sum_{i=0}^{N-1}\mathbb{E}\Big{[}\big{[}{\cal
Y}_{t_{i+1}}-{\cal Y}_{t_{i}}\big{]}{\cal
X}_{t_{i}}-\int_{0}^{t_{i}}\big{[}\widetilde{\cal
Y}(t_{i+1},s)-\widetilde{\cal Y}(t_{i},s)\big{]}\big{[}\int_{0}^{s}{\cal
X}_{r}~{}\check{b}(t_{i},s,dr)\big{]}ds$
$\displaystyle\quad\qquad\qquad-\int_{0}^{t_{i}}\big{[}{\cal
Z}(t_{i+1},s)-{\cal Z}(t_{i},s)\big{]}\big{[}\int_{0}^{s}{\cal
X}_{r}~{}\check{\sigma}(t_{i},s,dr)\big{]}ds\Big{]}$
$\displaystyle\quad\approx\sum_{k=0}^{N-1}\mathbb{E}\Big{[}\big{[}{\cal
Y}_{t_{k+1}}-{\cal Y}_{t_{k}}\big{]}{\cal X}_{t_{k}}\Big{]}-{T\over
n}\sum_{0\leqslant k<j<i\leqslant N-1}\Big{[}\big{[}\widetilde{\cal
Y}(t_{i+1},t_{j})-\widetilde{\cal Y}(t_{i},t_{j})\big{]}$
$\displaystyle\quad\quad\times\big{[}\check{b}(t_{i},t_{j},t_{k+1})-\check{b}(t_{i},t_{j},t_{k})\big{]}+\big{[}{\cal
Z}(t_{i+1},t_{j})-{\cal
Z}(t_{i},t_{j})\big{]}\big{[}\check{\sigma}(t_{i},t_{j},t_{k+1})-\check{\sigma}(t_{i},t_{j},t_{k})\big{]}\Big{]}{\cal
X}_{t_{k}}.$

Here and in the sequel, we are using $\approx$ to denote a difference of
$o(1)$ term when $N\to\infty$. Then

(6.8)
$\left.\begin{array}[]{lll}\displaystyle\int_{0}^{T}\eta_{t}\widetilde{\cal
Y}(dt,0)-\mathbb{E}\Big{[}\int_{0}^{T}{\cal X}_{t}\check{g}(dt)\Big{]}\\\
\displaystyle\quad\approx\int_{0}^{T}\eta_{t}\widetilde{\cal
Y}(dt,0)-\sum_{k=0}^{N-1}\mathbb{E}\Big{[}\big{[}\check{g}(t_{k+1})-\check{g}(t_{k})\big{]}{\cal
X}_{t_{k}}\Big{]}\approx\sum_{k=0}^{N-1}\mathbb{E}\big{[}{\cal
X}_{t_{k}}I_{k}\big{]},\end{array}\right.$

where, for each $k$,

$\displaystyle I_{k}$ $\displaystyle:=$ $\displaystyle\int_{t_{k}\leqslant
l\leqslant s\leqslant r\leqslant T}\Big{[}\check{b}(r,s,dl)\widetilde{\cal
Y}(dr,s)+\check{\sigma}(r,s,dl){\cal Z}(dr,s)\Big{]}ds$
$\displaystyle-\int_{t_{k+1}\leqslant l\leqslant s\leqslant r\leqslant
T}\Big{[}\check{b}(r,s,dl)\widetilde{\cal Y}(dr,s)+\check{\sigma}(r,s,dl){\cal
Z}(dr,s)\Big{]}ds$ $\displaystyle-{T\over n}\sum_{k<j<i\leqslant
N-1}\Big{[}\big{[}\check{b}(t_{i},t_{j},t_{k+1})-\check{b}(t_{i},t_{j},t_{k})\big{]}\big{[}\widetilde{\cal
Y}(t_{i+1},t_{j})-\widetilde{\cal Y}(t_{i},t_{j})\big{]}$
$\displaystyle\qquad+\big{[}\check{\sigma}(t_{i},t_{j},t_{k+1})-\check{\sigma}(t_{i},t_{j},t_{k})\big{]}\big{[}{\cal
Z}(t_{i+1},t_{j})-{\cal Z}(t_{i},t_{j})\big{]}\Big{]}.$

One may easily check that

$\displaystyle I_{k}$ $\displaystyle\approx$
$\displaystyle\int_{t_{k}\leqslant s\leqslant r\leqslant
T}\Big{[}\big{[}\check{b}(r,s,s)-\check{b}(r,s,t_{k})\big{]}\widetilde{\cal
Y}(dr,s)+\big{[}\check{\sigma}(r,s,s)-\check{\sigma}(r,s,t_{k})\big{]}{\cal
Z}(dr,s)\Big{]}ds$ $\displaystyle-\int_{t_{k+1}\leqslant s\leqslant r\leqslant
T}\Big{[}\big{[}\check{b}(r,s,s)-\check{b}(r,s,t_{k+1})\big{]}\widetilde{\cal
Y}(dr,s)+\big{[}\check{\sigma}(r,s,s)-\check{\sigma}(r,s,t_{k+1})\big{]}{\cal
Z}(dr,s)\Big{]}ds$ $\displaystyle-\int_{t_{k+1}\leqslant s\leqslant r\leqslant
T}\Big{[}\big{[}\check{b}(r,s,t_{k+1})-\check{b}(r,s,t_{k})\big{]}\widetilde{\cal
Y}(dr,s)+\big{[}\check{\sigma}(r,s,t_{k+1})-\check{\sigma}(r,s,t_{k})\big{]}{\cal
Z}(dr,s)\Big{]}ds$ $\displaystyle=$ $\displaystyle\int_{t_{k}\leqslant
s\leqslant r\leqslant
T}\Big{[}\big{[}\check{b}(r,s,s)-\check{b}(r,s,t_{k})\big{]}\widetilde{\cal
Y}(dr,s)+\big{[}\check{\sigma}(r,s,s)-\check{\sigma}(r,s,t_{k})\big{]}{\cal
Z}(dr,s)\Big{]}ds$ $\displaystyle-\int_{t_{k+1}\leqslant s\leqslant r\leqslant
T}\Big{[}\big{[}\check{b}(r,s,s)-\check{b}(r,s,t_{k})\big{]}\widetilde{\cal
Y}(dr,s)+\big{[}\check{\sigma}(r,s,s)-\check{\sigma}(r,s,t_{k})\big{]}{\cal
Z}(dr,s)\Big{]}ds$ $\displaystyle=$
$\displaystyle\int_{t_{k}}^{t_{k+1}}\int_{s}^{T}\Big{[}\big{[}\check{b}(r,s,s)-\check{b}(r,s,t_{k})\big{]}\widetilde{\cal
Y}(dr,s)+\big{[}\check{\sigma}(r,s,s)-\check{\sigma}(r,s,t_{k})\big{]}{\cal
Z}(dr,s)\Big{]}ds.$

Substituting the above into (6.8) implies that

(6.9) $\displaystyle\int_{0}^{T}\eta_{t}\widetilde{\cal
Y}(dt,0)-\mathbb{E}\Big{[}\int_{0}^{T}{\cal
X}_{t}\check{g}(dt)\Big{]}\approx\sum_{k=0}^{N-1}\mathbb{E}\Big{[}\int_{t_{k}}^{t_{k+1}}\int_{s}^{T}\Big{[}\big{[}\check{b}(r,s,s)-\check{b}(r,s,t_{k})\big{]}\widetilde{\cal
Y}(dr,s)$
$\displaystyle\quad\qquad+\big{[}\check{\sigma}(r,s,s)-\check{\sigma}(r,s,t_{k})\big{]}{\cal
Z}(dr,s)\Big{]}ds{\cal X}_{t_{k}}\Big{]}.$

Using the fact that the finite variated function is a.e continuous, we get

$\displaystyle\lim_{t_{k}\uparrow
s}\big{[}\check{b}(r,s,s)-\check{b}(r,s,t_{k})\big{]}=\lim_{t_{k}\uparrow
s}\big{[}\check{\sigma}(r,s,s)-\check{\sigma}(r,s,t_{k})\big{]}=0,\quad\mbox{for
a.e. $s$}.$

Then from (6.9) we see that (6.3) holds true by letting $N\to\infty$.

######  Remark 6.2.

In the state dependent case, the measures are degenerate:

$\displaystyle\check{b}(t,s,dr)=b(t,s)\delta_{s}(r),\quad\check{\sigma}(t,s,dr)=\sigma(t,s)\delta_{s}(r),\quad\check{g}(dr)=g(r)dr,$

with the Dirac measure $\delta$ being defined by

$\delta_{s}{\bf x}={\bf x}_{s},\quad s\in[0,T].~{}{\bf x}\in C([0,T]).$

Then (6.1) and (6.7) become

(6.10) $\left.\begin{array}[]{l}\displaystyle{\cal
X}_{t}=\eta_{t}+\int_{0}^{t}b(t,s){\cal X}_{s}ds+\int_{0}^{t}\sigma(t,s){\cal
X}_{s}dW_{s};\\\ \displaystyle{\cal
Y}_{t}=\check{g}(t)-\int_{t}^{T}\int_{s}^{T}\Big{[}b(r,s)\widetilde{\cal
Y}(dr,s)+\sigma(r,s){\cal Z}(dr,s)\Big{]}ds-\int_{t}^{T}{\cal
Z}(t,s)dW_{s};\\\ \displaystyle\widetilde{\cal Y}(t,s)={\cal
Y}_{t}-\int_{s}^{t}{\cal Z}(t,r)dW_{r},\quad 0\leqslant s\leqslant
t.\end{array}\right.$

Let $(Y,Z)$ denote the solution to the following type-II BSVIE:

(6.11) $\left.\begin{array}[]{l}\displaystyle
Y_{t}=g(t)+\int_{t}^{T}[b(s,t)Y_{s}+\sigma(s,t)Z(s,t)]ds-\int_{t}^{T}Z(t,s)dW_{s};\\\
\displaystyle
Y_{t}=\mathbb{E}[Y_{t}]+\int_{0}^{t}Z(t,s)dW_{s}.\end{array}\right.$

We can easily check that

$\displaystyle{\cal Y}_{t}={\cal
Y}_{0}+\int_{0}^{t}Y_{r}dr,\quad\widetilde{\cal Y}(t,s)={\cal
Y}_{s}+\int_{s}^{t}\mathbb{E}_{s}[Y_{r}]dr,\quad{\cal
Z}(t,s)=\int_{s}^{t}Z(r,s)dr,\quad 0\leqslant s\leqslant t\leqslant T$

satisfy the BSVIE in (6.10). Then (6.3) becomes

$\displaystyle\mathbb{E}\Big{[}\int_{0}^{T}g(t){\cal
X}_{t}dt\Big{]}=\mathbb{E}\Big{[}\int_{0}^{T}{\cal
X}_{t}\check{g}(dt)\Big{]}=\int_{0}^{T}\eta_{t}\widetilde{\cal
Y}(dt,0)=\int_{0}^{T}\eta_{t}\mathbb{E}[Y_{t}]dt=\mathbb{E}\Big{[}\int_{0}^{T}\eta_{t}Y_{t}dt\Big{]}.$

This is exactly the duality in Yong [69, 71]. So our result here is a
generalization of these works.

######  Remark 6.3.

Our result also generalizes the duality between delayed SDEs and anticipated
BSDEs in Peng–Yang [53]. Let $(X,Y,Z)$ denote the solution to the following
equations:

(6.12) $\left\\{\begin{array}[]{ll}\displaystyle
dX^{\xi}_{s}=(\mu_{s}X^{\xi}_{s}+\bar{\mu}_{s-\theta}X^{\xi}_{s-\theta})ds+(\sigma_{s}X^{\xi}_{s}+\sigma_{s-\theta}X^{\xi}_{s-\theta})dW_{s},\quad
s\in[t,T+\theta],\\\ \vskip 3.0pt plus 1.0pt minus 1.0pt\cr\displaystyle
X_{t}=\xi,\quad X_{s}=0,\quad s\in[t-\theta,t];\\\ \vskip 3.0pt plus 1.0pt
minus 1.0pt\cr\displaystyle-
dY_{s}=\big{(}\mu_{s}Y_{s}+\bar{\mu}_{s}\mathbb{E}_{s}[Y_{s+\theta}]+\sigma_{s}Z_{s}+\sigma_{s}\mathbb{E}_{s}[Z_{s+\theta}]+l_{s}\big{)}ds-
Z_{s}dW_{s},\quad s\in[t,T],\\\ \vskip 3.0pt plus 1.0pt minus
1.0pt\cr\displaystyle Y_{s}=Q_{s},~{}~{}Z_{s}=P_{s},\quad
s\in[T,T+\theta],\end{array}\right.$

where $\theta>0$ is a fixed delay time. From [53, Theorem 2.1] we get the
duality

(6.13) $\langle
Y_{t},\xi\rangle=\mathbb{E}_{t}\Big{[}X^{\xi}_{T}Q_{T}+\int_{t}^{T}X^{\xi}_{s}l_{s}ds+\int_{T}^{T+\theta}(Q_{s}\bar{\mu}_{s-\theta}+P_{s}\bar{\sigma}_{s-\theta})X^{\xi}_{s-\theta}ds\Big{]}:=\mathbb{E}_{t}\Big{[}\int_{t}^{T}X^{\xi}_{s}\check{g}(ds)\Big{]},$

which shows that $Y_{t}$ is an explicit representation of the linear
functional
$\xi\mapsto\mathbb{E}_{t}\big{[}\int_{t}^{T}X^{\xi}_{s}\check{g}(ds)\big{]}$.
Since FSVIE (6.1) is more general than the delayed SDE in (6.12), we can also
use Theorem 6.1 to give such an explicit representation for
$\xi\mapsto\mathbb{E}_{t}\big{[}\int_{t}^{T}X^{\xi}_{s}\check{g}(ds)\big{]}$.
Indeed, take

$\displaystyle\check{b}(s,dr)=\mu_{s}\delta_{s}(r)+\bar{\mu}_{s-\theta}\delta_{s-\theta}(r),\quad\check{\sigma}(s,dr)=\sigma(s)\delta_{s}(r)+\bar{\sigma}_{s-\theta}\delta_{s-\theta}(r),\quad
s\in[t+\theta,T],$
$\displaystyle\check{b}(s,dr)=\mu_{s}\delta_{s}(r),\quad\check{\sigma}(s,dr)=\sigma(s)\delta_{s}(r),\quad
s\in[t,t+\theta],$
$\displaystyle\check{g}(dr)=l(r)dr+\mathbb{E}_{r}[Q_{r+\theta}\bar{\mu}_{r}+P_{r+\theta}\bar{\sigma}_{r}]1_{[T-\theta,T]}(r)dr+Q(T)\delta_{T}(r).$

Note that $\check{b}(\tau,s,dr),\check{\sigma}(\tau,s,dr)$ are independent of
$\tau$, the corresponding BSVIE (6.7) reads

$\left.\begin{array}[]{c}\displaystyle{\cal
Y}_{\tau}=\check{g}(\tau)-\int_{\tau}^{T}\mu_{s}[\widetilde{\cal
Y}(T,s)-\widetilde{\cal
Y}(s,s)]ds-\int_{\tau+\theta}^{T}\bar{\mu}_{s-\theta}[\widetilde{\cal
Y}(T,s)-\widetilde{\cal Y}(s,s)]ds\\\
\displaystyle\qquad\qquad-\int_{\tau}^{T}\sigma_{s}[{\cal Z}(T,s)-{\cal
Z}_{s}]ds-\int_{\tau+\theta}^{T}\bar{\sigma}_{s-\theta}[{\cal Z}(T,s)-{\cal
Z}_{s}]ds-\int_{\tau}^{T}{\cal Z}_{s}dW_{s};\\\ \displaystyle\widetilde{\cal
Y}(\tau,s)={\cal Y}_{\tau}-\int_{s}^{\tau}{\cal Z}(\tau,r)dW_{r},\quad
0\leqslant s\leqslant\tau.\end{array}\right.$

Then it is easy to check

$\displaystyle Y_{t}={\cal Y}(T,t)-{\cal Y}_{t},\quad Z_{t}={\cal
Z}(T,t)-{\cal Z}_{t},$ $\displaystyle\langle{\cal Y}(T,t)-{\cal
Y}_{t},\,\xi\rangle=\langle
Y_{t},\,\xi\rangle=\mathbb{E}_{t}\Big{[}\int_{t}^{T}X^{\xi}_{s}\check{g}(ds)\Big{]}.$

Thus Theorem 6.1 covers the duality in [53].

######  Remark 6.4.

The duality (6.6) still holds true in the multidimensional case, where the
FSVIE (6.1) and type-II BSVIE (6.7) become

$\left.\begin{array}[]{l}\displaystyle{\cal
X}_{t}=\eta_{t}+\int_{0}^{t}\int_{0}^{s}{\cal
X}_{r}~{}\check{b}(t,s,dr)ds+\sum_{j=1}^{d}\int_{0}^{t}\int_{0}^{s}{\cal
X}_{r}~{}\check{\sigma}^{j}(t,s,dr)dW^{j}_{s};\\\ \displaystyle{\cal
Y}_{t}=\check{g}(t)-\int_{t\leqslant l\leqslant s\leqslant r\leqslant
T}\Big{[}\check{b}(r,s,dl)\widetilde{\cal
Y}(dr,s)+\sum_{j=1}^{d}\check{\sigma}^{j}(r,s,dl){\cal
Z}^{j}(dr,s)\Big{]}ds-\sum_{j=1}^{d}\int_{t}^{T}{\cal
Z}^{j}(t,s)dW_{s}^{j};\\\ \displaystyle\widetilde{\cal Y}(t,s)={\cal
Y}_{t}-\sum_{j=1}^{d}\int_{s}^{t}{\cal Z}^{j}(t,r)dW^{j}_{r},\quad 0\leqslant
s\leqslant t,\end{array}\right.$

with
$\check{b},\check{\sigma}^{j}:(t,s,r,\omega)\in\mathbb{T}_{-}^{3}\times\Omega\to\mathbb{R}^{n\times
n}$ and $\check{g}:\mathbb{T}\times\Omega\to\mathbb{R}^{m\times n}$ being
proper maps.

###  6.2 An explicit solution for linear BSVIEs

In this subsection we investigate the following linear BSVIE:

(6.14) ${\cal Y}_{t}=\xi_{t}+\int_{t}^{T}\big{[}\alpha(t,r){\cal
Y}_{r}+\beta(t,r){\cal Z}^{t}_{r}\big{]}dr-\int_{t}^{T}{\cal
Z}^{t}_{r}dW_{r},$

where $\xi:\mathbb{T}\times\Omega\to\mathbb{R}$,
$\alpha,\beta:\mathbb{T}_{+}^{2}\times\Omega\to\mathbb{R}$ are progressively
measurable (omitting the variable $\omega$).

######  Proposition 6.5.

Assume $\alpha,\beta$ are bounded and
$\sup_{t\in\mathbb{T}}\mathbb{E}[|\xi_{t}|^{2}]<\infty$. Then

(6.15) ${\cal
Y}_{t}=\mathbb{E}_{t}\Big{[}M^{t}_{T}\xi_{t}+\int_{t}^{T}\Gamma(t,r)M^{r}_{T}\xi_{r}dr\Big{]},$

where $M$ is the solution to the following SDE:

(6.16)
$dM^{t}_{r}=M^{t}_{r}\beta(t,r)dW_{r},~{}~{}(t,r)\in\mathbb{T}^{2}_{+};\quad
M_{t}^{t}=I_{m},$

and

(6.17)
$\Gamma(t,s):=\sum_{n=1}^{\infty}K_{n}(t,s),~{}~{}K_{1}(t,s):=M^{t}_{s}\alpha(t,s),~{}~{}K_{n+1}(t,s):=\int_{t}^{s}K_{1}(t,r)K_{n}(r,s)dr.$

###### Proof.

First, by Proposition 2.11 we see that (6.14) is wellposed. Next, since
$\alpha,\beta$ are bounded, it is clear that
$\mathbb{E}_{t}[|K_{1}(t,s)|^{2}]\leqslant C_{0}<\infty$. Note that

$\displaystyle\mathbb{E}_{t}[|K_{n+1}(t,s)|^{2}]\leqslant(s-t)\int_{t}^{s}\mathbb{E}_{t}\Big{[}|K_{1}(t,r)|^{2}\mathbb{E}_{r}[|K_{n}(r,s)|^{2}]\Big{]}dr.$

Then by induction one can easily show that

$\displaystyle\mathbb{E}_{t}[|K_{n+1}(t,s)|^{2}]\leqslant{C_{0}^{n+1}(s-t)^{2n}\over(2n-1)!!},\quad\mbox{and
thus}\quad\mathbb{E}_{t}[|\Gamma(t,s)|^{2}]\leqslant C<\infty.$

We now let $(\widetilde{\cal Y},\widetilde{\cal Z})$ satisfy the following
BSDE:

(6.18) $\widetilde{\cal Y}^{t}_{s}=\xi_{t}+\int_{s}^{T}\big{[}\alpha(t,r){\cal
Y}_{r}+\beta(t,r)\widetilde{\cal
Z}^{t}_{r}\big{]}dr-\int_{s}^{T}\widetilde{\cal Z}^{t}_{r}dW_{r}.$

Then

${\cal Y}_{t}=\widetilde{\cal Y}^{t}_{t},\quad{\cal Z}^{t}_{s}=\widetilde{\cal
Z}^{t}_{s}.$

Apply Itô formula to the mapping $s\mapsto M^{t}_{s}\widetilde{\cal
Y}^{t}_{s}$ on $[t,T]$, we get

(6.19) ${\cal Y}_{t}=\widetilde{\cal
Y}_{t}^{t}=\mathbb{E}_{t}\Big{[}M^{t}_{T}\xi_{t}+\int_{t}^{T}M^{t}_{s}\alpha(t,s){\cal
Y}_{s}ds\Big{]}.$

Moreover, note that

$\Gamma(t,s)=K_{1}(t,s)+\int_{t}^{s}K_{1}(t,r)\Gamma(r,s)dr.$

Then

$\displaystyle{\cal Y}_{t}$ $\displaystyle=$
$\displaystyle\mathbb{E}_{t}\Big{[}M^{t}_{T}\xi_{t}+\int_{t}^{T}K_{1}(t,s)\mathbb{E}_{s}\big{[}M^{s}_{T}\xi_{s}+\int_{s}^{T}\Gamma(s,r)M^{r}_{T}\xi_{r}dr\big{]}ds\Big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{t}\Big{[}M^{t}_{T}\xi_{t}+\int_{t}^{T}K_{1}(t,s)M^{s}_{T}\xi_{s}ds+\int_{t}^{T}K_{1}(t,s)\int_{s}^{T}\Gamma(s,r)M^{r}_{T}\xi_{r}drds\Big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{t}\Big{[}M^{t}_{T}\xi_{t}+\int_{t}^{T}K_{1}(t,s)M^{s}_{T}\xi_{s}ds+\int_{t}^{T}\int_{t}^{r}K_{1}(t,s)\Gamma(s,r)dsM^{r}_{T}\xi_{r}dr\Big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{t}\Big{[}M^{t}_{T}\xi_{t}+\int_{t}^{T}\big{[}K_{1}(t,s)+\int_{t}^{s}K_{1}(t,r)\Gamma(r,s)dr\big{]}M^{s}_{T}\xi_{s}ds\Big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{t}\Big{[}M^{t}_{T}\xi_{t}+\int_{t}^{T}\Gamma(t,s)M^{s}_{T}\xi_{s}ds\Big{]}={\cal
Y}_{t}.$

This implies that $({\cal Y},{\cal Z})$ satisfy (6.14). The result then
follows from the uniqueness of (6.14).

######  Remark 6.6.

The representation (6.15) of ${\cal Y}$ is exactly the so-called variation of
constants formula for linear BSVIEs. A similar result was first obtained by
Hu–Øksendal [36] for the linear BSVIEs driven by a Brownian motion and a
compensated Poisson random measure. However, in [36] the coefficients
$\alpha,\beta$ are assumed to be deterministic functions and
$\beta(t,r)\equiv\beta(r)$ is required to be independent of $t$. Thus our
result is a generalized version of [36, Theorem 3.1].

###  6.3 Representation of $\partial_{\bf x}U$

In this subsection we assume Assumption 3.3 holds true, and let $U$ be the
classical solution to PPDE (3.1), corresponding to the decoupled FBSVIE
(2.3)–(2.8). We shall use type-II BSVIE to provide an explicit representation
formula for $\partial_{\bf x}U(t,s,{\bf x})$, which is determined by
(3.15)–(3.16).

We first apply Proposition 6.5 to the middle equation of (3.16) with

(6.20)
$\left.\begin{array}[]{l}\displaystyle\xi_{l}:=\big{\langle}Dg(l,X^{s,{\bf
x}}),\nabla_{\eta}X^{s,{\bf x}}\big{\rangle}+\int_{l\vee
s}^{T}\big{\langle}Df\big{(}l,r,X^{s,{\bf x}},Y^{s,{\bf x}}_{r},Z^{l,s,{\bf
x}}_{r}\big{)},\nabla_{\eta}X^{s,{\bf x}}\big{\rangle}dr;\\\
\displaystyle\alpha(l,r):=\partial_{y}f\big{(}l,r,X^{s,{\bf x}},Y^{s,{\bf
x}}_{r},Z^{l,s,{\bf
x}}_{r}\big{)},\quad\beta(l,r):=\partial_{z}f\big{(}l,r,X^{s,{\bf
x}},Y^{s,{\bf x}}_{r},Z^{l,s,{\bf x}}_{r}\big{)},\quad l\vee s\leqslant r;\\\
\vskip 3.0pt plus 1.0pt minus
1.0pt\cr\displaystyle\alpha(t,r):=0,\quad\beta(t,r):=0,\quad t\leqslant
r<s.\end{array}\right.$

Define $M^{l}_{r}$, $K_{1}(l,r)$, and $\Gamma(l,r)$ by (6.16)–(6.17), then

$\displaystyle\nabla_{\eta}Y^{s,{\bf
x}}_{l}=\mathbb{E}_{l}\Big{[}M^{l}_{T}\xi_{l}+\int_{l}^{T}\Gamma(l,r)M^{r}_{T}\xi_{r}dr\Big{]},\quad
l\in[s,T].$

Note that $M^{t}_{s}=1$ and $K_{1}(t,r)=0$ for $r\in[t,s]$, thanks to the
third line of (6.20). Then, by (3.15) and the last equation of (3.16) we have

$\displaystyle\partial_{\bf x}U(t,s,{\bf x})$ $\displaystyle=$
$\displaystyle\nabla_{\eta}\widetilde{Y}^{t,s,{\bf
x}}_{s}=\mathbb{E}\Big{[}M^{t}_{T}\xi_{t}+\int_{s}^{T}M^{t}_{l}\alpha(t,l)\nabla_{\eta}Y^{s,{\bf
x}}_{l}dl\Big{]}$ $\displaystyle=$
$\displaystyle\mathbb{E}\Big{[}M^{t}_{T}\xi_{t}+\int_{s}^{T}K_{1}(t,l)\big{[}M^{l}_{T}\xi_{l}+\int_{l}^{T}\Gamma(l,r)M^{r}_{T}\xi_{r}dr\big{]}dl\Big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}\Big{[}M^{t}_{T}\xi_{t}+\int_{s}^{T}\big{[}K_{1}(t,l)+\int_{s}^{r}K_{1}(t,l)\Gamma(l,r)dl\big{]}M^{r}_{T}\xi_{r}dr\Big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}\Big{[}M^{t}_{T}\xi_{t}+\int_{s}^{T}\Gamma(t,r)M^{r}_{T}\xi_{r}dr\Big{]}.$

Plug the first line of (6.20) into this, we obtain

(6.21) $\left.\begin{array}[]{c}\displaystyle\partial_{\bf x}U(t,s,{\bf
x})=\mathbb{E}\big{[}\langle G^{s,{\bf x}}(t),\nabla_{\eta}X^{s,{\bf
x}}\rangle\big{]},\\\ \vskip 3.0pt plus 1.0pt minus
1.0pt\cr\displaystyle\mbox{where}\quad G^{s,{\bf
x}}(t):=M^{t}_{T}Dg(t,X^{s,{\bf
x}})+\int_{s}^{T}\Gamma(t,l)M^{l}_{T}Dg(l,X^{s,{\bf
x}})dl+\int_{s}^{T}H^{s,{\bf x}}(t,r)dr;\\\ \vskip 3.0pt plus 1.0pt minus
1.0pt\cr\displaystyle H^{s,{\bf x}}(t,r):=M^{t}_{r}Df\big{(}t,r,X^{s,{\bf
x}},Y^{s,{\bf x}}_{r},Z^{t,s,{\bf
x}}_{r}\big{)}+\int_{s}^{r}\Gamma(t,l)M^{l}_{r}Df\big{(}l,r,X^{s,{\bf
x}},Y^{s,{\bf x}}_{r},Z^{l,s,{\bf x}}_{r}\big{)}dl.\end{array}\right.$

Next, recall the first equation of (3.16). We set

(6.22) $\displaystyle\check{\varphi}(t,s,{\bf
x};t^{\prime},s^{\prime},dr^{\prime}):=D\varphi(t^{\prime},s^{\prime},X^{s,{\bf
x}})(dr^{\prime}),\quad\hbox{for~{}}\varphi=b,\sigma;$
$\displaystyle\check{g}(t,s,{\bf x};dt^{\prime}):=G^{s,{\bf
x}}(t)(dt^{\prime}).$

We now introduce the type-II BSVIE on $[s,T]$:

(6.23) $\displaystyle{\cal
Y}_{t^{\prime}}=\check{g}(t^{\prime})-\int_{t^{\prime}\leqslant
l^{\prime}\leqslant s^{\prime}\leqslant r^{\prime}\leqslant
T}\Big{[}\check{b}(t,s,{\bf
x};r^{\prime},s^{\prime},dl^{\prime})\widetilde{\cal
Y}(dr^{\prime},s^{\prime})$ $\displaystyle\qquad\quad+\check{\sigma}(t,s,{\bf
x};r^{\prime},s^{\prime},dl^{\prime}){\cal
Z}(dr^{\prime},s^{\prime})\Big{]}ds^{\prime}-\int_{t^{\prime}}^{T}{\cal
Z}(t^{\prime},s^{\prime})dW_{s^{\prime}};$ $\displaystyle\widetilde{\cal
Y}(t^{\prime},s^{\prime})={\cal
Y}_{t^{\prime}}-\int_{s^{\prime}}^{t^{\prime}}{\cal
Z}(t^{\prime},r^{\prime})dW_{r^{\prime}},\quad 0\leqslant s^{\prime}\leqslant
t^{\prime}.$

By Theorem 6.1, we obtain the following explicit representation formula for
$\partial_{\bf x}U(t,s,{\bf x})$.

######  Theorem 6.7.

For any fixed $(t,s,{\bf x})\in\mathbb{T}^{2}_{+}\times\mathbb{X}$, let
$\widetilde{\cal Y}$ be determined by (6.23). Then the path derivative of the
solution $U$ to PPDE (3.1) can be represented explicitly as follows:

(6.24) $\partial_{\bf x}U(t,s,{\bf x})=\widetilde{\cal Y}(\cdot,s).$

## References

  * [1] E. Abi Jaber, M. Larsson and S. Pulido, Affine Volterra processes, Ann. Appl. Probab., 29 (2019), 3155–3200.
  * [2] N. Agram, Dynamic risk measure for BSVIE with jumps and semimartingale issues, Stoch. Anal. Appl., 37 (2019), 1–16.
  * [3] E. Alos, J. Leon and J. Vives, On the short-time behavior of the implied volatility for jump-diffusion models with stochastic volatility, Finance Stoch 11 (2007), 571–589.
  * [4] C. Bayer, P. Friz and J. Gatheral, Pricing under rough volatility, Quant. Finance, 16 (2016), 887–904.
  * [5] A. Barrasso and F. Russo, Gâteaux type path-dependent PDEs and BSDEs with Gaussian forward processes, preprint, arXiv:1907.13366.
  * [6] A. Barrasso and F. Russo, Decoupled mild solutions of path-dependent PDEs and Integro PDEs represented by BSDEs driven by cadlag martingales, Potential Anal., 53 (2020), 449–481.
  * [7] M. Bennedsen, A. Lunde and M. Pakkanen, Decoupling the short- and long-term behavior of stochastic volatility, preprint, arXiv:1610.00332.
  * [8] M. Berger and V. Mizel, Volterra equation with Itô integrals, I,II, J. Intergal Equations, 2 (1980), 187–245; 319–337.
  * [9] A. Chronopoulou and F. G. Alexandra, Stochastic volatility and option pricing with long-memory in discrete and continuous time, Quant. Finance, 12 (2012), 635–649.
  * [10] F. Comte and E. Renault, Long Memory in Continuous-time Stochastic Volatility Models, Math. Finance, 8 (1998), 291–323.
  * [11] R. Cont and D. A. Fournié, Change of variable formulas for non-anticipative functionals on path space, J. Funct. Anal., 259 (2010), 1043–1072.
  * [12] R. Cont and D. A. Fournié, Functional Itô calculus and stochastic integral representation of martingales, Ann. Probab., 41 (2013), 109–133.
  * [13] A. Cosso and F. Russo, Strong-viscosity solutions: semilinear parabolic PDEs and path-dependent PDEs, Osaka J. Math., 56 (2019), 323–373.
  * [14] A. Cosso and F. Russo, Crandall-Lions Viscosity Solutions for Path-Dependent PDEs: The Case of Heat Equation, preprint, arXiv:1911.13095.
  * [15] C. Cuchiero and J. Teichmann, Generalized Feller processes and Markovian lifts of stochastic Volterra processes: the affine case, J. Evol. Equ., (2020), https://doi.org/10.1007/s00028-020-00557-2.
  * [16] M. G. Crandall, H. Ishii and P. L. Lions, User’s guide to viscosity solutions of second order partial differential equations, Bull. Amer. Math. Soc., 27 (1992), 1–67.
  * [17] M. G. Crandall and P. L. Lions, Hamilton-Jacobi equations in infinite dimensions, V: Unbounded linear terms and $B$-continuous solutions, J. Funt. Anal., 97, (1991), 417–465.
  * [18] L. Di Persio, Backward stochastic Volterra integral equation approach to stochastic differential utility, Int. Electron. J. Pure Appl. Math., 8 (2014), 11–15.
  * [19] J. Djordjević and S. Janković, On a class of backward stochastic Volterra integral equations, Appl. Math. Lett., 26 (2013), 1192–1197.
  * [20] J. Djordjević and S. Janković, Backward stochastic Volterra integral equations with additive perturbations, Appl. Math. Comput., 265 (2015), 903–910.
  * [21] B. Dupire, Functional Itô Calculus, Quantitative Finance 19 (2019), 721–729.
  * [22] I. Ekeland and A. Lazrak, The golden rule when preferences are time inconsistent, Math. Finance Econ., 4 (2010), 29–55.
  * [23] I. Ekren, C. Keller, N. Touzi and J. Zhang, On viscosity solutions of path dependent PDEs, Ann. Probab., 42 (2014), 204–236.
  * [24] I. Ekren, N. Touzi and J. Zhang, Viscosity solutions of fully nonlinear parabolic path dependent PDEs: part I,  Ann. Probab., 44 (2016), 1212–1253.
  * [25] I. Ekren, N. Touzi and J. Zhang,  Viscosity solutions of fully nonlinear parabolic path dependent PDEs: part II, Ann. Probab., 44 (2016), 2507–2553.
  * [26] O. El Euch and M. Rosenbaum, The characteristic function of rough Heston models, Math. Finance, 29 (2019), 3–38.
  * [27] O. El Euch and M. Rosenbaum, Perfect hedging in rough Heston models. Ann. Appl. Probab., 28 (2018), 3813–3856.
  * [28] G. Fabbri, F. Gozzi and A. Swiech, Stochastic Optimal Control in Infinite Dimensions, Springer, 2017.
  * [29] J. Fouque and R. Hu, Optimal Portfolio under Fractional Stochastic Environment, Math. Finance, 29 (2019), 697–734.
  * [30] J. Gatheral, T. Jaisson and M. Rosenbaum, Volatility is rough, Quant. Finance, 18 (2018), 933–949.
  * [31] J. Gatheral and M. Keller-Ressel, Affine forward variance models, Finance and Stoch., 23 (2019), 501–533.
  * [32] A. Gulisashvili, F. Viens and X. Zhang, Small-time asymptotics for Gaussian self-similar stochastic volatility models, Appl. Math. Optim., 82 (2020), 183–223 .
  * [33] Y. Hamaguchi, Small-time solvability of a flow of forward-backward stochastic differential equations, Appl. Math. Optim., (2020), https://doi.org/10.1007/s00245-020-09654-7.
  * [34] C. Hernández and D. Possamai, Me, myself and I: a general theory of non-Markovian time-inconsistent stochastic control for sophisticated agents, preprint, arXiv:2002.12572.
  * [35] C. Hernández and D. Possamai, A unified approach to well-posedness of type-I backward stochastic Volterra integral equations, preprint, arXiv:2007.12258.
  * [36] Y. Hu and B. Øksendal, Linear Volterra backward stochastic integral equations, Stochastic Process. Appl., 129 (2019), 626–633.
  * [37] I. Karatzas and S. Shreve, Brownian Motion and Stochastic Calculus, Springer-Verlag, New York, 1988.
  * [38] L. Karp, Non-constant discounting in continuous time, Journal of Economic Theory, 132 (2007), 557–568.
  * [39] E. Kromer and L. Overbeck, Differentiability of BSVIEs and dynamical capital allocations, Int. J. Theor. Appl. Finance, 20 (2017), No.07, 1750047.
  * [40] D. Laibson, Golden eggs and hyperbolic discounting, Q. J. Econ., 112 (1997), 443–478.
  * [41] D. Leao, A. Ohashi and A. B. Simas, A weak version of path-dependent functional Itô calculus, Annals of Probability, 46 (2018), 3399–3441.
  * [42] X. Li and J. Yong, Optimal Control Theory for Infinite Dimensional Systems, Birkhäuser, Boston, 1995.
  * [43] J. Lin, Adapted solution of a backward stochastic nonlinear Volterra integral equation, Stoch. Anal. Appl., 20 (2002), 165–183.
  * [44] N. Yu. Lukoyanov, On viscosity solution of functional Hamilton-Jacobi type equations for hereditary systems, Proceedings of the Steklov Institute of Mathematics, 259 (2007), 190–200.
  * [45] J. Ma, P. Protter and J. Yong, Solving forward-backward stochastic differential equations explicitly — a four step scheme, Probab. Theory Related Fields, 98 (1994), 339–359.
  * [46] D. Nualart, Malliavin calculus and related topics. In Stochastic Processes and Related Topics, 2nd ed. Springer, Berlin, 2006.
  * [47] L. Overbeck and J. A. L. Röder, Path-dependent backward stochastic Volterra integral equations with jumps, differentiability and duality principle, Probab. Uncertain. Quant. Risk, (2018), DOI 10.1186/s41546-018-0030-2.
  * [48] E. Pardoux and S. Peng, Backward stochastic differential equations and quasilinear parabolic partial differential equations, Stochastic Partial Differential Equations and Their Applications, Springer, Berlin, Heidelberg, 1992: 200–217.
  * [49] S. Peng, A nonlinear Feynman–Kac formula and applications, Proc. Symposium of System Sciences and Control Theory, Chen & Yong eds., 173–184, World Scientific, Singapore, 1991.
  * [50] S. Peng, Backward stochastic differential equation, nonlinear expectation and their applications, Proc. International Congress of Mathematicians 2010, Vol. I, 393–432.
  * [51] S. Peng and Y. Song, G-expectation weighted Sobolev spaces, backward SDE and path dependent PDE, J. Math. Soc. Japan, 67 (2015), 1725–1757.
  * [52] S. Peng and F. Wang, BSDE, path-dependent PDE and nonlinear Feynman–Kac formula, Science China Math., 59 (2016), 19–36.
  * [53] S. Peng and Z. Yang, Anticipated backward stochastic differential equations, Ann. Probab., 37 (2009), 877–902.
  * [54] R. A. Pollak, Consistent planning, Rev. Econ. Stud., 35 (1968), 185–199.
  * [55] A. Popier, Backward stochastic Volterra integral equations with jumps in a general filtration, preprint, arXiv:2002.06992.
  * [56] Z. Ren and M. Rosestolato, Viscosity solutions of path-dependent PDEs with randomized time, SIAM J. Math. Anal., 52 (2020), 1943–1979.
  * [57] Z. Ren, N. Touzi and J. Zhang, Comparison of viscosity solutions of fully nonlinear degenerate parabolic path-dependent PDEs, SIAM J. Math. Anal., 49 (2017), 4093–4116.
  * [58] J. Ruan and J. Zhang, Numerical methods for high dimensional path dependent PDEs driven by stochastic Volterra integral equations, working paper.
  * [59] Y. Shi, T. Wang and J. Yong, Optimal control problems of forward-backward stochastic Volterra integral equations, Math. Control Relat. Fields, 5 (2015), 613–649.
  * [60] R. H. Strotz, Myopia and inconsistency in dynamic utility maximization, Rev. Econ. Stud., 23 (1955-1956), 165–180.
  * [61] F. Viens and J. Zhang, A martingale approach for fractional Brownian motions and related path dependent PDEs, Ann. Appl. Probab., 29 (2019), 3489–3540.
  * [62] H. Wang, Extended backward stochastic Volterra integral equations, quasilinear parabolic equations, and Feynman–Kac formula, Stoch. Dyn., 21 (2021), 2150004.
  * [63] H. Wang, J. Sun and J. Yong, Recursive utility processes, dynamic risk measures and quadratic backward stochastic Volterra integral equations, Appl. Math. Optim., (2019), https://doi.org/10.1007/s00245-019-09641-7.
  * [64] H. Wang and J. Yong, Time-inconsistent stochastic optimal control problems and backward stochastic Volterra integral equations, preprint, arXiv:1911.04995.
  * [65] T. Wang and J. Yong, Comparison theorems for some backward stochastic Volterra integral equations, Stochastic Process. Appl., 125 (2015), 1756–1798.
  * [66] T. Wang and J. Yong, Backward stochastic Volterra integral equations—representation of adapted solutions, Stochastic Process. Appl., 129 (2019), 4926–4964.
  * [67] T. Wang and H. Zhang, Optimal control problems of forward-backward stochastic Volterra integral equations with closed control regions, SIAM J. Control Optim., 55 (2017), 2574–2602.
  * [68] Q. Wei, J. Yong and Z. Yu, Time-inconsistent recursive stochastic optimal control problems, SIAM J. Control Optim., 55 (2017), 4156–4201.
  * [69] J. Yong, Backward stochastic Volterra integral equations and some related problems, Stochastic Process. Appl., 116 (2006), 779–795.
  * [70] J. Yong, Continuous-time dynamic risk measures by backward stochastic Volterra integral equations, Appl. Anal., 86 (2007), 1429–1442.
  * [71] J. Yong, Well-posedness and regularity of backward stochastic Volterra integral equations, Probab. Theory Related Fields, 142 (2008), 21–77.
  * [72] J. Yong, Time-inconsistent optimal control problems and the equilibrium HJB equation, Math. Control Relat. Fields, 2 (2012), 271–329.
  * [73] J. Yong, Representation of adapted solutions to backward stochastic Volterra integral equations, Scientia Sinica Mathematica, 47 (2017), 1355–1366 (in Chinese).
  * [74] K. Yosida, Functinal Analysis, 6th Edition, Springer-Verlag, Berlin, 1980.
  * [75] J. Zhang, Backward Stochastic Differential Equations: From Linear to Fully Nonlinear Theory, Springer, New York, 2017.
  * [76] J. Zhou, Viscosity solutions to second order path-dependent Hamilton–Jacobi–Bellman equations and applications, preprint, arXiv:2005.05309.


# Experimental quantum imaging distillation
with undetected light

Jorge Fuenzalida,1,2,†,⋆ Marta Gilaberte Basset,1,3,⋆ Sebastian Töpfer,1,2,⋆
Juan P. Torres,4,‡ and Markus Gräfe1,2,3,§
1Fraunhofer Institute for Applied Optics and Precision Engineering IOF,
Albert-Einstein-Str. 7, 07745 Jena, Germany.
2Technical University of Darmstadt, Department of Physics, Institute of
Applied Physics, Schloßgartenstraße 7, 64289 Darmstadt, Germany.
3Friedrich-Schiller-University Jena, Abbe Center of Photonics,
Albert-Einstein-Str. 6, 07745 Jena, Germany.
4ICFO-Institut de Ciencies Fotoniques, The Barcelona Institute of Science and
Technology,
08860 Castelldefels, Spain, and Dept. Signal Theory and Communications,
Universitat Politecnica de Catalunya, 08034 Barcelona, Spain.
†<EMAIL_ADDRESS>
‡<EMAIL_ADDRESS>
§<EMAIL_ADDRESS>
⋆These authors contributed equally.

(August 28, 2024)

## Abstract

Imaging based on the induced coherence effect makes use of photon pairs to
obtain information of an object without detecting the light that probes it.
While one photon illuminates the object, only its partner is detected, so no
measurement of coincidence events are needed. The sought-after object’s
information is revealed observing a certain interference pattern on the
detected photon. Here we demonstrate experimentally that this imaging
technique can be made resilient to noise. We introduce an imaging distillation
approach based on the interferometric modulation of the signal of interest. We
show that our scheme can generate a high-quality image of an object even
against noise levels up to 250 times the actual signal of interest. We also
include a detailed theoretical explanation of our findings.

## Introduction

Quantum imaging Gilaberte Basset et al. (2019) is an emerging and promising
field in quantum technologies with certified advantages over classical
protocols. This has been demonstrated in different scenarios: in schemes that
work in the low-photon flux regime Aspden et al. (2013); Morris et al. (2015),
in schemes that make use of undetected probing photons Lemos et al. (2014);
Gilaberte Basset et al. (2021), for super-resolution imaging Schwartz et al.
(2013); Classen et al. (2017); Unternährer et al. (2018); Tenne et al. (2019),
sub-shot-noise imaging Brida et al. (2010); Sabines-Chesterking et al. (2019);
Casacio et al. (2021), or enhanced two-photon absorption processes Teich and
Saleh (1997). Moreover, protocols in quantum imaging with no classical
counterpart has been developed based on quantum interference Ndagano et al.
(2022), and entanglement Defienne et al. (2021); Camphausen et al. (2021). In
recent years, it has also been proven that quantum imaging protocols can be
resilient to noise Lloyd (2008); Tan et al. (2008); Lopaeva et al. (2013).

Distillation (also known as purification) is the process wherein the
decoherence introduced in a quantum system by the environment can be removed
Pan et al. (2001). In quantum imaging, the effect of the environment can be
modeled through classical illumination superimposed over a quantum image on
the camera. Since most cameras only detect intensity, quantum and classical
images seems to be indistinguishable. However, quantum correlations of photon
pairs can be employed to differentiate the quantum image from a classical one.
Quantum imaging distillation has been implemented with one and several photon
pair degrees of freedom England et al. (2019); Defienne et al. (2019); Zhang
et al. (2020); Gregory et al. (2020); Zhao et al. (2022). To the best of our
knowledge, every implementation to date has used the joint detection of photon
pairs. In this work, we introduce and experimentally verify a quantum imaging
distillation technique that employs the detection of single photons only.

Quantum imaging with undetected light (QIUL) Lemos et al. (2014); Lahiri et
al. (2015); Fuenzalida et al. (2022); Vega et al. (2022) is a two-photon wide-
field interferometric imaging technique. In QIUL, one photon illuminates an
object and its partner photon is detected on the camera. The photon that
illuminates the object remains undetected. Using an interferometric
configuration, the object information is transferred to the detected photon
interference pattern. Due to its unique detection advantage, QIUL has been
employed to probe samples with unconventional wavelengths while visible light
is detected Kviatkovsky et al. (2020); Paterova et al. (2020a, b); Paterova et
al. (2021). Up to date, the effects of noise in QIUL have not yet been
explored.

Here we introduce a source of noise in a QIUL scheme and study the resilience
of the quantum imaging technique. The properties of the noise, its intensity
and variance, are changed during this study. We perform a quantum imaging
distillation technique based on quantum phase-shifting digital holography
Töpfer et al. (2022). Our distillation technique uses phase modulation of the
undetected photon to vary the interference pattern detected on the camera. We
notice that if the intensity difference of the interference patterns is bigger
than the variance of the noise, the quantum image can be distilled. We also
observe that the noise variance affects the distilled quantum images linearly
in their phase estimation. Our technique shows a good performance, even for
noise intensities above 250 times the quantum signal intensity.

## Distillation principle

Figure 1: Principle of quantum imaging distillation. We employ a quantum
imaging distillation protocol to remove a noisy image from a quantum image.
(a) is the quantum image we aim to distill. (b) is the noise image that is
superimposed on the quantum image. (c) is the superposition of noise and
quantum images.(d) is the resulting distilled image from noise.

Quantum imaging distillation is a process whereby a quantum image is cleaned
from noise. To explain our distillation technique let us consider two images:
a quantum image, which is acquired by illuminating the sample with with non-
classical light, and a noise image, which is an image detected at the camera
and generated with classical illumination. These two images are shown in Figs.
1(a) and 1(b), respectively. A noise image is an unwanted signal that is
superimposed over a quantum image on the camera. This image superposition is
shown in Fig. 1(c). To distill an image, different photon pair degrees of
freedom can be employed, e.g., frequency, time, or spatial correlations. We
use the amplitude modulation of quantum holography with undetected light
(QHUL) Töpfer et al. (2022), which is an interferometric quantum imaging
technique Lemos et al. (2014). In QHUL, the object information is carried into
a single-photon interference pattern. When the noise reaches the camera, if
the intensity difference of QHUL is bigger than the intensity variance of the
noise, the quantum image can be distilled. The resulting distilled image is
shown in Fig. 1(d).

## Theory

Spontaneous parametric down-conversion (SPDC) Klyshko (1969); Burnham and
Weinberg (1970) is a well-known nonlinear process that generates photon pairs
(signal and idler) mediated by the interaction of an intense pump beam with
the atoms of a nonlinear crystal Walborn et al. (2010). Our imaging scheme
makes use on a SU(1,1) interferometer, wherein a pair of signal-idler photons
can be generated in one of two propagation modes, forward and backward. The
probability to generate paired photons in both modes (forward or backward)
simultaneously is negligible Lahiri et al. (2019); Wiseman and Mølmer (2000).
In the forward propagation mode, the pump, signal, and idler beams are
spatially separated, and later, back-reflected into the nonlinear crystal with
the help of 4f systems. Before back reflection the idler photon is reflected
from an object, with complex reflectivity $R=|R|\exp(i\varphi_{R})$, placed in
front of its end-mirror. In the backward propagation mode, the idler photon do
not interact with the sample. The signal photons are collected by a camera,
and the idler photon remains undetected.

The mean value of signal photons detected in time $T_{D}$ at one pixel of the
camera of area $S_{D}$ (see supplementary material for details) is

$\displaystyle\left\langle
N_{S}\right\rangle_{\delta}=2\>S_{0}\>[1+|R|\>\gamma\,\cos(\delta+\varphi_{R})].$
(1)

$\delta$ is an interferometric spatially invariant phase and $S_{0}$ is the
number of signal photons generated in single-pass SPDC (in a time window
$T_{D}$ and area $S_{D}$). The parameter $\gamma$ is related to the effective
bandwidth of the signal-idler photon pairs, determined essentially by the
bandwidth of the filters located in front of the camera Töpfer et al. (2022).
From Eq. (1), we see that $\left\langle N_{S}\right\rangle$ changes when
$\delta$ is varied. In particular, using $\delta=0,\pi/2,\pi$, and $3\pi/2$,
the object’s information can be retrieved by means of QHUL as follows:

$\displaystyle|R|=2\times\frac{\left(\left[\left\langle
N_{S}\right\rangle_{3\pi/2}-\left\langle
N_{S}\right\rangle_{\pi/2}\right]^{2}+\Big{[}\left\langle
N_{S}\right\rangle_{0}-\left\langle
N_{S}\right\rangle_{\pi}\Big{]}^{2}\right)^{1/2}}{\left\langle
N_{S}\right\rangle_{0}+\left\langle N_{S}\right\rangle_{\pi/2}+\left\langle
N_{S}\right\rangle_{\pi}+\left\langle N_{S}\right\rangle_{3\pi/2}},$ (2)
$\displaystyle\varphi_{R}=\arctan\left(\frac{\left\langle
N_{S}\right\rangle_{3\pi/2}-\left\langle
N_{S}\right\rangle_{\pi/2}}{\left\langle N_{S}\right\rangle_{0}-\left\langle
N_{S}\right\rangle_{\pi}}\right).$ (3)

Equations (2) and (3) are not unique representations of $|R|$ and
$\varphi_{R}$ and, in general, these quantities can be extracted using
different number of phases Töpfer et al. (2022). We emphasize that in this
technique paired photon coincidences are not needed and only signal photons
are measured.

For the important case of phase estimation, we evaluate the sensitivity of
QHUL obtaining the variance of $\varphi_{R}$ given by Eq. (3). We first
calculate the variance of the signal-photon flux $\left\langle(\Delta
N_{S})^{2}\right\rangle=\left\langle N_{S}^{2}\right\rangle-\left\langle
N_{S}\right\rangle^{2}$. Since the coherence time $T_{C}$ of signal-idler
photon pairs ($T_{C}\sim 1/B$, $B$ is the effective bandwidth of SPDC) is much
smaller than the detection time, we can approximate the variance of the
signal-photon flux to as (see Supplementary Material),

$\left\langle(\Delta N_{S})^{2}\right\rangle=\left\langle N_{S}\right\rangle,$
(4)

which is equivalent to considering Poissonian statistics. This result is well-
known to be valid when considering a multimode signal where each mode has the
same non-Poissonian statistics.

The result in Eq. (4) corresponds to the minimum signal variance achievable in
QHUL. However, this variance can rapidly increase by electronic noise, e.g.,
camera signal-to-noise ratio, or external sources of noise such as temperature
fluctuations, airflow, and external illumination, among others. In this work,
we study the effect of an external classical illumination impinging on the
camera, overlapping the quantum image of interest. Since QHUL detects only the
single-photon stream of signal photons, the decoherence produced by an
external source of light seems extremely harmful and, therefore, the image
distillation highly improbable. However, we will demonstrate experimentally
that the quantum imaging distillation is possible even in scenarios with
considerable high levels of noise in comparison to the quantum signal
intensity.

Figure 2: Intensity detected in one camera pixel. For visualization purposes,
we have considered the same intensities (chart bars) and variances (error
bars) for the signal photon and the noise. In (a) is presented the signal
photon intensity (in pink) for different values of $\delta$. This intensity
fluctuation allows us to compute the object information using QHUL Töpfer et
al. (2022). In (b) is presented the noise intensity (in blue) for the same
phases $\delta$. In contrast to the signal intensity, the noise intensity is
not affected by the value of $\delta$. In (c) are added the noise and signal
intensities. Since noise intensity does not change, its contribution just sets
a higher background. On top of it, signal photon intensity still changes, and
the total variance is its previous variance plus the noise variance. Thus, an
external source of noise increases the shot noise of QHUL.

Quantum holography with undetected light employs interferometric modulation of
the signal photon to retrieve the object information, as shown in Eqs. (2) and
(3). We show that this modulation can also be used for distillation purposes,
which is depicted in Fig. 2. For each value of the interference phase
$\delta$, the signal photon has a well-defined intensity and variance, given
by Eqs. (1) and (4), respectively. In Fig. 2(a), signal intensity (variance)
is represented with pink bar charts (error bars). In contrast, the intensity
of a stochastic noise $\left\langle N_{T}\right\rangle$ fluctuates randomly
with a variance $\left\langle(\Delta N_{T})^{2}\right\rangle$. For the sake of
simplicity, we consider (but are not restricted to) to the case where the
noise has the same total mean intensity and variance than the signal photon.
In Fig. 2(b), the noise intensity (variance) is represented with blue bar
charts (error bars). As a result of adding these two intensities, see Fig.
2(c), the background increases up to the noise intensity, while the signal
intensity varies on top of it. The noise variance contributes to the signal
intensity variance, i.e., the shot noise increases. In this way, one can infer
that if the difference of the signal intensity is higher than the noise
variance, the quantum image can be distilled. Additionally, the shot noise of
QHUL always increases if the noise intensity and/or its variance increases.
More details are given in the Supplementary Material.

Let us analyze the performance of our distillation technique by considering a
generalization of Eq. (2). For QHUL with $M$ phase steps, we have that

$\displaystyle\varphi_{R}=-\tan^{-1}\left(\sum_{j}\langle
N_{S}\rangle_{j}\sin\delta_{j}/\sum_{j}\langle
N_{S}\rangle_{j}\cos\delta_{j}\right),$ (5)

with $\delta_{j}=j\>2\pi/M$, and $j=0,1,...,M-1$. The phase variance,
including noise, it reads

$\displaystyle\left\langle(\Delta\varphi_{R})^{2}\right\rangle=\sum_{j}\left(\frac{\partial\varphi_{R}}{\partial\left\langle
N_{S}\right\rangle_{j}}\right)^{2}\left[\left\langle(\Delta
N_{S})^{2}\right\rangle_{j}+\left\langle(\Delta
N_{T})^{2}\right\rangle\right],$ (6)

where

$\displaystyle\left(\frac{\partial\varphi_{R}}{\partial\left\langle
N_{S}\right\rangle_{j}}\right)^{2}=\frac{1}{M^{2}\,\gamma^{2}\,|R|^{2}\,S^{2}_{0}}\sin^{2}(\varphi_{R}+\delta_{j}).$
(7)

Replacing Eqs. (4) and (7) into Eq. (6), and considering $n$ measurements, we
obtain that the variance of phase estimation is

$\displaystyle\left\langle(\Delta\varphi_{R})^{2}\right\rangle=\frac{1}{n\,S_{0}}\,\frac{1}{M\,V^{2}}\left\\{1+\frac{\left\langle(\Delta
N_{T})^{2}\right\rangle}{2\,S_{0}}\right\\}.$ (8)

$S_{0}$ is the number of idler photons that illuminate the object whose phase
we want to estimate, $\left\langle(\Delta N_{T})^{2}\right\rangle$ is the
variance of the number of background photons that illuminate the detector, and
$V=|R|\gamma$ is the visibility of the signal-photon flux interference pattern
as a function of the phase $\delta$ 111The visibility is defined by
$V=(\left\langle N\right\rangle_{\textup{max}}-\left\langle
N\right\rangle_{\textup{min}})/(\left\langle
N\right\rangle_{\textup{max}}+\left\langle N\right\rangle_{\textup{min}})$,
where $\left\langle N\right\rangle_{\textup{max}}$ ($\left\langle
N\right\rangle_{\textup{min}}$) is the maximum (minimum) photon count rate..
Equation (8) contains two contributions to the variance of the phase: the
first term comes from the quantum illumination, and the second term comes from
the noise illumination. While the former can be shown to be well described by
Poissonian statistics (see Supplementary Material), the latter depends on the
specific characteristics of the noise illumination.

## Results

### Quantum imaging

Figure 3: Setup. The signal and idler beams (in paths $b$ and $c$,
respectively) are generated by the pump beam in path $a$ interacting with the
nonlinear crystal (ppKTP) in the forward direction, while paths $e$ and $f$
represent propagations of the down converted beams generated after the pump
beam is reflected back into the crystal by mirror M3 in path $d$. An object in
path $c$ is illuminated with the idler beam in the Fourier plane of the
crystal. To create the noise, a laser diode of the same wavelength as the
signal photon (910 nm) is used. The signal beam in path $e$ is merged with the
noise in path $g$ before reaching the camera with a 10:90 beam splitter. On
the detector plane we obtain the quantum image with lenses L2, L4 and L5, and
the noise image with lenses L6 and L7. Different type of noise are created
with a linear polarizer and a light diffuser in path $g$. The linear polarizer
controls the pump power of the diode laser. The diffuser that consists on a
rotating ground glass plate produces a speckle pattern of the noise source.
The speed of the rotation is controlled through the glass plate motor
interface.

A sketch of our experimental implementation is depicted in Fig. 3. For our
quantum image, we used a SU(1,1) nonlinear interferometer Yurke et al. (1986)
in a Michelson configuration, where its input/output is a nonlinear medium.
Our crystal is a periodically poled potassium titanyl phosphate (ppKTP) of
$2\times 2\times 1$ mm3 (length $\times$ width $\times$ height), which is
pumped bidirectionally ($a$ and $f$ directions) by a CW laser at 405 nm and
with avarage power of 90 mW. Due to its strong $\chi^{(2)}$–nonlinearity, a
photon pair (signal and idler photons), is generated through SPDC into the
paths $a$ or $f$, but never simultaneously. Signal (idler) photons have a
central wavelength of $\lambda_{S}=910$ nm ($\lambda_{I}=730$ nm).

In the forward propagation direction $a$, signal, idler, and pump beams are
spatially separated with dichroic mirrors DM2 and DM3 into the paths $b$, $c$,
and $d$, and reflected back into the crystal with mirrors M1, M2, and M3. In
front of mirror M2, an object with a complex amplitude
$R=|R|\exp(i\varphi_{R})$ is placed. In $b$, $c$, and $d$, lenses of focal
length f$=150$ mm transform transverse position (source plane) into transverse
momentum (mirrors plane). Therefore, in path $c$, a wave vector
$\mathbf{k}_{I}$ representing a plane wave of the idler photon is focused to a
point on the object Lahiri et al. (2015); Fuenzalida et al. (2022). The
interaction of idlers being absorbed or reflected by the object can be modeled
with the help of a beam splitter Vega et al. (2022). In the backward
propagation $f$, signals are collected by a camera and idlers remain
undetected. We ensured that by placing a 800 nm long-pass filter and a $910\pm
1.5$ nm interference filter in front of the camera. Our camera is the Prime
BSI Scientific CMOS from Teledyne Photometrics with a pixel size of 6.5
$\mu$m. Signal photon’s transverse momentum is obtained with the lens L4 of
focal length f$=100$ mm performing a Fourier transform of the source plane.
This plane is later imaged on camera with the lens L5 of focal length f$=150$
mm. Thus, a wave vector $\mathbf{k}_{S}$ of the signal photon is focused to a
point on the camera. If $a$ and $f$ propagation are perfectly aligned, the
photon pair emission (which-source) information is erased. Consequently, on
the camera, an interference pattern of signal photons is observed Zou et al.
(1991). Moreover, the object information obtained herein by the idler photon,
is transferred to the signal photon interference pattern Lemos et al. (2014);
Gilaberte Basset et al. (2021), see Eq. (1). The interferometric phase
$\delta$ is changed with a piezo placed below mirror M2. The object
information is retrieved by employing QHUL of 12 steps Töpfer et al. (2022)
with an acquisition time of t=1 s per image.

### Noise source

A CW diode laser of $\lambda_{N}=910$ nm and variable pump power is employed
to introduce noise in the system. The laser illuminates an object, which is
imaged on the camera with a 4f system using the lenses L6 and L7 of focal
lengths f$=150$ mm and f$=125$ mm, respectively. This classical image is
superimposed on top of the quantum image on the camera using a 10:90 beam
splitter, see Fig. 3. Properties of classical illumination, intensity and
variance, are changed in order to evaluate the effects of noise in QHUL and
our distillation performance. Experimental details about the noise properties
can be found in the Supplemental Material.

### Distillation performance to different noise intensities

In the first experiment, while having superimposed classical and quantum
images, QHUL is performed to distill the quantum image under different
intensities of noise. We first characterized the signal flux rate emission
measuring its mean intensity of an illuminated area on the camera. Signal
intensity does not changed during experiments. In a similar way but
independently measured, different noise intensities are characterized, which
are obtained by changing the angle of a linear polarizer (LP) in front of the
laser in path $g$. The experiment starts superimposing the quantum and
classical images on the camera. Experimental results are shown in Fig. 4. Its
first row shows the superposition of classical and quantum images; noise
intensity increases from left to right with the following ratios ($r=$ signal
intensity:noise intensity), $r\approx 1:8$, $r\approx 1:37$, $r\approx 1:50$,
$r\approx 1:104$, and $r\approx 1:252$. Second row in Fig. 4 shows distilled
images by QHUL of the corresponding upper superposed images. Imaging
distillation through QHUL is successfully achieved in every case, even with a
noise intensity 250 times higher than the signal intensity. However, we notice
that while noise intensity increases, sharpness of distilled images decreases.
One can observe this in detail in the third row that shows a transverse cut of
the distilled images (represented by a dotted red line). It is clear from our
experimental results that phase accuracy diminishes as the noise intensity
increases, which also corresponds to prediction given in Eq. (8).

Figure 4: Resilience to different noise intensities. In the upper row are
shown superpositions of quantum (IOF letters) and classical (square shape)
images. The ratio between their intensities is stated on top of each image. In
the middle row are presented the experimental results for our distillation
technique through QHUL. In the last row are presented a transverse cut of the
distilled images. We observe that while the noise intensity increases, the
phase estimation diminishes.

### Induced variance by noise

In a second experiment, we quantified the effects of noise variances on the
phase accuracy of distilled images. The same configurations of noise
intensities are employed. Additionally, a light diffuser mounted on a
rotational motor with four angular frequencies of 0, 1, 2, and 3 Hz changed
the noise variance. The noise variance is characterized considering the
intensity variation of one pixel over 12 consecutive images. Experimental
results are shown in Fig. 5. We plot the experimental measured values for the
phase variance of distilled images against the noise variance for different
angular frequencies (data point with error bars; purple circle = 0 Hz; rose
star = 1 Hz; green triangle = 2 Hz; yellow square = 3 Hz). We also provide a
theoretical prediction for comparison (solid black line). The results show
that an increment of the noise variance increases proportional with the phase
variance. Also it can be observed that in every case a linear dependence
appears between these two variances. However, the noise variance introduces a
slightly higher phase variance than expected. A reasonable explanation for
this is that additional sources of noise were involved during the measurement
process, such as airflow or temperature fluctuations. The experimental
behaviour of variances is in good agreement to theoretical predictions
presented above in Eq. (8).

Figure 5: Distillation phase variance affected by noise variance. The noise
variance was measured with $S_{0}=134\leavevmode\nobreak\ \text{signal
photons}$ generated in a single pass through the crystal. The detection window
was set to be $T_{D}=1\leavevmode\nobreak\ \rm{s}$ and the detection area
$S_{D}$ was $\approx 32.5\times 32.5\leavevmode\nobreak\ \rm{\mu m}^{2}$. A
light diffuser with four different rotation speeds is employed to change the
properties of the noise illumination. In all configurations we observed that
the phase sensitivity is linearly dependent with the noise variance. The noise
variance in dependence to the signal intensity shows a linear dependence as
well (see Supplemental Material). A higher noise variance increases the phase
inaccuracy in QHUL.

## Discussion and conclusion

Our work explores for the first time the effects of noise in Quantum imaging
with undetected light. We have also introduced a technique to distill the
quantum image from that noise. Our quantum imaging distillation technique is
based on quantum holography with undetected light Töpfer et al. (2022). This
technique uses a photon pair, signal and idler, where idler illuminates the
object and signal is detected on the camera. The idler photon remains
undetected and its phase modulation is employed in the imaging distillation
procedure.

To prove our technique, we superimposed partially or completely a classical
source of noise on top of our quantum image on the camera. Our technique
worked in every occasion, even for noise intensities 250 times higher than our
signal intensity. However, the noise variance does affect the phase accuracy
of our distillation technique. A higher noise variance produces a higher phase
inaccuracy, where in general, these two quantities are linearly dependent.

Although, in our experiment we employed a classical source of noise, this
distillation technique should also work for a quantum source of noise.
Furthermore, since the underlying principle of this distillation technique is
the phase modulation, our technique should be applicable to QIUL based on
position correlations Viswanathan et al. (2021); Kviatkovsky et al. (2022).

Our experiment is a step forward for quantum imaging in open systems and could
be useful to the understand the limitations of a (quantum) LIDAR with
undetected light.

## Acknowledgments

The authors thank Fabian Steinlechner for fruitful discussions. This work was
supported as a Fraunhofer LIGHTHOUSE PROJECT (QUILT). Furthermore, funding
support is acknowledged from the German Federal Ministry of Education and
Research (BMBF) within the funding program Photonics Research Germany with
contract number 13N15088. In addition, funding is acknowledged from the
Thüringer Aufbaubank via the projects Multi-Use (2020FGI0023), SPEQTRA
(2021FE9016), and Quantum Hub Thuringia (2021FGI0041). J.P.T. acknowledges the
funding by the R&D project CEX2019-000910-S, funded by the Ministry of Science
and innovation (MCIN/ AEI/10.13039/501100011033/), from Fundació Cellex,
Fundació Mir-Puig, and from Generalitat de Catalunya through the CERCA
program. J.P.T. also acknowledges support from the project 20FUN02 “POLight”,
that has received funding from the EMPIR programme co-financed by the
Participating States and from the European Union’s Horizon 2020 research and
innovation programme, and financial support from project QUISPAMOL
(PID2020-112670GB-I00) funded by MCIN/AEI /10.13039/501100011033.

## References

## References

  * Gilaberte Basset et al. (2019) M. Gilaberte Basset, F. Setzpfandt, F. Steinlechner, E. Beckert, T. Pertsch, and M. Gräfe, Laser Photonics Rev. 13, 1900097 (2019).
  * Aspden et al. (2013) R. S. Aspden, D. S. Tasca, R. W. Boyd, and M. J. Padgett, New J. Phys. 15, 073032 (2013).
  * Morris et al. (2015) P. A. Morris, R. S. Aspden, J. E. Bell, R. W. Boyd, and M. J. Padgett, Nat. Commun. 6, 5913 (2015).
  * Lemos et al. (2014) G. B. Lemos, V. Borish, G. D. Cole, S. Ramelow, R. Lapkiewicz, and A. Zeilinger, Nature 512, 409 EP (2014), URL https://doi.org/10.1038/nature13586.
  * Gilaberte Basset et al. (2021) M. Gilaberte Basset, A. Hochrainer, S. Töpfer, F. Riexinger, P. Bickert, J. R. León-Torres, F. Steinlechner, and M. Gräfe, Laser Photonics Rev. 15, 2000327 (2021).
  * Schwartz et al. (2013) O. Schwartz, J. M. Levitt, R. Tenne, S. Itzhakov, Z. Deutsch, and D. Oron, Nano Lett. 13, 5832 (2013).
  * Classen et al. (2017) A. Classen, J. von Zanthier, M. O. Scully, and G. S. Agarwal, Optica 4, 580 (2017).
  * Unternährer et al. (2018) M. Unternährer, B. Bessire, L. Gasparini, M. Perenzoni, and A. Stefanov, Optica 5, 1150 (2018).
  * Tenne et al. (2019) R. Tenne, U. Rossman, B. Rephael, Y. Israel, A. Krupinski-Ptaszek, R. Lapkiewicz, Y. Silberberg, and D. Oron, Nat. Photon. 13, 116 (2019).
  * Brida et al. (2010) G. Brida, M. Genovese, and I. R. Berchera, Nat. Photon. 4, 227 (2010).
  * Sabines-Chesterking et al. (2019) J. Sabines-Chesterking, A. McMillan, P. Moreau, S. Joshi, S. Knauer, E. Johnston, J. Rarity, and J. Matthews, Opt. Express 27, 30810 (2019).
  * Casacio et al. (2021) C. A. Casacio, L. S. Madsen, A. Terrasson, M. Waleed, K. Barnscheidt, B. Hage, M. A. Taylor, and W. P. Bowen, Nature 594, 201 (2021).
  * Teich and Saleh (1997) M. C. Teich and B. E. A. Saleh, Cesk. Cas. Fyz 47, 3 (1997).
  * Ndagano et al. (2022) B. Ndagano, H. Defienne, D. Branford, Y. D. Shah, A. Lyons, N. Westerberg, E. M. Gauger, and D. Faccio, Nat. Photon. 16, 384 (2022).
  * Defienne et al. (2021) H. Defienne, B. Ndagano, A. Lyons, and D. Faccio, Nat. Phys. 17, 591 (2021).
  * Camphausen et al. (2021) R. Camphausen, Á. Cuevas, L. Duempelmann, R. A. Terborg, E. Wajs, S. Tisa, A. Ruggeri, I. Cusini, F. Steinlechner, and V. Pruneri, Sci. Adv. 7, eabj2155 (2021).
  * Lloyd (2008) S. Lloyd, Science 321, 1463 (2008).
  * Tan et al. (2008) S.-H. Tan, B. I. Erkmen, V. Giovannetti, S. Guha, S. Lloyd, L. Maccone, S. Pirandola, and J. H. Shapiro, Phys. Rev. Lett. 101, 253601 (2008).
  * Lopaeva et al. (2013) E. Lopaeva, I. R. Berchera, I. P. Degiovanni, S. Olivares, G. Brida, and M. Genovese, Phys. Rev. Lett. 110, 153603 (2013).
  * Pan et al. (2001) J.-W. Pan, C. Simon, Č. Brukner, and A. Zeilinger, Nature 410, 1067 (2001).
  * England et al. (2019) D. G. England, B. Balaji, and B. J. Sussman, Phys. Rev. A 99, 023828 (2019), URL https://link.aps.org/doi/10.1103/PhysRevA.99.023828.
  * Defienne et al. (2019) H. Defienne, M. Reichert, J. W. Fleischer, and D. Faccio, Sci. Adv. 5, eaax0307 (2019).
  * Zhang et al. (2020) Y. Zhang, D. England, A. Nomerotski, P. Svihra, S. Ferrante, P. Hockett, and B. Sussman, Phys. Rev. A 101, 053808 (2020), URL https://link.aps.org/doi/10.1103/PhysRevA.101.053808.
  * Gregory et al. (2020) T. Gregory, P. A. Moreau, E. Toninelli, and M. J. Padgett, Sci. Adv. 6, eaay2652 (2020).
  * Zhao et al. (2022) J. Zhao, A. Lyons, A. C. Ulku, H. Defienne, D. Faccio, and E. Charbon, Opt. Express 30, 3675 (2022).
  * Lahiri et al. (2015) M. Lahiri, R. Lapkiewicz, G. B. Lemos, and A. Zeilinger, Phys. Rev. A 92, 013832 (2015).
  * Fuenzalida et al. (2022) J. Fuenzalida, A. Hochrainer, G. B. Lemos, E. A. Ortega, R. Lapkiewicz, M. Lahiri, and A. Zeilinger, Quantum 6, 646 (2022).
  * Vega et al. (2022) A. Vega, E. A. Santos, J. Fuenzalida, M. Gilaberte Basset, T. Pertsch, M. Gräfe, S. Saravi, and F. Setzpfandt, Phys. Rev. Research 4, 033252 (2022), URL https://link.aps.org/doi/10.1103/PhysRevResearch.4.033252.
  * Kviatkovsky et al. (2020) I. Kviatkovsky, H. M. Chrzanowski, E. G. Avery, H. Bartolomaeus, and S. Ramelow, Sci. Adv. 6, eabd0264 (2020).
  * Paterova et al. (2020a) A. V. Paterova, S. M. Maniam, H. Yang, G. Grenci, and L. A. Krivitsky, Sci. Adv. 6, eabd0460 (2020a).
  * Paterova et al. (2020b) A. V. Paterova, H. Yang, Z. S. D. Toa, and L. A. Krivitsky, Appl. Phys. Lett. 117, 054004 (2020b).
  * Paterova et al. (2021) A. V. Paterova, D. A. Kalashnikov, E. Khaidarov, H. Yang, T. W. W. Mass, R. Paniagua-Domínguez, A. I. Kuznetsov, and L. A. Krivitsky, Nanophotonics 10, 1775 (2021).
  * Töpfer et al. (2022) S. Töpfer, M. Gilaberte Basset, J. Fuenzalida, F. Steinlechner, J. P. Torres, and M. Gräfe, Sci. Adv. 8, eabl4301 (2022).
  * Klyshko (1969) D. Klyshko, Sov. Phys. JETP 28, 522 (1969).
  * Burnham and Weinberg (1970) D. C. Burnham and D. L. Weinberg, Phys. Rev. Lett. 25, 84 (1970).
  * Walborn et al. (2010) S. P. Walborn, C. Monken, S. Pádua, and P. S. Ribeiro, Phys. Rep. 495, 87 (2010).
  * Lahiri et al. (2019) M. Lahiri, A. Hochrainer, R. Lapkiewicz, G. B. Lemos, and A. Zeilinger, Phys. Rev. A 100, 053839 (2019), URL https://link.aps.org/doi/10.1103/PhysRevA.100.053839.
  * Wiseman and Mølmer (2000) H. Wiseman and K. Mølmer, Phys. Lett. A 270, 245 (2000).
  * Yurke et al. (1986) B. Yurke, S. L. McCall, and J. R. Klauder, Phys. Rev. A 33, 4033 (1986), URL https://link.aps.org/doi/10.1103/PhysRevA.33.4033.
  * Zou et al. (1991) X. Y. Zou, L. J. Wang, and L. Mandel, Phys. Rev. Lett. 67, 318 (1991), URL https://link.aps.org/doi/10.1103/PhysRevLett.67.318.
  * Viswanathan et al. (2021) B. Viswanathan, G. B. Lemos, and M. Lahiri, Optics Express 29, 38185 (2021).
  * Kviatkovsky et al. (2022) I. Kviatkovsky, H. M. Chrzanowski, and S. Ramelow, Optics Express 30, 5916 (2022).


Department of Information and Computing Sciences, Utrecht University, the
Netherlands and Department of Mathematics and Computer Science, TU Eindhoven,
the<EMAIL_ADDRESS>Department of Information and Computing
Sciences, Utrecht University, the Netherlands and Department of Mathematics
and Computer Science, TU Eindhoven, the<EMAIL_ADDRESS>Department of Mathematics and Computer Science, TU Eindhoven, the
<EMAIL_ADDRESS>Theory of computation
Computational geometry

# Simply Realising an Imprecise Polyline is NP-hard

Thijs van der Horst  Tim Ophelders  Bart van der Steenhoven

###### Abstract

We consider the problem of deciding, given a sequence of regions, if there is
a choice of points, one for each region, such that the induced polyline is
simple or weakly simple, meaning that it can touch but not cross itself.
Specifically, we consider the case where each region is a translate of the
same shape. We show that the problem is NP-hard when the shape is a unit-disk
or unit-square. We argue that the problem is NP-complete when the shape is a
vertical unit-segment.

###### keywords:

Imprecise polylines, Simple curves, Perturbation

##  1 Introduction

Finding a planar drawing of a graph has been studied widely due to its many
applications, for example in floor-planning and visualisations [7]. Often,
when the to be drawn graphs arise from geometric data, such as road networks,
each vertex already has a predetermined location. In this case, if we insist
on drawing edges as straight line segments, there is a unique corresponding
drawing. Real-world data such as GPS trajectories are often imprecise.
Imprecision is often modeled by assigning to each vertex an imprecision
region, and an assignment of each vertex to a point in its imprecision region
is called a _realisation_.

Algorithms for imprecise data have been considered in the past [5, 8]. A
particularly relevant setting for us is when we know that the underlying data
has no self-intersections. We can then look for a realisation whose drawing
also has no self-intersections. Godau [4] showed that this problem is NP-hard
when the imprecision regions are closed disks of varying radius. In follow-up
work, Angelini et al. [2] showed that the problem remains NP-hard for
straight-line drawings when the regions are all equal-sized disks, diamonds or
squares under the requirement that these regions do not overlap. In this work,
we consider this problem in a very restricted graph class, namely path-graphs.
That is, we are looking for a realisation that is a simple polyline.
Algorithms exist to determine whether a polygon or polyline is weakly simple
[1, 3]. The most relevant related work is that of Löffler [6], who proved the
NP-hardness of determining whether a realisation exists that is a weakly
simple polygon in the case that the imprecision regions are scaled translates
of a fixed shape, such as a segment or circle. Finally, Silveira et al. [9]
showed that the problem is NP-complete for straight-line drawings of graphs
where each vertex has degree exactly one (i.e. the graph is a matching) using
unit-length vertical segments as imprecision regions.

### Definitions and problem statement.

A _polygonal chain_ or _polyline_ is a piecewise-linear path in the plane, and
is given by a sequence $P=(p_{i})_{i=0}^{n}$ of points in the plane, called
vertices. The pieces of $P$ are the $n$ segments connecting consecutive
vertices. With slight abuse of notation, we interpret $P$ as the polyline,
instead of its vertices. An _imprecise polyline_ is given by a sequence of
regions $R=(r_{i})_{i=0}^{n}$ in the plane. We call the polyline
$(p_{i})_{i=0}^{n}$ a _realisation_ of $R$ if $p_{i}\in r_{i}$ for each $i$.

A polyline is _simple_ (or plane) if it does not cross or touch itself. An
_$\varepsilon$ -perturbation_ of a polyline $P=(p_{i})_{i=0}^{n}$ is a
polyline $P^{\prime}=(p^{\prime}_{i})_{i=0}^{n}$ such that
$\|p_{i}-p^{\prime}_{i}\|\leq\varepsilon$ for all $i$. A polyline
$(p_{i})_{i=0}^{n}$ is _weakly simple_ if for every $\varepsilon>0$ there is
an $\varepsilon$-perturbation that is simple. We are interested in the problem
of deciding whether an imprecise polyline $R$ admits a weakly simple
realisation.

### Results and organisation.

We show that the problem is NP-hard already when each region is a translate of
the same shape $S$. In Section 2 we prove this for the case where $S$ is a
unit disk, and discuss how the construction can be adapted to show NP-hardness
for unit squares. It follows that it is hard to compute the infimum
$\varepsilon$ for which a polyline has a simple $\varepsilon$-perturbation
under the $L_{1}$, $L_{2}$, and $L_{\infty}$ norms. In Section 3 we show NP-
completeness when $S$ is a unit-length vertical segment.

##  2 Unit disks as regions

We prove by reduction from planar monotone 3SAT that the problem is NP-hard
when all regions are unit disks. We first introduce planar monotone 3SAT. A
monotone 3CNF formula is a formula
$\varphi(x_{1},\dots,x_{m}):=\bigwedge_{i}C_{i}$ with Boolean variables
$x_{1},\dots,x_{m}$, where each clause $C_{i}$ is either positive (of the form
$(x_{j}\lor x_{k}\lor x_{l})$) or negative (of the form $(\neg x_{j}\lor\neg
x_{k}\lor\neg x_{l})$). A monotone rectilinear layout of a monotone 3CNF
formula is a plane drawing of the incidence graph between its clauses and
variables, in which variables are drawn as disjoint horizontal segments on the
$x$-axis, all positive clauses lie above the $x$-axis, all negative clauses
lie below the $x$-axis, and edges are rectilinear, do not cross the $x$-axis,
and have at most one bend. We may assume for each clause that its central edge
does not bend, see Figure 1. Planar monotone 3SAT is an NP-complete problem
that asks, given a monotone 3CNF formula $\varphi$ with a given monotone
rectilinear layout, whether $\varphi$ is satisfiable. For our reduction we
construct gadgets consisting of imprecise polylines corresponding to
variables, clauses, and edges of the layout. We then show how to connect these
gadgets into a single imprecise polyline that has a weakly simple realisation
if and only if the formula $\varphi$ if satisfiable.

Figure 1: Example of an induced variable-clause graph for planar monotone
3SAT.

### Pivot gadget.

(a)

(b)

Figure 2: 2(a) The pivot gadget. 2(b) A weakly simple realisation, showing a
simple perturbation. Note that this perturbation moves most vertices outside
of their assigned disks.

Before we construct the gadgets for the variables, clauses and edges, we
introduce an auxiliary gadget: the _pivot gadget_. The purpose of the pivot
gadget is to force a given edge of any weakly simple realisation to go through
some fixed point of our choosing. The gadget is illustrated in Figure 2 and
consists of three components. Two of these components together form the pivot
so that the edge of the third component must pass through the center of the
pivot. If we wish to force this edge to pass through $(0,0)$, the coordinates
of the top component will be

$1,\ldots,7\mapsto(-1-\varepsilon,2),(1,2),(1,5),(0,-1),(-1,5),(-1,2),(1+\varepsilon,2)$

for some value $\varepsilon>0$, and the bottom component is a rotated copy of
the top component:

$1^{\prime},\ldots,7^{\prime}\mapsto(1+\varepsilon,-2),(-1,-2),(-1,-5),(0,1),(1,-5),(1,-2),(-1-\varepsilon,-2)\text{.}$

There is some freedom in choosing the placement of regions $1^{\prime\prime}$
and $2^{\prime\prime}$, but to make sure that the realisation passes through
the pivot we require that the x-coordinate of region $1^{\prime\prime}$ is
less than -1, that of region $2^{\prime\prime}$ is greater than 1, and the
tangent lines to the pair of circles $1^{\prime\prime}$ and $2^{\prime\prime}$
all intersect the segment between $(0,-5)$ and $(0,5)$. We can accommodate any
angle of the edge between regions $1^{\prime\prime}$ and $2^{\prime\prime}$ by
choosing $\varepsilon>0$ sufficiently small. Namely, such that the point
$(-\varepsilon,2)$ where we will realise region 1 lies above the tangent lines
from point $(0,0)$ to region $1^{\prime\prime}$, and such that symmetric
properties hold for regions 7, $1^{\prime}$ and $7^{\prime}$.

Figure 2(b) depicts a weakly simple realisation of the pivot gadget. Other
weakly simple realisations may differ in placement for points in regions 1, 7,
$1^{\prime}$, $7^{\prime}$, $1^{\prime\prime}$ and $2^{\prime\prime}$ only,
but the segment connecting $1^{\prime\prime}$ and $2^{\prime\prime}$ must
always pass through $(0,0)$.

######  Lemma 2.1.

For any weakly simple realisation, the segment of the pivot gadget connecting
regions $1^{\prime\prime}$ and $2^{\prime\prime}$ must pass through $(0,0)$.

######  Proof 2.2.

First we consider the top pivot component individually. If we look at the part
of any polyline consisting of only points 3, 4 and 5 then we note that these
will always form a V-shape where the angle can be changed by changing the
location of the points. From the point of view of points 1, 2, 6 and 7 the
lines from 3 to 4 and from 4 to 5 might as well be infinite since with the
defined region placements a line from 1 to 2 can never pass above or below
these lines. This means the lines from 3 to 4 and from 4 to 5 define (closed)
half-planes. In order to avoid intersections points 1 and 2 must be in the
same half-plane for every valid placement. Since any point chosen for region 1
will always be in the left half-plane, we know that the point of region 2 must
also be to the left. At the same time, similar reasoning tells us that the
points of region 6 and 7 must both be in the right half-plane for both lines
between 3, 4 and 5. With the given region placements, the only way to make
this happen is if the points in region 2, 3, 4, 5 and 6 are all placed on a
vertical line, which must be $x=0$ since this is the only line that hits all
of these regions. The same holds for the mirrored bottom pivot component. This
means that points 4 and $4^{\prime}$ lie on the same vertical line. We must
have that point 4 has y-coordinate greater or equal than points $4^{\prime}$
because otherwise the line between the $1^{\prime\prime}$ and
$2^{\prime\prime}$ will always have an intersection. The only realisation
where point 4 is not below point $4^{\prime}$ is one where they are both
placed at $(0,0)$. Since the tangent lines to the pair of circles
$1^{\prime\prime}$ and $2^{\prime\prime}$ all intersect the segment between
$(0,-5)$ and $(0,5)$, any line between these two regions cannot pass
completely above or below the pivot gadget. Thus, for any weakly simple
realisation, the point $(0,0)$ then becomes the only position where an edge
can pass from one side of the pivot gadget to the other without intersections.

######  Lemma 2.3.

Any choice of points for regions $1^{\prime\prime}$ and $2^{\prime\prime}$
such that the segment connecting them passes through $(0,0)$ has a
corresponding weakly simple realisation of the pivot gadget.

######  Proof 2.4.

Observe that, similar as before, the points of regions 2 to 6 and $2^{\prime}$
to $6^{\prime}$ can be placed on a vertical line such that an edge from region
$1^{\prime\prime}$ to $2^{\prime\prime}$ through $(0,0)$ does not intersect
any of them. Furthermore, we chose $\varepsilon$ such that the regions 1, 7,
$1^{\prime}$ and $7^{\prime}$ do not cause any intersections. To see this
consider region 1, for which we can choose point $(-\varepsilon,2)$ in a
realisation. We have chosen $\varepsilon$ such that this point lies above the
tangent lines from point $(0,0)$ to region $1^{\prime\prime}$, which means it
lies above any edge between region $1^{\prime\prime}$ and $2^{\prime\prime}$
that goes through $(0,0)$. Therefore the edge from region 1 to 2 does not
intersect the edge from $1^{\prime\prime}$ to $2^{\prime\prime}$, and the same
holds for the edges from the other three corner points of the gadget.

### Variable gadget.

For the reduction we want to have a variable gadget that can take on two
discrete states, one for true and one for false, such that the difference
between them can be used to allow for different behaviour. To this end, we
devised our variable gadget as seen in Figure 3(a). The exact coordinates and
order of the points is as follows, assuming the leftmost point as our $(0,0)$
and $l$ as an arbitrary value such that $l>8$:

$1,\ldots,6\mapsto(0,0),(8,0),(5,2),(5,-2),(2,0),(l,0)$

######  Lemma 2.5.

There are exactly two distinct weakly simple realisations for the regions of
the variable gadget.

######  Proof 2.6.

To see why this is the case first note that for any realisation of the
regions, the only way a line from region 5 to 6 does not cross the line from
region 3 to 4 is if it goes above or below it. The same holds for the line
from region 1 to 2. Due to the placement of the regions, these lines can only
go above the line from 3 to 4 if the point of 3 is placed at the very bottom
$(5,1)$ of its region and both endpoints of the line going over it are placed
at the very top of their regions at $y=1$. A similar property holds for when a
line needs to go below the line between 3 and 4. Finally, note that putting
the points of regions 1, 2, 5 and 6 all on the same horizontal line does not
lead to a weakly simple polyline.

If the final horizontal line from region 5 to 6 is above the blocking vertical
line between regions 3 and 4, then the gadget is in its false state as seen in
Figure 3(b). We consider the situation where it is below as the true state
(Figure 3(c)).

(a)

(b)

(c)

Figure 3: 3(a) The variable gadget. 3(b) The false state. 3(c) The true state.

### Clause gadget.

The clause gadget is used to represent the disjunctions of the shape
$(x_{1}\vee x_{2}\vee x_{3})$, where the variables can also all be negated.
The initial placement of the regions for this gadget can be seen in Figure
4(a). In these figures, for sake of clarity, we use an X-shape to
schematically represent that a pivot gadget is placed at that position. The
regions $x_{1}$, $x_{2}$ and $x_{3}$ correspond to the literals of the clause
and the regions 1, 2, 3 and 4 are used to put restrictions on these literals.
The exact positions of the points of this gadget are as follows, taking the
left top point as $(0,0)$:

$1,2,3,4\mapsto(0,0),(0,-5),(6,-5),(6,0)$

We place the point for $x_{1}$ at $(1,-3)$, $x_{2}$ at $(2,-4.6)$ and $x_{3}$
at $(5,-3)$. The construction used to connect the regions of these literals to
variable gadgets and the exact placement of the pivot gadgets is explained in
a later section. For now, it is only necessary to know that when a variable is
false, then the part of the polyline going to the literal point can only go
completely vertical through the pivot gadget at the bottom, or completely
horizontal through the pivot gadgets at the sides. The regions of $x_{1}$,
$x_{2}$ and $x_{3}$ are placed precisely so that in this situation there is
exactly one realisation that does not intersect the pivot gadget. We shall
refer to the position of a variable in this realisation as its _false
position_ and say that it is _covered_ in a solution if it lies in the
interior of the polyline defined by the corner points of the clause gadget. If
the variable is true then the line can be placed at an angle through the pivot
gadget, meaning that the literal point can be be realised in multiple
different ways. Specifically we shall call the leftmost, bottommost and
rightmost positions of $x_{1}$, $x_{2}$ and $x_{3}$ their respective _true
position_. The clause gadget simulates clauses of the Boolean formula
according to the following lemma:

######  Lemma 2.7.

For every choice of two of the three literals there exists a realisation that
uncovers their false positions, and any realisation uncovers at most two false
positions.

######  Proof 2.8.

The false positions of the literals $x_{1}$, $x_{2}$ and $x_{3}$ are $(1,-2)$,
$(3,-4.6)$ and $(5,-2)$ respectively. Due to the placements of region 1 and 2,
the only way to uncover position $(1,-2)$ is by placing the points of both of
these regions at the rightmost positions, so at $(1,0)$ and $(1,-5)$.
Similarly, the only way to uncover the false position of $x_{3}$ is by placing
the points of region 3 and 4 at the leftmost positions $(5,-5)$ and $(5,0)$.
However, this means the line from region 2 to 3 is a horizontal line from
$(1,-5)$ to $(5,-5)$. The false position of $x_{2}$ lies above this line which
means it is not uncovered. Since this choice of points of regions 1 to 4 is
the only one that uncovers the false positions of both $x_{1}$ and $x_{3}$, it
is impossible to uncover all three false positions simultaneously.

We can easily see that for any choice of two literals, we can uncover both
false positions simultaneously by considering the separate cases. To uncover
the false positions of both $x_{1}$ and $x_{2}$ we can choose for regions 1
and 2 the rightmost position, for region 3 the topmost position and for region
4 any position inside the region. A corresponding (part of a) weakly simple
realisation is illustrated in Figure 4(b), where an orange line indicates that
a literal is false and a blue line that it is true. We have already described
the case for $x_{1}$ and $x_{3}$ (see Figure 4(c)) and the case for $x_{2}$
and $x_{3}$ (Figure 4(d)) is symmetric to that of $x_{1}$ and $x_{2}$. The
important observation is that for any weakly simple realisation, at least one
of the variable points cannot be in its false position and must thus be set to
true, just like in a disjunction.

(a)

(b)

(c)

(d)

Figure 4: 4(a) The clause gadget, with realisations where 4(b) $x_{3}$, 4(c)
$x_{2}$, or 4(d) $x_{1}$ is true.

### Connecting variables and clauses.

For the reduction construction we still need a way to connect the variable
gadgets to the clause gadgets correctly. For this we look at the shape of the
induced variable-clause graphs we get for planar monotone 3SAT. We have seen
an example before in Figure 1. Clauses are always connected to variables in an
either downward or upward facing E-shape. To preserve the planarity of this
graph, our reduction should follow this shape to a close enough degree. So the
clause gadget is to be placed directly above one of the variable gadgets and
the other two variable gadgets connect to it with a bend from the side.

We first look at the connection from a right variable to a clause. The wire
gadget in this case involves three regions and two pivot gadgets as seen in
Figure 5(a). Here region 1 is horizontally aligned with the variable gadget of
the variable corresponding to the right literal of the clause. Based on Figure
3, we place these variable regions between region 2 and 6, which means
depending on the state of the variable gadget our realisation has a horizontal
line at the top (orange in Figure 5(a)) if the state is false and at the
bottom (blue) if the state is true. We denote the position of region 1 as
$(0,0)$. Region three is the right literal region of the clause gadget. The
corresponding two states of the clause gadget are drawn in blue and orange.
The position of this region is determined by the clause gadget and it should
not depend on the wire gadget. Let region 3 to be positioned at $(-a,b)$ for
some $a,b>0$. For our wire gadget, we place region 2 at position $(1,b+1)$ and
place two pivot gadgets at $(1-\frac{a}{2},b+1)$ and $(0,1+\frac{b}{2})$,
oriented appropriately. We stretch the variable-clause graph without changing
its validity, so that $a$ and $b$ are large enough that the components of the
wire gadget do not overlap.

(a)

(b)

(c)

(d)

Figure 5: 5(a) The right wire gadget to connect a variable to a clause.
Realisations 5(b) when both are in the false state, 5(c) where the variable is
in its false state and the clause in its true state and 5(d) with the variable
gadget in its true state.

######  Lemma 2.9.

If a variable gadget for $x_{i}$ is in its false state, any weakly simple
realisation places $x_{i}$ in its false position. Otherwise $x_{i}$ can be
placed in either its true or false position.

######  Proof 2.10.

If the variable gadget is in its false state, its horizontal line will be at
the top of region 1. The only choice of position for point in region 1 that
prevents a crossing with this line is the very top of the region $(0,1)$. Due
to the pivot gadget, the line to region 2 must then be perfectly vertical in
which case it only touches the region at position $(0,b+1)$, so the point of
that region must be placed there. Similarly due to the second pivot gadget the
point of region 3 must be placed at position $(a,b+1)$, which is its false
position. This realisation can be seen in Figure 5(b) and is the only one that
does not directly cause intersections. If the variable gadget is in its false
state but the clause gadget in its true state then this will always lead to a
crossing. An example of this can be seen in Figure 5(c). If the variable
gadget is in the true state the horizontal line is at the bottom of region 1
which means it does not constrain our choice of point in this region. Most
notably, we can place a point at position $(-1,0)$ which then propagates to
the possibility of choosing point $(1,b+2)$ in region 2 and true position
$(a+1,b)$ for region 3. This means there will be no crossings on this part of
the polyline regardless of the state that the clause gadget is in (see Figure
5(d)). Note that in contrast to the false realisation, the described true
realisation is not the only one that is possible. Any choice of coordinates
that leads to the point of the third region being to the right of the blue
line and not causing any crossings is valid.

The wire gadget for connecting the left literal of a clause to its variable
gadget is a mirrored version of the right wire gadget. The middle wire gadget
is a simplified version needing only one pivot gadget, as this connection does
not need to make a bend. All three versions of the wire gadget can be seen in
effect in Figure 6.

### The reduction.

A general reduction method should be able to convert any monotone rectilinear
layout of a planar monotone 3SAT formula into a sequence of unit disks for
which there exists a weakly simple realisation if and only if the formula is
satisfiable.

The general construction works as follows. First we place all gadgets as
prescribed by the layout obtained from the planar monotone 3SAT instance.
Next, we connect the gadgets in a planar manner. For this, we connect the
variables from left to right as in Figure 6. We connect the gadgets in the top
half of the construction by processing the clauses on the outer face (that lie
above the $x$-axis) as follows, and connecting the results from left to right.
Connect the clause to its right wire (and its pivot gadgets), then recursively
process and connect the clauses in the region enclosed by its right and middle
wire, then connect the middle wire, then recursively process and connect the
clauses in the region enclosed by the middle and left wire, and finally
connect the left wire. The gadgets in the bottom half are connected in a
symmetric manner. Due to the nature of our variable gadgets, making wire
gadget connections from below automatically results in getting the negated
value of the variable, which is in line with the definition of planar monotone
3SAT. Furthermore, the regions of the wire gadgets in the bottom half do not
interfere (cause crossings) with those in the top half, since the horizontal
line of the variable gadget ensures they remain separated even if their
regions overlap.

We give an example for the very simple case where we have only three variables
and a single clause as seen in Figure 6(a). After construction we end up with
a sequence of regions. In Figure 6(b) we see a potential weakly simple
realisation where the variable $x_{2}$ is set to true. Another example is
shown in Figure 6(c) where instead the $x_{1}$ variable gadget is true. It is
for this example of course also possible for multiple variables gadgets to be
in the true state simultaneously.

(a)

(b)

(c)

Figure 6: Example of the construction for variable-clause graph 6(a). The
weakly simple realisation in 6(b) sets $x_{2}$ to true and the realisation in
6(c) sets $x_{1}$ to true.

A potential issue could be that when we have nested clauses in the variable-
clause graph, we have insufficient space to fully draw the clause gadget and
its wires in the enclosure defined by the outer clauses. This is remedied by
scaling the variable-clause graph, preserving planarity.

Correctness of the reduction follows from correctness of the individual
gadgets, for which we already argued when describing them. Furthermore, each
gadget and connection uses a constant number of regions and their positions
can be determined based on the variable-clause graph, which leads to the
reduction being polynomial in size and time. This allows us to conclude the
following:

######  Theorem 2.11.

Given a sequence of unit disks, the problem of deciding if there exists a
weakly simple realisation for this sequence is NP-hard.

In our construction, if there is a weakly simple realisation, then there is
one that uses only the top, right, bottom or leftmost point of each
imprecision region. Hence, if we use a different imprecision region that
contains these four points, there will still be a weakly simple realisation if
there was one initially. And if each region is a subset of the original, then
if there is a weakly simple realisation in the second, then there is also one
in the original.

The problem we considered can also be looked at from a different point of
view. One could consider the center of each region in the sequence to be a
point of an input polyline and the regions themselves denoting how we are
allowed to perturb these points. In that case the setting of unit disks that
we discussed can be seen as being allowed to move the point unit distance
under the $L_{2}$ norm. Therefore, it might be interesting to consider the
cases for the $L_{1}$ and $L_{\infty}$ norms. Under the $L_{1}$ norm the
regions are diamond-shaped. By the above observation the problem remains NP-
hard. Furthermore, we can consider the square-shaped regions of the
$L_{\infty}$ norm as the $L_{1}$ norm if we rotate everything by 45 degrees
and scale the gadgets appropriately. This means that the problem stays NP-hard
in this case.

##  3 Vertical segments as regions

Next to the previously discussed cases we consider one additional scenario:
what if the regions are all vertical segments of the same size? We show that
even here, the problem remains NP-hard. We can prove this again using a
reduction from planar monotone 3SAT. Since the reduction is very similar to
the one from Section 2 we shall keep the description concise. In our reduction
we will work with vertical segments of length 2 as it makes the coordinates
clearer, but this can easily be adapted to unit-length vertical segments.

### Pivot gadget.

Like before, in our reduction we are going to want to force lines to go
through certain points by using a pivot gadget. However, the placement of
regions used for disks will not work for vertical segments, since in this case
it is not possible to place the points for regions 2 to 6 (and $2^{\prime}$ to
$6^{\prime}$) all on a vertical line. However, due to the vertical segments as
regions only allowing a single choice for the x-coordinate of their point, a
simpler version of the pivot gadget as seen in Figure 7(a) can be constructed.
It is the same as the pivot gadget for unit disks, except we replace regions
2, 3, 5 and 6 by two regions at the exact same position (2 and 4 in the
figure) and do the same for the bottom component. Similar to before, the pivot
gadget requires any line of a weakly simple realisation to pass through the
exact center as seen in Figure 7(b). There is however the difference that now
it is not possible to rotate the gadget due to regions being restricted to
vertical segments.

(a)

(b)

Figure 7: 2(a) The pivot gadget for vertical segments. 2(b) A weakly simple
realisation.

### Variable gadget.

The variable gadget from Section 2 only makes use of the topmost and
bottommost position of the regions. For this reason the variable gadget can
stay exactly the same for the situation with vertical segments.

### Clause gadget.

The clause gadget from Section 2 fundamentally makes use of both the vertical
and horizontal extremes of the disk regions. This means that we need to define
a new clause gadget that does work for vertical segments. The new clause
gadget places the regions at the following positions in order:

$1,\ldots,6\mapsto(0,0),(0,-3),(4,-5),(6,-5),(10,-3),(10,0)$

With two pivot gadgets placed with centers at $(2,-4)$ and $(8,-4)$. The
regions for the literals should be placed at $(1,-4)$, $(5,-6)$ and $(9,-4)$
for $x_{1}$, $x_{2}$ and $x_{3}$ respectively. A simplified visualisation of
construction can be seen in Figure 8(a). For the literal regions we force the
point to be placed at its topmost position when the literal it corresponds to
is false (orange points in the figure). Just like before, we refer to this
position as the false position of the literal. Only if the literal is true is
the point allowed to be placed at its true position, the bottom of the region
(blue points). The exact construction between variable and clause gadget to
make this construction work is explained in a later part. In the same vein as
before, the clause gadget can only uncover the false positions of at most two
literal regions at the same time. In Figure 8(b) we see this happening for
$x_{2}$ and $x_{3}$, meaning that $x_{1}$ needs to be true to not cause
crossings. In Figure 8(c) this is the case for $x_{2}$ and a third realisation
exists for $x_{3}$.

(a)

(b)

(c)

Figure 8: 8(a) The clause gadget for vertical segments, with realisations
where 8(b) $x_{1}$ or 8(c) $x_{2}$ should be true.

### Wire gadget.

Just like before, we need to define a wire gadget to connect literal regions
at the clause gadget to the corresponding variable gadgets. The gadget
consists of three regions (one of which the literal region) and two pivot
gadgets. The wire is visualised in Figure 9 together with the two important
weakly simple realisations. Region 1 is again placed at $(0,0)$ horizontally
aligned with a variable gadget. Then assuming literal region 3 as positioned
at $(-a,b)$ for $a,b>0$, we get that region 2 must be placed at $(2,b)$ and
the two pivot gadgets at $(1,\frac{b}{2})$ and $(\frac{-a}{2}+1,b)$. By
placing these pivot gadgets exactly in the middle between two consecutive
regions we get an alternating pattern in the solution polyline of the points
lying at the very top or at the very bottom of their region, as can be seen in
Figure 9(b) and Figure 9(c). This idea can also be used to make a connection
for the middle literal of the clause gadget where, in contrast to the case
with unit disks, we do need an intermediate region and two pivot gadgets this
time.

(a)

(b)

(c)

Figure 9: 9(a) The right wire gadget for vertical segments. Weakly simple
realisations 9(b) where both the clause and variable gadget are in its false
state and 9(c) where the variable gadget is in its true state.

### The reduction.

Before looking at the full reduction, we can argue that the setting of
vertical segments is in fact in NP. Our argument is similar to that used by
Silveira et al. [9], where they argue for that a similar problem lies in NP
using the fact that any solution can be represented as a solution to a system
of linear constraints that can be guessed in nondeterministic polynomial time.
Consider a weakly simple realisation, and a corresponding simple perturbation.
This simple perturbation induces an order type: for any vertex and any edge,
record whether that vertex lies on, above, or below the supporting line of the
edge. This order type induces a polynomial size system of linear constraints,
and by picking a sufficiently small perturbation, we can ensure that the
weakly-simple realisation lies in the closure of the solution space of this
system of constraints. We can in nondeterministic polynomial time guess this
system of linear constraints, and find a realisation in its closure. This
realisation is then used as input to one of the algorithms [1, 3] to verify
that the realisation is weakly simple. Since the output of these algorithms
depend only on the order type, they will report that the realisation is indeed
weakly simple. Theorem 3.1 follows.

######  Theorem 3.1.

Given a sequence of unit-length vertical segments, deciding if there exists a
weakly simple realisation for these regions is in NP.

With the gadgets adapted to work for when the regions are vertical segments,
the remainder of the reduction stays the same. We convert a monotone
rectilinear layout of a formula to an instance of our problem by first
constructing all variable gadgets, then all clauses and wires of the top half
in order from right to left and finally all clauses and wires of the bottom
half from left to right.

######  Theorem 3.2.

Given a sequence of unit-length vertical segments, the problem of deciding if
there exists a weakly simple realisation for these regions is NP-complete.

##  4 Discussion

We showed that deciding if an imprecise polygon has a weakly simple
realisation is NP-hard when each region is a unit disk, unit square, or
vertical unit segment. By growing each region slightly, the same follows for
deciding whether a simple realisation exists. Whereas the case of vertical
segments is NP-complete, it is unclear whether the problems of Section 2 lie
in NP, as it is unclear whether polynomially many bits suffice to encode a
solution. The settings of Section 2 lie in the complexity class
$\exists\mathbb{R}$, and we wonder if these settings are
$\exists\mathbb{R}$-hard.

## References

  * [1] Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba D. Tóth.  Recognizing weakly simple polygons.  Discret. Comput. Geom., 58(4):785–821, 2017.
  * [2] Patrizio Angelini, Giordano Da Lozzo, Marco Di Bartolomeo, Giuseppe Di Battista, Seok-Hee Hong, Maurizio Patrignani, and Vincenzo Roselli.  Anchored drawings of planar graphs.  In GD, volume 8871 of Lecture Notes in Computer Science, pages 404–415. Springer, 2014.
  * [3] Hsien-Chih Chang, Jeff Erickson, and Chao Xu.  Detecting weakly simple polygons.  In SODA, pages 1655–1670. SIAM, 2015.
  * [4] Michael Godau.  On the difficulty of embedding planar graphs with inaccuracies.  In GD, volume 894 of Lecture Notes in Computer Science, pages 254–261. Springer, 1994.
  * [5] Maarten Löffler.  Data Imprecision in Computational Geometry.  PhD thesis, Utrecht University, 2009.
  * [6] Maarten Löffler.  Existence and computation of tours through imprecise points.  Int. J. Comput. Geom. Appl., 21(1):1–24, 2011.
  * [7] Takao Nishizeki and Md. Saidur Rahman.  Planar Graph Drawing, volume 12 of Lecture Notes Series on Computing.  World Scientific, 2004.
  * [8] Marcel Roeloffzen.  Finding structures on imprecise points.  Master’s thesis, TU Eindhoven, 2009.
  * [9] Rodrigo I. Silveira, Bettina Speckmann, and Kevin Verbeek.  Non-crossing paths with geographic constraints.  Discret. Math. Theor. Comput. Sci., 21(3), 2019.