#  Hardware requirements for realizing a quantum advantage with deterministic
single-photon sources

Patrik I. Sund  Center for Hybrid Quantum Networks (Hy-Q), Niels Bohr
Institute
University of Copenhagen, Blegdamsvej 17, DK-2100 Copenhagen, Denmark  Ravitej
Uppu  Center for Hybrid Quantum Networks (Hy-Q), Niels Bohr Institute
University of Copenhagen, Blegdamsvej 17, DK-2100 Copenhagen, Denmark
Department of Physics & Astronomy, University of Iowa, Iowa City, IA 52242
United States  Stefano Paesani  Center for Hybrid Quantum Networks (Hy-Q),
Niels Bohr Institute
University of Copenhagen, Blegdamsvej 17, DK-2100 Copenhagen, Denmark  NNF
Quantum Computing Programme, Niels Bohr Institute, University of Copenhagen,
Blegdamsvej 17, Copenhagen 2100, Denmark.  Peter Lodahl<EMAIL_ADDRESS>Center for Hybrid Quantum Networks (Hy-Q), Niels Bohr Institute
University of Copenhagen, Blegdamsvej 17, DK-2100 Copenhagen, Denmark

(October 16, 2023)

###### Abstract

Boson sampling is a specialised algorithm native to the quantum photonic
platform developed for near-term demonstrations of quantum advantage over
classical computers. While clear useful applications for such near-term pre-
fault-tolerance devices are not currently known, reaching a quantum advantage
regime serves as a useful benchmark for the hardware. Here, we analyse and
detail hardware requirements needed to reach quantum advantage with
deterministic quantum emitters, a promising platform for photonic quantum
computing. We elucidate key steps that can be taken in experiments to overcome
practical constraints and establish quantitative hardware-level requirements.
We find that quantum advantage is within reach using quantum emitters with an
efficiency of $60\%-70\%$ and interferometers constructed according to a
hybrid-mode-encoding architecture, constituted of Mach–Zehnder interferometers
with an insertion loss of $0.0035\text{\,}\mathrm{dB}$ (a transmittance of
$99.92\%$) per component.

Devices based on quantum systems can potentially outperform the capabilities
of classical computers [1, 2]. Quantum technologies are rapidly progressing
towards this goal and new computational regimes are being explored [3, 4, 5].
While fault-tolerance is generally thought to be necessary to reach most
practical applications, reaching this regime necessitates hardware
requirements that are far from current capabilities, limiting demonstrations
to small-scale experiments [6, 7]. Quantum advantage (QA), where specialized
algorithms can demonstrate speed-ups over classical computers, has been
identified as an intermediate milestone computational regime amenable for
near-term hardware using readily available quantum hardware components [8, 9,
3]. While it is currently not known if any practical applications are possible
in this regime, it serves as an entry point to beyond-classical capabilities
and an important benchmark for developing scalable platforms that can evolve
towards fault-tolerance. In this context, we analyze the hardware requirements
for achieving QA using photonic quantum hardware, where fusion-based
approaches for fault-tolerant quantum computing have been proposed [10, 11].

Aaronson and Arkhipov proposed boson sampling of photonic quantum states [8]
as a route for demonstrating QA with near-term quantum hardware. The key
insight is the connection between the correlations induced by linear
interference operations on $N$ indistinguishable photons in an $M$-mode linear
optical interferometer and the matrix permanent, a quantity that is
$\\#$P-hard to compute on a classical machine [12, 13]. However, imperfections
in photon sources and losses in optical interferometer networks and detectors
rapidly diminish the degree of quantum correlations and overthrow the quantum
advantage. This loss of QA has been captured in models on ‘noisy’ boson
samplers that proposed efficient classical computation algorithms, thereby
imposing strict bounds on the indistinguishability of photons and the overall
optical loss [14, 15, 16]. As quantum photonic hardware continues to rapidly
advance [17, 18, 19, 20], the formulation of quantitative benchmarks for
realizing QA is a critical need as they provide milestones for guiding the
hardware development.

In this paper, we present a comprehensive analysis quantifying the performance
metrics of the constituent building blocks essential for surpassing efficient
classical algorithms with boson sampling. By benchmarking our framework
against state-of-the-art single-photon sources and photonic integrated
circuits, we identify a realistic regime for conducting QA experiments. Our
analysis focuses on the case of boson samplers based on single-photon sources
(discrete variable photonic qubits), where several proof-of-concept
experiments have been carried out to date [21, 22, 23, 24, 25].

Recent advances in deterministic photon sources employing semiconductor
quantum dots have demonstrated the generation of $>$100 nearly-identical
photons [26, 27], setting the stage for scaling up from proof-of-concept
experiments. A remaining challenge is to realize large photonic circuits with
sufficiently low loss such that the large photonic resource can be processed
and measured to demonstrate QA [14, 19]. As the optical loss in an
interferometer circuit is highly dependent on its design, i.e., the spatial
arrangement of Mach-Zehnder interferometers (MZI), we analyze the requirements
of the individual MZIs and their integration into an optimal architecture.
Combining the analysis of the source imperfections and optical circuit loss,
we identify two key optimizations, a rectangular circuit architecture and the
encoding of modes in multiple degrees of freedom, that could enable an
unequivocal demonstration of QA. We determine that an insertion loss of
$3.5\text{\,}\mathrm{m}\mathrm{d}\mathrm{B}$ per MZI interferometer, i.e., a
transmittance of $99.92\text{\,}\mathrm{\char 37\relax}$ is sufficient for the
optimal architecture using state-of-the-art photon sources and detectors. This
sets a clear target metric for ongoing advances in photonic integrated
circuits [28, 29], and is already within reach for the specialized, fixed
circuits employed in Refs. [25, 30].

##  I The boson sampling algorithm and its validation

Figure 1:  a A general boson sampling setup, consisting of a source of multi-
photon input states, a multi-port interferometer, and detectors. The
associated system losses $\rho$ are indicated for each sub-component. b A
boson sampling setup based on a deterministic single-photon source (SPS) and a
spatially encoded multimode interferometer. The single-photon source emits a
string of single photons in pre-determined time bins, illustrated as filled
red circles. A demultiplexer converts the photon stream into a $p$-photon
source by deterministically switching each photon into a separate mode. The
spatially encoded input state is sent into an interferometer constructed from
a network of MZIs. Each MZI is illustrated as a cross, where each cross
consists of two phase shifters (PSs) and two beamsplitters (BSs) arranged
according to the illustration at the bottom. c A boson sampling setup based on
a deterministic single-photon source (SPS) and a time-bin interferometer. The
SPS is identical to the case in (b) where $\tau$ denotes the time separation
between subsequent photons. The interferometer consists of reconfigurable
time-dependent MZIs, where time-dependent phase shifters are implemented using
electro-optic modulators (EOMs), which are connected by delay lines
illustrated as blue lines, where one loop corresponds to a single time-bin
$\tau$ of delay. For both b and c, it is assumed that up to $l$ photons may be
lost throughout the setup—illustrated as a red circle with a dashed
outline—due to residual optical loss associated with each component.

Boson sampling is the task of sampling from the output photon distribution
after multiple independent photons have interfered in a multimode linear
optical interferometer. The setup for implementing boson sampling is
schematically illustrated in Fig. 1a) highlighting the key components: an
input consisting of multiple indistinguishable photons, a large multimode
interferometer module, and single-photon detectors.

The computational complexity of simulating boson sampling arises from the
connection between multi-photon correlations and the calculation of matrix
permanents. However, the computational hardness of calculating the matrix
permanent decreases when duplicate rows or columns occur from multiple photons
occupying the same input or output mode. To preserve the computational
complexity, it is crucial to ensure collision-free states at both the inputs
and outputs [8], meaning that each mode contains at most one photon.
Collision-free input states can be guaranteed by choosing the initial
condition, where no more than one photon is injected into each input mode.
Ensuring collision-free outputs demands the interferometer to possess a large
number of modes per photon. Specifically, the number of modes $m$ must scale
at least quadratically with the number of photons $p$, i.e., $m\propto p^{2}$,
a requirement arising from a phenomenon called the bosonic birthday paradox
[8, 31]. In experiments, collision-free outputs can be ensured through post-
selection of events where photons are detected in the same number of output
modes as input modes while discarding all other events. This post-selection
strategy remains applicable even when the detectors lack number-resolving
capabilities, thereby enabling near-term implementations of QA with efficient
single-photon detectors [25, 30, 32].

To demonstrate QA, it is essential that the output samples can be validated as
being computationally hard to produce by classical means [14]. Due to the
computational hardness, direct validation of the samples by comparison with
exact distributions is infeasible. Within these constraints, the validation of
QA through boson sampling requires two steps. First, we must require that
deviations in the experimental setup are small enough that approximate
classical algorithms cannot simulate the output distribution efficiently.
Secondly, instead of validating that the samples are produced from the exact
distribution, one verifies that the outputs are not reproduced by a
computationally efficient distribution [14, 25]. Specifically, statistical
tests performed on the output samples obtained in a boson sampling experiment
verify that the experimentally observed distribution differs significantly
from a set of efficiently computable distributions. These statistical tests
provide a termination condition for the experiment, whereby the boson sampler
is run until a sufficient number of output samples are generated to establish
the statistical tests’ convergence unequivocally. Thus, a QA demonstration
will be feasible if a sufficient number of samples can be produced over an
experimentally viable integration time, proportional to the sample acquisition
rate, $r_{\text{sample}}$. The sample acquisition rate in an experiment is
equal to the product of the generation rate of the multiple photon input state
$r_{\text{input}}$ and the probability of the state reaching the detectors,
$P_{\text{sample}}$:

$\displaystyle r_{\text{sample}}=P_{\text{sample}}\cdot r_{\text{input}}.$ (1)

The probability of sampling a $p$-photon coincidence at the output is related
to the total per-photon efficiency of the system $P_{\text{sys}}$ as

