††thanks<EMAIL_ADDRESS>Deceased 5 June, 2020.

# Boosting photonic quantum computation with moderate nonlinearity

A. Pick  Department of Chemical Physics, Weizmann Institute of Science,
Rehovot 76100, Israel  E. S. Matekole  Department of Physics and Astronomy,
Louisiana State University, Baton Rouge, LA 70803, USA  Z. Aqua  Department of
Chemical Physics, Weizmann Institute of Science, Rehovot 76100, Israel  G.
Guendelman  Department of Chemical Physics, Weizmann Institute of Science,
Rehovot 76100, Israel  O. Firstenberg  Department of Physics, Weizmann
Institute of Science, Rehovot 76100, Israel  J. P. Dowling  Department of
Physics and Astronomy, Louisiana State University, Baton Rouge, LA 70803, USA
B. Dayan  Department of Chemical Physics, Weizmann Institute of Science,
Rehovot 76100, Israel

Photonic measurement-based quantum computation (MBQC) is a promising route
towards fault-tolerant universal quantum computing. A central challenge in
this effort is the huge overhead in the resources required for the
construction of large photonic clusters using probabilistic linear-optics
gates. Although strong single-photon nonlinearity ideally enables
deterministic construction of such clusters, it is challenging to realise in a
scalable way. Here we explore the prospects of using moderate nonlinearity
(with conditional phase shifts smaller than $\pi$) to boost photonic quantum
computing and significantly reduce its resources overhead. The key element in
our scheme is a nonlinear router that preferentially directs photonic
wavepackets to different output ports depending on their intensity. As a
relevant example, we analyze the nonlinearity provided by Rydberg blockade in
atomic ensembles, in which the trade-off between the nonlinearity and the
accompanying loss is well understood. We present protocols for efficient Bell
measurement and GHZ-state preparation – both key elements in the construction
of cluster states, as well as for the CNOT gate and quantum factorization.
Given the large number of entangling operations involved in fault-tolerant
MBQC, the increase in success probability provided by our protocols already at
moderate nonlinearities can result in a dramatic reduction in the required
resources.

Photonic quantum computation is a leading platform in the effort towards
fault-tolerant universal quantum computers Kok  _et al._ (2007); O’brien  _et
al._ (2009); Rudolph (2017); Bartolucci  _et al._ (2021). It combines the
paradigm of measurement-based quantum computation (MBQC) Gottesman and Chuang
(1999); Raussendorf and Briegel (2001); Knill  _et al._ (2001); Nielsen
(2003); Verstraete and Cirac (2004); Leung (2004); Briegel  _et al._ (2009),
where the computation is carried out by applying a sequence of measurements to
entangled cluster states Briegel and Raussendorf (2001); Hein  _et al._
(2004); Nielsen (2004) with topological quantum error correction Gottesman
(1997); Bravyi and Kitaev (2005); Varnava  _et al._ (2006); Dawson  _et al._
(2006); Raussendorf  _et al._ (2007); Fowler  _et al._ (2012). In particular,
the promise of all-optical photonic quantum computation with discrete
variables 111Our work focuses on discrete-variable quantum computation. While
large clusters of squeezed states have been demonstrated in continuous-
variable quantum computation Yokoyama  _et al._ (2013); Chen  _et al._ (2014);
Reimer  _et al._ (2016); Asavanant  _et al._ (2019), the latter approach faces
other challenges that currently hinder its scalability, including the
generation of Gottesman-Kitaev-Preskill (GKP) states Gottesman  _et al._
(2001). lies in the ability to entangle single photons into graphs and
clusters using only linear-optics probabilistic operations Zeilinger  _et al._
(1997); Browne and Rudolph (2005); Lu  _et al._ (2007); Kieling  _et al._
(2007); Wilde  _et al._ (2007); Shadbolt  _et al._ (2012); Wang  _et al._
(2016); Istrati  _et al._ (2020). The price, however, is a huge overhead:
constructing a cluster of $10^{7}$ photons (corresponding to $\sim 1000$
logical qubits, assuming $10^{4}\times$ redundancy for error correction) with
probabilistic gates may require $10^{12}$ input single photons Li  _et al._
(2015).

One approach to tackle this challenge is efficient and strong interaction with
single quantum emitters, such as atoms, ions, or quantum dots. Such coupling
ideally enables deterministic construction of cluster states either by
generation of a stream of entangled photons Schön  _et al._ (2007); Lindner
and Rudolph (2009); Schwartz  _et al._ (2016); Pichler  _et al._ (2017), or by
entangling single photons via photon-atom quantum gates Duan and Kimble
(2004); Reiserer  _et al._ (2014); Hacker  _et al._ (2016); Rosenblum  _et
al._ (2017); Bechler  _et al._ (2018); Borregaard  _et al._ (2019). However,
achieving strong interaction with single quantum emitters requires challenging
optical structures, which are not straightforwardly scalable. A number of
theoretical works explored the possibility of enhancing weak Kerr-type
nonlinearities by classical driving fields to make them strong enough to
support photonic quantum computation Paris  _et al._ (2000); Nemoto and Munro
(2004, 2005); Munro  _et al._ (2005a, b); Barrett  _et al._ (2005); Shapiro
(2006); Louis  _et al._ (2007); Shapiro and Razavi (2007); Gea-Banacloche
(2010). To be precise, we define nonlinearity as “strong” if it can provide a
conditional phase shift $\varphi=\pi$; namely, a difference of $\pi$ between
twice the phase acquired by a single photon in a mode, and the phase acquired
by two photons in the same mode.

In contrast to previous studies, here we explore whether there is an
intermediate regime between the linear optics and strong nonlinearity regimes
in which moderate nonlinearity can provide a practical advantage. The
motivation is that since fault-tolerant photonic quantum computation involves
a large number of probabilistic gates Li  _et al._ (2015), even a small
improvement in the success probability per gate could amount to a dramatic
reduction in the required resources. The reason for focusing on moderate
nonlinearity is that attaining small phase shifts (e.g., $\pi/10$) typically
requires significantly less resources than attaining $\pi$, and, accordingly,
is accompanied by much lower costs, such as, in particular, photon loss, which
is the dominant fault mechanism in photonic qubits. Although advanced
protocols for photonic quantum computing can tolerate up to 50$\%$ overall
photon loss (being an inherently detectable error in most cases) Varnava  _et
al._ (2006); Stace  _et al._ (2009); Barrett and Stace (2010); Bartolucci  _et
al._ (2021), the large number of elements and operations involved makes
reaching this level challenging nonetheless. Given the progress in photonic
technologies, including large scale on-chip single-photon detection
capabilities with superconducting nanowires Marsili  _et al._ (2013); Reddy
_et al._ (2020), the additional loss induced by the nonlinear medium itself
will likely become the dominant one. We therefore wish to quantify the trade-
off offered by introducing nonlinear elements to the task of graph-states
construction, namely increasing the success probability of each operation at
the price of significant additional loss.

In order to take loss into account as accurately as possible, we consider
below the very relevant and well-studied platform of electromagnetically-
induced transparency (EIT Boller  _et al._ (1991)) with Rydberg atoms
(Rydberg-EIT) Distante  _et al._ (2017); Tiarks  _et al._ (2019). In these
systems, the loss grows quadratically with the conditional phase shift
$\varphi$ (for small $\varphi$), which is eventually limited by the physical
parameters of the Rydberg ensemble Lahad and Firstenberg (2017).

Figure 1: Nonlinear router: (a) When a photon enters the interferometer in
mode $a$, it leaves in $u$. (b) The interferometer contains a nonlinear medium
(NL, gray) in both arms. Photon pairs traveling through different arms acquire
opposite conditional phases $\pm\varphi$ [Eq. (2)]. When $\varphi=\pi$, a pair
that enters in mode $a$ leaves in mode $w$. (c) Probabilities for detection
outcomes for an incoming pair in mode $a$ when $\varphi\in[0,\pi]$: both
photons in $u$ (brown), both in $w$ (blue), and one in each mode (green).
Solid lines show a loss-free model [Eq. (3)]. Dashed lines include nonlinear
loss in Rydberg-EIT systems [Eq. (6)]. We assume that the optical depth of the
blockaded volume is $\text{OD}_{\text{b}}=30$, which sets the loss probability
$\tau(\varphi)$ via Eq. (5), as shown in (d). The relation between the
attenuation coefficient, $\varepsilon\equiv-\ln(1-\tau)$, and $\varphi$ is a
circle Lahad and Firstenberg (2017), plotted for $\text{OD}_{\text{b}}=3.5$
and 8 (red and black).

The key element in our protocols is a nonlinear router Rosenblum  _et al._
(2016); Tiecke  _et al._ (2014); Ralph  _et al._ (2015), realized by a
Mach–Zehnder interferometer (MZI) with a nonlinear medium in both arms (Fig.
1). The conditional phase-shift acquired by two-photon pulses (photon pairs)
in the nonlinear media causes the router to preferentially direct single
photon pulses to one port and photon pairs to another. We use the router to
obtain nonlinearity-enhanced protocols for Bell-state measurement (BM) and for
Greenberger–Horne–Zeilinger (GHZ) state preparation (Figs. 2 and 3), which are
key building blocks in MBQC Gottesman and Chuang (1999). As an application, we
use these elements to construct protocols for a CNOT gate and quantum
factorization (Fig. 4). By adding nonlinearity, our protocols outperform the
linear methods, potentially reducing resource requirements for fault-tolerant
photonic quantum computing by up to two orders of magnitude already at
moderate nonlinearities.

Nonlinear router: As shown in Fig. 1(a), when single photons enter the MZI in
mode $a$, they exit through port $u$, following the transformation rule Gerry
_et al._ (2005):

$\displaystyle
a^{\dagger}\xrightarrow[]{\text{BS1}}1/\sqrt{2}(f^{\dagger}+ig^{\dagger})\xrightarrow[]{\text{BS2}}u^{\dagger}.$
(1)

The MZI contains a nonlinear atomic medium that induces opposite conditional
phase shifts $\pm\varphi$ for photon pairs in each of its arms:

$\displaystyle(f^{\dagger})^{2}\rightarrow
e^{i\varphi}(f^{\dagger})^{2}\quad,\quad(g^{\dagger})^{2}\rightarrow
e^{-i\varphi}(g^{\dagger})^{2}.$ (2)

As a result, photon pairs undergo the transformation

