# ParamISP: Learned Forward and Inverse ISPs using Camera Parameters

Woohyeok Kim1 Geonu Kim1 Junyong Lee1
Seungyong Lee1 Seung-Hwan Baek1 Sunghyun Cho1
1 POSTECH

###### Abstract

RAW images are rarely shared mainly due to its excessive data size compared to
their sRGB counterparts obtained by camera ISPs. Learning the forward and
inverse processes of camera ISPs has been recently demonstrated, enabling
physically-meaningful RAW-level image processing on input sRGB images.
However, existing learning-based ISP methods fail to handle the large
variations in the ISP processes with respect to camera parameters such as ISO
and exposure time, and have limitations when used for various applications. In
this paper, we propose ParamISP, a learning-based method for forward and
inverse conversion between sRGB and RAW images, that adopts a novel neural-
network module to utilize camera parameters, which is dubbed as ParamNet.
Given the camera parameters provided in the EXIF data, ParamNet converts them
into a feature vector to control the ISP networks. Extensive experiments
demonstrate that ParamISP achieve superior RAW and sRGB reconstruction results
compared to previous methods and it can be effectively used for a variety of
applications such as deblurring dataset synthesis, raw deblurring, HDR
reconstruction, and camera-to-camera transfer.

##  1 Introduction

A camera ISP converts a RAW image into a visually pleasing sRGB image, which
is typically saved as a JPEG image. A camera ISP performs a series of
operations including defective pixel correction, denoising, lens shading
correction, white balance, color filter array interpolation, color space
conversion, tone reproduction, and non-linear contrast enhancement. Detailed
operations of camera ISPs are typically sealed to the public and vary from
camera to camera.

Unlike sRGB images, RAW images provide physically-meaningful and interpretable
information such as noise distributions as they have the linear relationship
between image intensity and radiant energy incident on a camera sensor. Such
properties of RAW images have been exploited for denoising [1, 17, 23], HDR
[5, 14], and super-resolution [32, 24], leading to superior reconstruction
quality than using only sRGB images. However, a RAW image demands large memory
to store due to the use of per-pixel high-precision bits without any
compression. Therefore, only sRGB images are often shared without their RAW
counterparts, making it difficult to utilize the useful properties of RAW
images.

Recent methods have studied ways of reconstructing RAW images from sRGB images
and vice versa by modeling forward and inverse ISPs [4, 30, 29, 3, 7].
However, despite notable improvements, existing methods suffer from
limitations. First, they do not account for the adaptive nature of the real-
world ISPs, which adjust their operations based on the camera parameters such
as exposure time, sensor sensitivity and focal length accessible in the EXIF
metadata of a JPEG image. The operations of real-world ISPs such as denoising,
sharpening and tone adjustment depend on the camera parameters, producing
images with different tones and colors, as shown in Fig. 1. Furthermore,
previous methods adopt rather simple network architectures disregarding the
complexity of the ISP operations, which leads to low RAW reconstruction
quality. They construct a single network by stacking residual blocks [30] or
invertible blocks [29], or organize the modules by simply arranging
convolution layers [3] continuously.

Figure 1: Impact of camera parameters on a camera ISP. Images (a) and (b) are
taken by a Samsung Galaxy S22 with different camera parameters. SS and ISO
indicate the shutter speed and sensor sensitivity, respectively. In (c), we
visualize RGB histograms of each cropped patch of (a) and (b). Despite the
same target scene, the captured images exhibit distinct histograms, implying
complex ISP operations dependent on the camera parameters.

In this paper, we present a novel forward and inverse ISP framework,
_ParamISP_. ParamISP is designed to faithfully reflect the real-world ISP
operations that change based on camera parameters. To effectively incorporate
the camera parameters, ParamISP consists of a pair of forward and inverse ISP
networks that include a novel neural network module _ParamNet_. ParamNet
extracts a feature vector from the camera parameters including exposure time,
sensitivity, aperture size, and focal length, and feeds it to the forward and
inverse ISP subnetworks to control their behaviors.

To learn ISP operations for varying camera parameters, we need to address the
following problems. First, the camera parameters have significantly different
scales, such as an exposure time of 0.01 sec. and a sensitivity of 800.
Moreover, some parameters such as exposure time and sensor sensitivity have
non-linearly increasing parameter values, e.g., the pre-set exposure time of
commodity cameras roughly increases exponentially (1/250 sec., 1/125 sec.,
1/60 sec., …). Second, existing datasets lack of diversity in camera
parameters [8, 23, 21], while a significant effort is required to collect a
sufficient number of images for possible combinations of different camera
parameters. Such scale difference and insufficient amount of training data
make it difficult to reliably learn ISP operations for different camera
parameters. Therefore, we propose a non-linear equalization scheme that
adjusts the scales of the camera parameters and a random-dropout-based
learning strategy to effectively learn the effects of all the camera
parameters.

Finally, we present novel network architectures that reflect the real-world
ISP operations. Specifically, our ISP networks consist of four subnetworks:
_CanoNet_ , _LocalNet_ and _GlobalNet_ , along with _ParamNet_. CanoNet
performs common ISP operations such as demosaicing, white balance, and color
space conversion using fixed operations without learnable weights. GlobalNet
performs global tone manipulation with respect to the camera parameters.
LocalNet performs other residual operations that are not captured by CanoNet
and GlobalNet.

By incorporating camera parameters, novel network architectures, and training
schemes, ParamISP achieves accurate reconstruction performance with a smaller
network size. Our extensive evaluation shows that ParamISP surpasses previous
learning-based ISP models by an average of 1.93 dB and 1.84 dB in RAW and sRGB
reconstruction, respectively (Sec. 4). Furthermore, ParamISP is robustly
applicable to various applications (_e.g_., deblurring dataset synthesis, RAW
deblurring, HDR reconstruction, camera-to-camera transfer) (Sec. 5).

Our contributions are summarized as follows:

  * $\bullet$

We propose _ParamISP_ , a novel learning-based forward and inverse ISP
framework that leverages camera parameters (_e.g_., exposure time,
sensitivity, aperture size, and focal length) for high-quality sRGB and RAW
reconstruction.

  * $\bullet$

To effectively incorporate camera parameters, we develop _ParamNet_ , a novel
neural network module that controls the forward and inverse ISP networks
according to camera parameters. We also introduce a non-linear equalization
scheme and a random-dropout-based learning strategy for stable and effective
learning of ISP operations with respect to camera parameters.

  * $\bullet$

We present novel network architectures for the forward and inverse ISP
networks that better reflect real-world ISPs. (CanoNet, LocalNet, GlobalNet,
ParamNet)

  * $\bullet$

We demonstrate the performance of _ParamISP_ and its internal modules on many
cameras, and show its applicability to various applications.

##  2 Related Work

Figure 2: Overview of the proposed ParamISP framework. The full pipeline is
constructed by combining learnable networks (ParamNet, LocalNet, GlobalNet)
with invertible canonical camera operations (CanoNet). CanoNet consists of
differentiable operations without learnable weights, where WB and CST denote
white balance and color space transform, respectively.

#### Parametric ISPs

To approximate the mapping between RAW and sRGB images, ISP approaches based
on non-learnable parametric operations [4, 7] have been proposed. They employ
simple invertible ISPs that are composed of non-learnable operations using
either camera parameters [4] (_e.g_., white balance and color correction
matrices) or parameters learned from DNNs [7]. However, they do not consider
complex nonlinear ISP operations (_e.g_., local tone mapping and denoising),
resulting in inaccurate reconstruction of sRGB and RAW images.

Learnable ISPs For more accurate approximation to forward and inverse ISP
operations, DNN-based approaches [30, 29, 3] have been proposed, for which
symmetrical forward and inverse ISP networks [30, 3] and an invertible ISP
network [29] are employed to learn mapping between sRGB and RAW images.
However, they are designed without considering camera parameters (_e.g_.,
exposure time, sensor sensitivity, etc), which limit their RAW and sRGB
reconstruction quality.

Moreover, some of the previous methods primarily focus on cyclic
reconstruction (sRGB-to-RAW-to-sRGB) and try to minimize the difference
between the input sRGB image and the sRGB image restored back by the inverse
and forward ISPs. Specifically, CycleISP [30] uses the input sRGB image for
restoring the tone when reconstructing an sRGB image back from a RAW image,
which makes it unsuitable for applications that manipulate the tone in the RAW
space. InvISP [29] employs a single normalizing flow-based invertible network
for both inverse and forward processes. While this design choice leads to near
perfect reconstruction quality for cyclic reconstruction, its quality
significantly degrades when the intermediate RAW images are altered, making it
unsuitable for applications that manipulate images in the RAW space as
demonstrated in Sec. 5. In contrast, we design our forward and inverse ISP
networks to operate independently during inference time to cater to a broader
range of applications.

#### RAW Reconstruction using Additional Information

To achieve precise RAW reconstruction from an sRGB image, another line of
research that utilizes additional information has been introduced [20, 18, 11,
26]. This approach encodes necessary metadata such as a small portion of a RAW
image within an sRGB image at capture time to reconstruct the original RAW
image with high accuracy. However, it necessitates a modification to the
existing ISP process to store the metadata. In contrast, our approach utilizes
the EXIF metadata that commodity cameras already provide.

##  3 ParamISP

Given a target camera, our goal is to learn its forward and inverse ISP
processes that change with respect to camera parameters. To accomplish this,
ParamISP is designed to have a pair of forward (RAW-to-sRGB) and inverse
(sRGB-to-RAW) ISP networks (Fig. 2). Both networks are equipped with ParamNet
so that they adaptively operate based on camera parameters.

In ParamISP, we classify camera parameters into two distinct categories:
optical parameters (including exposure time, sensitivity, aperture size, and
focal length) and canonical parameters (Bayer pattern, white balance
coefficients, and a color correction matrix). The canonical parameters
directly influence fundamental ISP operations like demosaicing, white balance
adjustments, and color space conversion. These operations are relatively
straightforward, and their relationship with the canonical parameters is well-
defined.

While previous approaches have leveraged the canonical parameters [4, 7], the
optical parameters have remained untapped. In contrast, ParamISP exploits both
sets of parameters to achieve highly accurate sRGB and RAW reconstruction. To
harness the canonical parameters, our ISP networks incorporate CanoNet, a
subnetwork that performs canonical ISP operations without learnable weights.
For the optical parameters, we introduce ParamNet, which is the key component
to dynamically control the behavior of the ISP networks based on the optical
parameters.

In the following, we describe ParamNet and our training strategy for stable
and effective training. We then explain the forward and inverse ISP
subnetworks in detail.

###  3.1 ParamNet

Figure 3: Architecture of ParamNet. (a) Given camera optical parameters,
ParamNet estimates optical parameter features used for modulating the LocalNet
and GlobalNet. (b) In order to deal with different scales and non-linearly
distributed values of optical parameters, we propose to use non-linear
equalization that exploits multiple non-linear mapping functions.

As described in Fig. 3, ParamNet takes optical parameters as input and
converts them into an optical parameter feature vector $z$, which is then fed
to both LocalNet and GlobalNet. ParamNet consists of a non-linear equalization
layer, and fully-connected layers. The non-linear equalization layer computes
a normalized feature vector for each optical parameter to compensate for the
scale difference between the optical parameters. The equalized feature vectors
are then arithmetically summed together, and fed to the fully-connected layers
to obtain an optical parameter feature vector $z$.

#### Non-linear Equalization

As discussed in Sec. 1, the optical parameters exhibit significantly different
scales, and their values are non-linearly distributed. While some optical
parameters may substantially alter the behavior of the camera ISP, others may
have minimal effect. Moreover, the influence of optical parameters may vary
across different camera models. As a result, naïvely incorporating the optical
parameters leads to unstable training of ParamNet.

To resolve this issue, the non-linear equalization layer of ParamNet applies
various non-linear mapping to each optical parameter and learns the best
composition of them that enables stable training. Specifically, we first apply
non-linear mapping functions such as $x$, $1/x$, $\sqrt{x}$, $x^{-1/2}$,
$x^{1/4}$, $x^{-1/4}$, $\log(x)$, $\sin(\log(x))$, $\cos(\log(x))$,
$\sin(c\cdot x)$, and $\cos(c\cdot x)$ to each optical parameter, where $x$ is
the value of an optical parameter, and $c$ controls the frequency of the
sinusoidal functions, for which we use three different values empirically
chosen. We then normalize each of the non-linear mapping results into $[0,1]$.
As a result, we obtain a $15$-dim. vector for each optical parameter. Then,
each vector is processed through a subsequent fully-connected layer to extract
useful information from each parameter vector.

