# Cavity-like strong coupling in macroscopic waveguide QED using three coupled
qubits in the deep non-Markovian regime

Sofia Arranz Regidor<EMAIL_ADDRESS>Department of Physics, Engineering
Physics and Astronomy, Queen’s University, Kingston, Ontario, Canada, K7L 3N6
Stephen Hughes  Department of Physics, Engineering Physics and Astronomy,
Queen’s University, Kingston, Ontario, Canada, K7L 3N6<EMAIL_ADDRESS>
(August 27, 2024)

###### Abstract

We introduce a three qubit waveguide QED system to mimic the cavity-QED strong
coupling regime of a probe qubit embedded in atom-like mirrors, which was
realized in recent experiments. We  then extend this system into the deep non-
Markovian regime and demonstrate the profound role that retardation plays on
the dressed resonances, allowing one to significantly improve the polariton
lifetimes (by many orders of magnitude), tune the resonances, as well as
realize Fano-like resonances and simultaneous coupling to multiple cavity
modes. Exact Green function solutions are presented for the spectral
resonances, and the  quantum dynamics are simulated using matrix product
states, where we demonstrate additional control of the cavity-QED system using
chiral probe qubits.  We also show example qubit dynamics with both one and
two quantum excitations.

Introduction.—Cavity-QED phenomena have been studied both theoretically and
experimentally for various cavity system (e.g., see Refs. [1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]), showing a variety of applications
and rich quantum physics. These cavity systems are typically characterized by
Markovian decay dynamics, where interactions between system operators are
essentially instantaneous. One of the key signatures of such systems is the
“strong coupling” regime, where the intrinsic quantum coherence overcomes
system losses.

A fundamentally different dynamic can be realized using waveguide QED systems
[18, 19, 20, 21, 22, 23, 24, 25, 26, 27], which allow one to efficiently
couple quantum emitters and two level systems acting as qubits, over
macroscopic length scales. Here the waveguide modes mediate the photon
coupling between the qubits, and the system can have a non-Markovian memory
[28, 29, 30, 31, 32]. Coherent feedback systems can thus lead to non-trivial
dynamical protocols such as population trapping, and photon transport beyond
the usual dipole-dipole interaction regimes [33, 34, 35]. For example, these
waveguide-QED regimes can be experimentally realized in chip-based systems
with semiconductor quantum dots and semiconducting circuits [36, 37, 25].

It is interesting to explore when these two disparate systems  (cavities and
waveguides) overlap with each other, in terms of the connecting physics, and
in particular if one can realize familiar cavity-QED phenomena with richer
non-Markovian dynamics than what is often assumed with traditional cavities.
To help address this question, recently it was experimentally demonstrated how
one can achieve cavity-QED phenomena, such as vacuum Rabi oscillations and
qubit strong coupling, by simply having some of the qubits act as “atom-like
mirrors” [38, 39]. A schematic representation of this scenario is shown in
Fig. 1, where a probe qubit is situated between two external mirror qubits.
Reference [38] showed how the usual strong coupling regime can be reached by
precisely positioning the external qubits, which can behave as a collective
entangled state, creating a cavity-like system. This regime is mediated by
coherent qubit interactions [38]. This recent experimental achievement  allows
one to manipulate correlated dissipation and coherence of quantum emitter
arrays, with engineerable feedback. Strong coupling dynamics have also been
theoretically demonstrated for qubits at a waveguide mode edge [40].

Figure 1: Schematic of three qubits on a waveguide.

Motivated by these emerging experiments on tunable quantum networks, here we
present a study of qubit-mirrors in the deep non-Markovian regime, and show
how longer time delays between the qubits result in much richer coupling
dynamics than traditional cavity-QED, yielding spectrally narrow linewidths
and the simultaneous coupling to multiple cavity modes for sufficiently long
round trip times. We first employ a classical scattering theory, solving for
the exact Green function to analyze the spectral resonances beyond the
Markovian approximation, in a strong coupling regime. We find that the main
two Rabi split resonances (from an infinite set) depend on the mirror-qubit
delay times, which significantly narrow when the retardation increases, and
recover the Markovian limit solution  only for small delay times. We show
explicitly how a non-Markovian delay time significantly improves the cavity-
QED resonances. We also study this problem from the viewpoint of matrix
products states (MPS), which allows us to solve the quantum Hamiltonian also
in the non-Markovian regime [41] as well as the nonlinear regime. We directly
show how the lifetimes improve dramatically for long delay times when the
retardation is considered, giving a method to precisely control the coherence
times of these novel polariton states. In addition, we investigate the time
dynamics for a chiral probe qubit [42, 43],  and explore qubit dynamics with
one and two initial quantum excitations.

Classical Scattering Theory.—Light propagation through an arbitrary dielectric
medium can be described in terms of the mode solutions to the Helmholtz
equation:
$\nabla\times\nabla\times\mathbf{f}_{\lambda}(\mathbf{r})-\frac{\omega_{\lambda}^{2}}{c^{2}}\epsilon(\mathbf{r})\mathbf{f}_{\lambda}(\mathbf{r})=0,$
where $\epsilon(\mathbf{r})$ describes the relative permittivity of the
structure and $\mathbf{f}_{\lambda}(\mathbf{r})$ are generalized field modes
with a harmonic $e^{-i\omega t}$ time dependence. For the waveguide, we
consider a photonic nanowire, supporting lossless waveguide modes
$\mathbf{f}_{k_{\omega}}(\mathbf{r})=\sqrt{\frac{1}{L_{W}}}\mathbf{e}_{k_{\omega}}(\bm{\rho})e^{ik_{\omega}x}$,
with $\mathbf{e}_{k_{\omega}}(\bm{\rho})$ the mode solution, normalized from
$\int_{A_{\rm
w}}\epsilon(\bm{\rho})\mathbf{e}_{k_{\omega}}^{*}(\bm{\rho})\cdot\mathbf{e}_{k_{\omega}^{\prime}}(\bm{\rho})=\delta_{k_{\omega},k_{\omega}^{\prime}}$,
where $A_{\rm w}$ is the spatial area, and  $L_{W}$ is the length of the
waveguide. The waveguide Green function is [44]

$\displaystyle\mathbf{G}_{\rm w}(\mathbf{r},\mathbf{r^{\prime}},\omega)$
$\displaystyle=\frac{i\omega}{2v_{g}}\Big{[}\Theta(x-x^{\prime})\mathbf{e}_{k_{\omega}}(\bm{\rho})\mathbf{e}^{*}_{k_{\omega}}(\bm{\rho}^{\prime})e^{ik_{\omega}(x-x^{\prime})}$
$\displaystyle+\Theta(x^{\prime}-x)\mathbf{e}^{*}_{k_{\omega}}(\bm{\rho})\mathbf{e}_{k_{\omega}}(\bm{\rho}^{\prime})e^{ik_{\omega}(x^{\prime}-x)}\Big{]},$
(1)

where the terms preceded by Heaviside functions correspond to forward and
backwards propagating modes, respectively, and $v_{g}$ is the group velocity
at the frequency on interest. Since the modes are translationally invariant in
$x$, then $\mathbf{e}_{k_{\omega}}({\bf
r})=\mathbf{e}_{k_{\omega}}(\bm{\rho})$. The notation can be easily
generalized for photonic crystal waveguides [44].

Next, we consider adding in a single qubit treated at the level of a
polarization dipole. The polarizability of the qubit, with resonance energy
$\omega_{0}$, is described through the polarizability tensor
${\bm{\alpha}}_{0}=\alpha_{0}{\bf n}_{d}{\bf n}_{d}^{\dagger}$ , where ${\bf
n}_{d}$ is a unit vector describing the polarization direction of the qubit
dipole, and $\alpha_{0}={A_{0}\omega^{2}}/{(\omega_{0}^{2}-\omega^{2})}$ is
the “bare polarizability” volume [45], i.e., it does not include radiative
coupling effects to the environment, and
$A_{0}=2\omega_{p}d_{0}^{2}/\epsilon_{0}\hbar$.

The total electric field in the waveguide is ($\omega$ is implicit)
$\mathbf{E}(\mathbf{r})=\mathbf{E}^{\rm
h}(\mathbf{r})+\mathbf{G}(\mathbf{r},\mathbf{r}_{d})\cdot{\bm{\alpha}}_{0}\cdot{\bf
E}({\bf r}_{d})$, where ${\bm{\alpha}}_{0}$ has units of volume, ${\bf r}_{d}$
is the position of the qubit,  $\mathbf{E}^{\rm h}(\mathbf{r})$ is the
homogeneous field solution in the absence of the qubits. It is also convenient
to exploit the Dyson equation, ${\bf G}^{(1)}={\bf G}+{\bf
G}\cdot{\bm{\alpha}}_{0}\cdot{\bf G}^{(1)}$, where the ‘1’ superscript denotes
the GF with the addition of one  qubit, so that

$\mathbf{E}(\mathbf{r})=\mathbf{E}^{\rm
h}(\mathbf{r})+\mathbf{G}^{(1)}(\mathbf{r},\mathbf{r}_{d})\cdot{\bm{\alpha}}_{0}\cdot{\bf
E}^{\rm h}({\bf r}_{d}),$ (2)

where $\mathbf{G}^{(1)}(\mathbf{r},{\bf
r^{\prime}})={\mathbf{G}(\mathbf{r},{\bf r^{\prime}})}/{(1-\alpha_{0}{\bf
n}_{d}^{\dagger}\cdot{\bf G}_{d}\cdot{\bf n}_{d})}$. Alternatively, one can
introduce the renormalized polarizability,
${\bm{\alpha}}^{(1)}={\bm{\alpha}}_{0}+\ {\bm{\alpha}}_{0}\cdot{\bf
G}_{d}\cdot{\bm{\alpha}}$, with ${\bf G}_{d}\equiv{\bf G}({\bf r}_{d},{\bf
r}_{d})$. The polarizability, including coupling to the medium is

${\bm{\alpha}}^{(1)}=\frac{A_{0}\omega_{0}^{2}\,{\bf n}_{d}^{\dagger}{\bf
n}_{d}}{\omega_{0}^{2}-\omega^{2}-i\omega_{0}\gamma},$ (3)

where $\gamma=A_{0}\omega_{0}\,{\bf n}_{d}^{\dagger}\cdot{\rm Im}{\bf
G}_{d}\cdot{\bf n}_{d}=\gamma_{\rm L}+\gamma_{\rm R}$, and we assume the qubit
is symmetrically coupled to both forward and backwards modes  (unless stated
otherwise). It is also useful to define the normalized scattered field at the
qubit, from $\tilde{E}_{\rm s}^{(1)}({\bf r}_{d})={\bm{\alpha}}_{0}\cdot{\bf
G}^{(1)}({\bf r}_{d},{\bf r}_{d})\cdot{\bf n}_{d}$.

Next we consider an injected waveguide mode from the left,  $\mathbf{E}^{\rm
h}(\mathbf{r})=\mathbf{f}_{k_{\rm
h}}(\mathbf{r})=\sqrt{\frac{1}{L_{W}}}\mathbf{e}_{k_{\rm
h}}(\mathbf{r})e^{ik_{\rm h}x}$.  The reflection coefficient from one qubit is

$r_{1}(\omega)=\frac{{\bf E}_{\rm r}(\mathbf{r};x\rightarrow-\infty)}{{{\bf
E}^{\rm h}}(\mathbf{r};x\rightarrow-\infty)}=\frac{i\omega_{0}\gamma
e^{i\phi(x_{d})}}{\omega_{0}^{2}-\omega^{2}-i\omega_{0}\gamma},$ (4)

where $\mathbf{E}_{\rm r}$ is the reflected field, and $\phi(x_{d})$ is a
positional dependent phase; the transmission coefficient can be derived in a
similar way. Thus, we see that the waveguide qubit indeed acts as a mirror,
with a Lorentzian lineshape, whose spectral width is determined by the
radiation decay rate. The strategy for obtaining atom-like mirrors then
becomes clear: we can surround a single qubit with two mirror qubit and expect
the system to mimic a Fabry-Pérot resonator. To make this clearer, we now add
in another qubit, acting as a second resonant mirror, separated from the first
by a distance $L$. Assuming identical mirror qubits, we can use the Dyson
equation again to derive the total reflection coefficient as

${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r_{\rm
2dots}}(\omega)=\frac{r_{1}(\omega)\left[1+e^{2ikL}+2r_{1}(\omega)e^{2ikL}\right]}{1-r_{1}^{2}(\omega)e^{2ikL}},$
(5)

which is precisely the solution expected from a 1d cavity with two identical
mirrors with a complex reflection coefficient, $r_{1}$.  For simplicity, he
have neglected the mirror phase terms. The mirror round trip time is
$\tau_{\rm RT}={n_{g}L}/{c}=2\tau$ (with $n_{g}$ the group index), which will
yield cavity modes with a free spectral range (FSR) $\Delta\omega_{\rm
FSR}\approx 2\pi/\tau_{\rm RT}$. Note if we make a rotating wave
approximation,  $\omega_{0}^{2}-\omega^{2}\approx
2\omega_{0}(\omega_{0}-\omega)$, then we recover the quantum mechanically
derived results [46].

We next add in a probe (third) qubit, also with $\omega_{p}=\omega_{0}$, and
use the Dyson equation again to derive an explicit solution for the Green
function and for the scattered fields. At the probe qubit (${\bf r}_{p}$), we
have

