# Contrastive Lift: 3D Object Instance Segmentation by Slow-Fast Contrastive
Fusion

Yash Bhalgat Iro Laina João F. Henriques Andrew Zisserman Andrea Vedaldi
Visual Geometry Group
University of Oxford
<EMAIL_ADDRESS>
###### Abstract

Instance segmentation in 3D is a challenging task due to the lack of large-
scale annotated datasets. In this paper, we show that this task can be
addressed effectively by leveraging instead 2D pre-trained models for instance
segmentation. We propose a novel approach to lift 2D segments to 3D and fuse
them by means of a neural field representation, which encourages multi-view
consistency across frames. The core of our approach is a slow-fast clustering
objective function, which is scalable and well-suited for scenes with a large
number of objects. Unlike previous approaches, our method does not require an
upper bound on the number of objects or object tracking across frames. To
demonstrate the scalability of the slow-fast clustering, we create a new semi-
realistic dataset called the Messy Rooms dataset, which features scenes with
up to 500 objects per scene. Our approach outperforms the state-of-the-art on
challenging scenes from the ScanNet, Hypersim, and Replica datasets, as well
as on our newly created Messy Rooms dataset, demonstrating the effectiveness
and scalability of our slow-fast clustering method. Code available here:
https://github.com/yashbhalgat/Contrastive-Lift.

##  1 Introduction

While the content of images is three-dimensional, image understanding has
largely developed by treating images as two-dimensional patterns. This was
primarily due to the lack of effective machine learning tools that could model
content in 3D. However, recent advancements in neural field methods [50, 41,
43, 5, 69] have provided an effective approach for applying deep learning to
3D signals. These breakthroughs enable us to revisit image understanding tasks
in 3D, accounting for factors such as multi-view consistency and occlusions.

In this paper, we study the problem of _object instance segmentation_ in 3D.
Our goal is to extend 2D instance segmentation to the third dimension,
enabling simultaneous 3D reconstruction and 3D instance segmentation. Our
approach is to extract information from multiple views of a scene
independently with a pre-trained 2D instance segmentation model and fuse it
into a single 3D neural field. Our main motivation is that, while acquiring
densely labelled 3D datasets is challenging, annotations and pre-trained
predictors for 2D data are widely available. Recent approaches have also
capitalized on this idea, demonstrating their potential for 2D-to-3D semantic
segmentation [69, 61, 38, 32] and distilling general-purpose 2D features in 3D
space [29, 56]. When distilling semantic labels or features, the information
to be fused is inherently consistent across multiple views: semantic labels
are viewpoint invariant, and 2D features across views are typically learned
with the same loss function. Additionally, the number of labels or feature
dimensions is predetermined. Thus, 3D fusion amounts to multi-view
aggregation.

When it comes to instance segmentation, however, the number of objects in a 3D
scene is not fixed or known, and can indeed be quite large compared to the
number of semantic classes. More importantly, when objects are detected
independently in different views, they are assigned different and inconsistent
identifiers, which cannot be aggregated directly. The challenge is thus how to
fuse information that is not presented in a viewpoint-consistent manner.

Figure 1: Contrastive Lift takes as input several views of a scene (left), as
well as the output of a panoptic 2D segmenter (middle). It then reconstructs
the scene in 3D while fusing the 2D segments, which are noisy and generally
labelled inconsistently between views, when no object association (tracking)
is assumed. Our method represents object instances in 3D space by a low-
dimensional continuous embedding which can be trained efficiently using a
contrastive formulation that is agnostic to the inconsistent labelling across
views. The result (right) is a consistent 3D segmentation of the objects,
which, once imaged, results in more accurate and consistent 2D segmentations.

Recently, Panoptic Lifting [49] proposed to resolve the lack of multi-view
consistency by explicitly fitting a permutation that aligns labels extracted
from multiple views. Although this yields good results, there are two
drawbacks to this approach. Firstly, determining the permutation matrix
involves solving a linear assignment problem using Hungarian Matching for
every gradient computation. The cost of this increases cubically with the
number of identifiers, which may limit scalability when dealing with a large
number of object instances. Secondly, the canonical label space, where the
permutation maps each 2D label, may need to be extensive to accommodate a
large number of objects.

In this study, we propose a more efficient formulation, which also leads to
more accurate results. To understand our approach, consider first a 2D image
segmenter: it takes an image $I$ as input and produces a mapping $y$ that
assigns each pixel $u\in\mathbb{R}^{2}$ to an object instance label
$y(u)\in\\{1,\dots,L\\}$. It is natural to extend this mapping to 3D by
introducing a function $Y$ that associates each 3D point $x\in\mathbb{R}^{3}$
with the label $Y(x)$ of the corresponding object. To account for the fact
that labels are arbitrary and thus inconsistent between views, Panoptic
Lifting [49] seeks an image-dependent permutation matrix $P$ such that
$Y(x)=P\cdot y(u)$, where $u$ is the projection of $x$ onto the image.

To address the aforementioned challenges with the linear-assignment-based
approach, we identify the labels $y(u)$ with coordinate vectors in the
Euclidean space $\mathbb{R}^{L}$. The functions $y(u)$ can be reconstructed,
up to a label permutation, from the distances
$d(y(u),y(u^{\prime}))\\!=\\!\|y(u)-y(u^{\prime})\|_{2}$ of such vectors, as
they tell whether labels of two pixels $(u,u^{\prime})$ are the same or
different, without considering the specific labelling. Notably, similar to
compressed sensing, we can seek lower-dimensional projections of the vectors
$y$ that preserve this information. With this in mind, we replace the 3D
labelling function $Y$ with a low-dimensional Euclidean embedding
$\Theta(x)\in\mathbb{R}^{D}$. Then, we supervise the embeddings such that
their distances
$d(\Theta(x),\Theta(x^{\prime}))\\!\approx\\!d(y(u),y(u^{\prime}))$ are
sufficiently similar to that of corresponding 2D label embeddings.

This approach has two advantages. First, it only requires learning vectors of
dimensionality $D\ll L$ which is independent of the number of objects $L$.
Second, learning this function does not require solving an assignment problem;
rather, it only considers pairwise distances. Hence, the complexity of
computing the learning objective is independent of the number of objects in
the scene.

We translate this idea into a neural fusion field framework, which we call
_Contrastive Lift_. We build on the recent progress in self-supervised
learning, and combine two key ideas: the usage of a contrastive loss, and the
usage of a slow-fast learning scheme for minimizing the latter in a stable
manner. We believe to be the first to introduce these two ideas in the context
of neural fields.

We compare our method to recent techniques including Panoptic Lifting [49] on
standard 3D instance segmentation benchmarks, viz. ScanNet [13], Replica [51],
and Hypersim [47]. To better demonstrate the scalability of our method to a
very large number of object instances, we introduce a semi-realistic Messy
Rooms dataset featuring scenes with up to 500 objects.

##  2 Related Work

#### Neural Radiance Fields (NeRFs).

NeRF [41] and its numerous variants [5, 43, 2, 37, 35] have achieved
breakthrough results in generating photorealistic 3D reconstructions from 2D
images of a scene. These systems typically represent the scene as a continuous
volumetric function that can be evaluated at any 3D point, enabling high-
quality rendering of novel views from any viewpoint.

#### Objects and Semantics in NeRF.

While NeRF by default offers low-level modelling of radiance and geometry,
recent methods have expanded the set of tasks that can be addressed in this
context to include _semantic_ 3D modelling and scene decomposition. Some works
use neural scene representations to decompose scenes into foreground and
background without supervision or from weak signals [17, 64, 65, 57, 48, 42],
such as text or object motion. Others exploit readily available annotations
for 2D datasets to further extend the capabilities of NeRF models. For
example, Semantic NeRF [69] proposes to incorporate a separate branch
predicting semantic labels, while NeSF [61] predicts a semantic field by
feeding a density field as input to a 3D semantic segmentation model.

Closer to our work are methods that employ NeRFs to address the problem of 3D
panoptic segmentation [32, 49, 19, 63, 26]. Panoptic NeRF [19] and Instance-
NeRF [26] make use of 3D instance supervision. In Panoptic Neural Fields [32],
each instance is represented with its own MLP but dynamic object tracking is
required prior to training the neural field. In this work, we focus on the
problem of lifting 2D instance segmentation to 3D without requiring any 3D
masks or object tracks. A paper most related to our work is Panoptic Lifting
[49], which also seeks to solve the same problem, using linear assignment to
make multi-view annotations consistent. Here, we propose a more efficient and
effective technique based on learning permutation-invariant embedding vectors
instead.

#### Fusion with NeRF.

The aforementioned works, such as Semantic NeRF [70] or Panoptic Lifting [49],
are also representative of a recent research direction that seeks to _fuse_
the output of 2D analysis into 3D space. This is not a new idea; multi-view
semantic fusion methods [25, 39, 52, 36, 38, 60] predate and extend beyond
NeRF. The main idea is that multiple 2D semantic observations (_e.g._ , noisy
or partial) can be combined in 3D space and re-rendered to obtain clean and
multi-view consistent labels. Instead of assuming a 3D model, others
reconstruct a semantic map incrementally using SLAM [33, 54, 44]. Neural
fields have greatly improved the potential of this idea. Instead of 2D labels,
recent works, such as FFD [29], N3F [56], and LERF [27], apply the 3D fusion
idea directly to supervised and unsupervised dense features; in this manner,
unsupervised semantics can be transferred to 3D space, with benefits such as
zero-shot 3D segmentation.

#### Slow-fast contrastive learning.

Many self-supervised learning methods are based on the idea of learning
representations that distinguish different samples, but are similar for
different augmentations of the same sample. Some techniques build on InfoNCE
[58, 55] and, like MoCo [23] and SimCLR [7], use a contrastive objective.
Others such as SWaV [3] and DINO [4] are based on online pseudo-labelling.
Many of these methods stabilise training by using mean-teachers [53], also
called momentum encoders [23]. The idea is to have two versions of the same
network: a fast “student” network supervised by pseudo-labels generated from a
slow “teacher” network, which is in turn updated as the moving average of the
student model. Our formulation is inspired by this idea and extends it to
learning neural fields.

#### Clustering operators for segmentation.

Some works [30, 18, 14, 46] have explored using clustering of pixel-level
embeddings to obtain instance segment assignments. Recent works [67, 66] learn
a pixel-cluster assignment by reformulating cross-attention from a clustering
perspective. Our proposed method, Contrastive Lift, is similar in spirit,
although we learn the embeddings (and cluster centers) using volumetric
rendering from 2D labels.

##  3 Proposed Method: Contrastive Lift

Figure 2: Overview of the Contrastive Lift architecture. See Section 3 for
details.

Here and in Fig. 2, we describe Contrastive Lift, our approach for fusing 2D
instance segmentation in 3D space. An image is a mapping
$I:\Omega\rightarrow\mathbb{R}^{3}$, where $\Omega$ is a pixel grid in
$\mathbb{R}^{2}$, and the values are RGB colours. We have a set of images
$\mathcal{I}$ captured in the same scene and, for each image
$I\in\mathcal{I}$, we have its camera pose $\pi\in SE(3)$ as well as object
identity labels $y:\Omega\rightarrow\\{1,\dots,L\\}$ obtained from a 2D
instance segmentation model for the image $I$. The labels $y$ assigned to the
3D objects in one image $I$ and the labels $y^{\prime}$ in another image
$I^{\prime}$ are in general not consistent. Furthermore, these 2D label maps
can be noisy across views.

We use this data to fit a neural field. The latter is a neural network that
maps 3D coordinates $x\in\mathbb{R}^{3}$ to multiple quantities. The first two
quantities are density, denoted by $\rho:\mathbb{R}^{3}\mapsto[0,1]$, and
radiance (colour), denoted by
$c:\mathbb{R}^{3}\times\mathbb{S}^{2}\mapsto[0,1]^{3}$. Following the standard
neural radiance field approach [37], the colour $c(x,d)$ also depends on the
viewing direction $d\in\mathbb{S}^{2}$. The third quantity is a
$D$-dimensional instance embedding (vector) denoted as
$\Theta:\mathbb{R}^{3}\mapsto\mathbb{R}^{D}$. Each 3D coordinate is also
mapped to a semantic embedding that represents a distribution over the
semantic classes.

#### Differentiable rendering.