Our non-linear equalization layer incorporates a range of diverse non-linear
mapping functions, rather than relying on a predefined set of carefully-chosen
functions, in order to cover the wide spectrum of potential relationships
between each optical parameter and the camera ISP. Thus, some mapping
functions may look redundant or unnecessary. Nevertheless, the subsequent
fully-connected layer can successfully learn to extract only useful
information from them by combining them with different weights.

#### Random Dropout

Even with the non-linear equalization, ParamNet can still be trained to
overfit to a subset of the optical parameters due to the scale difference and
the insufficient amount of training data. To mitigate the problem, during
training, we randomly drop out the equalized feature vector of each optical
parameter. Specifically, each optical parameter is randomly dropped out by the
probablity of 20% at each training iteration.

###  3.2 Forward ISP Network

Figure 4: Detailed architecture of LocalNet and GlobalNet. In GlobalNet,
$f_{g}$ and $f_{q}$ represent the gamma correction and quadratic
transformation, respectively, while $c_{n}$ represents the $n$-th coefficients
$G^{n}$ and $W^{n}$, as explained in Sec. 3.2.

The forward ISP network consists of four subnetworks: CanoNet, LocalNet,
GlobalNet, and ParamNet (Fig. 2(a)). CanoNet performs canonical ISP
operations: demosaicing [9], white balance, and color space conversion,
exploiting the canonical parameters. LocalNet performs local operations of an
ISP such as denoising, sharpening and local tone mapping in addition to
compensating for the residual errors of the canonical ISP operations of
CanoNet. GlobalNet performs global tone manipulation with respect to the
camera parameters. ParamNet is connected to LocalNet and GlobalNet and
controls their behavior. In the following, we explain each of CanoNet,
LocalNet and GlobalNet in detail.

#### CanoNet

CanoNet takes a RAW image $I_{RAW}\\!\in\\!\mathbb{R}^{1\times H\times W}$ and
first performs demosaicing [9] to produce $I_{Dem}\\!\in\\!\mathbb{R}^{3\times
H\times W}$ according to the Bayer pattern of $I_{RAW}$. The demosaicing
algorithm of CanoNet may differ from that of the target camera ISP.
Nonetheless, such discrepancy is compensated by the subsequent LocalNet. It
then performs white balance using the coefficients
$g_{\mathrm{WB}}\in\mathbb{R}^{3}$. Lastly, it transforms the color space from
the RAW space to the linear sRGB space using the color correction matrix
$M_{\mathrm{Cam}}\\!\in\\!\mathbb{R}^{3\times 3}$. We denote the resulting
image as $I_{lin}\\!\in\\!\mathbb{R}^{3\times H\times W}$.

#### LocalNet

Fig. 4 shows an overview of LocalNet. LocalNet takes $I_{lin}$ and an optical
parameter feature vector $z$ from ParamNet as input, and performs local ISP
operations. As well as $I_{lin}$, LocalNet also takes additional handcrafted
features: a gradient map, a soft histogram map, and an over-exposure mask
computed from $I_{lin}$, as they help improve reconstruction quality, as shown
in [13, 12, 14]. For more details, refer to the supplementary material.
Finally, LocalNet predicts a residual image, which is then added to $I_{lin}$
to obtain the output image $I_{local}$.

As the goal of LocalNet is to learn local ISP operations, LocalNet adopts a
network architecture based on the U-Net [22], which has been proven to be
highly effective for various image restoration and enhancement tasks [31, 27,
2, 10, 6]. Specifically, the input image and the additional input features
computed from the input image are concatenated, and fed to LocalNet. Besides,
the optical parameter feature vector $z$ is duplicated horizontally and
vertically to build a feature map of the same spatial size as the input image.
The feature map is then added to an intermediate feature map of LocalNet.
Then, the resulting feature map is processed through multi-scale residual
blocks (ResBlocks) with convolutional block attention modules (CBAMs) [28],
and converted to a residual image.

#### GlobalNet

GlobalNet globally adjusts tone and color according to the content of its
input image and the optical parameter feature vector $z$. To this end,
GlobalNet adopts parametric global adjustment operations and predicts their
parameters. Specifically, GlobalNet adopts two types of global adjustment
operations: quadratic transformation $f_{q}$ and gamma correction $f_{g}$. Let
us denote the input image to global adjustment operation as $I$, and its pixel
as $p=(p_{r},p_{g},p_{b})$. Then, the quadratic transformation $f_{q}$ is
defined as:

$f_{q}(p)=Wp^{\prime}$ (1)

where $p^{\prime}$ is a 10-dim. vector defined as
$p^{\prime}=[p_{r}^{2},p_{g}^{2},p_{b}^{2},p_{r}p_{g},p_{g}p_{b},p_{b}p_{r},p_{r},p_{g},p_{b},1]^{T}$.
$W$ is a $3\times 10$ matrix with the coefficients of the quadratic
transformation, which is uniformly applied to all the pixels in $I$. The gamma
correction operator $f_{g}$ is defined as:

$f_{g,c}(p_{c})=\frac{(\alpha_{c}p_{c}+\beta_{c})^{\gamma_{c}}-\beta_{c}^{\gamma_{c}}}{(\alpha_{c}+\beta_{c})^{\gamma_{c}}-\beta_{c}^{\gamma_{c}}}$
(2)

where the subscript $c$ is an index to each color channel, i.e.,
$c\in\\{r,g,b\\}$. $\gamma_{c}$ is a gamma parameter, while $\alpha_{c}$ and
$\beta_{c}$ are a scale and an offset, respectively. The set of the gamma
correction coefficients is denoted by $G$, i.e.,
$G=\\{\alpha_{r},\beta_{r},\gamma_{r},\alpha_{g},\beta_{g},\gamma_{g},\alpha_{b},\beta_{b},\gamma_{b}\\}$.
Similar to $W$, $G$ is also uniformly applied to all the pixels in $I$. For
the sake of notational simplicity, we represent the quadratic transformation
and gamma correction of an entire image $I$ as $f_{q}(I)$ and $f_{g}(I)$,
respectively, in the rest of the paper.

To support a wide range of potential non-linear tone adjustments of commodity
camera ISPs, GlobalNet models the global tone adjustment as a series of gamma
correction and quadratic transformation. Specifically, given an input image
$I$, GlobalNet performs global tone adjustment as:

$\hat{I}=f_{gq}^{N}\circ\cdots\circ f_{gq}^{1}(I)$ (3)

where $f_{gq}^{n}(I)$ is defined as $f_{gq}^{n}=f_{g}^{n}(f_{q}^{n}(I))$.
$f_{g}^{n}$ and $f_{q}^{n}$ are the gamma correction and quadratic
transformation with the $n$-th coefficients $G^{n}$ and $W^{n}$, respectively.
In our experiments, we use $N=4$ as it leads to the best quality (Tab. 4).

The quadratic transformation is also adopted by previous modular learnable
ISPs [3, 23]. However, a single quadratic transformation cannot accurately
model diverse non-linear tone adjustments performed by commodity camera ISPs
including gamma correction. Therefore, in our approach, we extend the global
tone adjustment by adopting the gamma correction and iteratively applying both
gamma correction and quadratic transformation.

Fig. 4 shows an overview of GlobalNet. To predict the coefficients
$\\{\cdots,(G^{n},W^{n}),\cdots\\}$, GlobalNet takes a concatenation of
$I_{local}$ and the handcrafted features computed from $I_{local}$ as done in
LocalNet as input, and extracts a global feature vector through a series of
convolution layers with max pooling, and a global average pooling layer. The
global feature vector is then added to the optical parameter feature vector,
and processed through fully-connected layers to obtain the coefficients.

###  3.3 Inverse ISP Network

The inverse ISP network also consists of CanoNet, LocalNet, GlobalNet and
ParamNet with an inverse order of the forward ISP network (Fig. 2(b)).
Specifically, GlobalNet takes an sRGB image as input and performs inverse tone
manipulation. Next, LocalNet executes inverse local operations, and finally,
CanoNet handles inverse color space conversion, inverse white balance, and
mosaicing. GlobalNet and LocalNet use the same network architectures as those
in the forward ISP network. On the other hand, CanoNet consists of the inverse
operations of those of the forward ISP network, but in reverse order.

##  4 Experiments

#### Implementation

We used PyTorch [19] to implement our models. We train our model in two
stages: pre-training and fine-tuning. In the pre-training stage, we train our
models with multiple datasets captured from multiple cameras. In the fine-
tuning stage, we train our models on a specific target camera. Although our
models aim at learning the ISP of a single target camera model, we found that
pre-training with multiple cameras substantially improves the reconstruction
quality. In the pre-training stage, we use the RAISE dataset [8] from Nikon
D7000, D90, and D40, the RealBlur dataset [21] from Sony A7R3, and the S7 ISP
dataset [23] from Samsung Galaxy S7. More details such as the effect of the
pre-training, the statistics of the datasets, and how we split the datasets to
training, validation, and test sets can be found in the supplementary
material.

Baseline (Ours w/o ParamNet) | PSNR$\uparrow$ | Param$\downarrow$
---|---|---
ParamNet | Non-linear | Random |  |
(w/ Opt. Params) | Equalization | Dropout |  |
|  |  | 34.77 | 0.68M
$\checkmark$ |  |  | - | -
$\checkmark$ | $\checkmark$ |  | 35.64 | 0.71M
$\checkmark$ | $\checkmark$ | $\checkmark$ | 36.21 | 0.71M
|  |  |  |

Table 1: Ablation study on the components of ParamNet.

Otical Params | w/o $A$ | w/o $B$ | w/o $C$ | w/o $D$ | Full
---|---|---|---|---|---
PSNR$\uparrow$ | 35.13 | 35.25 | 35.87 | 35.46 | 36.21
SSIM$\uparrow$ | 0.9678 | 0.9718 | 0.9724 | 0.9705 | 0.9724
|  |  |  |  |

Table 2: Ablation study on the impact of each optical parameter. $A$,$B$,$C$,
and $D$ represent sensor sensitivity, exposure time, aperture size, and focal
length, respectively.

We train our network in the pre-training stage for 520 epochs with an initial
learning rate of $2.0\times 10^{-4}$, and in the fine-tuning stage for 2,140
epochs with an initial learning rate of $2.0\times 10^{-5}$. For both pre-
training and fine-tuning, we employ AdamW [15] and the learning rate is step-
decayed with a rate of 0.8 every 10 epochs. In each epoch in the pre-training
stage, we randomly sample 1024 cropped patches of size $448\times 448$ from
the dataset of each camera, resulting in a total of 5120 patches. In the fine-
tuning stage, we sample 1024 patches from the dataset of a target camera in
each epoch. We evaluated our models and other models on a PC equipped with an
NVIDA RTX A6000. For a fair comparison, we also apply both pre-training and
fine-tuning to other models in our experiments.

We train our forward and inverse ISP networks in an end-to-end fashion using
losses $\mathcal{L}_{for}$ and $\mathcal{L}_{inv}$:

$\displaystyle\mathcal{L}_{for}$ $\displaystyle=$
$\displaystyle\|\hat{I}_{sRGB}-I_{sRGB}\|_{1}$ (4)
$\displaystyle\mathcal{L}_{inv}$ $\displaystyle=$
$\displaystyle\|\hat{I}_{RAW}-I_{RAW}\|_{1}$ (5)

respectively, where $\hat{I}_{sRGB}$, $I_{sRGB}$, $\hat{I}_{RAW}$, and
$I_{RAW}$ are a reconstructed sRGB image, its ground-truth sRGB image, a
reconstructed RAW image, and its ground-truth RAW image, respectively.

###  4.1 Ablation Study

Figure 5: sRGB-to-RAW reconstruction. We show error maps between reconstructed
and GT RAW images. Figure 6: RAW-to-sRGB reconstruction. We show error maps
between reconstructed and GT sRGB images.

For all the ablation studies in this section, we train inverse (sRGB-to-RAW)
ISP network using the D7000 training images of the RAISE dataset [8].
Additional ablation studies using the forward ISP network and different camera
datasets, and on the effect of the input features and training approach can be
found in the supplementary material.

#### ParamNet

We first evaluate the effect of the non-linear equalization and random optical
parameter dropout of ParamNet. To this end, we compare variants of our model
in Tab. 1. The first row in the table corresponds to a baseline model without
ParamNet. Introducing ParamNet without non-linear equalization (2nd row)
results in the failure of training with diverging losses. On the other hand,
the non-linear equalization (3rd row) not only stabilizes the training but
also improves the reconstruction quality compared to the baseline model in the
first row, which proves that the non-linear equalization is essential for
training, and that exploiting the optical parameters is necessary to improve
the reconstruction quality. Finally, random dropout of the optical parameters
(4th row) further enhances the reconstruction quality as it prevents
overfitting and enhances the generalization ability of ParamNet.

