# Generalized Few-Shot Point Cloud Segmentation Via Geometric Words

Yating Xu1 Conghui Hu1 Na Zhao2 Gim Hee Lee1
1Department of Computer Science, National University of Singapore
2Singapore University of Technology and Design
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Na Zhao was concurrently a visiting professor at the
National University of Singapore when this work was done.

###### Abstract

Existing fully-supervised point cloud segmentation methods suffer in the
dynamic testing environment with emerging new classes. Few-shot point cloud
segmentation algorithms address this problem by learning to adapt to new
classes at the sacrifice of segmentation accuracy for the base classes, which
severely impedes its practicality. This largely motivates us to present the
first attempt at a more practical paradigm of generalized few-shot point cloud
segmentation, which requires the model to generalize to new categories with
only a few support point clouds and simultaneously retain the capability to
segment base classes. We propose the geometric words to represent geometric
components shared between the base and novel classes, and incorporate them
into a novel geometric-aware semantic representation to facilitate better
generalization to the new classes without forgetting the old ones. Moreover,
we introduce geometric prototypes to guide the segmentation with geometric
prior knowledge. Extensive experiments on S3DIS and ScanNet consistently
illustrate the superior performance of our method over baseline methods. Our
code is available at: https://github.com/Pixie8888/GFS-3DSeg_GWs.

##  1 Introduction

Point cloud segmentation aims at predicting the category of each point in the
3D scenes represented by the point cloud, and has wide applications in
autonomous driving, robotics, _etc_. Although fully-supervised point cloud
segmentation methods (Full-3DSeg) [19, 20, 28, 11, 9, 29] have achieved
impressive performance, they heavily require large-scale annotated training
data and rely on the closed set assumption that the class distribution of the
testing point cloud remains the same as the training dataset. However, the
closed set assumption is unrealistic in the open world where new classes arise
continuously. The Full-3DSeg in this challenging open-world setting thus
requires large amounts of annotated data for new classes, which are time-
consuming and expensive to collect.

The few-shot point cloud segmentation (FS-3DSeg) [35, 14, 8] algorithms are
designed to ameliorate the lack of data for novel class adaptation. Generally,
FS-3DSeg first trains a model with abundant training samples of the base
classes, and then targets at segmenting the new classes by learning from only
a small number of samples from the corresponding new classes. By adopting
episodic training [26] to mimic the testing environment and specific designs
for feature extraction [35], FS-3DSeg achieves promising novel class
segmentation results for the query point clouds. However, in the task of point
cloud segmentation, base and novel classes often appear together in one scene
(see Figure 5 as examples). An ideal segmentor in practice is expected to give
each point in the scene a semantic label. As a result, the FS-3DSeg setting
that only segments points of novel classes while ignoring the base classes
suffers limited practicality.

Figure 1: Visualization of the geometric words (GWs) on S3DIS. The left figure
shows the original point cloud and the right figure shows the activated point
cloud to a geometric word. The activated points are colored green. It shows
the horizontal planes of the sofa, table and chair are all activated to the
same GW due to similar geometric structure.

In view of the impracticality of FS-3DSeg, we introduce the generalized few-
shot point cloud segmentation (GFS-3DSeg) task. As shown in Tab. 1, given the
model originally trained on base classes, the objective of GFS-3DSeg is to
segment both base and novel classes using merely a limited number of labeled
samples for the new classes during testing. Furthermore, there is no access to
the base training data during testing in GFS-3DSeg considering the issues of
data privacy and storage memory limitations. In this demanding but practical
context, we expect a good generalized few-shot point cloud segmentor to
effectively learn to segment novel classes with few samples and also maintain
the knowledge of the base classes. A potential solution to GFS-3DSeg can be
using prototype learning [25, 21] to generate class prototypes of the base and
novel classes as the classifier weights, which can quickly adapt to new
classes and avoid forgetting past knowledge caused by fine-tuning. However,
effective learning of the representation and classifier for the novel classes
is not trivial and remains as a major challenge.

In this paper, we propose geometric words111Analogous to visual words in bag-
of-words image retrieval systems [17]. (GWs) as the transferable knowledge
obtained from the base classes to enhance the learning of the new classes
without forgetting the old ones. Although different (old and new) classes
contain distinct semantic representations, they usually share similar local
geometric structures as shown in Fig. 1. Based on this observation, we first
mine the representation for the local geometric structures from the pretrained
features of the base classes and store them as the geometric words to
facilitate learning of the new classes with few examples. We then learn a
geometric-aware semantic representation based on the geometric words.
Specifically, the geometric-aware semantic representation is a fusion of two
features: 1) Class-agnostic geometric feature obtained by the assignment of
low-level features to their most similar geometric words. 2) Class-specific
semantic feature which is the output of a feature extractor. Intuitively, our
geometric-aware semantic representation allows the encoding of the
transferable geometric information across classes while preserving the
semantic information for effective segmentation.

We further introduce geometric prototype (GP) to supplement the original
semantic prototype in the prototype learning. Particularly, the geometric
prototype refers to the frequency histogram of GWs that can uniquely represent
each class from the global geometric perspective despite GWs are class
agnostic. We thus leverage GP to propose a geometric-guided classifier re-
weighting module for the rectification of biased predictions originating from
semantic prototypes. Specifically, we first perform minor frequency pruning on
the geometric prototypes to suppress noisy responses of the geometric words
for each class. Subsequently, we measure the geometric matching score between
each query point and the pruned geometric prototypes, and employ these scores
as geometric-guided weights. By re-weighting the semantic logits with
geometric-guided weights, our final prediction is enriched with geometric
information that is transferable across classes. Such transferable information
helps to facilitate the segmentation of new classes that only have a few
samples while preserving the knowledge of base classes. Our main contributions
can be summarized as:

Setting | Training Stage | Testing Stage
---|---|---
Learn $D_{\text{train}}^{b}$ | Learn $D_{\text{train}}^{n}$ | Access $D_{\text{train}}^{b}$ | Test Classes
Full-3DSeg | ✓ | ✗ | ✗ | $C^{b}$
FS-3DSeg | ✓ | ✓ | ✗ | $C^{n}$
GFS-3DSeg | ✓ | ✓ | ✗ | $C^{b}\cup C^{n}$

Table 1: The comparison of different settings. $D_{\text{train}}^{b}$ and
$D_{\text{train}}^{n}$ denotes the training dataset of base and novel classes,
respectively. $D_{\text{train}}^{b}$ has sufficient training data, while
$D_{\text{train}}^{n}$ only has few shots for each new class. $C^{b}$ and
$C^{n}$ denotes the label set for base classes and novel classes,
respectively.

  * •

We are the first to study the important generalized few-shot point cloud
segmentation task, which is more practical than its counterparts of fully-
supervised and few-shot setting in the dynamic testing environment.

  * •

We propose geometric words to represent diverse basic geometric structures
that are shared across different classes, and a geometric-aware semantic
representation that allows for generalizable knowledge encoding.

  * •

We introduce geometric prototype to supplement the semantic prototype. We
design a geometric-guided classifier re-weighting module comprising minor
frequency pruning to dynamically guide the segmentation of novel classes with
geometric similarity.

  * •

We conduct extensive experiments on S3DIS and ScanNet to verify the
effectiveness of our method. Specifically, our method improves over the state-
of-the-art FS-3DSeg method by 6 and 8 times on the 5-shot and 1-shot settings
of ScanNet, respectively.

##  2 Related Work

#### Few-shot Learning.

Few-shot learning aims at classification of novel classes by learning with
only a few labeled samples during testing stage. There are mainly three types
of approaches: meta-learning [5, 15, 16, 10], metric-learning [23, 26, 32, 18]
and transfer learning based methods [24, 13]. Meta-learning based methods aim
to predict a set of parameters that can be quickly adapted to new tasks.
Metric-learning methods learn a mapping from images to an embedding space
where images of the same class are clustered together. Transfer learning
methods aim to learn a general feature representation during base class
training, and then train a classifier for each new task.

Generalized few-shot learning is first proposed in [7], which aims to classify
both base and novel classes after learning from the few-shot training samples
of novel classes during testing stage. Gidaris _et al_. [6] and Qi _et al_.
[21] introduce cosine similarity between image feature and classifier weight
as the classifier, which unifies the recognition of both novel and base
categories. To reduce the biased learning of base classes, Gidaris _et al_.
[6] and Ye _et al_. [31] improve the classifier of the novel classes by
utilizing the knowledge of base classes. Gidaris _et al_. [6] propose few-shot
classification weight generator to perform attention over the classification
weight vectors of the base classes. Ye _et al_. [31] synthesize calibrated
few-shot classifiers with a shared neural dictionary learned in the base class
training stage. In this work, we study generalized few-shot point cloud
segmentation, a more challenging task as it targets at dense 3D point-level
classification. Instead of fusion classifier weights of novel classes with
past knowledge [6, 31], we use geometric prototype as an additional classifier
weight to help calibrate the biased prediction. Moreover, we propose
geometric-aware semantic representation to facilitate the representation
learning for novel classes.

Figure 2:  The overview of our proposed framework. (a) GW Generation: shows
the generation of geometric words from base class training data. (b)
Geometric-aware Semantic representation (GSR): semantic feature
$f_{\text{sem}}$ is fused with geometric feature $f_{\text{geo}}$ as the final
representation $f_{\text{fin}}$ for each point. (c) GP Generation: shows the
generation of the geometric prototype $p_{\text{geo}}^{c}$ for class c. (d)
Geometric-guided Classifier Re-weighting (GCR): we compute geometric matching
between geometric feature $\hat{f}_{\text{geo}}$ and pruned GP
$p_{\text{pgeo}}^{c}$ to find potential target classes and derive weight
$w^{c}$ to supplement semantic prediction $l_{\text{sem}}^{c}$.
$l_{\text{fin}}^{c}$ is the final prediction logit of class c.

#### Few-shot Semantic Segmentation.

Few-shot semantic segmentation performs segmentation of novel classes for
images [12, 34, 33, 22] or point clouds [35, 8, 14] by only learning from a
few support samples. The methods for few-shot image semantic segmentation can
be categorized into metric-based [27, 12] and relation-based [34, 33] methods.
Metric-based methods aggregate prototypes from the support set as the
classifier, and perform cosine similarity with the query features. Relation-
based methods concatenate the support features with query features for dense
feature comparison via deep convolutional network. Few-shot point cloud
segmentation [35] also adopts metric-based technique by performing label
propagation among the query points and the multi-prototypes of each class to
infer the query point label.

Generalized few-shot image semantic segmentation (GFS-2DSeg) [25, 2] aims to
segment both base and novel classes in the query images during testing stage,
which is more practical than the few-shot setting. CAPL [25] leverages the
contextual cues from the support set and query images to enhance the
classifier weights of the base classes. PIFS [2] finetunes on the support set
of novel classes during testing stage and proposes prototype-based
distillation loss to combat catastrophic forgetting of base classes. In this
paper, we study generalized few-shot point cloud semantic segmentation
(GFS-3DSeg), a practical yet unexplored task. Different from GFS-2DSeg which
assumes the annotation of base classes is available in the novel training
samples, we strictly follow the definition of GFSL that only the annotation of
novel classes are provided in the support set. Consequently, both CAPL and
PIFS fail to work properly under the GFS-3DSeg since both rely on the co-
occurence of base classes in the support sets of novel classes to calibrate
the imbalanced learning between base and novel classes. To solve this
challenging problem, we propose to mine the representation for the basic
geometric structures as the transferable knowledge to improve the
representation and classifier of the novel classes.