$\displaystyle P_{\text{sample}}=P_{\text{sys}}^{p}.$ (2)

For convenience, we express these probabilities in decibels, i.e.,
$\rho_{\text{i}}=-10\log_{10}(P_{\text{i}})$. For brevity, we refer to the
decibel probability, $\rho_{\text{i}}$ as loss, while $P_{\text{i}}$ is
referred to as efficiency.

##  II Experimental setup and imperfections

As illustrated in Fig. 1a), the loss in the boson sampling architecture can be
broken down into component-level losses as

$\displaystyle\rho_{\text{sys}}=\rho_{\text{src}}+\rho_{\text{int}}+\rho_{\text{det}},$
(3)

where $\rho_{\text{src}}$ is the source loss, $\rho_{\text{int}}$ is the
interferometer loss, and $\rho_{\text{det}}$ is the detector loss. In this
section, we detail the implementation and requirements on the components and
discuss strategies to tackle experimental limitations in each component.

###  II.1 Input state preparation

The input state in the boson sampling algorithm consists of multiple
indistinguishable single photons, each generated and encoded separately.
Below, we discuss these two steps and any imperfections introduced in real
experiments.

An important figure of merit for the photons employed in a boson sampling
experiment is the pair-wise indistinguishability, $x^{2}$, defined as the
overlap integral of photons with wavefunctions $\psi$ and $\psi^{\prime}$,
$x^{2}=\braket{\psi^{\prime}}{\psi}=\int\psi^{\prime*}(t)\psi(t)\mathrm{d}t$.
In experiments, the indistinguishability is quantified through the
Hong–Ou–Mandel visibility in an interference experiment [33]. To ensure
computational hardness, photon indistinguishability approaching near-unity
visibility is necessary.

Highly indistinguishable photons have been generated employing two approaches:
1) non-linear optics and 2) single quantum emitters. The former exploits the
energy-time correlations in optical processes in nonlinear media like
spontaneous parametric down-conversion and spontaneous four-wave mixing to
generate correlated photon pairs. The resulting squeezed state can be used
directly for Gaussian Boson Sampling [9, 30, 4], or alternatively, the
detection of one photon in the pair can be used to herald the presence of the
other. Despite being probabilistic, the heralded nature can be exploited
through active feed-forward and multiplexing to realize a near-deterministic
photon source [34]. As the sources suffer from an intrinsic trade-off between
the photon number purity (the probability of having one and only one photon
pair per pulse) and the photon pair generation rate, this requires massive
multiplexing of many probabilistic sources to reach near-deterministic
operation with high number purity, which is an active area of research [35].
These challenges and trade-offs could be overcome by leveraging the
deterministic light-matter interactions enabled by coupling a highly-efficient
single-photon emitter (e.g., a semiconductor quantum dot) to a nanophotonic
structure [36]. Single-photon sources based on such deterministic light–matter
interfaces have recently enabled the on-demand generation of $>$100 highly
indistinguishable single photons operational at a rate of up to GHz, thus
highlighting an avenue for realizing boson sampling in the QA regime [26].

Photons generated using such deterministic light-matter interfaces are
naturally encoded in different time bins as determined by the excitation
process of the quantum emitter. While these time-bin encoded photonic states
can be readily employed for boson sampling [37, 38], compatibility with
photonic integrated circuits requires converting the time-bin encoded photons
to spatial encoding using a demultiplexer [25, 39]. The demultiplexer takes an
incoming stream of $p$ single photons separated in time and converts it to $p$
simultaneous photons in separate spatial modes. In both time-bin (see Fig.
1c)) as well as demultiplexed spatial-bin encoding (Fig. 1b), in the
demultiplexed spatial-bin encoded case, a single-photon source emitting at a
rate of $r_{\text{single-photon}}$ is converted to a source of $p$ single
photons emitted at a rate of $r_{\text{single-photon}}/p$. With a time-bin
encoding, the rate will depend on the time-bin interferometer architecture
employed, but for the case we will analyze, the input state generation rate
will be $2r_{\text{single-photon}}/m$, where $m$ is the number of modes, such
that $m/2$ is the number of time-bins, as will be explained in more detail
later.

As quantum dot sources have proven capable of producing long strings of highly
indistinguishable photons [26], the scalability of this approach is mainly
determined by the overall efficiency of generating single photons and
delivering them to the demultiplexer, as well as the actual efficiency of the
demultiplexer setup. We specifically consider and benchmark the case of a
single deterministic source but note that access to multiple deterministic
quantum dot sources would allow for spatially encoded experiments with higher
input state generation rates and lower demultiplexer losses. The simultaneous
use of multiple sources relies on the development of local tuning methods for
overcoming intrinsic inhomogeneities of quantum dot sources, and important
progress has recently been reported both for quantum dots in bulk samples [40]
and in nanophotonic waveguides [41].

A time-to-spatial mode demultiplexer can be realized by sending the emitted
photon stream through a binary tree of switches. Each step in the tree doubles
the number of spatial modes, as illustrated in Fig. 1b), such that the full
demultiplexer requires a depth of $\lceil\log_{2}(p)\rceil$. Each output mode
from the demultiplexer requires a specific optical delay to synchronize all
photons. We associate a loss of $\rho_{\text{switch}}$ with each switching
operation, such that the overall loss of the demultiplexer is:

$\displaystyle\rho_{\text{dmx}}=\lceil\log_{2}(p)\rceil\rho_{\text{switch}}.$

Finally, there will be a coupling loss, $\rho_{\text{coupling}}$ associated
with connecting the output of the demultiplexer to the input of the
interferometer. Thus, the overall source loss is

$\displaystyle\rho_{\text{src}}=\rho_{\text{sps}}+\rho_{\text{dmx}}+\rho_{\text{coupling}},$

where $\rho_{\text{sps}}$ is the loss associated with the single-photon source
itself, accommodating for inefficiencies associated with the generation of
single photons and subsequent coupling from the cavity or waveguide applied
[36].

We note that the number of photons generated should ideally be kept as low as
possible (for the targeted computational complexity) while maintaining
intractability, as the sample acquisition rate will decrease exponentially
with system efficiency for an increasing number of input photons in accordance
with Eq. (2). In order to increase acquisition rates, experimental efforts
typically employ a related algorithm called Aaronson–Brod boson sampling [42],
where an additional $l$ photons are added to the $p$ input photons, while the
outputs are post-selected to contain the same number of photons as before. The
probability of detecting the correct number of photons, i.e. the probability
of generating a sample, $P_{\text{sample}}(p,l)$ can then be expressed as

$\displaystyle P_{\text{sample}}(p,l)$
$\displaystyle=P_{\text{sys}}^{p-l}(1-P_{\text{sys}})^{l}\binom{p}{l},$ (4)

where the factor $\binom{p}{l}$ is the number of combinations in which one can
lose $l$ photons from $p$ input photons. This leads to a speed-up in the
sample acquisition rate, which increases combinatorially with the number of
lost photons $l$. The downside is that post-selection increases the deviation
from the ideal case and lowers the computational complexity. In practice, the
simulation algorithm in Ref. [15] can approximate the output of such an
experiment within an error $E$ bounded by

$\displaystyle\frac{x^{2(k+1)}(\frac{p-l}{p})^{k+1}}{1-(x^{2}\frac{p-l}{p})}$
$\displaystyle\geq E^{2},$ (5)

where $x^{2}$ is the indistinguishability of the photons. Thus, the number of
lost photons allowed depends on the indistinguishability of the photons in the
input state.

###  II.2 Interferometer design and operation

Multimode interferometers are typically constructed using cascaded arrays of
Mach-Zehnder Interferometers (MZIs) and implement an $m$-dimensional unitary
matrix operation, with the circuit accommodating $m$ input modes and $m$
output modes. To validate boson sampling through statistical sampling of
random unitary circuits [8], experiments require either several static
circuits or a programmable circuit of MZIs with adjustable beam splitters and
phase shifters. The latter approach is favored, as it offers access to a
substantial number of random unitary operations [43]. Universal interferometer
architectures enable the implementation of all unitary transformations on $m$
modes, effectively generating any $m\times m$ unitary matrix [44, 45].

The per-photon loss for an interferometer architecture depends on the number
of optical components, i.e. MZIs, a photon passes through from the input to
the output. We will refer to this number of MZIs as the optical depth $D(m)$,
such that the interferometer loss can be written as

$\displaystyle\rho_{\text{int}}$ $\displaystyle=D(m)\cdot\rho_{\text{MZI}}.$

The depth will increase for a higher number of modes where the exact
dependence is given by the specific architecture employed. As such, there are
two main strategies that are employed to reduce loss: 1. Reducing the number
of modes, and 2. Employing interferometer architectures with a lower optical
depth for a given number of modes.

###  II.3 Reducing the number of modes

Due to the challenges in scaling up low-loss interferometers, experiments
involving a large number of photons ($p>10$) have employed interferometers
with the number of modes $m$ smaller than $p^{2}$. Consequently, this choice
yields a proportionally reduced depth $D(m)$. Although this reduction in the
number of modes mitigates optical loss within the interferometer, the bosonic
birthday paradox no longer holds, i.e., the outputs cannot be assumed to be
collision-free. In this scenario, the output event where multiple photons
occupy the same mode will be indistinguishable from photon loss unless
detectors with number-resolving capabilities are utilized. However, using the
framework established in Ref. [46], it can be shown that the computational
complexity of boson sampling with collisions is at least as high as the
computational complexity of collision-free boson sampling with the same number
of nonzero elements. For more details, we refer to Appendix A.

Assuming a post-selection criterion where the detection of photons is
restricted to $d$ $(<p)$ modes, with $p$ representing the number of input
photons, Eq. (4) can be reformulated to derive the total sample efficiency
$P_{\text{sample, lin}}$ for a linear number of modes ($m\propto p$)