#### Optical Parameters

We now analyze the impact of the optical parameters. To this end, we compare
four variants of ParamNet, for each of which, we exclude each one of the four
optical parameters. Tab. 2 shows the quantitative ablation results. Compared
to the model that uses all the optical parameters, all the other variants
exhibit performance degradation, indicating that all the optical parameters
need to be considered for high-quality reconstruction. We can also observe
that excluding the sensitivity and exposure time shows the largest performance
degradation. While how commodity camera ISPs utilize the optical parameters is
unknown, these optical parameters may affect the image enhancement operation
of camera ISPs, such as denoising, as they are closely related to noise. The
impact of the aperture size and focal length is not as significant as the
others, but the reconstruction quality still decreases without them. This is
because aperture size and focal length are related to defocus blur and lens
aberrations, so the camera ISP operations may alter based on them.

#### ISP Network Architecture

We verify the effectiveness of the network architecture of our ISP
subnetworks. As our modular network structure is inspired by CIE XYZ Net [3]
that consists of a pair of local and global mapping modules, we consider its
local and global mapping networks as our baseline for LocalNet and GlobalNet.
Specifically, we build a baseline model for the inverse ISP network by
replacing the LocalNet and GlobalNet with the local and global mapping
networks of CIE XYZ Net, then compare the performance of the baseline and its
variants to ours. The local mapping network of CIE XYZ Net simply stacks
convolution layers, while the global mapping network models global tone
manipulation as a single quadratic function and estimate its parameters using
fully-connected layers. Tab. 3 shows the comparison result. The table shows
that LocalNet significantly improves the PSNR by more than 3 dB over the local
mapping of CIE XYZ Net. Moreover, GlobalNet further improves the PSNR by
around 0.5 dB and leads to a significantly reduced model size thanks to our
global tone adjustment model and efficient network architecture.

Additionally, we verify the effects of a series of gamma correction and
quadratic transformation in GlobalNet (Tab. 4). We compare global adjustment
operations of previous methods [3, 23] to GlobalNet with a series of gamma
correction and quadratic transformation (1st to 3rd columns). Subsequently, we
progressively increase the number of gamma correction and quadratic
transformation in the series to validate the effects of overlaying (4th to 7th
columns). The table shows that our global tone adjustment operation improves
the PSNR by more than 0.89 dB over the others [3, 23].

Baseline (CIE XYZ Net [3]) | PSNR$\uparrow$ | SSIM$\uparrow$ | Param$\downarrow$
---|---|---|---
LocalNet | GlobalNet |  |  |
|  | 30.04 | 0.9461 | 1.3M
$\checkmark$ |  | 33.12 | 0.9644 | 1.7M
$\checkmark$ | $\checkmark$ | 33.66 | 0.9646 | 0.6M
|  |  |  |

Table 3: Ablation study on the effects of LocalNet and GlobalNet.

Operation | $A$ | $B$ |  $C$$\times$1 |  $C$$\times$2 |  $C$$\times$3 |  $C$$\times$4 |  $C$$\times$5
---|---|---|---|---|---|---|---
PSNR$\uparrow$ | 32.70 | 32.77 | 32.87 | 32.96 | 33.27 | 33.66 | 33.50
SSIM$\uparrow$ | 0.962 | 0.961 | 0.961 | 0.962 | 0.963 | 0.965 | 0.967
|  |  |  |  |  |  |

Table 4: Ablation study on the effects of global adjustment operation. $A$ and
$B$ represent 3$\times$6 polynomial mapping function (CIE XYZ Net [3]) and
3$\times$10 quadratic transformation (DeepISP [23]) respectively, while $C$
denotes a series of gamma correction and quadratic transformation (Ours).
Additionally, in $C$$\times$$N$, $N$ represents the number of pairs
($N=1,2,3,4,5$).

###  4.2 RAW & sRGB Reconstruction

In this section, we compare the sRGB-to-RAW and RAW-to-sRGB reconstruction
ability of ParamISP with existing state-of-the-art methods: UPI [4], CIE XYZ
Net [3], CycleISP [30], and InvISP [29]. UPI is a non-learnable parametric
method that approximates the general structure of the camera ISP. CIE XYZ Net,
CycleISP, and InvISP are learning-based approaches that employ symmetrical
forward and inverse ISP networks. For CIE XYZ Net whose output is an image in
the CIE XYZ color space, we convert its output to a RAW image using canonical
ISP operations as in CanoNet for a fair comparison. For InvISP whose output is
white-balanced RAW image, we apply inverse white balancing and mosaicing
operations to obtain a RAW image. These learning-based methods train the
forward and inverse networks together, but we found that separately training
them for each yields better performance. Therefore, we train them separately
in the same manner as ours.

Method | sRGB$\rightarrow$RAW measured in PSNR$\uparrow$ | Param$\downarrow$
---|---|---
D7000 | D90 | D40 | S7 | A7R3
UPI [4] | 20.67 | 26.57 | 22.05 | 29.98 | 30.48 | -
CIE XYZ Net [3] | 30.04 | 32.62 | 38.57 | 33.24 | 36.42 | 1.3M
CycleISP [30] | 35.52 | 35.85 | 42.83 | 34.55 | 45.35 | 3.1M
InvISP [29] | 33.48 | 35.39 | 45.08 | 34.29 | 47.14 | 1.4M
ParamISP (Ours) | 38.49 | 37.06 | 45.97 | 35.20 | 48.33 | 0.7M
|  |  |  |  |  |

Table 5: Quantitative comparison on RAW reconstruction.

Method | RAW$\rightarrow$sRGB measured in PSNR$\uparrow$ | Param$\downarrow$
---|---|---
D7000 | D90 | D40 | S7 | A7R3
UPI [4] | 18.81 | 20.30 | 16.01 | 20.05 | 19.37 | -
CIE XYZ Net [3] | 26.76 | 27.61 | 34.84 | 27.63 | 37.19 | 1.3M
InvISP [29] | 30.20 | 28.89 | 37.86 | 28.96 | 43.93 | 1.4M
ParamISP (Ours) | 34.14 | 30.83 | 39.54 | 29.02 | 45.51 | 0.7M
|  |  |  |  |  |

Table 6: Quantitative comparison on sRGB reconstruction.

Tab. 5 shows quantitative results of the inverse sRGB-to-RAW reconstruction in
terms of PSNR evaluated on our test set. UPI [4] results in high
reconstruction errors due to its parametric model-based pipeline. CIE XYZ Net
[3], CycleISP [30], and InvISP [29] show better reconstruction quality than
UPI, but their quality is still limited compared to our method. ParamISP
achieves the best reconstruction quality despite its much smaller model size,
thanks to leveraging the optical parameters and our carefully-designed network
architecture. Fig. 5 shows the qualitative results of error maps between
reconstructed RAW images and ground-truth RAW images. As the figure shows, our
method produces much less error than the others.

Tab. 6 reports quantitative results of the forward reconstruction (RAW-to-
sRGB). CycleISP is not included in this comparison because it needs an input
sRGB image for sRGB reconstruction in the sRGB-to-RAW-to-sRGB cyclic
reconstruction. Similar to the inverse sRGB-to-RAW reconstruction, ParamISP
clearly outperforms the other methods, showing the effectiveness of our
approach.

##  5 Applications

Forward and inverse ISP models can benefit various applications as shown in
[3, 29, 30]. In this section, we demonstrate a couple of applications of
ParamISP: RAW deblurring and HDR reconstruction. Other additional applications
including deblurring dataset synthesis and camera-to-camera transfer are also
provided in the supplementary material. Before applying ParamISP to
applications, we further perform joint fine-tuning on separately trained
forward and inverse ISP networks. For details on the joint fine-tuning, refer
to the supplementary material.

Figure 7: Qualitative results of RAW deblurring. In (c) and (d), red artifacts
are visible in white text, while in (b) and (e), the results are blurrier than
ours.

Method |  UPI [4] |  CIE XYZ Net [3] |  InvISP [29] |  CycleISP [30] |  ParamISP (Ours)
---|---|---|---|---|---
PSNR$\uparrow$ | 24.63 | 28.30 | 28.82 | 29.94 | 30.70
SSIM$\uparrow$ | 0.8011 | 0.8444 | 0.8721 | 0.8855 | 0.8984
Param$\downarrow$ | - | 2.7M | 1.4M | 7.4M | 1.4M
|  |  |  |  |

Table 7: Quantitative results of RAW deblurring.

#### Deblurring in RAW Space

While the irradiance of a blurred image has a linear relationship with its
latent sharp image, such a linear relationship no longer holds in sRGB images
after non-linear operations have been applied by camera ISPs. Such non-
linearity varies across different cameras. Consequently, learning sRGB image
deblurring requires camera-specific training datasets, which leads to an
excessive amount of training time and memory space to support diverse camera
models. Instead, we can effectively reconstruct a RAW image from an sRGB image
using ParamISP, apply a camera-independent deblurring model to the RAW image,
and obtain a deblurred sRGB image. While ParamISP also requires camera-wise
training, it requires a much smaller number of parameters ($2\times 0.7$M)
compared to deblurring models (Stripformer: 20M [25] and Uformer-B: 51M [27]),
and supports a wide range of applications.

Tab. 7 and Fig. 7 show quantitative and qualitative comparisons of deblurring
results in the RAW space using different ISP networks. For deblurring in the
RAW space, we use Stripformer [25] trained on the RealBlur-R dataset, which is
a real-world RAW blurry image dataset [21]. The evaluation is done on the
RealBlur-J test set [21]. As the comparisons show, ParamISP clearly
outperforms all the other ISP networks in deblurring performance thanks to its
high-quality sRGB and RAW reconstruction.

Figure 8: Qualitative results of HDR reconstruction.

#### HDR Reconstruction

As shown in CIE XYZ Net [3], RAW image reconstruction can also be used for
high-dynamic-range (HDR) image reconstruction from a single low-dynamic-range
(LDR) image as RAW images provide a wider tonal value range. Specifically, we
first convert an LDR sRGB image to an LDR RAW image, and multiply the
reconstructed RAW image by synthetic digital gains (0.1, 1.4, 2.7, 4.0) to
create four RAW images. Each of these is then passed through the forward ISP
to reconstruct sRGB images. Finally, we apply an off-the-shelf exposure-fusion
algorithm [16] to obtain a single HDR image.

Fig. 8 shows qualitative results using different models. Previous methods
primarily focus on cyclic reconstruction. Specifically, CycleISP uses an input
LDR sRGB image for the forward ISP to adjust the tone, while InvISP, composed
of a single flow-based network, is not robust when intermediate RAW images are
altered. On the other hand, ParamISP successfully produces an HDR
reconstruction result compared to other methods.

##  6 Conclusion

In this paper, we present ParamISP, a novel learning-based forward and inverse
ISP framework that leverages camera parameters (_e.g_., exposure time,
sensitivity, aperture size, and focal length). To incorporate camera
parameters effectively, we introduce ParamNet to control the forward and
inverse ISP networks, proposing a stable and effective training strategy with
respect to camera parameters. We also present novel network architectures for
ISP networks that better reflect real-world ISP operations. Through our
extensive experiments on different cameras, ParamISP shows the state-of-the-
art performance in RAW and sRGB reconstruction and the robust applicability to
various applications compared to previous methods.