#### Geometric Primitives

Geometric primitives are the fundamental components for the 3D objects, and
has been initially studied in the transfer learning in 3D [3, 36]. Chowdhury
_et al_. [3] use microshapes as the basic geometric components to describe any
3D objects in the 3D object recognition task. However, object-level annotation
is not available for the query point cloud in the point cloud semantic
segmentation or object detection. Therefore, Zhao _et al_. [36] only utilize
the geometric information at point-level by enhancing the local geometric
representation of each query point with a geometric memory bank. Although we
also performs point-level enhancement in our geometric-aware semantic
representation, different from Zhao _et al_. [36], we inject geometric
information to the high-level semantic representation to help model understand
the geometric structures through learning the class semantics. Moreover, we
propose to use the geometric prototype as the global geometric enhancement to
each class to calibrate the biased prediction during testing stage.

##  3 Problem Formulation

In generalized few-shot point cloud semantic segmentation, a base class
training dataset $D_{\text{train}}^{b}$, and a novel class training dataset
$D_{\text{train}}^{n}$ with non-overlapping label space $C^{b}\cap
C^{n}=\varnothing$ are provided. The testing dataset $D_{\text{test}}$ has a
label space $C_{\text{test}}=C^{b}\cup C^{n}$. During the training stage, the
model learns the base classes $C^{b}$ from abundance of labeled point cloud
data
$D_{\text{train}}^{b}=\left\\{\left(P_{k}^{b},M_{k}^{b}\right)_{k=1}^{\left|D_{\text{train}}^{b}\right|}\right\\}$,
where $\left|D_{\text{train}}^{b}\right|$ denotes the size of
$D_{\text{train}}^{\text{b}}$. Each point cloud
$P_{k}^{b}\in\mathbb{R}^{m\times d_{0}}$ contains $m$ points with feature
dimension $d_{0}$ and $M_{k}^{b}$ denotes the annotation of $C^{b}$ in
$P_{k}^{b}$.

During the testing stage, the model first learns $C^{n}$ from limited labeled
data
$D_{\text{train}}^{n}=\left\\{\left(P_{k}^{n,i},M_{k}^{n,i}\right)_{k=1}^{K}\right\\}_{i=1}^{\left|C^{n}\right|}$,
with $K$ support point clouds per novel class $C^{n,i}\in C^{n}$, and
$\left|C^{n}\right|$ is the number of novel classes.
$P_{k}^{n,i}\in\mathbb{R}^{m\times d_{0}}$ and $M_{k}^{n,i}$ is the binary
mask indicating the presence of $C^{n,i}$. Note that during testing stage, the
model does not have access to $D_{\text{train}}^{b}$. The testing dataset
$D_{\text{test}}=\left\\{\left(P_{k}^{q},M_{k}^{q}\right)_{k=1}^{\left|D_{\text{test}}\right|}\right\\}$,
with each query point cloud $P_{k}^{q}\in\mathbb{R}^{m\times d_{0}}$.
$M_{k}^{q}$ represents the ground-truth annotation of $C_{\text{test}}$ in
$P_{k}^{q}$. The goal of GFS-3DSeg is to correctly segment both $C^{b}$ and
$C^{n}$ in the testing query point cloud.

##  4 Our Method

#### Background.

We adopt prototype learning to segment both base and novel classes during
testing stage. Class prototypes are learned as the classifier weight for each
class. Base class prototypes are learned in the training stage via gradient
descent, and novel class prototypes are learned by aggregating the foreground
features of the support set during the testing stage. We name the prototype
“semantic prototype” since it captures the semantic information of each class.
The prediction of each query point is assigned by the class label of the most
similar semantic prototypes. However, naively adopting prototype learning is
insufficient to learn well on new classes due to the small support set. We
thus propose geometric-aware semantic representation and geometric-guided
classifier re-weighting to help segmenting new classes.

#### Framework Overview.

Fig. 2 shows the overview our framework, which consists of four main parts: a)
The geometric words (GWs) to enhance the representation and classifier of the
new classes. b) The geometric-aware semantic representation (GSR) based on the
GWs to learn a transferable representation during the base class training
stage. we first get the geometric feature of a point as the assignment of the
GWs to the point. We then fuse the geometric feature with its corresponding
semantic feature to get the final GSR. c) The geometric prototype (GP) to
supplement the semantic prototype learned from the insufficient training
samples. Specifically, a GP is the frequency histogram of the GWs assigned to
the points in each class that can uniquely describe the class from the global
geometric perspective. d) The geometric-guided classifier re-weighting (GCR)
based on GPs to provide prior knowledge of each query point belonging to the
potential target classes based on the geometric similarity.

Figure 3: Motivation for geometric-guided classifier re-weighting. For each
histogram, the horizontal axis represents the index of the GWs and the
vertical axis represents the normalized frequency ratio within the class or
point. (a) Visualize the geometric feature $\hat{f}_{\text{geo}}$ of the
yellow query point on the window frame. (b),(c) and (d) shows the geometric
prototypes of window, door and beam, respectively. The red bar denotes the GW
with same index.

###  4.1 Geometric Words

Unlike its 2D images counterpart, 3D point clouds contain complete geometric
information with shared basic geometric components. Understanding these basic
geometric components helps learning across old and new classes due to the
shared similar local geometric structures. We thus propose geometric words as
the representation of these basic geometric components, and utilize it during
training and testing stage to facilitate learning of new classes from few
shots training point clouds.

To obtain the geometric words, we pretrain the feature extractor $E$ of
attMPTI [35] on $D_{\text{train}}^{b}$ and collect the features
$\left\\{f_{\text{low}}\right\\}$ of all the points belonging to $C^{b}$. We
concatenate the output feature of the first three EdgeConv layers and denote
it as $f_{\text{low}}\in\mathbb{R}^{d_{1}}$ since lower level features
contains more geometric cues. We then obtain $H$ geometric words
$\mathcal{G}=\left\\{g_{h}\right\\}_{h=1}^{H}\in\mathbb{R}^{H\times d_{1}}$ by
applying K-means on $\left\\{f_{\text{low}}\right\\}$ to calculate the $H$
centroids. Each $g_{h}$ is a local aggregation of the points with similar
$f_{\text{low}}$, _i.e_. similar geometric characteristic.

Fig. 1 visualizes the point-to-GWs assignments by searching points with
$f_{\text{low}}$ that are most similar to a given geometric word $g_{h}$. As
shown in Fig. 1, the horizontal plane of the chair, tables and sofas are all
activated to the same geometric word. It suggests that our GWs are able to
represent shared geometric components among different classes.

#### Geometric-aware Semantic Representation.

Based on the GWs, we propose the geometric-aware semantic representation (GSR)
to enhance the feature representation of the new classes. The GSR is a fusion
of a class-agnostic geometric feature $f_{\text{geo}}\in\mathbb{R}^{H}$ and a
class-specific semantic feature $f_{\text{sem}}\in\mathbb{R}^{d_{2}}$.
Specifically, the geometric feature $f_{\text{geo}}$ that represents the
geometric information of each point is computed by the soft-assignment of its
feature $f_{\text{low}}$ to its most similar GW as follow:

$f_{\text{geo}}=\operatorname{Softmax}\left(\left[f_{\text{low}}\cdot
g_{1},\ldots,f_{\text{low}}\cdot g_{H};\tau\right]\right),$ (1)

where $\cdot$ denotes the cosine similarity between the feature and a
geometric word. $\tau$ is the temperature to sharpen the probability vector,
and we empirically set it to 10. We adopt soft assignment to make it
differentiable with respect to the feature extractor. We use the final output
of $E$ as the semantic feature $f_{\text{sem}}$. Subsequently,
$f_{\text{geo}}$ and $f_{\text{sem}}$ are concatenated and sent into a small
convolution block $E_{\text{fuse}}$ to obtain the final representation
$f_{\text{final}}\in\mathbb{R}^{d_{3}}$ for each point as follow:

$f_{\text{fin}}=E_{\text{fuse}}\left(f_{\text{geo}}\parallel
f_{\text{sem}}\right),$ (2)

where $\parallel$ represents the concatenation of two vectors.

During base class training, we simulate query and fake novel class support set
in each batch following [25] to enhance the model’s adaptability to unseen
environments. The optimization objective is to minimize cross-entropy loss
computed by the prototypes generated through the assembling of
$\left\\{p_{\text{sem}}^{c}|c\in C^{b}\right\\}$ and the fake novel prototypes
from the simulated support set. We refer readers to [25] for a more
comprehensive understanding of the training strategy.

###  4.2 Geometric prototype

Although GWs are class-agnostic, their combinations are able to represent
different classes in a geometric way. We visualize the frequency of GWs
assigned to the points in different classes in Fig. 3(b), (c) and (d). The
horizontal axis represents the index of the GWs and the vertical axis
represents the normalized frequency ratio. The histogram conveys the global
structure of each class via the frequency ratios of the GWs, and different
classes have different histograms. The histogram thus uniquely represents its
corresponding class and we refer to it as geometric prototype
$p_{\text{geo}}^{c}\in\mathbb{R}^{H}$:

$p_{\text{geo}}^{c}=\frac{\sum_{i=1}^{N^{c}}\left[\hat{f}_{\text{geo}}\right]^{c,i}}{N^{c}},$
(3)

where $N^{c}$ denotes the number of points belonging to class $c$ in the
training dataset $D_{\text{train}}^{b}$ or $D_{\text{train}}^{n}$.
$\hat{f}_{\text{geo}}\in\mathbb{R}^{H}$ is the hard assignment in the form of
one-hot vector. We augment the semantic prototype $p_{\text{sem}}^{c}$ with
the geometric prototype $p_{\text{geo}}^{c}$, as the semantic prototype
primarily encodes semantic information and, as a result, becomes insufficient
in representing the new classes due to limited training samples.

#### Geometric-guided Classifier Re-weighting.

Based on the GP, we propose the geometric-guided classifier re-weighting
module to help the prediction of the novel classes. As shown in Fig. 3, the
corresponding geometric word for a point on the window frame is activated in
the GP of window and the geometrically similar class door, but suppressed in
beam which does not have the frame structure. This implies that comparing the
geometric feature of the query point with GP can be employed as a hint for
segmentation. Therefore, we compute a geometric matching score $s^{c}$ based
on the cosine similarity between a query point’s geometric feature and GP as:

$s^{c}=\mathds{1}\left[{p_{\text{geo}}^{c}\cdot\hat{f}_{\text{geo}}}\right]=\begin{cases}1&p_{\text{geo}}^{c}\cdot\hat{f}_{\text{geo}}>0\\\
0&\text{otherwise}\end{cases},$ (4)

where $\mathds{1}[\cdot]$ is an indicator fucntion, and $s^{c}=1$ indicates
the query point has the same geometric structure as class $c$. $c$ is the
class name.

Figure 4: Illustration of minor frequency pruning. The top left figure shows
the green points on the table are activated to the GW representing the
horizontal plane, while the red points on the vertical plane of the wall are
wrongly activated to the same GW due to scene context. The right figure shows
the proposed minor frequency pruning to suppress the activation to the wrong
GWs introduced by scene context.