$\displaystyle P_{\text{sample, lin}}(p,d)$
$\displaystyle=\sum_{l=0}^{d}P_{\text{sys}}^{(p-l)}(1-P_{\text{sys}})^{l}\binom{p}{l}P_{\text{ps}}(p,d,l,m).$
(6)

Here, $P_{\text{ps}}(p,d,l,m)$ is the probability of detecting an output state
with $d-l$ collisions and $p-l$ photons from an interferometer with $m$
modes–essentially quantifying the effective post-selection efficiency. This
equation involves summing the probabilities of all possible collision and
photon loss configurations that result in photodetection in $d$ modes. These
probabilities are then multiplied by the occurrence probability of the given
combination of losses and collisions. The computation of Eq. (6) relies on the
knowledge of the effective post-selection efficiency $P_{\text{ps}}(p,d,l,m)$.
To estimate this quantity, we assume uniform sampling of Haar-random
scattering matrices in the Hilbert space. Thus, we can estimate the effective
post-selection efficiency as the ratio between the size of the Hilbert space
with $p-l$ photons in $m$ modes with $p-l-d$ collisions—essentially the post-
selected portion of the Hilbert space—and the full Hilbert space for $p-l$
photons in $m$ modes. This is expressed as:

$\displaystyle
P_{\text{ps}}(p,d,l,m)=\frac{\binom{m}{d}\cdot\binom{p-l-1}{p-l-d}}{\binom{m+p-l-1}{p-l}.},$
(7)

where $\binom{a}{b}$ represents the binomial coefficient for $a$ and $b$. For
more details, we refer to Appendix B.

###  II.4 Path-encoded boson sampling circuit architectures

Figure 2:  a Illustration of the Clements interferometer architecture, as
detailed in Ref. [45]. Each cross corresponds to an MZI, which can be
constructed from two 50:50 beamsplitters (BSs) and two phase-shifters (PSs). b
Illustration of a rectangular interferometer with a larger number of output
modes than input modes, the latter of which is equal to the number of input
photons. The interferometer can be described by a rectangular matrix, hence
the name. c Illustration of an interferometer with multiple mode-encodings,
i.e. a hybrid mode-encoding. In this case, one mode encoding has spatial modes
separated in the x-direction, while the other has modes separated in the
y-direction.

The physical design of the interferometer architecture depends on the mode
encoding employed. We will first present the architectures for spatial
encoding. While theoretical works typically assume the use of universal
interferometer architectures [8], larger-scale experimental endeavors have so
far featured interferometers constructed from non-universal architectures [25,
30, 4] with lower optical depth. Formally, the complexity arguments from Refs.
[8, 42] are valid only in the universal case, but practically, quantum
advantage experiments are hard to simulate even in nonuniversal cases. To
provide an overview of how the different approaches compare, we will examine
three interferometer architectures: a universal architecture, a fully-
connected architecture with single mode-encoding, and a fully-connected
hybrid-mode-encoded architecture. Here, “fully connected” signifies that all
of the output ports of the interferometer are connected to all of the input
ports, generally resulting in a unitary matrix where all elements are non-
zero, but that in general can be non-universal. In all three cases, the
architectures were chosen to balance the loss per photon to the best possible
degree for all input–output configurations. In the Clements case, and to a
lesser extent the Rectangular case, paths along the edges traverse fewer MZIs.
Since the number of such edge cases is negligible, we assume uniform loss for
all input–output configurations in our analysis.

The universal architecture introduced by Clements et al. [45], which we will
refer to as the ‘Clements’ architecture for simplicity, is constructed from
$m$ columns of MZIs, as shown in Fig. 1a). The interferometer loss in the
Clements architecture is given by $\rho_{\text{int}}=m\cdot\rho_{\text{MZI}}$.
The interferometer loss can be optimized by employing non-universal
architectures. We propose a non-universal ‘Rectangular’ interferometer
architecture (see Fig. 1b), which maintains full connectivity but reduces the
depth $D$. This is achieved by reducing the number of input modes to be equal
to the number of input photons $p$, while maintaining the same number of
output modes $m$. The interferometer consists of an initial section where two
modes are added at the edges of each additional column of MZIs, and a second
section fully connecting every input mode to all output modes. In practice,
the Rectangular architecture is equivalent to starting a Clements architecture
partway in, distributing input modes starting from the middle, and removing
unused MZIs. The interferometer loss, $\rho_{\text{int}}$, given by the number
of MZI columns multiplied by the MZI insertion loss, is
$\big{(}\lceil\frac{m}{2}\rceil+\lceil\frac{p}{2}\rceil-1\big{)}\cdot\rho_{\text{MZI}}$.
Notably, when the number of output modes is much larger than the number of
input modes, i.e. the number of input photons, such that $m\gg p$,
$\rho_{\text{int}}$ is approximately halved compared to the Clements
architecture.

Next, we introduce a ‘hybrid mode interferometer architecture’ inspired by
recent experiments [25, 30, 4]. These interferometers encode modes over
multiple degrees of freedom, e.g. path or polarization, resulting in a hybrid
mode encoding. For instance, one degree of freedom might represent spatial
modes separated in the x-direction, while another represents spatial modes
separated in the y-direction as shown in Fig. 2c). Concatenating fully
connected interferometers in each direction results in an interferometer that
is fully connected across all modes. The power of this approach lies in the
way the number of modes and the depth scale with degrees of freedom. The total
number of modes in the interferometer is equal to the product
$m=\prod_{i}m_{i},$ where $m_{i}$ is the number of modes encoded over the
$i$th degree of freedom. The optical depth, however, is equal to the sum of
individual optical depths
$\rho_{\text{int}}=\sum_{i}D_{i}\cdot\rho_{\text{MZI},i},$ where $D_{i}$ is
the depth for the interferometer connecting all modes for the $i$th degree of
freedom, and $\rho_{\text{MZI},i}$ is the MZI insertion loss for the $i$th
degree of freedom. As an example, if we encode modes over two degrees of
freedom, with $m_{x}=\sqrt{m}$ modes in the $x$ direction and $m_{y}=\sqrt{m}$
modes $y$ direction, the total number of modes remains as $m_{x}\cdot
m_{y}=m$. A fully connected interferometer can then be constructed from
Clements interferometers over the $m_{x}$ modes followed by Clements
interferometers over the $m_{y}$ modes, as illustrated in Fig. 2c). The total
optical depth will then be $D_{x}+D_{y}=m_{x}+m_{y}=2\sqrt{m}$. This approach
allows for efficient scaling of both modes and depth, and it’s worth noting
that the Clements interferometers in each mode encoding can be replaced with
Rectangular interferometers to reduce depth further.

The optical depth scalings for the different architectures can be summarized
as follows

$\displaystyle\rho_{\text{int}}=\Bigg{\\{}\begin{array}[]{lr}m\cdot\rho_{\text{MZI}}&\text{Clements,}\\\
\big{(}\lceil\frac{m}{2}\rceil+\lceil\frac{p}{2}\rceil-1\big{)}\cdot\rho_{\text{MZI}}&\text{Rectangular,}\\\
\sum_{i}D_{i}\cdot\rho_{\text{MZI},i}&\text{Hybrid}.\end{array}$ (11)

###  II.5 Time-bin encoded interferometer architectures

Figure 3:  Illustration of how time-bin interferometers can be constructed to
implement specific features in interferometer architectures. The red bin
symbols $\color[rgb]{1,0,0}{\sqcup}$ correspond to the modes of the
interferometer, and $\tau$ is the temporal separation between photons, which
is equal to the inverse of the SPS emission rate $\tau=r^{-1}_{\text{single-
photon}}$. Numbers correspond to input modes, and numbers with primes
correspond to output modes. All of the time-bin interferometer architectures
make use of reconfigurable MZIs, illustrated as boxed crosses. As is shown in
the bottom-left corner, these MZIs are constructed using time-dependent phase
shifters $\phi(\mathrm{t})$ and $\theta(\mathrm{t})$, which determine the
unitary transformation U(t) effected by the interferometer. a Illustration of
a Rectangular interferometer architecture implemented with spatial modes on
the left-hand side and with a time-bin interferometer on the right-hand side.
The MZI columns are split into three categories $\text{C}_{\text{1}}(m)$,
$\text{C}_{\text{2}}(m)$, and $\text{C}_{\text{3}}(m)$, where $m$ is the
number of modes which is assumed to be an even number. b Upper Illustration of
a specific MZI column for four input modes, $\text{C}_{\text{1}}(4)$. Lower
Operation protocol of the $\text{C}_{\text{1}}(m)$ MZI column for a general
even number of input modes, $m$. c Upper Illustration of a specific MZI column
for four input modes, $\text{C}_{\text{2}}(4)$. Lower Operation protocol of
the $\text{C}_{\text{2}}(m)$ MZI column for a general even number of input
modes, $m$. This type of MZI column increases the total number of modes in the
time-bin interferometer by two. d Upper Illustration of a specific MZI column
for six input modes, $\text{C}_{\text{3}}(6)$. Lower Operation protocol of the
$\text{C}_{\text{3}}(m)$ MZI column for a general even number of input modes,
$m$. In the first and last time-bins, the MZI must be configured to perform
the operation $\text{U}_{\text{swap}}$, which swaps the two input modes. This
ensures that the number of output modes from the column is equal to the number
of input modes $m$.

Time-bin interferometers make use of time-dependent MZIs and fiber delays to
implement multimode interferometers with significantly fewer physical
resources than their spatially encoded counterparts. This is achieved by
reconfiguring each physical MZI to implement a different transformation for
every time-bin. Several interferometer architectures have been proposed and
implemented [37, 38, 47], which differ in the number of spatial modes, and
number of physical interferometers. We will analyze the architecture in Ref.
[38], with one modification – instead of using a single MZI, we employ a
cascaded series of multiple physical MZIs based on the interferometer employed
in Ref. [47]. This choice is due to the lower total propagation loss and
higher input generation rate of cascaded interferometers, as explained in
Appendix C. The multiphoton state input into this time-bin interferometer is
encoded over two spatial modes of the MZI and $m/2$ time-bins. Each physical
MZI in the cascade implements operations equivalent to a column of MZIs in the
Clements or Rectangular interferometer, as illustrated in Fig. 3. The number
of physical MZIs in the cascade then determines the depth $D(m)$ of the
interferometer. In addition, a relative time delay of one time-bin is
introduced between the two output arms of the MZI between each step in the
cascade, which ensures interference between photons in separate time-bins.

Fig. 3 shows how certain spatial interferometers can be converted to time-bin
interferometers. Specifically, we can construct the equivalent of spatial
interferometers by combining three different MZI column types as shown in Fig.
3a). All of the interferometer columns have the exact same construction for
the time-bin interferometer architecture, a time-dependent MZI with a delay in
one of the output modes, with the only difference being the sequence of
transformations. The first MZI column type, labeled $\text{C}_{1}$ interferes
all modes pairwise, starting with the first mode. The time-bin implementation
of $\text{C}_{1}$ increases the total number of time-bins at the output by 1
due to the time delay, where the first mode and last mode will occupy their
own time-bins. The second interferometer column type, $\text{C}_{2}$ differs
from $\text{C}_{1}$ in the nature of the input state, where the first and last
time-bins of the input states are occupied by only one mode, as shown in Fig.
3c). The operation of the MZI on this asymmetric input state results in two
additional modes (time-bins) at the output in addition to the time delay. The
final interferometer column type, $\text{C}_{3}$, takes an input state where
the first and final time-bins are only occupied by one of the modes and enacts
a swap transformation