The neural field associates attributes (density, colour, and embedding
vectors) to each 3D point $x\in\mathbb{R}^{3}$. These attributes are projected
onto an image $I$ taken from a viewpoint $\pi$ via differentiable ray casting.
Given a pixel location $u\in\Omega$ in the image, we take $N$ successive 3D
samples $r_{i}\in\mathbb{R}^{3}$, $i=0,\dots,N-1$ along the ray from the
camera center through the pixel (so that $(u,f)\propto\pi^{-1}(r_{i})$ where
$f$ is the focal length). The probability that a photon is not absorbed when
travelling from sample $r_{i}$ to sample $r_{i+1}$ is
$\exp(-\rho(r_{i})\delta_{i})$ where $\delta_{i}=\|r_{i+1}-r_{i}\|_{2}$ is the
distance between points. The _transmittance_
$\tau_{i}=\exp(-\sum_{j=0}^{i-1}\rho(r_{j})\delta_{j})$ is the probability
that the photon travels through sample $r_{i}$. The projection of any neural
field $\mathbf{f}$ onto pixel $u$ is thus given by the rendering equation:

$\mathcal{R}(u|\mathbf{f},\rho,\pi)=\sum_{i=0}^{N-1}\mathbf{f}(r_{i})(\tau_{i}-\tau_{i+1})=\sum_{i=0}^{N-1}\mathbf{f}(r_{i})\tau_{i}(1-\exp(-\rho(r_{i})\delta_{i}))$
(1)

In particular, the colour of a pixel is reconstructed as
$I(u)\approx\mathcal{R}(u|c(\cdot,d_{u}),\rho,\pi)$ where the viewing
direction $d_{u}=r_{0}/\|r_{0}\|_{2}$. The photometric loss is thus:

$\mathcal{L}_{\text{RGB}}(c,\rho|I)=\frac{1}{|\Omega|}\sum_{u\in\Omega}\|I(u)-\mathcal{R}(u|c(\cdot,d_{u}),\rho,\pi)\|^{2}.$
(2)

#### Instance embeddings and slow-fast contrastive learning.

The photometric loss (2) learns the colour and density fields $(c,\rho)$ from
the available 2D views $\mathcal{I}$. Now we turn to learning the instance
embedding field $\Theta:\mathbb{R}^{3}\mapsto\mathbb{R}^{D}.$ As noted in
Section 1, the goal of the embeddings is to capture the (binary) distances
between pixel labels sufficiently well. By that, we mean that the segments can
be recovered, modulo a permutation of their labels, by simply _clustering_ the
embeddings a posteriori.

We cast learning the embeddings as optimising the following contrastive loss
function:

$\mathcal{L}_{\textrm{contr}}(\Theta,\rho|y)=-\frac{1}{|\Omega|}\sum_{u\in\Omega}\log\frac{\sum_{u^{\prime}\in\Omega}\boldsymbol{1}_{y(u)=y(u^{\prime})}\exp(\operatorname{sim}(\theta_{u},\theta_{u^{\prime}};\gamma))}{\sum_{u^{\prime}\in\Omega}\exp(\operatorname{sim}(\theta_{u},\theta_{u^{\prime}};\gamma))},~{}~{}~{}\theta_{u}=\mathcal{R}(u|\Theta,\rho,\pi),$
(3)

where $\boldsymbol{1}$ is the indicator function, and
$\operatorname{sim}(x,x^{\prime};\gamma)=\exp(-\gamma\|x-x^{\prime}\|^{2})$ is
a Gaussian RBF kernel used to compute the similarity between embeddings in
Euclidean space. Therefore, pixels that belong to the same segment are
considered positive pairs, and their embeddings are brought closer, while the
embeddings of pixels from different segments are pushed apart. It is worth
emphasizing that, since the object identity labels obtained from the
underlying 2D segmenter are not consistent across images,
$\mathcal{L}_{\textrm{contr}}$ is only applied to positive and negative pixel
pairs sampled from the same image.

While Eq. 3 is logically sound, we found it to result in gradients with high
variance. To address this, we draw inspiration from momentum-teacher
approaches [24, 4, 1] and define a slowly-updated instance embedding field
$\tilde{\Theta}$, with parameters that are updated with an exponential moving
average of the parameters of $\Theta$, instead of gradient descent. With this,
we reformulate Eq. 3 as:

$\mathcal{L}_{\textrm{sf}}(\Theta,\rho|y,\tilde{\Theta})=-\frac{1}{|\Omega_{1}|}\sum_{u\in\Omega_{1}}\log\frac{\sum_{u^{\prime}\in\Omega_{2}}\boldsymbol{1}_{y(u)=y(u^{\prime})}\exp(\operatorname{sim}(\theta_{u},\tilde{\theta}_{u^{\prime}};\gamma))}{\sum_{u^{\prime}\in\Omega_{2}}\exp(\operatorname{sim}(\theta_{u},\tilde{\theta}_{u^{\prime}};\gamma))},$
(4)

where $\theta_{u}=\mathcal{R}(u|\Theta,\rho,\pi)$, and
$\tilde{\theta}_{u^{\prime}}=\mathcal{R}(u^{\prime}|\tilde{\Theta},\rho,\pi)$.
Here, we randomly partition the pixels $\Omega$ into two non-overlapping sets
$\Omega_{1}$ and $\Omega_{2}$, one for the “fast” embedding field $\Theta$,
and another for the “slow” field $\tilde{\Theta}$. This avoids the additional
cost of predicting and rendering each pixel’s embedding using both models, and
allows the computational cost to remain the same as for Eq. 3.

#### Concentration loss.

In order to further encourage the separation of the embedding vectors $\Theta$
and thus simplify the extraction of the objects via a posteriori clustering,
we introduce a loss function that further encourages the embeddings to form
concentrated clusters for each object:

$\mathcal{L}_{\textrm{conc}}(\Theta,\rho|y,\tilde{\Theta})=\frac{1}{|\Omega_{1}|}\sum_{u\in\Omega_{1}}\left\|\theta_{u}-\frac{\sum_{u^{\prime}\in\Omega_{2}}\boldsymbol{1}_{y(u)=y(u^{\prime})}\tilde{\theta}_{u^{\prime}}}{\sum_{u^{\prime}\in\Omega_{2}}\boldsymbol{1}_{y(u)=y(u^{\prime})}}\right\|^{2}.$
(5)

This loss computes a centroid (average) embedding as predicted by the “slow”
field $\tilde{\Theta}$ and penalizes the squared error between each embedding
(as predicted by the “fast” field $\Theta$) and the corresponding centroid.
While this loss reduces the variance of the clusters, it is not a sufficient
training objective by itself as it does not encourage the separation of
different clusters, as done by Eqs. 3 and 4.

#### Semantic segmentation.

For semantic segmentation, we follow the same approach as Semantic NeRF [69],
learning additional embedding dimensions (one per semantic class), rendering
labels in the same manner as Eq. 1, and using the cross-entropy loss for
fitting the semantic field. Additionally, we also leverage the segment
consistency loss introduced in [49] which encourages the predicted semantic
classes to be consistent within an image segment.

#### Architectural details.

Our neural field architecture is based on TensoRF [6]. For the density, we use
a single-channel grid whose values represent the scalar density field
directly. For the colour, a multi-channel grid predicts an intermediate
feature which is concatenated with the viewing direction and passed to a
shallow 3-layer MLP to predict the radiance field. The viewing directions are
encoded using a frequency encoding [41, 59]. For the instance embedding field
$\Theta$ (and also the “slow” field $\tilde{\Theta}$ which has the exact same
architecture as the “fast” field $\Theta$), we use a shallow $5$-layer MLP
that predicts an embedding given an input 3D coordinate. The same architecture
is used for the semantic field. We use raw 3D coordinates directly without a
frequency encoding for the instance and semantic components. More details are
provided in Section B.1.

#### Rendering instance segmentation maps.

After training is complete, we sample $10^{5}$ pixels from $100$ random
viewpoints (not necessarily training views) and render the fast instance field
$\Theta$ at these pixels using the corresponding viewpoint pose. The rendered
$10^{5}\\!\times\\!D$ embeddings are clustered using HDBSCAN [40] to obtain
centroids, which are cached. Now, for any novel view, the field $\Theta$ is
rendered and for each pixel, the label of the centroid nearest to the rendered
embedding is assigned.

##  4 Messy Rooms Dataset

In order to study the scalability of our method to scenes with a large number
of objects, we generate a semi-realistic dataset using Kubric [20]. To
generate a scene, we first spawn $N$ realistically textured objects, randomly
sampled from the Google Scanned Objects dataset [15], without any overlap. The
objects are dropped from their spawned locations and a physics simulation is
run for a few seconds until the objects settle in a natural arrangement. The
static scene is rendered from $M$ inward-facing camera viewpoints randomly
sampled in a dome-shaped shell around the scene. Background, floor, and
lighting are based on $360^{\circ}$ HDRI textures from PolyHaven [68]
projected onto a dome.

Specifically, we create scenes with $N=25,50,100$, and $500$ objects. The
number of viewpoints, $M$ is set to $\min(1200,\lfloor
600\times\sqrt{\nicefrac{{N}}{{25}}}\rceil)$, and the rendered image
resolution is $512\\!\times\\!512$. To ensure that the focus is on the added
objects, we use background textures old_room and large_corridor from PolyHaven
that do not contain any objects. A total of $8$ scenes are generated. The use
of realistic textures for objects and background environments makes them
representative of real-world scenarios.

Additionally, we would like to maintain a consistent number of objects per
image as we increase the total number of objects so that the performance of
the 2D segmenter is not a factor in the final performance. Firstly, we ensure
that the floor area of the scene scales proportionally with the number of
objects, preventing objects from becoming densely packed. Secondly, the
cameras move further away from the scene as its extent increases. To ensure
that the same number of objects is visible in each image, regardless of the
scene size, we adjust the focal length of the cameras accordingly, _i.e._ ,
$f=35.0\times\sqrt{\nicefrac{{N}}{{25}}}$, creating an effect similar to
magnification. This approach ensures a comparable object distribution in each
image, while enabling us to study the scalability of our method.

We render the instance IDs from each camera viewpoint to create ground-truth
instance maps. These ground-truth instance IDs remain consistent (tracked)
across views, as they are rendered from the same 3D scene representation.111In
all experiments, tracked ground-truth instance maps are used only for
evaluation and not to train models. Figure 3 shows illustrative examples from
the dataset, which we name _Messy Rooms_. For evaluation (Section 5), semantic
maps are required. As there is a large variety of different object types in
Kubric, there is no off-the-shelf detector that can classify all of these, and
since we are interested in the instance segmentation problem, rather than the
semantic classes, we simply lump all object types in a single “foreground”
class, which focuses the evaluation on the quality of instance segmentation.
More details about the dataset are provided in Appendix A.

Figure 3: Messy Rooms dataset visualization. Left: physically realistic static
3D scene with $N$ objects from GSO [15]. Middle: $M$ camera viewpoints sampled
in a dome-shaped shell. Right: ground-truth RGB and instance IDs, and instance
segmentations obtained from Detic [71].

##  5 Experiments

#### Benchmarks and baselines.

We train and evaluate our proposed method on challenging scenes from the
ScanNet [13], Hypersim [47], and Replica [51] datasets. We compare our method
with Panoptic Lifting (PanopLi) [49], which is the current state-of-the-art
for lifting 2D panoptic predictions to 3D, along with other 3D panoptic
segmentation approaches: Panoptic Neural Fields [31] and DM-NeRF [62]. We
follow PanopLi [49] for the data preprocessing steps and train-test splits for
each scene from these datasets. We also evaluate our proposed method and
PanopLi on our Messy Rooms dataset (Section 4) that features scenes with up to
$500$ objects. These experiments aim to demonstrate the scalability of our
proposed method as compared to the linear-assignment approach.

We compare two variants of our Contrastive Lift method: (1) Vanilla: uses the
simple contrastive loss (Eq. 3), and (2) Slow-Fast: uses slow-fast contrastive
(Eq. 4) and concentration (Eq. 5) losses.

#### Metrics.

The metric used in our evaluations is the scene-level Panoptic Quality
(PQ${}^{\text{scene}}$) metric introduced in [49]. PQ${}^{\text{scene}}$ is a
scene-level extension of standard PQ [28] that takes into account the
consistency of instance IDs across views/frames (aka tracking). In
PQ${}^{\text{scene}}$, predicted/ground-truth segments with the same instance
ID across all views are merged into subsets and all pairs of predicted/ground-
truth subsets are compared, marking them as a match if the IoU is greater than
$0.5$.