## References

  * Abdelhamed et al. [2018] Abdelrahman Abdelhamed, Stephen Lin, and Michael S Brown.  A high-quality denoising dataset for smartphone cameras.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * Abuolaim and Brown [2020] Abdullah Abuolaim and Michael S Brown.  Defocus deblurring using dual-pixel data.  In _Proceedings of the European conference on computer vision (ECCV)_ , 2020.
  * Afifi et al. [2021] Mahmoud Afifi, Abdelrahman Abdelhamed, Abdullah Abuolaim, Abhijith Punnappurath, and Michael S Brown.  CIE XYZ Net: Unprocessing images for low-level computer vision tasks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI)_ , 44(9):4688–4700, 2021.
  * Brooks et al. [2019] Tim Brooks, Ben Mildenhall, Tianfan Xue, Jiawen Chen, Dillon Sharlet, and Jonathan T Barron.  Unprocessing images for learned raw denoising.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * Chen et al. [2018a] Chen Chen, Qifeng Chen, Jia Xu, and Vladlen Koltun.  Learning to see in the dark.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018a.
  * Chen et al. [2018b] Yu-Sheng Chen, Yu-Ching Wang, Man-Hsin Kao, and Yung-Yu Chuang.  Deep photo enhancer: Unpaired learning for image enhancement from photographs with gans.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018b.
  * Conde et al. [2022] Marcos V. Conde, Steven McDonagh, Matteo Maggioni, Ales Leonardis, and Eduardo Pérez-Pellitero.  Model-based image signal processors via learnable dictionaries.  _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , 36(1):481–489, 2022.
  * Dang-Nguyen et al. [2015] Duc-Tien Dang-Nguyen, Cecilia Pasquini, Valentina Conotter, and Giulia Boato.  RAISE: A raw images dataset for digital image forensics.  In _Proceedings of the 6th ACM multimedia systems conference (MMSys)_ , 2015.
  * Getreuer [2011] Pascal Getreuer.  Malvar-he-cutler linear image demosaicking.  _Image Processing on Line_ , 1:83–89, 2011.
  * Kupyn et al. [2018] Orest Kupyn, Volodymyr Budzan, Mykola Mykhailych, Dmytro Mishkin, and Jiří Matas.  Deblurgan: Blind motion deblurring using conditional adversarial networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 8183–8192, 2018.
  * Li et al. [2023] Leyi Li, Huijie Qiao, Qi Ye, and Qinmin Yang.  Metadata-based raw reconstruction via implicit neural functions.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023.
  * Lin and Zhang [2005] Steve Lin and L. Zhang.  Determining the radiometric response function from a single grayscale image.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2005.
  * Lin et al. [2004] Steve Lin, Jinwei Gu, Shuntaro Yamazaki, and Harry Shum.  Radiometric calibration from a single image.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2004.
  * Liu et al. [2020] Yu-Lun Liu, Wei-Sheng Lai, Yu-Sheng Chen, Yi-Lung Kao, Ming-Hsuan Yang, Yung-Yu Chuang, and Jia-Bin Huang.  Single-image hdr reconstruction by learning to reverse the camera pipeline.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * Loshchilov and Hutter [2019] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In _Proceedings of the International Conference on Learning Representations (ICLR)_ , 2019.
  * Mertens et al. [2007] Tom Mertens, Jan Kautz, and Frank Van Reeth.  Exposure fusion.  In _15th Pacific Conference on Computer Graphics and Applications (PG)_ , 2007.
  * Mildenhall et al. [2018] Ben Mildenhall, Jonathan T Barron, Jiawen Chen, Dillon Sharlet, Ren Ng, and Robert Carroll.  Burst denoising with kernel prediction networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * Nam et al. [2022] Seonghyeon Nam, Abhijith Punnappurath, Marcus A Brubaker, and Michael S Brown.  Learning srgb-to-raw-rgb de-rendering with content-aware metadata.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * Paszke et al. [2017] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer.  Automatic differentiation in pytorch.  In _Proceedings of the Neural Information Processing Systems Workshops (NeurIPSW)_ , 2017.
  * Punnappurath and Brown [2021] Abhijith Punnappurath and Michael S Brown.  Spatially aware metadata for raw reconstruction.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_ , 2021.
  * Rim et al. [2020] Jaesung Rim, Haeyun Lee, Jucheol Won, and Sunghyun Cho.  Real-world blur dataset for learning and benchmarking deblurring algorithms.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2020.
  * Ronneberger et al. [2015] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In _International Conference on Medical image computing and computer-assisted intervention (MICCAI)_ , 2015.
  * Schwartz et al. [2018] Eli Schwartz, Raja Giryes, and Alex M Bronstein.  DeepISP: Toward learning an end-to-end image processing pipeline.  _IEEE Transactions on Image Processing (TIP)_ , 28(2):912–923, 2018.
  * Tang et al. [2022] Chengzhou Tang, Yuqiang Yang, Bing Zeng, Ping Tan, and Shuaicheng Liu.  Learning to zoom inside camera imaging pipeline.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * Tsai et al. [2022] Fu-Jen Tsai, Yan-Tsung Peng, Yen-Yu Lin, Chung-Chi Tsai, and Chia-Wen Lin.  Stripformer: Strip transformer for fast image deblurring.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2022.
  * Wang et al. [2023] Yufei Wang, Yi Yu, Wenhan Yang, Lanqing Guo, Lap-Pui Chau, Alex C Kot, and Bihan Wen.  Raw image reconstruction with learned compact metadata.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023.
  * Wang et al. [2022] Zhendong Wang, Xiaodong Cun, Jianmin Bao, Wengang Zhou, Jianzhuang Liu, and Houqiang Li.  Uformer: A general u-shaped transformer for image restoration.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * Woo et al. [2018] Sanghyun Woo, Jongchan Park, Joon-Young Lee, and In So Kweon.  CBAM: Convolutional block attention module.  In _Proceedings of the European conference on computer vision (ECCV)_ , 2018.
  * Xing et al. [2021] Yazhou Xing, Zian Qian, and Qifeng Chen.  Invertible image signal processing.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * Zamir et al. [2020] Syed Waqas Zamir, Aditya Arora, Salman Khan, Munawar Hayat, Fahad Shahbaz Khan, Ming-Hsuan Yang, and Ling Shao.  Cycleisp: Real image restoration via improved data synthesis.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * Zamir et al. [2021] Syed Waqas Zamir, Aditya Arora, Salman Khan, Munawar Hayat, Fahad Shahbaz Khan, Ming-Hsuan Yang, and Ling Shao.  Multi-stage progressive image restoration.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * Zhang et al. [2019] Xuaner Zhang, Qifeng Chen, Ren Ng, and Vladlen Koltun.  Zoom to learn, learn to zoom.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.


# Fast Quantum Concentration via Grover’s Search

Cem M Unsal
Department of Mathematics
<EMAIL_ADDRESS>
A Yavuz Oruc
University of Maryland, College Park, Maryland, 20742 Department of Electrical
and
Computer Engineering
<EMAIL_ADDRESS>
# Faster Quantum Concentration via Grover’s Search

Cem M Unsal
Department of Mathematics
<EMAIL_ADDRESS>
A Yavuz Oruc
University of Maryland, College Park, Maryland, 20742 Department of Electrical
and
Computer Engineering
<EMAIL_ADDRESS>
###### Abstract

We present quantum algorithms for routing concentration assignments on full
capacity fat-and-slim concentrators, bounded fat-and-slim concentrators, and
regular fat-and-slim concentrators. Classically, the concentration assignment
takes $O(n)$ time on all these concentrators, where $n$ is the number of
inputs. Powered by Grover’s quantum search algorithm, our algorithms take
$O(\sqrt{nc}\ln{c})$ time, where $c$ is the capacity of the concentrator.
Thus, our quantum algorithms are asymptotically faster than their classical
counterparts, when $c\ln^{2}{c}=o(n)$. In general, $c=n^{\mu},$ satisfies
$c\ln^{2}{c}=o(n),$ implying a time complexity of $O(n^{0.5(1+\mu)}\ln n),$
for any $\mu,0<\mu<1.$

###### Index Terms:

Concentrator, fat-and-slim crossbar, Grover’s search, quantum information,
network device, routing complexity, matching problem.

##  I Introduction

The promise of quantum computing in speeding up computations continues to
attract research into exploring quantum algorithms for problems that arise in
computer science, mathematics, and other scientific fields of study beyond
searching and factorization. Indeed, several quantum algorithms and circuits
have been reported for a wide range of classical problems extending from
algebraic computations to pattern matching and many problems in graph theory.
See for example [1] and [2] for a survey of quantum algorithms for Abelian and
non-Abelian discrete Fourier transform, hidden subgroup problem, computing
discrete logarithms, and several other problems in number theory,
cryptography, and group theory. Another article by Montanaro provides an
overview of quantum algorithms, and in particular surveys the complexity of
quantum searching and optimization algorithms [3]. In graph theory, Grover’s
search algorithm and quantum walk techniques have been used to solve matching
and network flow problems [4, 5, 6] and graph traversals [7].

In this paper, we focus our attention on a different direction, namely the
application of quantum computing to developing fast quantum algorithms to
realize connection requests in concentrators. Concentration is a fundamental
operation in data processing and is closely related to matchings in graph
theory. Thus, we think that developing fast quantum algorithms for realizing
connection requests in concentrators will likely have a significant impact on
routing in packet switching networks. Loosely speaking, concentration is a
one-to-one mapping between two sets of objects, called inputs and outputs,
where only inputs can be specified, and it is assumed that there are fewer
outputs than inputs. Formally, a graph with a set of vertices, representing
inputs and another set of vertices, representing outputs, in which a one-to-
one mapping exists between every subset of inputs and some subset of outputs
over a set of non-overlapping paths is called a concentrator. Pinsker
established that concentrators with $n$ inputs, $m$ outputs, and at most $29n$
edges exist for all $m\leq n$ in [8]. Since Pinsker’s seminal result, quite a
few concentrator designs have been reported in the literature, see for example
[9, 10, 11, 12, 13, 14, 15, 16, 17, 18]. The earlier designs in [9, 10, 11]
provide non-explicit solutions and can be viewed as upper bound results. The
first explicit concentrator was reported in [12] using a binomial sparse
crossbar design with $O(n^{1.5})$ edges. The design given in [13] falls
outside the focus of our work as it is based on binary comparators and
sorters. In this paper, we are concerned with designing classical and quantum
algorithms for a particular set of concentrators that are referred to as fat-
and-slim sparse crossbars. These were introduced in [14] and developed in [15,
16, 17, 18]. We note that concentrators are further refined to study a family
of bipartite graphs, widely-known as expanders[19, 20, 21, 22, 23]. Expanders
provide bounded capacity concentration with $O(n)$ edges. Our work on how to
route concentration assignments in such graphs using quantum algorithms will
be deferred to another place. In this paper, we give classical algorithms to
realize concentration assignments in sparse crossbar concentrators and use
Grover’s search to transform them to quantum algorithms, decreasing their time
complexity. The rest of the paper is organized as follows. The next section
provides the preliminary concepts needed to describe our results. In Section
III, we state our assumptions of classical and quantum models of computation.
Sections IV and V present our main results. The paper is concluded in Section
VI with a discussion of our results and possible directions for future
research.

##  II Sparse Crossbar Concentrators

An $(n,m,c)$-concentrator is a graph with a set of $n$ vertices, called
inputs, a set of $m$ vertices that are disjoint from the set of inputs, called
outputs, and in which a $k$-matching, i.e., a set of $k$ vertex-disjoint paths
exists between every $k$ inputs and some $k$ outputs, $1\leq k\leq c\leq m$.
Such a concentrator is referred to as a bipartite or sparse crossbar
concentrator if all paths are of length one, i.e., each path consists of two
vertices and an edge that is represented by a crosspoint in the fat-and-slim
crossbar model[14]. If $c<m$ then an $(n,m,c)$-concentrator is said to have
bounded capacity111The maximum number of inputs that can be concentrated in
unit time independent of the location of the inputs [24]., and if $c=m,$ it is
said to have full capacity. Henceforth, we will refer to the latter as an
$(n,m)$-concentrator. A concentrator is called explicit if all of its edges
(crosspoints) are specified, inexplicit if all of its edges exist with a non-
vanishing probability other than 1, and semi-explicit if only a proper subset
of its edges is explicitly specified.

Figure 1: An (11, 5) full-capacity, fat-and-slim concentrator.

Numerous explicit, semi-explicit, and inexplicit concentrators have been
described in the literature as mentioned in the introduction. In this paper,
we focus on two explicit concentrator designs introduced in [14] and one
introduced in [16]. The first among these is a bipartite concentrator, called
a full capacity fat-and-slim crossbar in which inputs are divided into two
subsets of size $n-m$ and $m$. Each of the $n-m$ inputs is connected to all
the outputs, and forms the fat-part of the concentrator, whereas each of the
$m$ inputs is connected to exactly one output and forms its slim part. These
concentrators are often diagrammed using a sparse crossbar representation as
shown in Figure 1. As described, the left-hand side forms the fat part, and
the diagonal line on right hand side forms the slim part of the concentrator.
Adding all the crosspoints (edges) together, we find that an fat-and-slim
$(n,m)$-concentrator consists of $(n-m)m+m=(n-m+1)m$ crosspoints, and it was
established in [14] that every bipartite $(n,m)$-concentrator must have at
least $(n-m+1)m$ crosspoints. Therefore, the full-capacity fat-and-slim
concentrator is minimal with respect to the number of crosspoints.

Figure 2: A bounded capacity fat-and-slim $(9,7,2)$-concentrator, which is
also a $(9,7,3)$-concentrator by our extension of its capacity.