$\displaystyle\tilde{E}_{\rm s}^{(3)}({\bf r}_{p})$
$\displaystyle={\bm{\alpha}_{0}}\cdot{\bf G}^{(3)}({\bf r}_{p},{\bf
r}_{p})\cdot{\bf
n}_{p}=\frac{i\omega_{p}\tilde{\gamma}_{p}}{\omega_{p}^{2}-\omega^{2}-i\omega\tilde{\gamma}_{p}},$
(6)

with the modified decay rate

$\displaystyle\tilde{\gamma}_{p}=\gamma_{p}$
$\displaystyle\bigg{[}1+e^{ikL}r_{1}(\omega)+(e^{ikL/2}+e^{ikL/2}e^{ikL}r_{1}(\omega))\times$
$\displaystyle\ \
\frac{r_{1}(\omega)\left(e^{ikL/2}+r_{1}(\omega)e^{ikL/2}e^{ikL}\right)}{1-r_{1}^{2}(\omega)e^{2ikL}}\bigg{]},$
(7)

which is an exact solution. It is also straightforward to derive the scattered
field from the mirror qubits, but this solution alone is enough to probe the
system resonances.

Strong Coupling Regime.— To connect to the familiar cavity-QED strong coupling
regime, we can study the complex poles in Eq. (6). Strong coupling is
optimally achieved when the modified probe decay rate approaches infinity, and
when  $\omega=\omega_{0}=\omega_{p}$, $r_{1}\rightarrow-1$. Thus, one needs to
satisfy the following phase matching conditions:  $e^{i2\omega\tau}\equiv
e^{i2kL}=1$ and $e^{i\omega\tau}=-1$. Neglecting retardation effects (Markov
approximation), this is possible when  $\omega_{0}\tau/2=m\,\pi+\pi/2$, which
was achieved in Ref. [38] by having $L=\lambda/2$ ( $m=0$),  and the probe
qubit at cavity center. Using this phase conditions, and a rotating wave
approximation, the two main complex roots are:

$\tilde{\omega}^{\pm}\approx\omega_{p}-i\frac{\gamma_{p}}{4}\pm\frac{1}{2}\sqrt{2\gamma_{p}\gamma_{m}}\,,$
(8)

where we assume $\gamma_{m}\gg\gamma_{p}$, with $\gamma_{m}$ the mirror qubit
decay rate. For on-resonance,  $\omega=\omega_{0}$, then $r_{1}\rightarrow-1$,
and the term in brackets in Eq. (7) tends to infinity, as does the Purcell
effect of an immutable dipole. However, in a strong coupling regime, with
small $\tau$, the original linewidth is reduced by 50% and there will be a
splitting of $\pm g_{0}$, with $g_{0}=\sqrt{2\gamma_{m}\gamma_{p}}/2$ [38].
For longer delay times, the polariton states decrease in energy and their
lifetime increases, an effect that requires retardation in the model.

Figure 2: Complex poles of the two main polariton states using Eq. (6) with no
approximations. Note that $\tau=\tau_{\rm RT}/2$, and
$\gamma_{m}=10\gamma_{p}$. The dashed lines show the non-retarded solution
(Markov) as also identified in the text. Figure 3: Scattered field (red curve)
and two qubit reflectivity (blue curve) at the probe dot for various delay
times, using $\gamma_{m}=10\gamma_{p}$. (a) $\tau\gamma_{m}=0.1$; (b)
$\tau\gamma_{m}=10$; (c) $\tau\gamma_{m}=50$. The greed dashed curve shows the
single qubit scattered field.

Figure 2 shows the first near-resonant complex poles as a function of $\tau$
for a decay rate $\gamma_{m}=10\gamma_{p}$. In the Markovian limit, the value
of the poles are constant (horizontal dashed lines). However, if the delay
times are taken into account (non-Markovian case, symbols), it can be seen how
the values of the complex poles decrease as the separation between the atoms
increases; thus, the resonances are in fact dependent on the retardation (and
other modes can also become important, not shown here); however, in units of
$g_{0}$, and using a Markov approximation, the coupling rate is always 1
(splitting of $\pm g_{0}$), but this only applies for sufficiently short delay
times. When the retardation is  sufficiently large, we can have $g_{\rm
eff}<1$ as $\tau$ increases, with already notable differences as small at
$\tau\gamma_{m}=0.1$. In addition, we observe that in the units presented in
Fig. 2 ($\tau\gamma_{m}$), the results look identical for different decay rate
ratios (e.g., if $\gamma_{m}=100\gamma_{p}$).

In Fig. 3, we show the  reflectivity (blue curve) of the bare two-qubit mirror
system as well as the probe qubit scattered field (red curve) for different
delay times. For the scattered field, we observe how Rabi splitting decreases
and sharpens for longer delay times. In contrast, the single qubit system just
displays a Lorentzian lineshape (green curve). In addition, for the longer
delay  time, we can observe a coupling to the  $m=\pm 2,4$ modes causing a
striking Fano resonance [46, 47]; note that the  $m=\pm 1,3$ modes do not
couple since the probe qubit is at a node of these cavity modes. For the
shorter delay time in (a), the peaks are placed approximately at $\pm g_{0}$
(slightly decreased), which corresponds close to the  Markovian limit result.
However, for the longer delay times, in (b) and (c), then clearly the
effective Rabi splitting, $g_{\rm eff}$, becomes smaller for longer delay
times. The first cavity sideband resonance in (b) and (c) are at
$\omega_{c1}=1.19g_{0}$ and $0.27g_{0}$, respectively; and note that these are
also influenced by the dispersion in $r_{1}(\omega)$. Also note that
$\omega_{c1}/g_{0}\propto\sqrt{\gamma_{m}/\gamma_{p}}$.

Quantum Theory using Matrix Products States (MPSs).—To represent the time
evolution of the probe qubit in the non-Markovian regime, and to confirm our
semiclassical results in the frequency domain, we next solve the same system
using MPSs [48, 49, 50]. To do this, we first consider the Hamiltonian for
three qubits [41],

$H=\sum_{n=1,2,3}\omega_{n}\sigma^{+}_{n}\sigma^{-}_{n}+\sum_{\alpha=L,R}\int_{-\infty}^{\infty}d\omega\omega
b_{\alpha}^{\dagger}(\omega)b_{\alpha}(\omega)+H_{\rm I},$ (9)

where $\omega_{n}$ are the resonant frequencies and $\sigma^{\pm}_{n}$ are the
Pauli operators of the qubits, and $b_{\alpha}(\omega)$ is the frequency
dependent boson operator. The interaction term,

$\displaystyle H_{\rm I}$
$\displaystyle=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}d\omega\,\bigg{\\{}\sum_{n=1,2,3}\bigl{(}\sqrt{\gamma_{n}^{L}}e^{i\omega
x_{n}/c}\,b_{L}(\omega)\sigma^{+}_{n}$
$\displaystyle+\sqrt{\gamma_{n}^{R}}e^{-i\omega
x_{n}/c}b_{R}(\omega)\sigma^{+}_{n}\bigr{)}+\rm H.c.\bigg{\\}},$ (10)

where $x_{n}$ are the positions of the atoms, and $\gamma_{n}^{L}$,
$\gamma_{n}^{R}$ represent the left and right decay rates, respectively.

Figure 4: Probe and mirror population dynamics using $n_{p}(0)=1$ in vacuum,
where again we use $\gamma_{m}=10\gamma_{p}$, for the same three delay times
shown in Fig. 3: (blue) $\tau\gamma_{m}=0.1$; (green) $\tau\gamma_{m}=10$;
(orange) $\tau\gamma_{m}=50$. Cases (a,c,e) are the symmetric examples
corresponding to the ones studied in Fig. 3 in the frequency domain, where
$\gamma_{p}^{L}=\gamma_{p}^{R}=\gamma_{p}/2$. Subplots (b,d,f) show the same
time dynamics when the probe qubit is chiral, with $\gamma_{p}^{L}=\gamma_{p}$
and $\gamma_{p}^{R}=0$. The grey dashed line is the corresponding symmetric
case for comparison.

Choosing a rotating frame corresponding to the center (probe) qubit frequency,
and defining the boson operators in the time domain, the Hamiltonian can be
written as

$\displaystyle
H=\Delta_{m}\sigma^{+}_{1}\sigma^{-}_{1}+\Delta_{m}\sigma^{+}_{3}\sigma^{-}_{3}$
$\displaystyle+\sqrt{\gamma_{m}}\bigl{(}e^{i\omega_{0}\tau}b_{L}(t{-}\tau)+b_{R}(t)\bigr{)}\sigma^{+}_{1}+{\rm
H.c.}$
$\displaystyle+\sqrt{\gamma_{p}}\bigl{(}e^{i\omega_{0}\tau/2}b_{L}(t{-}\tau/2)+e^{i\omega_{0}\tau/2}b_{R}(t{-}\tau/2)\bigr{)}\sigma^{+}_{2}+{\rm
H.c.}$
$\displaystyle+\sqrt{\gamma_{m}}\bigl{(}b_{L}(t)+e^{i\omega_{0}\tau}b_{R}(t{-}\tau)\bigr{)}\sigma^{+}_{3}+{\rm
H.c.},$ (11)

where we have considered symmetric decay rates, with
$\gamma_{1}=\gamma_{3}=\gamma_{m}$, $\gamma_{2}=\gamma_{p}$, and the probe
qubit is situated in the middle; $\Delta_{m}=\omega_{m}-\omega_{0}$ where
$\omega_{m}$ is the frequency of the external qubits. For the cases
considered, all qubits are on resonance and $\Delta_{m}=0$. Equation (11)
allows us to write the time evolution operator in the MPS representation as a
matrix product operator [51],

$\displaystyle U(t_{k},t_{k+1})$
$\displaystyle{=}\exp\bigl{[}-i\sqrt{\gamma_{m}}\bigl{(}e^{i\omega_{0}\tau}\tilde{B}_{L}(t_{k-l})+\tilde{B}_{R}(t_{k})\bigr{)}\sigma^{+}_{1}$
$\displaystyle+{\rm
H.c.}-i\sqrt{\gamma_{p}}\bigl{(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}e^{i\omega_{0}\tau/2}}\tilde{B}_{L}(t_{k-l/2})$
$\displaystyle+e^{i\omega_{0}\tau/2}\tilde{B}_{R}(t_{k-l/2})\bigr{)}\sigma^{+}_{2}+{\rm
H.c.}$
$\displaystyle-i\sqrt{\gamma_{m}}\bigl{(}\tilde{B}_{L}(t_{k})+e^{i\omega_{0}\tau}\tilde{B}_{R}(t_{k-l})\bigr{]},$
(12)

where $\tilde{B}$ is the time-bin bosonic noise operator [33, 34].

Following this procedure, the cases shown in Fig. 3 are studied in the time
domain and the evolution of the probe dot population
($n_{p}(t)=\braket{\sigma_{2}^{+}\sigma_{2}^{-}}(t)$) is represented in Figs.
4 (a,c,e),  and similarly for the mirror qubit populations. Vacuum Rabi
oscillations are present in all the cases. It is also observed that
significantly  larger decay rates appear for the probe dot for the longer
delay time in (c) compared to (a), while the dynamics in (e)
($\tau\gamma_{m}=50$) results in a high degree of interference because the
qubit resonance now couples to the multiple cavity modes. In addition,
population evolution of the mirror qubits is shown in black (both mirror
qubits show the  same population). We observe that this population stays
closer to zero for longer delay times, and in (e) the interference is also
reflected in the mirror dots.

We next show further control of this waveguide cavity-QED system by
considering a chiral probe qubit with $\gamma_{p}^{L}=\gamma_{p}$ and
$\gamma_{p}^{R}=0$. Chiral systems allow direction-dependent coupling,
offering multiple applications in quantum networks (e.g., see Refs. [42, 52,
53]). In Figs. 4 (b,d,f), we show the time evolution for similar systems as
before but now considering the chiral probe qubit. In this case, the photons
only interact with the probe dot when they are reflected from the  right
mirror. We also observe a variation of the time evolution with a further
improvement of the coherence times. In addition, the mirror qubits results do
not match as we have broken the symmetry of the system, and it can be seen
that, when the delay times increase, the separation between the same peak for
each mirror increases, showing very clearly the influence of the retardation
on the chiral qubit dynamics.

Figure 5:  Probe and mirror population dynamics using one excitation
($n_{p}(0)=1$) in vacuum for (a,c,e), and two excitations ($n_{p}(0)=1$,
$n_{m1}(0)=1$) in vacuum for (b,d,f). In all cases $\gamma_{m}=10\gamma_{p}$,
for a delay time $\tau\gamma_{m}=1$. Subplots (c,d,e,f) show the time dynamics
when the probe qubit is chiral, with $\gamma_{p}^{L}=\gamma_{p}$ fand
$\gamma_{p}^{R}=0$ in (c,d), and $\gamma_{p}^{L}=0$ and
$\gamma_{p}^{R}=\gamma_{p}$ in (e,f). Although probe qubit behaves similarly
in (c,e), the double excitation breaks the symmetry giving rise to different
quantum dynamics in (d,f).