#### Implementation Details.

We train our neural field model for 400k iterations on all scenes.
Optimization-related hyper-parameters can be found in Section B.2. The density
grid is optimised using only the photometric loss
($\mathcal{L}_{\text{RGB}}$). While rendering the instance/semantic fields and
computing associated losses (Eqs. 3, 4 and 5), gradients are stopped from
flowing to the density grid.

For experiments on ScanNet, Hypersim and Replica, we use Mask2Former (M2F) [8]
as the 2D segmenter to obtain the image-level semantic labels and instance
identities. Although any 2D segmenter can be used, using M2F allows direct
comparisons with other state-of-the-art approaches [49]. We follow the
protocol used in [49] to map the COCO [34] vocabulary to 21 classes in
ScanNet.

For experiments on Messy Rooms, we use Detic [71] instead since the object
categories are not isomorphic to the COCO vocabulary M2F uses. We use the LVIS
[21] vocabulary with Detic. To show the scalability of our method compared to
a linear-assignment-based approach, we train the PanopLi [49] model on this
dataset. For fair comparison, we first train the density, colour and semantic
fields, which are identical in PanopLi and our approach. We then separately
train the instance field using the respective linear-assignment and slow-fast
contrastive losses, with all other components frozen, ensuring that
performance is only influenced by the quality of the learned instance field.

###  5.1 Results

Table 1: Results on ScanNet, Hypersim, and Replica datasets. The performance
of all prior work has been sourced from [49]. For each dataset, we report the
PQ${}^{\text{scene}}$ metric.

Method | ScanNet [13] | HyperSim [47] | Replica [51]
---|---|---|---
DM-NeRF [62] | 41.7 | 51.6 | 44.1
PNF [31] | 48.3 | 44.8 | 41.1
PNF + GT BBoxes | 54.3 | 47.6 | 52.5
PanopLi [49] | 58.9 | 60.1 | 57.9
Vanilla (Ours) | 60.5 | 60.9 | 57.8
Slow-Fast (Ours) | 62.3 | 62.3 | 59.1

Table 2: Results on the Messy Rooms dataset. PQ${}^{\text{scene}}$ metric is
reported on “old room” and “large corridor” environments with increasing
number of objects in the scene ($N=25,50,100,500$).

Method | Old Room environment | Large Corridor environment
---|---|---
25 Objects | 50 Objects | 100 Objects | 500 Objects | 25 Objects | 50 Objects | 100 Objects | 500 Objects
PanopLi [49] | 73.2 | 69.9 | 64.3 | 51.0 | 65.5 | 71.0 | 61.8 | 49.0
Vanilla (Ours) | 74.1 | 71.2 | 63.6 | 49.7 | 67.9 | 69.3 | 62.2 | 47.2
Slow-Fast (Ours) | 78.9 | 75.8 | 69.1 | 55.0 | 76.5 | 75.5 | 68.7 | 52.5

In Table 1, we compare the performance of our proposed approach with existing
methods on three datasets: ScanNet [13], HyperSim [47], and Replica [51].
Since the semantic field and underlying TensoRF [5] architecture we use is
similar to Semantic-NeRF [69] and PanopLi [49], we only report the
PQ${}^{\text{scene}}$ metric here and have added an additional table to
Appendix D where we show that the mIoU and PSNR of our method match the
performance of prior methods as expected. We observe that the proposed Slow-
Fast approach consistently outperforms the baselines on all three datasets,
while also outperforming the state-of-the-art Panoptic Lifting [49] method by
$+3.9$, $+1.4$ and $+0.8$ PQ${}^{\text{scene}}$ points on these datasets
respectively. We note that the Vanilla version of our method also performs
comparably with PanopLi and outperforms other methods on all datasets.

Table 2 shows comparisons between our method and PanopLi [49] on scenes from
our Messy Rooms dataset with $25,50,100$, and $500$ objects. We see that the
margin of improvement achieved by Contrastive Lift over PanopLi is even larger
on these scenes, which shows that the proposed method scales favorably to
scenes with a large number of objects. Fig. 4 shows qualitative results on two
of these scenes. Even though the 2D segments obtained using Detic [71] are
noisy (sometimes over-segmented) and generally labelled inconsistently between
views, the resulting instance segmentations rendered by Contrastive Lift are
clearer and consistent across views. We also note that PanopLi sometimes fails
to distinguish between distinct objects as pointed out in LABEL:fig:two.

(a)

(b)

Figure 4: Qualitative comparisons of our method with PanopLi [49] and Detic
[71] (underlying 2D segmenter model) on scenes from our Messy Rooms dataset.
Colour coding: regions where PanopLi performs poorly are highlighted with red
boxes, while regions where both PanopLi and our method exhibit poor
performance are marked with blue boxes. Additionally, red arrows indicate
instances where PanopLi fails to distinguish between different objects. Please
zoom in to observe finer details.

###  5.2 Ablations

#### Different variants of Contrastive Lift.

Our proposed method uses $\mathcal{L}_{\textrm{sf}}$ (Eq. 4) and
$\mathcal{L}_{\textrm{conc}}$ (Eq. 5) to optimise the instance embedding
field. To study the effect of these losses, we design a comprehensive set of
variants of the proposed method: (1) Proposed
($\mathcal{L}_{\textrm{sf}}\\!+\\!\mathcal{L}_{\textrm{conc}}$), (2) Proposed
without Concentration loss ($\mathcal{L}_{\textrm{sf}}$), (3) Vanilla
contrastive ($\mathcal{L}_{\textrm{contr}}$), (4) Vanilla contrastive with
Concentration loss applied to “fast” field since there is no “slow” field
($\mathcal{L}_{\textrm{contr}}\\!+\\!\mathcal{L}_{\textrm{conc}}(\text{fast})$).
Table 3 shows these ablations.

Table 3: Ablations of different variants of the Contrastive Lift method.
PQ${}^{\text{scene}}$ metric averaged over the scenes of ScanNet and Messy
Rooms datasets is reported. Embedding size of $3$ is used.

Dataset | $\mathcal{L}_{\textrm{sf}}\\!+\\!\mathcal{L}_{\textrm{conc}}$ | $\mathcal{L}_{\textrm{sf}}$ | $\mathcal{L}_{\textrm{contr}}$ | $\mathcal{L}_{\textrm{contr}}\\!+\\!\mathcal{L}_{\textrm{conc}}(\text{fast})$
---|---|---|---|---
ScanNet [13] | 62.0 | 61.3 | 60.5 | 55.2
Messy Rooms | 69.0 | 66.5 | 63.2 | 51.7

#### Effect of embedding size on performance.

We investigate the impact of varying the instance embedding size on the
performance of our proposed Contrastive Lift method. Specifically, we evaluate
the effect of different embedding sizes using the PQ${}^{\text{scene}}$ metric
on ScanNet, Hypersim and Replica datasets. As shown in Fig. 5, we find that an
embedding size as small as $3$ is already almost optimal. Based on this, we
use an embedding size of $24$ for experiments with these datasets (c.f. Table
1). For experiments with Messy Rooms dataset (c.f. Table 2), we keep the
embedding size to $3$.

(a) ScanNet [13]

(b) Replica [51]

(c) Hypersim [47]

Figure 5: Impact of the embedding size on the performance
(PQ${}^{\text{scene}}$) of the instance module.

#### Qualitative evaluation: Slow-fast vs vanilla contrastive learning.

(a) ScanNet scene0300_01 scene

(b) Messy Rooms large_corridor_25 scene

Figure 6: Embeddings obtained using vanilla (plain) contrastive learning and
our proposed Slow-Fast contrastive learning. We use LDA [22] to project the
embeddings to 2D for the illustration here.

Fig. 6 shows how the embeddings are distributed in Euclidean space when
learned using our proposed slow-fast contrastive loss (Eqs. 4 and 5) and the
vanilla contrastive loss (Eq. 3). Embeddings learned with the slow-fast method
are clustered more compactly and are easy to distinguish using any post-
processing algorithm, such as HDBSCAN [40] which is used in this example.

#### Comparison to underlying 2D instance segmentation model with tracking.

Before lifting, the predictions of the underlying 2D instance segmentation
model (e.g., Mask2Former [8] or Detic [71]) are not consistent (aka tracked)
across frames/views. To achieve consistency and to allow comparisons with our
approach, we post-process the 2D segmenter’s predictions using Hungarian
Matching for cross-frame tracking as follows:

  1. 1.

w/ Hungarian matching (2D IoU): Given sets of predicted segments ($P_{i}$ and
$P_{i+1}$) from consecutive frames, compute IoU matrix by comparing all
segment pairs in $P_{i}\times P_{i+1}$. Apply Hungarian matching to the IoU
matrix to associate instance segments across frames.

  2. 2.

w/ Hungarian matching based on IoU after depth-aware pose-warping: Use ground-
truth pose and depth for warping $(i+1)$-th frame’s segmentation to frame $i$.
Compute IoU matrix using warped segmentations and apply Hungarian matching.

  3. 3.

w/ Hungarian matching using ground-truth pointcloud: Using only consecutive
frames leads to errors in long-range tracking. To address this, starting from
the first frame, unproject 2D segments into the 3D point cloud. Iteratively
fuse segments in 3D using Hungarian matching. This way, segments from
preceding frames along with 3D information are used for tracking.

The last two baselines use 3D groundtruth for tracking. Table 4 shows that
despite 3D information being used for matching, Contrastive Lift still
significantly improves over the underlying 2D model.

Table 4: Comparison of our approach with the underlying 2D segmentations on ScanNet [13]. For M2F predictions [8], consistency across frames is obtained with different tracking variants. Method |  PQ${}^{\text{scene}}$
---|---
Mask2Former [8] (M2F) (non-tracked) | $32.3$
M2F w/ Tracking method (1) | $33.7$
M2F w/ Tracking method (2) | $34.0$
M2F w/ Tracking method (3) | $41.0$
Contrastive Lift (ours trained w/ Mask2Former labels) | 62.3

#### Frame-level improvement on underlying 2D segmentation models.

In addition to generating consistent (tracked) instance segmentations, our
method also improves the per-frame quality (i.e., not considering tracking) of
the underlying 2D segmentation model. To show this, we train Contrastive Lift
on ScanNet scenes with different 2D models, viz. Mask2Former [8], MaskFormer
[9] and Detic [71]. In Section 5.2 we report the Panoptic Quality (PQ) metric
(computed per frame) for these 2D models and for our method when trained with
segments from each corresponding model.

Table 5: Improvement of per-frame segmentation quality as measured by Panoptic
Quality (PQ).

Method | PQ
---|---
MaskFormer [9] | 41.1
Contrastive Lift (w/ MaskFormer labels) | 61.7
Mask2Former [8] | 42.0
Contrastive Lift (w/ Mask2Former labels) | 61.6
Detic [71] | 43.6
Contrastive Lift (w/ Detic labels) | 62.1

#### Comparison of training speed with the linear-assignment loss method.

While the exact number of objects present in a scene is unknown, linear
assignment-based methods typically require a hyperparameter $K$ that specifies
the maximum number of objects. Solving the linear assignment problem in
PanopLi’s loss is $O(K^{3})$ [49]. Our method is agnostic to object count,
eliminating the need for such a parameter. Our approach does rely on the size
of the embedding size, but, as shown above, even a very small size suffices.
In the slow-fast contrastive loss computation, the Softmax function dominates
more than the pairwise similarity matrix calculation. Consequently, we find
that the training speed of Contrastive Lift is largely unaffected by the
choice of embedding size.

Table 6 compares the training speed, measured on a NVIDIA A40 GPU, between
PanopLi and our method, showing that PanopLi iterations become slower as $K$
increases. We only optimise the instance embedding field with associated
losses, while the density/colour/semantic fields are frozen.

Table 6: Training speed in iterations/second. Mean $\pm$ error margin measured over 8 runs. Contrastive Lift |  Panoptic Lifting [49]
---|---
$K=25$ | $K=50$ | $K=100$ | $K=500$
16.06 $\pm$ 2.34 |  13.01 $\pm$ 1.26 |  12.53 $\pm$ 0.92 |  12.10 $\pm$ 1.07 |  9.41 $\pm$ 0.60

##  6 Limitations