However, the geometric matching may be negatively influenced by the noisy GWs
in the $p_{\text{geo}}^{c}$ due to the scene context. As shown in Fig. 4,
although points on the wall (in red) are on the vertical plane, they are still
activated to the same GW as the points on the horizontal table plane due to
adjacency. To suppress these noisy GWs in $p_{\text{geo}}^{c}$ and improve the
accuracy of geometric matching, we propose minor frequency pruning as shown in
Algorithm 1. Our motivation is that the GWs representing the typical geometric
structure of the class usually contributes a large frequency on the histogram,
while the GWs that are introduced by the scene context have relatively low
frequencies. Consequently, we remove GWs corresponding to lower frequencies to
only preserve the representative geometric structures. We denote the pruned
geometric prototype as $p_{\text{pgeo}}^{c}$. The frequency limit $\alpha$ in
Algorithm 1 denotes the amount of the frequencies to keep in the original
$p_{\text{geo}}^{c}$, and the $p_{\text{geo}}^{c,j}$ denotes the j-th entry of
$p_{\text{geo}}^{c}$. The computation of the matching score is then updated
as:

$s^{c}=\mathds{1}\left[{p_{\text{pgeo}}^{c}\cdot\hat{f}_{\text{geo}}}\right],$
(5)

To highlight the geometrically matched class in the prediction, we set a
weight $w^{c}$ to the prediction of each class according to the matching score
as follow:

$w^{c}:=\begin{cases}\beta&s^{c}=1\\\ 1&s^{c}=0\end{cases}.$ (6)

We set $\beta>1$ to highlight the potential target classes of the query point.
We then re-weight the semantic classification logit $l_{\text{sem}}^{c}$ with
$w^{c}$ to compute the final prediction logit $l_{\text{fin}}^{c}$ as follows:

$\displaystyle l_{\text{fin}}^{c}=w^{c}\times l_{\text{sem}}^{c},\qquad
l_{\text{sem}}^{c}=p_{\text{sem}}^{c}\cdot f_{\text{fin}}.$ (7)

The $l_{\text{fin}}^{c}$ considers both semantic and geometric similarity when
segmenting new classes, which is more reliable than using semantic prediction
logit $l_{\text{sem}}^{c}$ alone as shown in Tab. 4. Finally, we predict the
label $y$ for each query point as follow:

$y=\operatorname{argmax}\left(\operatorname{Softmax}\left(\left[l_{\text{fin}}^{1},...,l_{\text{fin}}^{\left|C_{\text{test}}\right|}\right];\tau\right)\right).$
(8)

Algorithm 1 Minor Frequency Pruning

1:Geometric prototype $p_{\text{geo}}^{c}$, frequency limit
$\alpha\in\left[0,1\right]$

2:Pruned geometric prototype $p_{\text{pgeo}}^{c}$

3:$\gamma\leftarrow 0$ $\triangleright$ $\gamma$ records the accumulated
frequencies and is initialized to 0

4:$p_{\text{pgeo}}^{c}\leftarrow\left[0,...,0\right]^{H}$ $\triangleright$
Initialize all entries of $p_{\text{pgeo}}^{c}$ to 0

5:$\left\\{\text{idx}_{1},...,\text{idx}_{H}\right\\}\leftarrow$
Sort_Descending $\left\\{p_{\text{geo}}^{c,j}\right\\}_{j=1}^{H}$
$\triangleright$ Get indices of
$\left\\{p_{\text{geo}}^{c,j}\right\\}_{j=1}^{H}$ in descending order

6:$\text{idx}_{i}\leftarrow\text{idx}_{1}$

7:while $\gamma<\alpha$ do

8: $p_{\text{pgeo}}^{c,\text{idx}_{i}}\leftarrow
p_{\text{geo}}^{c,\text{idx}_{i}}$

9: $\gamma\leftarrow\gamma+p_{\text{geo}}^{c,\text{idx}_{i}}$

10: $\text{idx}_{i}\leftarrow\text{idx}_{i+1}$

11:end while

12:$p_{\text{pgeo}}^{c}\leftarrow
p_{\text{pgeo}}^{c}/\text{Sum}\left(p_{\text{pgeo}}^{c}\right)$
$\triangleright$ Normalization

Method | 5-shot | 1-shot
---|---|---
|  mIoU-B |  mIoU-N |  mIoU-A |  HM |  mIoU-B |  mIoU-N |  mIoU-A |  HM
Fully Supervised |  76.51 |  58.69 |  68.29 |  66.42 |  76.51 |  58.69 |  68.29 |  66.42
attMPTI [35] |  34.90 |  16.08 |  26.21 |  21.99 |  21.89 |  11.39 |  17.05 |  14.95
PIFS [2] |  56.99 |  19.66 |  39.76 |  29.23 |  57.85 |  14.59 |  37.88 |  23.31
CAPL [25] |  73.56 |  35.18 |  55.85 |  47.51 |  72.80 |  23.87 |  50.22 |  35.67
Ours |  73.61 |  43.26 |  59.60 |  54.42 |  74.10 |  29.66 |  53.58 |  41.92

Table 2: Results on S3DIS under 5-shot and 1-shot settings.

Method | 5-shot | 1-shot
---|---|---
|  mIoU-B |  mIoU-N |  mIoU-A |  HM |  mIoU-B |  mIoU-N |  mIoU-A |  HM
Fully Supervised |  43.12 |  37.04 |  41.34 |  39.85 |  43.12 |  37.04 |  41.34 |  39.85
attMPTI [35] |  16.31 |  3.12 |  12.35 |  5.21 |  12.97 |  1.62 |  9.57 |  2.88
PIFS [2] |  35.14 |  3.21 |  25.56 |  5.88 |  35.80 |  2.54 |  25.82 |  4.75
CAPL [25] |  38.22 |  14.39 |  31.07 |  20.88 |  38.70 |  10.59 |  30.27 |  16.53
Ours |  40.18 |  18.58 |  33.70 |  25.39 |  40.06 |  14.78 |  32.47 |  21.55

Table 3: Results on ScanNet under 5-shot and 1-shot settings.

##  5 Experiments

###  5.1 Datasets and Setup

#### Datasets.

We evaluate on two datasets: 1) S3DIS [1] consists 272 point clouds from six
areas with annotation corresponding to 13 semantic classes. We use area 6 as
the testing dataset $D_{\text{test}}$, and leverage the other five areas to
construct the training dataset for base and novel classes. 2) ScanNet [4]
consists of 1,513 point clouds with annotation corresponding to 20 semantic
classes. We use 1,201 point clouds to construct training dataset of
$D_{\text{train}}^{b}$ and $D_{\text{train}}^{n}$ and the rest 312 point
clouds to construct $D_{\text{test}}$.

For both datasets, we choose the last 6 classes with least labeled points in
the corresponding dataset as the novel classes $C^{n}$ and the rest classes as
base classes $C^{b}$. The motivation is to simulate the scenario in real
world, where the frequency of novel class occurring is low and it is hard to
collect sufficient training data. Consequently, the novel classes for S3DIS
are table, window, column, beam, board and sofa. The novel classes for ScanNet
are sink, toilet, bathtub, shower curtain, picture and counter. We follow the
data pre-processing of [35] to divide each point cloud into blocks with size
of $1\ \text{meter}\times 1\ \text{meter}$ on the $xy$ plane. From each block,
we sample $m=2,048$ points as input. The dimension $d_{0}$ for the input
feature is 9 with XYZ, RGB and normalized XYZ to the block.

#### Evaluation Metrics.

We evaluate the performance of model using mean intersection-over-union
(mIoU). We use mIoU-B, mIoU-N and mIoU-A to denote the mIoU on the base
classes, novel classes, and all the classes, respectively. In addition, we use
harmonic mean of mIoU-B and mIoU-N to better describe the overall performance
on base and novel classes, _i.e_.,
$\text{HM}=\frac{2\times\text{mIoU-B}\times\text{mIoU-N}}{\text{mIoU-B}+\text{mIoU-N}}$.
In comparison to mIoU-A, HM is not biased towards the base classes [31].

###  5.2 Implementation details

We adopt the feature extractor of [35] as $E$ and pretrain it on the
$D_{\text{train}}^{b}$ for 100 epochs. We then perform K-means on the
collection of the base class features $\left\\{f_{\text{low}}\right\\}$. We
set $H$ as 200 for S3DIS and 180 for ScanNet, respectively. During base class
training, we perform geometric-aware semantic representation learning and
learn semantic prototypes for base classes $\left\\{p_{\text{sem}}^{c}\mid
c\in C^{b}\right\\}$. $d_{1}$ and $d_{2}$ are both 192 following attMPTI [35],
and $d_{3}$ is set to 128. We set batch size to 32 and train for 150 epochs.
We use Adam optimizer with initial learning rate of 0.01 and decayed by 0.5
every 50 epochs. We load the pretrained weight of the first three EdgeConv
layers and set their learning rate to be 0.001. We compute the geometric
prototypes for base classes $\left\\{p_{\text{pgeo}}^{c}\mid c\in
C^{b}\right\\}$ after training completes. During testing stage, we first
obtain the semantic prototypes $\left\\{p_{\text{sem}}^{c}\mid c\in
C^{n}\right\\}$ and geometric prototypes $\left\\{p_{\text{pgeo}}^{c}\mid c\in
C^{n}\right\\}$ for novel classes by averaging $f_{\text{fin}}$ and
$\hat{f}_{\text{geo}}$ (followed by minor frequency pruning) of the foreground
points in the support set, respectively. We then predict the class labels for
each query point via proposed GCR. $\alpha$ is set to 0.9 and 0.95 for S3DIS
and ScanNet, respectively. $\beta$ is set to 1.2.

###  5.3 Baselines

We design three baselines for comparison with our method. 1) attMPTI [35] is
the state-of-the-art FS-3DSeg method. We follow the original implementation in
[35] and episodically train attMPTI on base class dataset. Upon finishing
training, we collect multi-prototypes for base classes. During testing stage,
we first generate multi-prototypes for novel classes from
$D_{\text{train}}^{n}$. We then estimate the query label by performing label
propagation among query points and prototypes of base and novel classes. 2)
PIFS [2] is the state-of-the-art method for GFS-2DSeg that fine-tunes on
$D_{\text{train}}^{n}$ to learn novel classes. We apply their proposed
prototype-based distillation loss to only the scores of novel classes since we
do not provide the annotation of base classes in $D_{\text{train}}^{n}$. 3)
CAPL [25] is the state-of-the-art method in GFS-2DSeg that performs prototype
learning to learn novel classes. We remove the SCE module of CAPL since the
annotations of base classes in the $D_{\text{train}}^{n}$ are not available.
All the baselines use the same feature extractor with us for fair comparison.

In addition, we design an oracle setting, Fully Supervised, where the model is
trained on the fully annotated dataset of base and novel classes using the
same feature extractor with us and a small segmentation head.

Figure 5: Qualitative comparison on 5-shot setting of S3DIS dataset. Novel
classes are marked with red rectangle. The target novel classes in the first
row are board, table, column and window. The target novel classes in the
second row is beam.

###  5.4 Comparison with Baselines