Finally, we consider a double excitation (nonlinear) case by also starting an
excitation in one of the mirrors (mirror 1 in Fig. 5). Here, we compare this
new case with the one shown previously with just one excitation. For this
example, we choose the decay rate of $\gamma_{m}=10\gamma_{p}$ and a feedback
$\tau\gamma_{m}=1$. In Fig. 5(a,b), we show the symmetric coupling case
($\gamma_{p}^{L}=\gamma_{p}^{R}=\gamma_{p}/2$) and observe how the values of
$n_{p}$ change but the oscillation period is similar. A significantly faster
initial decay of the mirror qubit is seen in (b) due to the larger decay rate
of the mirror qubits. Then we study the chiral cases, with
$\gamma_{p}^{L}=\gamma_{p}$ and $\gamma_{p}^{R}=0$ in (c,d), and
$\gamma_{p}^{L}=0$ and $\gamma_{p}^{R}=\gamma_{p}$ in (e,f). In (c,e), the
mirror qubit are exchanged and the probe qubit behaves similarly. However, in
the double excited cases (d,f), we can see that not only does $n_{p}$ vary but
also the position of the peaks changes. In (d), only the photons coming from
the right mirror (mirror 2) interact with the probe qubit, while in (f) the
photons interacting with the probe qubit are the ones coming from the left one
(mirror 1). This leads to higher values of $n_{p}$ in (f), and a phase
difference between both scenarios.

Conclusions.—We have introduced a theory of  qubit-like mirrors which  mimics
caviy-QED interactions, consistent with  recent experiments. We then extended
this system into a much richer dynamical coupling regime, by introducing
retardation through a finite round trip memory, which increases the lifetime
of the cavity-qubit polariton states by several orders of magnitude, while
also reducing the overall vacuum Rabi splitting. For sufficiently long delays,
we  demonstrated how several cavity modes can act in concern, producing non-
trivial and highly non-Markovian population dynamics of a probe qubit. Our
theory first presented an analytical solution to the semiclassical problem of
three dipoles in a waveguide, using an exact Green function. This picture was
complemented by using MPS, where we showed the population dynamics including
an example for an embedded chiral probe qubit. In both theoretical pictures,
we explicitly showed how to increase the lifetime of the polariton states by
increasing the delay time between the external qubit mirrors.  In addition, we
demonstrated the role of several quantum excitations in a nonlinear regime,
showing significantly faster early time decay. These retardation effects also
facilitate the exploration of quantum nonlinear cavity-QED effects with
coherent driving fields using engineerable multiple qubits in waveguides.

Acknowledgements.—We acknowledge funding from the Canadian Foundation for
Innovation (CFI), Queen’s University and the Natural Sciences and Engineering
Research Council of Canada (NSERC).

## References

  * Ashhab and Nori [2010] S. Ashhab and F. Nori, Qubit-oscillator systems in the ultrastrong-coupling regime and their potential for preparing nonclassical states, Phys. Rev. A 81, 042311 (2010).
  * Sedov  _et al._ [2020] D. D. Sedov, V. K. Kozin, and I. V. Iorsh, Chiral waveguide optomechanics: First order quantum phase transitions with ${\mathbb{z}}_{3}$ symmetry breaking, Phys. Rev. Lett. 125, 263606 (2020).
  * Kuhn  _et al._ [2002] A. Kuhn, M. Hennrich, and G. Rempe, Deterministic single-photon source for distributed quantum networking, Phys. Rev. Lett. 89, 067901 (2002).
  * Zhu  _et al._ [1990] Y. Zhu, D. J. Gauthier, S. E. Morin, Q. Wu, H. J. Carmichael, and T. W. Mossberg, Vacuum Rabi splitting as a feature of linear-dispersion theory: Analysis and experimental observations, Phys. Rev. Lett. 64, 2499 (1990).
  * Shamailov  _et al._ [2010] S. Shamailov, A. Parkins, M. Collett, and H. Carmichael, Multi-photon blockade and dressing of the dressed states, Optics Communications 283, 766 (2010).
  * Leroux  _et al._ [2018] C. Leroux, L. C. G. Govia, and A. A. Clerk, Enhancing cavity quantum electrodynamics via antisqueezing: Synthetic ultrastrong coupling, Phys. Rev. Lett. 120, 093602 (2018).
  * Qin  _et al._ [2018] W. Qin, A. Miranowicz, P.-B. Li, X.-Y. Lü, J. Q. You, and F. Nori, Exponentially enhanced light-matter interaction, cooperativities, and steady-state entanglement using parametric amplification, Phys. Rev. Lett. 120, 093601 (2018).
  * Garziano  _et al._ [2015] L. Garziano, R. Stassi, V. Macrì, A. F. Kockum, S. Savasta, and F. Nori, Multiphoton quantum Rabi oscillations in ultrastrong cavity QED, Phys. Rev. A 92, 063830 (2015).
  * Yoshie  _et al._ [2004] T. Yoshie, A. Scherer, J. Hendrickson, G. Khitrova, H. M. Gibbs, G. Rupper, C. Ell, O. B. Shchekin, and D. G. Deppe, Vacuum Rabi splitting with a single quantum dot in a photonic crystal nanocavity, Nature 432, 200 (2004).
  * Reithmaier  _et al._ [2004] J. P. Reithmaier, G. Sęk, A. Löffler, C. Hofmann, S. Kuhn, S. Reitzenstein, L. V. Keldysh, V. D. Kulakovskii, T. L. Reinecke, and A. Forchel, Strong coupling in a single quantum dot–semiconductor microcavity system, Nature 432, 197 (2004).
  * Peter  _et al._ [2005] E. Peter, P. Senellart, D. Martrou, A. Lemaître, J. Hours, J. M. Gérard, and J. Bloch, Exciton-photon strong-coupling regime for a single quantum dot embedded in a microcavity, Phys. Rev. Lett. 95, 067401 (2005).
  * Brune  _et al._ [1996] M. Brune, F. Schmidt-Kaler, A. Maali, J. Dreyer, E. Hagley, J. M. Raimond, and S. Haroche, Quantum Rabi oscillation: A direct test of field quantization in a cavity, Phys. Rev. Lett. 76, 1800 (1996).
  * Schuster  _et al._ [2008] I. Schuster, A. Kubanek, A. Fuhrmanek, T. Puppe, P. W. H. Pinkse, K. Murr, and G. Rempe, Nonlinear spectroscopy of photons bound to one atom, Nature Physics 4, 382 (2008).
  * Bishop  _et al._ [2008] L. S. Bishop, J. M. Chow, J. Koch, A. A. Houck, M. H. Devoret, E. Thuneberg, S. M. Girvin, and R. J. Schoelkopf, Nonlinear response of the vacuum Rabi resonance, Nature Physics 5, 105 (2008).
  * Fink  _et al._ [2008] J. M. Fink, M. Göppl, M. Baur, R. Bianchetti, P. J. Leek, A. Blais, and A. Wallraff, Climbing the Jaynes–Cummings ladder and observing its nonlinearity in a cavity QED system, Nature 454, 315 (2008).
  * Englund  _et al._ [2010] D. Englund, A. Majumdar, A. Faraon, M. Toishi, N. Stoltz, P. Petroff, and J. Vučković, Resonant excitation of a quantum dot strongly coupled to a photonic crystal nanocavity, Phys. Rev. Lett. 104, 073904 (2010).
  * Press  _et al._ [2007] D. Press, S. Götzinger, S. Reitzenstein, C. Hofmann, A. Löffler, M. Kamp, A. Forchel, and Y. Yamamoto, Photon antibunching from a single quantum-dot-microcavity system in the strong coupling regime, Phys. Rev. Lett. 98, 117402 (2007).
  * Hughes [2004] S. Hughes, Enhanced single-photon emission from quantum dots in photonic crystal waveguides and nanocavities., Opt. Lett. 29, 2659 (2004).
  * Shen and Fan [2005] J. T. Shen and S. Fan, Coherent photon transport from spontaneous emission in one-dimensional waveguides, Opt. Lett. 30, 2001 (2005).
  * Zheng  _et al._ [2010] H. Zheng, D. J. Gauthier, and H. U. Baranger, Waveguide QED: Many-body bound-state effects in coherent and fock-state scattering from a two-level system, Phys. Rev. A 82, 063816 (2010).
  * Longo  _et al._ [2011] P. Longo, P. Schmitteckert, and K. Busch, Few-photon transport in low-dimensional systems, Phys. Rev. A 83, 063828 (2011).
  * Román-Roche  _et al._ [2020] J. Román-Roche, E. Sánchez-Burillo, and D. Zueco, Bound states in ultrastrong waveguide QED, Phys. Rev. A 102, 023702 (2020).
  * Roy [2010] D. Roy, Few-photon optical diode, Phys. Rev. B 81, 155117 (2010).
  * Roy  _et al._ [2017] D. Roy, C. M. Wilson, and O. Firstenberg, Colloquium: Strongly interacting photons in one-dimensional continuum, Rev. Mod. Phys. 89, 021001 (2017).
  * Rosario Hamann  _et al._ [2018] A. Rosario Hamann, C. Müller, M. Jerger, M. Zanner, J. Combes, M. Pletyukhov, M. Weides, T. M. Stace, and A. Fedorov, Nonreciprocity realized with quantum nonlinearity, Phys. Rev. Lett. 121, 123601 (2018).
  * Masson and Asenjo-Garcia [2020] S. J. Masson and A. Asenjo-Garcia, Atomic-waveguide quantum electrodynamics, Phys. Rev. Research 2, 043213 (2020).
  * Sheremet  _et al._ [2021] A. S. Sheremet, M. I. Petrov, I. V. Iorsh, A. V. Poshakinskiy, and A. N. Poddubny, Waveguide quantum electrodynamics: collective radiance and photon-photon correlations (2021), arXiv:2103.06824 .
  * Sinha  _et al._ [2020] K. Sinha, P. Meystre, E. A. Goldschmidt, F. K. Fatemi, S. L. Rolston, and P. Solano, Non-Markovian collective emission from macroscopically separated emitters, Phys. Rev. Lett. 124, 043603 (2020).
  * Longhi [2021] S. Longhi, Rabi oscillations of bound states in the continuum, Opt. Lett. 46, 2091 (2021).
  * Du  _et al._ [2021] L. Du, M.-R. Cai, J.-H. Wu, Z. Wang, and Y. Li, Single-photon nonreciprocal excitation transfer with non-Markovian retarded effects, Phys. Rev. A 103, 053701 (2021).
  * Guo  _et al._ [2020] L. Guo, A. F. Kockum, F. Marquardt, and G. Johansson, Oscillating bound states for a giant atom, Phys. Rev. Research 2, 043014 (2020).
  * Longhi [2020] S. Longhi, Superradiance paradox in waveguide lattices, Opt. Lett. 45, 3297 (2020).
  * Pichler and Zoller [2016] H. Pichler and P. Zoller, Photonic circuits with time delays and quantum feedback, Phys. Rev. Lett. 116, 093601 (2016).
  * Arranz Regidor  _et al._ [2021] S. Arranz Regidor, G. Crowder, H. Carmichael, and S. Hughes, Modeling quantum light-matter interactions in waveguide QED with retardation, nonlinear interactions, and a time-delayed feedback: Matrix product states versus a space-discretized waveguide model, Phys. Rev. Research 3, 023030 (2021).
  * Crowder  _et al._ [2020] G. Crowder, H. Carmichael, and S. Hughes, Quantum trajectory theory of few-photon cavity-QED systems with a time-delayed coherent feedback, Physical Review A 101, 023807 (2020).
  * Gu  _et al._ [2017] X. Gu, A. F. Kockum, A. Miranowicz, Y. xi Liu, and F. Nori, Microwave photonics with superconducting quantum circuits, Physics Reports 718-719, 1 (2017).
  * Kockum  _et al._ [2018] A. F. Kockum, G. Johansson, and F. Nori, Decoherence-free interaction between giant atoms in waveguide quantum electrodynamics, Phys. Rev. Lett. 120, 140404 (2018).
  * Mirhosseini  _et al._ [2019] M. Mirhosseini, E. Kim, X. Zhang, A. Sipahigil, P. B. Dieterle, A. J. Keller, A. Asenjo-Garcia, D. E. Chang, and O. Painter, Cavity quantum electrodynamics with atom-like mirrors, Nature 569, 692 (2019).
  * Chang  _et al._ [2012] D. E. Chang, L. Jiang, A. V. Gorshkov, and H. J. Kimble, Cavity QED with atomic mirrors, New Journal of Physics 14, 063003 (2012).
  * Chen and Liu [2012] T. Chen and R.-B. Liu, Non-Markovian dynamics and strong coupling between atomic transitions and a waveguide continuum edge, Phys. Rev. A 85, 043830 (2012).
  * Carmele  _et al._ [2020] A. Carmele, N. Nemet, V. Canela, and S. Parkins, Pronounced non-Markovian features in multiply excited, multiple emitter waveguide QED: Retardation induced anomalous population trapping, Phys. Rev. Research 2, 013238 (2020).
  * Young  _et al._ [2015] A. B. Young, A. C. T. Thijssen, D. M. Beggs, P. Androvitsaneas, L. Kuipers, J. G. Rarity, S. Hughes, and R. Oulton, Polarization engineering in photonic crystal waveguides for spin-photon entanglers, Phys. Rev. Lett. 115, 153901 (2015).
  * Lodahl  _et al._ [2017] P. Lodahl, S. Mahmoodian, S. Stobbe, A. Rauschenbeutel, P. Schneeweiss, J. Volz, H. Pichler, and P. Zoller, Chiral quantum optics, Nature 541, 473 (2017).
  * Manga Rao and Hughes [2007] V. S. C. Manga Rao and S. Hughes, Single quantum-dot purcell factor and $\beta$ factor in a photonic crystal waveguide, Phys. Rev. B 75, 205437 (2007).
  * de Vries  _et al._ [1998] P. de Vries, D. V. van Coevorden, and A. Lagendijk, Point scatterers for classical waves, Rev. Mod. Phys. 70, 447 (1998).
  * Cheng  _et al._ [2017] M.-T. Cheng, J. Xu, and G. S. Agarwal, Waveguide transport mediated by strong coupling with atoms, Phys. Rev. A 95, 053807 (2017).
  * Limonov  _et al._ [2017] M. F. Limonov, M. V. Rybin, A. N. Poddubny, and Y. S. Kivshar, Fano resonances in photonics, Nature Photonics 11, 543 (2017).
  * Yang  _et al._ [2018] C. Yang, F. C. Binder, V. Narasimhachar, and M. Gu, Matrix product states for quantum stochastic modeling, Physical Review Letters 121, 260602 (2018).
  * Vanderstraeten [2017] L. Vanderstraeten,  _Tensor Network States and Effective Particles for Low-Dimensional Quantum Spin Systems_ (Springer, Cham, 2017).
  * Orús [2014] R. Orús, A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Annals of Physics 349, 117 (2014).
  * Hubig  _et al._ [2017] C. Hubig, I. P. McCulloch, and U. Schollwöck, Generic construction of efficient matrix product operators, Phys. Rev. B 95, 035129 (2017).
  * Mahmoodian  _et al._ [2016] S. Mahmoodian, P. Lodahl, and A. S. Sørensen, Quantum networks with chiral-light–matter interaction in waveguides, Phys. Rev. Lett. 117, 240501 (2016).
  * Mehrabad  _et al._ [2020] M. J. Mehrabad, A. P. Foster, R. Dost, E. Clarke, P. K. Patil, A. M. Fox, M. S. Skolnick, and L. R. Wilson, Chiral topological photonics with an embedded quantum emitter, Optica 7, 1690 (2020).