Contrastive Lift improves noisy 2D input segmentations, but cannot recover
from catastrophic failures, such as entirely missing object classes. It also
requires the 3D reconstruction to work reliably. As a result, we have focused
on static scenes, as 3D reconstruction remains unreliable in a dynamic
setting. Contrastive Lift is a useful building block in applications, but has
no particular direct societal impact. The datasets used in this paper are
explicitly licensed for research and contain no personal data.

##  7 Conclusion

We have introduced Contrastive Lift, a method for fusing the outputs of 2D
instance segmenter using a 3D neural fields. It learns a 3D vector field that
characterises the different object instances in the scene. This field is
fitted to the output of the 2D segmenter in a manner which is invariant to
permutation of the object labels, which are assigned independently and
arbitrarily in each input image. Compared to alternative approaches that
explicitly seek to make multi-view labels compatible, Contrastive Lift is more
accurate and scalable, enabling future work on larger object collections.

## Acknowledgments and Disclosure of Funding

We are grateful for funding from EPSRC AIMS CDT EP/S024050/1 and AWS (Y.
Bhalgat), ERC-CoG UNION 101001212 (A. Vedaldi and I. Laina), EPSRC VisualAI
EP/T028572/1 (I. Laina, A. Vedaldi and A. Zisserman), and Royal Academy of
Engineering RF\201819\18\163 (J. Henriques).

## References

  * [1] Yutong Bai, Angtian Wang, Adam Kortylewski, and Alan Yuille.  Coke: Contrastive learning for robust keypoint detection.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 65–74, 2023.
  * [2] Jonathan T Barron, Ben Mildenhall, Matthew Tancik, Peter Hedman, Ricardo Martin-Brualla, and Pratul P Srinivasan.  Mip-nerf: A multiscale representation for anti-aliasing neural radiance fields.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5855–5864, 2021.
  * [3] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  In Proc. NeurIPS, 2020.
  * [4] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In Proc. ICCV, 2021.
  * [5] Anpei Chen, Zexiang Xu, Andreas Geiger, Jingyi Yu, and Hao Su.  TensoRF: Tensorial radiance fields.  In arXiv, 2022.
  * [6] Anpei Chen, Zexiang Xu, Andreas Geiger, Jingyi Yu, and Hao Su.  Tensorf: Tensorial radiance fields.  In European Conference on Computer Vision (ECCV), 2022.
  * [7] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton.  A simple framework for contrastive learning of visual representations.  In Proc. ICML, 2020.
  * [8] Bowen Cheng, Ishan Misra, Alexander G Schwing, Alexander Kirillov, and Rohit Girdhar.  Masked-attention mask transformer for universal image segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1290–1299, 2022.
  * [9] Bowen Cheng, Alexander G. Schwing, and Alexander Kirillov.  Per-pixel classification is not all you need for semantic segmentation.  2021\.
  * [10] Sumit Chopra, Raia Hadsell, and Yann LeCun.  Learning a similarity metric discriminatively, with application to face verification.  In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), volume 1, pages 539–546. IEEE, 2005.
  * [11] Dorin Comaniciu and Peter Meer.  Mean shift: A robust approach toward feature space analysis.  IEEE Transactions on pattern analysis and machine intelligence, 24(5):603–619, 2002.
  * [12] Blender Online Community.  Blender - a 3D modelling and rendering package.  Blender Foundation, Stichting Blender Foundation, Amsterdam, 2018.
  * [13] Angela Dai, Angel X Chang, Manolis Savva, Maciej Halber, Thomas Funkhouser, and Matthias Nießner.  Scannet: Richly-annotated 3d reconstructions of indoor scenes.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5828–5839, 2017.
  * [14] Bert De Brabandere, Davy Neven, and Luc Van Gool.  Semantic instance segmentation with a discriminative loss function.  arXiv preprint arXiv:1708.02551, 2017.
  * [15] Laura Downs, Anthony Francis, Nate Koenig, Brandon Kinman, Ryan Hickman, Krista Reymann, Thomas B McHugh, and Vincent Vanhoucke.  Google scanned objects: A high-quality dataset of 3d scanned household items.  In 2022 International Conference on Robotics and Automation (ICRA), pages 2553–2560. IEEE, 2022.
  * [16] Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al.  A density-based algorithm for discovering clusters in large spatial databases with noise.  In kdd, volume 96, pages 226–231, 1996.
  * [17] Zhiwen Fan, Peihao Wang, Yifan Jiang, Xinyu Gong, Dejia Xu, and Zhangyang Wang.  NeRF-SOS: Any-view self-supervised object segmentation on complex scenes.  In The Eleventh International Conference on Learning Representations, 2023.
  * [18] Alireza Fathi, Zbigniew Wojna, Vivek Rathod, Peng Wang, Hyun Oh Song, Sergio Guadarrama, and Kevin P Murphy.  Semantic instance segmentation via deep metric learning.  arXiv preprint arXiv:1703.10277, 2017.
  * [19] Xiao Fu, Shangzhan Zhang, Tianrun Chen, Yichong Lu, Lanyun Zhu, Xiaowei Zhou, Andreas Geiger, and Yiyi Liao.  Panoptic NeRF: 3d-to-2d label transfer for panoptic urban scene segmentation.  arXiv.cs, abs/2203.15224, 2022.
  * [20] Klaus Greff, Francois Belletti, Lucas Beyer, Carl Doersch, Yilun Du, Daniel Duckworth, David J Fleet, Dan Gnanapragasam, Florian Golemo, Charles Herrmann, Thomas Kipf, Abhijit Kundu, Dmitry Lagun, Issam Laradji, Hsueh-Ti (Derek) Liu, Henning Meyer, Yishu Miao, Derek Nowrouzezahrai, Cengiz Oztireli, Etienne Pot, Noha Radwan, Daniel Rebain, Sara Sabour, Mehdi S. M. Sajjadi, Matan Sela, Vincent Sitzmann, Austin Stone, Deqing Sun, Suhani Vora, Ziyu Wang, Tianhao Wu, Kwang Moo Yi, Fangcheng Zhong, and Andrea Tagliasacchi.  Kubric: a scalable dataset generator.  2022\.
  * [21] Agrim Gupta, Piotr Dollar, and Ross Girshick.  Lvis: A dataset for large vocabulary instance segmentation.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 5356–5364, 2019.
  * [22] Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman.  The elements of statistical learning: data mining, inference, and prediction, volume 2.  Springer, 2009.
  * [23] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross B. Girshick.  Momentum contrast for unsupervised visual representation learning.  arXiv.cs, abs/1911.05722, 2019.
  * [24] Olivier J Hénaff, Skanda Koppula, Evan Shelhamer, Daniel Zoran, Andrew Jaegle, Andrew Zisserman, João Carreira, and Relja Arandjelović.  Object discovery and representation networks.  In Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XXVII, pages 123–143. Springer, 2022.
  * [25] Alexander Hermans, Georgios Floros, and Bastian Leibe.  Dense 3d semantic mapping of indoor scenes from rgb-d images.  In 2014 IEEE International Conference on Robotics and Automation (ICRA), pages 2631–2638. IEEE, 2014.
  * [26] Benran Hu, Junkai Huang, Yichen Liu, Yu-Wing Tai, and Chi-Keung Tang.  Instance neural radiance field.  arXiv preprint arXiv:2304.04395, 2023.
  * [27] Justin Kerr, Chung Min Kim, Ken Goldberg, Angjoo Kanazawa, and Matthew Tancik.  Lerf: Language embedded radiance fields.  arXiv preprint arXiv:2303.09553, 2023.
  * [28] Alexander Kirillov, Kaiming He, Ross B. Girshick, Carsten Rother, and Piotr Dollár.  Panoptic segmentation.  In Proc. CVPR, 2019.
  * [29] Sosuke Kobayashi, Eiichi Matsumoto, and Vincent Sitzmann.  Decomposing NeRF for editing via feature field distillation.  arXiv.cs, 2022.
  * [30] Shu Kong and Charless C Fowlkes.  Recurrent pixel embedding for instance grouping.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 9018–9028, 2018.
  * [31] Abhijit Kundu, Kyle Genova, Xiaoqi Yin, Alireza Fathi, Caroline Pantofaru, Leonidas J Guibas, Andrea Tagliasacchi, Frank Dellaert, and Thomas Funkhouser.  Panoptic neural fields: A semantic object-aware neural scene representation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12871–12881, 2022.
  * [32] Abhijit Kundu, Kyle Genova, Xiaoqi Yin, Alireza Fathi, Caroline Pantofaru, Leonidas J. Guibas, Andrea Tagliasacchi, Frank Dellaert, and Thomas A. Funkhouser.  Panoptic neural fields: A semantic object-aware neural scene representation.  2022\.
  * [33] Abhijit Kundu, Yin Li, Frank Dellaert, Fuxin Li, and James M Rehg.  Joint semantic segmentation and 3d reconstruction from monocular video.  In Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part VI 13, pages 703–718. Springer, 2014.
  * [34] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13, pages 740–755. Springer, 2014.
  * [35] Lingjie Liu, Jiatao Gu, Kyaw Zaw Lin, Tat-Seng Chua, and Christian Theobalt.  Neural sparse voxel fields.  Advances in Neural Information Processing Systems, 33:15651–15663, 2020.
  * [36] Lingni Ma, Jörg Stückler, Christian Kerl, and Daniel Cremers.  Multi-view deep learning for consistent semantic mapping with RGB-D cameras.  In Proc.IROS, 2017.
  * [37] Ricardo Martin-Brualla, Noha Radwan, Mehdi S. M. Sajjadi, Jonathan T. Barron, Alexey Dosovitskiy, and Daniel Duckworth.  NeRF in the wild: Neural radiance fields for unconstrained photo collections.  In Proc. CVPR, volume abs/2008.02268, 2021.
  * [38] Ruben Mascaro, Lucas Teixeira, and Margarita Chli.  Diffuser: Multi-view 2D-to-3D label diffusion for semantic scene segmentation.  In Proc. ICRA, 2021.
  * [39] John McCormac, Ankur Handa, Andrew Davison, and Stefan Leutenegger.  Semanticfusion: Dense 3d semantic mapping with convolutional neural networks.  In 2017 IEEE International Conference on Robotics and automation (ICRA), pages 4628–4635. IEEE, 2017.
  * [40] Leland McInnes, John Healy, and Steve Astels.  hdbscan: Hierarchical density based clustering.  J. Open Source Softw., 2(11):205, 2017.
  * [41] Ben Mildenhall, Pratul P. Srinivasan, Matthew Tancik, Jonathan T. Barron, Ravi Ramamoorthi, and Ren Ng.  NeRF: Representing scenes as neural radiance fields for view synthesis.  In Proc. ECCV, 2020.
  * [42] Ashkan Mirzaei, Yash Kant, Jonathan Kelly, and Igor Gilitschenski.  Laterf: Label and text driven object radiance fields.  In Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part III, pages 20–36. Springer, 2022.
  * [43] Thomas Müller, Alex Evans, Christoph Schied, and Alexander Keller.  Instant neural graphics primitives with a multiresolution hash encoding.  In Proc. SIGGRAPH, 2022.
  * [44] Gaku Narita, Takashi Seno, Tomoya Ishikawa, and Yohsuke Kaji.  Panopticfusion: Online volumetric semantic mapping at the level of stuff and things.  In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4205–4212. IEEE, 2019.
  * [45] Alejandro Newell, Zhiao Huang, and Jia Deng.  Associative embedding: End-to-end learning for joint detection and grouping.  Advances in neural information processing systems, 30, 2017.
  * [46] David Novotny, Samuel Albanie, Diane Larlus, and Andrea Vedaldi.  Semi-convolutional operators for instance segmentation.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 86–102, 2018.
  * [47] Mike Roberts, Jason Ramapuram, Anurag Ranjan, Atulit Kumar, Miguel Angel Bautista, Nathan Paczan, Russ Webb, and Joshua M Susskind.  Hypersim: A photorealistic synthetic dataset for holistic indoor scene understanding.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10912–10922, 2021.
  * [48] Prafull Sharma, Ayush Tewari, Yilun Du, Sergey Zakharov, Rares Andrei Ambrus, Adrien Gaidon, William T. Freeman, Fredo Durand, Joshua B. Tenenbaum, and Vincent Sitzmann.  Neural groundplans: Persistent neural scene representations from a single image.  In The Eleventh International Conference on Learning Representations, 2023.
  * [49] Yawar Siddiqui, Lorenzo Porzi, Samuel Rota Bulò, Norman Müller, Matthias Nießner, Angela Dai, and Peter Kontschieder.  Panoptic lifting for 3d scene understanding with neural fields.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 9043–9052, June 2023.
  * [50] Vincent Sitzmann, Michael Zollhöfer, and Gordon Wetzstein.  Scene representation networks: Continuous 3D-structure-aware neural scene representations.  Proc. NeurIPS, 2019.
  * [51] Julian Straub, Thomas Whelan, Lingni Ma, Yufan Chen, Erik Wijmans, Simon Green, Jakob J Engel, Raul Mur-Artal, Carl Ren, Shobhit Verma, et al.  The replica dataset: A digital replica of indoor spaces.  arXiv preprint arXiv:1906.05797, 2019.
  * [52] Niko Sünderhauf, Trung T Pham, Yasir Latif, Michael Milford, and Ian Reid.  Meaningful maps with object-oriented semantic mapping.  In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5079–5085. IEEE, 2017.
  * [53] Antti Tarvainen and Harri Valpola.  Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results.  In Proc. NeurIPS, 2017.
  * [54] Keisuke Tateno, Federico Tombari, Iro Laina, and Nassir Navab.  Cnn-slam: Real-time dense monocular slam with learned depth prediction.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6243–6252, 2017.
  * [55] Michael Tschannen, Josip Djolonga, Paul K. Rubenstein, Sylvain Gelly, and Mario Lucic.  On mutual information maximization for representation learning.  In Proc. ICLR, 2020.
  * [56] Vadim Tschernezki, Iro Laina, Diane Larlus, and Andrea Vedaldi.  Neural Feature Fusion Fields: 3D distillation of self-supervised 2D image representation.  In Proceedings of the International Conference on 3D Vision (3DV), 2022.
  * [57] Vadim Tschernezki, Diane Larlus, and Andrea Vedaldi.  NeuralDiff: Segmenting 3D objects that move in egocentric videos.  In Proceedings of the International Conference on 3D Vision (3DV), 2021.
  * [58] Aäron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  In Proc. NeurIPS, 2019.
  * [59] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In NIPS, 2017.
  * [60] Vibhav Vineet, Ondrej Miksik, Morten Lidegaard, Matthias Nießner, Stuart Golodetz, Victor A Prisacariu, Olaf Kähler, David W Murray, Shahram Izadi, Patrick Pérez, et al.  Incremental dense semantic stereo fusion for large-scale semantic scene reconstruction.  In 2015 IEEE international conference on robotics and automation (ICRA), pages 75–82. IEEE, 2015.
  * [61] Suhani Vora, Noha Radwan, Klaus Greff, Henning Meyer, Kyle Genova, Mehdi S. M. Sajjadi, Etienne Pot, Andrea Tagliasacchi, and Daniel Duckworth.  NeSF: Neural semantic fields for generalizable semantic segmentation of 3D scenes.  arXiv.cs, abs/2111.13260, 2021.
  * [62] Bing Wang, Lu Chen, and Bo Yang.  Dm-nerf: 3d scene geometry decomposition and manipulation from 2d images.  arXiv preprint arXiv:2208.07227, 2022.
  * [63] Bing WANG, Lu Chen, and Bo Yang.  DM-neRF: 3d scene geometry decomposition and manipulation from 2d images.  In The Eleventh International Conference on Learning Representations, 2023.
  * [64] Christopher Xie, Keunhong Park, Ricardo Martin-Brualla, and Matthew Brown.  Fig-nerf: Figure-ground neural radiance fields for 3d object category modelling.  In 2021 International Conference on 3D Vision (3DV), pages 962–971. IEEE, 2021.
  * [65] Hong-Xing Yu, Leonidas Guibas, and Jiajun Wu.  Unsupervised discovery of object radiance fields.  In International Conference on Learning Representations, 2022.
  * [66] Qihang Yu, Huiyu Wang, Dahun Kim, Siyuan Qiao, Maxwell Collins, Yukun Zhu, Hartwig Adam, Alan Yuille, and Liang-Chieh Chen.  Cmt-deeplab: Clustering mask transformers for panoptic segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2560–2570, 2022.
  * [67] Qihang Yu, Huiyu Wang, Siyuan Qiao, Maxwell Collins, Yukun Zhu, Hartwig Adam, Alan Yuille, and Liang-Chieh Chen.  k-means mask transformer.  In European Conference on Computer Vision, pages 288–307. Springer, 2022.
  * [68] Greg Zaal, Rob Tuytel, Rico Cilliers, James Ray Cock, Andreas Mischok, Sergej Majboroda, Dimitrios Savva, and Jurita Burger.  Polyhaven: a curated public asset library for visual effects artists and game designers.  https://polyhaven.com/hdris, 2021.
  * [69] Shuaifeng Zhi, Tristan Laidlow, Stefan Leutenegger, and Andrew J. Davison.  In-place scene labelling and understanding with implicit scene representation.  In Proc. ICCV, 2021.
  * [70] Shuaifeng Zhi, Tristan Laidlow, Stefan Leutenegger, and Andrew J Davison.  In-place scene labelling and understanding with implicit scene representation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 15838–15847, 2021.
  * [71] Xingyi Zhou, Rohit Girdhar, Armand Joulin, Philipp Krähenbühl, and Ishan Misra.  Detecting twenty-thousand classes using image-level supervision.  In ECCV, 2022.