Tab. 2 and Tab. 3 show the results of GFS-3DSeg on S3DIS and ScanNet,
respectively. We conduct experiments in two settings with the number of
support point clouds $K=\\{1,5\\}$ on each dataset. We randomly generate 5
sets of $D_{\text{train}}^{n}$ using different seeds for each setting and
calculate the averaged results over all 5 sets to obtain a more reliable
results. It is clear to see that the segmentation accuracy of novel classes
increases with more number of shots. Compared with all the baselines, our
method is able to utilize the limited number of training samples from
$D_{\text{train}}^{n}$ in a more effective way and achieves much better
performance in terms of the HM and mIoU-N.

attMPTI [35] fails to perform well on the GFS-3DSeg since it only focuses on
establishing the decision boundary for those classes appearing in each
episode. When including all the classes in the evaluation, the original
decision boundary collapses. PIFS [2] also performs poorly on the GFS-3DSeg.
The large intra-class variances of the 3D objects make novel class adaptation
difficult for the 2D fine-tuning method. Moreover, their fine-tuning method
leads to severe catastrophic forgetting of the base classes due to the absence
of base class training data. Our method is based on CAPL [25]. Compared to
CAPL which mainly utilizes the context information to enhance the semantic
prototypes of the base classes, we focus on enhancing the learning of the new
classes by leveraging transferable knowledge GWs. As a result, our method
shows great superiority over CAPL in the performance of the novel classes.
This can also be verified in Fig. 5, where our model is able to segment target
new classes (board and table in the first row, and beam in the second row)
more precisely.

GSR | GCR | mIoU-B | mIoU-N | mIoU-A | HM
---|---|---|---|---|---
✗ | ✗ | 73.56 | 35.18 | 55.85 | 47.51
✓ | ✗ | 73.48 | 40.10 | 58.07 | 51.81
✓ | ✓ | 73.61 | 43.26 | 59.60 | 54.42

Table 4: Effectiveness of geometric-aware semantic representation (GSR) and
geometric-guided classifier re-weighting (GCR) on S3DIS.

Number of GWs | mIoU-B | mIoU-N | mIoU-A | HM
---|---|---|---|---
$H=100$ | 72.45 | 43.61 | 59.14 | 54.38
$H=150$ | 73.88 | 42.27 | 59.29 | 53.71
$H=200$ | 73.61 | 43.26 | 59.60 | 54.42
$H=250$ | 72.96 | 41.29 | 58.32 | 52.63
$H=400$ | 73.19 | 40.84 | 58.26 | 52.36

Table 5: Ablation study of number of geometric words in S3DIS.

Frequency Limit | mIoU-B | mIoU-N | mIoU-A | HM
---|---|---|---|---
$\alpha=1$ | 73.50 | 41.05 | 58.50 | 52.59
$\alpha=0.95$ | 73.48 | 43.19 | 59.50 | 54.34
$\alpha=0.9$ | 73.61 | 43.26 | 59.60 | 54.42
$\alpha=0.85$ | 73.59 | 43.01 | 59.48 | 54.22

Table 6: Ablation Study of frequency limit $\alpha$. $\alpha=1$ denotes model
without minor frequency pruning in the GCR.

logits weight | mIoU-B | mIoU-N | mIoU-A | HM
---|---|---|---|---
$\beta=1$ | 73.48 | 40.10 | 58.07 | 51.81
$\beta=1.2$ | 73.61 | 43.26 | 59.60 | 54.42
$\beta=1.5$ | 73.20 | 42.25 | 58.90 | 53.51

Table 7: Ablation Study of logits weight $\beta$. $\beta=1$ is equivalent to
the model without using GCR.

Method | mIoU-B | mIoU-N | mIoU-A | HM
---|---|---|---|---
PTv2+CAPL | 86.35 | 27.58 | 59.22 | 41.68
PTv2+Ours | 86.38 | 37.26 | 63.71 | 52.01

Table 8: Comparison using state-of-the-art feature extractor Point Transformer
v2 (PTv2) [30].

Method | ceiling | floor | wall | beam | column | window | door | table | chair | sofa | bookcase | board | clutter
---|---|---|---|---|---|---|---|---|---|---|---|---|---
CAPL | 93.17 | 97.36 | 72.92 | 52.44 | 28.82 | 35.12 | 77.57 | 60.60 | 61.29 | 10.38 | 54.42 | 23.75 | 58.19
Ours | 92.34 | 97.16 | 70.73 | 60.37 | 32.16 | 46.30 | 76.21 | 64.41 | 63.42 | 16.99 | 54.77 | 39.30 | 60.66

Table 9: Per-class IoU. Red denotes new classes.

Method | mIoU-B | mIoU-N | mIoU-A | HM
---|---|---|---|---
CAPL | 0.17 | 3.25 | 1.46 | 2.94
Ours | 0.35 | 3.34 | 1.63 | 2.75

Table 10: Standard deviation.

###  5.5 Ablation Study

#### Effectiveness of GSR and GCR.

We verify the effectiveness of the geometric-aware semantic representation
(GSR) and geometric-guided classifier re-weighting (GCR) on 5-shot setting
using S3DIS (Tab. 4).The model without GSR uses $f_{\text{sem}}$ as the
feature representation for each point. The model without GCR adopts
$l_{\text{sem}}^{c}$ as the final prediction logit of class c. Both GSR and
GCR are beneficial to new class segmentation, which suggests the successful
enhancement of the representation and classifier of the novel classes by using
transferable geometric information.

#### Analysis of the number of GWs.

Tab. 5 studies the influence of GW numbers on the performance of 5-shot
setting using S3DIS. Although the performance varies with the different
numbers of geometric words, they all largely outperform the baselines without
GWs. We choose $H=200$ in our model regarding its best overall performance.

#### Effectiveness of the minor frequency pruning.

In Tab. 6, we analyze the effect of the minor frequency pruning in the
geometric prototype. GP without pruning ($\alpha=1$) shows worst performance
compared to the pruned GPs. $\alpha=0.9$ gives the best performance, thus we
adopt $\alpha=0.9$ in our final model.

#### Analysis of the weight $\beta$.

We present the ablation study of the weight $\beta$ in Tab. 7. $\beta=1$ does
not highlight any potential target classes predicted by geometric matching,
which is equivalent to the model without GCR. Setting a moderate threshold
$>1$ is helpful to improve the segmentation performance, so we choose
$\beta=1.2$ for model testing.

#### Using SOTA feature extractor.

Tab. 8 shows the result of replacing DGCNN-based feature extractor [35] with
Point Transformer v2 (PTv2) under the 5-shot setting of S3DIS. Our method
outperforms the strongest baseline CAPL by a large margin on novel classes and
overall performance. It verifies that our method can work successfully with a
state-of-the-art point cloud feature extractor. We notice that the mIoU-N in
Tab. 8 is lower than that of Tab. 2. One possible reason is that the feature
extractor in [35] is specially designed to be able to quickly learn new
classes from a small support set.

#### Standard deviation and per-class IoU.

Tab. 10 shows the standard deviation results on the 5 testing sets of the
5-shot setting of S3DIS. Our model shows similar variation with CAPL. Tab. 10
shows per-class IoU of the 5-shot setting of S3DIS. Our method largely
outperforms CAPL for all new classes while maintaining on-par performance on
base classes.

##  6 Conclusion

In this paper, we present the unexplored yet important generalized few-shot
point cloud segmentation. We address the challenge of facilitating new class
segmentation with limited training samples by utilizing transferable knowledge
geometric words (GWs) mined from the base classes. We propose geometric-aware
semantic representation to learn generalizable representation where geometric
features described through GWs are fused with semantic representation. We
further propose the geometric prototype (GP) to supplement the semantic
prototype in the testing stage. Extensive experiments on two benchmark
datasets demonstrate the superiority of our method.

#### Acknowledgement.

This research work is fully done at the National University of Singapore and
is supported by the Agency for Science, Technology and Research (A*STAR) under
its MTC Programmatic Funds (Grant No. M23L7b0021).

## Supplementary Material

##  Appendix A Experimental Results on 3-shot Setting

To further validate the effectiveness of our model, we compare our method with
the baselines under the 3-shot setting on S3DIS and ScanNet in Tab. A1 and
Tab. A2, respectively. The results consistently illustrate that our model
outperforms all baselines by a large margin on novel class segmentation, and
achieves the best overall performance.

Methods | mIoU-B | mIoU-N | mIoU-A | HM
---|---|---|---|---
Fully Supervised | 76.51 | 58.69 | 68.29 | 66.42
attMPTI [35] | 36.28 | 13.32 | 25.68 | 19.28
PIFS [2] | 54.34 | 20.00 | 38.53 | 29.23
CAPL [25] | 73.66 | 33.39 | 55.05 | 45.76
Ours | 73.55 | 41.55 | 58.78 | 53.04

Table A1: Results on S3DIS under 3-shot setting.

Methods | mIoU-B | mIoU-N | mIoU-A | HM
---|---|---|---|---
Fully Supervised | 43.12 | 37.04 | 41.34 | 39.85
attMPTI [35] | 16.78 | 2.42 | 12.47 | 4.24
PIFS [2] | 35.97 | 2.86 | 26.04 | 5.31
CAPL [25] | 38.32 | 13.65 | 30.92 | 20.05
Ours | 40.22 | 17.90 | 33.52 | 24.72

Table A2: Results on ScanNet under 3-shot setting.

##  Appendix B t-SNE Visualization

Fig. B1 displays the t-SNE visualization for S3DIS under the 5-shot setting.
The difference between the left and right figures is whether the geometric-
aware semantic representation (GSR) is employed. By using GSR, the
representation of novel classes are more discriminative.

Figure B1: t-SNE visualization on 5-shot setting of S3DIS. Small dots
represent point features and triangle represents weights for semantic
prototypes $P_{\text{ori}}$. Novel classes are indicated with the red
rectangle. Best viewed zoomed-in.

##  Appendix C Further Analysis on ScanNet

To comprehensively evaluate the performance of our framework on GFS-3DSeg, we
provide further analysis on ScanNet in this section.

###  C.1 Ablation Study

Tab. C3 shows the ablation study on ScanNet. Both geometric-aware semantic
representation (GSR) and geometric-guided re-weighting (GRW) are beneficial to
novel class generalization, and our full model with both GSR and GRW performs
the best regarding overall segmentation accuracy.

###  C.2 Qualitative Results

The qualitative results in Fig. C2 demonstrate that our model can segment
novel classes (Picture in the first row, Toilet and Sink in the second row)
more precisely than CAPL [25]. Concurrently, we can still maintain good
segmentation performance on base classes.

GSR | GRW | mIoU-B | mIoU-N | mIoU-A | HM
---|---|---|---|---|---
✗ | ✗ | 38.22 | 14.39 | 31.07 | 20.88
✓ | ✗ | 40.21 | 17.54 | 33.40 | 24.39
✓ | ✓ | 40.18 | 18.58 | 33.70 | 25.39

Table C3: Effectiveness of geometric-aware semantic representation (GSR) and
geometric-guided re-weighting (GRW) on ScanNet.

###  C.3 Visualization of Geometric Words

Fig. C3 visualizes the geometric words (GWs) on ScanNet. Each row shows two
activated point clouds regarding to the same geometric word in different
scenes. In the first row, the edge of the sofa, table, bathtub and toilet are
all activated when provided with the same GW. In the second row, the stick of
chair and table are activated. It suggests that the GWs are able to represent
shared geometric components across different scenes and different classes.
Interestingly, we also find that GWs are height-aware. The activated parts in
the third and fourth rows regarding two GWs represent vertical planes of
different heights.