is co-reachable.

######  Proposition 38.

Let $T$ be an NRT over $(\mathbb{N},\left\\{<,0\right\\})$ and $f=\llbracket
T\rrbracket$. The following are equivalent:

  * •

$f$ is uniformly continuous,

  * •

There is a critical pattern (see Definition 3.1.3) with $D_{1},D_{2}$ co-
reachable in $\mathbb{N}$.

######  Proof 4.12.

Let $T^{\prime}$ denote the same transducer as $T$ except that 1) it is over
$\mathbb{Q}$ and 2) it is restricted to configurations which are co-reachable
in $\mathbb{N}$.

We claim that $T$ realizes a uniformly continuous function if and only if
$T^{\prime}$ does. From Proposition 16, this is enough to show the expected
result.

Any run over $T$ is in particular a run over $T^{\prime}$, hence if $T$ is not
uniformly continuous then, in particular, $T^{\prime}$ is not either.
Conversely, let us assume that $T^{\prime}$ is not uniformly continuous.
According to Proposition 16, this means that we can exhibit a critical pattern
$C_{0}\xrightarrow{u|u_{1}}C_{1}\xrightarrow{v|v_{1}}\mu(C_{1})\xrightarrow{w|w_{1}}D_{1}$,
$C_{0}\xrightarrow{u|u_{2}}C_{2}\xrightarrow{v|v_{2}}\mu(C_{2})\xrightarrow{z|w_{2}}D_{2}$
such that $D_{1},D_{2}$ are co-reachable. By definition we have that
$D_{1},D_{2}$ are co-reachable in $\mathbb{N}$. Let $i$ denote the mismatching
position in the pattern. Let $n>0$, we want to exhibit two inputs that have a
common prefix of length at least $n$ but outputs that have a longest common
prefix smaller than $i$. We consider the two runs
$C_{0}\xrightarrow{u|u_{1}}C_{1}\xrightarrow{v|v_{1}}\mu(C_{1})\cdots\mu^{n}(C_{1})\xrightarrow{\mu^{n}(v)|\mu^{n}(v_{1})}\mu^{n+1}(C_{1})\xrightarrow{\mu^{n}(w)|\mu^{n}(w_{1})}\mu^{n}(D_{1})$
and
$C_{0}\xrightarrow{u|u_{2}}C_{2}\xrightarrow{v|v_{2}}\mu(C_{2})\cdots\mu^{n}(C_{2})\xrightarrow{\mu^{n}(v)|\mu^{n}(v_{2})}\mu^{n+1}(C_{2})\xrightarrow{\mu^{n}(w)|\mu^{n}(w_{1})}\mu^{n}(D_{2})$.
Note that it could be that $\mu^{n}$ cancels the mismatch, in which case we
can consider $\mu^{n+1}$. Since $\mu^{n}(D_{1})$ and $\mu^{n}(D_{2})$ are co-
reachable, we can use Proposition 31 and we obtain the result.

As a corollary, we obtain:

######  Theorem 39.

Let $f:\mathbb{N}^{\omega}\rightarrow\mathbb{N}^{\omega}$ be a function
defined by an NRT over $\mathbb{N}$. Deciding its uniform continuity is
PSpace-c.

######  Proof 4.13.

We are left to show that uniform continuity of $T^{\prime}$ is in PSpace. This
problem is in PSpace from Theorem 21. We have to be careful however, since
computing $T^{\prime}$ explicitly may be too costly. The trick is that
checking if a configuration is co-reachable can be done on the fly in PSpace,
using Proposition 32 and Corollary 33.

The complexity lower bound can again be obtained by reducing the problem to
emptiness of register automata over $(\mathbb{N},\\{=\\})$, which is PSpace-c
[DL09].

###  4.8 Continuity

We end our study with the property of continuity of NRT over $\mathbb{N}$.

To simplify the following statement, we assume that transducers are equipped
with a distinguished register $r_{m}$ which along the run stores the maximal
data value seen in the input so far.

######  Proposition 40 (Continuity).

Let $f:\mathbb{N}^{\omega}\rightarrow\mathbb{N}^{\omega}$ be given by an NRT
$T$ over $\mathbb{N}$. The following are equivalent:

  1. 1.

$f$ is not continuous

  2. 2.

there exists a critical pattern in
$\mathsf{Critical}(u,v,w,z,C_{1},C_{2},C_{1}^{\prime},C_{2}^{\prime},D_{1},D_{2})$
with $u,v,w,z\in\mathbb{Q}_{+}^{*}$, where $C_{1}$ is final, $D_{1}$ and
$D_{2}$ are co-reachable in $\mathbb{N}$ and such that
$\sigma=\tau((C_{1}\uplus C_{2})\uplus(C^{\prime}_{1}\uplus C^{\prime}_{2}))$
satisfies the $\star$ property for $X=R_{1}\cup R_{2}^{l}$, where
$R_{2}^{l}=\\{r_{2}\in R_{2}\mid\exists r^{\prime}_{1}\in
R^{\prime}_{1},\sigma\Rightarrow r_{2}\leq r^{\prime}_{1}\\}$.

######  Proof 4.14 (Proof of
$(\ref{itm:NfNotCont})~{}\Rightarrow~{}(\ref{itm:NfPattern})$).

Assume first that $f$ is not continuous. Let $x\in\mathbb{N}^{\omega}$, and
let $(x_{n})_{n\in\mathbb{N}}$ be such that $\forall
n\in\mathbb{N},x_{n}\in\mathrm{dom}(f)$ $x_{n}\xrightarrow[n\infty]{}x$ but
$f(x_{n})\not\xrightarrow[n\infty]{}f(x)$. Up to extracting subsequences, we
can assume w.l.o.g. that there exists some $k\in\mathbb{N}$ such that for all
$n\in\mathbb{N}$, $\lvert f(x)\wedge f(x_{n})\rvert\leq k$. We denote by
$\rho$ a run of $T$ over $x$ yielding output $f(x)$, and by
$(\rho_{n})_{n\in\mathbb{N}}$ a sequence of runs of $T$ such that $\rho_{n}$
yields output $f(x_{n})$ over input $f(x)$.

First, since the set $\Delta$ of transitions of $T$ is finite,
$\Delta^{\omega}$ is compact (cf Remark 3), so $(\rho_{n})_{n\in\mathbb{N}}$
admits a converging subsequence, so we can assume w.l.o.g. that
$(x_{n})_{n\in\mathbb{N}}$ is such that $(\rho_{n})_{n\in\mathbb{N}}$
converges to some infinite sequence of transitions $\pi$.

######  Remark 41.

Note however that $\pi$ is not necessarily a run over some concrete data word:
since transducers are allowed to guess arbitrary data value, we do not have
the property that after reading input $u$, the configuration of the transducer
takes its values in $\mathsf{data}(u)\cup\\{0\\}$, which would allow to build
a concrete run by extracting subsequences of runs whose configurations
coincide on longer and longer prefixes. If we disallow guessing, such property
is restored, which greatly simplifies the proof. Indeed, then, we can require
that $\sigma$ has the $\star$ property, without allowing some wild registers
to go astray (namely those that are above $r^{\prime}_{k}$, which necessarily
correspond to data values that have been guessed, otherwise their content is
at most equal to the one of $r_{m}$), and having two runs that can be
instantiated by actual data words allow to extract $\sigma$ with a Ramsey
argument which is similar to the one used for emptiness (see Proposition 32).

Now, let $(E_{i})_{i\in\mathbb{N}}$ be the sequence of configurations of
$\rho$, and, for each $\rho_{n}$, let $(C_{n,i})_{i\in\mathbb{N}}$ be its
corresponding sequence of configurations. Then, for all $0\leq i<j$, let
$\tau_{n,i}=\tau(C_{n,i})$ and $\sigma_{n,i,j}=\sigma(E_{i}\uplus
C_{n,i},E_{j}\uplus C_{n,j})$. Since the $\tau_{n,i}$ and $\sigma_{n,i,j}$
take their values in a finite set, by using compactness arguments, we can
extract two subsequences $(\tau^{\prime}_{n,i})_{n,i\in\mathbb{N}}$ and
$(\sigma^{\prime}_{n,i,j})_{n\in\mathbb{N},0\leq i<j}$ which respectively
converge to $(\tau^{\prime}_{i})_{i\in\mathbb{N}}$ and to a family
$(\sigma_{i,j})_{0\leq i<j}$. Formally, we require that for all $M\geq 0$,
there exists some $N\geq 0$ such that for all $n\geq N$, we have that
$\tau^{\prime}_{n,i}=\tau^{\prime}_{i}$ and
$\sigma^{\prime}_{n,i,j}=\sigma_{i,j}$ for all $0\leq i<j\leq M$ (note that
for types $\tau^{\prime}_{n,i}$, this corresponds to convergence for infinite
words). By first restricting to final configurations in $\rho$ (we know there
are infinitely many since $\rho$ is accepting), we can assume that all $E_{i}$
are final. We further restrict to $E_{i}$ which all have the same type $\nu$
(there is at least one type which repeats infinitely often). To avoid
cluttering the notations, we name again $(\rho_{n})_{n\in\mathbb{N}}$ the
corresponding subsequence of runs, $(\tau_{n,i})_{n,i\in\mathbb{N}}$ the
corresponding types, and $(\sigma_{n,i,j})_{n,i,j}$ their associated family of
pairwise types. Finally, by applying Ramsey’s theorem to
$(\tau_{i})_{i\in\mathbb{N}}$ and $(\sigma_{i,j})_{0\leq i<j}$, we know that
there exists some type $\tau$, some pairwise type $\sigma$ and some infinite
subset $I\subseteq\mathbb{N}$ such that for all $i,j\in I$ such that $i<j$,
$\tau_{i}=\tau$ and $\sigma_{i,j}=\sigma$. For simplicity, we reindex the
$(E_{j})_{j\in I}$ and the $(C_{n,j})_{j\in I}$ over $\mathbb{N}$, that we
again name $(E_{j})_{j\in\mathbb{N}}$ and $(C_{n,i})_{i\in\mathbb{N}}$.

Now, assume by contradiction that $\sigma$ does not have the property $\star$
for $X=R_{1}\cup R_{2}^{l}$. There are two cases, that we treat iteratively:

  * •

There exists some $r\in X$ such that $\sigma\Rightarrow r>r^{\prime}$. There
are two subcases:

    * –

If there exists such $r\in R_{1}$, then we get that for all $0\leq i<j$,
$E_{i}(r)>E_{j}(r)$, which immediately yields an infinite descending chain in
$\mathbb{N}$, and hence a contradiction.

    * –

If there exists such $r\in R_{2}^{l}$, then let $r^{\prime}_{M}$ be such that
$\sigma\Rightarrow r\leq r^{\prime}_{M}$. Since $r_{M}\in R_{1}$, we know that
$\sigma\Rightarrow r_{M}\leq r^{\prime}_{M}$, otherwise we are back to the
previous case. Then, let $N\in\mathbb{N}$ be such that $\sigma_{N,i,j}=\sigma$
for all $0\leq i<j\leq B=E_{1}(r^{\prime}_{M})+1$. Such $N$ necessarily exists
since we took the $(\rho_{n})_{n\in\mathbb{N}}$ such that the
$(\sigma_{n,i,j})_{0\leq i<j}$ converges. Thus, $E_{1}(r^{\prime}_{M})\geq
C_{N,0}(r)>C_{N,1}(r)>\dots C_{N,B}(r)$, which again yields a contradiction.

  * •

Assume now that there exists $r,s\in X$ such that $\sigma\Rightarrow
s=s^{\prime}$, $\sigma\Rightarrow r\leq s$ but $\sigma\Rightarrow
r<r^{\prime}$. There are again two subcases:

    * –