$\displaystyle\text{U}_{\text{swap}}=\bigg{[}\begin{matrix}0&1\\\
1&0\end{matrix}\bigg{]},$

on the first and last time-bins, as shown in Fig. 3d). This reduces the number
of time bins by one compared to the input state. This type of column
effectively interferes the modes pairwise starting with the second mode, such
that the first and last modes don’t interfere with any other mode.

In order to construct a specific architecture, we only need to identify the
order and type of MZI columns that must be implemented. A Clements
interferometer can be implemented by combining $m/2$ pairs of
$\text{C}_{\text{1}}(m)$ and $\text{C}_{\text{3}}(m)$ columns, such that the
optical depth, i.e. the number of physical MZIs in the interferometer, is $m$.
The Rectangular interferometer consists of a $\text{C}_{\text{1}}(2p)$ column
followed by $(m-2p)/2$ $\text{C}_{\text{2}}(m^{\prime})$ columns where
$m^{\prime}$ is increased from $2p$ at the input of the interferometer to $m$
at the interferometer by increasing the number of modes by 2 for every column.
This is followed by $p-1$ pairs of $\text{C}_{\text{3}}(m)$ and
$\text{C}_{\text{1}}(m)$ columns, resulting in an optical depth of
$(m+2p)/2-1$. Note that we have increased the number of input modes from $p$
in Eq. (11) to $2p$ as one SPS can only populate one of the spatial input
modes as shown in Fig. 1, i.e. half of the input modes of the Rectangular
interferometer.

To account for the effect of delay lines when establishing hardware
requirements for time-bin interferometers, we can adjust the MZI insertion
loss to include the propagation loss of the output with the longest delay

$\displaystyle\rho_{\text{MZI, time-
bin}}=\rho_{\text{MZI}}+\tau\cdot\rho_{\text{prop}}+\rho_{\text{coupling}},$
(12)

where $\tau$ is the separation between time-bins, $\rho_{\text{prop}}$ is the
propagation loss per unit time for the delay lines, and
$\rho_{\text{coupling}}$ is the coupling loss associated with going from one
MZI to the next, i.e. coupling into and out of delay lines.

Lastly, we have to account for the empty time-bins that are required to
implement an interferometer where the number of modes (output modes in the
case of Rectangular interferometers) exceeds $2p$. The interferometer can only
process $m/2$ time-bins at a time, which necessitates a temporal separation of
$m/2$ time-bins between the start of two input states. Therefore, the input
state generation rate, $r_{\text{input}}$, is limited in comparison to the
single-photon generation rate as

$\displaystyle r_{\text{input}}=\frac{2r_{\text{single-photon}}}{m}.$ (13)

##  III System benchmark for implementing the Aaronson–Brod boson sampling
algorithm

Before delving into the component-level hardware benchmarks, we address the
overall system requirements, focusing on the two key system parameters, photon
indistinguishability $x^{2}$ and system loss $\rho_{\textrm{sys}}$. We analyze
the interplay between these two parameters in implementing Aaronson–Brod’s
boson sampling algorithm with lost photons. To provide a practical assessment
of hardware performance, we choose realistic experimental conditions for run
time and error rate of approximate classical algorithms for QA demonstrations
with $p\geq 50$ photons.

We use the coupon collectors problem [48, 26] to estimate the number of
samples required for validation

$r_{\text{sample}}\cdot t_{\text{integration}}\approx m\log(m)/p,$ (14)

where $t_{\text{integration}}$ is the total run time of the boson sampler and
${r_{\text{sample}}\cdot t_{\text{integration}}}$ is the total number of
samples acquired. We set the target for $r_{\text{sample}}$ to be 100 samples
per day, $r_{\text{sample}}=$100/(24\cdot 3600)\text{\,}\mathrm{Hz}$$, which
is in line with the measured $6/3600\text{\,}\mathrm{Hz}$ photon coincidence
rate reported in Ref. [25] that allowed validating the boson sampling
experiment.

We analyze the boson sampling experiment for a deterministic single-photon
source at the input that emits photons at a rate of 1 GHz. We consider both
the case with a demultiplexer and a spatially encoded interferometer as well
as the case with a time-bin interferometer. In the former, the $p$ photon
input state is generated at a rate of $r_{\text{input,
spatial}}=1/p$\text{\,}\mathrm{GHz}$$. In the latter, the input state
containing $M/2$ time-bins is generated at a rate of $r_{\text{input, time-
bin}}=2/m$\text{\,}\mathrm{GHz}$$. We consider two circuit architectures of
the interferometer: one with a quadratic number of modes $m=(p-l)^{2}$ and
another with a linear number of modes $m=10\cdot(p-l)$, as detailed in Sec.
II.A and II.C, respectively. By comparing the two cases we can examine the
influence of mode scaling on the trade-off between photon indistinguishability
and system loss tolerance. We combine Eq. (1) with Eq. (4) (Eq. (6))for the
quadratic (linear) case, to find the level of loss that results in an
$r_{\text{sample}}$ of 100 samples per day.

We choose an error rate of $E\leq 0.01$, given by Eq. (5), for approximating
the noisy boson sampling output using classically computed permanents of order
$k=49$. We plot this relation for a varying number of detected photons
$(p-l)$, where the number of lost photons $l$ has been set as high as possible
while keeping the error of the approximation below the threshold of $E\leq
0.01$.

Figure 4:  Maximum per-photon loss for the full circuit to perform boson
sampling in the QA regime versus degree of indistinguishability and number of
detected photons and for different values $l$ of lost or colliding photons.
The two upper plots are for the case where the number of modes scales
quadratically with the number of photons $m=(p-l)^{2}$, and the two bottom
plots are for the case where the number of modes scales linearly with the
number of photons $m=10\cdot(p-l)$. The two plots to the left are for spatial
interferometers with a demultiplexed source, whereas the two plots on the
right are for time-bin interferometers. White contours indicate the added
number of lost photons $l$, which increases with the indistinguishability, and
detected number of photons.

Results for mode scalings $m=(p-l)^{2}$ and $m=10\cdot(p-l)$ are shown in the
upper and lower rows of Fig. 4, respectively. The lowest indistinguishability
$x^{2}\approx 0.805$, found by setting $l=0$ and $p=50$ in Eq. (5),
corresponds to the maximal per-photon loss for Aaronson–Arkhipov boson
sampling, i.e. with no photon loss or collisions. Increasing the photon
indistinguishability allows for a higher number of lost photons with
Aaronson–Brod sampling, increasing the per-photon loss that can be tolerated.
We find that $>$ 3 dB (i.e. $50\%$) loss tolerance for realistic degrees of
indistinguishability of quantum dot SPSs [36] for all four cases. We find the
highest maximal loss values at an indistinguishability of $x^{2}=0.98$ to be,
from highest to lowest: $3.78\text{\,}\mathrm{dB}$ for the quadratic spatial
case, $3.46\text{\,}\mathrm{dB}$ for the quadratic time-bin case,
$3.35\text{\,}\mathrm{dB}$ for the linear spatial case, and
$3.20\text{\,}\mathrm{dB}$ for the linear time-bin case. For comparison, in
the limit of perfect indistinguishability, $x^{2}=1$ where up to $l=12$
photons can be lost with 50 detected photons, the highest maximal loss values
would be $3.96\text{\,}\mathrm{dB}$ for the quadratic spatial case,
$3.65\text{\,}\mathrm{dB}$ for the quadratic time-bin case,
$3.53\text{\,}\mathrm{dB}$ for the linear spatial case, and
$3.39\text{\,}\mathrm{dB}$ for the linear time-bin case.

As the number of detected photons increases the total loss of the system
typically increases, leading to a decreased maximum per-photon loss. However,
for a fixed degree of indistinguishability, gradually increasing the number of
detected photons can lead to abrupt changes when an additional lost photon can
be tolerated according to Eq. (5). Thus, the optimum number of lost photons
and the detected photons will both depend on the exact photon
indistinguishability in the experiment.