The second concentrator is also a sparse crossbar concentrator similar in
concept to a full-capacity fat-and-slim concentrator, but with a bounded
capacity $c$ as illustrated in Figure 2 for $n=9$, $m=7=5$, $c=2$. In this
construction, the left-hand side forms the slim-part, whereas the right hand
side is added to provide a minimum capacity of $c$. This is ensured by
requiring $c\leq m/c$ or $c\leq\sqrt{m}$. The key idea is to provide a
sufficient number of crosspoints (edges) to each input in the right part so
that, if it gets blocked by as many as $c-1$ inputs from the slim part, it can
still find an idle output to match with. Requiring $c\leq m/c$ secures this as
each input in the right part is connected to $\lfloor m/c\rfloor$ outputs. The
constriction also assumes that $n-m\leq c$. This assumption ensures that the
main diagonal of crosspoints in the slim section on the left spans the entire
set of outputs. It was shown in [14] that the crosspoint complexity of this
construction remains with a factor of two of a lower bound of
$\lfloor\frac{(n-c+1)m}{m-c+1}\rfloor$ crosspoints.

We refer the reader to [14] for a more in-depth account of these two
concentrator constructions, while we note that the capacity of the second
sparse crossbar concentrator is actually larger than $c$ when $m/c>c.$ In
fact, the capacity of this crossbar is $\lfloor m/c\rfloor$ as each input in
the fact section is connected to at least $\lfloor m/c\rfloor$ outputs. We
adjust our notation to highlight this observation by replacing $c$ for the
width of the inputs in the fat-section by $q,$ and letting $n-m\leq q\leq m,$
and $c=\lfloor m/q\rfloor.$ Therefore, $c\leq\sqrt{m}$ is no longer required
as described in [14]. For the rest of this paper, this updated construction
will be referred to as “bounded capacity fat-and-slim concentrator”. Thus, we
revise the capacity of the fat-and-slim crossbar in Figure 2 to 3.

In addition to these two concentrators, we will also present a quantum routing
algorithm for a third sparse concentrator that has a more regular
structure[16]. This concentrator uses $n=pm$ inputs and $m$ outputs, and it is
derived from the full-capacity fat-and-slim concentrator. Each output is
connected to $n-m+1$ inputs as in the full-capacity fat-and-slim concentrator.
On the other hand, each input is connected to between $m-\lfloor m/p\rfloor$
and $m-\lfloor m/p\rfloor+1$ outputs, making this $(pm,m)$-concentrator nearly
regular in terms of its in-degree (fan-in) as well. In this paper, we will
consider the case when $p$ divides $m$. Additionally, we only consider cases
when $p\geq 3$. Figure 3 illustrates this construction for $p=3,$ and $m=6$.
It is seen that the out-degree of the construction falls between 4 and 5.
Effectively, this construction is obtained from the full-capacity fat-and-slim
concentrator by (i) dividing $n=pm$ columns of crosspoints into $p$ sections,
(ii) chopping the diagonal of $m$ crosspoints in the slim part into $p$ groups
of $m/p$ columns, and (iii) swapping each of those $m/p$ columns with an equal
number of columns in one of the remaining $p-1$ sections on the left. Using
the notation in [16], we denote the sets of inputs in the $p$ sections by
$I_{j},1\leq j\leq p,$ and let $I_{j}=\\{x_{j,1},x_{j,2},\cdots,x_{j,m}\\}$.
We further let $V_{j}=\cap_{k=1}^{m-1}N(x_{j,k}),$ $U_{j}=O\backslash V_{j},$
and $W_{j}$ denote the set of inputs that are connected to the outputs in
$U_{j},$ where $N(x_{j,k})$ denotes the neighbor set of input $x_{j,k},1\leq
j\leq p,1\leq k\leq m$. In Figure 3,
$V_{1}=\\{z_{3},z_{4},z_{5},z_{6}\\},V_{2}=\\{z_{1},z_{2},z_{5},z_{6}\\},V_{3}=\\{z_{1},z_{2},z_{3},z_{4}\\},U_{1}=\\{z_{1},z_{2}\\},U_{2}=\\{z_{3},z_{4}\\},U_{3}=\\{z_{5},z_{6}\\},W_{1}=\\{x_{1,1},x_{1,2}\\},W_{2}=\\{x_{2,3},x_{2,4}\\},W_{3}=\\{x_{3,5},x_{3,6}\\}$.

The crux of this construction is a transformation theorem proved in [16].

Figure 3: A regular (18,6)-fat-and-slim concentrator.

As we describe in the latter part of Section IV, the construction of this
concentrator makes the design of a classical routing algorithm for it more
involved, but we establish that the time complexity of such an algorithm
remains $O(m)$ once active inputs are located.

##  III Classical Versus Quantum Routing Model

The algorithms presented in this paper will be run on two models of
computation: (III-A) classical model and (III-B) quantum model. It is
important to highlight the differences between these two models to make a
justifiable comparison of their execution times.

###  III-A The Classical Routing Model

In the classical model, we assume that quantities of interest are represented
using classical bits of 0 and 1. For example, we use $\lg n$ bits and $\lg m$
bits to identify the inputs and outputs of an $(n,m)$-concentrator,
respectively. We further assume that the bits within the representation of
each input and/or output can be processed in parallel. For example, we can
inspect all of the bits within a representation of any input (output) in
parallel to determine if it is a particular input we seek, or we can compare
the bits in representations of any two inputs (outputs) or a constant number
of inputs (outputs) in parallel to see if they are the same in $O(1)$ time.
Such bit-level operations can generally be carried out by logic circuits that
consist of elementary logic components such as OR, AND, XOR, XNOR, and NOT
gates that we assume have $O(1)$ computation time, and have a constant fan-in
and fan-out, i.e., they have a constant number of inputs and outputs. We note
that two or a constant number of $\lg n$-bit numbers can be added, subtracted
or compared using $O(\lg n)$ 2-input, 2-output logic gates in $O(\lg\lg n)$
time using a prefix-adder as described in [25]. This $O(\lg\lg n)$ time will
be suppressed in our time complexity formulas, leaving us with $O(1)$ time. It
will also be assumed that $O(\lg n)$-bit operands can be written and read in
and out of a random access memory in $O(1)$ time. We will be using an array
named $in$ to specify if a given input is active. We will assume that $in$ is
an array that is stored in a random access memory with $O(1)$ access time. It
is possible to relax $O(1)$ access time complexity. However, since such a non-
constant access time complexity would be a multiplicative coefficient in the
time complexity of the bottleneck step of both classical and quantum
algorithms, we will omit this factor from our complexity calculations,
effectively assume that the access time of $in$ is $O(1).$

###  III-B The Quantum Routing Model

In the quantum routing model, classical bits are replaced by quantum bits
(qubits), and classical logic gates are replaced by those that represent
unitary transformations. We assume that unitary gates have one or two inputs.
All together, we allow $O(\lg n)$ qubits in the quantum routing model. This
allows us to work with possibly up to $n$ states in parallel. We further allow
any combination of quantum gates to be used on these $O(\lg n)$ qubits, but
with the restriction that each qubit can source only one quantum gate at a
time. This last restriction is a corollary of the no-cloning theorem[26]. This
fanout restriction of one in the quantum routing model is not imposed on the
bits in the classical routing model. However, we still assume that the fanout
of each input is $O(1)$ in the classical model as well. Therefore, the two
models can be viewed to be analogous, where any quantum operation on mutually
exclusive $O(\lg n)$ qubits takes $O(1)$ time much the same way each operation
on $O(\lg n)$ classical bits takes $O(1)$ time. The difference lies in the
amount of parallelism afforded by the two models: in the classical model, we
assume that the parallelism is limited to operations on any given pattern of
$O(\lg n)$ bits, whereas in the quantum routing model, the parallelism
transcends any particular or fixed pattern as quantum operations are applied
to the totality of the quantum state that includes all $O(n)$ binary patterns
of $O(\lg n)$ qubits. This vast amount of parallelism inherently present in
quantum mechanical systems resulted in Shor’s quantum prime number
factorization algorithm[27], which is exponentially faster than the best-known
classical algorithm. Another key quantum algorithm, Grover’s quantum
search[28] provides a speed-up of $O(\sqrt{n})$ over a sequential algorithm to
search an element in an unordered list of $n$ elements. The latter algorithm
will be used in Section V to reduce the routing time of concentration
assignment on fat-and-slim concentrators using quantum algorithms. Before we
describe these algorithms, we provide their classical analogs in the next
section.

##  IV Classical Routing On Concentrators

Routing an assignment on a sparse crossbar concentrator amounts to
constructing a matching between any given subset of inputs and some subset of
outputs of equal cardinality. The particular topologies of the three
concentrators given in Section II guide the design of a routing algorithm for
each concentrator as we describe next.

###  IV-A Full-Capacity Fat-Slim (F-S) Concentrator Routing

Our first algorithm, Algorithm 1 is a restatement of the algorithm that was
originally described in [29] for a full-capacity fat-and-slim concentrator. We
recall from Section II that the set of inputs is partitioned into two sets:
those in the fat section: $X=\\{x_{1},x_{2},\cdots\\!,x_{n-m}\\}$ and those in
the slim section: $Y=\\{y_{1},y_{2},\cdots\\!,y_{m}\\}$. The set of outputs of
the concentrator is denoted by $Z=\\{z_{1},z_{2},\cdots\\!,z_{m}\\}$.

Algorithm 1 Classical Full-Capacity F-S Concentration

1:function Classical Full FS Route($in,n,m$)
//$in$: $n$-bit array that marks up to $m$ active inputs
//$n$: number of inputs.
//$m$: number of outputs.

2: $L\leftarrow list()$

3: for $i\leftarrow 1:m$ do //slim section

4: if $in[m-n+i]==1$ then

5: $pair(y_{i},z_{i});$

6: else

7: $L.insert(z_{i});$

8: end if

9: end for

10: for $i\leftarrow 1:n-m$ do //fat section

11: if $in[i]==1$ then

12: $\\{z=L.remove();pair(x_{i},z);\\}$

13: end if

14: end for

15:end function

As we stated in the earlier section, the active inputs in a routing request,
i.e., those to be concentrated are specified by ‘1’ entries in an $n$-bit
array, named in. A routing request with $k$ active inputs is first completed
to a request with $m$ inputs by combining the leftmost unused $m-k$ inputs in
$in$ with the given $k$ active inputs. Moreover, the leftmost $m-k$ unused
inputs in $in$ can be determined in $O(m)$ time by examining the leftmost $m$
inputs of $in$.

Effectively, the first for loop assigns each active input in the slim section
to the output with the same index value, while also inserting each unused
output $z_{i}$ into a list $L$ of $m$ elements as it checks if input
$y_{i},1\leq i\leq m$ is active. The second for loop then assigns the active
inputs from left to right in the fat section to the unused outputs, i.e.,
those that are inserted into $L$ from top to bottom.

The time complexity of Algorithm 1 is easily seen to be $O(n)$ steps, given
that (i) each iteration in the first loop involves checking if a bit in the
list $in$ is ‘1’, pairing an input in the slim-section with an output or
inserting a value into a list of $m$ elements, and (ii) each iteration in the
second loop involves checking a bit, pairing an input in the fat-section with
an output, and removing an output from the list $L$. Checking if $in[i]==1$
clearly takes $O(1)$ time. It is further assumed that pairing an input and
output as well as inserting or removing a value in and out of a list also
takes $O(1)$ time. This is a reasonable assumption, considering that all three
operations involve no more than a basic memory read or write operation.

###  IV-B Bounded Capacity Fat-Slim Concentration Routing

Algorithm 2 extends the main idea of Algorithm 1 to routing active inputs in a
bounded capacity fat-and-slim concentrator222Even though we refer to this
construction as a bounded capacity, fat-and-slim concentrator, the fat section
on the right is not completely filled with crosspoints as in the case of full-
capacity fat-and-slim concentrator.. As in Algorithm 1, the inputs are divided
into fat and slim sections, but this time, the slim section is placed on the
left and the pseudo-fat section is placed on the right in Figure 2. An $m$-bit
array, named out is added to mark the outputs. The first for loop pairs the
active inputs in the slim section with outputs whose indices coincide with
those of the active inputs, while marking those outputs by entering ‘0’s into
out in their index positions. The second for loop finds the active inputs in
the pseudo-fat section on the right. The last nested loop pairs the active
inputs in the pseudo-fat section on the right by searching for an available
output from among the set of outputs to which each active is connected by a
crosspoint.

Algorithm 2 has an execution time of $O(n)=O(m)$.

  1. 1.

Lines 2-6 take $O(m)$ time as they involve steps to check if $in[i]=1,$ pair
$x_{i}$ with $z_{i},$ and clear a bit in the $out$ array.

  2. 2.