If $s\in R^{1}$, then we know that for all $i\in\mathbb{N}$,
$E_{i}(s)=E_{0}(s)$. Now, if $r\in R^{1}$, then we get that
$E_{0}(r)<E_{1}(r)<\dots$ but for all $i\in\mathbb{N}$, $E_{i}(r)<E_{i}(s)$,
which leads to a contradiction. If $r\in R_{2}^{l}$, then let $N$ be such that
$\sigma_{N,i,j}=\sigma$ for all $0\leq i<j\leq B=E_{0}(s)+1$. We then get a
strictly increasing chain $C_{N,0}(r)<C_{N,1}(r)<\dots<C_{N,B}(r)$ of length
$B$ which is bounded from above by $B-1$, which does not exist in
$\mathbb{N}$.

    * –

If $s\in R_{2}^{l}$ then let $r^{\prime}_{M}\in R_{1}$ be such that
$\sigma\Rightarrow s\leq r^{\prime}_{M}$. Then, let
$B=E_{1}(r^{\prime}_{M})+1$, and let $N$ be such that $\sigma_{N,i,j}=\sigma$
for all $0\leq i<j\leq B$. If $r\in R^{1}$ then we have that
$E_{0}(r)<E_{1}(d)<\dots<E_{B}(r)\leq E_{B}(s)=E_{0}(s)\leq
E_{1}(r^{\prime}_{M})$; similarly if $r\in R_{2}^{l}$ we get
$C_{N,0}(r)<C_{N,1}(r)<\dots<C_{N,B}(r)\leq C_{N,B}(s)=C_{N,0}(s)\leq
E_{1}(r_{M}^{\prime})$. In both cases, this leads to a contradiction.

As a consequence, $\sigma$ indeed has the property $\star$ for $X=R_{1}\cup
R_{2}^{l}$.

Now, it remains to exhibit a critical pattern from $\rho$ and the (last)
extracted subsequence $(\rho_{n})_{n\in\mathbb{N}}$ and the corresponding
inputs $(x_{n})_{n\in\mathbb{N}}$. Let $k\in\mathbb{N}$ be such that for all
$n\in\mathbb{N}$, $\lvert f(x)\wedge f(x_{n})\rvert\leq k$. On the one hand,
we have $\rho=E_{0}\xrightarrow{u_{0}\mid v_{0}}E_{1}\xrightarrow{u_{1}\mid
v_{1}}E_{2}\dots$, where $x=u_{0}u_{1}\dots$ and such that all $(E_{i})_{i>0}$
are final and they all have the same type. On the other hand, each $\rho_{n}$
can be written $\rho_{n}=C_{n,0}\xrightarrow{u^{n}_{0}\mid
v^{n}_{0}}C_{n,1}\xrightarrow{u^{n}_{1}\mid v^{n}_{1}}C_{n,2}\dots$, where for
all $j\geq 0,\lvert u^{n}_{j}\rvert=\lvert u_{j}\rvert$ (the configurations
$C_{n,i}$ are synchronised with those of $E_{i}$, as we always extracted
subsequences in a synchronous way) and $u^{n}_{0}u^{n}_{1}\dots=x_{n}$. Now,
let $M$ be such that $\forall n\geq M$, we have $\forall 0\leq i<j\leq
B+3,\sigma_{n,i,j}=\sigma$, where $B=2k$. Finally, take some $l\geq M$ such
that $\lvert x_{l}\wedge x\rvert\geq\lvert u_{0}u_{1}\dots u_{B+1}\rvert$.
There are two cases:

  * •

$v_{0}\dots
v_{B}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}v^{l}_{0}\dots
v^{l}_{B}$. Then, we exhibited a critical parttern with two runs
$E_{0}\xrightarrow{u_{0}\dots u_{B}\mid v_{0}\dots
v_{B}}E_{B+1}\xrightarrow{u_{B+1}\mid v_{B+1}}E_{B+2}\xrightarrow{u_{B+2}\mid
v_{B+2}}E_{B+3}$ along with $C_{l,0}\xrightarrow{u^{l}_{0}\dots u^{l}_{B}\mid
v^{l}_{0}\dots v^{l}_{B}}C_{l,B+1}\xrightarrow{u^{l}_{B+1}\mid
v^{l}_{B+1}}C_{l,B+2}\xrightarrow{u^{l}_{B+2}\mid v^{l}_{B+2}}C_{l,B+3}$.
First, the outputs indeed mismatch, by hypothesis, so we are in case 1 of the
definition of a critical pattern (see Definition 3.1.3).

  * •

$v_{0}\dots v_{B}\mathrel{{\hstretch{.8}{\parallel}}}v^{l}_{0}\dots
v^{l}_{B}$. Then, since $v_{0}\dots v_{B}\leq f(x)$ and $v^{l}_{0}\dots
v^{l}_{B}\leq f(x_{l})$, and since $\lvert f(x)\wedge f(x_{l})\rvert\leq k$,
we get that $\lvert v_{0}\dots v_{B}\rvert\leq k$ or $\lvert v^{l}_{0}\dots
v^{l}_{B}\rvert\leq k$. Now, there are again two cases:

    * –

There exists some $i\leq B$ such that $v_{i}=v^{l}_{i}=\varepsilon$. Then, we
exhibited a critical pattern with two runs $E_{0}\xrightarrow{u_{0}\dots
u_{i-1}\mid v_{0}\dots
v_{i-1}}E_{i}\xrightarrow{u_{i}\mid\varepsilon}E_{i+1}\xrightarrow{u_{i+1}\dots
u_{m}\mid v_{i+1}\dots v_{m}}E_{m+1}$ and $C_{l,0}\xrightarrow{u^{l}_{0}\dots
u^{l}_{i-1}\mid v^{l}_{0}\dots
v^{l}_{i-1}}C_{l,i}\xrightarrow{u^{l}_{i}\mid\varepsilon}C_{l,i+1}\xrightarrow{u^{l}_{i+1}\dots
u^{l}_{m}\mid v^{l}_{i+1}\dots v^{l}_{m}}C_{l,m+1}$, where $m$ is such that
$v^{l}_{0}\dots
v^{l}_{m}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}v_{0}\dots
v_{m}$ (such $m$ exists since
$f(x_{n})\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}f(x)$). We
are then in case 3 of the definition of a critical pattern (see Definition
3.1.3).

    * –

Otherwise, there necessarily exists some $i\leq B$ such that
$v_{i}=\varepsilon$ or $v^{l}_{i}=\varepsilon$ since $\lvert v_{0}\dots
v_{B}\rvert\leq k$ or $\lvert v^{l}_{0}\dots v^{l}_{B}\rvert\leq k$. We assume
that $v_{i}=\varepsilon$, the reasoning is symmetric if instead
$v^{l}_{i}=\varepsilon$. Necessarily, $v^{l}_{0}\dots
v^{l}_{i-1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}f(x)$,
otherwise we can find some $i$ such that both $v_{i}=v^{l}_{i}$ and we are
back to the previous case. Then, we exhibited a critical pattern with two runs
$E_{0}\xrightarrow{u_{0}\dots u_{i-1}\mid v_{0}\dots
v_{i-1}}E_{i}\xrightarrow{u_{i}\mid\varepsilon}E_{i+1}\xrightarrow{u_{i+1}\dots
u_{m}\mid v_{i+1}\dots v_{m}}E_{m+1}$ and $C_{l,0}\xrightarrow{u^{l}_{0}\dots
u^{l}_{i-1}\mid v^{l}_{0}\dots v^{l}_{i-1}}C_{l,i}\xrightarrow{u^{l}_{i}\mid
v^{l}_{i}}C_{l,i+1}\xrightarrow{u^{l}_{i+1}\dots u^{l}_{m}\mid
v^{l}_{i+1}\dots v^{l}_{m}}C_{l,m+1}$, where $m$ is such that $v^{l}_{0}\dots
v^{l}_{m}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}v_{0}\dots
v_{m}$ (such $m$ exists since we assumed that $v^{l}_{0}\dots
v^{l}_{i-1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}f(x)$).
We are then in case 2 of the definition of a critical pattern (see Definition
3.1.3).

Finally, in all the considered cases, the last configuration $D_{1}=E_{j}$ of
the first run of the critical pattern (the one which is a prefix of $\rho$) is
final, since we extracted the $(E_{i})$ so that we only kept the final ones.
Also, both $D_{1}=E_{j}$ and $D_{2}=C_{l,j}$ are co-reachable in $\mathbb{N}$
since they are configurations of accepting runs in $\mathbb{N}$, which
concludes the proof of
$(\ref{itm:NfNotCont})~{}\Rightarrow~{}(\ref{itm:NfPattern})$.

######  Proof 4.15 (Proof of
$(\ref{itm:NfPattern})~{}\Rightarrow~{}(\ref{itm:NfNotCont})$).

We assume now that $(\ref{itm:NfPattern})$ holds and show that $f$ is not
continuous. Intuitively, following notations of the critical pattern, we will
prove that $f$ is not continuous at some input
$x=u^{\prime}v^{\prime}\mu(v^{\prime})\mu(v^{\prime})\ldots$, where
$u^{\prime},v^{\prime}$ elements of $\mathbb{N}^{+}$, images of $u,v$ by some
automorphism.

Thus, let us consider two runs
$C_{0}\xrightarrow{u|u_{1}}C_{1}\xrightarrow{v|v_{1}}\mu(C_{1})$ with $C_{1}$
final, and
$C_{0}\xrightarrow{u|u_{2}}C_{2}\xrightarrow{v|v_{2}}\mu(C_{2})\xrightarrow{z|w_{2}}D_{2}$
with $D_{2}$ co-reachable in $\mathbb{N}$. Two cases can occur: either
$u_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{2}$, or
$v_{2}=\epsilon$ and
$u_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{2}w_{2}$.
As in the proof in the oligomorphic setting, we want to show that it is
possible to build from the first run an infinite run looping forever along
(some renaming of) $v$, and from the second run a family of infinite runs,
looping more and more. While this is directly true in some oligomorphic data
domain, as we saw before, iteration in $\mathbb{N}$ is more tricky.

These runs can be seen as finite runs in the transducer $T\times T$, with
twice as many registers as $T$, which we denote by $R_{1}$ for the first copy,
and $R_{2}$ for the second. By assumption, $\sigma=\tau((C_{1}\uplus
C_{2})\uplus(C^{\prime}_{1}\uplus C^{\prime}_{2}))$ satisfies the $\star$
property for $X=R_{1}\cup R_{2}^{l}$. If we had that $\sigma$ satisfies the
$\star$ property for $R_{1}\cup R_{2}$, then we could immediately deduce by
Proposition 27 that the two loops on $v$ could be iterated infinitely many
times. However, the weaker hypothesis we have will only allow us to show that
the loop from $C_{1}$ can indeed by $\omega$-iterated, while the loop from
$C_{2}$ can be iterated as many times as we want, but finitely many times. To
this end, we have to take care of registers in $R_{2}\setminus R_{2}^{l}$ to
show that these runs indeed exist.

As we assumed that there is a register $r_{m}$ storing the maximal data value
appearing in the input word, the definition of the set $R_{2}^{l}$ ensures
that every register not in $R_{2}^{l}$ has its value coming from a guess along
the run $C_{0}\xrightarrow{u}C_{2}$. This is directly linked with the
technical difficulty inherent to the presence of guessing. In particular, this
allows us to consider different runs, in which the input data word is not
modified, but the guessed values are.

As $C_{2}$ and $\mu(C_{2})$ have the same type, and registers not in
$R_{2}^{l}$ have “large” values, their behaviour along the cycle (w.r.t.
types) $C_{2}\xrightarrow{v}\mu(C_{2})$ is very restricted: they can only
increase or decrease at each step. In particular, if one starts from some
configuration $C_{2}$ in which values of registers not in $R_{2}^{l}$ are very
far apart, this will allow to iterate the cycle several times. More precisely,
for any integer $n$, we can compute an integer $n^{\prime}$ and values for the
guesses of registers not in $R_{2}^{l}$ which are pairwise $n^{\prime}$ far
apart, ensuring that the cycle can be repeated at least $n$ times.

Thus, the previous reasoning allows us to replicate the proof of Proposition
27 to show that there exist a word $v^{\prime}\in\mathbb{N}^{*}$ and an
automorphism $\alpha$ preserving $\mathbb{N}$, such that:

  * •

$C^{\prime}_{1}\xrightarrow{x|y}$, with $\tau(C^{\prime}_{1})=\tau(C_{1})$ and
$x=v^{\prime}\alpha(v^{\prime})\alpha^{2}(v^{\prime})\ldots$

  * •

there exists $C^{\prime}_{2}$ and, for all $n$, some $C^{\prime}_{2}(n)$ with
$C^{\prime}_{2}(n)_{|R_{2}^{l}}=C^{\prime}_{2|R_{2}^{l}}$,
$\tau(C^{\prime}_{2}(n))=\tau(C_{2})$, and
$C^{\prime}_{2}(n)\xrightarrow{v^{\prime}}\alpha(C^{\prime}_{2}(n))\ldots\xrightarrow{\alpha^{n}(v^{\prime})}\alpha^{n+1}(C^{\prime}_{2}(n))$

Using previous remark on guessed values, together with Proposition 31 applied
on $C_{0}\xrightarrow{u}C_{1}$ and $C_{0}\xrightarrow{u}C_{2}$, and
Proposition 25 applied on
$\mu(C_{2})\xrightarrow{z|w_{2}}D_{2}\xrightarrow{z_{l}}$, we end up with:

  * •

a run
$C_{0}\xrightarrow{u^{\prime}|u^{\prime}_{1}}E_{1}\xrightarrow{x^{\prime}|y^{\prime}}$,
with
$x^{\prime}=v^{\prime\prime}\alpha(v^{\prime\prime})\alpha^{2}(v^{\prime\prime})\ldots$

  * •