$\displaystyle\scalebox{0.9}{$\left(a^{\dagger}\right)^{2}\\!\\!\xrightarrow[]{\text{BS1}}\\!\tfrac{1}{2}\left(e^{i\tfrac{\varphi}{2}}f^{\dagger}+ie^{-i\tfrac{\varphi}{2}}g^{\dagger}\right)^{2}\\!\xrightarrow[]{\text{BS2}}\\!\left(w^{\dagger}\sin\tfrac{\varphi}{2}+u^{\dagger}\cos\tfrac{\varphi}{2}\right)^{2}$}.$
(3)

Consequently, the probability of routing pairs to the second output mode $w$
increases monotonously with $\varphi$ [Fig. 1(c)]. For $\varphi=\pi$, the
nonlinear router deterministically separates pairs to a different port than
single photons [Fig. 1(b)].

The effect of photon loss: Our schemes can be implemented with any nonlinear
medium that provides moderate conditional phase shifts, including tightly
confined atomic ensembles (e.g., atom-cladded optical fibers Stern  _et al._
(2013); Keil  _et al._ (2016); Kitching (2018), atom-filled hollow-core
fibersBajcsy  _et al._ (2009); Venkataraman  _et al._ (2011, 2013), or optical
traps Meng  _et al._ (2018); Corzo  _et al._ (2019); Johnson  _et al._ (2019))
and nonlinear fibers Matsuda  _et al._ (2009). Here, we focus on Rydberg-EIT
systems to analyze effect of loss on our protocols. We choose this platform
since it enables achieving moderate (and even large) conditional phase shifts
Distante  _et al._ (2017); Tiarks  _et al._ (2019), since linear losses under
EIT conditions can be made negligible Boller  _et al._ (1991), and since the
phase-loss relation in this system is well understood Lahad and Firstenberg
(2017). In such systems, once a photon generates a Rydberg excitation, the
energy levels of the surrounding atoms (within the Rydberg-blockade radius)
are shifted, violating the EIT conditions Gorshkov  _et al._ (2011).
Consequently, any subsequent photon in this volume acquires a phase and
suffers loss.

We model loss as the annihilation of a photon (in $f$ or $g$) and the creation
of a photon in an undetected mode ($\ell$ or $k$). Denoting the absorption
probability by $\tau$, a photon pair in the atomic medium follows the rule:

$\displaystyle{f^{\dagger}}^{2}\rightarrow\sqrt{1-\tau}\,e^{i\varphi}{f^{\dagger}}^{2}+\sqrt{\tau}f^{\dagger}\ell^{\dagger}$
(4a)
$\displaystyle{g^{\dagger}}^{2}\rightarrow\sqrt{1-\tau}\,e^{-i\varphi}{g^{\dagger}}^{2}+\sqrt{\tau}g^{\dagger}k^{\dagger}.$
(4b)

The conditional phase shift $\varphi$ and absorption coefficient
$\varepsilon\equiv-\ln{(1-\tau)}$ follow the phase-loss circle Lahad and
Firstenberg (2017):

$\displaystyle\varphi^{2}+(\tfrac{\varepsilon}{2}-\tfrac{\mathrm{OD}_{\text{b}}}{4})^{2}=(\tfrac{\mathrm{OD}_{\text{b}}}{4})^{2},$
(5)

where $\text{OD}_{\text{b}}$ is the optical depth of the blockade volume – the
core resource of nonlinearity in Rydberg-EIT systems 222There is a factor of 2
difference between our definition of $\varepsilon$ and Lahad and Firstenberg
(2017), since we refer to loss of modal amplitude and Lahad and Firstenberg
(2017) refers to intensity loss.. As evident from Eq. (5) and Fig. 1(d), high
$\text{OD}_{\text{b}}$ enables large conditional phase shifts with low loss.
In particular, $\mathrm{OD}_{\text{b}}>4\pi$ is required for $\varphi=\pi$.
The value $\text{OD}_{\text{b}}=13$ has already been reached experimentally
Tresp  _et al._ (2016), and higher values have been predicted Baur  _et al._
(2014); Gaj  _et al._ (2014). Additionally, high total OD can be utilized to
generate an effective cavity in the atomic medium with finesses
$F\sim(\text{OD}/2)^{0.4}$ Lahad and Firstenberg (2017), leading to a phase-
loss circle whose radius is $F$ times larger, thereby enabling an effective
$\text{OD}_{\text{b}}$ of $100$ or more. Using Eqs. (1, 4, 5), we obtain

${a^{\dagger}}^{2}\rightarrow\tfrac{\sqrt{1-\tau(\varphi)}}{2}\left[\cos\varphi\left({w^{\dagger}}^{2}\\!-{u^{\dagger}}^{2}\right)-2\sin\varphi(w^{\dagger}u^{\dagger})\right]$

$\\!-\tfrac{1}{2}\left({w^{\dagger}}^{2}+{u^{\dagger}}^{2}\right)+\tfrac{\sqrt{\tau(\varphi)}}{2\sqrt{2}}\left[(w^{\dagger}+iu^{\dagger})\ell^{\dagger}-(u^{\dagger}+iw^{\dagger})k^{\dagger}\right]\\!.$

(6)

From Eq. (6), we calculate the probabilities for different outcomes of the MZI
when including loss [Fig. 1(c)].

Equations (5–6) assume that the photon wavelength is tuned exactly on the EIT
resonance, where the single-photon phase shift and loss are ideally zero. In
the supplementary material (SM), we analyze the possibility of detuning from
the EIT resonance to include the effect of single-photon phase shift and loss
in the atomic medium. We find that the performance of our protocols is
relatively unaffected by these processes.

Figure 2: Nonlinear Bell measurement (BM): Two photons are sent through a beam
splitter (BS) and nonlinear routers before reaching polarizing beam splitters
(PBS) followed by detectors (1–8), which measure their joint polarization
state in the Bell basis. While $|\\!\left.{\psi_{\pm}}\right>$ produce
distinct final states, $|\\!\left.{\phi_{\pm}}\right>$ can only be
distinguished with nonlinearity. (b) Success probability of a BM,
$P_{\text{BM}}$, as a function of $\varphi$. Black solid curve neglects loss
[Eq. (8) with $\tau=0$ and $P_{\text{DE}}=1$]. Blue solid curve includes only
nonlinear loss, assuming $\text{OD}_{\text{b}}=30$, while the cyan dashed
(dotted) curve includes also linear loss with $P_{\text{DE}}=98\%$ ($90\%$).
With $P_{\text{DE}}=98\%$ and $\varphi=\pi/3$, $P_{\text{BM}}$ improves from
$0.48$ to $0.67$. (c) Success probability of the nonlinear enhancement of the
Ewert-van Loock protocol Ewert and van Loock (2014), $P_{\text{EVL}}$ [Eq.
(9)] that includes two ancillary qubits. Curves are labeled as in (b). With
$P_{\text{DE}}=98\%$ and $\varphi=\pi/3$, $P_{\text{EVL}}$ improves from
$0.69$ to $0.77$.

Nonlinear Bell-state measurement (BM): As a first application, we use the
nonlinear router to improve linear BMs. We begin this section by revisiting
the traditional linear BM protocol. Then, we present our nonlinear protocol
and discuss its key features in the limit of strong nonlinearity and
negligible loss. Finally, we discuss moderate nonlinearity and non-negligible
loss.

A photonic qubit is defined as a single excitation in an arbitrary coherent
combination of two non-overlapping optical modes. For convenience, here we use
the linear polarization basis, yet our analysis is generally applicable to
other choices of optical modes, including dual-rail and time-bin qubits. In
this basis, the photonic two-qubit Bell states are
$|\\!\left.{\psi_{\pm}}\right>=\tfrac{1}{\sqrt{2}}(a_{H}^{\dagger}b_{V}^{\dagger}\pm
a_{V}^{\dagger}b_{H}^{\dagger})|\\!\left.{\text{vac}}\right>$ and
$|\\!\left.{\phi_{\pm}}\right>=\tfrac{1}{\sqrt{2}}(a_{H}^{\dagger}b_{H}^{\dagger}\pm
a_{V}^{\dagger}b_{V}^{\dagger})|\\!\left.{\text{vac}}\right>$, where
$x_{k}^{\dagger}$ denotes the creation operator of a photon in mode $x$ with
polarization $k$ operating on the vacuum state
$|\\!\left.{\text{vac}}\right>$. In a linear-optics BM, photons are sent
through a balanced beam splitter (BS) Braunstein and Mann (1995). Applying the
BS transformation
$a_{k}^{\dagger}\rightarrow\tfrac{1}{\sqrt{2}}(d_{k}^{\dagger}+ic_{k}^{\dagger})$
and
$b_{k}^{\dagger}\rightarrow\tfrac{1}{\sqrt{2}}(c_{k}^{\dagger}+id_{k}^{\dagger})$,
one finds

$\displaystyle|\\!\left.{\psi_{-}}\right>\xrightarrow[]{\text{BS}}\tfrac{1}{\sqrt{2}}(d_{H}^{\dagger}c_{V}^{\dagger}-c_{H}^{\dagger}d_{V}^{\dagger})|\\!\left.{\text{vac}}\right>,$
(7a)
$\displaystyle|\\!\left.{\psi_{+}}\right>\xrightarrow[]{\text{BS}}\tfrac{i}{\sqrt{2}}(d_{H}^{\dagger}d_{V}^{\dagger}+c_{H}^{\dagger}c_{V}^{\dagger})|\\!\left.{\text{vac}}\right>,$
(7b)

$|\\!\left.{\phi_{\pm}}\right>\xrightarrow[]{\text{BS}}\tfrac{i}{2\sqrt{2}}[(d_{H}^{\dagger})^{2}+(c_{H}^{\dagger})^{2}\pm((d_{V}^{\dagger})^{2}+(c_{V}^{\dagger})^{2})]|\\!\left.{\text{vac}}\right>.$

(7c)

The states $|\\!\left.{\psi_{\pm}}\right>$ lead to distinguishable outcomes.
While $|\\!\left.{\psi_{-}}\right>$ produces one photon in $c_{k}$ and one in
$d_{k}$, the state $|\\!\left.{\psi_{+}}\right>$ produces an orthogonal pair
in either $c_{k}$ or $d_{k}$. In contrast, the states
$|\\!\left.{\phi_{\pm}}\right>$ produce a “bunched” pair in one of the four
detectors and are, therefore, indistinguishable. Hence, when detectors are
placed at the exit of the BS, the success probability of the BM is $50\%$
Braunstein and Mann (1995).