In comparing the different plots it is evident that quadratic mode scalings
and spatial interferometers lead to higher overall loss tolerance compared to
the linear mode scaling and time-bin interferometers. The advantage of
quadratic mode scaling can be attributed to the added effective post-selection
loss associated with linear mode-scaling, described by Eq. (7). Specifically,
the average difference between quadratic and linear mode scalings is
$0.430\text{\,}\mathrm{dB}$ for spatial interferometers and
$0.277\text{\,}\mathrm{dB}$ for time-bin interferometers, in favor of
quadratic interferometers. The advantage of spatial interferometers can be
attributed to the lower input state generation rate for time-bin
interferometers. The average difference between spatial and time-bin
interferometers is $0.298\text{\,}\mathrm{dB}$ for a quadratic number of modes
and $0.145\text{\,}\mathrm{dB}$ for a linear number of modes, both in favor of
spatial interferometers.

Although quadratic mode-scalings allow for higher per-photon loss, the
interferometers consist of more MZIs. As such, there is a trade-off between
lower effective post-selection loss for quadratic interferometers and lower
interferometer loss for linear mode scalings where the MZI insertion loss
determines which mode scaling is favored.

Time-bin interferometers have a similar trade-off, as they have a lower
maximal per-photon loss due to the lower input state generation rate, but do
not require the use of a demultiplexer. However, a demultiplexer can be
constructed from the same MZIs that are used to construct a time-bin
interferometer, and as such, this trade-off can also be quantified in terms of
MZI insertion loss. Specifically, a demultiplexer has an optical depth of
$\lceil\log_{2}(p)\rceil=6$, where the equality holds for the optimal number
of detected and lost photons for all indistinguishabilities considered in Fig.
4. The demultiplexer also involves a delay on all except the last photon,
where the first photon has to go through the longest delay of $(p-1)$ time-
bins. As for the time-bin interferometer, all of the $D(m)$ MZIs in the
interferometer will in the worst case include one time-bin of delay which is
not present in the spatial case. If we compare the added per-photon loss from
the demultiplexer in the spatial case with the added delay and lower maximum
per-photon loss in the time-bin case, we can find the following inequality for
the regime where time-bin interferometers are less favorable implementations
than spatial interferometers:

$\displaystyle\begin{split}6\cdot\rho_{\text{MZI}}+(p-1)\rho_{\text{prop}}&\leq(D(m)-1)\rho_{\text{prop}}+\Delta,\\\
\Delta=\rho_{\text{sys, spatial}}&-\rho_{\text{sys, time-bin}}.\end{split}$
(15)

The average of the value for $\Delta$, i.e. the difference between maximal
per-photon loss for spatial and time-bin interferometers, was found to be
$0.145\text{\,}\mathrm{dB}$ for the case where $m=10(p-l)$ and
$0.298\text{\,}\mathrm{dB}$ for the case where $m=(p-l)^{2}$. If we neglect
propagation loss, $\rho_{\text{prop}}=0$, and insert the average values we can
estimate this inequality in the two cases considered in Fig. 4:

$\displaystyle\begin{split}\rho_{\text{MZI}}&\leq$0.05\text{\,}\mathrm{dB}$\quad
m=(p-l)^{2},\\\ \rho_{\text{MZI}}&\leq$0.024\text{\,}\mathrm{dB}$\quad
m=10\cdot(p-l).\end{split}$ (16)

In practice, coupling into the delay between MZIs will inevitably incur loss,
and as such, these inequalities present a best-case scenario in favor of time-
bin interferometers.

##  IV Benchmarking hardware requirements

The requirements on component losses for a given interferometer architecture
can be found by combining Eqs. (3), (11), with either Eq. (4) or Eq. (6). To
simplify the analysis, we note that only the interferometer loss scales with
the number of modes, and separate the losses into the interferometer loss,
$\rho_{\text{int}}$, and the remaining system loss,
$\rho_{\text{sys}}-\rho_{\text{int}}=\rho_{\text{sps}}+\rho_{\text{dmx}}+\rho_{\text{coupling}}$.
We fix the degree of indistinguishability to $x^{2}=0.96$, which is readily
achievable with present-day quantum dot single-photon sources [49], while
routes to achieve even higher values have been laid out [50]. This allows us
to fix the number of input photons to $p=59$ with up to $l=9$ lost photons in
accordance with Eq. (5). We also consider the requirements for
Aaronson–Arkhipov sampling where we post-select on detecting the same number
of photons as are sent into the interferometer, i.e. fixing the number of
input and output photons to $p=50$. The hardware requirements on the
interferometer can be formulated as specific requirements on the MZI insertion
loss by specifying the architecture and number of modes used for the
interferometer.

Figure 5: Plot of the requirements on MZI insertion loss (x-axis) and
$\rho_{\text{sys}}-\rho_{\text{int}}$ (y-axis) with photon
indistinguishability set to $x^{2}=0.96$. The upper plots show the
requirements for Aaronson–Brod boson sampling, where the input state consists
of $59$ photons with the outputs post-selected to contain $50$ photon
detection events. The lower plots show the requirements for Aaronson–Arkhipov
boson sampling, where we send in $50$ photons and detect $50$ photons, not
allowing for photon loss or collisions. The first, second, and third column
shows hardware requirements for setups where the interferometers are
constructed according to the Clements architecture, the Rectangular
architecture, and a set of Hybrid architectures, respectively. For the
Clements and Rectangular architectures, the solid lines correspond to the
requirements for spatially encoded architectures, whereas dashed lines
correspond to the requirements for time-bin architectures. For the Hybrid
architectures, the solid lines correspond to requirements for an
interferometer encoded over two spatial mode-encodings, whereas dashed lines
correspond to requirements for an interferometer encoded over time-bins and
two spatial mode encodings. The dotted vertical lines mark the estimated MZI
loss for a state-of-the-art experimental realization with static,
nonprogrammable MZIs [25]. The dash-dotted vertical line in the plots for
Hybrid interferometers marks the estimated MZI loss for a state-of-the-art
experimental realization with programmable MZIs [51].

Single mode-encoding: The first two columns of Fig. 5 show the requirements
for three different choices of mode scaling for both Clements and Rectangular
interferometer architectures, where the top figures show requirements for
Aaronson–Brod [42] boson sampling, and the bottom figures show requirements
for Aaronson–Arkhipov boson sampling [8], i.e. with post-selection on the same
number of detected photons as input photons. The figures include a vertical
dotted line corresponding to the state-of-the-art insertion loss for a static
MZI, estimated to be
$-10\cdot\log_{10}(0.987)/(10+6)\>$\text{\,}\mathrm{dB}$\approx$0.0035\text{\,}\mathrm{dB}$$,
which is the overall interferometer efficiency in Ref. [25] divided by the
number of MZIs corresponding to the optical depth of a 10-mode interferometer
followed by a 6-mode interferometer.

Comparing the requirements on MZI insertion loss with the Eqs. (16), we find
that we are in the regime where demultiplexing and spatial mode encoded
interferometers are favorable in terms of loss even with access to the rapidly
reprogrammable MZIs required to construct a time-bin interferometer.

As seen from the figure, a QA demonstration using single-mode-encoding
architectures would be within reach if one could use interferometers with
state-of-the-art efficiency in conjunction with a source and detection
efficiency of around $P_{\text{sps}}\cdot P_{\text{dmx}}\cdot
P_{\text{coupling}}\cdot P_{\text{det}}\geq 0.65$. This overall efficiency is
currently beyond the state-of-the-art values reported with quantum dot
sources[6, 25, 52, 53], see Table 1 for an overview of parameters already
reported in the literature. Further expected near-term improvements of the
approach is also listed in the table, indicating that explicit QA
demonstration with single-mode encoding is not far outside reach.

Reference | $P_{\text{sps}}$ | $P_{\text{coupling}}$ |  $P_{\text{dmx}}$ ($p$) | $P_{\text{det}}$ | Total efficiency | $x^{2}$
---|---|---|---|---|---|---
Current best | 0.658 [52] | 0.902 [25] | 0.83 (20) [25] | 0.95 [4] | 0.47 | 0.964 [49]
Near-term estimated best | 0.78 [26] | 0.902 [25] | 0.92 [26] | 0.95 [6] | 0.615 | 0.985 [49, 54]
Table 1: Table of state-of-the-art system efficiencies. In the column for
demultiplexer efficiency, the number of modes of the demultiplexer employed is
indicated in parentheses. For the current best indistinguishability, we have
used the measured photon indistinguishability, whereas for the near-term
estimated best we have used the estimated intrinsic photon
indistinguishability which has been corrected for experimental imperfections.

Hybrid mode encoding: Hybrid encoding schemes make the algorithms more robust
to optical loss and hence put QA demonstrations within closer reach. We
consider two distinct Hybrid architectures, one with two spatial mode
encodings, like the one employed in Refs. [25, 30] and illustrated in Fig.
2c), and one with two spatial mode encodings and one time-bin encoding. For
the former, the number of modes in each encoding was chosen to optimize the
optical depth, as described by Eq. (11). This optimization procedure allowed
for the total number of modes to be slightly increased if it led to favorable
optical depth. Rectangular interferometers were employed in each mode encoding
to minimize depth. For the latter encoding, we considered an architecture
where the input state is partially demultiplexed, whereby sets of two spatial
modes are inserted into a time-bin interferometer. By ensuring that there are
no empty time-bins in the time-bin interferometer, we avoid the issue of a
lowered input state generation rate for time-bin interferometers. The output
modes of the time-bin interferometers are then sent into a two-spatial-mode-
encoding Hybrid interferometer employing Rectangular interferometers across
the two spatial encodings. The total optical depth of this interferometer,
including the initial demultiplexer is equal to:

$\displaystyle
D(n,p,m_{1},m_{2})=n+2\lceil\frac{p}{2^{n}}\rceil+\lceil\frac{m_{1}}{2}\rceil+\lceil\frac{m_{2}}{2}\rceil+\frac{2^{n}}{2},$
(17)

where $n$ is the depth of the demultiplexer, such that there are $2^{n}$
spatial modes and $\lceil\frac{p}{2^{n}}\rceil$ time-bins after the
demultiplexer, and where $m_{1}$ and $m_{2}$ correspond to the number of
output modes in each spatial encoding. Similarly to the case of the spatial
hybrid interferometer, we allow for the number of modes to be increased if it
leads to a lower optical depth, only requiring that