for every $n$, there is a run
$C_{0}\xrightarrow{u^{\prime}|u^{\prime}_{2}}E_{2}\xrightarrow{v^{\prime\prime}}\alpha(E_{2})\ldots\xrightarrow{\alpha^{n}(v^{\prime\prime})}\alpha^{n+1}(E_{2})\xrightarrow{z^{\prime}|w^{\prime}_{2}}D^{\prime}_{2}\xrightarrow{z^{\prime}_{l}}$

  * •

$u^{\prime}_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u^{\prime}_{2}$
or
$u^{\prime}_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u^{\prime}_{2}w^{\prime}_{2}$

Hence, this proves the non functionality as we have a sequence of runs whose
inputs converge towards $u^{\prime}x^{\prime}$ but whose outputs mismatch.

######  Theorem 42.

Continuity of NRT on $\mathbb{N}$ is PSpace-c.

######  Proof 4.16.

Small critical pattern property (Claim 3.1.3) on oligomorphic data can easily
be adapted to $\mathbb{N}$. Indeed, the only difference lies in the loops on
$v$, but is is important to notice that loop removal used to reduce length of
runs preserves the extremal configurations (see Proposition 11), hence it
preserves the type of the global run, here the type $\sigma=\tau((C_{1}\uplus
C_{2})\uplus(C^{\prime}_{1}\uplus C^{\prime}_{2}))$.

Then, one can proceed similarly by guessing such a small critical pattern, and
checking mismatches with counters. Note that we have to verify in addition
that $D_{2}$ is co-reachable in $\mathbb{N}$, but again, as already detailed
in previous proofs, this property can be decided on-the-fly.

Finally, the PSpace lower bound can again be obtained by a reduction to the
emptiness problem of register automata over $(\mathbb{N},\\{=\\})$, which is
PSpace-c [DL09].

###  4.9 Transfer result

We have extended our result to one non-oligomorphic structure, namely
$(\mathbb{N},\left\\{<,0\right\\})$, which is a substructure of
$(\mathbb{Q},\left\\{<,0\right\\})$. If we want to extend the result to other
substructures of $(\mathbb{Q},\left\\{<\right\\})$, say
$(\mathbb{Z},\left\\{<\right\\})$, we could do the same work again and study
the properties of iterable loops in $\mathbb{Z}$. However, a simpler way is to
observe that $(\mathbb{Z},\left\\{<\right\\})$ can be simulated by
$\mathbb{N}$, using two copies of the structure. We show a quite simple yet
powerful result: given a structure $\mathbb{D}$, if the structure
$\mathbb{D}^{\prime}$ can be defined as a quantifier-free interpretation over
$\mathbb{D}$ then the problems of emptiness, functionality, continuity, etc
reduce to the same problems over $\mathbb{D}^{\prime}$.

A _quantifier-free interpretation_ of dimension $l$ with signature $\Gamma$
over a structure $(\mathbb{D},\Sigma)$ is given by $\textsf{QF}[\Sigma]$
quantifier-free formulas: a formula
$\phi_{\text{domain}}(x_{1},\ldots,x_{l})$, for each constant symbol
$\mathsf{c}$ of $\Gamma$ a formula $\phi_{\mathsf{c}}(x_{1},\ldots,x_{l})$ and
for each relation symbol $R$ of $\Gamma$ of arity $r$ a formula
$\phi_{R}(x_{1}^{1},\ldots,x_{l}^{1},\ldots,x_{1}^{r},\ldots,x_{l}^{r})$. The
structure $\mathbb{D}^{\prime}$ is defined by the following: a domain
$D^{\prime}=\left\\{(d_{1},\ldots,d_{l})|\
\mathbb{D}\models\phi_{\text{domain}}(d_{1},\ldots,d_{l})\right\\}$; an
interpretation $(d_{1},\ldots,d_{l})\in D^{\prime}$ for each constant symbol
$\mathsf{c}$ such that
$\mathbb{D}\models\phi_{\mathsf{c}}(d_{1},\ldots,d_{l})$ (we assume that there
is a unique possible tuple satisfying the formula, which can be syntactically
ensured); an interpretation
$R^{\mathbb{D}}=\left\\{(x_{1}^{1},\ldots,x_{l}^{1},\ldots,x_{1}^{r},\ldots,x_{l}^{r})|\
\mathbb{D}\models\phi_{R}(x_{1}^{1},\ldots,x_{l}^{1},\ldots,x_{1}^{r},\ldots,x_{l}^{r})\right\\}$
for each relation symbol $R$.

######  Theorem 43.

Let $\mathbb{D}^{\prime}$ be a quantifier-free interpretation over
$\mathbb{D}$. Let $P$ denote a decision problem among non-emptiness,
functionality, continuity, Cauchy continuity or uniform continuity. There is a
PSpace reduction from $P$ over $\mathbb{D}^{\prime}$ to $P$ over $\mathbb{D}$.

######  Proof 4.17.

Let $R\subseteq\mathbb{D}^{\prime\omega}\times\mathbb{D}^{\prime\omega}$ be
given by an NRT $T$. If we assume that $\mathbb{D}^{\prime}$ is an
$l$-dimension interpretation of $\mathbb{D}$, then we can view $R$ as a
relation $P\subseteq(\mathbb{D}^{l})^{\omega}\times(\mathbb{D}^{l})^{\omega}$.
Note that $P$ is empty (resp. functional, continuous, Cauchy continuous,
uniformly continuous) if and only if $R$ is.

Moreover, since $\mathbb{D}^{\prime}$ is an interpretation, one can construct
an NRT $S$ which realizes $P$. It uses $l$ registers for every register of $T$
plus $l-1$ registers to store the input. In its first $l-1$ transitions it
just stores the input and every $l$ transition, it simulates a transition of
$T$, just by substituting the formulas of the interpretation for the
predicates. As usual, we do not construct $S$ explicitly, but we are able to
simulate it using only polynomial space.

As a direct corollary we can, in particular, transfer our result over
$(\mathbb{N},\\{<,0\\})$ to $(\mathbb{Z},\\{<,0\\})$:

######  Corollary 44.

The problems of non-emptiness, functionality, continuity, Cauchy continuity,
uniform continuity over $(\mathbb{Z},\\{<,0\\})$ are in PSpace.

######  Proof 4.18.

From Theorem 43, using the fact that $(\mathbb{Z},\\{<,0\\})$ is given by the
following two-dimensional interpretation over $(\mathbb{N},\\{<,0\\})$:
$\phi_{\text{domain}}:=(x=0)\vee(y=0)$,
$\phi_{0}:=(x=y=0),\phi_{<}:=(x_{1}=x_{2}=0\wedge(y_{1}<y_{2}))\vee(y_{1}=y_{2}=0\wedge(x_{1}>x_{2}))\vee(x_{2}=y_{1}=0\wedge\neg(x_{1}=y_{2}=0))$.

######  Remark 45.

Of course our transfer result applies to many other substructures of
$(\mathbb{Q},\\{<,0\\})$, such as the ordinals $\omega+\omega$,
$\omega\times\omega$, etc.

######  Remark 46.

Considering first-order interpretation (i.e. where $\phi_{\text{domain}}$, etc
are first-order formulas instead of quantifier-free ones) would yield too much
expressive power. Indeed, $(\mathbb{N},\left\\{+1,0\right\\})$, where
$+1(x,y)$ holds whenever $y=x+1$, can easily be defined as a (one-dimensional)
first-order interpretation of $(\mathbb{N},\left\\{<,0\right\\})$, by letting
$\phi_{+1}(x,y)=y>x\wedge\neg\exists z,x<z<y$. However, over such a domain,
register automata coincide with counter machines, which is a Turing-complete
model (with two or more counters); in particular, emptiness of such register
automata is easily shown undecidable (with two or more registers).

## Future work

We have given tight complexity results in a family of oligomorphic structures,
namely polynomially decidable ones. An example of an exponentially decidable
oligomorphic structure is the one of finite bitvectors with bitwise xor
operation. Representing the type of $k$ elements may require exponential sized
formulas (for example stating that a family of $k$ elements is free, i.e. any
non-trivial sum is non-zero). The same kind of proof would give ExpSpace
algorithms over this particular data set (for the transducer problems we have
been studying). One could try to classify the different structures based on
the complexity of solving these kinds of problems.

We have been able to show decidability of several transducer problems over the
data set $\mathbb{N}$ with the linear order. This was done using two
properties: 1) that $\mathbb{N}$ is a substructure of $\mathbb{Q}$ and 2) that
we were able to characterize the iterable loops in $\mathbb{N}$. Moreover we
can transfer the result to other substructures of $\mathbb{Q}$, e.g.
$\mathbb{Z}$. One possible extension would be to investigate data sets which
have a tree-like structure, e.g. the infinite binary tree. There exists a
tree-like oligomorphic structure, of which the binary tree is a substructure.
Studying the iterable loops of the binary tree may yield a similar result as
in the linear order case. But, as it turns out, the notion of quantifier-free
interpretation can directly yield decidability, as the binary tree is a
quantifier-free interpretation of $\mathbb{N}$, thanks to a result of Demri
and Deters [DD16, Section 3]. Indeed, they show that words over a finite
alphabet of size $k$ with the prefix relation (which corresponds to a $k$-ary
tree) can be encoded in $\mathbb{N}$. However, the question remains open for
non-tree-like structures that are substructures of an oligomorphic structure,
for which we might be able to characterize iterable loops.

There are several classical ways of extending synthesis results, for instance
considering larger classes of specifications, larger classes of
implementations or both. In particular, an interesting direction is to
consider non-functional specifications. As mentioned in Introduction however,
and as a motivation for studying the functional case, enlarging both (non-
functional) specifications and implementations to an asynchronous setting
leads to undecidability. Indeed, already in the finite alphabet setting, the
synthesis problem of deterministic transducers over $\omega$-words from
specifications given by non-deterministic transducers is undecidable [CL14]. A
simple adaptation of the proof of [CL14] allows to show that in this finite
alphabet setting, enlarging the class of implementations to any computable
function also yields an undecidable synthesis problem. An interesting case
however is yet unexplored already in the finite alphabet setting: given a
synchronous specifications, as an $\omega$-automaton, is to possible to
synthesise a computable function realizing it? In [HKT12, FLZ11], this
question has been shown to be decidable for specifications with _total_ input
domain (any input word has at least one correct output by the specification).
More precisely, it is shown that realizability by a continuous function is
decidable, but it turns out that the synthesised function is definable by a
deterministic transducer (hence computable). When the domain of the
specification is partial, the situation changes drastically: deterministic
transducers may not suffice to realize a specification realizable by a
computable function. This can be seen by considering the (partial) function
$g$ of Introduction, seen as a specification and casted to a finite alphabet
$\\{a,b,c\\}$: it is not computable by a deterministic transducer, since it
requires an unbounded amount of memory to compute this function.

## References

  * [BKL14] Mikolaj Bojanczyk, Bartek Klin, and Slawomir Lasota.  Automata theory in nominal sets.  Log. Methods Comput. Sci., 10(3), 2014.
  * [Boj19] Mikołaj Bojańczyk.  Atom Book.  2019\.
  * [CHVB18] Edmund M. Clarke, Thomas A. Henzinger, Helmut Veith, and Roderick Bloem, editors.  Handbook of Model Checking.  Springer, 2018.
  * [CL14] Arnaud Carayol and Christof Löding.  Uniformization in Automata Theory.  In Proceedings of the 14th Congress of Logic, Methodology and Philosophy of Science Nancy, July 19-26, 2011, pages 153–178. London: College Publications, 2014.
  * [DD16] Stéphane Demri and Morgan Deters.  Temporal logics on strings with prefix relation.  J. Log. Comput., 26(3):989–1017, 2016.
  * [DFKL20] Vrunda Dave, Emmanuel Filiot, Shankara Narayanan Krishna, and Nathan Lhote.  Synthesis of computable regular functions of infinite words.  In Igor Konnov and Laura Kovács, editors, 31st International Conference on Concurrency Theory, CONCUR 2020, September 1-4, 2020, Vienna, Austria (Virtual Conference), volume 171 of LIPIcs, pages 43:1–43:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020\.
  * [DL09] Stéphane Demri and Ranko Lazic.  LTL with the freeze quantifier and register automata.  ACM Trans. Comput. Log., 10(3):16:1–16:30, 2009.
  * [EFK21] Léo Exibard, Emmanuel Filiot, and Ayrat Khalimov.  Church synthesis on register automata over infinite ordered data domains.  STACS, 2021.
  * [EFR19] Léo Exibard, Emmanuel Filiot, and Pierre-Alain Reynier.  Synthesis of data word transducers.  In 30th International Conference on Concurrency Theory, CONCUR 2019, August 27-30, 2019, Amsterdam, the Netherlands., pages 24:1–24:15, 2019\.
  * [EFR20] Léo Exibard, Emmanuel Filiot, and Pierre-Alain Reynier.  On computability of data word functions defined by transducers.  In Jean Goubault-Larrecq and Barbara König, editors, Foundations of Software Science and Computation Structures - 23rd International Conference, FOSSACS 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25-30, 2020, Proceedings, volume 12077 of Lecture Notes in Computer Science, pages 217–236. Springer, 2020.
  * [ESKG14] Rüdiger Ehlers, Sanjit A. Seshia, and Hadas Kress-Gazit.  Synthesis with identifiers.  In Proceedings of the 15th International Conference on Verification, Model Checking, and Abstract Interpretation - Volume 8318, VMCAI 2014, pages 415–433, 2014.
  * [Exi21] Léo Exibard.  Automatic Synthesis of Systems with Data.  Theses, Aix Marseille Université (AMU); Université libre de Bruxelles (ULB), September 2021.
  * [FJLW16] Emmanuel Filiot, Ismaël Jecker, Christof Löding, and Sarah Winter.  On equivalence and uniformisation problems for finite transducers.  In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, Rome, Italy, pages 125:1–125:14, 2016.
  * [FLZ11] Wladimir Fridman, Christof Löding, and Martin Zimmermann.  Degrees of lookahead in context-free infinite games.  In Marc Bezem, editor, Computer Science Logic, 25th International Workshop / 20th Annual Conference of the EACSL, CSL 2011, September 12-15, 2011, Bergen, Norway, Proceedings, volume 12 of LIPIcs, pages 264–276. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2011.
  * [HKT12] Michael Holtmann, Lukasz Kaiser, and Wolfgang Thomas.  Degrees of lookahead in regular infinite games.  Logical Methods in Computer Science, 8(3), 2012.
  * [JL69] J.R. Büchi and L.H. Landweber.  Solving sequential conditions finite-state strategies.  Transactions of the American Mathematical Society, 138:295–311, 1969.
  * [KK19] Ayrat Khalimov and Orna Kupferman.  Register-bounded synthesis.  In 30th International Conference on Concurrency Theory, CONCUR 2019, August 27-30, 2019, Amsterdam, the Netherlands., pages 25:1–25:16, 2019\.
  * [KMB18] Ayrat Khalimov, Benedikt Maderbacher, and Roderick Bloem.  Bounded synthesis of register transducers.  In Automated Technology for Verification and Analysis, 16th International Symposium, ATVA 2018, Los Angeles, October 7-10, 2018. Proceedings, 2018.
  * [KZ10] Michael Kaminski and Daniel Zeitlin.  Finite-memory automata with non-deterministic reassignment.  Int. J. Found. Comput. Sci., 21(5):741–760, 2010.
  * [MH94] Bohdan S. Majewski and George Havas.  The complexity of greatest common divisor computations.  In Leonard M. Adleman and Ming-Deh A. Huang, editors, Algorithmic Number Theory, First International Symposium, ANTS-I, Ithaca, NY, USA, May 6-9, 1994, Proceedings, volume 877 of Lecture Notes in Computer Science, pages 184–193. Springer, 1994.
  * [Pri02] Christophe Prieur.  How to decide continuity of rational functions on infinite words.  Theor. Comput. Sci., 276(1-2):445–447, 2002.
  * [WZ20] Sarah Winter and Martin Zimmermann.  Finite-state strategies in delay games.  Inf. Comput., 272:104500, 2020.