By adding nonlinearity, one can improve the success probability of the BM. To
this end, we place nonlinear routers that help distinguish between
$|\\!\left.{\phi_{\pm}}\right>$ at the output of the BS [red boxes in Fig.
2(a)]. When existing the routers, the photon pass through polarizing beam
splitters (PBSs), which transmit horizontal and reflect vertical polarization,
before hitting single-photon detectors (labeled as 1-8). When the acquired
conditional phase shift in the MZIs is $\varphi=\pi$ and when neglecting loss,
all four Bell states are distinguishable by this setup. That is, each input
Bell state produces a unique set of detection clicks. For example, only the
state $|\\!\left.{\psi_{+}}\right>$ can produce clicks in $3\,\&\,4$ or
$5\,\&\,6$ (see SM) 333 This calculation assumes that the nonlinearity is
implemented using self-phase modulation, which takes place when two photons of
the same polarization travel along the same arm of the MZI. The latter is
experimentally achievable in existing Rydberg-EIT platforms Firstenberg  _et
al._ (2013); Tiarks  _et al._ (2019)..

Next, we consider the effect of photon loss on our scheme, caused either by
the nonlinear medium (NL loss) or by the detectors. In the SM, we compute the
success probability in the presence of loss and obtain

$\displaystyle
P_{\mathrm{BM}}=P_{\text{DE}}^{2}\left[1-\tfrac{1}{8}\left(\sqrt{1-\tau(\varphi)}\cos\varphi+1\right)^{2}-\tfrac{\tau(\varphi)}{4}\right],$
(8)

where $P_{\text{DE}}$ denotes the single-photon detection efficiency. The
formula is evaluated in Fig. 2(b). Our scheme assumes multiple detectors or
photon-number resolving detectors are used Divochiy  _et al._ (2008); Dauler
_et al._ (2009); Sahin  _et al._ (2013); Endo  _et al._ (2021) to distinguish
between instances with two photons in the same detector from instances with a
single detection due to a loss event. Assuming moderate conditional phase
shift of $\varphi=\pi/3$ (achievable using available setups Liu  _et al._
(2016)) and $P_{\text{DE}}=98\%$ improves the $P_{\text{BM}}$ from 0.48 to
0.67. Evidently, in the presence of loss, the optimal operating point is at an
intermediate phase $\varphi_{\text{opt}}<\pi$, which tends to $\pi$ upon
increasing $\text{OD}_{\text{b}}$, scaling as
$\pi-\varphi_{\text{opt}}\propto\text{OD}_{\text{b}}^{-1}$ at large
$\text{OD}_{\text{b}}$ values (Fig. D1 in the SM).

Figure 2(c) shows our nonlinear modification of the linear Ewert-van Loock
protocol, that attains higher success probabilities at the cost of using two
ancillary qubits Ewert and van Loock (2014); Grice (2011). As shown in the SM,
the success probability of the protocol is

$\displaystyle
P_{\mathrm{EVL}}=P_{\text{DE}}^{4}\left[1-\tfrac{1}{16}\left(\sqrt{1-\tau(\varphi)}\cos\varphi+1\right)^{2}-\tfrac{\tau(\varphi)}{4}\right].$
(9)

Assuming $\pi/3$ and $P_{\text{DE}}=98\%$, the success probability
$P_{\text{EVL}}$ improves from 0.69 to 0.77.

Figure 3: Nonlinear GHZ state generation: (a) Two Bell pairs are prepared, and
one photon from each pair is sent through PBS1. Two scenarios can produce a
GHZ state: 1\. When photons leave PBS1 through different ports and exit the
routers in ports $u$ and $p$. 2\. When photons leave PBS1 through the same
port and also exit the routers in $w$ or $q$. When none of the photons are
lost, zero or two clicks in detectors 1–4 or a click in 5 herald failure. The
switch selects one of the output modes, $g$ or $p$, that together with modes
$r$ and $s$ contain a three-photon GHZ state when our protocol succeeds;
during its operation, photons travel in delay lines (coils). (b) Success
probability, $P_{\text{GHZ}}$, as function of $\varphi$. Black solid curve
neglects loss [Eq. (10) with $\tau=0$ and $P_{\text{DE}}=1$]. Blue solid curve
includes only nonlinear loss, assuming $\text{OD}_{\text{b}}=30$, while cyan
dashed (dotted) curve includes also detector loss with $P_{\text{DE}}=98\%$
($90\%$). With $P_{\text{DE}}=98\%$ and $\varphi=\pi/3$, $P_{\text{GHZ}}$
improves from $0.49$ to $0.52$.

Nonlinear GHZ-state preparation: Our protocol is shown in Fig. 3(a). We
discuss its key features here and provide the derivation details in the SM.
Initially, two Bell states are prepared in
$|\\!\left.{\phi_{+}}\right>\\!|\\!\left.{\phi_{+}}\right>$ and one photon
from each Bell pair is sent through a polarizing beam splitter (PBS1). Then,
the photons enter nonlinear routers. The photons may either leave PBS1 from
different ports ($c_{H}^{\dagger}d_{H}^{\dagger}$ and
$c_{V}^{\dagger}d_{V}^{\dagger}$) or through the same port
($c_{H}^{\dagger}c_{V}^{\dagger}$ and $d_{H}^{\dagger}d_{V}^{\dagger}$). In
the former case, the photons leave the routers in modes $u$ and $p$. Then, the
photon in $u$ undergoes a $45^{\circ}$ rotation and a subsequent measurement
of the rotated photon in the diagonal basis projects the surviving photons
onto a GHZ state. This process is called “fusion type I” Browne and Rudolph
(2005).

Our nonlinear scheme aims to “save” also photons that leave PBS1 through the
same port. To this end, we use nonlinear routers that have the property that
when $\varphi=\pi$, photons from $c_{H}^{\dagger}c_{V}^{\dagger}$ and
$d_{H}^{\dagger}d_{V}^{\dagger}$ are routed into modes
$w_{H}^{\dagger}w_{V}^{\dagger}$ and $q_{H}^{\dagger}q_{V}^{\dagger}$. By
sending these photons to PBS2, rotating the photon in mode $f$, and measuring
the rotated photon in the diagonal basis, a GHZ state is produced. By adding
the probabilities for successful GHZ-state generation, either by “fusion type
I” or by successful nonlinear routing, we obtain (see SM)

$P_{\mathrm{GHZ}}=P_{\text{DE}}\left[\frac{1}{2}+\tfrac{1}{8}\left(\sqrt{1-\tau(\varphi)}\cos\varphi-1\right)^{2}\right].$
(10)

$P_{\mathrm{GHZ}}$ as a function of $\varphi$ is shown in Fig. 3(b). The
optimal operating point is attained at $\varphi_{\text{opt}}<\pi$ and scales
as $\pi-\varphi_{\text{opt}}\propto\text{OD}_{\text{b}}^{-1/3}$ with
increasing $\text{OD}_{\text{b}}$ (Fig. D1). With $P_{\text{DE}}=98\%$ and
$\varphi=\tfrac{\pi}{3}$, $P_{\text{GHZ}}$ improves from 0.49 to 0.52.

Figure 4: Nonlinear CNOT and quantum factorization: (a) The Gottesman-Chuang
linear CNOT gate Gottesman and Chuang (1999). The gate requires three BMs, two
GHZ states and single-qubit Pauli ($X,Z$) and Hadamard ($H$) rotations. (b)
Success probability (log scale) of the CNOT gate, using our nonlinear protocol
(with BMs and GHZs from Figs. 2-3). Black solid curve neglects loss [Eq. (10)
with $\tau=0$ and $P_{\text{DE}}=1$]. Blue solid curve includes only nonlinear
loss, assuming $\text{OD}_{\text{b}}=30$, while cyan dashed (dotted) curve
includes also detector loss with $P_{\text{DE}}=98\%$ ($90\%$). (c) Success
probability (log scale) of quantum factorization of the number 15, using a
protocol that requires two CNOT gates Politi  _et al._ (2009), with the same
building blocks and curve labels as in (b). For $\varphi=\pi/3$ and
$P_{\text{DE}}=98\%$, the success probabilities of CNOT and quantum
factorization increase by factors of 3.32 and 11 respectively.

Our protocol accepts four input photons and (when successfully operated)
produces three output photons in a GHZ state. The goal of the switch is to
select the modes that contain the GHZ state in order to prepare the input for
a quantum computation protocol or for a subsequent stage in a cluster-state-
generation protocol. Specifically, the switch selects to output mode $g$ and
measure $p$ if there was a click in detectors 3 or 4, and vice versa if a
click occurred in detectors 1 or 2. During the switch operation, the photons
travel in delay lines. Success of this scheme is heralded only if exactly one
photon is detected - by detectors 1-4. Failure is heralded by detection of two
photons in detectors 1-5 (indicating that the output is empty), or by the lack
of any detection events in detectors 1-4 (whether cause by imperfect routing,
detection inefficiency or loss). All these cases are accordingly disregarded.
If two photons are routed to detectors 1-5 but only one is detected due to
loss (e.g. in the delay lines or the switch) or imperfect detection
efficiency, this leads to a ”false positive” indication of success. However,
the result in this case is again the lack of photon at the output channel, and
therefore is equivalent to any other loss event, and is accordingly tolerated
as long as the overall loss is below the required threshold.

CNOT and Factorization: In Gottesman and Chuang (1999), Gottesman and Chuang
(GC) present an optical-circuit implementation of the CNOT gate, which
requires two GHZ states and three BMs [Fig. 4(a)]. Accordingly, the success
probability of this protocol scales like
$(P_{\text{GHZ}})^{2}\times(P_{\text{BM}})^{3}$, being $1/2^{5}$ in the
linear-optics case. When using our nonlinear elements, the success probability
for $\varphi=\pi/3$ becomes $0.72^{3}*0.53^{2}=0.105$, which is 3.32 larger
than $1/2^{5}$, as shown in Fig. 4(c) 444Since finite detection efficiency
limits our protocols in the same manner as the linear protocols, it does not
affect the improvement factor and, hence, not included in the presented
equation.. As CNOT is an elementary building block in most quantum protocols,
this enhancement is a dramatic result. For example, the algorithm for quantum
factorization of the number 15 from Politi  _et al._ (2009) requires two CNOT
gates. Accordingly, our nonlinear protocols lead to an order-of-magnitude
(11-fold) improvement in its success probability at $\varphi=\pi/3$ [Fig.
4(d)].