Lines 7-12 take $O(q)$ time as they involve checking $q$ array elements and
adding them to a list.

  3. 3.

Lines 13-20 consist of a nested loop that takes $O(c)$ time. To see this, let
$c^{\prime},0\leq c^{\prime}\leq c,$ be the number of active inputs found in
lines 2-6. In line 17, we exit the interior for loop. This happens when an
available output is found for that input. The number of unsuccessful checks
for an available output can at most be $c^{\prime}$ and successful checks for
such an output can at most be $c$. Since the number of elements in the list
$L$ is also bounded by $c$, this nested loop takes $O(c)$ time.

Algorithm 2 Classical Bounded Capacity F-S Concentration

1:function Classical Bounded F-S Route($in,n,m,q$)
//$in$: $n$-bit array that marks up to $c$ active inputs.
//$n$: number of inputs.
//$m$: number of outputs.
//$q$: the width of the fat section.
//$c=\lfloor m/q\rfloor$: capacity.
//$out$: $m$-bit array that marks available outputs (initialized to all 1’s).

2: for $i\leftarrow 1:n-q$ do //slim section

3: if $in[i]==1$ then

4: $pair(x_{i},z_{i});$ $out[i]\leftarrow 0;$

5: end if

6: end for

7: $L\leftarrow list()$ //pseudo-fat section

8: for $i\leftarrow 1:q$ do

9: if $in[i+m]==1$ then

10: $L.insert(i);$

11: end if

12: end for

13: while $i\leftarrow L.remove()$ do

14: for $j\leftarrow 0:c-1$ do

15: if $out[i+qj]==1$ then

16: $pair(y_{i},z_{i+qj});$

17: break

18: end if

19: end for

20: end while

21:end function

###  IV-C Regular Fat-Slim Concentration Routing

Our third classical algorithm restates the one given in [29] with a tighter
time complexity analysis on some steps. This time, we have a sparse crossbar
construction with $n=pm$ inputs and $m$ outputs as described in Section II,
where we assume that $p$ divides $m$. A routing request with $k$ active inputs
is first completed to a request with $m$ inputs by combining the first unused
$m-k$ inputs in $I_{1}$ with the given $k$ active inputs. This is always
possible since if all $k\leq m$ active inputs belong to $I_{1}$ then its
remaining $m-k$ inputs can be combined with the $k$ active inputs to obtain an
$m$-request. On the other hand, if only some $k^{\prime}<k\leq m$ of the $k$
active inputs belong to $I_{1}$ then $I_{1}$ must have $m-k^{\prime}>m-k$
unused inputs, the first $m-k$ of which can be combined with the given $k$
active inputs to obtain an $m$-request. Moreover, the first $m-k$ unused
inputs in $I_{1}$ can be determined in $O(m)$ time by examining all $m$ inputs
in $I_{1}$ in the worst case333The selection of $I_{1}$ is arbitrary and
simplifies our description for the completion of a $k$-assignment to an
$m$-assignment. The algorithm will work regardless of which set of inputs
selected.. Therefore, we will assume that a $k$-request is completed to an
$m$-request and specified by an array of $n$-bits named $in$, in which 0 and 1
bits represent the absence and presence of an active input respectively. At
the beginning of the algorithm, the locations of these active inputs are
searched and active inputs in $I_{j}=\\{x_{j,1},x_{j,2},\ldots,x_{j,m}\\}$ are
placed in a linked list $R_{j},1\leq i\leq p$.

Algorithm 3 routes an $m$-request by considering two distinct cases: (a) One
of the $R_{j}$’s has more than $m-m/p$ active inputs. (b) None of $R_{j}$’s
has more than $m-m/p$ active inputs. That there can be no other case for all
$p\geq 2$ is shown as follows. Suppose there exists $R_{j}$ with more than
$m-m/p$ active inputs, for some $j$. Then there remain less than
$m-(m-m/p)=m/p$ active inputs in the union of all the remaining $p-1$ sets of
$m$ inputs. Therefore, another $m$-bit array, i.e., $R_{j^{\prime}}$ for some
$j^{\prime}\neq j,1\leq j^{\prime}\leq p$ with more than $m-m/p$ active inputs
exists only if $m/p>m-m/p,$ which implies $p<2$ or $p=1,$ contradicting our
assumption that $p\geq 2$ as stated in Section II.

Now, continuing with Algorithm 3, lines 1 through 8 construct the linked lists
in $O(n)$ time, assuming that we have $m$ active inputs as described above and
determine the number of entries in each linked list by incrementing a size
field each time an active input is found. Next, we see that the for statement
in line 9 is iterated at most $p$ times, which occurs either when none of
$R_{j},1\leq j\leq p$ has more than $m-m/p$ active inputs or $R_{p}$ does.
During the $j$th iteration, the if statement in line 10 checks if $R_{j}$ has
more than $m-m/p$ 1’s. The size of each set can be queried in $O(1)$ time with
the help of the size field that has been computed in line 5.

Case (a): If there exists such an $R_{j}$ then line 11 pairs all the active
inputs in $R_{j}\cap W_{j},$ if any, and the outputs in $U_{j}$ to which those
active inputs are connected by crosspoints. Line 12 then pairs as many active
inputs in $R_{i},1\leq i\neq j\leq p$ as possible, if any, with unused outputs
in $U_{j}$. At this point, any active remaining inputs in $R_{i},1\leq i\neq
j\leq p$, are paired with unused outputs in $U_{l},l\neq j$ in lines 13 and
14. This pairing is implemented in such a way that one of the $U_{i},1\leq
i\neq j$ is arbitrarily fixed ($U_{j-1}$ in the algorithm) to start the
pairing. It is possible that $U_{j-1}$ may not even have an active input, but
line 13 serves to initiate pairing of the active inputs in the remaining
subsets of inputs other than $I_{j}$. We note that the number of active inputs
in $I_{j-1}$ is less than $m/p=|U_{j+1}|$ and a full crossbar connection
exists between $I_{j-1}$ and $U_{j+1}$. Similarly, in line 14, it is always
possible to pair the number of active inputs in
$\\!\\!\\!\\!\\!\bigcup\limits_{\begin{subarray}{c}i\neq j,i\neq
j-1\end{subarray}}\\!\\!\\!\\!\\!\\!I_{k}$ with the outputs in $U_{j-1}$ as
$U_{j-1}$ has $m/p$ available outputs, which are more numerous than the active
inputs in $\\!\\!\\!\\!\\!\bigcup\limits_{\begin{subarray}{c}i\neq j,i\neq
j-1\end{subarray}}\\!\\!\\!\\!\\!\\!I_{k}$, and a full crossbar connection
exists between the two sets. Here, the indexing is cyclical, and it is assumed
that $j$, $j-1,$ and $j+1$ are distinct from each other and $p\geq 3$. If
$p=2$ then line 14 is not needed. Finally, any remaining inputs in $R_{j}$ are
paired with the remaining unused outputs in $V_{j}$ in line 15 as there is a
full crossbar connection between the inputs in $I_{j}$ and outputs in
$V_{j},1\leq j\leq p$.

Algorithm 3 Classical Regular F-S Concentration

1:function Classical Regular F-S Route($in,p,m$)
//$in$: $n$-bit array that marks up to $m$ active inputs.
//$n=m*p$: number of inputs.
//$R_{j},1\leq j\leq p$: linked lists of active inputs.
//$m$: number of outputs.
//The size fields of $R_{j},1\leq j\leq p$ are cleared.

2: for $j\leftarrow 1:p$ do

3: for $i\leftarrow 1:m$ do //find active elements

4: if $in[(j-1)m+i]==1$ then

5: $R_{j}.insert(i);R_{j}.size\scriptstyle{+\\!+}$

6: end if

7: end for

8: end for

9: for $j\leftarrow 1:p$ do

10: if $R_{j}.size>m-m/p$ then //case (a)

11: Pair inputs in $R_{j}\cap W_{j}$ with outputs in $U_{j};$

12: Pair inputs in $\\!\\!\underset{i\neq j}{\cup}R_{i}$ with unpaired outputs
in $U_{j};$

13: Pair unpaired inputs in $R_{j-1}$ with outputs in $U_{j+1};$

14: Pair unpaired inputs in $\\!\\!\underset{i\neq j,i\neq
j-1}{\cup}\\!\\!R_{i}$ with outputs in $U_{j-1};$

15: Pair unpaired inputs in $R_{j}$ with unpaired outputs in $V_{j};$

16: return

17: else //case (b)

18: $a[j]\leftarrow(m/p\leq|R_{j}|);$ //$p$-bit array for reindexing

19: end if

20: end for

21: $r\leftarrow$ prefixSum$(a);$ $s\leftarrow$ prefixSum$(\neg a);$

22: $d[j]\leftarrow a[j]r[j]+(\neg a[j])(s[j]+r[p]);{1\leq j\leq p;}$ //new
indices

23: $R^{\prime}_{d[j]}\leftarrow R_{j}$; $U^{\prime}_{d[j]}\leftarrow
U_{j},1\leq j\leq p;$

24: for $j\leftarrow 2:r[p]$ do

25: Take first $m/p$ elements from $R^{\prime}_{j}$ and place them in
$P^{\prime}_{j};$

26: Pair inputs in $P^{\prime}_{j}$ with outputs in $U^{\prime}_{j-1};$

27: $Q^{\prime}_{j}\leftarrow R^{\prime}_{j}\backslash P^{\prime}_{j};$

28: end for

29: Pair inputs in
$R^{\prime}_{r[p]+1},R^{\prime}_{r[p]+2},...,R^{\prime}_{p},R^{\prime}_{1},Q_{2},Q_{3},...,Q_{r[p]}$

30: with outputs in $U^{\prime}_{r[p]},$
$U^{\prime}_{r[p]+1},...,U^{\prime}_{p};$

31:end function

These steps are illustrated in Figure 4, where the circled numbers identify
the steps in the algorithm. In this example, lines 13 and 14 do not result in
any pairing. As another example, let $m=12,p=3,$
$R_{1}=\\{1,2,3,5,6,7,8,9,10\\}$, $R_{2}=\\{3,8\\}$, $R_{3}=\\{1\\}$. We have
$U_{1}=\\{z_{1},z_{2},z_{3},z_{4}\\},U_{2}=\\{z_{5},z_{6},z_{7},z_{8}\\},U_{3}=\\{z_{9},z_{10},z_{11},z_{12}\\},$
and $|R_{1}|=9>8=m-m/p$. Thus, $x_{1,1},x_{1,2},x_{1,3}$ are paired with
$z_{1},z_{2},z_{3}$ in $U_{1}$ in line 11, $x_{2,3}$ is paired with $z_{4}$ in
$U_{1}$ in line 12, $x_{3,1}$ in $I_{3}$ is paired with output $z_{5}$ in
$U_{2}$ and the remaining active input $x_{2,7}$ in $I_{2}$ is paired with
output $z_{9}$ in $U_{2}$ in lines 13 and 14. Finally,
$x_{1,5},x_{1,6},x_{1,7},x_{1,8},x_{1,9},x_{1,10}$ are paired with the
remaining outputs all of which belong to $V_{1}$. We established that any
routing request in case (a) can always be realized in lines 11 through 15. Now
suppose that the condition $|R[j]|>m-m/p$ fails for all $j,1\leq j\leq p$. The
remaining part of the algorithm handles case (b) as described next.

Case (b): First, in line 17, we initiate a process to identify the subsets of
inputs with at most $m/p$ active inputs. This is done to reindex the sets of
inputs $I_{j},1\leq j\leq p$ so that those that have between $m/p$ and $m-m/p$
active inputs are given lower index values. Effectively, the $R_{j}$’s and the
corresponding $U_{j}$’s are implicitly sorted in descending order, based on
whether they contain more than the threshold of $m/p$ active inputs. To
facilitate this, we follow the approach in [29] and form a bit-array of $p$
elements, $a$ in line 18 such that $a[j]=1$ if and only if $m/p\leq|R_{j}|\leq
m-m/p,1\leq j\leq p$. This array is used to split $R_{j}$ into two groups,
those for which $m/p\leq|R_{j}|\leq m-m/p$ and those for which $|R_{j}|<m/p$.
This splitting is carried out by computing the prefix sums of the bits in $a$
and $\neg a$ into two $p$-element arrays $r$ and $s$ in line 21, where $r$
ranks those $R_{j}$ for which $m/p\leq|R_{j}|\leq m-m/p,$ and $s$ ranks those
$R_{j}$ for which $|R_{j}|<m/p$. The ranks index the active inputs in each
group separately. The ranks are threaded together in line 22 to obtain a
$p$-element array, $d$, which represents a permutation of the indices of
$R_{j}$. This step essentially involves selecting one of $r[j]$ or $r[p]+s[j]$
into $d[j]$ and is used to compute the indices of $R_{j}$’s. It is not
difficult to see that $d$ is a permutation of the indices of $R_{j}$’s and
applying $d$ to the indices of $R_{j}$’s and $U_{j}$’s amounts to renaming
them so that $R_{j}$ becomes $R_{d[j]}$ and $U_{j}$ becomes $U_{d[j]},1\leq
j\leq p$. For clarity, we replace $R_{d[j]}$ and $U_{j}$ by
$R^{\prime}_{d[j]}$ and $U^{\prime}_{j}$ in the algorithm.