$\displaystyle m_{1}\cdot m_{2}\cdot\lceil\frac{p}{2^{n}}\rceil\geq m,$

where the left-hand side is the actual number of modes, and the right-hand
side is the target number of modes, calculated from the mode scaling. The
depth of the demultiplexer and the number of spatial modes were optimized in
order to minimize Eq. (17). For the case of a quadratic number of time-bins,
the ideal demultiplexer depth was found to be $n=3$, with $m_{1}=m_{2}=18$,
whereas for the linear mode scalings, the ideal demultiplexer depth was found
to be $n=4$ with the number of spatial modes equal to $m_{1}=11,\;m_{2}=12$
and $m_{1}=8,\;m_{2}=9$ for the case where $m=10(p-l)$ and $m=5(p-l)$,
respectively.

The resulting hardware requirements for Aaronson–Brod (Aaronson–Arkhipov)
boson sampling are shown in the top (bottom) plot of the right column of Fig.
5, where the solid lines (‘Spatial’) refer to the case with two spatial mode
encodings, and the dashed lines (‘Time-bin’) refer to the case with time-bin
and two spatial encodings. In addition to the dashed line for the state-of-
the-art static MZI insertion loss, the plots include a dashed-dotted line
marking the state-of-the-art insertion loss for a reconfigurable MZI,
estimated from Ref. [51] to be
$$1.1\text{\,}\mathrm{dB}$/20=$0.055\text{\,}\mathrm{dB}$$, which is the
interferometer insertion loss divided by the number of MZIs.

The hybrid encoding with the time-bin encoding performs better at larger mode-
scalings but seems to perform comparably or slightly worse for the case where
$m=5(p-l)$. The advantage at higher mode-scalings comes from the fact that the
number of modes is distributed over three encodings, which means that the sum
of the number of modes can be smaller. This is less of an advantage for the
case where $m=5(p-l)$, where the additional demultiplexer loss included in the
time-bin case gives a higher overall depth. It should be noted that the
spatial hybrid interferometer requires the addition of a demultiplexer at a
depth of $n=\lceil\log_{2}(p)\rceil$, which should be included as part of the
source efficiency. As such, the time-bin hybrid interferometer would be
expected to perform advantageously even for low mode-scaling.

Figure 5 clearly shows that the MZI insertion loss determines whether a
quadratic mode scaling or linear mode scaling is favorable. Specifically, at
the state-of-the-art static MZI insertion loss, employing an interferometer
with a quadratic mode-scaling is best, whereas linear mode scalings are
favored when using MZIs with the state-of-the-art reconfigurable MZI insertion
loss. This is not the case for Clements or Rectangular architectures except
for the case where the MZI insertion loss is vanishingly low. The discrepancy
between the Clements and Rectangular architectures and the Hybrid architecture
is attributed to how the optical depth scales with the number of modes, as
shown in Eq. (11). With modes distributed across two mode-encodings, the
optical depth of Hybrid interferometers scales with $\sim\sqrt{m}$, as opposed
to linearly in $m$. As increasing the number of modes has a smaller impact on
interferometer loss, the added effective post-selection loss associated with
linear mode-scalings has a proportionally higher impact on the system loss for
hybrid interferometers.

##  V Hardware requirements for near-term QA demonstrations

From Fig. 5 it is observed that an explicit QA demonstration is within reach
with a deterministic quantum dot source. Indeed using state-of-the-art static
interferometers would imply that QA is reached for $P_{\text{sps}}\cdot
P_{\text{dmx}}\cdot P_{\text{coupling}}\cdot P_{\text{det}}\geq 0.45$, where
the required efficiency of each sub-component was already realized
experimentally, see Table 1. As time-bin interferometers require the use of
reprogrammable MZIs, one could not make use of hybrid architectures with time-
bin encoding in this case. As for state-of-the-art reconfigurable
interferometers, this would require a setup with combined source and detection
efficiencies around $0.65$ ($0.7$) for the time-bin (spatial) Hybrid
architectures. These values are reachable with the estimated near-term values
of the approach, cf. Table 1. It is important to note that the state-of-the-
art values of MZIs hold for thermo-optic phase-shifters, which are unsuitable
for realizing time-bin interferometers due to their slow response time.
Consequently, this would limit the present implementations of Hybrid time-bin
architectures. On the other hand, Hybrid interferometers with spatial mode
encodings appear to be promising candidates for near-term QA demonstrations
with quantum dot single-photon sources.

It is clear from Table 1 that the source efficiency is the main bottleneck in
realizing a demonstration of QA. In the following, we restrict the focus to
the exact requirements for the single-photon source by fixing other losses to
state-of-the-art values. We fix the MZI insertion loss to the state-of-the-art
value for static MZIs shown in Fig. 5. The demultiplexer efficiency and
coupling losses are fixed to realistic parameters extrapolated from Refs. [30,
26]:

$\displaystyle\rho_{\text{dmx}}$
$\displaystyle=\frac{0.458}{5}\lceil\log_{2}(p)\rceil$\text{\,}\mathrm{dB}$,$
$\displaystyle\rho_{\text{coupling}}$
$\displaystyle=$0.458\text{\,}\mathrm{dB}$.$

Figure 6: Requirements on source efficiency for a given indistinguishability
with a hybrid interferometer encoded in two mode-encodings as per Fig. 1d).
Rectangular interferometers have been used within both mode encodings. The
requirements are defined to allow for 100 samples to be obtained per day with
a 1 GHz single-photon generation rate. For each value of indistinguishability,
the number of photons detected and lost has been optimized to increase the
loss tolerance while maintaining an error bound higher than 1% for the
approximation algorithm. a) Quadratic mode scaling b) Linear mode scaling

We examine how the requirements on the source efficiency change as a function
of the photon indistinguishability. The resulting curves for quadratic and
linear mode-scalings are shown in Fig. 6. It is clear from the figure that
quadratic mode-scaling is favored regardless of photon indistinguishability.
For realistic photon indistinguishability, $x^{2}\geq 0.96$, the results show
that a QA demonstration is within reach for single-photon source efficiencies
greater than $0.6$, which has been demonstrated experimentally [52]. The
challenge will be to construct a demultiplexer and an interferometer that are
sufficiently large while maintaining sufficiently low loss, and connecting
them to an exceedingly large number of low-loss detectors.

##  VI Conclusion

In conclusion, we have presented an in-depth analysis of the hardware
requirements for realizing boson-sampling in the QA regime with deterministic
single-photon sources, notably quantum dots in nanophotonic cavities and
waveguides. The estimated benchmarks provide precise requirements on optical
circuits and single-photon sources that must be reached, thereby offering a
roadmap for future engineering efforts to realize that goal. Our analysis
elucidates the precise advantages and disadvantages of strategies that are
commonly employed in experiments to lower hardware requirements, such as
making use of specialized interferometer architectures and employing
interferometers with linear mode scaling. We have identified interferometers
with hybrid mode encoding and quadratic mode scaling as a key strategy to
demonstrating QA, an approach that has yet to see realization in experiments.
Specifically, we have shown that a QA experiment based on single-photon boson
sampling is within reach of current state-of-the-art hardware, provided that
one can reach source efficiencies as high as 60%-70%.

In examining the requirements for time-bin encoded interferometers, we have
found time-bin interferometers utilizing the Clements and Rectangular
architectures to be inferior to equivalent spatial interferometers for QA
demonstrations. This is due to the disadvantages associated with empty time-
bins in the input state in the regime where MZI insertion loss is low enough
for a QA demonstration to be feasible. For hybrid interferometer
architectures, however, encoding a subset of the modes in time-bins leads to
improved hardware requirements on MZI insertion loss. As such, developing
rapidly reconfigurable photonic integrated circuits with bandwidth to support
time-bin-compatible MZIs with sufficiently low loss is a promising direction
to enable QA demonstrations.

Our analysis has focused on the requirements of the interferometers and
single-photon sources, however, an underlying assumption for parts of the
analysis was that the loss associated with coupling photons from the source
and into the interferometer were comparable with the losses quoted in Refs.
[25, 30]. Achieving ultra-low-loss chip-to-fiber coupling is an important
engineering challenge and an area of active research [55, 56, 57]. Ultimately
coupling losses could be further mitigated by a partial or full-scale system
integration, whereby sources, demultiplexer, interferometers, and detectors
would be combined in a single device [18], which constitutes an important
future research direction.