Discussion: We examined photonic quantum computation protocols in the
intermediate regime between linear optics and strong nonlinearity at the
single photon level, and presented efficient protocols for key elementary
operations, including BM, GHZ-state generation, CNOT gate, and quantum
factorization. Our results demonstrate the potential of moderate nonlinearity,
which is achievable in a variety of platforms, using Rydberg-EIT systems
Firstenberg  _et al._ (2013); Tiarks  _et al._ (2019) as a relevant example.
As photonic quantum computation, and fault-tolerant MBQC in particular,
require a large number of elementary operations Li  _et al._ (2015), any
modest increase in the success probability of each operation is translated to
a dramatic reduction in the required resources. For example, a conditional
phase shift of $\varphi=\pi/3$, which in our scheme increases the success
probability of ancilla-assisted BM with detection efficiency of 98% from
$0.69$ to $0.77$, and of GHZ-state preparation from $0.49$ to $0.52$, can be
translated into two orders of magnitude reduction in resources after $35$
operations. With the recent developments in interacting atomic ensembles with
integrated photonics Stern  _et al._ (2013); Keil  _et al._ (2016); Kitching
(2018); Meng  _et al._ (2018); Corzo  _et al._ (2019); Johnson  _et al._
(2019); Finkelstein  _et al._ (2020); Pang  _et al._ (2020), few-photon
nonlinearty on chip-scale devices is becoming feasible, making protocols that
rely on moderate nonlinearities a promising new platform for photonic quantum
information processing.

Acknowledgment. The authors thank Ephraim Shahmoon, Serge Rosenblum, and Ran
Finkelstein for helpful discussions. AP acknowledges support of the Koshland
Foundation. BD and OF acknowledge support from the Israeli Science Foundation.
ESK, BD, and JPD are also supported by Binational Science Foundation. ESM and
JPD acknowledge the support by the U.S. Air Force Office Scientific Research,
and also by the U.S. Army Research Office with the grant W911NF- 17-1-0541. BD
is also supported by the Minerva Foundation, IMOD (OR RISHON), and a research
grant from Dr. Saul Unter. OF is also supported by the European Research
Council starting investigator grant QPHOTONICS 678674.

## Supplementary Material

## Table of contents

A. Nonlinear Bell measurement
A1. Protocol without ancillas.
A2. Protocol with ancillas.
B. Nonlinear GHZ-state preparation.
C. Introducing single-photon phase shifts
C1. Nonlinear router
C2. Nonlinear Bell measurement.
C3. Nonlinear GHZ-state generation.
D. Selecting optimal phase shifts.

##  A Nonlinear Bell measurement

###  A.1 Protocol without ancillas

Figure A.1: For convenience, we present Fig. 2(a) from the main text,
introducing labeling of the modes inside the interferometer (modes $f$, $g$,
$u$ and $w$).

In this section, we provide calculation details for the success probability of
a nonlinear Bell measurement [Eq. (8) in the main text]. For convenience, we
present Fig. 2(a) from the main text in Fig. A.1, and introduce additional
labeling of the modes involved in the protocol. First, we rewrite Eq. (7) in
the diagonal basis

$|\\!\left.{\psi_{+}}\right>\xrightarrow[]{\text{BS}}\tfrac{i}{2\sqrt{2}}[(c_{+}^{\dagger})^{2}-(c_{-}^{\dagger})^{2}+(d_{+}^{\dagger})^{2}-(d_{-}^{\dagger})^{2}]|\\!\left.{\text{vac}}\right>$

$|\\!\left.{\phi_{+}}\right>\xrightarrow[]{\text{BS}}\tfrac{i}{2\sqrt{2}}[(c_{+}^{\dagger})^{2}+(c_{-}^{\dagger})^{2}+(d_{+}^{\dagger})^{2}+(d_{-}^{\dagger})^{2}]|\\!\left.{\text{vac}}\right>$

$\displaystyle\scalebox{0.9}{$|\\!\left.{\phi_{-}}\right>\xrightarrow[]{\text{BS}}\tfrac{i}{\sqrt{2}}[c_{+}^{\dagger}c_{-}^{\dagger}+d_{+}^{\dagger}d_{-}^{\dagger}]|\\!\left.{\text{vac}}\right>$}.$
(A.1)

To trace the evolution upon entering and leaving the MZI, we invoke the beam-
splitter (BS) transformation

$\displaystyle
c^{\dagger}\rightarrow\tfrac{1}{\sqrt{2}}(f^{\dagger}+ig^{\dagger})$
$\displaystyle
f^{\dagger}\rightarrow\tfrac{1}{\sqrt{2}}(w^{\dagger}+iu^{\dagger})$
$\displaystyle
g^{\dagger}\rightarrow\tfrac{1}{\sqrt{2}}(u^{\dagger}+iw^{\dagger}).$ (A.2)

Due to self-phase modulation in the atomic medium, an identical photon pair
that enters modes $f$ or $g$ undergoes the transformation

$\displaystyle(f_{\pm}^{\dagger})^{2}\rightarrow\sqrt{1-\tau}\,e^{i\varphi}(f_{\pm}^{\dagger})^{2}+\sqrt{\tau}f_{\pm}^{\dagger}\ell_{\pm}^{\dagger}$
(A.3)
$\displaystyle(g_{\pm}^{\dagger})^{2}\rightarrow\sqrt{1-\tau}\,e^{i\varphi}(g_{\pm}^{\dagger})^{2}+\sqrt{\tau}g_{\pm}^{\dagger}k_{\pm}^{\dagger},$
(A.4)

where the first term on the right hand side accounts for phase acquisition and
the second for loss. By using Eqs. (A.1–A.4), we find

$(c_{\pm}^{\dagger})^{2}\rightarrow\tfrac{\sqrt{1-\tau}\cos\varphi-1}{2}(w_{\pm}^{\dagger})^{2}-\tfrac{\sqrt{1-\tau}\cos\varphi+1}{2}(u_{\pm}^{\dagger})^{2}-$

$\sqrt{1-\tau}\sin\varphi\,w_{\pm}^{\dagger}u_{\pm}^{\dagger}+\tfrac{\sqrt{\tau}}{2\sqrt{2}}\left[(w_{\pm}^{\dagger}+iu_{\pm}^{\dagger})l_{\pm}^{\dagger}-(u_{\pm}^{\dagger}+iw_{\pm}^{\dagger})k_{\pm}^{\dagger}\right],$

(A.5)

generalizing Eq. (6) in the main text. A similar transformation rule applies
for the $d_{+}d_{-}$ component of the wavefunction.

Both the states $|\\!\left.{\phi_{+}}\right>$ and
$|\\!\left.{\psi_{+}}\right>$ are affected by the nonlinearity, since both
contain identical photon pairs [see Eq. (A.1)]. However, whenever two photons
are detected, $|\\!\left.{\phi_{+}}\right>$ is distinguishable from the
remaining states because it is the only state that produces a pair of
orthogonal photons either in the upper detectors (1–4) or in the lower
detectors (5–8). Therefore, when both photons reach the detectors, only the
cases where both photons from $|\\!\left.{\psi_{+}}\right>$ are routed into
$u_{+}^{\dagger}u_{-}^{\dagger}$ lead to failure. Therefore, the failure
probability is found by collecting the terms proportional to
$u_{+}^{\dagger}u_{-}^{\dagger}$. Photon loss also leads to failure of the BM.
Both $|\\!\left.{\phi_{+}}\right>$ and $|\\!\left.{\psi_{+}}\right>$ can
experience loss, and the final states in that case are indistinguishable.
Given that the initial state is $|\\!\left.{\psi_{+}}\right>$ or
$|\\!\left.{\phi_{+}}\right>$, the probability for loss is $\tau/2$.
Therefore, the overall success probability becomes

$\displaystyle
P_{\mathrm{BM}}=P_{\text{DE}}^{2}\left[1-\tfrac{1}{8}\left(\sqrt{1-\tau(\varphi)}\cos\varphi+1\right)^{2}-\tfrac{\tau(\varphi)}{4}\right],$
(A.6)

where the last term corresponds to nonlinear-loss events and $P_{\text{DE}}$
accounts for finite detection efficiency.

###  A.2 Protocols with ancillas

In the main text, we present a Bell measurement (BM) that uses conditional
phase shifts to improve a linear method whose success probability is $50\%$.
However, linear protocols that use ancillary photons may have higher success
rates, with probability approaching $100\%$; the failure rate drops
exponentially with the number of ancillary photons Grice (2011). Fig. 2(c)
depicts the success rate of a refined nonlinear protocol, which is based on a
linear method with two ancillary qubits and success probability of $75\%$
Ewert and van Loock (2014). The linear protocol and its nonlinear improvement
are shown in Fig. A.2(a) and (b) respectively.

Figure A.2: (a) Bell-state measurement using four ancillary qubits prepared in
$\tfrac{1}{2}[{(a^{\dagger}_{H})^{2}+(a^{\dagger}_{V})^{2}}]|\\!\left.{\text{vac}}\right>$.
A Bell state is sent through the device, and the final measurement can
determine the input state with success probability of $75\%$. (b) By
introducing nonlinear routers (and additional ancillas and detectors), the
success probability increases, and reaches $100\%$ for $\pi$ conditional phase
shifts, as shown by the green line in Fig. 2(b) in the main text.

The linear method, proposed independently by Grice and Ewert and van-Loock
Grice (2011); Ewert and van Loock (2014), utilizes additional photons prepared
in
$|\\!\left.{A_{i}}\right>=\tfrac{1}{2}[{(a^{\dagger}_{i,H})^{2}+(a^{\dagger}_{i,V})^{2}}]|\\!\left.{\text{vac}}\right>,$
where the index $i=1,2$ enumerates the ancillas and
$|\\!\left.{\text{vac}}\right>$ is the vacuum of the acillary modes. The
protocol is shown inFig. A.2(a). we briefly revise the linear method before
introducing our nonlinear modification. By using 8 detectors, the Bell state
can be determined with success probability of $75\%$. The states $\psi_{\pm}$
and $\phi_{\pm}$ differ in the parity of $H$ and $V$ polarized photons, since
the parity is unaltered by the device. The states $\psi_{\pm}$ can be
distinguished since they differ in the number of photons that reach the upper
detectors ($D1,\ldots,D4$). Finally, the states $\phi_{\pm}$ can only be
distinguished with probability $50\%$ (instances where all detected photons
have the same polarization can occur for both $\phi_{+}$ and $\phi_{-}$ and
lead to failure).

By introducing two nonlinear routers, one in each output of the first beam
splitter, we increase the probability to distinguish between the $\phi_{\pm}$
states. The setup is shown in Fig. A.2(b). The success probability of our
nonlinear protocol (when neglecting loss) is

$\displaystyle
P_{\mathrm{EVL}}=P_{\text{DE}}^{4}\left[1-\tfrac{1}{16}\left(\sqrt{1-\tau(\varphi)}\cos\varphi+1\right)^{2}-\tfrac{\tau(\varphi)}{4}\right].$
(A.7)

With a conditional phase shift of $\pi$, the BM becomes deterministic. Note,
however, that the nonlinear setup requires four ancillary qubits and eight
detectors (while the linear counterpart required only two ancilla qubits).