Figure C2: Qualitative comparison on 5-shot setting of ScanNet. Target novel
classes are marked with red rectangles. The target novel class in the first
row is picture. The target novel classes in the second row are toilet and
sink. Figure C3: Visualization of geometric words on ScanNet. Each row shows
the activated point cloud regarding the same geometric word in two different
scenes. The activated points are colored green.

## References

  * [1] Iro Armeni, Ozan Sener, Amir R Zamir, Helen Jiang, Ioannis Brilakis, Martin Fischer, and Silvio Savarese.  3d semantic parsing of large-scale indoor spaces.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1534–1543, 2016.
  * [2] Fabio Cermelli, Massimiliano Mancini, Yongqin Xian, Zeynep Akata, and Barbara Caputo.  Prototype-based incremental few-shot semantic segmentation.  arXiv preprint arXiv:2012.01415, 2020.
  * [3] Townim Chowdhury, Ali Cheraghian, Sameera Ramasinghe, Sahar Ahmadi, Morteza Saberi, and Shafin Rahman.  Few-shot class-incremental learning for 3d point cloud objects.  In Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XX, pages 204–220. Springer, 2022.
  * [4] 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.
  * [5] Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In International conference on machine learning, pages 1126–1135. PMLR, 2017.
  * [6] Spyros Gidaris and Nikos Komodakis.  Dynamic few-shot visual learning without forgetting.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4367–4375, 2018.
  * [7] Bharath Hariharan and Ross Girshick.  Low-shot visual recognition by shrinking and hallucinating features.  In Proceedings of the IEEE international conference on computer vision, pages 3018–3027, 2017.
  * [8] Lvlong Lai, Jian Chen, Chi Zhang, Zehong Zhang, Guosheng Lin, and Qingyao Wu.  Tackling background ambiguities in multi-class few-shot point cloud semantic segmentation.  Knowledge-Based Systems, 253:109508, 2022.
  * [9] Xin Lai, Jianhui Liu, Li Jiang, Liwei Wang, Hengshuang Zhao, Shu Liu, Xiaojuan Qi, and Jiaya Jia.  Stratified transformer for 3d point cloud segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8500–8509, 2022.
  * [10] Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto.  Meta-learning with differentiable convex optimization.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10657–10665, 2019.
  * [11] Yangyan Li, Rui Bu, Mingchao Sun, Wei Wu, Xinhan Di, and Baoquan Chen.  Pointcnn: Convolution on x-transformed points.  Advances in neural information processing systems, 31, 2018.
  * [12] Yongfei Liu, Xiangyi Zhang, Songyang Zhang, and Xuming He.  Part-aware prototype network for few-shot semantic segmentation.  In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part IX 16, pages 142–158. Springer, 2020.
  * [13] Puneet Mangla, Nupur Kumari, Abhishek Sinha, Mayank Singh, Balaji Krishnamurthy, and Vineeth N Balasubramanian.  Charting the right manifold: Manifold mixup for few-shot learning.  In Proceedings of the IEEE/CVF winter conference on applications of computer vision, pages 2218–2227, 2020.
  * [14] Yongqiang Mao, Zonghao Guo, Xiaonan Lu, Zhiqiang Yuan, and Haowen Guo.  Bidirectional feature globalization for few-shot semantic segmentation of 3d point cloud scenes.  arXiv preprint arXiv:2208.06671, 2022.
  * [15] Tsendsuren Munkhdalai and Hong Yu.  Meta networks.  In International conference on machine learning, pages 2554–2563. PMLR, 2017.
  * [16] Alex Nichol, Joshua Achiam, and John Schulman.  On first-order meta-learning algorithms.  arXiv preprint arXiv:1803.02999, 2018.
  * [17] David Nister and Henrik Stewenius.  Scalable recognition with a vocabulary tree.  In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06), volume 2, pages 2161–2168. Ieee, 2006.
  * [18] Boris Oreshkin, Pau Rodríguez López, and Alexandre Lacoste.  Tadam: Task dependent adaptive metric for improved few-shot learning.  Advances in neural information processing systems, 31, 2018.
  * [19] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 652–660, 2017.
  * [20] Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas.  Pointnet++: Deep hierarchical feature learning on point sets in a metric space.  Advances in neural information processing systems, 30, 2017.
  * [21] Hang Qi, Matthew Brown, and David G Lowe.  Low-shot learning with imprinted weights.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5822–5830, 2018.
  * [22] Amirreza Shaban, Shray Bansal, Zhen Liu, Irfan Essa, and Byron Boots.  One-shot learning for semantic segmentation.  arXiv preprint arXiv:1709.03410, 2017.
  * [23] Jake Snell, Kevin Swersky, and Richard Zemel.  Prototypical networks for few-shot learning.  Advances in neural information processing systems, 30, 2017.
  * [24] Yonglong Tian, Yue Wang, Dilip Krishnan, Joshua B Tenenbaum, and Phillip Isola.  Rethinking few-shot image classification: a good embedding is all you need?  In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XIV 16, pages 266–282. Springer, 2020.
  * [25] Zhuotao Tian, Xin Lai, Li Jiang, Shu Liu, Michelle Shu, Hengshuang Zhao, and Jiaya Jia.  Generalized few-shot semantic segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11563–11572, 2022.
  * [26] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al.  Matching networks for one shot learning.  Advances in neural information processing systems, 29, 2016.
  * [27] Kaixin Wang, Jun Hao Liew, Yingtian Zou, Daquan Zhou, and Jiashi Feng.  Panet: Few-shot image semantic segmentation with prototype alignment.  In proceedings of the IEEE/CVF international conference on computer vision, pages 9197–9206, 2019.
  * [28] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon.  Dynamic graph cnn for learning on point clouds.  Acm Transactions On Graphics (tog), 38(5):1–12, 2019.
  * [29] Ziyi Wang, Yongming Rao, Xumin Yu, Jie Zhou, and Jiwen Lu.  Semaffinet: Semantic-affine transformation for point cloud segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11819–11829, 2022.
  * [30] Xiaoyang Wu, Yixing Lao, Li Jiang, Xihui Liu, and Hengshuang Zhao.  Point transformer v2: Grouped vector attention and partition-based pooling.  Advances in Neural Information Processing Systems, 35:33330–33342, 2022.
  * [31] Han-Jia Ye, Hexiang Hu, and De-Chuan Zhan.  Learning adaptive classifiers synthesis for generalized few-shot learning.  International Journal of Computer Vision, 129:1930–1953, 2021.
  * [32] Han-Jia Ye, Hexiang Hu, De-Chuan Zhan, and Fei Sha.  Few-shot learning via embedding adaptation with set-to-set functions.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 8808–8817, 2020.
  * [33] Chi Zhang, Guosheng Lin, Fayao Liu, Jiushuang Guo, Qingyao Wu, and Rui Yao.  Pyramid graph networks with connection attentions for region-based one-shot semantic segmentation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9587–9595, 2019.
  * [34] Chi Zhang, Guosheng Lin, Fayao Liu, Rui Yao, and Chunhua Shen.  Canet: Class-agnostic segmentation networks with iterative refinement and attentive few-shot learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5217–5226, 2019.
  * [35] Na Zhao, Tat-Seng Chua, and Gim Hee Lee.  Few-shot 3d point cloud semantic segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8873–8882, 2021.
  * [36] Shizhen Zhao and Xiaojuan Qi.  Prototypical votenet for few-shot 3d point cloud object detection.  arXiv preprint arXiv:2210.05593, 2022.


# Degenerate Local-dimension-invariant Stabilizer Codes and an Alternative
Bound for the Distance Preservation Condition

Lane G. Gunderman<EMAIL_ADDRESS>The Institute for Quantum
Computing, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada
Department of Physics and Astronomy, University of Waterloo, Waterloo,
Ontario, N2L 3G1, Canada

(August 27, 2024)

###### Abstract

One hurdle to performing reliable quantum computations is overcoming noise.
One possibility is to reduce the number of particles needing to be protected
from noise and instead use systems with more states, so called qudit quantum
computers. In this paper we show that codes for these systems can be derived
from already known codes, and in particular that degenerate stabilizer codes
can have their distance also promised upon sufficiently large local-dimension,
as well as a new bound on the local-dimension required to preserve the
distance of local-dimension-invariant codes, which is a result which could
prove to be useful for error-corrected qudit quantum computers.

††preprint: APS/123-QED

Having protected quantum information is an essential piece of being able to
perform quantum computations. There are a variety of methods to help protect
quantum information such as those discussed in [1]. In this work we focus on
stabilizer codes as they are the quantum analog of classical linear codes.
Even with error-correcting codes, having sufficient amounts of protected
quantum information to perform useful tasks is still an unresolved challenge.
A way to retain a similarly sized computational space while reducing the
number of particles that need precise controls is to replace the standard
choice of qubits with qudits, quantum particles with $q$ levels, also known as
local-dimension $q$ [2]. Throughout this work we require $q$ to be a prime so
that each nonzero element has a unique multiplicative inverse over
$\mathbb{Z}_{q}$. This restriction can likely be removed, but for simplicity
and clarity we only consider this case. Experimental realizations of qudit
systems are currently underway [3, 4, 5, 6], so having more error-correcting
codes will aid in protecting such systems.

Prior work on qudit error-correcting codes have at times had challenging
restrictions between the parameters of the code [7, 8, 9], and we’ve already
made progress on reducing this barrier in a prior paper [10]. Our prior work
showed the ability to make error-correcting codes that preserved their
parameters even upon changing the local-dimension of the system, provided the
local-dimension is sufficiently large. Unfortunately the ability to promise
the distance of the codes was only shown for non-degenerate codes and with a
large local-dimension value required. Beyond this, qudits also have proven
connections to foundational aspects of physics [11]. Seeing these potential
reasons for using qudits, this work builds off of our prior work to expand the
local-dimension-invariant work to the case of degenerate codes as well as
providing a roughly quadratic improvement in the size of the local-dimension
needed to still promise the distance of the code. With these results the
practicality of using this method is improved as well as now providing the
option of applying the result to the essential class of degenerate codes, such
as quantum versions of low-density parity-check (LDPC) codes.

##  I Definitions for Qudit Stabilizer Codes

In this section we review some key facts about qudit stabilizer codes. For a
more complete guide on qudit stabilizer codes, we recommend [7]. The
definitions laid out here will be used throughout this work. Let $q$ be the
local-dimension of a system, where $q$ is a prime number. We will denote by
$\mathbb{Z}_{q}$ the set $\\{0,1,\ldots q-1\\}$. When $q=2$ we refer to each
register as a qubit, while for any value of $q$ we call each register a qudit.
In order to speak more generally and not specify $q$, we will often times
refer to each register as a particle instead. We now begin to define the
operations for these registers.

######  Definition 1.

Generalized Paulis for a particle over $q$ orthogonal levels (local-dimension
$q$) are given by:

$X_{q}|j\rangle=|(j+1)\mod q\rangle,\quad Z_{q}|j\rangle=\omega^{j}|j\rangle$
(1)

with $\omega=e^{2\pi i/q}$, where $j\in\mathbb{Z}_{q}$. These Paulis form a
group, denoted $\mathbb{P}_{q}$.