## References

  * Preskill [2012] J. Preskill, Quantum computing and the entanglement frontier, arXiv preprint arXiv:1203.5813 (2012).
  * Preskill [2018] J. Preskill, Quantum computing in the nisq era and beyond, Quantum 2, 79 (2018).
  * Boixo  _et al._ [2018] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Characterizing quantum supremacy in near-term devices, Nature Physics 14, 595 (2018).
  * Madsen  _et al._ [2022] L. S. Madsen, F. Laudenbach, M. F. Askarani, F. Rortais, T. Vincent, J. F. Bulmer, F. M. Miatto, L. Neuhaus, L. G. Helt, M. J. Collins, _et al._ , Quantum computational advantage with a programmable photonic processor, Nature 606, 75 (2022).
  * Morvan  _et al._ [2023] A. Morvan, B. Villalonga, X. Mi, S. Mandrà, A. Bengtsson, P. Klimov, Z. Chen, S. Hong, C. Erickson, I. Drozdov, _et al._ , Phase transition in random circuit sampling, arXiv preprint arXiv:2304.11119 (2023).
  * Maring  _et al._ [2023] N. Maring, A. Fyrillas, M. Pont, E. Ivanov, P. Stepanov, N. Margaria, W. Hease, A. Pishchagin, T. H. Au, S. Boissier, _et al._ , A general-purpose single-photon-based quantum computing platform (2023), arXiv:2306.00874 [quant-ph] .
  * Quantum  _et al._ [2020] G. A. Quantum, Collaborators*†, F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, S. Boixo, M. Broughton, B. B. Buckley, _et al._ , Hartree-fock on a superconducting qubit quantum computer, Science 369, 1084 (2020).
  * Aaronson and Arkhipov [2011] S. Aaronson and A. Arkhipov, The computational complexity of linear optics, in  _Proceedings of the forty-third annual ACM symposium on Theory of computing_ (2011) pp. 333–342.
  * Hamilton  _et al._ [2017] C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, Gaussian boson sampling, Physical review letters 119, 170501 (2017).
  * Bartolucci  _et al._ [2023] S. Bartolucci, P. Birchall, H. Bombin, H. Cable, C. Dawson, M. Gimeno-Segovia, E. Johnston, K. Kieling, N. Nickerson, M. Pant, _et al._ , Fusion-based quantum computation, Nature Communications 14, 912 (2023).
  * Paesani and Brown [2023] S. Paesani and B. J. Brown, High-threshold quantum computing by fusing one-dimensional cluster states, Phys. Rev. Lett. 131, 120603 (2023).
  * Valiant [1979] L. G. Valiant, The complexity of computing the permanent, Theoretical computer science 8, 189 (1979).
  * Scheel [2004] S. Scheel, Permanents in linear optical networks, arXiv preprint arXiv:quantph/0406127 (2004).
  * Brod  _et al._ [2019] D. J. Brod, E. F. Galvão, A. Crespi, R. Osellame, N. Spagnolo, and F. Sciarrino, Photonic implementation of boson sampling: a review, Advanced Photonics 1, 034001 (2019).
  * Renema  _et al._ [2018a] J. Renema, V. Shchesnovich, and R. Garcia-Patron, Classical simulability of noisy boson sampling, arXiv preprint arXiv:1809.01953 (2018a).
  * Renema  _et al._ [2018b] J. J. Renema, A. Menssen, W. R. Clements, G. Triginer, W. S. Kolthammer, and I. A. Walmsley, Efficient classical algorithm for boson sampling with partially distinguishable photons, Physical review letters 120, 220502 (2018b).
  * Elshaari  _et al._ [2020] A. W. Elshaari, W. Pernice, K. Srinivasan, O. Benson, and V. Zwiller, Hybrid integrated quantum photonic circuits, Nat. Photon. 14, 285 (2020).
  * Uppu  _et al._ [2021] R. Uppu, L. Midolo, X. Zhou, J. Carolan, and P. Lodahl, Quantum-dot-based deterministic photon–emitter interfaces for scalable photonic quantum technology, Nat. Nanotechnol. 16, 1308 (2021).
  * Pelucchi  _et al._ [2021] E. Pelucchi, G. Fagas, I. Aharonovich, D. Englund, E. Figueroa, Q. Gong, H. Hannes, J. Liu, C.-Y. Lu, N. Matsuda, _et al._ , The potential and global outlook of integrated photonics for quantum technologies, Nat. Rev. Phys. 4, 194 (2021).
  * Moody  _et al._ [2022] G. Moody, V. J. Sorger, D. J. Blumenthal, P. W. Juodawlkis, W. Loh, C. Sorace-Agaskar, A. E. Jones, K. C. Balram, J. C. F. Matthews, A. Laing, _et al._ , 2022 Roadmap on integrated quantum photonics, J. Phys. Photonics 4, 012501 (2022).
  * Broome  _et al._ [2013] M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White, Photonic boson sampling in a tunable circuit, Science 339, 794 (2013).
  * Spring  _et al._ [2013] J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X.-M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, _et al._ , Boson sampling on a photonic chip, Science 339, 798 (2013).
  * Crespi  _et al._ [2013] A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, Integrated multimode interferometers with arbitrary designs for photonic boson sampling, Nature photonics 7, 545 (2013).
  * Tillmann  _et al._ [2013] M. Tillmann, B. Dakić, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, Experimental boson sampling, Nature photonics 7, 540 (2013).
  * Wang  _et al._ [2019] H. Wang, J. Qin, X. Ding, M.-C. Chen, S. Chen, X. You, Y.-M. He, X. Jiang, L. You, Z. Wang, _et al._ , Boson sampling with 20 input photons and a 60-mode interferometer in a $10^{14}$-dimensional hilbert space, Physical review letters 123, 250503 (2019).
  * Uppu  _et al._ [2020] R. Uppu, F. T. Pedersen, Y. Wang, C. T. Olesen, C. Papon, X. Zhou, L. Midolo, S. Scholz, A. D. Wieck, A. Ludwig, and P. Lodahl, Scalable integrated single-photon source, Science advances 6, eabc8268 (2020).
  * Tomm  _et al._ [2021] N. Tomm, A. Javadi, N. O. Antoniadis, D. Najer, M. C. Löbl, A. R. Korsch, R. Schott, S. R. Valentin, A. D. Wieck, A. Ludwig, _et al._ , A bright and fast source of coherent single photons, Nat. Nanotechnol. 16, 399 (2021).
  * Stojanović  _et al._ [2018] V. Stojanović, R. J. Ram, M. Popović, S. Lin, S. Moazeni, M. Wade, C. Sun, L. Alloatti, A. Atabaki, F. Pavanello, _et al._ , Monolithic silicon-photonic platforms in state-of-the-art cmos soi processes, Optics express 26, 13106 (2018).
  * Bao  _et al._ [2023] J. Bao, Z. Fu, T. Pramanik, J. Mao, Y. Chi, Y. Cao, C. Zhai, Y. Mao, T. Dai, X. Chen, _et al._ , Very-large-scale integrated quantum graph photonics, Nature Photonics , 1 (2023).
  * Zhong  _et al._ [2020] H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, _et al._ , Quantum computational advantage using photons, Science 370, 1460 (2020).
  * Arkhipov and Kuperberg [2012] A. Arkhipov and G. Kuperberg, The bosonic birthday paradox, Geometry & Topology Monographs 18, 10 (2012).
  * Bulmer  _et al._ [2022] J. F. F. Bulmer, S. Paesani, R. S. Chadwick, and N. Quesada, Threshold detection statistics of bosonic states, Phys. Rev. A 106, 043712 (2022).
  * Hong  _et al._ [1987] C.-K. Hong, Z.-Y. Ou, and L. Mandel, Measurement of subpicosecond time intervals between two photons by interference, Physical review letters 59, 2044 (1987).
  * Migdall  _et al._ [2002] A. L. Migdall, D. Branning, and S. Castelletto, Tailoring single-photon and multiphoton probabilities of a single-photon on-demand source, Physical Review A 66, 053805 (2002).
  * Bartolucci  _et al._ [2021] S. Bartolucci, P. Birchall, D. Bonneau, H. Cable, M. Gimeno-Segovia, K. Kieling, N. Nickerson, T. Rudolph, and C. Sparrow, Switch networks for photonic fusion-based quantum computing (2021), arXiv:2109.13760 [quant-ph] .
  * Lodahl  _et al._ [2022] P. Lodahl, A. Ludwig, and R. J. Warburton, A deterministic source of, Physics Today 75, 3 (2022).
  * Motes  _et al._ [2014] K. R. Motes, A. Gilchrist, J. P. Dowling, and P. P. Rohde, Scalable boson sampling with time-bin encoding using a loop-based architecture, Physical review letters 113, 120501 (2014).
  * He  _et al._ [2017] Y. He, X. Ding, Z.-E. Su, H.-L. Huang, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y.-M. He, _et al._ , Time-bin-encoded boson sampling with a single-photon device, Physical review letters 118, 190501 (2017).
  * Hummel  _et al._ [2019] T. Hummel, C. Ouellet-Plamondon, E. Ugur, I. Kulkova, T. Lund-Hansen, M. A. Broome, R. Uppu, and P. Lodahl, Efficient demultiplexed single-photon source with a quantum dot coupled to a nanophotonic waveguide, Applied Physics Letters 115, 021102 (2019).
  * Zhai  _et al._ [2022] L. Zhai, G. N. Nguyen, C. Spinnler, J. Ritzmann, M. C. Löbl, A. D. Wieck, A. Ludwig, A. Javadi, and R. J. Warburton, Quantum interference of identical photons from remote gaas quantum dots, Nature Nanotechnology 17, 829 (2022).
  * Papon  _et al._ [2022] C. Papon, Y. Wang, R. Uppu, S. Scholz, A. D. Wieck, A. Ludwig, P. Lodahl, and L. Midolo, Independent operation of two waveguide-integrated single-photon sources (2022), arXiv:2210.09826 [quant-ph] .
  * Aaronson and Brod [2016] S. Aaronson and D. J. Brod, Bosonsampling with lost photons, Physical Review A 93, 012335 (2016).
  * Carolan  _et al._ [2015] J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, _et al._ , Universal linear optics, Science 349, 711 (2015).
  * Reck  _et al._ [1994] M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani, Experimental realization of any discrete unitary operator, Physical review letters 73, 58 (1994).
  * Clements  _et al._ [2016] W. R. Clements, P. C. Humphreys, B. J. Metcalf, W. S. Kolthammer, and I. A. Walmsley, Optimal design for universal multiport interferometers, Optica 3, 1460 (2016).
  * Chin and Huh [2018] S. Chin and J. Huh, Generalized concurrence in boson sampling, Scientific reports 8, 6101 (2018).
  * Qi  _et al._ [2018] H. Qi, L. G. Helt, D. Su, Z. Vernon, and K. Brádler, Linear multiport photonic interferometers: loss analysis of temporally-encoded architectures, arXiv preprint arXiv:1812.07015 https://doi.org/10.48550/arXiv.1812.07015 (2018).
  * Ferrante and Frigo [2012] M. Ferrante and N. Frigo, A note on the coupon-collector’s problem with multiple arrivals and the random sampling, arXiv preprint arXiv:1209.2667 (2012).
  * Ding  _et al._ [2016] X. Ding, Y. He, Z.-C. Duan, N. Gregersen, M.-C. Chen, S. Unsleber, S. Maier, C. Schneider, M. Kamp, S. Höfling, _et al._ , On-demand single photons with high extraction efficiency and near-unity indistinguishability from a resonantly driven quantum dot in a micropillar, Physical review letters 116, 020401 (2016).
  * Dreeßen  _et al._ [2018] C. L. Dreeßen, C. Ouellet-Plamondon, P. Tighineanu, X. Zhou, L. Midolo, A. S. Sørensen, and P. Lodahl, Suppressing phonon decoherence of high performance single-photon sources in nanophotonic waveguides, Quantum Science and Technology 4, 015003 (2018).
  * Taballione  _et al._ [2023] C. Taballione, M. C. Anguita, M. de Goede, P. Venderbosch, B. Kassenberg, H. Snijders, N. Kannan, W. L. Vleeshouwers, D. Smith, J. P. Epping, _et al._ , 20-mode universal quantum photonic processor, Quantum 7, 1071 (2023).
  * Chen  _et al._ [2023] S. Chen, L.-C. Peng, Y.-P. Guo, X.-M. Gu, X. Ding, R.-Z. Liu, X. You, J. Qin, Y.-F. Wang, Y.-M. He, J. J. Renema, Y.-H. Huo, H. Wang, C.-Y. Lu, and J.-W. Pan, Heralded three-photon entanglement from a single-photon source on a photonic chip (2023), arXiv:2307.02189 [quant-ph] .
  * Wang  _et al._ [2023] Y. Wang, C. F. D. Faurby, F. Ruf, P. I. Sund, K. H. Nielsen, N. Volet, M. J. R. Heck, N. Bart, A. D. Wieck, A. Ludwig, L. Midolo, S. Paesani, and P. Lodahl, Deterministic photon source interfaced with a programmable silicon-nitride integrated circuit (2023), arXiv:2302.06282 [quant-ph] .
  * Pedersen [2020] F. T. Pedersen,  _Deterministic Single and Multi-Photon Sources with Quantum dots in Planar Nanostructures_ , Phd thesis, University of Copenhagen (2020).
  * Tiecke  _et al._ [2015] T. Tiecke, K. Nayak, J. D. Thompson, T. Peyronel, N. P. de Leon, V. Vuletić, and M. Lukin, Efficient fiber-optical interface for nanophotonic devices, Optica 2, 70 (2015).
  * Notaros  _et al._ [2016] J. Notaros, F. Pavanello, M. T. Wade, C. M. Gentry, A. Atabaki, L. Alloatti, R. J. Ram, and M. A. Popović, Ultra-efficient cmos fiber-to-chip grating couplers, in  _2016 Optical Fiber Communications Conference and Exhibition (OFC)_ (IEEE, 2016) pp. 1–3.
  * Marchetti  _et al._ [2019] R. Marchetti, C. Lacava, L. Carroll, K. Gradkowski, and P. Minzioni, Coupling strategies for silicon photonics integrated chips, Photonics Research 7, 201 (2019).