##  Appendix A Proof of Lemma 14

Recall Lemma 14: See 14 In order to show the lemma we use the result from
[MH94, Theorem 9]:

######  Theorem 47.

Let $p_{1},\ldots,p_{k}\in\mathbb{Z}{\setminus}{\left\\{0\right\\}}$ be non-
zero integers. Then there exist integers
$z_{1},\ldots,z_{k}\leq\max(|p_{1}|,\ldots,|p_{k}|)$ such that:

$z_{1}p_{1}+\ldots+z_{k}p_{k}=\gcd(p_{1},\ldots,p_{k})$

It is more convenient to split the integers into two groups depending on their
signs. Let $p_{0},\ldots,p_{k}$ be positive integers and $q_{0},\ldots,q_{l}$
be negative integers, let $d=\gcd(p_{0},\ldots,p_{k},q_{0},\ldots,q_{l})$ and
let $M=\max(p_{0},\ldots,p_{k},-q_{0},\ldots,-q_{l})$. Using the previous
theorem, we know there are integers $m_{0},\ldots,m_{k}$ and
$n_{0},\ldots,n_{l}$ all in $[-M,M]$ so that $\sum_{0\leq i\leq
k}m_{i}p_{i}+\sum_{0\leq j\leq l}n_{i}q_{i}=d$. We modify the coefficients in
the following way: $m_{0}^{\prime}=m_{0}-M\sum_{1\leq j\leq l}q_{j}$,
$m_{i}^{\prime}=m_{i}-Mq_{0}$ for $i\in\left\\{1,\ldots,k\right\\}$,
$n_{0}^{\prime}=n_{0}+M\sum_{1\leq i\leq k}p_{i}$,
$n_{j}^{\prime}=n_{j}+Mp_{0}$ for $j\in\left\\{1,\ldots,l\right\\}$. Note that
all the new coefficients are positive. We only have left to check that the sum
is unchanged.

$\begin{array}[]{l}\sum_{0\leq i\leq k}m_{i}^{\prime}p_{i}+\sum_{0\leq j\leq
l}n_{i}^{\prime}q_{i}=\\\ \sum_{0\leq i\leq k}m_{i}p_{i}-p_{0}M\sum_{1\leq
j\leq l}q_{j}-\sum_{0\leq i\leq k}Mq_{0}p_{i}\\\ +\sum_{0\leq j\leq
l}n_{i}q_{i}+q_{0}M\sum_{1\leq i\leq k}p_{i}+\sum_{0\leq j\leq
l}Mp_{0}q_{j}\\\ =\sum_{0\leq i\leq k}m_{i}p_{i}+\sum_{0\leq j\leq
l}n_{i}q_{i}\end{array}$

We have manage to obtain positive coefficients, all smaller than $M^{3}$.

##  Appendix B Proof of Lemma 30

Recall Lemma 30: See 30

######  Proof B.1.

There are two cases:

  * •

If $d-c=b-a$, then take $f:x\rightarrow x+c-a$.

  * •

Otherwise, define $f$ as: for all $x\in[a;b-1]$ (note that such interval can
be empty), let $f(x)=x+c-a$ as above. Then, for $x\in[b-1;b]$, let
$e=c+(b-1-a)$ and $f(x)=d-(b-x)(d-e)$. We have $f(b-1)=e$, which is consistent
with the definition of $f$ on $[a;b-1]$, and $f(b)=d$, and $f$ is moreover
increasing and bijective. Finally, $f(b-1)\in\mathbb{N}$ and
$f(b)\in\mathbb{N}$. Overall, $f$ satisfies the required properties.

•$a$•$c$$\cdots$•$b-1$•$e=c+(b-1-a)$•$b-1/2$•$e+\dfrac{d-e}{2}$•$b$•$d$


# Noisy detectors with unmatched detection efficiency thwart identification of
single photon emitters via photon coincidence correlation

Darien J. Morrow<EMAIL_ADDRESS>Center for Nanoscale Materials, Argonne
National Laboratory, Lemont, Illinois 60439, United States  Xuedan Ma
<EMAIL_ADDRESS>Center for Nanoscale Materials, Argonne National Laboratory,
Lemont, Illinois 60439, United States  Consortium for Advanced Science and
Engineering, University of Chicago, Chicago, Illinois 60637, United States
Northwestern-Argonne Institute of Science and Engineering, 2205 Tech Drive,
Evanston, IL 60208, USA

###### Abstract

Single photon emitters (SPEs) are often identified with a Hanbury Brown and
Twiss intensity interferometer (HBTII) consisting of a 50:50 beamsplitter and
two time-correlated single photon counters. For an SPE, the cross-correlation
of photon arrival time between the two detectors, $g^{(2)}(\tau)$, shows a
hallmark dip to zero at $\tau=0$. One common heuristic for identifying SPEs is
by measuring a system to have $g^{(2)}(0)<1/2$. Here in, we use stochastic
methods to simulate the case of a SPE observed with non-ideal detectors and
optics. We show that identification of SPEs is thwarted when the detectors
have asymmetric detection efficiency, and when detector background noise is
more than half the true SPE signal rate.

Single photon emitters (SPEs) play a crucial role in many extant and proposed
quantum information technologies.[1, 2] Categorization of an emitter as a SPE
is usually accomplished by measuring the degree of second-order temporal
coherence, $g^{(2)}(\tau)$, of the emission. For photons described by Fock
states, $|n\rangle$, of number $n$, the second-order coherence is[3, 4]

$\displaystyle g^{(2)}(\tau)$ $\displaystyle=\frac{\left\langle
n^{2}\right\rangle-\left\langle n\right\rangle}{\left\langle
n\right\rangle^{2}}$ (1) $\displaystyle=1-\frac{1}{n}\text{ for }n\geq 1.$ (2)

If only one photon exists at a time then $g^{(2)}(\tau)=0$, and if two photons
exist at a time then $g^{(2)}(\tau)=1/2$; this analysis implies that if an
emitter is found to have $g^{(2)}(0)<1/2$, that emitter must be a SPE.[5, 6]

In order to measure $g^{(2)}(\tau)$, most labs employ variants of the Hanbury
Brown and Twiss intensity interferometer (HBTII) consisting of a 50:50
beamsplitter which feeds two detector arms equipped with time correlated
single photon counters.[7] In terms of the long-time average intensity,
$\bar{I}$, the normalized second order coherence is[3, 4, 8]

$\displaystyle
g^{(2)}(\tau)=\frac{\left\langle\bar{I}(t)\bar{I}(t+\tau)\right\rangle}{\bar{I}^{2}},$
(3)

which has properties of $g^{(2)}(0)\geq 1$ for thermal emission and
$g^{(2)}(0)=1$ for coherent (random, Poissonian) emission. Classical (not
quantized) light exhibits bunching $g^{(2)}(0)\geq 1$ while quantum light
exhibits antibunching $g^{(2)}(0)<1$. Experimentally, a conspicuous dip of
$g^{(2)}(\tau)$ near $\tau=0$ heralds the existence of a quantized
phenomena.[9] Figure 1 shows simulated correlation functions when the emitters
are excited by continuous (Figure 1a) or pulsed (Figure 1b,c) sources.

Figure 1: Simulation of photon antibunching data. (a) Cross-correlation from a
HBTII where the length of one arm is swept while measuring fluorescence from a
chromophore excited with a continuous wave (CW) source. (b,c) Cross-
correlation of photon arrival times at two time-tagging detectors when
measuring fluorescence from a chromophore excited with a pulsed source. (b)
shows prominent antibunching in photon arrival time while (c) exhibits random
(Poisson statistics) arrival times.

Traditionally, background counts originating from scattered excitation light,
or detector shot noise are understood to uniformly increase the value of
$g^{(2)}(\tau=0)$ measured by a HBTII.[8, 10, 11, 12] Simplistically, if a SPE
measurement is saturated with truly random background noise, the coherent case
of $g^{(2)}(0)=1$ results.[10] While ubiquitous, background noise is not the
only nonideality which can plague SPE measurements. In our lab, we have
identified three phenomena which can possibly complicate the measurement of
SPEs with our HBTIIs:

  * •

high levels of random background noise logged by both photon counting modules,

  * •

photon counting modules with different quantum efficiencies or beamsplitters
which do not evenly feed the counting modules,

  * •

and photon counting modules with intrinsically different background count
rates.

This work computationally demonstrates how these three phenomena can conspire
to make SPE identification impossible.

To model the role of these three nonidealities, we imagine an impulsive,
pulsed source exciting a single, perfect SPE which emits exactly one photon
per excitation pulse resulting in a photon emission rate of $k_{S}$. As
diagrammed in Figure 2, the stream of photons from the SPE is split into two
streams, $k_{A,S}^{\prime}$ and $k_{B,S}^{\prime}$, which excite two
detectors, $A$ and $B$, respectively. The beamsplitter is assumed to be
lossless,

$\displaystyle k_{S}=k_{A,S}^{\prime}+k_{B,S}^{\prime}.$ (4)

If the detectors are asymmetrically fed by the beamsplitter (e.g. it is not
50:50) or if they have different quantum efficiencies, $\Xi$, then the
effective count rate is

$\displaystyle k_{A,S}$ $\displaystyle=\Xi\left(\frac{1}{2}+\xi\right)k_{S},$
(5) $\displaystyle k_{B,S}$
$\displaystyle=\Xi\left(\frac{1}{2}-\xi\right)k_{S},$ (6)

for $\xi\in(-1/2,1/2)$ and $\Xi\in(0,1]$. For this work, we let $\Xi=1$.

Figure 2: Idealized Hanbury Brown and Twiss intensity interferometer. A and B
are detectors which detect fluorescence signal at a rate of $k_{A,S}$ and
$k_{B,S}$, respectively. Dark (background) counts are recorded at a rate of
$k_{A,D}$ and $k_{B,D}$, respectively.

To add noise to our model, we define a total background count rate, $k_{D}$,
in reference to the total signal rate,

$\displaystyle k_{D}=\sigma\Xi k_{S},$ (7)

with $\sigma$ being the _noise factor_ which connects the two rates. Just like
the signal rate, the background rate is losslessly split and fed into the two
detectors

$\displaystyle k_{A,D}$ $\displaystyle=\left(\frac{1}{2}+\chi\right)k_{D},$
(8) $\displaystyle k_{B,D}$
$\displaystyle=\left(\frac{1}{2}-\chi\right)k_{D},$ (9)

with $\chi\in[-1/2,1/2]$ being the background rate asymmetry between the two
detectors.

This system of rates encodes in scalar factors the three detrimental phenomena
previously listed:

  * •

$\sigma$ describes the _background count rate_ relative to the signal count
rate, it can be experimentally controlled by e.g. cooling the detectors;[13,
14, 15, 16]

  * •

$\xi$ describes the _asymmetry in signal rates_ between the two detectors, it
can be experimentally controlled by e.g. adding neutral density filters in
front of one of the detectors;

  * •

$\chi$ describes the _asymmetry in background rates_ between the two
detectors, it is hard to experimentally control because it is caused by e.g.
differences in trap concentration in the active elements of the detectors.[15,
16]