When $q=2$, these are the standard qubit operators $X$ and $Z$, with $Y=iXZ$.
This group structure is preserved over tensor products since each of these
Paulis has order $q$. A generalized Pauli over $n$ registers is a tensor
product of $n$ generalized Pauli group members over a single register.

A commuting subgroup of generalized Pauli operators with $n-k$ generators, but
not including any nontrivial coefficient for the identity operator, is
equivalent to a stabilizer code. The number of orthogonal eigenvectors, which
form bases called codewords, for these $n-k$ generators is $q^{k}$. In effect,
we have constructed $k$ logical particles from the $n$ physical particles. If
we are to use these subgroups for error-correction purposes then they ought to
be able to have some accidental operator occur and still have the codewords be
discernible. We will work under the assumption that errors on distinct
particles are independent and we will assume the error model on each qudit is
the depolarizing channel.Given this error model we will predominantly be
interested in the number of non-identity terms in any error as the exponent of
the error term increases with this.

######  Definition 2.

The weight of an $n$-qudit Pauli operator is the number of non-identity
operators in it.

######  Definition 3.

A stabilizer code, specified by its $n-k$ generators, is characterized by the
following set of parameters:

  * •

$n$: the number of (physical) particles that are used to protect the
information.

  * •

$k$: the number of encoded (logical) particles.

  * •

$d$: the distance of the code, given by the lowest weight of an undetectable
generalized Pauli error. An undetectable generalized Pauli error is an
$n$-qudit Pauli operator which commutes with all elements of the stabilizer
group, but is not in the group itself.

These values are specified for a particular code as $[[n,k,d]]_{q}$, where $q$
is the local-dimension of the qudits.

We pause for a moment here to discuss how degenerate codes differ from non-
degenerate codes. Degenerate codes are different in the following equivalent
ways. Firstly, they may have multiple errors with the same syndrome value and
that map to different physical states, but upon recovery still map back to the
same logical state. Secondly, degenerate codes may have generators, aside from
the identity operator, which have lower weight than the distance of the code.
These two differences make degenerate codes markedly different from their non-
degenerate counterpart. Degenerate codes, while having these extra nuances,
are a crucial class of stabilizer codes as any quantum analog of a low-density
parity-check (LDPC) code with high distance will need to be a degenerate code.
We will begin our new results by focusing on non-degenerate codes, then move
to the degenerate case in Theorem 15, however, there are more tools needed
before discussing the new results.

Working with tensors of operators can be challenging, and so we make use of
the following well-known mapping from these to vectors, following the notation
from [10]. This representation is often times called the symplectic
representation for the operators, but we use this notation instead to allow
for greater flexibility, particularly in specifying the local-dimension of the
mapping. This linear algebraic representation will be used for our proofs.

######  Definition 4 ($\phi$ representation of a qudit operator).

We define the linear surjective map:

$\phi_{q}:\mathbb{P}_{q}^{n}\mapsto\mathbb{Z}_{q}^{2n}$ (2)

which carries an $n$-qudit Pauli in $\mathbb{P}_{q}^{n}$ to a $2n$ vector mod
$q$, where we define this mapping by:

$I^{\otimes i-1}X_{q}^{a}Z_{q}^{b}I^{\otimes n-i}\mapsto\left(0^{i-1}\ a\
0^{n-i}\middle|0^{i-1}\ b\ 0^{n-i}\right),$ (3)

which puts the power of the $i$-th $X$ operator in the $i$-th position and the
power of the $i$-th $Z$ operator in the $(n+i)$-th position of the output
vector. This mapping is defined as a homomorphism with: $\phi_{q}(s_{1}\circ
s_{2})=\phi_{q}(s_{1})\oplus\phi_{q}(s_{2})$, where $\oplus$ is component-wise
addition mod $q$. We denote the first half of the vector as $\phi_{q,x}$ and
the second half as $\phi_{q,z}$.

We may invert the map to return to the original $n$-qudit Pauli operator with
the global phase being undetermined. We make note of a special case of the
$\phi$ representation:

######  Definition 5.

Let $q$ be the dimension of the initial system. Then we denote by
$\phi_{\infty}$ the mapping:

$\phi_{\infty}:\mathbb{P}_{q}^{n}\mapsto\mathbb{Z}^{2n}$ (4)

where no longer are any operations taken $\mod$ some base, but instead carried
over the full set of integers.

The ability to define $\phi_{\infty}$ as a homomorphism still (and with the
same rule) is a portion of the results of [10]. $\phi_{q}$ is the standard
choice for working over $q$ bases, however, our $\phi_{\infty}$ allows us to
avoid being dependent on the local-dimension of our system when working with
our code. Formally we will write a code in $\phi_{q}$, perform some
operations, then write it in $\phi_{\infty}$, then select a new local-
dimension $q^{\prime}$ and use $\phi_{q^{\prime}}$. We shorten this to write
it as $\phi_{\infty}$, and can later select to write it as $\phi_{q^{\prime}}$
for some prime $q^{\prime}$ by taking element-wise $\mod q^{\prime}$.

The commutator of two operators in this picture is given by the following
definition:

######  Definition 6.

Let $s_{i},s_{j}$ be two qudit Pauli operators over $q$ bases, then these
commute if and only if:

$\phi_{q}(s_{i})\odot\phi_{q}(s_{j})=0\mod q$ (5)

where $\odot$ is the symplectic product, defined by:

$\phi_{q}(s_{i})\odot\phi_{q}(s_{j})\\\
=\oplus_{k}[\phi_{q,z}(s_{j})_{k}\cdot\phi_{q,x}(s_{i})_{k}-\phi_{q,x}(s_{j})_{k}\cdot\phi_{q,z}(s_{i})_{k}]$
(6)

where $\cdot$ is standard integer multiplication $\mod q$ and $\oplus$ is
addition $\mod q$.

When the commutator of $s_{i}$ and $s_{j}$ is not zero, this provides the
difference in the number of $X$ operators in $s_{i}$ that must pass a $Z$
operator in $s_{j}$ and the number of $Z$ operators in $s_{i}$ that must pass
an $X$ operator in $s_{j}$ when attempting to switch the order of these two
operators.

Before finishing, we make a brief list of some possible operations we can
perform on our $\phi$ representation:

  1. 1.

We may perform elementary row operations over $\mathbb{Z}_{q}$, corresponding
to relabelling and composing generators together.

  2. 2.

We may swap registers (qudits) in the following ways:

    1. (a)

We may swap columns $(i,i+n)$ and $(j,j+n)$ for $1\leq i,j\leq n$,
corresponding to relabelling qudits.

    2. (b)

We may swap columns $i$ and $(-1)\cdot(i+n)$, for $1\leq i\leq n$,
corresponding to conjugating by a Hadamard gate on particle $i$ (or Discrete
Fourier Transforms in the qudit case [12]) thus swapping $X$ and $Z$’s roles
on that qudit.

All of these operations leave the code parameters $n$, $k$, and $d$ alone, but
can be used in proofs.

###  I.1 Local-dimension-invariant Codes

In this section we recall the results relating to local-dimension-invariant
(LDI) stabilizer codes. These codes answer the question of when we can apply a
code from one local-dimension $q$ on a system with a different local-dimension
$p$. While an unusual property, a LDI code would permit the importing of
smaller local-dimension codes for larger local-dimension systems. Some codes
with particular parameters may not be known and so this fills in some of these
gaps. Additionally, this framework could potentially provide insights into
local-dimension-invariant measurements. Few examples of LDI codes, although
not by this name, were known, notable the 5 particle code [13] and the 9
particle code [14], until the recent work in [10] which showed that all codes
can satisfy the commutation requirements, and at least for sufficiently large
local-dimension the distance can also be at least preserved. We will review
next the primary results from that work.

######  Definition 7.

A stabilizer code $S$ is called local-dimension-invariant (LDI) iff:

$\phi_{\infty}(s_{i})\odot\phi_{\infty}(s_{j})=0,\quad\forall s_{i},s_{j}\in
S.$ (7)

As an example, consider the two qubit code generated by $\langle X\otimes
X,Z\otimes Z\rangle$. The symplectic product between the two generators is
$2$, so it makes it a valid qubit code, however, $2\mod p\neq 0$ unless $p=2$,
so it is not a valid qudit code for $p\neq 2$. If we instead transform the
code into one generated by $\langle X\otimes X^{-1},Z\otimes Z\rangle$, then
the symplectic product is now $0$, and so it can be used as generators for any
choice of local-dimension, and so is an LDI code. The next statement explains
that it is always possible to do so:

######  Theorem 8.

All stabilizer codes, $S$, can be put into an LDI form. One such method is to
put $S$ into canonical form $[I_{k}\ X_{2}\ |\ Z_{1}\ Z_{2}]$ then transform
the code into $[I_{k}\ X_{2}\ |\ Z_{1}+L\ \ Z_{2}]$, with
$L_{ij}=\phi_{\infty}(s_{i})\odot\phi_{\infty}(s_{j})$ when $i>j$ and $0$
otherwise.

Note that this does not say all codes have a unique LDI form, just that there
exists one. The proof used is useful as it gives a prescriptive method for
turning a code into an LDI form, however, if one does not put the code into
canonical form, the code can still be transformed into an LDI form as this
process is equivalent to finding solutions to an integer linear program with
an abundance of variables.

As of this point we have merely generated a set of commuting operators that
are local-dimension independent. This does not provide for any claims on the
distance of the code produced through this method aside from promising that
the procedure does not change the distance of the code over the initial local-
dimension $q$. For this, we have the following Theorem:

######  Theorem 9.

For all primes $p>p^{*}$, with $p^{*}$ a cutoff value greater than $q$, the
distance of an LDI form of a non-degenerate stabilizer code $[[n,k,d]]_{q}$
into $p$ bases, $[[n,k,d^{\prime}]]_{p}$, has $d^{\prime}\geq d$.

There are two caveats to this result, one of which we resolve here, the other
of which we provide an improvement on. Let $B$ be the maximal entry in
$\phi_{\infty}(S)$. Firstly, this result is only for the case of non-
degenerate codes. We will resolve this with Theorem 15. Secondly, the
initially proven bound was $p^{*}=B^{2(d-1)}(2(d-1))^{(d-1)}$, which grows
very rapidly. While it was true that all primes below $p^{*}$ could have their
distances checked computationally, this still left a large number of primes to
check in most cases. In this work we manage to prove an alternative bound that
has a nearly quadratic improvement on the dependency on $B$, as well as a
cutoff bound $p_{D}^{*}$ in the degenerate case. In the next section we show
this alternative cutoff bound, while in the section thereafter the ability to
provide a distance promise for degenerate codes is proven.

##  II Alternative Cutoff Bound for the Distance Promise

While the proof of Theorem 8 from [10] used
$L_{ij}=\phi_{\infty}(s_{i})\odot\phi_{\infty}(s_{j})$ in order to generate a
single LDI form, we may generate other LDI forms by altering the added $L$
matrix. We note two of these now: $L^{(+)}$ and $L^{(-)}$.

######  Definition 10.

$L^{(+)}$ ($L^{(-)}$) has $L_{ij}^{(+)}$ ($L_{ij}^{(-)}$) is
$\phi_{\infty}(s_{i})\odot\phi_{\infty}(s_{j})$ if the symplectic product is
greater than zero (less than zero).