##  B Nonlinear GHZ-state preparation

Figure B.1: To fascillitate the reading of the derivation, we present Fig.
3(a) from the main text also here.

In the main text, we describe a nonlinear protocol for GHZ-state generation.
In this section, we provide the details of the derivation. For the the
notation we refer to Fig. B.1. The protocol uses a resource of two Bell pairs,

$\displaystyle|\\!\left.{\psi}\right>=\tfrac{1}{2}(r_{H}^{\dagger}a_{H}^{\dagger}+r_{V}^{\dagger}a_{V}^{\dagger})(s_{H}^{\dagger}b_{H}^{\dagger}+s_{V}^{\dagger}b_{V}^{\dagger})|\\!\left.{\text{vac}}\right>.$
(B.1)

Then, one photon from each pair is sent through a polarizing beam splitter
(PBS) (which transmits $H$-polarized photons and reflects $V$ photons) and the
state becomes

$\displaystyle|\\!\left.{\psi}\right>\xrightarrow[]{\text{PBS1}}\tfrac{1}{2}(r_{H}^{\dagger}d_{H}^{\dagger}+ir_{V}^{\dagger}c_{V}^{\dagger})(s_{H}^{\dagger}c_{H}^{\dagger}+is_{V}^{\dagger}d_{V}^{\dagger})|\\!\left.{\text{vac}}\right>.$
(B.2)

This wavefunction contains two types of components: ones with single photons
in each output arm of the PBS ($c_{H}^{\dagger}d_{H}^{\dagger}$ and
$c_{V}^{\dagger}d_{V}^{\dagger}$) and others with both photons in the same arm
($c_{H}^{\dagger}c_{V}^{\dagger}$ and $d_{H}^{\dagger}d_{V}^{\dagger}$). The
former type of terms lead to successful GHZ-state generation. For these
states, our protocol reproduces the linear protocol “fission I.” For these
terms, the photons leave the routers through ports $u$ or $p$. Then, the
photon in $u$ undergoes a $45^{\circ}$ rotation, resulting in

$\tfrac{1}{2}(r_{H}^{\dagger}s_{H}^{\dagger}c_{H}^{\dagger}d_{H}^{\dagger}-r_{V}^{\dagger}s_{V}^{\dagger}c_{V}^{\dagger}d_{V}^{\dagger})\xrightarrow[]{\text{MZI}}\tfrac{1}{2}(r_{H}^{\dagger}s_{H}^{\dagger}p_{H}^{\dagger}u_{H}^{\dagger}-r_{V}^{\dagger}s_{V}^{\dagger}p_{V}^{\dagger}u_{V}^{\dagger})$

$\xrightarrow[]{45^{\circ}}\tfrac{1}{2\sqrt{2}}[u_{+}^{\dagger}(r_{H}^{\dagger}s_{H}^{\dagger}p_{H}^{\dagger}-r_{V}^{\dagger}s_{V}^{\dagger}p_{V}^{\dagger})+u_{-}^{\dagger}(r_{H}^{\dagger}s_{H}^{\dagger}p_{H}^{\dagger}+r_{V}^{\dagger}s_{V}^{\dagger}p_{V}^{\dagger})].$

(B.3)

Therefore, a click in either $u_{+}$ or $u_{-}$ projects the surviving photons
onto a GHZ state.

On the other hand, our protocol can save also the latter type of terms. The
wavefunction components with both photons in the same arm (containing
$c_{H}^{\dagger}c_{V}^{\dagger}$ and $d_{H}^{\dagger}d_{V}^{\dagger}$) are
routed into modes $u,p$ or $w,q$ with probabilities shown in Fig. 1(c). For
these terms, the cases where both photons are also routed into $w$ or $q$ lead
to successful GHZ generation. This is because the latter transform as

$\tfrac{1}{2}(r_{V}^{\dagger}s_{H}^{\dagger}w_{H}^{\dagger}w_{V}^{\dagger}+r_{H}^{\dagger}s_{V}^{\dagger}q_{H}^{\dagger}q_{V}^{\dagger})\xrightarrow[]{\text{PBS2}}\tfrac{i}{2}(r_{V}^{\dagger}s_{H}^{\dagger}g_{H}^{\dagger}f_{V}^{\dagger}+r_{H}^{\dagger}s_{V}^{\dagger}f_{H}^{\dagger}g_{V}^{\dagger})$

$\displaystyle\scalebox{0.9}{$\xrightarrow[]{45^{\circ}}\tfrac{i}{2\sqrt{2}}[f_{+}^{\dagger}(r_{V}^{\dagger}s_{H}^{\dagger}g_{H}^{\dagger}+r_{H}^{\dagger}s_{V}^{\dagger}g_{V}^{\dagger})+f_{-}^{\dagger}(r_{V}^{\dagger}s_{H}^{\dagger}g_{H}^{\dagger}-r_{H}^{\dagger}s_{V}^{\dagger}g_{V}^{\dagger})]$}.$
(B.4)

By scrutinizing the terms in the second line of Eq. (B.4), one can see that a
measurement of the photon in mode $f$ in the diagonal basis projects the
surviving photons onto a GHZ state.

##  C  Introducing single-photon phase shifts

Figure C.1: Adding a single-photon phase shift, $\mathbf{\varphi_{1}}$, to
reduce the nonlinear loss: (a) Conditional phase-loss relation in Rydberg EIT
systems, using Eq. (C.13). Same as Fig. 1(c), with the addition of the case
$\varphi_{1}=-0.5,\mathrm{OD}_{\mathrm{b}}=3.5$ (brown-dashed curve). (b)
Nonlinear router: Probabilities for detection outcomes, $P_{\text{output}}$,
for an incoming photon pair. Same as in Fig. 1(b), with the addition of the
case $\varphi_{1}=-\tfrac{\varphi}{11}$, evaluated using Eq. (C.11) (dotted
curves here and in all of the following subplots in this figure). This value
of $\varphi_{1}$ is chosen to optimize the success probability and is used in
all remaining subplots. (c–f) Success probabilities of a nonlinear BM
($P_{\text{BM}}$), GHZ-states generation ($P_{\text{GHZ}}$), CNOT gate
($P_{\text{CNOT}}$), and quantum factorization ($P_{\text{factorization}}$) as
a function of $\varphi$. Same as Figs. 2(c), 3(b), 4(b,c), with the addition
of the case $\varphi_{1}<0$.

###  C.1 Nonlinear router

In this appendix, we introduce single-photon phase shifts in order to achieve
conditional (two-photon) phase shifts with reduced nonlinear loss. In the
applications that we study in this paper, we find that this trade-off between
single-photon phase shifts and loss leads to a minor improvement in the
performance. The results of our analysis are shown in Fig. C.1.

In order to reduce the nonlinear loss, we choose photon frequencies that are
detuned from the EIT resonance, such that a photon traveling through the
medium acquires a phase shift $\varphi_{1}$ and experiences loss, described by
the absorption coefficient $\varepsilon_{1}$. Once a photon generates a
Rydberg excitation, a subsequent photon inside the blockade radius effectively
experiences an ensemble of two-level atoms and acquires a phase shift
$\varphi_{2}$ and loss with absorption coefficient $\varepsilon_{2}$. When
neglecting loss, this model produces the following transformation rules for
the creation operators in the MZI [Fig. 1(a) in the main text]:

$\displaystyle f^{\dagger}\rightarrow
e^{i\varphi_{1}}f^{\dagger}\quad,\quad{f^{\dagger}}^{2}\rightarrow
e^{i(\varphi_{1}+\varphi_{2})}{f^{\dagger}}^{2}$ (C.1) $\displaystyle
g^{\dagger}\rightarrow
e^{-i\varphi_{1}}g^{\dagger}\quad,\quad{g^{\dagger}}^{2}\rightarrow
e^{-i(\varphi_{1}+\varphi_{2})}{g^{\dagger}}^{2}.$ (C.2)

Our motivation is that by introducing small negative $\varphi_{1}$, one needs
a smaller $\varphi_{2}$ to achieve the same conditional phase shift,

$\displaystyle\varphi\equiv\varphi_{2}-\varphi_{1}.$ (C.3)

Since the phase shifts and loss coefficients satisfy the circle relations [Eq.
(C.12) below], we expect to reduce the total loss

$\displaystyle\varepsilon\equiv\varepsilon_{1}+\varepsilon_{2}.$ (C.4)

Once introducing $\varphi_{1}\neq 0$, one must balance the MZI (by adding a
linear phase shift to one of its arm) in order for single photons to exit
deterministically through one port. Revisiting Eq. (1) from the main text and
introducing single-photon phase shifts, $e^{\pm\varphi_{1}}$, and an
additional phase shift of $e^{i\Delta}$ for mode $f$, we obtain

$\displaystyle
a^{\dagger}\xrightarrow[]{\text{BS1}}\tfrac{1}{\sqrt{2}}(e^{i(\varphi_{1}+\Delta)}f^{\dagger}+ie^{-i\varphi_{1}}g^{\dagger})\xrightarrow[]{\Delta=-2\varphi_{1}}$
$\displaystyle\tfrac{e^{-i\varphi_{1}}}{\sqrt{2}}(f^{\dagger}+ig^{\dagger})\xrightarrow[]{\text{BS2}}e^{-i\varphi_{1}}u^{\dagger}.$
(C.5)

With this choice of $\Delta$, the MZI is balanced. Next, let us trace the
propagation of a photon pair in the MZI. Revisiting Eq. (3), we find

$\left(a^{\dagger}\right)^{2}\\!\\!\xrightarrow[]{\text{BS1}}\\!\tfrac{1}{2}\left(e^{i\tfrac{\varphi_{1}+\varphi_{2}+\Delta}{2}}f^{\dagger}+ie^{-i\tfrac{\varphi_{1}+\varphi_{2}}{2}}g^{\dagger}\right)^{2}\xrightarrow[]{\Delta=-2\varphi_{1}}$

$\displaystyle\scalebox{0.9}{$\tfrac{e^{-2i\varphi_{1}}}{2}\left(e^{i\tfrac{\varphi}{2}}f^{\dagger}+ie^{-i\tfrac{\varphi}{2}}g^{\dagger}\right)^{2}\xrightarrow[]{\text{BS2}}e^{-2i\varphi_{1}}\left(w^{\dagger}\sin\tfrac{\varphi}{2}+u^{\dagger}\cos\tfrac{\varphi}{2}\right)^{2}$}.$
(C.6)

In the second line, we used the definition of $\varphi$ [Eq. (C.3)].

Next, we account for the effect of loss on the probability amplitude of the
surviving terms. For brevity, we do not keep track of the loss channels and
denote them symbolically by the word “loss” in Eqs. (C7-11) below. The
transformation rule [Eq. (C.2)] is modified:

$\displaystyle
f^{\dagger}\rightarrow\sqrt{1-\tau_{1}}e^{i\varphi_{1}}f^{\dagger}+\text{loss},$
(C.7) $\displaystyle
g^{\dagger}\rightarrow\sqrt{1-\tau_{1}}e^{-i\varphi_{1}}g^{\dagger}+\text{loss},$
(C.8)
$\displaystyle{f^{\dagger}}^{2}\rightarrow\sqrt{(1-\tau_{1})(1-\tau_{2})}e^{i(\varphi_{1}+\varphi_{2})}{f^{\dagger}}^{2}+\text{loss},$
(C.9)
$\displaystyle{g^{\dagger}}^{2}\rightarrow\sqrt{(1-\tau_{1})(1-\tau_{2})}e^{-i(\varphi_{1}+\varphi_{2})}{g^{\dagger}}^{2}+\text{loss}.$
(C.10)

Tracing the propagation of photon pairs through the MZI, we find [generalizing
Eq. (5) in the main text]

${a^{\dagger}}^{2}\rightarrow\tfrac{\sqrt{(1-\tau_{1})(1-\tau_{2})}}{2}e^{-2i\varphi_{1}}\left[\cos\varphi\left({w^{\dagger}}^{2}\\!-{u^{\dagger}}^{2}\right)-2\sin\varphi(w^{\dagger}u^{\dagger})\right]$

$\displaystyle\scalebox{0.9}{$\\!-\tfrac{(1-\tau_{1})}{2}e^{-2i\varphi_{1}}\left({w^{\dagger}}^{2}+{u^{\dagger}}^{2}\right)+\text{loss}$}.$
(C.11)

The acquired phase shifts and loss coefficients satisfy the circle relation:

$\displaystyle\varphi_{i}^{2}+\left(\tfrac{\text{OD}}{4}-\tfrac{\varepsilon_{i}}{2}\right)^{2}=\left(\tfrac{\text{OD}}{4}\right)^{2},$
(C.12)

for $i=1,2$, where $e^{-\varepsilon_{i}}=1-\tau_{i}$.

Equation (C.11) is used in Fig. 1(a) in the main text to compute the
probability for a photon pair to exit in modes $w,u$ or both when
$\varphi_{1}\neq 0$ (dotted curves). The probabilities can be expressed in
terms of $\varphi_{1},\varphi,\varepsilon_{1},$ and $\varepsilon$. We choose
$\varphi_{1}$ and $\varphi$ and express $\varepsilon_{1}(\varphi_{1})$ using
Eq. (C.12) and the overall loss, using

$\displaystyle\varepsilon(\varphi,\varphi_{1})=\varepsilon_{1}(\varphi_{1})+\tfrac{\text{OD}}{2}\pm\sqrt{\left(\tfrac{\text{OD}}{2}\right)^{2}-4(\varphi+\varphi_{1})^{2}}.$
(C.13)

###  C.2 Nonlinear Bell measurement

Introducing conditional phase shifts for identical photon pairs, the
transformation rule for creation operators becomes

$\displaystyle{f_{\pm}^{\dagger}}^{2}\rightarrow\sqrt{(1-\tau_{1})(1-\tau_{2})}e^{i(\varphi_{1}+\varphi_{2})}{f_{\pm}^{\dagger}}^{2}+\text{loss},$
(C.14) $\displaystyle
f_{+}^{\dagger}f_{-}^{\dagger}\rightarrow(1-\tau_{1})e^{2i\varphi_{1}}f_{+}^{\dagger}f_{-}^{\dagger}+\text{loss}.$
(C.15)

Recall that the states $|\\!\left.{\psi_{-}}\right>$ and
$|\\!\left.{\phi_{-}}\right>$ do not contain identical photon pairs in the
diagonal basis after the first BS [see Eq. (A.1)]. Therefore, these states can
only encounter single-photon loss and the survival probability for each of
these states is $(1-\tau_{1})^{2}$. Conversely, the states
$|\\!\left.{\psi_{+}}\right>$ and $|\\!\left.{\phi_{+}}\right>$ contain
identical photon pairs. By summing the probability of the no-loss terms in Eq.
(C.11), one finds that the survival probability for each of these states is
$\frac{1}{2}[(1-\tau_{1})^{2}+(1-\tau_{1})(1-\tau_{2})]$. The interpretation
of the last result is that either the photons survive two single-photon loss
events (in an EIT medium) or they survive a single photon and a second-photon
loss (in an effective two-level medium) event. The overall survival
probability is

$\displaystyle
P_{\mathrm{survive}}=\tfrac{(1-\tau_{1})^{2}}{2}+\tfrac{(1-\tau_{1})(2-\tau_{1}-\tau_{2})}{4}.$
(C.16)

Therefore, the success probability of a BM is

$\displaystyle\scalebox{0.9}{$P_{\mathrm{BM}}=P_{\mathrm{survive}}-\tfrac{1}{8}\left(\sqrt{(1-\tau_{1})(1-\tau_{2})}\cos\varphi+(1-\tau_{1})\right)^{2}$}.$
(C.17)

To account for finite detection efficiency, one needs to multiply this result
by $P_{\text{DE}}^{2}$.

###  C.3 Nonlinear GHZ-state generation

To compute the success probability of our protocol in the presence of
$\varphi_{1}\neq 0$, recall that there are two scenarios that produce a GHZ
state: (i) When the photon pair leaves PBS1 through different ports and both
photons reach the final detectors (avoiding absorption due to linear loss in
the MZI), and (ii) When the photons leave PBS1 through the same port and,
later, also leave the MZI in modes $w$ or $q$. Adding the probabilities for
these scenarios, we obtain

$\displaystyle\scalebox{0.9}{$P_{\mathrm{GHZ}}=\tfrac{1}{2}(1-\tau_{1})^{2}-\tfrac{1}{8}\left(\sqrt{(1-\tau_{1})(1-\tau_{2})}\cos\varphi+(1-\tau_{1})\right)^{2}$}.$
(C.18)

##  D Selecting optimal phase shifts

Figure D.1: (a) Optimal phase shift as a function of the blockaded optical
depth for BMs (blue solid) and for GHZ-state generation (black dashed). (b)
The success probabilities at the optimal phases shown in (a). The insets show
the same data on a logarithmic scale.

When examining the plots in the main text that show of the success probability
versus $\varphi$, a surprising feature emerges: While one would naively expect
that $\pi$ phase shifts yield optimal results, it turns out that in all
studied applications, the optimal phase is smaller than $\pi$. In Fig. D.1(a),
we compute the optimal phase shift, $\varphi_{\text{opt}}$, as a function of
the blockaded optical depth, ODb, for or BM and GHZ-state generation
protocols. Figure D.1(b) shows the corresponding success probabilities at the
optimal phase shifts from (a). The insets show the same data as the main plots
on a logarithmic scale. One can see that at large optical depths
($\text{OD}_{\text{b}}>50$), all curves in the insets are linear. We find that
the optimal phases scale as
$\varphi_{\text{opt}}-\pi\propto\mathrm{OD}^{\alpha}$, where $\alpha=-1$ for
the GHZ-state preparation protocol and $\alpha=-0.3$ for BMs. The infidelity
of our protocols scales as $1-P_{\text{opt}}\propto\mathrm{OD}^{\alpha}$,
where $\alpha\approx-0.9$ for both protocols.