As an example, let $m=20,p=5,$ and suppose that
$I_{1},I_{2},I_{3},I_{4},I_{5}$ have $3,4,6,5,2$ active inputs, respectively.
Given that $m/p=5,m-m/p=20-20/5=16,$ $|I_{1}|,|I_{2}|,|I_{5}|<m/p$ and
$m/p<|I_{3}|,|I_{4}|\leq m-m/p$ so that $a=[0,0,1,1,0],\neg a=[1,1,0,0,1],$
$r=[0,0,1,2,2],s=[1,2,2,2,3],d=ar+(\neg
a)(r[p]+s)=[0,0,1,2,0]+[3,4,0,0,5]=[3,4,1,2,5]$. Thus,
$R^{\prime}_{3}\leftarrow R_{1},U^{\prime}_{3}\leftarrow
U_{1},R^{\prime}_{4}\leftarrow R_{2},U^{\prime}_{4}\leftarrow
U_{2},R^{\prime}_{1}\leftarrow R_{3},U^{\prime}_{1}\leftarrow
U_{3},R^{\prime}_{2}\leftarrow R_{4},U^{\prime}_{2}\leftarrow
U_{4},R^{\prime}_{5}\leftarrow R_{5},U^{\prime}_{5}\leftarrow U_{5}$. This
gives a permuted set of registers in descending cardinalities, i.e.,
$R^{\prime}_{3},R^{\prime}_{4},R^{\prime}_{1},R^{\prime}_{2},R^{\prime}_{5}$
and
$U^{\prime}_{3},U^{\prime}_{4},U^{\prime}_{1},U^{\prime}_{2},U^{\prime}_{5}$.

Once this sorting process is completed in line 23, we select the first $m/p$
active inputs in each of the $r[p]$ sets in which the number of active inputs
lies between $m/p$ and $m-m/p-1,$ and store all, but the first $m/p$ active
inputs into $P^{\prime}_{j},2\leq j\leq r[p]$ in line 25.

Figure 4: Routing in a regular (18,6)-fat-and-slim concentrator.

These active inputs are paired with sets of $m/p$ outputs in
$U^{\prime}_{j-1},2\leq j\leq r[p]$ in line 26 using the full crossbar
connection between them. This will complete the pairing of $(r[p]-1)m/p$
active inputs and $m-(r[p]-1)m/p=(p-r[p]+1)m/p$ active inputs remain.

The remaining active inputs in $R^{\prime}_{j}$ are saved into
$Q^{\prime}_{j},2\leq j\leq r[p]$ in line 27. Finally, the active inputs in
$Q_{j}$’s are concatenated with the active inputs in
$\\!R_{r[p]+1},R_{r[p]+2},...,R_{[p]},R_{1}$ which are then paired together
with the outputs in sets
$U^{\prime}_{r[p]+1},U^{\prime}_{r[p]+2},...,U^{\prime}_{p}$ in line 30. Note
that the number of active inputs in
$R^{\prime}_{r[p]+1},R^{\prime}_{r[p]+2},...,R^{\prime}_{p},R^{\prime}_{1},Q_{2},Q_{3},...,Q_{r[p]}$
is given by $(p-r[p]+1)m/p$ and it must match the number of active outputs in
in $U^{\prime}_{r[p]},$ $U^{\prime}_{r[p]+1},...,U^{\prime}_{p}$ after the
pairing in line 26.

Algorithm 3 has a time complexity of $O(n)$ as shown below.

  1. 1.

Lines 2-8: This is a linear search of active inputs out of $n$ inputs, and
therefore has a time complexity of $O(n)$.

  2. 2.

Lines 9-30: By the time we get to these lines, we already know where the
active inputs are located because $\\!R_{j}$’s consist only of active inputs.
At this point the only task left to do is to route these active inputs. We
route in two different ways as described in cases (a) and (b) in the
algorithm. Both take $O(m)$ time as described below.

    1. (a)

Lines 9 and 10: We see that the for statement here is iterated at most $p$
times, which occurs either when none of $R_{j},1\leq j\leq p$ has more than
$m-m/p$ active inputs or $R_{p}$ does. During the $j$th iteration, the if
statement in line 10 checks if $R_{j}$ has more than $m-m/p$ elements. Since
we can query the size of sets in $O(1)$ time and comparison of values in the
if statement can also be completed in $O(1)$ time, this line has a time
complexity of $O(p)$.

    2. (b)

Lines 11-16: In case (a), there are more active inputs than non-diagonals can
handle alone, and therefore diagonal crosspoints must be used. These lines
execute at most once and take $O(m)$ time as explained below.

      1. i.

Line 11 can be done by iterating through $R_{j}$ and checking if the current
element is in $W_{j}$. Since $W_{j}$ is an interval where endpoints are fixed
and known, the membership decision amounts to the comparison of the current
element against the two endpoints, and this takes $O(1)$ time in our classical
bit-parallel processor model. Moreover, the number of pairing operations is
clearly bounded by $|W_{j}|=|U_{j}|=m/p,$ and pairing an active input with the
corresponding output in $U_{j}$ takes $O(1)$ time. Therefore, this line can be
done in $O({\rm max}(m,m/p))=O(m)$ time, the size limit of $R_{j}$.

      2. ii.

Line 12: Let $\hat{R}=\underset{i\neq j}{\cup}R_{i}$. Given that all inputs in
$\hat{R}$ are connected to outputs in $U_{j}$ by a full crossbar connection,
the active inputs in $\hat{R}$ can be paired with unused outputs in $U_{j}$ by
scanning $\hat{R}$ from left to right and $U_{j}$ from top to bottom until all
unused outputs in $U_{j}$ are paired. As we represent $R_{j},1\leq j\leq p$ by
linked lists and since there are $m$ active inputs at the most, the pairing
can be completed in $O(m$) time in this case.

      3. iii.

In line 13 we pair two sides of a full crossbar connection, i.e., inputs in
$R_{j-1}$ and outputs in $U_{j+1}$. We loop through these sets, removing one
element from each to build a complete matching. Given that $|R_{j-1}|\leq
m,2\leq j\leq m+1,$ and $|U_{j+1}|=m/p,$ this line has a time complexity of
$O(m)$.

      4. iv.

In line 14, we proceed as in line 12, and note that $|\\!\\!\underset{i\neq
j,i\neq j-1}{\cup}\\!\\!\\!\\!R_{i}|\\!\leq\\!m$. Therefore this line has a
time complexity of $O(m)$.

      5. v.

Line 15 involves connecting the remaining active inputs in $I_{j}$ and the
unused outputs in $V_{j}$. It is not difficult to verify that this step can be
completed in $O(m-m/p)$ time as there is a full crossbar connection between
the inputs in $R_{j}$ and $V_{j},1\leq j\leq p$. It follows that the time
complexity of the for loop is $O(m-m/p)$.

    3. (c)

Lines 17-30: These lines are carried out in case (b) only. In this case, non-
diagonal crosspoints can handle the assignment without diagonal crosspoints.
Therefore, only the fat sections are used in the routing and these lines can
be done in $O(m)$ time as explained below.

      1. i.

Line 18 involves querying size of $R_{j}$ and comparing it to $m/p$, which can
be completed in $O(1)$ time per each iteration of the for loop and in $O(p)$
time for all iterations.

      2. ii.

Line 21 has prefix sum of $p$ elements that can be done in $O(p)$ time by an
iterative summation of $p$ bits.

      3. iii.

Line 22 involves an addition of two $O(\lg p)$-bit numbers and a $2\times 1$
multiplexer, both of which take $O(1)$ time and so the loop in this line takes
$O(p)$ time.

      4. iv.

Line 23 involves reindexing of $R_{j}$’s, which clearly takes $O(p)$ time.

      5. v.

Lines 24-27 can be carried out in $O(m/p)$ time per each set of $m/p$ inputs
and in $O(r[p]\times m/p)=O(m)$ time for all $r[p]$ sets of $m/p$ inputs.

      6. vi.

Lines 29-30 can be done by pairing the elements between the two sets described
in these lines one by one in $O(m)$ time.

######  Remark 1.

Algorithm 1, Algorithm 2 and Algorithm 3 are all optimal in terms of order of
execution time as it takes $\Omega(n)$ time to read a concentration
assignment.∎

##  V Quantum Routing-Grover’s Search

Now that we have established that classical routing algorithms all take $O(n)$
time for full and bounded capacity fat-and-slim concentrators described in
Section II, we turn our attention to quantum routing for them. Since both
these concentrators require searching of active inputs out of all inputs,
Grover’s search [28] provides a possible approach to identify such inputs
faster in the quantum domain. Grover’s search approach has been followed to
speed up various matching and network flow problems in [4] and [6]. These two
papers were among the inspirations for our approach. We will use the version
of Grover’s search analyzed in Theorem 3 of [30] and refer to it as
GroverSearch in this paper. We note that GroverSearch is the only quantum step
in the algorithms to be presented in this section and rest of the paper. The
time complexity of GroverSearch is known to be $O(\sqrt{n/k})$ to find one of
$k$ marked items out of $n$ possible items. Thus, it takes $O(\sqrt{nk})$ time
to discover all $k$ items by unmarking discovered items one at a time. This is
a widely used method even though the original source is unknown. The proof can
be found in Lemma 4.1 of [31].

######  Remark 2.

As in [4] and [6], we use Monte Carlo amplification to bound the total error
of the entire algorithm resulting in an increase in run-time that is a
logarithmic factor in the number of calls to the quantum subroutine, i.e.,
$\ln k$. Therefore, the time to discover all marked inputs is
$O(\sqrt{nk}\ln{k})$. ∎

Algorithm 4 Quantum Full F-S Concentration

1:function Quantum Full FS Route($in,n,m$)
//$in$: $n$-bit array that marks up to $m$ active inputs
//$n$: number of inputs.
//$m$: number of outputs.

2: $L\leftarrow list()$

3: for $i\leftarrow 1:m$ do //slim section

4: if $in[m-n+i]==1$ then

5: $pair(y_{i},z_{i});$

6: else

7: $L.insert(z_{i});$

8: end if

9: end for

10: while $i\leftarrow GroverSearch(in[1:n-m])$ do//fat section

11: $z=L.remove();pair(x_{i},z);$

12: $in[i]=0$

13: end while

14:end function

###  V-A Quantum Full-Capacity F-S Concentration

The pseudo-code of our routing algorithm for the full-capacity fat-and-slim
concentrator is given in Algorithm 4. As in the classical case, this algorithm
consists of two parts. In the first part, we route all the active inputs to
corresponding outputs in the slim section. We also make a list of idle inputs
in this part to identify the corresponding outputs that are not used by the
inputs in the slim section. Such outputs are then paired with the active
inputs that are found by GroverSearch in the second part of the algorithm.
This part of the algorithm is classical and deterministic. The second part of
the algorithm provides us with quantum speedup. We use GroverSearch to locate
the active inputs in the fat part of the concentrator. Once an active input is
found, we pair it with one of the idle outputs that were found in the first
part and unmark that input for another round of GroverSearch.

The time complexity of Algorithm 4 is computed as follows. First note that the
slim part of the algorithm is classical and deterministic. Since we assume
that each query of the array $in$ requires a constant time, identifying the
active inputs, assigning them to their respective outputs, and also
identifying the unused outputs in the slim part takes $O(m)$ time. Now, let
$k$ be the number of active inputs in the fat part. It is obvious that $k$ is
upper bounded by $m$. Hence by Remark 2, we find that the total time required
for the fat part is $O(\sqrt{m(n-m)}\ln m)$. Therefore the total time
complexity of concentration in a full-capacity, fat-and-slim
$(n,m)$-concentrator is $O(m+\sqrt{k(n-m)}\ln m)=O(m+\sqrt{nm}\ln m)$, and
hence, given that $n\geq m,$ the total time complexity is $O(\sqrt{nm}\ln m),$
using a quantum processor with $O(\ln n)$ qubits. For comparison, any
classical-bit processor routing algorithm for a full capacity, fat-and-slim
$(n,m)$-concentrator takes $\Theta(n)$ time as we established in the earlier
section (See Remark 1). When $n=\Theta(m\ln^{2}m)$, we have $O(\sqrt{nm}\ln
m)=O(n)$. Therefore, our algorithm performs better in quantum domain than any
known classical algorithm if $m\ln^{2}{m}=o(n)$. One such value of $m$ is
clearly $\Theta(\sqrt{n})$. In general, it can easily be shown that
$m=n^{\mu},$ satisfies $m\ln^{2}m=o(n)$, for any $\mu,0<\mu<1,$ and the time
complexity of our algorithm will increase less than linearly with $n$ for such
values of $m$.