##  Appendix A Messy Rooms dataset

The full Messy Rooms dataset introduced in this work can be accessed at this
link: https://figshare.com/s/b195ce8bd8eafe79762b. We show some representative
examples from this dataset below in Section 5.2, 5.2, 5.2, and 5.2, which
illustrate scenes with $25,50,100$ and $500$ objects respectively. Notice how
the density of “number of objects per image” remains similar as the number of
objects increases from $25$ to $500$. In Section 5.2, we show the
corresponding 3D scenes used to generate the datasets.

##  Appendix B Implementation Details

Here, we provide further implementation details for our method in addition to
the details mentioned in Sections 3 and 5 of the main paper.

###  B.1 Architectural details

Our neural field architecture is similar to [49] for fairness of comparisons.
The density and color grids are initialized with a resolution of
$128\\!\times\\!128\\!\times\\!128$ which is progressively increased up to
$192\\!\times\\!192\\!\times\\!192$ by the end of training. The density and
color grids use $16$ and $48$ components respectively. The output of the color
grid is projected to $27$ dimensions which are then processed by a 3-layer MLP
with $128$ hidden units per layer to output the RGB color. The fast and slow
instance fields use a $256$ hidden size in their MLP, while the semantic field
uses a hidden size of $128$.

###  B.2 Training details

We follow a schedule for training our neural field model as follows: (1) For
the first 40k iterations, the model is trained only with the RGB
reconstruction loss ($\mathcal{L}_{\text{RGB}}$). In this initial phase, the
density field is optimized to reach a reasonable quality such that it can be
used to render the instance/semantic field. (2) At 40k iterations, the
semantic segmentation loss (i.e., cross-entropy loss, as in [70, 49]) is
activated and used for the rest of the training iterations. (3) At 160k
iterations, the instance embedding loss (i.e.,
$\mathcal{L}_{\textrm{sf}}+\mathcal{L}_{\textrm{conc}}$ for the slow-fast
version of our method or $\mathcal{L}_{\textrm{contr}}$ for the vanilla
baseline) is activated. (4) At 280k iterations, the segment consistency loss
(proposed in [49]) is activated. For scenes from the Hypersim dataset [47], we
activate the segment consistency loss at 200k iterations instead. In our
proposed slow-fast clustering framework, the slow field parameters are updated
using an exponential moving average with momentum $m=0.9$, i.e.
$\tilde{\Theta}=\tilde{\Theta}\\!\times\\!m+\Theta\\!\times\\!(1-m)$.

The RGB reconstruction loss, semantic segmentation loss, instance embedding
loss, and segment consistency loss are balanced using weights of
$1.0,0.1,0.1$, and $1.0$ respectively. However, we empirically observe that
the final performance is not very sensitive to these choices. A learning rate
of $5\cdot 10^{-4}$ is used for all MLPs and $0.01$ for the grids. A batch-
size of $2048$ is used to train all models.

###  B.3 Post-processing Clustering details

Given the learned instance embedding field, a clustering mechanism (e.g.,
HDBSCAN [40]) can be used to obtain cluster centroids and generate instance
segmentation maps. We have chosen HDBSCAN since it does not require the number
of objects to be known a priori. Generally, clusters obtained by HDBSCAN are
non-convex and assigning the label of the nearest centroid is not recommended.
But, our proposed method results in highly compact clusters which makes this
simple method effective. We perform clustering as follows.

#### Hierarchical clustering using semantic predictions.

An advantage of our method is that we can use our model’s semantic predictions
to guide the clustering of the instance embeddings. “Instance” segmentation
requires separating instances of the same semantic class. Based on this, we
perform hierarchical clustering as follows:

  1. 1.

After training, sample $10^{5}$ pixels from $100$ random viewpoints and render
the fast instance field $\Theta$ and semantic field for these pixels.

  2. 2.

Group the $10^{5}$ rendered embeddings based on predicted semantic labels,
forming $S$ groups.

  3. 3.

Cluster the embeddings within each group separately using HDBSCAN, caching
cluster-centroids for each group, assigning a unique instance label to each
centroid.

  4. 4.

For a novel view, render the instance field and semantic field, assigning each
pixel an instance embedding and semantic class. Obtain the instance label for
a pixel by finding the closest centroid to the rendered instance embedding
within the group of the same semantic label as the pixel.

#### Tuning clustering hyperparameter.

Despite HDBSCAN’s robustness to hyperparameter selection, we found that it is
beneficial to specify a minimum cluster size. Since we always sample and
render $10^{5}$ pixels for clustering, the expected cluster size per object
decreases as the number of objects increases. To determine an optimal value,
we perform a hyperparameter sweep using $10\%$ of the training data, which
includes training viewpoints and associated segments from the 2D segmenter. We
then use this identified optimal value to perform clustering as described
above.

##  Appendix C Comparison between different clustering algorithms.

We compare HDBSCAN with other unsupervised clustering algorithms, viz.
MeanShift [11] and DBSCAN [16]. We tune the bandwidth parameter with
MeanShift, and the epsilon parameter with DBSCAN. However, we note that
MeanShift struggles to converge for embedding sizes greater than 10. For fair
comparison, we train our model with an embedding size of 3. Table 7 show that
both MeanShift and DBSCAN perform slightly worse but remain comparable to
HDBSCAN. Generally, any unsupervised clustering method that doesn’t require
prior knowledge of the number of clusters is suitable for use with our method.

Table 7: Performance (PQ${}^{\text{scene}}$) achieved with DBSCAN [16], MeanShift [11] and HDBSCAN [40]. |  ScanNet [13] | Messy Rooms
---|---|---
w/ DBSCAN | 61.8 | 68.2
w/ MeanShift | 62.0 | 68.6
w/ HDBSCAN | 62.0 | 69.0

##  Appendix D Quality of our semantic and radiance field

In Tables 1 and 2 in the main paper, we evaluate the quality and consistency
(aka tracking) of the instance segmentation maps obtained by the various
tested methods. The semantic field and density/color field architecture of our
method is based on Panoptic Lifting [49], which in turn is a modification of
Semantic-NeRF [70] for the semantic component. As a sanity check, we compare
the quality of rendered semantic and RGB maps obtained by these methods with
ours. Table 8 shows the mean Intersection over Union (mIoU) and peak-signal-
to-noise ratio (PSNR) metrics. As expected, the mIoU and PSNR obtained by our
method is nearly the same as Panoptic Lifting.

For the Messy Rooms dataset we have explicitly ensured that the density and
semantic model used by both Panoptic Lifting and our method are the same and
the only factor influencing the final performance is the quality of the
learned instance field. This is done by pre-training the same density and
semantic fields for both methods and subsequently training the instance field
using the respective objective functions.

Table 8: Comparisons of the rendered semantic and RGB maps. Performance numbers for [70, 49] are sourced from [49]. Method |  ScanNet [13] |  HyperSim [47] |  Replica [51]
---|---|---|---
mIoU | PSNR | mIoU | PSNR | mIoU | PSNR
Semantic-NeRF [70] | 58.9 | 26.6 | 58.5 | 24.8 | 59.2 | 26.6
PanopLi [49] | 65.2 | 28.5 | 67.8 | 30.1 | 67.2 | 29.6
Ours | 65.2 | 28.3 | 67.9 | 30.0 | 67.0 | 29.3