These alternative $L$ matrices each provide a different property. Firstly,
using $L^{(+)}$ allows $\phi_{\infty}(S)$ to have only non-negative entries.
There are certain properties that are only generally true for matrices with
non-negative entries, so this can perhaps be of use. Additionally, this could
be of use for systems formally with countably infinite local-dimension, such
as Bosonic systems. Secondly, $L^{(-)}$ permits a slight reduction in the
bound for the maximal entry in $\phi_{\infty}(S)$, as the following Lemma
shows:

######  Lemma 11.

The maximal entry in $\phi_{\infty}(S)$, $B$, can be at most
$(1+k(q-1))(q-1)$, and generally
$B\leq\max_{i,j}|\phi_{\infty}(s_{i})\odot\phi_{\infty}(s_{j})|$.

Upon putting the code into canonical form this follows immediately from the
definition of $L^{(-)}$ as each entry will be whatever value was already in
that location (values in $\mathbb{Z}_{q}$) minus the absolute value of the
inner product, which will be at most an absolute value of the inner product.
While this is a small improvement on the value of $B$, since it’s the base of
an exponential expression this amounts to a larger improvement in the overall
cutoff value.

We will now move to proving an alternative bound on the local-dimension needed
in order to promise the distance is at least preserved. The first proof of the
cutoff bound for the distance promise for LDI codes used random permutations
of the entries in $\phi_{\infty}$. Here we utilize the structure of the
symplectic product as well as that of the partitions of the code in terms of
its $X$ component and $Z$ component to obtain an alternative bound for all
non-degenerate codes. While this bound is looser when $d$ increases, for small
$d$ and large $k$ this bound will typically be roughly quadraticly smaller. In
particular we will show:

######  Theorem 12.

For all primes $p>p^{*}$ the distance of an LDI representation of a non-
degenerate stabilizer code $[[n,k,d]]_{q}$ over $p$ bases,
$[[n,k,d^{\prime}]]_{p}$, has $d^{\prime}\geq d$, where we may use as $p^{*}$
the value:

$(B(q-1)(d-1)(1+(d-1)^{2}(q-1)^{d-1}(d-2)^{(d-2)/2}))^{d-1},$ (8)

with $q$ the initial local-dimension, $d$ the distance of the initial code,
and $B$ the maximal entry in the $\phi_{\infty}$ representation of the code.

To make claims about the distance of the code we begin by breaking down the
set of undetectable errors into two sets. These definitions highlight the
subtle possibility of the distance reducing upon changing the local-dimension.

######  Definition 13.

An unavoidable error is an error that commutes with all stabilizers and
produces the $\vec{0}$ syndrome over the integers.

These correspond to undetectable errors that would remain undetectable
regardless of the number of bases for the code since they always exactly
commute under the symplectic inner product with all stabilizer generators–and
so all members of the stabilizer group. Since these errors are always
undetectable we call them unavoidable errors since changing the number of
bases would not allow this code to detect this error.

We also define the other possible kind of undetectable error for a given
number of bases, which corresponds to the case where some syndromes are
multiples of the number of bases:

######  Definition 14.

An artifact error is an error that commutes with all stabilizers but produces
at least one syndrome that is only zero modulo the base.

These are named artifact errors as their undetectability is an artifact of the
number of bases selected and could become detectable if a different number of
bases were used with this code. Each undetectable error is either an
unavoidable error or an artifact error. We utilize this fact to show our
theorem.

###### Proof.

Let us begin with a code with local-dimension $q$ and apply it to a system
with local-dimension $p$. The errors for the original code are the vectors in
the kernel of $\phi_{q}$ for the code. These errors are either unavoidable
errors or are artifact errors. The stabilizers that generate these multiples
of $q$ entries in the syndrome are members of the null space of the minor
formed using the corresponding stabilizers.

Now, consider the extension of the code to $p$ bases. Building up the qudit
Pauli operators by weight $j$, we consider the minors of the matrix. These
minors of size $2j\times 2j$ can have a nontrivial null space in two possible
ways:

  * •

If the determinant is 0 over the integers then this is either an unavoidable
error or an error whose existence did not occur due to the choice of the
number of bases.

  * •

If the determinant is not 0 over the integers, but takes the value of some
multiple of $p$, then it’s $0\mod p$ and so a null space exists.

Thus we can only introduce artifact errors to decrease the distance. By
bounding the determinant by $p^{*}$, any choice of $p>p^{*}$ will ensure that
the determinant is a unit in $\mathbb{Z}_{p}$, and hence have a trivial null
space since the matrix is invertible.

We next utilize the structure of the symplectic product more heavily in order
to reduce the cutoff local-dimension. Note that for a pair of Paulis in the
$\phi$ representation, we may write:

$\displaystyle\phi(s_{1})\odot\phi(s_{2})$ $\displaystyle=$
$\displaystyle\phi(s_{1})\begin{bmatrix}0&-I_{n}\\\
I_{n}&0\end{bmatrix}\phi(s_{2})^{T}$ (9) $\displaystyle:=$
$\displaystyle\phi(s_{1})g\phi(s_{2})^{T}$ (10)

and so we may consider the commutation for the generators with some Pauli $u$
as being given by $\bigoplus_{i=1}^{n-k}(\phi(s_{i})g)\phi(u)^{T}$. This
removes the distinction between the two components and allows the symplectic
product to act like the normal matrix-vector product. Now, notice that for any
Pauli weight $j$ operator, we will have up to $j$ nonzero entries in the $X$
component of the $\phi$ representation and up to $j$ nonzero entries in the
$Z$ component. This means that up to $j$ columns in each component will be
involved in any commutator.

Next note that to ensure that an artifact error is not induced it suffices to
ensure that there is a nontrivial kernel, induced by the local-dimension
choice, which is ensured so long as any $2(d-1)\times 2(d-1)$ minor does not
have a determinant which is congruent to the local-dimension. This can be
promised by requiring the local-dimension to be larger than the largest
possible determinant for such a matrix. Since there will be at most $j$
nonzero entries in each component it suffices to consider $j$ columns from
each component and subsets of $2j$ rows of this.

From this reduction, we need only ensure that the local-dimension is larger
than the largest possible determinant for this $2j\times 2j$ minor. Let us
denote this minor by:

$\begin{bmatrix}X_{1}&Z_{1}\\\ X_{2}&Z_{2}\end{bmatrix},$ (11)

where each block has dimensions $j\times j$. The maximal entries are $q-1$ for
$X_{1}$ and $X_{2}$, whereas for $Z_{1}$ and $Z_{2}$ it is bounded by $B$. We
now use the block matrix identity:

$det\begin{bmatrix}X_{1}&Z_{1}\\\
X_{2}&Z_{2}\end{bmatrix}=det(X_{1})det(Z_{2}-X_{2}X_{1}^{-1}Z_{1}).$ (12)

Since all entries in $X_{1}$ are integers and the determinant is, by
construction, nonzero, the maximal entry in $X_{1}^{-1}$ will be at most that
of the largest cofactor of $X_{1}$. The largest cofactor, $\tilde{C}$, will be
at most $(q-1)^{d-2}(d-2)^{(d-2)/2}$, as provided by Hadamard’s inequality.
The largest entry in $Z_{2}-X_{2}X_{1}^{-1}Z_{1}$ is then upper bounded by
$B(1+(q-1)\tilde{C}(d-1)^{2})$. From here, we may apply Hadamard’s inequality
for determinants again using the given entry bounds, using that each block has
dimensions up to $(d-1)\times(d-1)$, which provides
$p^{*}=(q-1)^{d-1}(d-1)^{d-1}(B(1+(q-1)\tilde{C}(d-1)^{2}))^{d-1}$, or
alternatively expressed in terms of our fundamental variables as

$(B(q-1)(d-1)(1+(d-1)^{2}(q-1)^{d-1}(d-2)^{(d-2)/2}))^{d-1}.$ (13)

In the case of $q=2$ this reduces to
$(B(d-1)(1+(d-1)^{2}(d-2)^{(d-2)/2}))^{d-1}$.

Lastly, when $j=d$, we can either encounter an unavoidable error, in which
case the distance of the code is $d$ or we could obtain an artifact error,
also causing the distance to be $d$. It is possible that neither of these
occur at $j=d$, in which case the distance becomes some $d^{\prime}$ with
$d<d^{\prime}\leq d^{*}$, with $d^{*}$ being the distance of the code over the
integers. ∎

Before concluding this section, we provide a brief comparison of this bound to
the original one of $B^{2(d-1)}(2(d-1))^{(d-1)}$. The new bound only depends
on $B^{d-1}$ opposed to the original $B^{2(d-1)}$, which as the bound on $B$
depends on $k$ means that for codes, or code families, with larger $k$ values
the new bound can provide a tighter expression. Unfortunately, however, this
new bound is doubly-exponential in the distance of the code $d$, having a
dependency of roughly $d^{d^{2}}$ opposed to the prior dependency of $d^{d}$,
so if one is attempting to promise the distance of a code with a larger
distance, this new bound is likely to be far less tight. In summary, this
alternative bound is not per se better, however, since one may simply use
whichever of the bounds is tighter this alternative bound may provide a lower
requirement for the local-dimension needed in order to ensure that the
distance of the code is at least preserved.

##  III Degenerate Codes

Degenerate codes are a uniquely quantum phenomenon, however, are a crucial
class of quantum error-correcting codes. For a degenerate quantum error-
correcting code we must avoid undetectable errors, but also detectable errors
which produce the same syndrome but do not map to the same logical codeword.
Any LDPC-like quantum error-correcting code will be degenerate, as,
equivalently, a quantum error-correcting code is degenerate if there is some
stabilizer group member with lower weight than the distance of the code and by
construction one would aim to have a high distance but still $O(1)$ weight for
each generator. We show now that a similar distance promise may be made in the
degenerate case as was possible in the non-degenerate case.

######  Theorem 15.

The distance promise can also be made for degenerate codes.

###### Proof.

For the undetectable error case, this follows the same reasoning as the non-
degenerate case of this theorem, so we only need to worry about two errors
with the same syndrome mapping to different logical states.

Let $u$ and $v$ be two Paulis not in $S$ with weight at most $d-1$. We will
prove that upon achieving local-dimension values at least as large as
$p_{D}^{*}$, a cutoff value, it is impossible to introduce any new degenerate
errors. Next, let $\phi_{\infty}(S)|_{u}$ and $\phi_{\infty}(S)|_{v}$ be the
columns in the $\phi_{\infty}$ representation of the code that are used in
determining the syndromes for $u$ and $v$, respectively. Further let
$\phi_{\infty}(S)|_{u\cup v}$ be the union of the columns from
$\phi_{\infty}(S)|_{u}$ and $\phi_{\infty}(S)|_{v}$. This will be up to
$4(d-1)$ columns, all of which are not scalar multiples of any other column–so
long as $d\geq 3$. If $\phi(u)$ and $\phi(v)$ have the same syndromes then it
must be the case that $\phi_{\infty}(S)|_{u}$ and $\phi_{\infty}(S)|_{v}$ have
some linearly dependent set of columns. As we are concerned with errors which
are induced as degenerate errors under a change in the local-dimension we will
omit the trivial linearly dependent columns (those which are the same columns
up to a scalar multiple). Upon removing those columns we now only have
$\phi_{\infty}(S)|_{u\cup v}$, which we aim to avoid having a linearly
dependent set of columns over the new local-dimension. This can be avoided by
not allowing the introduction of a nontrivial kernel for this matrix. From
here the same determinant bound technique may be used. This provides
$p_{D}^{*}$ as the $2(d-1)$ versions of the bounds:

$p_{D}^{*}=\min\\{B^{4(d-1)}(4(d-1))^{2(d-1)},\\\
((q-1)2(d-1)(B(1+(q-1)\tilde{C}(2(d-1))^{2}))^{2(d-1)}\\},$ (14)

with $\tilde{C}\leq((q-1)^{2}(2d-3))^{d-3/2}$. In totality, we must have
$p>\max\\{p^{*},p_{D}^{*}\\}$ in order to ensure the distance is preserved. ∎

This means that just like non-degenerate quantum codes, we may also promise
the distance of the code in the degenerate case, albeit with a larger required
cutoff value. While this cutoff value is large, it provides some local-
dimension value beyond which the distance will be kept and bounds the set of
local-dimension values for which the distance must be manually verified. This
provides information about when the distance of the code must be preserved,
however, if we apply a code over $q$ levels to a system with $p<q$ levels, is
there some range of values for $p$ whereby we know that the distance must
decrease? In the non-degenerate case, we denoted this by $p^{**}$, which was
given by:

$\sqrt{1+{n\choose t}^{1/((n-k)-t)}},\quad
t=\left\lfloor\frac{d-1}{2}\right\rfloor.$ (15)

Whenever $p<p^{**}$, it must be the case that the distance of the code must
decrease. The expression for $p^{**}$ was derived by using the generalized
quantum Hamming bound, which holds for all non-degenerate codes, however, for
degenerate codes this bound does not always hold . This means that for a
general degenerate code we have the following Lemma:

######  Lemma 16.

There is no corresponding $p_{D}^{**}$ that holds for arbitrary degenerate
codes.

While not all degenerate quantum codes obey the generalized quantum Hamming
bound, there are certain code families which do [7, 15]. For those code
families the exact same expression for $p^{**}$ holds as did for non-
degenerate codes.

To ground the prior result, we provide an example next.

######  Example 17.

For our example we consider the six qubit code, with parameters
$[[6,1,3]]_{2}$, generated by an extension of the five qubit code. The
generators for this code can be given by
$\\{YIZXYI,ZXIZYI,ZIXYZI,IIIIIX,IZZZZI\\}$. In the $\phi_{2}$ representation
this is given by:

$\setcounter{MaxMatrixCols}{13}\begin{bmatrix}1&0&0&1&1&0&|&1&0&1&0&1&0\\\
0&1&0&0&1&0&|&1&0&0&1&1&0\\\ 0&0&1&1&0&0&|&1&0&0&1&1&0\\\
0&0&0&0&0&1&|&0&0&0&0&0&0\\\ 0&0&0&0&0&0&|&0&1&1&1&1&0\\\ \end{bmatrix}$ (16)

We perform the following operations to put the code into canonical form: swap
rows $(4,5)$, $H$ on register $4$, swap registers $(5,6)$, then add row $4$ to
rows $2$ and $3$, resulting in:

$\setcounter{MaxMatrixCols}{13}\begin{bmatrix}1&0&0&0&0&1&|&1&0&1&1&0&1\\\
0&1&0&0&0&1&|&1&1&1&0&0&0\\\ 0&0&1&0&0&0&|&1&1&1&1&0&0\\\
0&0&0&1&0&0&|&0&1&1&0&0&1\\\ 0&0&0&0&1&0&|&0&0&0&0&0&0\\\ \end{bmatrix}$ (17)
$L=\begin{bmatrix}0&0&0&0&0\\\ 0&0&0&0&0\\\ 0&0&0&0&0\\\ 0&-2&0&0&0\\\
0&0&0&0&0\end{bmatrix}$ (18)
$\setcounter{MaxMatrixCols}{13}\begin{bmatrix}1&0&0&0&0&1&|&1&0&1&1&0&1\\\
0&1&0&0&0&1&|&1&1&1&0&0&0\\\ 0&0&1&0&0&0&|&1&1&1&1&0&0\\\
0&0&0&1&0&0&|&0&-1&1&0&0&1\\\ 0&0&0&0&1&0&|&0&0&0&0&0&0\\\ \end{bmatrix}$ (19)

In this case $B=1$, and so the original bound based on random permutation of
entries provides $p_{D}^{*}=8^{4}=4096$. This means that so long as more than
$4096$ levels are used the distance of the code can be promised to at least
remain the same. Below this value, unfortunately, one must apply numerical
verification to ensure the distance is preserved.

Lastly, for the logical operators of the local-dimension-invariant
representation of degenerate code the same argument holds as was given in
[10]. With all of these pieces we have an equally complete description of
degenerate LDI codes as existed for non-degenerate LDI codes.

##  IV Discussion

The local-dimension-invariant (LDI) representation of stabilizer codes allows
these codes to be applied regardless of the local-dimension of the underlying
system. When introduced only non-degenerate codes could be written in local-
dimension-invariant form and have their distance promised to be at least
preserved, once the system had sufficiently many levels. In this work we have
shown an alternative bound for how many levels are needed for the distance to
be promised. While this bound suffers a severe dependency on the distance of
the code, it does provide a nearly quadratic improvement on the dependency of
the largest entry in the LDI form of the code, given by $B$. So while this
bound is less helpful in some cases than the original bound it can be a
tighter bound in others.

Beyond this, this work has shown that the LDI representation’s associated
distance promise also exists for degenerate quantum codes, and so completes
the application of this technique to both families of standard stabilizer
codes. Degenerate codes are of particular appeal since they are not restricted
by the generalized quantum Hamming bound and can at times protect more logical
particles than permitted by non-degenerate codes for a given distance and
number of physical particles.

Unfortunately, the utility of this method is somewhat limited as both bounds
on the required local-dimension are quite large. In order to improve the
practicality of this technique the value for $p^{*}$ and $p_{D}^{*}$ must be
significantly decreased. One way to reduce these bounds is to reduce the
expression for $B$, the maximal entry in the LDI representation. To do so,
other analysis techniques will be needed beyond simple counting arguments.
Since the LDI form for a code is not unique, one possible method may be to
solve systems of homogeneous linear diophantine equations, which given the
surplus of variables (additions to entries) compared to variables (requirement
of commutations to be zero) is likely to yield far smaller bounds on $B$. A
starting point for this might include the following works: [16, 17].

The results shown here extend the utility of local-dimension-invariant
stabilizer codes, and so naturally there are questions as to what other uses
this technique will have. Is it possible to apply this technique to show some
foundational aspect of quantum measurements? Can this technique in some way be
used for other varieties of stabilizer like codes, such as Entanglement-
Assisted Quantum Error-Correcting Codes [18, 19]? If this method can be
applied in this situation it is possible that it could remove the need for
entanglement use in these codes, so long as the local-dimension is altered.
However, even still, the local-dimension required would likely be quite large
so the importance of decreasing the bounds for $p^{*}$ and $p_{D}^{*}$ would
become that much more.

## Acknowledgments

We thank Andrew Jena and David Cory for helpful comments.

## Funding

This work was supported by Industry Canada, the Canada First Research
Excellence Fund (CFREF), the Canadian Excellence Research Chairs (CERC 215284)
program, the Natural Sciences and Engineering Research Council of Canada
(NSERC RGPIN-418579) Discovery program, the Canadian Institute for Advanced
Research (CIFAR), and the Province of Ontario.

## References

  * [1] Daniel A Lidar and Todd A Brun.  Quantum error correction.  Cambridge university press, 2013.
  * [2] Yuchen Wang, Zixuan Hu, Barry C Sanders, and Sabre Kais.  Qudits and high-dimensional quantum computing.  Frontiers in Physics, 8:479, 2020.
  * [3] Pei Jiang Low, Brendan M White, Andrew A Cox, Matthew L Day, and Crystal Senko.  Practical trapped-ion protocols for universal qudit-based quantum computing.  Physical Review Research, 2(3):033128, 2020.
  * [4] Poolad Imany, Jose A Jaramillo-Villegas, Mohammed S Alshaykh, Joseph M Lukens, Ogaga D Odele, Alexandria J Moore, Daniel E Leaird, Minghao Qi, and Andrew M Weiner.  High-dimensional optical quantum logic in large operational spaces.  npj Quantum Information, 5(1):1–10, 2019.
  * [5] M Kononenko, MA Yurtalan, J Shi, and A Lupascu.  Characterization of control in a superconducting qutrit using randomized benchmarking.  arXiv preprint arXiv:2009.00599, 2020.
  * [6] Muhammet Ali Yurtalan, Jiahao Shi, M Kononenko, A Lupascu, and S Ashhab.  Implementation of a walsh-hadamard gate in a superconducting qutrit.  Physical Review Letters, 125(18):180504, 2020.
  * [7] Avanti Ketkar, Andreas Klappenecker, Santosh Kumar, and Pradeep Kiran Sarvepalli.  Nonbinary stabilizer codes over finite fields.  IEEE Transactions on Information Theory, 52(11):4892–4914, 2006\.
  * [8] Yang Liu, Ruihu Li, Guanmin Guo, and Junli Wang.  Some nonprimitive bch codes and related quantum codes.  IEEE Transactions on Information Theory, 65(12):7829–7839, 2019\.
  * [9] Xiaoshan Kai, Shixin Zhu, and Ping Li.  Constacyclic codes and some new quantum mds codes.  IEEE Transactions on Information Theory, 60(4):2080–2086, 2014\.
  * [10] Lane G Gunderman.  Local-dimension-invariant qudit stabilizer codes.  Physical Review A, 101(5):052343, 2020.
  * [11] Mark Howard, Joel Wallman, Victor Veitch, and Joseph Emerson.  Contextuality supplies the ‘magic’for quantum computation.  Nature, 510(7505):351–355, 2014.
  * [12] Daniel Gottesman.  Fault-tolerant quantum computation with higher-dimensional systems.  In NASA International Conference on Quantum Computing and Quantum Communications, pages 302–313. Springer, 1998.
  * [13] HF Chau.  Five quantum register error correction code for higher spin systems.  Physical Review A, 56(1):R1, 1997.
  * [14] HF Chau.  Correcting quantum errors in higher spin systems.  Physical Review A, 55(2):R839, 1997.
  * [15] Pradeep Sarvepalli and Andreas Klappenecker.  Degenerate quantum codes and the quantum hamming bound.  Physical Review A, 81(3):032318, 2010.
  * [16] LW Griffiths.  A note on linear homogeneous diophantine equations.  Bulletin of the American Mathematical Society, 52(8):734–736, 1946\.
  * [17] Wallace Givens.  Parametric solution of linear homogeneous diophantine equations.  Bulletin of the American Mathematical Society, 53(8):780–783, 1947\.
  * [18] Todd Brun, Igor Devetak, and Min-Hsiu Hsieh.  Correcting quantum errors with entanglement.  science, 314(5798):436–439, 2006.
  * [19] Mark M Wilde and Todd A Brun.  Optimal entanglement formulas for entanglement-assisted quantum coding.  Physical Review A, 77(6):064302, 2008.