## References

  * Kok  _et al._ (2007) P. Kok, W. J. Munro, K. Nemoto, T. C. Ralph, J. P. Dowling, and G. J. Milburn, “Linear optical quantum computing with photonic qubits,” Rev. Mod. Phys. 79, 135 (2007).
  * O’brien  _et al._ (2009) J. L. O’brien, A. Furusawa, and J. Vučković, “Photonic quantum technologies,” Nat. Photonics 3, 687–695 (2009).
  * Rudolph (2017) T. Rudolph, “Why I am optimistic about the silicon-photonic route to quantum computing,” APL Photonics 2, 030901 (2017).
  * Bartolucci  _et al._ (2021) S. Bartolucci, P. Birchall, H. Bombin, H. Cable, C. Dawson, M. Gimeno-Segovia, E. Johnston, K. Kieling, N. Nickerson, M. Pant, F. Pastawski, T. Rudolph, and C. Sparrow, “Fusion-based quantum computation,” arXiv: quant-ph/9705052 (2021).
  * Gottesman and Chuang (1999) D. Gottesman and I. L. Chuang, “Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations,” Nature 402, 390–393 (1999).
  * Raussendorf and Briegel (2001) R. Raussendorf and H. J. Briegel, “A one-way quantum computer,” Phys. Rev. Lett. 86, 5188 (2001).
  * Knill  _et al._ (2001) E. Knill, R. Laflamme, and G. J. Milburn, “A scheme for efficient quantum computation with linear optics,” Nature 409, 46–52 (2001).
  * Nielsen (2003) M. A. Nielsen, “Quantum computation by measurement and quantum memory,” Phys. Lett. A 308, 96–100 (2003).
  * Verstraete and Cirac (2004) F. Verstraete and J. I. Cirac, “Valence-bond states for quantum computation,” Phys. Rev. A 70, 060302(R) (2004).
  * Leung (2004) D. W. Leung, “Quantum computation by measurements,” Int. J. Quantum Inf. 2, 33–43 (2004).
  * Briegel  _et al._ (2009) H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest, “Measurement-based quantum computation,” Nat. Phys. 5, 19–26 (2009).
  * Briegel and Raussendorf (2001) H. J. Briegel and R. Raussendorf, “Persistent entanglement in arrays of interacting particles,” Phys. Rev. Lett. 86, 910 (2001).
  * Hein  _et al._ (2004) M. Hein, J. Eisert, and H. J. Briegel, “Multiparty entanglement in graph states,” Phys. Rev. A 69, 062311 (2004).
  * Nielsen (2004) M. A. Nielsen, “Optical quantum computation using cluster states,” Phys. Rev. Lett. 93, 040503 (2004).
  * Gottesman (1997) D. Gottesman, “Stabilizer codes and quantum error correction,” arXiv: quant-ph/9705052 (1997).
  * Bravyi and Kitaev (2005) S. Bravyi and A. Kitaev, “Universal quantum computation with ideal Clifford gates and noisy ancillas,” Phys. Rev. A 71, 022316 (2005).
  * Varnava  _et al._ (2006) M. Varnava, D. E. Browne, and T. Rudolph, “Loss tolerance in one-way quantum computation via counterfactual error correction,” Phys. Rev. Lett. 97, 120501 (2006).
  * Dawson  _et al._ (2006) C. M. Dawson, H. L. Haselgrove, and M. A. Nielsen, “Noise thresholds for optical quantum computers,” Phys. Rev. Lett. 96, 020501 (2006).
  * Raussendorf  _et al._ (2007) R. Raussendorf, J. Harrington, and K. Goyal, “Topological fault-tolerance in cluster state quantum computation,” New J. of Phys. 9, 199 (2007).
  * Fowler  _et al._ (2012) A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface codes: Towards practical large-scale quantum computation,” Phys. Rev. A 86, 032324 (2012).
  * Note (1) Our work focuses on discrete-variable quantum computation. While large clusters of squeezed states have been demonstrated in continuous-variable quantum computation Yokoyama  _et al._ (2013); Chen  _et al._ (2014); Reimer  _et al._ (2016); Asavanant  _et al._ (2019), the latter approach faces other challenges that currently hinder its scalability, including the generation of Gottesman-Kitaev-Preskill (GKP) states Gottesman  _et al._ (2001).
  * Zeilinger  _et al._ (1997) A. Zeilinger, M. A. Horne, H. Weinfurter, and M. Żukowski, “Three-particle entanglements from two entangled pairs,” Phys. Rev. Lett. 78, 3031 (1997).
  * Browne and Rudolph (2005) D. E. Browne and T. Rudolph, “Resource-efficient linear optical quantum computation,” Phys. Rev. Lett. 95, 010501 (2005).
  * Lu  _et al._ (2007) C.-Y. Lu, X.-Q. Zhou, O. Gühne, W.-B. Gao, J. Zhang, Z.-S. Yuan, A. Goebel, T. Yang, and J.-W. Pan, “Experimental entanglement of six photons in graph states,” Nat. Phys. 3, 91–95 (2007).
  * Kieling  _et al._ (2007) K. Kieling, T. Rudolph, and J. Eisert, “Percolation, renormalization, and quantum computing with nondeterministic gates,” Phys. Rev. Lett. 99, 130501 (2007).
  * Wilde  _et al._ (2007) M. M. Wilde, F. Spedalieri, J. P. Dowling, and H. Lee, “Alternate scheme for optical cluster-state generation without number-resolving photon detectors,” Int. J. Quantum Inf. 5, 617–626 (2007).
  * Shadbolt  _et al._ (2012) P. J. Shadbolt, M. R. Verde, A. Peruzzo, A. Politi, A. Laing, M. Lobino, J. C. F. Matthews, M. G. Thompson, and J. L. O’Brien, “Generating, manipulating and measuring entanglement and mixture with a reconfigurable photonic circuit,” Nat. Photonics 6, 45–49 (2012).
  * Wang  _et al._ (2016) X.-L. Wang, L.-K. Chen, W. Li, H.-L. Huang, C. Liu, C. Chen, Y.-H. Luo, Z.-E. Su, D. Wu, Z.-D. Li, H. Lu, Y. Hu, X. Jiang, C.-Z. Peng, L. Li, N.-L. Liu, Y. A. Chen, C. Y. Lu, and J.-W. Pan, “Experimental ten-photon entanglement,” Phys. Rev. Lett. 117, 210502 (2016).
  * Istrati  _et al._ (2020) D. Istrati, Y. Pilnyak, J. C. Loredo, C. Antón, N. Somaschi, P. Hilaire, H. Ollivier, M. Esmann, L. Cohen, L. Vidro, C. Millet, A. Lemaître, I. Sagnes, A. Harouri, L. Lanco, P. Senellart, and H. S Eisenberg, “Sequential generation of linear cluster states from a single photon emitter,” Nature Communications 11, 1–8 (2020).
  * Li  _et al._ (2015) Y. Li, P. C. Humphreys, G. J. Mendoza, and S. C. Benjamin, “Resource costs for fault-tolerant linear optical quantum computing,” Phys. Rev. X 5, 041007 (2015).
  * Schön  _et al._ (2007) C. Schön, K. Hammerer, M. M. Wolf, J. I. Cirac, and E. Solano, “Sequential generation of matrix-product states in cavity QED,” Phys. Rev. A 75, 032311 (2007).
  * Lindner and Rudolph (2009) N. H. Lindner and T. Rudolph, “Proposal for pulsed on-demand sources of photonic cluster state strings,” Phys. Rev. Lett. 103, 113602 (2009).
  * Schwartz  _et al._ (2016) I. Schwartz, D. Cogan, E. R. Schmidgall, Y. Don, L. Gantz, O. Kenneth, N. H. Lindner, and D. Gershoni, “Deterministic generation of a cluster state of entangled photons,” Science 354, 434–437 (2016).
  * Pichler  _et al._ (2017) H. Pichler, S. Choi, P. Zoller, and M. D. Lukin, “Universal photonic quantum computation via time-delayed feedback,” Proc. Natl. Acad. Sci. 114, 11362–11367 (2017).
  * Duan and Kimble (2004) L.-M. Duan and H. J. Kimble, “Scalable photonic quantum computation through cavity-assisted interactions,” Phys. Rev. Lett. 92, 127902 (2004).
  * Reiserer  _et al._ (2014) A. Reiserer, N. Kalb, G. Rempe, and S. Ritter, “A quantum gate between a flying optical photon and a single trapped atom,” Nature 508, 237–240 (2014).
  * Hacker  _et al._ (2016) B. Hacker, S. Welte, G. Rempe, and S. Ritter, “A photon–photon quantum gate based on a single atom in an optical resonator,” Nature 536, 193–196 (2016).
  * Rosenblum  _et al._ (2017) S. Rosenblum, A. Borne, and B. Dayan, “Analysis of deterministic swapping of photonic and atomic states through single-photon Raman interaction,” Phys. Rev. A 95, 033814 (2017).
  * Bechler  _et al._ (2018) O. Bechler, A. Borne, S. Rosenblum, G. Guendelman, O. E. Mor, M. Netser, T. Ohana, Z. Aqua, N. Drucker, R. Finkelstein, Y. Lovsky, R. Bruch, D. Gurovich, E. Shafir, and B. Dayan, “A passive photon–atom qubit swap operation,” Nat. Phys. 14, 996–1000 (2018).
  * Borregaard  _et al._ (2019) J. Borregaard, A. S. Sørensen, and P. Lodahl, “Quantum networks with deterministic spin–photon interfaces,” Adv. Quantum Technol. 2, 1800091 (2019).
  * Paris  _et al._ (2000) M. G. A. Paris, M. B. Plenio, S. Bose, D. Jonathan, and G. M. D’ariano, “Optical Bell measurement by Fock filtering,” Phys. Lett. A 273, 153–158 (2000).
  * Nemoto and Munro (2004) K. Nemoto and W. J. Munro, “Nearly deterministic linear optical controlled-NOT gate,” Phys. Rev. Lett. 93, 250502 (2004).
  * Nemoto and Munro (2005) K. Nemoto and W. J. Munro, “Universal quantum computation on the power of quantum non-demolition measurements,” Phys. Lett. A 344, 104–110 (2005).
  * Munro  _et al._ (2005a) W. J. Munro, K. Nemoto, and T. P. Spiller, “Weak nonlinearities: a new route to optical quantum computation,” N. J. Phys. 7, 137 (2005a).
  * Munro  _et al._ (2005b) W. J. Munro, K. Nemoto, R. G. Beausoleil, and T. P. Spiller, “High-efficiency quantum-nondemolition single-photon-number-resolving detector,” Phys. Rev. A 71, 033819 (2005b).
  * Barrett  _et al._ (2005) S. D. Barrett, P. Kok, K. Nemoto, R. G. Beausoleil, W. J. Munro, and T. P. Spiller, “Symmetry analyzer for nondestructive Bell-state detection using weak nonlinearities,” Phys. Rev. A 71, 060302(R) (2005).
  * Shapiro (2006) J. H. Shapiro, “Single-photon Kerr nonlinearities do not help quantum computation,” Phys. Rev. A 73, 062305 (2006).
  * Louis  _et al._ (2007) S. G. R. Louis, K. Nemoto, W. J. Munro, and T. P. Spiller, “The efficiencies of generating cluster states with weak nonlinearities,” N. J. Phys. 9, 193 (2007).
  * Shapiro and Razavi (2007) J. H. Shapiro and M. Razavi, “Continuous-time cross-phase modulation and quantum computation,” New J. Phys. 9, 16 (2007).
  * Gea-Banacloche (2010) J. Gea-Banacloche, “Impossibility of large phase shifts via the giant Kerr effect with single-photon wave packets,” Phys. Rev. A 81, 043823 (2010).
  * Stace  _et al._ (2009) T. M. Stace, S. D. Barrett, and A. C. Doherty, “Thresholds for topological codes in the presence of loss,” Phys. Rev. Lett. 102, 200501 (2009).
  * Barrett and Stace (2010) S. D. Barrett and T. M. Stace, “Fault tolerant quantum computation with very high threshold for loss errors,” Phys. Rev. Lett. 105, 200502 (2010).
  * Marsili  _et al._ (2013) F. Marsili, V. B. Verma, J. A. Stern, S. Harrington, A. E. Lita, T. Gerrits, I. Vayshenker, B. Baek, M. D. Shaw, R. P. Mirin, and S. N. Nam, “Detecting single infrared photons with 93% system efficiency,” Nat. Photonics 7, 210–214 (2013).
  * Reddy  _et al._ (2020) D. V. Reddy, R. R. Nerem, S. W. Nam, R. P. Mirin, and V. B. Verma, “Superconducting nanowire single-photon detectors with 98% system detection efficiency at 1550 nm,” Optica 7, 1649–1653 (2020).
  * Boller  _et al._ (1991) K.-J. Boller, A. Imamoğlu, and S. E. Harris, “Observation of electromagnetically induced transparency,” Phys. Rev. Lett. 66, 2593 (1991).
  * Distante  _et al._ (2017) E. Distante, P. Farrera, A. Padrón-Brito, D. Paredes-Barato, G. Heinze, and H. De Riedmatten, “Storing single photons emitted by a quantum memory on a highly excited Rydberg state,” Nat. Commun. 8, 1–6 (2017).
  * Tiarks  _et al._ (2019) D. Tiarks, S. Schmidt-Eberle, T. Stolz, G. Rempe, and S. Dürr, “A photon–photon quantum gate based on Rydberg interactions,” Nat. Phys. 15, 124–126 (2019).
  * Lahad and Firstenberg (2017) O. Lahad and O. Firstenberg, “Induced cavities for photonic quantum gates,” Phys. Rev. Lett. 119, 113601 (2017).
  * Rosenblum  _et al._ (2016) S. Rosenblum, O. Bechler, I. Shomroni, Y. Lovsky, G. Guendelman, and B. Dayan, “Extraction of a single photon from an optical pulse,” Nat. Photonics 10, 19–22 (2016).
  * Tiecke  _et al._ (2014) T. G. Tiecke, J. D. Thompson, N. P. de Leon, L. R. Liu, V. Vuletić, and M. D. Lukin, “Nanophotonic quantum phase switch with a single atom,” Nature 508, 241–244 (2014).
  * Ralph  _et al._ (2015) T. C. Ralph, I. Söllner, S. Mahmoodian, A. G. White, and P. Lodahl, “Photon sorting, efficient bell measurements, and a deterministic controlled-Z gate using a passive two-level nonlinearity,” Phys. Rev. Lett. 114, 173603 (2015).
  * Gerry  _et al._ (2005) C. Gerry, P. Knight, and P. L. Knight,  _Introductory Quantum Optics_ (Cambridge university press, 2005).
  * Stern  _et al._ (2013) L. Stern, B. Desiatov, I. Goykhman, and U. Levy, “Nanoscale light–matter interactions in atomic cladding waveguides,” Nat. Commun. 4, 1–7 (2013).
  * Keil  _et al._ (2016) M. Keil, O. Amit, S. Zhou, D. Groswasser, Y. Japha, and R. Folman, “Fifteen years of cold matter on the atom chip: promise, realizations, and prospects,” J. Mod. Opt. 63, 1840–1885 (2016).
  * Kitching (2018) J. Kitching, “Chip-scale atomic devices,” Appl. Phys. Rev. 5, 031302 (2018).
  * Bajcsy  _et al._ (2009) M. Bajcsy, S. Hofferberth, V. Balic, T. Peyronel, M. Hafezi, A. S. Zibrov, V. Vuletic, and M. D. Lukin, “Efficient all-optical switching using slow light within a hollow fiber,” Phys. Rev. Lett. 102, 203902 (2009).
  * Venkataraman  _et al._ (2011) V. Venkataraman, K. Saha, P. Londero, and A. L. Gaeta, “Few-photon all-optical modulation in a photonic band-gap fiber,” Phys. Rev. Lett. 107, 193902 (2011).
  * Venkataraman  _et al._ (2013) V. Venkataraman, K. Saha, and A. L. Gaeta, “Phase modulation at the few-photon level for weak-nonlinearity-based quantum computing,” Nat. Phot. 7, 138 (2013).
  * Meng  _et al._ (2018) Y. Meng, A. Dareau, P. Schneeweiss, and A. Rauschenbeutel, “Near-ground-state cooling of atoms optically trapped 300 nm away from a hot surface,” Phys. Rev. X 8, 031054 (2018).
  * Corzo  _et al._ (2019) N. V. Corzo, J. Raskop, A. Chandra, A. S. Sheremet, B. Gouraud, and J. Laurat, “Waveguide-coupled single collective excitation of atomic arrays,” Nature 566, 359–362 (2019).
  * Johnson  _et al._ (2019) A. Johnson, M. Blaha, A. E. Ulanov, A. Rauschenbeutel, P. Schneeweiss, and J. Volz, “Observation of collective superstrong coupling of cold atoms to a 30-m long optical resonator,” Phys. Rev. Lett. 123, 243602 (2019).
  * Matsuda  _et al._ (2009) N. Matsuda, R. Shimizu, Y. Mitsumori, H. Kosaka, and K. Edamatsu, “Observation of optical-fibre Kerr nonlinearity at the single-photon level,” Nat. photonics 3, 95–98 (2009).
  * Gorshkov  _et al._ (2011) A. V. Gorshkov, J. Otterbach, M. Fleischhauer, T. Pohl, and M. D. Lukin, “Photon-photon interactions via Rydberg blockade,” Phys. Rev. Lett. 107, 133602 (2011).
  * Note (2) There is a factor of 2 difference between our definition of $\varepsilon$ and Ref. Lahad and Firstenberg (2017), since we refer to loss of modal amplitude and Ref. Lahad and Firstenberg (2017) refers to intensity loss.
  * Tresp  _et al._ (2016) C. Tresp, C. Zimmer, I. Mirgorodskiy, H. Gorniaczyk, A. Paris-Mandoki, and S. Hofferberth, “Single-photon absorber based on strongly interacting Rydberg atoms,” Phys. Rev. Lett. 117, 223001 (2016).
  * Baur  _et al._ (2014) S. Baur, D. Tiarks, G. Rempe, and S. Dürr, “Single-photon switch based on Rydberg blockade,” Phys. Rev. Lett. 112, 073901 (2014).
  * Gaj  _et al._ (2014) A. Gaj, A. T. Krupp, J. B. Balewski, R. Löw, S. Hofferberth, and T. Pfau, “From molecular spectra to a density shift in dense Rydberg gases,” Nat. Commun. 5, 1–5 (2014).
  * Ewert and van Loock (2014) F. Ewert and P. van Loock, “3/4-efficient Bell measurement with passive linear optics and unentangled ancillae,” Phys. Rev. Lett. 113, 140403 (2014).
  * Braunstein and Mann (1995) S. L. Braunstein and A. Mann, “Measurement of the Bell operator and quantum teleportation,” Phys. Rev. A 51, R1727 (1995).
  * Note (3) This calculation assumes that the nonlinearity is implemented using self-phase modulation, which takes place when two photons of the same polarization travel along the same arm of the MZI. The latter is experimentally achievable in existing Rydberg-EIT platforms Firstenberg  _et al._ (2013); Tiarks  _et al._ (2019).
  * Divochiy  _et al._ (2008) A. Divochiy, F. Marsili, D. Bitauld, A. Gaggero, R. Leoni, F. Mattioli, A. Korneev, V. Seleznev, N. Kaurova, O. Minaeva, G. Gol’tsman, G. L. Konstantinos, M. Benkhaoul, F. Lévy, and A. Fiore, “Superconducting nanowire photon-number-resolving detector at telecommunication wavelengths,” Nat. Photonics 2, 302–306 (2008).
  * Dauler  _et al._ (2009) E. A. Dauler, A. J. Kerman, B. S. Robinson, J. K. W. Yang, B. Voronov, G. Goltsman, S. A. Hamilton, and K. K. Berggren, “Photon-number-resolution with sub-30-ps timing using multi-element superconducting nanowire single photon detectors,” J. Mod. Opt. 56, 364–373 (2009).
  * Sahin  _et al._ (2013) D. Sahin, A. Gaggero, Z. Zhou, S. Jahanmirinejad, F. Mattioli, R. Leoni, J. Beetz, M. Lermer, M. Kamp, S. Höfling, and A. Fiore, “Waveguide photon-number-resolving detectors for quantum photonic integrated circuits,” Appl. Phys. Lett. 103, 111116 (2013).
  * Endo  _et al._ (2021) M. Endo, T. Sonoyama, M. Matsuyama, F. Okamoto, S. Miki, M. Yabuno, F. China, H. Terai, and A. Furusawa, “Quantum detector tomography of superconducting nanostrip photon-number-resolving detector,” arXiv: quant-ph/2102.09712 (2021).
  * Liu  _et al._ (2016) Z.-Y. Liu, Y.-H. Chen, Y.-C. Chen, H.-Y. Lo, P.-J. Tsai, I. A. Yu, Y.-C. Chen, and Y.-F. Chen, “Large cross-phase modulations at the few-photon level,” Phys. Rev. Lett. 117, 203601 (2016).
  * Grice (2011) W. P. Grice, “Arbitrarily complete Bell-state measurement using only linear optical elements,” Phys. Rev. A 84, 042331 (2011).
  * Politi  _et al._ (2009) A. Politi, J. C. F. Matthews, and J. L. O’brien, “Shor’s quantum factoring algorithm on a photonic chip,” Science 325, 1221–1221 (2009).
  * Note (4) Since finite detection efficiency limits our protocols in the same manner as the linear protocols, it does not affect the improvement factor and, hence, not included in the presented equation.
  * Firstenberg  _et al._ (2013) O. Firstenberg, T. Peyronel, Q.-Y. Liang, A. V. Gorshkov, M. D. Lukin, and V. Vuletić, “Attractive photons in a quantum nonlinear medium,” Nature 502, 71–75 (2013).
  * Finkelstein  _et al._ (2020) R. Finkelstein, G. Winer, D. Z. Koplovich, O. Arenfrid, T. Hoinkes, G. Guendelman, M. Netser, E. Poem, A. Rauschenbeutel, B. Dayan, and O. Firstenberg, “Super-extended nanofiber-guided field for coherent interaction with hot atoms,” arXiv: 2010.08935 (2020).
  * Pang  _et al._ (2020) X.-L. Pang, A.-L. Yang, J.-P. Dou, H. Li, C.-N. Zhang, E. Poem, D. J. Saunders, H. Tang, J. Nunn, I. A. Walmsley, and X.-M. Jin, “A hybrid quantum memory–enabled network at room temperature,” Sci. Adv. 6, eaax1425 (2020).
  * Yokoyama  _et al._ (2013) S. Yokoyama, R. Ukai, S. C. Armstrong, C. Sornphiphatphong, T. Kaji, S. Suzuki, J.-I. Yoshikawa, H. Yonezawa, N. C. Menicucci, and A. Furusawa, “Ultra-large-scale continuous-variable cluster states multiplexed in the time domain,” Nat. Photonics 7, 982–986 (2013).
  * Chen  _et al._ (2014) M. Chen, N. C. Menicucci, and O. Pfister, “Experimental realization of multipartite entanglement of 60 modes of a quantum optical frequency comb,” Phys. Rev. Lett. 112, 120505 (2014).
  * Reimer  _et al._ (2016) C. Reimer, M. Kues, P. Roztocki, B. Wetzel, F. Grazioso, B. E. Little, S. T. Chu, T. Johnston, Y. Bromberg, L. Caspani, D. J. Moss, and R. Morandotti, “Generation of multiphoton entangled quantum states by means of integrated frequency combs,” Science 351, 1176–1180 (2016).
  * Asavanant  _et al._ (2019) W. Asavanant, Y. Shiozawa, S. Yokoyama, B. Charoensombutamon, H. Emura, R. N. Alexander, S. Takeda, J.-I. Yoshikawa, N. C. Menicucci, H. Yonezawa, and A. Furusawa, “Generation of time-domain-multiplexed two-dimensional cluster state,” Science 366, 373–376 (2019).
  * Gottesman  _et al._ (2001) D. Gottesman, A. Kitaev, and J. Preskill, “Encoding a qubit in an oscillator,” Phys. Rev. A 64, 012310 (2001).