##  Appendix E Comparisons to other metric learning loss functions

While we employ a contrastive loss formulation to learn the instance
embeddings, there are many alternative loss functions proposed in the metric
learning literature. For comparison, we also train our instance embedding
field with the Associative Embedding (AE) loss [45] and the margin-based
contrastive loss [10].

To compute the AE Loss, we divide the batch $\Omega$ into groups based on
segment ID. If there are $K$ groups/segments, $G_{1}\dots G_{K}$, then

$\mathcal{L}_{\textrm{AE}}(\Theta,\rho|y)=\frac{1}{|\Omega|}\sum_{k}\sum_{u\in
G_{k}}\|\theta_{u}-\bar{\theta}_{k}\|^{2}_{2}+\frac{1}{K^{2}}\sum_{k}\sum_{k^{\prime}}\|\bar{\theta}_{k}-\bar{\theta}_{k^{\prime}}\|^{2}_{2},~{}~{}~{}\bar{\theta}_{k}=\frac{1}{|G_{k}|}\sum_{u\in
G_{k}}\theta_{u}$ (6)

The margin-based contrastive loss is defined as:

$\mathcal{L}_{\text{margin}}(\Theta,\rho|y)=\frac{1}{|\Omega|^{2}}\sum_{u,u^{\prime}\in\Omega}\boldsymbol{1}_{[y(u)=y({u^{\prime}})]}\|\theta_{u}-\theta_{u^{\prime}}\|^{2}_{2}+\boldsymbol{1}_{[y(u)\neq
y({u^{\prime}})]}\max(0,\epsilon-\|\theta_{u}-\theta_{u^{\prime}}\|^{2}_{2})$
(7)

Here, $\theta_{u}=\mathcal{R}(u|\Theta,\rho,\pi)$ is the rendered instance
field at pixel $u$. Note that, the slow-fast field formulation is not used in
these comparisons. In Appendix E we compare the proposed objective (slow-fast)
to these baselines. We observe that both the vanilla contrastive, as well as
the slow-fast version of our method, outperform the alternatives.

#### DINO-style loss.

Since our method is inspired by momentum-teacher approaches, e.g. DINO [4], we
design a baseline with a DINO-style learning mechanism. Two pixels from the
same instance segment are fed into the slow and fast fields. This is akin to
DINO, where two random image transformations are fed to the student and
teacher networks. A Centering layer is applied to the slow field embedding. A
Projection module (with $\text{proj\\_dim}=512$) is added to both the slow and
fast fields followed by Softmax and a cross-entropy loss is used. After
training, embeddings from the fast field are used for clustering. Results in
Appendix E demonstrate that this baseline performs worse than the metric-
learning losses on ScanNet. We do not evaluate this baseline on the Messy
Rooms dataset.

Table 9: Comparing Associative Embedding Loss and Triplet Loss with our
proposed losses (vanilla and slow-fast). An embedding size of $3$ is used in
all cases. PQ${}^{\text{scene}}$ is reported here. (a)  (b)

Figure 14: Illustrative examples from Messy Rooms dataset. Here, we show
scenes with 25 objects.

(a)

(b)

Figure 15: Illustrative examples from Messy Rooms dataset. Here, we show
scenes with 50 objects.

(a)

(b)

Figure 16: Illustrative examples from Messy Rooms dataset. Here, we show
scenes with 100 objects.

(a)

(b)

Figure 17: Illustrative examples from Messy Rooms dataset. Here, we show
scenes with 500 objects.

(a)

(b)

Figure 18: We show (using Blender [12]) the actual 3D scenes without texture
that are used to render/generate the Messy Rooms scenes. _Note that the
surface area of the scene is increased proportionally to the number of
objects_.


# One-step quantum search algorithms based on smooth operators

Basanta R. Pahari  Department of Mechanical Engineering, Florida Center for
Advanced Aero Propulsion, Florida A&M University and Florida State University,
Tallahassee, FL 32310  Sagar Bhat  James S. Rickards High School, Tallahassee,
FL 32301  Siri Davidi  Lincoln High School, Tallahassee, FL 32311  William
Oates  Department of Mechanical Engineering, Florida Center for Advanced Aero
Propulsion, Florida A&M University and Florida State University, Tallahassee,
FL 32310

###### Abstract

The discovery of derivatives and integrals was a tremendous leap in scientific
knowledge and completely revolutionized many fields, including mathematics,
physics, and engineering. The existence of higher-order derivatives means
better approximation and, thus, more accurate modeling of any physical
phenomenon. Here we use smooth operators that are infinitely differentiable to
construct two quantum search algorithms and connect these seemingly different
areas. Along with smooth functions, permutation operators and the roots of
unity are exploited to create quantum circuits to perform a quantum search. We
validate our models through quantum simulators and test them on IBM’s quantum
hardware. Furthermore, we investigate the effect of noise and error
propagation and demonstrate that our approach is more robust to noise compared
to iterative methods like Grover’s algorithm.

###### keywords:

Quantum computing, Smooth operators, Quantum search

##  1 introduction and Motivations

Orthogonal projection is a useful technique for applications such as pattern
recognition and denoising, as it breaks down signals or functions into simpler
components, making them easier to analyze [3, 11, 10]. The most common way to
create projection operators on functional spaces is by multiplying functions
with the characteristic or indicator function associated with the projection
domain. However, this method has a significant drawback in that characteristic
functions are discontinuous and cannot accurately approximate functions close
to the boundary, nor have defined derivatives at the edges. To overcome this,
smooth projection operators with higher-order derivatives are desirable.

An orthogonal projection operator $P$ must be self-adjoint and idempotent,
meaning $P^{2}=P.$ If we take the projection operator $P$ to be $Pf=Gf$ for
some function $G$, then

$P^{2}f=Pf\iff G^{2}-G=0\iff G(G-1)=0.$

Hence G must be 1 or 0 almost everywhere. Any characteristic function
satisfies this condition, and therefore, characteristic functions are often
used to construct projection operators on functional spaces. To derive a
smooth version of this process, some of the authors presented a method using
the cyclic permutation operators on $L^{2}(\mathbb{R}^{N})$, the space of
square-integrable functions on $\mathbb{R}^{N},$[5, 17] based on ideas derived
from wavelet theory [2, 13]. Here we provide a summary of the process for
completion.

To generate orthogonal projections into subspaces of $L^{2}(\mathbb{R}^{N})$
associated with some cone shape partitions of $\mathbb{R}^{N}$, let
$N\in\mathbb{N}$ and $T$ be the cyclic coordinate permutation operator on
$\mathbb{R}^{N}$. Let $x\in\mathbb{R}^{N}$, $s_{1}\in
C^{\infty}(\mathbb{R}^{N})$ and $s_{j}=s_{1}(T^{j-1}(\cdot))$ for $j=1,2,...N$
such that

$\sum_{j=1}^{N}|s_{j}|^{2}=1.$

For $f\in L^{2}(\mathbb{R}^{N})$, define $V_{j}$ as

$\displaystyle
V_{j}f=\frac{1}{\sqrt{N}}\overline{s_{j}}\sum_{\tau=0}^{N-1}w^{\tau
j}f(T^{\tau}(\cdot)),$

where $w=e^{\frac{2\pi i}{N}}$ is the $N^{th}$ root of unity. Then, the
operator $P$ defined as below is an orthogonal projection[5, 17].

######  Theorem 1.1.

$\displaystyle
P_{j}f(x)=V_{j}V_{j}^{\dagger}f(x)=\overline{s_{j}}\sum_{\tau=0}^{N-1}\overline{w^{\tau
j}}s_{j}(T^{\tau}(x))f(T^{\tau}(x))$

is an orthogonal projection on $L^{2}(\mathbb{R}^{N})$. If for each
$\tau\in\\{0,1,2,\dots,N-1\\}$,

$\sum_{j=1}^{N}w^{\tau
j}\overline{s_{j}}(x){s_{j+\tau}}(x)=\delta_{\tau,0}\,,$ (1)

we also have that for any $f\in L^{2}(\mathbb{R}^{N})$

$f=\sum_{j=1}^{N}P_{j}f.$

The constant functions $s_{j}=w\frac{1}{\sqrt{N}}$, for every $j$, and
$s_{j}=\frac{1}{\sqrt{N}}$, for every $j$, satisfy equation (1).[5, 17] A non-
smooth solution can be obtained by using indicator functions. If $U_{j}$ are
disjoint subsets of $\mathbb{R}^{N}$ such that
$\chi_{U_{j+1}}=\chi_{U_{j}}(T(\cdot))$ with
$\bigcup_{\tau=}^{N}U_{\tau}=R^{N}$, then $s_{j}=\chi_{U_{j}}$ is a solution
of (1). The authors also remark that there is a relationship between the
solutions of (1) and the solution of the filter equations associated with
M-band wavelets [15].

Figure 1: Smooth function $s$ on 2D [15]. This function is a smooth version of
the indicator function of a cone shape domian of $\mathbb{R}^{2}.$

In Section 2, we present our quantum algorithm, built upon the process of
constructing smooth orthogonal projections described earlier. Remarkably, we
find that this process is highly compatible with quantum computing. In Theorem
1.1, the projection operator $P$ was created using an explicit symmetrization
technique that involves the cyclic permutation operator $T$ and the $N^{th}$
root of unity $w$. Both $T$ and $w$ are cyclic, and the latter lies on the
Bloch sphere with a norm of one, which makes them particularly useful for
quantum computing. Moreover, by modifying the operators $P$ and $T$, we can
transform them into quantum gates that produce unitary operators. Indeed, we
have the following result:

######  Theorem 1.2.

Let $N\in\mathbb{N}$, $T$ be the cyclic coordinate permutation operator on
$\mathbb{R}^{N},$ $s_{1}\in C^{\infty}(\mathbb{R}^{N})$ and
$s_{j}=s_{1}(T^{j-1}(\cdot))$ for $j=1,2,...N$ such that

$\sum_{j=1}^{N}|s_{j}|^{2}=1.$

Assume for each $\tau\in\\{0,1,2,\dots,N-1\\}$,

$\sum_{j=1}^{N}w^{\tau j}\overline{s_{j}}(x){s_{j+\tau}}(x)=\delta_{\tau,0}\,$

where $\delta_{\tau,0}$ is the Kronecker delta. Then for $j,k=1,2,..,N$ the
matrix $U$ defined as

$U_{jk}=\overline{s}_{j}w^{jk},$

is unitary.

######  Proof 1.3.

We have that

$\displaystyle(U^{\dagger}U)_{jk}=\sum_{l=1}^{N}\overline{U}_{lj}U_{lk}=\sum_{l=1}^{N}(\overline{\overline{s}_{l}w^{lj}})(\overline{s}_{l}w^{lk})=\sum_{l=1}^{N}({s}_{l}w^{-lj})(\overline{s}_{l}w^{lk})=\sum_{l=1}^{N}\overline{s_{l}}s_{l}w^{(k-j)l}.$

Since $\sum_{j=1}^{N}|s_{j}|^{2}=1$, we have
$\sum_{j=1}^{N}s_{j}\overline{s}_{j}=1$, so

$\displaystyle(U^{\dagger}U)_{jk}=\sum_{l=1}^{N}\overline{s_{l}}s_{l}w^{(k-j)l}=\delta_{k-j,0}=\delta_{j,k}.$

Thus $U^{\dagger}U=I$ and similarly one can show $UU^{\dagger}=I$ and
therefore $U$ is unitary.

Note that the double index notation used in this context differs from
Einstein’s summation. In particular, the notation $U_{jk}$ denotes the element
located in the $j^{th}$ row and $k^{th}$ column of the matrix $U$.
Additionally, the expression $w^{jk}$ represents $w$ raised to the power of
$j$ multiplied by $k$. Theorem 1.2 imposes certain restrictions on the smooth
function $s_{j}$, but there exist numerous smooth functions that satisfy it.
Just as with Theorem 1.1, the constant functions $s_{j}=w\frac{1}{\sqrt{N}}$
for every $j$, and $s_{j}=\frac{1}{\sqrt{N}}$ for every $j$ are both solutions
to Theorem 1.2. In our quantum circuit, we will use
$s_{j}=\frac{1}{\sqrt{N}}$, but depending on the task at hand, one could
construct a more complex function $s_{j}$, as illustrated in Figure 1. For
instance, multiple sparse representation systems of Parseval frames were
smoothly combined using the function depicted in Figure 1, and additional
research on related topics has also been pursued. [9, 6].