A HBTII instrument yields two streams of photons whose arrival times at the
two detectors are recorded. We write the digital data streams from the
detectors A and B as $A(t)$ and $B(t)$ where $t$ is laboratory time. $A(t)=1$
($B(t)=1$) if a photon hits detector A (B) at time $t$, while $A(t)=0$
($B(t)=0$) if no photon hits detector A (B) at time $t$. The normalized cross-
correlation between the two data streams,111For continuous functions the
cross-correlation, $z$, is given by,$z(\tau)=(x\star
y)(\tau)\equiv\int_{-\infty}^{\infty}\overline{x(t)}y(t+\tau)dt$ where
$\overline{f(t)}$ is the complex conjugate of $f(t)$. For finite, 1D arrays
the cross-correlation is instead $z[k]=(x\star
y)(k-N+1)=\sum_{l=0}^{||x||-1}x_{l}\overline{y_{l-k+N-1}}$ for
$k=0,1,\dots,||x||+||y||-2$ in which $||x||$ is the length of $x$,
$N=\max(||x||,||y||)$ and $y_{m}$ is zero-padded such that when $m$ is outside
the range of $y$ then $y_{m}=0$.

$\displaystyle g^{(2)}(\tau)=\frac{A(t)\star B(t)}{\left|\left|A(t)\star
B(t)\right|\right|},$ (10)

is analogous to Equation 3. For experiments conducted with pulsed excitation
sources it is common to quantify $g^{(2)}(0)$ using integrals over specific
pulse periods ($T$) of the excitation laser

$\displaystyle g^{(2)}(0)\approx\frac{2n\int_{-T/2}^{T/2}(A\star
B)\textrm{d}t}{\int_{-nT-T/2}^{-T/2}(A\star
B)\textrm{d}t+\int_{T/2}^{nT+T/2}(A\star B)\textrm{d}t}$ (11)

where $n$ is a small, positive integer. This is the definition of $g^{(2)}(0)$
which we will use for the remainder of this work.

In order to simulate measurement of a SPE, we assume impulsive excitation,
emission, and detection of the SPE with unity quantum efficiency. This Dirac-
delta distribution nature of dynamic processes allows us to write the data
streams, $A$ and $B$, as simple 1D numerical arrays whose index is identical
to the laser pulse period. To populate $A$ and $B$, for each array index, $i$,
a random number, $\rho$, is drawn from a uniform distribution, $\rho\in[0,1)$
and the arrays are written as:

  * •

If $\rho_{i}<0.5+\xi$ then $A[i]=1$ and $B[i]=0$.

  * •

If instead $\rho_{i}>0.5+\xi$ then $A[i]=0$ and $B[i]=1$

To add noise into the data stream, the arrays are updated using two more
random numbers, $\rho^{\prime}\in[0,1)$ and $\rho^{\prime\prime}\in[0,1)$:

  * •

If $\rho_{i}^{\prime}<0.5+\chi$ then
$A[i]\stackrel{{\scriptstyle+}}{{=}}\sigma$ if not,
$A[i]\stackrel{{\scriptstyle+}}{{=}}0$,

  * •

If $\rho_{i}^{\prime\prime}>0.5+\chi$ then
$B[i]\stackrel{{\scriptstyle+}}{{=}}\sigma$ if not,
$B[i]\stackrel{{\scriptstyle+}}{{=}}0$,

with the generation of $\rho^{\prime}$ and $\rho^{\prime\prime}$ being
uncorrelated to ensure the background noise is not correlated between the two
detectors. This iterative array population is accomplished for arrays of size
$N$. $N$ is both the number of pulse periods over which the experiment has run
as well as the number of single photon emission events.

We first simulate the role that an increase in background noise plays in
determining the value of $g^{(2)}(\tau)$ when noise and signal counts are
symmetrically distributed across the two detectors ($\xi=\chi=0$). Figure 3a
shows that with no background noise, $\sigma=0$, $g^{(2)}(0)=0$. As noise
increases, $g^{(2)}(0)$ smoothly increases until it passes $g^{(2)}(0)=0.5$ at
around $\sigma=0.4$; above this point the simulation indicates that detector
noise makes it impossible to identify SPEs using only the metric of
$g^{(2)}(0)<0.5$. Figure 3b likewise shows how the temporal structure of
$g^{(2)}(\tau)$ smoothly evolves as background noise increases—note the
resemblance of Figure 3b to a Dirac comb distribution. Figure 3 demonstrates
that our model recovers the common observation that background noise pushes up
the minimum achievable value of $g^{(2)}(0)$.[8, 10, 11, 12]

Figure 3: $g^{(2)}(\tau)$ as noise factor is increased for $\xi=\chi=0$
($N=20000$). (a) shows that $g^{(2)}(\tau=0)$ increases as noise is increased,
values of $g^{(2)}(0)>1/2$ are highlighted by red fill. (b) shows
$g^{(2)}(\tau)$ for three different noise scales (from bottom to top:
$\sigma=0$, $\sigma=0.2$, and $\sigma=0.6$) emphasizing the Dirac delta nature
of the simulation in comparison to the finite distributions of Figure 1b,c.

Next we model how asymmetry in the detection efficiency or noise distribution
affects the observable values of $g^{(2)}(0)$. Figure 4a demonstrates that
both background noise and detection efficiency asymmetry increase the
observable value of $g^{(2)}(0)$. As an example, for $\xi=0.3$ (i.e. an 80:20
beamsplitter) a noise factor of a little more than $\sigma=0.2$ causes our
ideal SPE to not be identified as a SPE using the $g^{(2)}(0)<0.5$ rule-of-
thumb.

Figure 4: $g^{(2)}(0)$ as a function of background noise and detector
asymmetry in signal (a) and noise (b). Note that the colormap is blue for
values of $g^{(2)}(0)<0.5$ which traditionally is the metric of a single
photon emitter. We draw a gray contour line at $g^{(2)}(0)=0.5$.

When there is no detection asymmetry, $\xi=0$, increasing the asymmetry of
noise, $\chi$, between the two detectors does not greatly affect the cutoff
value of noise for $g^{(2)}(0)<0.5$ (Figure 4b). If only one detector has
background noise ($\chi=0.5$) then the HBTII can still identify a SPE even
with the noisy detector having the same signal and noise count rates. This
effect may be rationalized by considering how a noise rate of $\sigma k_{S}$
on only one of the two detectors factors into Equation 11,

$\displaystyle g^{(2)}(0)=\frac{0+\sigma k_{S}}{k_{S}+\sigma k_{S}}.$ (12)

When noise and signal rates at one detector are similar ($\sigma=0.5$,
$k_{A,D}=k_{A,S}=k_{B,S}$, $k_{D,S}=0$) then $g^{(2)}(0)=0.5$. This
observations yields a heuristic that SPE identification is severely hampered
if the combined background noise rates of both detectors is greater than 50%
of the combined signal rates.

In order to further investigate the inability to measure $g^{(2)}(0)<0.5$ when
$\sigma\gtrsim 0.5$, we simulate how $g^{(2)}(0)$ changes jointly as a
function of $\xi$ and $\chi$ while stepping through values of $\sigma$ (Figure
5). Figure 5f shows that when $\sigma=1$ there are no values of $\xi$ and
$\chi$ which yields $g^{(2)}(0)<0.5$. As the noise factor decreases a region
around the line $\xi=\chi$ begins to have $g^{(2)}(0)<0.5$. At low background
noise levels, all but the largest signal detection asymmetries yield
$g^{(2)}(0)<0.5$.

Figure 5: $g^{(2)}(0)$ as a function of asymmetry of noise and signal for the
two detectors. The noise factor, $\sigma$, is varied from 0.1 to 1 in these
figures.

Taken together, this work allows us to bound the region of noise rates and
detection asymmetry which can hamper SPE categorization with a HBTII. Because
this work assumes the platonic ideal of both SPEs and HBTIIs with exactly one
photon emitted and detected per excitation pulse period, the derived
heuristics should be taken as an upper-bound on the non-idealities which can
exist and still allow for categorization of SPEs.

For facile categorization of SPEs, the signal count rate at the individual
detectors must be larger than the noise count rate for each detector.
Asymmetry in signal detection efficiency should be ardently avoided; larger
amounts of background noise compounds the detrimental nature of asymmetric
signal detection. Conversely, asymmetry in background noise between the two
detectors does not have a significant detrimental effect on a HBTII’s ability
to categorize SPEs. If one does have asymmetric signal and noise rates between
the two detectors, it is best to match them so one detector has both the
highest signal and background noise rates.

Finally, we note that while $g^{(2)}(0)<0.5$ is a fundamental characteristic
of a SPE (Equation 2), imperfections in the HBTII characterizing the SPE can
make it impossible to categorize the SPE as such. Much like recent work which
indicated that, within experimental limitations, $g^{(2)}(0)$ is a poor metric
for categorizing the lasing threshold of microlasers,[18] here we stress that
$g^{(2)}(0)<0.5$ is only a good identifier for SPEs when background noise is
less than half the fundamental signal rate and detectors are matched in
efficiency.

This work was performed at the Center for Nanoscale Materials, a U.S.
Department of Energy Office of Science User Facility, was supported by the
U.S. DOE, Office of Basic Energy Sciences, under Contract No. DE-
AC02-06CH11357.

## References

  * Aharonovich  _et al._ [2016] I. Aharonovich, D. Englund, and M. Toth, Solid-state single-photon emitters, Nat. Photon. 10, 631 (2016).
  * O'Brien  _et al._ [2009] J. L. O'Brien, A. Furusawa, and J. Vučković, Photonic quantum technologies, Nat. Photon. 3, 687 (2009).
  * Loudon [2000] R. Loudon,  _The quantum theory of light_ , 3rd ed. (Oxford University Press, 2000).
  * Paul [1982] H. Paul, Photon antibunching, Rev. of Mod. Phys. 54, 1061 (1982).
  * Michler  _et al._ [2000] P. Michler, A. Kiraz, C. Becher, W. V. Schoenfeld, P. M. Petroff, L. Zhang, E. Hu, and A. Imamoǧlu, A quantum dot single-photon turnstile device, Science 290, 2282 (2000).
  * Högele  _et al._ [2008] A. Högele, C. Galland, M. Winger, and A. Imamoğlu, Photon antibunching in the photoluminescence spectra of a single carbon nanotube, Phys. Rev. Lett. 100, 217401 (2008).
  * Brown and Twiss [1956] R. H. Brown and R. Q. Twiss, Correlation between photons in two coherent beams of light, Nature 177, 27 (1956).
  * Kimble  _et al._ [1977] H. J. Kimble, M. Dagenais, and L. Mandel, Photon antibunching in resonance fluorescence, Phys. Rev. Lett. 39, 691 (1977).
  * Walls [1979] D. F. Walls, Evidence for the quantum nature of light, Nature 280, 451 (1979).
  * Brouri  _et al._ [2000] R. Brouri, A. Beveratos, J.-P. Poizat, and P. Grangier, Photon antibunching in the fluorescence of individual color centers in diamond, Opt. Lett. 25, 1294 (2000).
  * Kuhn  _et al._ [2002] A. Kuhn, M. Hennrich, and G. Rempe, Deterministic single-photon source for distributed quantum networking, Phys. Rev. Lett. 89, 067901 (2002).
  * Kurtsiefer  _et al._ [2000] C. Kurtsiefer, S. Mayer, P. Zarda, and H. Weinfurter, Stable solid-state source of single photons, Phys. Rev. Lett. 85, 290 (2000).
  * Hofbauer  _et al._ [2018] M. Hofbauer, B. Steindl, and H. Zimmermann, Temperature dependence of dark count rate and after pulsing of a single-photon avalanche diode with an integrated active quenching circuit in 0.35 $\mu$m CMOS, Journal of Sensors 2018, 1 (2018).
  * Richardson  _et al._ [2009] J. Richardson, L. Grant, and R. Henderson, Low dark count single-photon avalanche diode structure compatible with standard nanometer scale CMOS technology, IEEE Photonics Technology Letters 21, 1020 (2009).
  * Kang  _et al._ [2003] Y. Kang, H. X. Lu, Y.-H. Lo, D. S. Bethune, and W. P. Risk, Dark count probability and quantum efficiency of avalanche photodiodes for single-photon detection, Appl. Phys. Lett. 83, 2955 (2003).
  * Spinelli and Lacaita [1997] A. Spinelli and A. Lacaita, Physics and numerical simulation of single photon avalanche diodes, IEEE Transactions on Electron Devices 44, 1931 (1997).
  * Note [1] For continuous functions the cross-correlation, $z$, is given by,$z(\tau)=(x\star y)(\tau)\equiv\intop\ilimits@_{-\infty}^{\infty}\overline{x(t)}y(t+\tau)dt$ where $\overline{f(t)}$ is the complex conjugate of $f(t)$. For finite, 1D arrays the cross-correlation is instead $z[k]=(x\star y)(k-N+1)=\sum@\slimits@_{l=0}^{||x||-1}x_{l}\overline{y_{l-k+N-1}}$ for $k=0,1,\dots,||x||+||y||-2$ in which $||x||$ is the length of $x$, $N=\mathop{max}\displaylimits(||x||,||y||)$ and $y_{m}$ is zero-padded such that when $m$ is outside the range of $y$ then $y_{m}=0$.
  * Carroll  _et al._ [2021] M. A. Carroll, G. D’Alessandro, G. L. Lippi, G.-L. Oppo, and F. Papoff, Thermal, quantum antibunching and lasing thresholds from single emitters to macroscopic devices, Phys. Rev. Lett. 126, 063902 (2021).