###  V-B Quantum Bounded-Capacity F-S Concentration

The time complexity of the classical routing algorithm for a bounded capacity
fat-and-slim concentrator can also be reduced using quantum search as well, as
described in Algorithm 5. The slim section of the algorithm finds at most $c$
marked elements out of at most $m$ total elements since $n-q\leq m$.
Similarly, the fat section of the algorithm also finds $c$ marked elements out
of at most $m$ total elements since $q\leq m$. The total time complexity of
both parts is $O(\sqrt{mc}\ln{c})$. Lines 12-19 is the same as 13-20 of
Algorithm 2. Therefore, the total time complexity is also
$O(\sqrt{mc}\ln{c})=O(\sqrt{nc}\ln{c})$. Once again, this algorithm perform
better than it’s classical counterpart when $c\ln^{2}{c}=o(n)$.

Algorithm 5 Quantum Bounded FS Concentration

1:function Quantum Sparse FS Route($in,n,m,q$)
//$in$: $n$-bit array that marks up to $c$ active inputs.
//$n$: number of inputs.
//$m$: number of outputs.
//$q$: the width of the fat section.
//$c=\lfloor m/q\rfloor$: capacity.
//$out$: $m$-bit array that marks available outputs (initialized to all 1’s).

2: while $i\leftarrow GroverSearch(in[1:n-q])$ do //slim section

3: $pair(x_{i},z_{i});$

4: $in[i]\leftarrow 0;$

5: $out[i]\leftarrow 0;$

6: end while

7: $L\leftarrow list();$ //pseudo-fat section

8: while $i\leftarrow GroverSearch(in[n-q+1:n])$ do //slim section

9: $L.insert(i);$

10: $in[i]\leftarrow 0;$

11: end while

12: while $i\leftarrow L.remove()$ do

13: for $j\leftarrow 0:c-1$ do

14: if $out[i+qj]==1$ then

15: $pair(y_{i},z_{i+qj});$

16: break

17: end if

18: end for

19: end while

20:end function

######  Remark 3.

In full capacity F-S concentrator, active inputs for the dense part are
located with Grover’s Search while for bounded capacity FS concentrator, all
active inputs are located with Grover’s Search. ∎

###  V-C Quantum Regular FS Concentration

Our last quantum algorithm handles concentration assignments for regular fat-
and-slim concentrators. It is obtained by replacing the search for active
inputs by GroverSearch. From the analysis in subsection IV-C we know that once
the active inputs are found, the routing takes $O(m)$. Just like full capacity
fat-and-slim concentrator, the search as well as the total time takes
$O(\sqrt{nm}\ln{m})$. Therefore the analysis done in subsection V-A also
applies here.

Algorithm 6 Quantum Regular F-S Concentration

1:function Quantum Regular F-S Route($in,p,m$)
//$in$: $n$-bit array that marks up to $m$ active inputs.
//$n=m*p$: number of inputs.
//$R_{j},1\leq j\leq p$: linked lists of active inputs.
//$m$: number of outputs.
//The size fields of $R_{j},1\leq j\leq p$ are cleared.

2: while $(i,j)\leftarrow GroverSearch(in)$ do

3: $R_{j}.insert(i);R_{j}.size\scriptstyle{+\\!+}$

4: end while

5: for $j\leftarrow 1:p$ do

6: if $R_{j}.size>m-m/p$ then //case (a)

7: Pair inputs in $R_{j}\cap W_{j}$ with outputs in $U_{j};$

8: Pair inputs in $\\!\\!\underset{i\neq j}{\cup}R_{i}$ with unpaired outputs
in $U_{j};$

9: Pair unpaired inputs in $R_{j-1}$ with outputs in $U_{j+1};$

10: Pair unpaired inputs in $\\!\\!\underset{i\neq j,i\neq
j-1}{\cup}\\!\\!R_{i}$ with outputs in $U_{j-1};$

11: Pair unpaired inputs in $R_{j}$ with unpaired outputs in $V_{j};$

12: return

13: else //case (b)

14: $a[j]\leftarrow(m/p\leq|R_{j}|);$ //$p$-bit array for reindexing

15: end if

16: end for

17: $r\leftarrow$ prefixSum$(a);$

18: $d[j]\leftarrow a[j]r[j]+(\neg a[j])(s[j]+r[p]);{1\leq j\leq p;}$ //new
indices

19: $R^{\prime}_{d[j]}\leftarrow R_{j}$

20: for $j\leftarrow 2:r[p]$ do

21: Take first $m/p$ elements from $R^{\prime}_{j}$ and place them in
$P^{\prime}_{j};$

22: Pair inputs in $P^{\prime}_{j}$ with outputs in $U^{\prime}_{j-1};$

23: $Q^{\prime}_{j}\leftarrow R^{\prime}_{j}\backslash P^{\prime}_{j};$

24: end for

25: Pair inputs in
$R^{\prime}_{r[p]+1},R^{\prime}_{r[p]+2},...,R^{\prime}_{p},R^{\prime}_{1},Q_{2},Q_{3},...,Q_{r[p]}$

26: with outputs in $U^{\prime}_{r[p]},$
$U^{\prime}_{r[p]+1},...,U^{\prime}_{p};$

27:end function

##  VI Conclusions and Future Work

We have presented three quantum algorithms, all with smaller time complexity
as compared to their classical counterparts. For full-capacity fat-and-slim
concentrator, our quantum algorithm has a time complexity of $O(\sqrt{nm}\log
m)$ versus the classical routing algorithm complexity of $O(n)$. Thus, in this
case, our quantum algorithm has a smaller time complexity if
$m=n^{\mu},0<\mu<1$. For regular fat-and-slim and bounded-capacity fat-and-
slim concentrators, similar speed-up formulas apply as established in the
paper. It should be noted in both classical and quantum domains, search
process can be speeded up by replicating computational resources. In the case
of a classical search algorithm, using $k$ processors results in a factor of
$k$ reduction in time complexity from $O(n)$ to $O(n/k)$. On the other hand,
in the quantum domain, this reduction in time will be limited to a factor
$\sqrt{k}$. Thus, the separation in time complexities between the classical
and quantum domains become more pronounced only when $k$ is small.

As for future research, we will investigate the possibility of quantum
accelerations for other concentrator architectures and explore other quantum
algorithms such as quantum walk in our research. Another related problem where
a similar approach might be helpful is routing on packet switching networks.
These and other related problems will be further explored in another paper.

## References

  * [1] A. M. Childs and W. Van Dam, “Quantum algorithms for algebraic problems,” _Reviews of Modern Physics_ , vol. 82, no. 1, p. 1, 2010.
  * [2] M. Mosca, “Quantum algorithms,” _arXiv preprint arXiv:0808.0369_ , 2008.
  * [3] A. Montanaro, “Quantum algorithms: an overview,” _npj Quantum Information_ , vol. 2, no. 1, pp. 1–8, 2016.
  * [4] A. Ambainis and R. Špalek, “Quantum algorithms for matching and network flows,” in _Annual Symposium on Theoretical Aspects of Computer Science_. Springer, 2006, pp. 172–183.
  * [5] A. Ambainis, “Quantum walk algorithm for element distinctness,” _SIAM Journal on Computing_ , vol. 37, no. 1, pp. 210–239, 2007.
  * [6] S. Dörn, “Quantum algorithms for matching problems.” _Theory Comput. Syst._ , vol. 45, no. 3, pp. 613–628, 2009.
  * [7] A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential algorithmic speedup by a quantum walk,” in _Proceedings of the thirty-fifth annual ACM symposium on Theory of computing_ , 2003, pp. 59–68.
  * [8] M. S. Pinsker, “On the complexity of a concentrator,” in _7th International Telegraffic Conference_ , vol. 4. Citeseer, 1973, pp. 1–318.
  * [9] N. Pippenger, “Superconcentrators,” _SIAM Journal on Computing_ , vol. 6, no. 2, pp. 298–304, 1977.
  * [10] F. Chung, “On concentrators, superconcentrators, generalizers, and nonblocking networks,” _The Bell System Technical Journal_ , vol. 58, no. 8, pp. 1765–1777, 1979.
  * [11] L. Bassalygo, “Asymptotically optimal switching circuits,” _Problems of Information Transmission_ , vol. 17, no. 3, pp. 206–211, 1981.
  * [12] S. Nakamura and G. M. Masson, “Lower bounds on crosspoints in concentrators,” _IEEE Transactions on Computers_ , no. 12, pp. 1173–1179, 1982.
  * [13] M. V. Chien and A. Y. Oruç, “High performance concentrators and superconcentrators using multiplexing schemes,” _IEEE Transactions on Communications_ , vol. 42, no. 11, pp. 3045–3050, 1994.
  * [14] A. Y. Oruc and H. Huang, “Crosspoint complexity of sparse crossbar concentrators,” _IEEE Transactions on Information Theory_ , vol. 42, no. 5, pp. 1466–1471, 1996.
  * [15] E. Gündüzhan and A. Y. Oruç, “Structure and density of sparse crossbar concentrators.” in _Advances in Switching Networks_. Citeseer, 1997, pp. 169–180.
  * [16] W. Guo and A. Y. Oruç, “Regular sparse crossbar concentrators,” _IEEE Transactions on Computers_ , vol. 47, no. 3, pp. 363–368, 1998.
  * [17] R. Ratan and A. Oruç, “Performance evaluation of inputqueued buffered sparse-crossbar packet concentrators,” in _Proc. Conference on Information Sciences and Systems CISS_ , vol. 3. Citeseer, 2003.
  * [18] R. Ratan and A. Y. Oruc, “Self-routing quantum sparse crossbar packet concentrators,” _IEEE Transactions on Computers_ , vol. 60, no. 10, pp. 1390–1405, 2010.
  * [19] G. A. Margulis, “Explicit constructions of concentrators,” _Problemy Peredachi Informatsii_ , vol. 9, no. 4, pp. 71–80, 1973.
  * [20] O. Gabber and Z. Galil, “Explicit constructions of linear-sized superconcentrators,” _Journal of Computer and System Sciences_ , vol. 22, no. 3, pp. 407–420, 1981.
  * [21] N. Alon, “On the number of subgraphs of prescribed type of graphs with a given number of edges,” _Israel Journal of Mathematics_ , vol. 38, no. 1-2, pp. 116–130, 1981.
  * [22] R. M. Tanner, “Explicit concentrators from generalized n-gons,” _SIAM Journal on Algebraic Discrete Methods_ , vol. 5, no. 3, pp. 287–293, 1984.
  * [23] S. Jimbo and A. Maruoka, “Expanders obtained from affine transformations,” in _Proceedings of the seventeenth annual ACM symposium on Theory of computing_ , 1985, pp. 88–97.
  * [24] A. Y. Oruc, _Foundations of Interconnection Networks_ , 2020.
  * [25] R. P. Brent and H. T. Kung, “A regular layout for parallel adders,” _IEEE transactions on Computers_ , no. 3, pp. 260–264, 1982.
  * [26] V. Bužek and M. Hillery, “Quantum copying: Beyond the no-cloning theorem,” _Physical Review A_ , vol. 54, no. 3, p. 1844, 1996.
  * [27] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in _Proceedings 35th annual symposium on foundations of computer science_. Ieee, 1994, pp. 124–134.
  * [28] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in _Proceedings of the twenty-eighth annual ACM symposium on Theory of computing_ , 1996, pp. 212–219.
  * [29] W. Guo and A. Y. Oruc, “Explicit construction of bounded capacity sparse crossbar concentrators,” in _Proceedings of the Conference on Information Sciences and Systems_ , vol. 1. Department of Electrical Engineering, Johns Hopkins University., 1996, p. 233.
  * [30] M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight bounds on quantum searching,” _Fortschritte der Physik: Progress of Physics_ , vol. 46, no. 4-5, pp. 493–505, 1998.
  * [31] A. M. Childs and R. Kothari, “Quantum query complexity of minor-closed graph properties,” _SIAM Journal on Computing_ , vol. 41, no. 6, pp. 1426–1450, 2012.