Since each quantum gate for a single qubit is represented by a $2\times 2$
matrix, we make a special remark on 2D unitary operators created by the above
process. In 2D, the requirement that for each $\tau\in\\{0,1,2,\dots,N-1\\}$,

$\sum_{j=1}^{N}w^{\tau j}\overline{s_{j}}(x){s_{j+\tau}}(x)=\delta_{\tau,0}\,$

is satisfied by all 2D real functions $s_{j}$ with the property

$\sum_{j=1}^{N}|s_{j}|^{2}=1.$

This follows because the second root of unity is $w=e^{i\pi}=-1.$ In fact, for
a real valued 2D function $s_{1}$, the matrix $U$ has the following form

$U=\begin{bmatrix}s_{1}w^{0}&s_{2}w^{1}\\\
s_{2}w^{0}&s_{1}w^{2}\end{bmatrix}=\begin{bmatrix}s_{1}&-s_{2}\\\
s_{2}&s_{1}\end{bmatrix}.$

Then clearly

$UU^{\dagger}=\begin{bmatrix}s_{1}&-s_{2}\\\
s_{2}&s_{1}\end{bmatrix}\begin{bmatrix}s_{1}&s_{2}\\\
-s_{2}&s_{1}\end{bmatrix}=\begin{bmatrix}{s_{1}}^{2}+{s_{2}}^{2}&s_{1}s_{2}-s_{2}s_{1}\\\
s_{2}s_{1}-s_{1}s_{2}&{s_{1}}^{2}+{s_{2}}^{2}\end{bmatrix}=\begin{bmatrix}1&0\\\
0&1\end{bmatrix}.$

The cyclic permutation operator $T$ is the second tool we use to build quantum
gates. To illustrate, consider a sequence of numbers where all elements are
zero, except for one with a value of 1. By combining all possible cyclic
permutations of this sequence, we can create a unitary operator. We will
demonstrate this process of building unitary operators in the next section.
The Quantum Cyclic Permutation Algorithm (QCPA), which we developed in Section
2.1, shares similarities with the Bernstein-Vazirani algorithm [4]. However,
our approach was inspired by function analysis and sparse representation
theory.

##  2 Quantum Search Algorithm

Grover’s search algorithm is a crucial algorithm in the field of quantum
computing that allows for searching through an unsorted database at a much
faster rate than classical algorithms [12]. This algorithm provides a
quadratic speedup over classical search methods, making it a vital tool for
solving optimization and search problems across various fields, including
cryptography, machine learning, and artificial intelligence. The algorithm is
composed of three significant steps, namely superposition, phase flip, and
amplitude amplification, achieved via the application of the Hadamard gate,
Grover oracle, and diffusion operator, respectively, as shown in Figure 2. The
inversion about the mean, the last step of the algorithm, is particularly
useful for amplifying the probability amplitude of the marked state and has
been applied to solve problems in other fields, including linear algebra [7,
1].

Figure 2: Three steps of Grover’s Search algorithm: superposition, phase flip
and amplitude amplification.

This paper’s primary purpose is not to directly compare the runtime complexity
between our proposed algorithm and Grover’s search algorithm. Instead, we aim
to investigate the potential of constructing algorithms that outperform
theoretically optimal algorithms under certain conditions. Quantum systems are
subject to inherent problems such as noise, coherence, and measurement
accuracy, which can affect the performance of quantum algorithms in practice
[18]. Furthermore, exploring the relationship between functions with higher-
order derivatives may provide insights into solving quantum approximation
problems, for instance, state estimations [16].

###  2.1 Quantum Cyclic Permutation Algorithm (QCPA)

We now present a new quantum search algorithm based on the cyclic-permutation
oracle. Suppose we have a sequence $x=(x_{i})$ for $i=1,2,...,N$ such that

$x_{i}=\begin{cases}1&i=s\\\ 0&\text{otherwise}.\end{cases}$

We construct a quantum circuit capable of finding the “marked state” $s.$

Let $w=\exp(\frac{2\pi i}{N})$ be the $N^{th}$ root of unity and

$U=\frac{1}{\sqrt{N}}\begin{bmatrix}{w}^{0\cdot 1}&w^{1\cdot
1}&\dots&w^{(N-1)\cdot 1}&\\\ {w}^{0\cdot 2}&w^{1\cdot 2}&\dots&w^{(N-1)\cdot
2}&\\\ \vdots&\vdots&\ddots\ &\vdots&\\\
{w}^{0\cdot(N-1)}&w^{1\cdot(N-1)}&\dots&w^{(N-1)\cdot(N-1)}&\\\ {w}^{0\cdot
N}&w^{1\cdot N}&\dots&w^{(N-1)\cdot
N}&\end{bmatrix}=\frac{1}{\sqrt{N}}\begin{bmatrix}{w}^{0}&w^{1}&\dots&w^{N-1}&\\\
{w}^{0}&w^{2}&\dots&w^{N-2}&\\\ \vdots&\vdots&\ddots\ &\vdots&\\\
{w}^{0}&w^{N-1}&\dots&w^{1}&\\\ {w}^{0}&w^{0}&\dots&w^{0}&\end{bmatrix}$

The $N\times N$ unitary matrix $U$ is the $N$ dimensional version of the
matrix constructed in Theorem 1.2 with $s_{j}=\frac{1}{\sqrt{N}}$ and hence
can act as a quantum gate. Additionally, for any scalar vector $v=[v_{1}\quad
v_{1}\quad\cdot\cdots\quad v_{1}]^{T}$, it possesses the property:

$Uv=\begin{cases}\sqrt{N}v_{1}&i=N\\\ 0&\text{otherwise}.\end{cases}$

Furthermore, let us suppose that we have an oracle $F$ capable of shifting all
quantum states by $s$ unit counter-clockwise. This oracle can be constructed
using a cyclic permutation of the sequence $x$, where

$F=\begin{bmatrix}x_{1}&x_{2}\qquad&\dots&x_{N}&\\\
x_{2}&x_{3}\qquad&\dots&x_{1}\\\ \vdots\qquad&\vdots&\ddots\ &\vdots&\\\
x_{N-1}&x_{N}\qquad&\dots&x_{N-2}&\\\
x_{N}&x_{1}&\qquad\dots&x_{N-1}&\end{bmatrix}.$

Given that the sequence $x$ contains only one non-zero element, which is $1$,
the columns of the matrix $F$ are orthonormal, making $F$ unitary and
therefore a quantum gate. The oracle $F$ is a permutation matrix and shares
similarity with the oracle used in Grover’s search. Grover’s oracle flips the
phase of the $s^{th}$ quantum state while $F$ cyclically shifts all states $s$
times. With the necessary setup complete, we can now outline our quantum
algorithm, which involves three primary steps:

  * •

Superposition: achieved by applying the Hadamard gate

  * •

Collapse: collapsing the probabilities to the last quantum state using the $U$
gate

  * •

Shift: shifting all quantum states counter-clockwise by $s$ units using the
$F$ gate.

@C=4em @R=3em &0 H 3U 3F
0 H U F
0 H U F
0 H U F

Figure 3: Circuit representation for QCPA

Finally, we can determine the location of the marked state $x$ by calculating
$s=N+1-j$, where $j$ is the quantum state obtained after measurement. This is
because the cyclic permutation operator shifts the location of quantum states
by $s$ units.

In the following discussion, we will demonstrate the workings of our algorithm
for a three-qubit system, where the state $\ket{101}$ (sixth location of the
sequence) is marked.

  1. 1.

Apply Hadamard gates to $3$ qubits initialized to $\ket{000}$ to create a
uniform superposition:

$\ket{{\Psi}_{H}}=\frac{1}{\sqrt{8}}\big{(}\ket{000}+\ket{001}+\ket{010}+\ket{011}+\ket{100}+\ket{101}+\ket{110}+\ket{111}\big{)}$

  2. 2.

Collapse the probabilities of all quantum states except the last state by
applying gate $U$ to obtain one state with a probability of one:

$\ket{{\Psi}_{U}}=U\ket{{\Psi}_{H}}=\frac{1}{\sqrt{8}}\cdot\frac{8}{\sqrt{8}}\ket{111}=\ket{111}$

  3. 3.

Shift the remaining state $s$ unit counter-clockwise using oracle $F$, where
$s$ is the location of the marked state:

$\ket{{\Psi}_{F}}=F\ket{{\Psi}_{U}}=F\ket{111}=\ket{010}$

As a result of the measurement, the quantum state $\ket{010}$ is be obtained,
corresponding to the third position in the sequence. Therefore, the $1$ in the
initial sequence is located at position $s=N+1-3=8+1-3=6,$ which is the state
$\ket{101}$.

####  2.1.1 Understanding QCPA via matrix operations

Suppose we have a sequence $x=0,1,0,0$. Since $N=4$, $w=\exp(\frac{2\pi
i}{4})=\exp(\frac{\pi i}{2})=i.$ Then

$U=\frac{1}{\sqrt{4}}\begin{bmatrix}{i}^{0\cdot 1}&i^{1\cdot 1}&i^{2\cdot
1}&i^{3\cdot 1}&\\\ {i}^{0\cdot 2}&i^{1\cdot 2}&i^{2\cdot 2}&w^{3\cdot 2}&\\\
{i}^{0\cdot 3}&i^{1\cdot 3}&i^{2\cdot 3}&w^{3\cdot 3}&\\\ {i}^{0\cdot
4}&i^{1\cdot 4}&i^{2\cdot 4}&w^{3\cdot
4}&\end{bmatrix}=\frac{1}{2}\begin{bmatrix}{i}^{0}&i^{1}&i^{2}&i^{3}&\\\
{i}^{0}&i^{2}&i^{0}&i^{2}&\\\ {i}^{0}&i^{3}&i^{2}&i^{1}&\\\
{i}^{0}&i^{0}&i^{0}&i^{0}&\end{bmatrix}=\frac{1}{2}\begin{bmatrix}1&i&-1&-i&\\\
1&-1&1&-1&\\\ 1&-i&-1&i&\\\ 1&1&1&1&\end{bmatrix}$

and

$F=\begin{bmatrix}0&1&0&0&\\\ 1&0&0&0&\\\ 0&0&0&1&\\\ 0&0&1&0&\end{bmatrix}$

Figure 4: Histogram of measurement outcomes on IBM hardware for finding the
location 1 in a sequence of four numbers. The state $\ket{10}$ is the expected
state predicted by QCPA.

Now, if we initialize 2 qubits to $0$ states and feed them through the
Hadamard gate, we get a superposition state $q=[q_{1}\quad q_{2}\quad
q_{3}\quad q_{4}]^{T},$ where $|q_{i}|=\frac{1}{2}.$ For simplicity, we write
$q=[0.5\quad 0.5\quad 0.5\quad 0.5]^{T}.$

$FUq=\frac{1}{2}\begin{bmatrix}0&1&0&0&\\\ 1&0&0&0&\\\ 0&0&0&1&\\\
0&0&1&0&\end{bmatrix}\begin{bmatrix}1&i&-1&-i&\\\ 1&-1&1&-1&\\\ 1&-i&-1&i&\\\
1&1&1&1&\end{bmatrix}\begin{bmatrix}0.5\\\ 0.5\\\ 0.5\\\ 0.5\end{bmatrix}$

$\qquad=\frac{1}{2}\begin{bmatrix}0&1&0&0&\\\ 1&0&0&0&\\\ 0&0&0&1&\\\
0&0&1&0&\end{bmatrix}\begin{bmatrix}0\\\ 0\\\ 0\\\ 2\end{bmatrix}$

$=\begin{bmatrix}0\\\ 0\\\ 1\\\ 0\end{bmatrix}$

This implies that the third quantum state will appear with a probability of
$1$ if a measurement is performed. Figure 4 presents an experimental
verification of the algorithm’s accuracy in determining the third quantum
state (i.e., 10) using IBM hardware. As anticipated, the results demonstrate
that the algorithm accurately predicted the correct quantum state. Once a
measurement is performed, the marked location is given by $s=N+1-j=5-3=2.$