##  Appendix A On the computational complexity of boson sampling with
collisions

Here we will evaluate the computational complexity of boson sampling with
collisions, which is relevant in the case of boson sampling with added lost
photons where photon collisions and photon loss are indistinguishable due to
the use of threshold detectors. To do so, we employ the approach used in Ref.
[46] which we summarize below. In this approach, the minimal computation time
$\mathcal{T}_{\text{min}}(\vec{n},\vec{m})$ is given as a function of the
input state $\vec{n}$ and output state $\vec{m}$ in the Fock basis, where a
state is defined as

$\displaystyle\vec{n}=(n_{1},n_{2},...,n_{M}),\quad\sum_{i}n_{i}=N$ (18)

where $n_{i}$ is the number of photons in the $i$th mode, $M$ is the total
number of modes, and $N$ is the total number of photons.

The minimal computation time, $\mathcal{T}_{\text{min}}(\vec{n},\vec{m})$ with
input state $\vec{n}$ and output state $\vec{m}$ is found to be

$\displaystyle\mathcal{T}_{\text{min}}(\vec{n},\vec{m})=\mathcal{O}\left(\min\left\\{\sum_{k=0}^{\alpha_{\vec{n}}}X_{k}(\vec{n}),\sum_{l=0}^{\alpha_{\vec{m}}}X_{l}(\vec{m})\right\\}\alpha_{\vec{n}}\alpha_{\vec{m}}\right).$
(19)

Here, $\alpha_{\vec{n}}$ is the number of nonzero elements in the Fock state
vector $\vec{n}$, called the Fock state coherence rank, and $X_{k}(\vec{n})$
is the $k$-th elementary symmetric potential defined as

$\displaystyle
X_{k}(\vec{n})=\sum_{i_{1}<i_{2}<...<i_{k}=1}^{\alpha_{\vec{n}}}n_{i1}n_{i2}...n_{ik},(0\leq
k\leq\alpha_{\vec{n}}\leq M).$ (20)

The minimal computation time is then determined by the quantity
$\sum_{k=0}^{\alpha_{\vec{n}}}X_{k}(\vec{n})$ for the input state and the
output state. The input state will be collision-free,
$\vec{n}_{\text{collision-free}}$ for which the following holds [46]

$\displaystyle\sum_{k=0}^{\alpha_{\vec{n}}}X_{k}(\vec{n}_{\text{collision-
free}})=2^{N}=2^{\alpha_{\vec{n}}}.$ (21)

Adding a collision to a collision-free state corresponds to increasing one of
the nonzero numbers $n_{i}$ in $\vec{n}$. From the definition of Eq. (20), we
can see that the value of $\sum_{k=0}^{\alpha_{\vec{n}}}X_{k}(\vec{n})$ then
has to increase. As such, the following inequality will be true for any state
$\vec{n}$

$\displaystyle\sum_{k=0}^{\alpha_{\vec{n}}}X_{k}(\vec{n})\geq
2^{\alpha_{\vec{n}}}.$ (22)

Thus we can say that the minimal computation time has to scale at least as
$\mathcal{O}(2^{\alpha_{\vec{m}}}\alpha_{\vec{n}}\alpha_{\vec{m}})$.
Accordingly, we can conclude that the computational complexity of boson
sampling with collisions is not diminished compared to the computational
complexity of collision-free boson sampling with the same number of nonzero
elements.

##  Appendix B The size of the Hilbert subspace for a given number of photon
collisions.

The number of basis states in the Hilbert space with a given number of
collisions is equal to the product of the number of ways one can distribute
$d$ nonzero modes in $m$ modes, and the number of ways one can place $p-l-d$
collisions into $d$ nonzero modes. The first number is equal to the number of
combinations without replacements with $d$ choices from $m$ possibilities:

$\displaystyle\binom{m}{d}.$

The second number is equal to the number of combinations with replacements
with $p-l-d$ choices from $d$ possibilities

$\displaystyle\binom{(p-l-d)+d-1}{p-l-d}$ $\displaystyle=$
$\displaystyle\binom{p-l-1}{p-l-d}$

Consequently the size of the Hilbert subspace with $p-d-l$ collisions,
$n_{\text{collisions}}(p,d,l,m)$, will be

$\displaystyle
n_{\text{collisions}}(p,d,l,m)=\binom{m}{d}\cdot\binom{p-l-1}{p-l-d}.$ (23)

The size of the full Hilbert space, $n_{\text{full}}$ will be the number of
ways one can place $p-l$ photons into $m$ modes. This is equivalent to the
number of combinations with replacements of $p-l$ choices with $m$
possibilities:

$\displaystyle n_{\text{full}}(m,p,l)=\binom{m+p-l-1}{p-l}.$ (24)

We can then take the ratio between Eqs. (23) and (24) to find Eq. (7)

##  Appendix C The downsides of using loop architectures for time-bin
interferometer

Though it is possible to implement large multimode interferometers using only
a single physical MZI connected to fiber delay loops, as in Refs. [37, 38],
this has two major downsides: higher propagation loss and severely reduced
input state rate. Much in the same way as in the cascaded case, a column of
MZIs in the Clements or Rectangular scheme can be implemented by sending the
time-bins through the MZI one by one and reconfiguring the MZI transformation
for each time-bin. In order to reuse the same physical MZI to implement
additional columns, we can connect the outputs to the inputs through a delay
loop, where the delay is sufficiently long that all output modes back at the
input after the previous MZI column has been finished. As each column
processes up to $m/2$ time-bins, this requires that the loops have a delay of
at least $m/2$ time-bins. This is in comparison to the cascaded scheme where
no such delay is necessary apart from the delay of one time-bin in one of the
modes, which will still be present in the loop architecture. To see the
difference, we can compare the total delay, $t_{\text{delay}}$ for the worst
case of the Clements scheme with a cascaded architecture and a loop
architecture

$\displaystyle t_{\text{delay, cascaded}}=\frac{m}{2}-1\cdot\tau,$ (25)
$\displaystyle t_{\text{delay, loop}}=(m-1)(\frac{m}{2}-1)\cdot\tau,$ (26)

where $\tau$ corresponds to the separation between time-bins. In other words,
the total propagation loss scales linearly with the number of modes for
cascaded time-bin interferometers, whereas it scales quadratically with the
number of modes for loop time-bin interferometers.

The second downside is that one has to wait for the full output state to come
out of the interferometer before processing a new input state. The time
difference between the first time-bin in the input state and the last time-bin
of the output state is equivalent to the delay in Eq. (26). As the time-bin
separation is related to the rate of the single-photon source, the input
generation rate, $r_{\text{input}}$ for the loop time-bin interferometer will
be given by

$\displaystyle r_{\text{input}}=\frac{2r_{\text{single-photon}}}{m(m-1))}.$
(27)

This is approximately a factor $1/m$ worse than the corresponding rate for a
cascaded interferometer.