The overall complexity of constructing the permutation quantum gate using a
sequence of the length of $N$ is $O(N^{2}).$ This is because the process of
creating each row of the gate requires $O(N)$ operations, and since there are
$N$ rows, the total complexity is $O(N^{2}).$ Once the gate is built, we only
require one step operation for detecting the marked state, so the complexity
of the entire algorithm is $O(N^{2}).$ Despite Grover’s method having lower
computational complexity than QCPA and QUSA, which is presented in Section
2.2, several advantages are associated with these algorithms. For instance,
both QCPA and QUSA demonstrate lower noise susceptibility, as seen in Section
3. Additionally, these methods contribute to advancing our theoretical
comprehension of search algorithms and offer a pathway for constructing
quantum circuits utilizing smooth operators.

###  2.2 Quantum Unity Sum Algorithm (QUSA)

The Quantum Unity Sum Algorithm (QUSA) is the second novel search algorithm
presented in this work. It bears similarities to the QCPA introduced in
Section 2.1, but it also features two distinctive elements. Firstly, QUSA
employs a function $f$, similar to the one used in Grover’s search, which
outputs $0$ for the marked state and $1$ for all other states. Secondly,
instead of explicitly using the permutation oracle, QUSA adjusts the unitary
operator $U$ by leveraging a well-known property of the $N^{th}$ root of
unity. This property allows the probability to be shifted to the correct
quantum state. If

$U=\frac{1}{\sqrt{N}}\begin{bmatrix}{w}^{0}&w^{1}&\dots&w^{N-1}&\\\
{w}^{0}&w^{2}&\dots&w^{N-2}&\\\ \vdots&\vdots&\ddots\ &\vdots&\\\
{w}^{0}&w^{N-1}&\dots&w^{1}&\\\ {w}^{0}&w^{0}&\dots&w^{0}&\end{bmatrix}$

then each element of the matrix $U$ in the $k$-th row and $l$-th column can be
represented as

$U_{kl}=\frac{1}{\sqrt{N}}w^{k(l-1)}$

@C=4em @R=3em &0 H 3~U
0 H U
0 H U
0 H U

Figure 5: Circuit representation for QUSA

We construct a new oracle $\tilde{U}$ capable of locating the marked state.
For $k=1,2,....,N-1$ let

$\tilde{U}_{kl}=({U}_{kl})^{(f(x_{k}))}$

and $S=\frac{1}{\sqrt{N}}\bigg{(}-\sum_{k=1}^{N-1}{U}_{kN}\bigg{)}^{-1}.$ The
last row of $\tilde{U}$ is given by

$\tilde{U}_{Nl}=\frac{1}{\sqrt{N}}{S^{l-1}}.$

The new unitary matrix $\tilde{U}$ has the property that for any scalar vector
$v=[v_{1}\quad v_{1}\quad\cdot\cdots\quad v_{1}]^{T},$

$\tilde{U}v=\begin{cases}\sqrt{N}v_{1}&i=s\\\ 0&\text{otherwise}.\end{cases}$

where $s$ is the marked state.

This approach involves a quantum circuit with the following sequence of steps:

  * •

Set all quantum states to the zero state

  * •

Use the Hadamard gate to create superposition

  * •

Apply the gate $\tilde{U}$

  * •

Perform a measurement

This completes the construction of our new circuit, and Figure 6 displays the
measurement results obtained by running this circuit on an IBM quantum
computer to locate the marked state of a sequence. This algorithm exploits a
key property of the $N^{th}$ root of unity, namely, that the sum of the roots
of unity is zero. The procedure involves generating $N-1$ rows of the unitary
operator $\tilde{U}$ by exponentiating the $i^{th}$ row of $U$ by $f(x_{i})$.
Since $f(x_{i})$ equals 1 for all but the marked state $s$, the rows of
$\tilde{U}$ corresponding to $x_{i}$ other than $s$ remain identical to the
corresponding rows of $U$, while the row corresponding to $s$ is set to all
ones. To ensure that $\tilde{U}$ is isometric, we construct its last row using
the $N-1$ previously constructed rows.

Figure 6: Histogram of measurement outcomes on IBM hardware for finding the
location 1 in a sequence of eight numbers. The state $011$ is the expected
state predicted by QUSA described in Section 2.2.

##  3 Noise Analysis

Quantum error correction and related topics have been extensively studied in
quantum computing, given the susceptibility of quantum hardware and
measurement instruments to errors [8, 14]. Error propagation can cause poor
performance in algorithms requiring more gate operations or larger circuits.
Here, we investigate how our algorithms perform when noise is added to the
system. We demonstrate that our one-step search algorithm is less susceptible
to noise than Grover’s search algorithm, which requires multiple iterations.
For this purpose, we performed two sets of experiments to verify this claim:
noise-added simulations and actual quantum hardware testing. All the quantum
circuits we used in this study were built and transpiled using the Qiskit
package in Python. We used the universal gates CX and U3 in the circuit
construction process. To simulate a noisy system, we added depolarizing errors
to single-qubit U3 and CX gates, which can model the effect of imperfect
control or environmental interaction. The depolarizing error was applied with
the probability of 0.001 gate error for both types of gates. We applied an
equal number of noisy gates to both our algorithms and Grover’s search
algorithm to examine the impact of error propagation on their performance and
to ensure a fair comparison of the three methods. We applied noise to the
first n-gates and let the noise propagate. Since the Grover search algorithm
is iterative, it necessitates more gate operations than our approach as the
number of states grows. Figure 7 presents a bar graph depicting the number of
gates required to execute each algorithm via the transpiler. As the sequence
order we are seeking rises, the Grover technique demands considerably more
gate operations than the other two. As expected, Grover’s search algorithm
predicted the right quantum state but with much less accuracy than our
algorithm. Table 1 presents the simulation results, while Figure 7 shows that
the QUSA requires fewer gates than QCPA to run, and consequently, the QUSA is
less susceptible to noise than QCPA.

Table 1: Comparison of Accuracy  Qubits | Grover | QCPA | QUSA
---|---|---|---
| Number of Noisy Gates | Number of Noisy Gates | Number of Noisy Gates
| 2 | 4 | 6 | 2 | 4 | 6 | 2 | 4 | 6
3 | 90.62 | 90.14 | 88.09 | 98.54 | 97.85 | 96.97 | 98.83 | 97.95 | 97.46
4 | 76.66 | 61.72 | 58.50 | 89.84 | 82.42 | 81.35 | 94.82 | 90.04 | 88.96
5 | 30.47 | 11.33 | 6.93 | 66.41 | 42.97 | 40.82 | 78.52 | 66.80 | 58.40
Figure 7: Number of gates in transpiled circuits for each of the three
methods.

To further validate our assumption, we tested both algorithms on actual
quantum hardware, which naturally introduces errors due to measurement and
other quantum system issues. Our algorithm outperformed Grover’s search, just
as in the noisy simulation case. The measurement results for a two-qubit
system consisting of four states, to predict the marked state of 10 using both
algorithms and Grover’s method, are presented in Table 2. Grover’s method had
a success rate of $94.04\%$, while our algorithm performed slightly better
with a success rate of $96.19\%$. The QUSA also performed well, with a success
rate of $95.60\%$. These findings support our assumption that one-step search
is less error-prone compared to Grover’s search, which can exacerbate errors
at each iteration. This is particularly relevant since quantum systems are
highly susceptible to measurement and other errors.

Table 2: Measurement results using Grover’s method, QCPA and QUSA for a two-qubit system (4 states) in predicting the marked state $\ket{10}$ on IBM quantum computer (ibm_jakarta). The simulation was conducted $1024$ times for each method.  Algorithm  | Quantum State | Performance(%)
---|---|---
00 | 01 | 10 | 11 |
Grover | 50 | 3 | 963 | 8 | 94.04
QCPA | 27 | 0 | 985 | 12 | 96.19
QUSA | 25 | 10 | 979 | 10 | 95.60

##  4 Conclusion

Previous related works in shearlet and wavelets used permutation operators to
achieve symmetrization, ensuring that the functions remained infinitely
differentiable at the intersection of N-dimensional partitions [17, 5, 2].
However, we used permutation operators for a different purpose: to shift
quantum states. Furthermore, smooth projection operators and shearlet theory
utilized the sum of the roots of unity equals zero to achieve perfect signal
reconstruction by carefully balancing the contributions from each partition of
the projected signal [9]. In contrast, our approach involves utilizing this
same property of the roots of unity to construct a unitary operator that
shifts the probabilities toward the marked quantum state. This demonstrates
that concepts derived from wavelet and shearlet theories can be adapted to
address quantum computing problems. Additionally, our algorithm demonstrated
better accuracy than the Grover search algorithm in predicting the correct
quantum state. This enhanced performance may be attributed to the fact that
our one-step search algorithms do not rely on the Grover oracle explicitly and
are non-iterative, unlike Grover’s algorithm.

We introduced two novel search algorithms that rely on smooth operators. Our
primary objective was to establish a link between infinitely differentiable
operators and quantum computing, which could lead to the development of new
quantum algorithms capable of leveraging the excellent approximation
properties of derivatives. Although we employed a single smooth function
$s_{j}=\frac{1}{N}$ to construct both algorithms, other smooth functions could
also be utilized to construct quantum operators that address the given
problems. Additional research could explore ways to decrease the runtime
complexity of both methods and develop novel quantum algorithms that utilize
smooth functions. These investigations need not be limited to search
algorithms but can encompass a broader range of applications within quantum
computing. This approach has the potential to expand our theoretical
understanding of quantum computing significantly.

## References

  * [1] Andris Ambainis.  Variable time amplitude amplification and quantum algorithms for linear algebra problems.  In STACS’12 (29th Symposium on Theoretical Aspects of Computer Science), volume 14, pages 636–647. LIPIcs, 2012.
  * [2] Pascal Auscher, Guido Weiss, and M. Victor Wickerhauser.  Local Sine and Cosine Bases of Coifman and Meyer and the Construction of Smooth Wavelets, page 237–256.  Academic Press Professional, Inc., USA, 1993.
  * [3] Richard T Behrens and Louis L Scharf.  Signal processing applications of oblique projection operators.  IEEE Transactions on signal processing, 42(6):1413–1424, 1994.
  * [4] Ethan Bernstein and Umesh Vazirani.  Quantum complexity theory.  SIAM Journal on Computing, 26(5):1411–1473, 1997.
  * [5] Bernhard G Bodmann, Demetrio Labate, and Basanta R Pahari.  Smooth projections and the construction of smooth parseval frames of shearlets.  Advances in Computational Mathematics, 45(5):3241–3264, 2019.
  * [6] Marcin Bownik and Karol Dziedziul.  Smooth orthogonal projections on sphere.  Constructive Approximation, 41(1):23–48, 2015.
  * [7] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp.  Quantum amplitude amplification and estimation.  Contemporary Mathematics, 305:53–74, 2002.
  * [8] Simon J Devitt, William J Munro, and Kae Nemoto.  Quantum error correction for beginners.  Reports on Progress in Physics, 76(7):076001, 2013.
  * [9] Glenn R Easley, Kanghui Guo, Demetrio Labate, and Basanta R Pahari.  Optimally sparse representations of cartoon-like cylindrical data.  The Journal of Geometric Analysis, 31(9):8926–8946, 2021.
  * [10] Lev Goldfarb.  A unified approach to pattern recognition.  Pattern Recognition, 17(5):575–582, 1984.
  * [11] J Scott Goldstein, Irving S Reed, and Louis L Scharf.  A multistage representation of the wiener filter based on orthogonal projections.  IEEE Transactions on Information Theory, 44(7):2943–2959, 1998\.
  * [12] Lov K Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996.
  * [13] Eugenio Hernández and Guido Weiss.  A first course on wavelets.  CRC press, 1996.
  * [14] Daniel A Lidar and Todd A Brun.  Quantum error correction.  Cambridge university press, 2013.
  * [15] Tony Lin, Shufang Xu, Qingyun Shi, and Pengwei Hao.  An algebraic construction of orthonormal m-band wavelets with perfect reconstruction.  Applied Mathematics and Computation, 172(2):717 – 730, 2006.  Special issue for The Beijing-HK Scientific Computing Meetings.
  * [16] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost.  Quantum algorithms for supervised and unsupervised machine learning.  arXiv preprint arXiv:1307.0411, 2013.
  * [17] Basanta Raj Pahari.  Smooth Projections and Optimally Sparse Representation of Cartoon-like Cylindrical Solids.  PhD thesis, University of Houston, 2020.
  * [18] John Preskill.  Quantum computing in the nisq era and beyond.  Quantum, 2:79, 2018.