# Conformal Predictor for Improving Zero-shot Text Classification Efficiency

Prafulla Kumar Choubey1 Yu Bai1 Chien-Sheng Wu1
Wenhao Liu2 Nazneen Rajani3 22footnotemark: 2
1Salesforce AI Research, 2Faire.com, 3Hugging Face
{pchoubey, yu.bai<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
work was done at Salesforce AI Research.

###### Abstract

Pre-trained language models (PLMs) have been shown effective for zero-shot
(0shot) text classification. 0shot models based on natural language inference
(NLI) and next sentence prediction (NSP) employ cross-encoder architecture and
infer by making a forward pass through the model for each label-text pair
separately. This increases the computational cost to make inferences linearly
in the number of labels. In this work, we improve the efficiency of such
cross-encoder-based 0shot models by restricting the number of likely labels
using another fast base classifier-based conformal predictor (CP) calibrated
on samples labeled by the 0shot model. Since a CP generates prediction sets
with coverage guarantees, it reduces the number of target labels without
excluding the most probable label based on the 0shot model. We experiment with
three intent and two topic classification datasets. With a suitable CP for
each dataset, we reduce the average inference time for NLI- and NSP-based
models by 25.6% and 22.2% respectively, without dropping performance below the
predefined error rate of 1%.

##  1 Introduction

Zero-shot (0shot) text classification is an important NLP problem with many
real-world applications. The earliest approaches for 0shot text classification
use a similarity score between text and labels mapped to common embedding
space (Chang et al., 2008; Gabrilovich and Markovitch, 2007; Chen et al.,
2015; Li et al., 2016; Sappadla et al., 2016; Xia et al., 2018). These models
calculate text and label embeddings independently and make only one forward
pass over the text resulting in a minimal increase in the computation. Later
approaches explicitly incorporate label information when processing the text,
e.g., Yogatama et al. (2017) uses generative modeling and generates text given
label embedding, and Rios and Kavuluru (2018) uses label embedding based
attention over text, both requiring multiple passes over the text and
increasing the computational cost.

Most recently, NLI- Condoravdi et al. (2003); Williams et al. (2018); Yin et
al. (2019) and NSP- Ma et al. (2021) based 0shot text classification
formulations have been proposed. NLI and NSP make inferences by defining a
representative hypothesis sentence for each label and producing a score
corresponding to every pair of input text and hypothesis. To compute the
score, they employ a cross-encoder architecture that is full self-attention
over the text and hypothesis sentences, which requires recomputing the
encoding for text and each hypothesis separately. It increases the
computational cost to make inferences linearly in the number of target labels.

NLI and NSP use large transformer-based PLMs (Devlin et al., 2019; Liu et al.,
2019b; Lewis et al., 2019) and outperform previous non-transformer-based
models by a large margin. However, the size of PLMs and the number of target
labels drastically reduce the prediction efficiency, increasing the
computation and inference time, and may significantly increase the carbon
footprint of making predictions (Strubell et al., 2019; Moosavi et al., 2020;
Schwartz et al., 2020; Zhou et al., 2021).

In this work, we focus on the correlation between the number of labels and
prediction efficiency and propose to use a conformal predictor (CP) Vovk et
al. (2005); Shafer and Vovk (2008) to filter out unlikely labels from the
target. Conformal prediction provides a model-agnostic framework to generate a
label set, instead of a single label prediction, within a pre-defined error
rate. Consequently, we use a CP, with a small error rate we select, based on
another fast base classifier to generate candidate target labels. Candidate
labels are then used with the larger NLI/NSP-based 0shot models to make the
final prediction.

We experiment with three intent classification (SNIPS (Coucke et al., 2018),
ATIS (Tur et al., 2010) and HWU64 (Liu et al., 2019a)) and two topic
classification (AG’s news and Yahoo! Answers (Zhang et al., 2015)) datasets
using 0shot models based on a moderately sized bart-large (NLI) (Lewis et al.,
2020) and a small bert-base (NSP) PLM. We use four different base classifiers,
each with different computational complexity, and a small error rate of 1%. By
using the best CP for each dataset, we reduce the average computational time
by 25.6% (22.2%) and the average number of labels by 41.09% (43.38%) for
NLI-(NSP-) based models.

##  2 Methodology

We improve the efficiency of NLI/NSP models by restricting the number of
target labels with a Conformal Predictor (CP). Using a fast but weak base
classifier-based CP, we produce the label set that removes some of the target
classes for the 0shot model without reducing the coverage beyond a pre-defined
error rate.

###  2.1 Building a Conformal Predictor (CP) for Label Filtering

Conformal prediction Vovk et al. (1999, 2005); Shafer and Vovk (2008);
Maltoudoglou et al. (2020); Angelopoulos and Bates (2021); Giovannotti and
Gammerman (2021); Dey et al. (2021) generates label sets with coverage
guarantees. For a given error rate $\alpha$ and a base classifier
$\hat{f}:x\rightarrow\mathbb{R}^{K}$ (here $K$ is the total number of class
labels), a CP outputs a label set $\Gamma^{\alpha}$ that also contains true
class label $y$ with probability at least $1-\alpha$.

To build a CP, we need calibration data
{$(x_{1},y_{1}),(x_{2},y_{2}),..,(x_{n},y_{n})$} and a measure of non-
conformity $s(x_{i},y_{i})$ that describes the disagreement between the actual
label $y_{i}$ and the prediction $\hat{f}(x_{i})$ from the base classifier. As
an example, a non-conformity score can be defined as the negative output logit
of the true class. Assuming the base classifier outputs logit scores, in this
case $s(x_{i},y_{i})$ will be $-\hat{f}(x_{i})_{y_{i}}$. Next, we define
$\hat{q}$ to be the $\lceil(n+1)(1-\alpha)\rceil/n$ empirical quantile of
scores $s(x_{1},y_{1}),s(x_{2},y_{2}),..,s(x_{n},y_{n})$ on the calibration
set. Finally, for a new exchangeable test data point $x_{test}$, we output the
label set $\Gamma^{\alpha}$ = {$y^{k}:s(x_{test},y^{k})<\hat{q}$}, i.e., the
classes corresponding to which the non-conformity score is lower than the
$\hat{q}$. $\Gamma^{\alpha}$ is finally used with the 0shot model to predict
the final class label. Next, we discuss the two components of a CP, namely the
calibration dataset and the non-conformity score.

###  2.2 Calibration Dataset

We require a calibration dataset that is exchangeable with the test data.
However, in a typical 0shot setting, we do not expect the availability of a
human-labeled dataset. Therefore, we use the 0shot classifier to label samples
for calibration. Since our goal is to obtain a label set that contains the
class label which is most probable according to the 0shot classifier, we do
not explicitly require human-labeled samples. Using model-predicted labels for
calibration guarantees the required coverage.

Figure 1: Coverage of CP-predicted label sets for different non-conformity
score and calibration dataset on the Intent/ Topic-classification tasks with
the NLI 0shot model.

Figure 2: Average Prediction Set (APS) size for different non-conformity score
and calibration dataset on the Intent/ Topic-classification tasks with the NLI
0shot model.

###  2.3 Non-Conformity score based on a Base Classifier

We want the base classifier to be computationally efficient when compared to
the 0shot model. We experiment with four base classifiers with different
complexity for building our CPs,

  * •

Token Overlap (CP-Token): For each target class label
($y^{k}\in\\{y^{1},..,y^{K}\\}$), we make a list of representative tokens
($C_{w}^{k}$) that includes all tokens in the calibration data samples
corresponding to that class. Then, we define the non-conformity score using
the percentage of common tokens between $C_{w}^{k}$ and the input text ($x$).
Given $\\#x$ defines the unique tokens in $x$, the token overlap-based non-
conformity score is defined as:

$s(x,y^{k})=1.0-\frac{|C_{w}^{k}\cap x|}{\\#x}$ (1)

  * •

Cosine Similarity (CP-Glove): Token overlap-based non-conformity score suffers
from sparsity unless we use a large representative words-set for each target
class label. Therefore, we also experiment with the cosine distance between
the bag-of-words (BoW) representation of a target label description
($C_{E}^{k}$) and input text ($x_{E}$). We use static GloVe embeddings
(Pennington et al., 2014) to obtain BoW representations for labels.

$s(x,y^{k})=1.-\frac{C_{E}^{k}\cdot
x_{E}}{{\|C_{E}^{k}\|}_{2}{\|x_{E}\|}_{2}}$ (2)

  * •

Classifier (CP-CLS): Besides the broadly applicable token overlap and cosine
similarity, we propose to use a task-specific base classifier to generate
label sets of smaller sizes. We fine-tune a distilled bert-base model on the
data labeled using the 0shot model and use the negative of class logits as the
non-conformity scores.

  * •

Distilled NLI Model (CP-Distil): Fine-tuning a PLM (CLS) requires data labeled
by the 0shot model, which may not be always accessible. In such scenarios, we
propose to use another parameter-efficient NLI 0shot model (e.g. distil-
roberta-base-nli) as the base classifier. While NLI-based 0shot models are
computationally expensive, they may make a good base classifier for relatively
larger PLMs, with many parameters (e.g. GPT-3 (Brown et al., 2020)), or when
there are many target class labels (e.g. 64 labels in HWU64). We define the
non-conformity score as the negative entailment probability.

##  3 Experiments

We evaluate our CP-based framework on the test set of intent (SNIPS, ATIS and
HWU64) and topic (AG’s news and Yahoo! Answers) classification datasets.
SNIPS, ATIS, HWU64, AG’s news and Yahoo! Answers have 7, 17, 64, 4 and 10
target labels, respectively. We use “facebook/bart-large-nli” and “bert-base-
uncased” models from the Hugging Face hub (Wolf et al., 2020) as our 0shot NLI
and NSP baselines. Our experimental setup is described in appendix ($\S$A).

| ATIS | HWU64 | SNIPS | AGNEWS | YAHOO
---|---|---|---|---|---
| A $\uparrow$ | T $\downarrow$ | |L| $\downarrow$ | A $\uparrow$ | T $\downarrow$ | |L| $\downarrow$ | A $\uparrow$ | T $\downarrow$ | |L| $\downarrow$ | A $\uparrow$ | T $\downarrow$ | |L| $\downarrow$ | A $\uparrow$ | T $\downarrow$ | |L| $\downarrow$
Entailment: bart-large-mnli
Full | 71.5 | 1.0 | 17.0 | 49.3 | 1.0 | 64.0 | 76.7 | 1.0 | 7.0 | 75.9 | 1.0 | 4.0 | 51.8 | 1.0 | 10.0
CP-Token | 70.1 | 0.63 | 9.1 | 49.4 | 0.79 | 47.6 | 75.8 | 0.88 | 5.9 | 75.5 | 0.91 | 3.5 | 51.4 | 0.91 | 9.7
CP-Glove | 71.0 | 1.01 | 16.7 | 49.3 | 1.0 | 63.4 | 76.0 | 0.98 | 6.8 | 75.0 | 0.99 | 3.9 | 51.4 | 1.05 | 9.8
CP-CLS | 71.5 | 0.98 | 9.2 | 49.3 | 0.71 | 30.59 | 77.0 | 0.98 | 3.5 | 76.2 | 0.99 | 2.4 | 51.7 | 0.80 | 8.1
CP-Distil | 71.5 | 0.98 | 14.0 | 49.7 | 0.50 | 27.7 | 76.7 | 0.91 | 4.6 | 75.9 | 0.94 | 2.9 | 51.9 | 0.83 | 7.2
Next Sentence Prediction: bert-base-uncased
Full | 23.6 | 1.0 | 17.0 | 47.2 | 1.0 | 64.0 | 81.7 | 1.0 | 7.0 | 79.3 | 1.0 | 4.0 | 52.0 | 1.0 | 10.0
CP-Token | 23.1 | 0.41 | 5.3 | 47.2 | 0.85 | 53.8 | 81.0 | 0.94 | 6.0 | 78.9 | 0.96 | 3.5 | 52.0 | 0.97 | 9.6
CP-Glove | 23.9 | 0.99 | 16.4 | 47.1 | 1.0 | 63.0 | 80.8 | 1.0 | 6.8 | 78.3 | 0.99 | 3.9 | 51.8 | 1.0 | 9.6
CP-CLS | 23.6 | 0.61 | 6.1 | 47.3 | 0.69 | 39.3 | 81.8 | 0.88 | 4.4 | 80.4 | 1.41 | 2.1 | 52.3 | 0.95 | 7.8
CP-Distil | 23.7 | 1.51 | 16.1 | 47.3 | 1.15 | 57.7 | 82.7 | 1.97 | 4.2 | 80.1 | 2.13 | 3.0 | 52.6 | 1.69 | 8.8

Table 1: Performance comparison of different base classifiers. We use the
error rate $\alpha$ of 0.01, and report accuracy (A), average time to make
inference (T) and average prediction set size (|L|). We underline the cases
where a CP increases the inference time.

In Fig. 1 and 2, we plot the empirical coverage and the average prediction set
(APS) size of four base classifiers on ATIS, HWU64 and Yahoo! Answers
datasets. Coverage defines the proportion of samples for which the predicted
set contains the 0shot model-predicted label. APS size equals the average
number of labels in the set predicted by the CP base classifier.

In Table 1, we compare the accuracy (A), average inference time (T) and the
APS size (|L|) used with the 0shot model. Average inference time is reported
relative to the full model. “Full” represents the 0shot model that uses the
full label set. During inference, we create one batch for all text-label pairs
in a sample. For instance, with 64 labels, a batch includes 64 text-label
pairs where each pair consists of text and one label. This allows us to
measure the reduction in inference time while fully utilizing the available
compute resources.

###  3.1 Results

A CP achieves a valid coverage. We find that for smaller values of $\alpha$,
all four base classifiers achieve valid coverage (Fig. 1), i.e., empirical and
nominal coverages are identical, implying that we can use a CP to filter
unlikely target labels without dropping the performance below a low predefined
error rate $\alpha$. For larger $\alpha$s (>$\sim$0.5), empirical coverage
drops to 0 on intent datasets for token overlap-based non-conformity score.
The reduced coverage for token overlap at lower $\alpha$ results from an empty
label set, as evident from 0 APS size in Fig. 2.

A CP reduces the average number of labels for the 0shot model. We find that a
stronger base classifier (CLS and Distil) provides lower APS size for the same
empirical (or nominal) coverage (Fig. 2). On average, CP-CLS provides the
lowest APS size, reducing the average number of labels for both 0shot models
by roughly 41% (Table 1). This suggests that fine-tuning a base classifier
should be preferred when unlabelled samples are easily available.

A simpler and efficient CP base classifier may reduce the inference time the
most. We observe that CP-Token achieves the best inference time with the NLI
model on ATIS, SNIPS and AG’s news datasets, and with the NSP model on ATIS
and AG’s news datasets. On the other hand, it achieves the lowest APS size for
both models only on the ATIS dataset. Minimal complexity for calculating
token-overlap adds negligible overhead to the 0shot model, thus, achieving the
best speed up despite higher APS size in several cases.

A CP base classifier needs to be computationally inexpensive. CP-Distil
improves inference time for the NLI model on all datasets but fails to do so
for the NSP model, despite reduced APS size. This ineffectiveness is explained
by the comparable inference time for the base (distil-nli) classifier and the
0shot NSP model. When building a CP, it is imperative to select a base
classifier that is computationally economical relative to the 0shot model.

A CP improves efficiency the most on the dataset with many labels. We observe
the maximum speed up on HWU64 and ATIS datasets. This is unsurprising given
the relatively higher number of possible target labels for both datasets,
emphasizing the benefit of a CP for tasks with many target labels.

A CP performs comparably to the 0shot model. CP-based label filtering retains
the performance of the corresponding models that use a full label set. Among
the four base classifiers, CP-Token performs the worst (-0.46% absolute drop)
and CP-Distil performs the best (+0.31% absolute gain) on the average
accuracy. It is noteworthy that the accuracy increases in many cases,
suggesting that pruning label space using a CP may remove noisy labels and
boost the performance.

###  3.2 Applying a CP in Practical Applications

Our experiments show that the inference speed-up from a CP depends on the
sizes of the zero-shot model, the base classifier, and the label space. A
strong base classifier (e.g., CP-CLS, CP-Distil) often gives better APS size
leading to faster zero-shot inference. But it is also slow in generating the
label set for the 0shot model. On the other hand, weaker base classifiers are
fast but generate larger prediction sets resulting in slower 0shot inference.
Given the trade-off, a stronger base classifier model such as BERT/ RoBERTa
(or distilled model) makes a better choice when the label space is large
(e.g., 64 for HWU64) and (or) the zero-shot model is large (e.g., bart-large-
mnli). Otherwise, a faster base classifier (e.g., token overlap matching)
would be ideal.

##  4 Discussion and Future Work

In this work, we show that CP-based target label filtering improves the
efficiency of NLI- and NSP-based zero-shot text classification models. Our CP
framework is generalizable to many formulations of zero- or few-shot models.
For instance, prompt-based models that auto-regressively generate verbalizers
(Schick and Schütze, 2021) are very slow, as the number of forward passes
increases with the number of labels and verbalizer’s tokens (Karimi Mahabadi
et al., 2022). Our conformal prediction framework can be directly used there
to reduce the number of labels and improve efficiency. Additionally, the
proposed conformal prediction framework can be used to filter training
examples when constructing prompts for in-context learning (Brown et al.,
2020), where we prime PLM with a sequence of training examples. For a task
with many target labels, a naively constructed prompt would require at least
one training example for each label. However, with CP, we can limit the number
of labels (and consequently the number of training examples) in the prompt,
minimizing the computational cost.

In the future, we will explore newer methods to build conformal predictors
that can further reduce the average prediction set size and inference time, as
well as boost the performance of a 0shot model.

##  5 Limitations

The datasets utilized in this research contain texts in English and thus
mainly represent the culture of the English-speaking populace. Gender or age
biases may also exist in the datasets, and pre-trained models may also exhibit
these biases. In addition, though the likelihood is slim, additional biases
may also be introduced by CP-based label filtering.

We recommend that any subsequent usage of the proposed technique clearly
states that the conformal predictor was used for label filtering. In addition,
while results suggest that our framework is generally effective for different
zero-shot tasks, it should not be utilized on any new task without thorough
evaluation, including evaluating for ethical or social risks.

## Acknowledgement

We would like to thank the anonymous reviewers for their feedback.

## References

  * Angelopoulos and Bates (2021) Anastasios N. Angelopoulos and Stephen Bates. 2021.  A gentle introduction to conformal prediction and distribution-free uncertainty quantification.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  _CoRR_ , abs/2005.14165.
  * Chang et al. (2008) Ming-Wei Chang, Lev Ratinov, Dan Roth, and Vivek Srikumar. 2008.  Importance of semantic representation: Dataless classification.  In _Proceedings of the 23rd National Conference on Artificial Intelligence - Volume 2_ , AAAI’08, page 830–835. AAAI Press.
  * Chen et al. (2015) Xingyuan Chen, Yunqing Xia, Peng Jin, and John A. Carroll. 2015.  Dataless text classification with descriptive lda.  In _AAAI_.
  * Condoravdi et al. (2003) Cleo Condoravdi, Dick Crouch, Valeria de Paiva, Reinhard Stolle, and Daniel G. Bobrow. 2003.  Entailment, intensionality and text understanding.  In _Proceedings of the HLT-NAACL 2003 Workshop on Text Meaning_ , pages 38–45.
  * Coucke et al. (2018) Alice Coucke, Alaa Saade, Adrien Ball, Théodore Bluche, Alexandre Caulier, David Leroy, Clément Doumouro, Thibault Gisselbrecht, Francesco Caltagirone, Thibaut Lavril, Maël Primet, and Joseph Dureau. 2018.  Snips voice platform: an embedded spoken language understanding system for private-by-design voice interfaces.  _ArXiv_ , abs/1805.10190.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Dey et al. (2021) Neil Dey, Jing Ding, Jack Ferrell, Carolina Kapper, Maxwell Lovig, Emiliano Planchon, and Jonathan P Williams. 2021.  Conformal prediction for text infilling and part-of-speech prediction.
  * Gabrilovich and Markovitch (2007) Evgeniy Gabrilovich and Shaul Markovitch. 2007.  Computing semantic relatedness using wikipedia-based explicit semantic analysis.  In _Proceedings of the 20th International Joint Conference on Artifical Intelligence_ , IJCAI’07, page 1606–1611, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
  * Giovannotti and Gammerman (2021) Patrizio Giovannotti and Alex Gammerman. 2021.  Transformer-based conformal predictors for paraphrase detection.  In _Proceedings of the Tenth Symposium on Conformal and Probabilistic Prediction and Applications_ , volume 152 of _Proceedings of Machine Learning Research_ , pages 243–265. PMLR.
  * Karimi Mahabadi et al. (2022) Rabeeh Karimi Mahabadi, Luke Zettlemoyer, James Henderson, Lambert Mathias, Marzieh Saeidi, Veselin Stoyanov, and Majid Yazdani. 2022.  Prompt-free and efficient few-shot learning with language models.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 3638–3652, Dublin, Ireland. Association for Computational Linguistics.
  * Lewis et al. (2019) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2019.  BART: denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _CoRR_ , abs/1910.13461.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880, Online. Association for Computational Linguistics.
  * Li et al. (2016) Yuezhang Li, Ronghuo Zheng, Tian Tian, Zhiting Hu, Rahul Iyer, and Katia Sycara. 2016.  Joint embedding of hierarchical categories and entities for concept categorization and dataless classification.  In _Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers_ , pages 2678–2688, Osaka, Japan. The COLING 2016 Organizing Committee.
  * Liu et al. (2019a) Xingkun Liu, Arash Eshghi, Pawel Swietojanski, and Verena Rieser. 2019a.  Benchmarking natural language understanding services for building conversational agents.  In _IWSDS_.
  * Liu et al. (2019b) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019b.  Roberta: A robustly optimized bert pretraining approach.  _ArXiv_ , abs/1907.11692.
  * Loshchilov and Hutter (2019) Ilya Loshchilov and Frank Hutter. 2019.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_.
  * Ma et al. (2021) Tingting Ma, Jin-Ge Yao, Chin-Yew Lin, and Tiejun Zhao. 2021.  Issues with entailment-based zero-shot text classification.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 786–796, Online. Association for Computational Linguistics.
  * Maltoudoglou et al. (2020) Lysimachos Maltoudoglou, Andreas Paisios, and Harris Papadopoulos. 2020.  Bert-based conformal predictor for sentiment analysis.  In _Proceedings of the Ninth Symposium on Conformal and Probabilistic Prediction and Applications_ , volume 128 of _Proceedings of Machine Learning Research_ , pages 269–284. PMLR.
  * Moosavi et al. (2020) Nafise Sadat Moosavi, Angela Fan, Vered Shwartz, Goran Glavaš, Shafiq Joty, Alex Wang, and Thomas Wolf, editors. 2020.  _Proceedings of SustaiNLP: Workshop on Simple and Efficient Natural Language Processing_. Association for Computational Linguistics, Online.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014.  Glove: Global vectors for word representation.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1532–1543.
  * Rios and Kavuluru (2018) Anthony Rios and Ramakanth Kavuluru. 2018.  Few-shot and zero-shot multi-label learning for structured label spaces.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3132–3142, Brussels, Belgium. Association for Computational Linguistics.
  * Sappadla et al. (2016) Prateek Veeranna Sappadla, Jinseok Nam, Eneldo Loza Mencía, and Johannes Fürnkranz. 2016.  Using semantic similarity for multi-label zero-shot classification of text documents.  In _ESANN_.
  * Schick and Schütze (2021) Timo Schick and Hinrich Schütze. 2021.  It’s not just size that matters: Small language models are also few-shot learners.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2339–2352, Online. Association for Computational Linguistics.
  * Schwartz et al. (2020) Roy Schwartz, Jesse Dodge, Noah A. Smith, and Oren Etzioni. 2020.  Green ai.  _Commun. ACM_ , 63(12):54–63.
  * Shafer and Vovk (2008) Glenn Shafer and Vladimir Vovk. 2008.  A tutorial on conformal prediction.  _Journal of Machine Learning Research_ , 9(12):371–421.
  * Strubell et al. (2019) Emma Strubell, Ananya Ganesh, and Andrew McCallum. 2019.  Energy and policy considerations for deep learning in NLP.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3645–3650, Florence, Italy. Association for Computational Linguistics.
  * Tur et al. (2010) Gokhan Tur, Dilek Hakkani-Tür, and Larry Heck. 2010.  What is left to be understood in atis? In _2010 IEEE Spoken Language Technology Workshop_ , pages 19–24.
  * Vovk et al. (2005) Vladimir Vovk, Alex Gammerman, and Glenn Shafer. 2005.  _Algorithmic Learning in a Random World_.  Springer-Verlag, Berlin, Heidelberg.
  * Vovk et al. (1999) Volodya Vovk, Alex Gammerman, and Craig Saunders. 1999.  Machine-learning applications of algorithmic randomness.  In _In Proceedings of the Sixteenth International Conference on Machine Learning_ , pages 444–453. Morgan Kaufmann.
  * Williams et al. (2018) Adina Williams, Nikita Nangia, and Samuel Bowman. 2018.  A broad-coverage challenge corpus for sentence understanding through inference.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1112–1122, New Orleans, Louisiana. Association for Computational Linguistics.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Xia et al. (2018) Congying Xia, Chenwei Zhang, Xiaohui Yan, Yi Chang, and Philip Yu. 2018.  Zero-shot user intent detection via capsule neural networks.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3090–3099, Brussels, Belgium. Association for Computational Linguistics.
  * Yin et al. (2019) Wenpeng Yin, Jamaal Hay, and Dan Roth. 2019.  Benchmarking zero-shot text classification: Datasets, evaluation and entailment approach.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3914–3923, Hong Kong, China. Association for Computational Linguistics.
  * Yogatama et al. (2017) Dani Yogatama, Chris Dyer, Wang Ling, and Phil Blunsom. 2017.  Generative and discriminative text classification with recurrent neural networks.  _ArXiv_ , abs/1703.01898.
  * Zhang et al. (2015) Xiang Zhang, Junbo Zhao, and Yann LeCun. 2015.  Character-level convolutional networks for text classification.  In _Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1_ , NIPS’15, page 649–657, Cambridge, MA, USA. MIT Press.
  * Zhou et al. (2021) Xiyou Zhou, Zhiyu Chen, Xiaoyong Jin, and William Yang Wang. 2021.  HULK: An energy efficiency benchmark platform for responsible natural language processing.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: System Demonstrations_ , pages 329–336, Online. Association for Computational Linguistics.

##  Appendix A Experimental Details

We use the entire training set of intent datasets and 5000 samples from the
validation set of topic datasets to calibrate CP-Token, CP-Glove and CP-
Distil. For CP-CLS, we use the entire training set of intent datasets and 2500
samples from the validation set of topic datasets to train the base
classifier, and the entire validation set of intent datasets and 2500 samples
from the validation set of topic datasets for calibration.

For the CP-Distil base classifier, we use “cross-encoder/nli-distilroberta-
base” model from the Hugging Face hub. We describe the procedure for building
CP-CLS in $\S$A.1. Note that we only require the text to be classified
(without labels) for calibrating base classifiers and training CP-CLS base
classifier. We use the 0shot model to label the corresponding training and
calibration samples.

###  A.1 CP-CLS: Training and Evaluation

We fine-tune distilbert-base PLM for 15 epochs with the batch size of 16. We
use AdamW optimizer (Loshchilov and Hutter, 2019) with default hyper-
parameters, warm-up steps of 100 and weight decay of 0.01. We choose the
checkpoint with the highest accuracy on the calibration dataset. The accuracy
of the CP-CLS base classifier with respect to the labels generated by the
0shot model is reported in Table 2.

| ATIS | HWU64 | SNIPS | AGNEWS | YAHOO
---|---|---|---|---|---
NLI | 84.99 | 67.28 | 88.0 | 66.88 | 87.64
NSP | 82.80 | 71.18 | 89.40 | 73.16 | 88.24

Table 2: Accuracy of the CP-CLS base classifier with respect to the labels
generated by the 0shot model on the calibration dataset.

##  Appendix B Calibration dataset

Figure 3: Coverage of CP-predicted label sets for different size of
calibration set.  Figure 4: APS size with different size of calibration set.
Figure 5: Coverage of CP-predicted label sets for calibration set from another
dataset.  Figure 6: APS size for calibration set from another dataset.

In our experiments, we assumed the availability of text from the target task
for calibration (and training a base classifier). While we can use a 0shot
base classifier (e.g., CP-Token /Glove/ Distil), we still require a few
samples for the CP calibration. Next, we analyze the number of samples
required to build a CP and the transferability of a CP from another different
dataset in Fig. 3, 4, 5 and 6. These plots belong to the NLI-based 0shot model
on the HWU64 dataset with the corresponding best-performing CP-Distil non-
conformity score. 200 (up to 2500) in Fig. 3 and 4 represents the number of
samples used for calibration. The full model is calibrated on the entire
dataset. In Fig. 5 and 6, SNIPS+ATIS is calibrated using the samples from
SNIPS and ATIS datasets, and ALL is calibrated using the samples from SNIPS,
ATIS, Yahoo! Answers and AG’s news datasets. We describe our findings below.

A small sized-calibration set with low chosen $\alpha$ improves 0shot
classification efficiency without dropping the performance. We find that the
empirical coverage is worse than the nominal coverage for smaller-sized
calibration data (200-1000) (Fig. 3). A model using calibration data with 1500
or more samples has identical empirical and nominal coverages. At the same
time, the difference in empirical and nominal coverage is negligible for all
calibration data sizes at a low error rate ($\alpha=0.01$), as evident from
the same starting point for all plots (at $1-\alpha=0.99$). Consequently, we
can use the conformal prediction framework even with a small calibration set
provided we use a low value for $\alpha$. Next, as shown in Fig. 4, the
dependence between the APS size and the size of calibration data is not
linear. CP-Distil models based on 200, 400 and full calibration samples obtain
comparable APS sizes. Additionally, APS sizes for other models are
significantly better than the full label set (maximum APS size of 37 for
models calibrated on 1000 and 1500 samples vs full label set size of 64).

We can use a calibration set from another dataset only if the $\alpha$ is set
to a low value We observe that none of the ATIS, SNIPS, ATIS+SNIPS or ALL
calibration sets obtains the same empirical and nominal coverage. But, similar
to our observations on the size of the calibration set, samples from another
dataset can be used for calibration (Fig. 5), provided we use a low $\alpha$.
However, the resulting APS size is larger than that of the model that uses
calibration data from the target task (Fig. 6).


# A circuit-level protocol and analysis for twist-based lattice surgery

Christopher Chamberland<EMAIL_ADDRESS>AWS Center for Quantum Computing,
Pasadena, CA 91125, USA  IQIM, California Institute of Technology, Pasadena,
CA 91125, USA  Earl T. Campbell<EMAIL_ADDRESS>AWS Center for
Quantum Computing, Cambridge, UK

###### Abstract

Lattice surgery is a measurement-based technique for performing fault-tolerant
quantum computation in two dimensions. When using the surface code, the most
general lattice surgery operations require lattice irregularities called twist
defects. However, implementing twist-based lattice surgery may require
additional resources, such as extra device connectivity, and could lower the
threshold and overall performance for the surface code. Here we provide an
explicit twist-based lattice surgery protocol and its requisite connectivity
layout. We also provide new stabilizer measurement circuits for measuring
twist defects which are compatible with our chosen gate scheduling. We
undertake the first circuit-level error correction simulations during twist-
based lattice surgery using a biased depolarizing noise model. Our results
indicate a slight decrease in the threshold for timelike logical failures
compared to lattice surgery protocols with no twist defects in the bulk.
However, comfortably below threshold (i.e. with CNOT infidelities below
$5\times 10^{-3}$), the performance degradation is mild and in fact preferable
over proposed alternative twist-free schemes. Lastly, we provide an efficient
scheme for measuring $Y$ operators along boundaries of surface codes which
bypasses certain steps that were required in previous schemes.

##  I Introduction

The surface code is a quantum error correcting code with a high threshold and
which can be realised with two-dimensional hardware [1, 2]. Other codes have
been observed to have comparable thresholds for toy noise models [3, 4, 5, 6,
7, 8], but when considering realistic circuit-level noise their performance
(relative to the surface code) drops appreciably. The surface code’s high
threshold can be partially attributed to the simplicity of its stabilizers and
the circuits used to measure them. Realising the surface code requires
measurements of pure $X$-type and $Z$-type stabilizers involving no more than
four qubits. These measurements can be performed using a depth-four sequence
of two-qubit gates; the minimum we can hope for. Furthermore, choosing the
right gate schedule can make the stabilizer measurement circuits immune to
“hook” errors that effectively reduce the code distance. The moral here is
that careful, circuit-level analysis of the microscopic details is crucial for
a full understanding of the best route to fault-tolerant quantum computing.

Logical operations in two-dimensional surface code architectures can be
performed by code deformation where the code stabilizers change over time,
such as through braiding [9, 2] or lattice surgery [10, 11, 12], with the
latter being more resource efficient [13, 14]. The basic primitive in lattice
surgery is a logical multi-qubit Pauli measurement, which when combined with
logical ancilla states can be used to fault-tolerantly perform logical
Clifford operations in addition to logical non-Clifford gates by
teleportation. When measuring logical Paulis composed of $X$ and $Z$
operators, the code is deformed with several surface code patches merged into
a large patch, though locally the code stabilizers are unchanged. However,
more generally, measurements involving Pauli $Y$ operators are needed. Such
measurements can be realised with twist-based lattice surgery [11], though
this requires some weight-five measurements in addition to long range multi-
qubit gates. The proposed twist-based approaches were presented abstractly,
ignoring circuit-level implementation details and any related performance
impacts.

Figure 1: Connectivity diagram between data qubits (yellow) and ancilla qubits
(grey) with two example gate schedules. Thick, solid grey lines show the
connectivity needed to perform a standard weight-four check as shown here for
a blue $Z^{\otimes 4}$ stabilizer. To perform a check along an elongated
rectangle (such as the red check shown in the figure) additional connectivity
can be used which we illustrate as dashed grey lines. For the elongated
$X^{\otimes 4}$ check, the two grey ancilla qubits are prepared in a GHZ state
which is used to perform the desired stabilizer measurement. Examples of gate
schedulings and circuits used to measure stabilizers are shown (numbers
indicate the time step for each two-qubit gate) and further circuit details
are given in Appendix A. The first and last time steps are used for state
preparation and measurement and so are both labeled as time step 1. In
subsequent figures, we will sometimes just provide numerical labels when the
type of gate is clear from the context.

Our work gives the first proposal for a circuit-level implementation of twist-
based lattice surgery and numerically benchmarks the performance. In twist-
based lattice surgery, we need to measure some longer range stabilizers that
we call elongated rectangles and twist defects. To perform these measurements
without increasing the circuit-depth (which would significantly degrade
performance), we assume the hardware connectivity illustrated in Fig. 1. We
say two qubits are connected when a two-qubit gate can be performed between
these qubits. Standard surface code implementations have each qubit connected
to four other qubits. In this work, we assume a minimal extension where some
qubits are connected to eight other qubits. The cat-qubit based architecture
of Ref. [15] naturally provides this connectivity, and it could be produced in
other architectures, though at the risk of additional cross-talk. Yoder and
Kim proposed a twist-based scheme with lower weight measurements [16], but
they required a substantial change to the underlying surface code [16] and did
not use a homogeneous (translationally invariant) hardware. We leave open the
question of whether twist-based lattice surgery can be realised using less
connectivity within a homogeneous two-dimensional architecture.

To benchmark twist-based lattice surgery, we perform Monte Carlo simulations
with a minimum-weight perfect matching (MWPM) decoding protocol (following the
method of Ref. [17]) of $Y\otimes Y$ and $Z\otimes Z$ measurements. We perform
our simulations for biased noise and rectangular surface codes since this
enables us to perform larger simulations and these noise models are of recent
interest [18, 19, 20, 21, 22, 15]. We observe that the measurement of a
logical $Y\otimes Y$ operator has a higher logical failure rate relative to a
comparable $Z\otimes Z$ measurement of the same area. We attribute such
differences to the presence of twist defects and elongated checks. The logical
failure probability of these measurements is exponentially suppressed in the
number of stabilizer measurement rounds used. Therefore, we can ask how many
more rounds (and therefore time cost) is needed for a $Y\otimes Y$ measurement
to achieve the same logical fidelity as a $Z\otimes Z$ measurement. We find,
well below threshold ($p_{\text{CNOT}}\leq 0.1\%$), the use of twists incurs
only a small multiplicative time cost (less than $1.2\times$ for one of the
studied noise models when $p_{\text{CNOT}}=10^{-3}$) since the twists are a
small fraction of all possible fault locations. However, the twist defects are
the weakest point and thus fail with a higher probability compared to other
fault locations. Consequently, we find these multiplicative time costs
increase as we approach the threshold.

In previous work [17], we proposed an alternative twist-free lattice surgery
scheme that replicated the computational power of Pauli $Y$ measurements
without the need for twist defects. However, this alternative strategy came
with its own $\sim 2\times$ time cost. Therefore, a key conclusion of this
work is that twist-based approaches outperform twist-free alternatives when
operating comfortably below threshold, and under our connectivity assumptions
along with the biased noise model used for the simulations. Twist-free lattice
surgery may still prove useful in connectivity limited hardware or very close
to threshold. Hardware afflicted by a different noise model than considered in
this work might also benefit from twist-free lattice surgery.

Figure 2: Illustration of a $Z\otimes Z$ and $Y\otimes Y$ measurement
performed by lattice surgery. The left most figure shows two $d_{x}=3$ and
$d_{z}=9$ logical patches prior to the measurements. The qubits (yellow and
grey vertices) in between the two patches are part of the routing space. The
middle figure shows the measurement of $Z\otimes Z$ by gauge fixing, i.e.
measuring the appropriate stabilizers in the routing space such that a
$Z\otimes Z$ measurement is performed along the logical $Z$ boundaries of the
surface code patches. Red plaquettes correspond to $X$-type stabilizers, blue
plaquettes to $Z$-type stabilizers. Gradient colour plaquettes correspond to
domain walls that measure mixed $X$ and $Z$-type stabilizers. The labels A, B
and C describe particular gate schedulings. Stabilizers with white vertices
encode the parity of the logical $Z\otimes Z$ measurement. The rightmost
figure illustrates a logical $Y\otimes Y$ measurement implemented by lattice
surgery. As explained in Appendix C, the $Y\otimes Y$ measurement can be done
directly without first extending the logical patches so that logical $Y$
operators can be expressed along their respective horizontal boundaries. When
performing the gauge fixing step, weight-five stabilizers illustrated by
yellow plaquettes (referred to as twist defects) must be measured, in addition
to elongated $X$ and $Z$-type stabilizers. The measurements of both twist
defects and elongated stabilizers require the use two ancilla qubits prepared
in a GHZ state with the assumed hardware connectivity constraints described in
Section I. Lastly, we remark that in addition to the A and B gate schedules,
the $Y\otimes Y$ also requires the use of the C schedule.

##  II Lattice surgery with twist defects in the bulk

In this section, we describe our protocol for performing twist-based lattice
surgery. In Section II.1, we provide a gate scheduling that can be used to
measure an arbitrary number of Pauli $Y$ operators using twist defects in the
bulk. Fault-tolerant circuits for measuring stabilizers at twist defects are
provided in Appendix A. In Section II.2, we will then compare the performance
of a lattice surgery protocol for measuring $P=Y\otimes Y$ to a $P=Z\otimes Z$
protocol that does not require twist defects in the bulk. The Pauli $Z\otimes
Z$ is chosen for comparison since the measurement of both $Y\otimes Y$ and
$Z\otimes Z$ require domain walls between the logical patches and the routing
space. In what follows, the surface code encoding a logical qubit will be
referred to as a logical patch. The extra space required to perform lattice
surgery will be referred to as the routing space.

###  II.1 Gate scheduling for twist-based lattice surgery

Recall that in a lattice surgery protocol, mutli-qubit Pauli measurements
between logical patches are performed by measuring a set of operators in the
routing space between the logical patches. Such measurements (which correspond
to gauge fixing [12]) merge the logical patches into one large surface code
patch, and a subset of the stabilizers of the merged patch encode the parity
of the logical multi-qubit Pauli measurement. A simple example for a $Z\otimes
Z$ and $Y\otimes Y$ measurement is provided in Fig. 2.

Figure 3: Lattice and valid gate scheduling for measuring the multi-qubit
Pauli operator $P=Y\otimes Y\otimes Y\otimes Y$ via lattice surgery. The A, B
and C gate schedules are described in Fig. 2. The chosen gate scheduling
imposes the need for different ancilla states used to measure twist defects on
the left strip compared to twist defects on the right strip. More details are
provided in Appendix A.

Let $P=P_{1}\otimes P_{2}\otimes\cdots\otimes P_{k}$ be a multi-qubit Pauli
operator that is to be measured using a lattice surgery protocol. If
$P_{j}\in\\{X,Z\\}$ for all $j\in\\{1,\cdots,k\\}$, then the standard surface
code gate scheduling can be used to measure all the stabilizers during the
lattice surgery protocol [23]. For instance, see the scheduling used for a
logical $Z\otimes Z$ measurement performed by lattice surgery in Fig. 2. With
such a scheduling, all two-qubit gates can be applied in four time steps thus
minimizing the number of idling qubit locations. One of the important features
of the standard surface code gate scheduling circuits is that a weight-two
error arising from a single fault will be perpendicular to the relevant
logical operator thus preserving the surface code distance (i.e. the code will
be guaranteed to correct any error arising from at most $(d-1)/2$ faults). By
relevant logical operator, we mean that if the weight-two data-qubit error
arising from a single fault is of the form $E_{X}=X_{q_{1}}\otimes X_{q_{2}}$
and the minimum-weight representatives of $X_{L}$ form vertical strings, then
$E_{X}$ will have support along horizontal strings. Similarly, $E_{Z}$ will
have support along vertical strings since the minimum-weight representatives
of $Z_{L}$ form horizontal strings.

Now suppose there exists at least one $j\in\\{1,\cdots,k\\}$ such that
$P_{j}=Y$. In Fig.2d of Ref [14], Litinski proposed measuring the $Y$
operators as follows. First, logical patches are extended using qubits in the
routing space such that the logical $Y_{L}$ operator of the logical patch can
be expressed along a horizontal boundary. The logical $Y$ operator is then
given by

$Y=Z_{q_{1}}\otimes Z_{q_{2}}\otimes\cdots\otimes X_{q_{d_{z}-1}}\otimes
Y_{q_{d_{z}}}\otimes X_{q_{d_{z}+1}}\otimes\cdots\otimes X_{q_{d_{z}+d_{x}}}$
(1)

where $d_{x}$ and $d_{z}$ are the minimum weights of the logical $X$ and $Z$
operators of the logical patch. The $Y$ operator can then be measured via
gauge fixing by performing $Z$ and $X$-type stabilizer measurements between
the extended logical patch and qubits in the routing space. The gauge-fixing
step requires the measurement of mixed $X\otimes X\otimes Z\otimes Z$
stabilizers which we refer to as domain walls. In addition, it requires the
measurement of a weight-five operator operator containing a physical $Y$ term.
Such weight-five operators are referred to as twist defects. An important
feature of our scheme is that when measuring multi-qubit Pauli’s involving $Y$
operators, such measurements can be done directly, without first extending the
logical patches. Using an extension step doubles the implementation time and
uses additional routing space, thus making our direct approach more efficient.
Further, we show in Appendix C that our direct approach for measuring Pauli
$Y$ operators is fault-tolerant using the gauge fixing formalism of Ref. [12].

The presence of twist defects reduces the set of gate scheduling solutions
that can be used for a twist-based lattice surgery protocol with minimal
circuit depth. A valid gate scheduling for the measurement of $P=Y\otimes Y$
via lattice surgery is shown in Fig. 2. The chosen gate scheduling ensures
that all two-qubit gates can be applied in four time steps. Three different
gate schedules are used, which are labelled A, B and C. The C schedule is only
used in the routing space to the right of the twist defects. Note that the A,
B and C schedules must follow a set of rules for how they can be tilled on the
lattice in order to avoid scheduling conflicts or invalid schedules for
performing the stabilizer measurements111A valid schedule is one where all
stabilizers are guaranteed to be measured as $+1$ in the absence of faults.
Further, if an error anticommutes with a stabilizer $g$, then $g$ is
guaranteed to be measured as $-1$.. For instance, a stabilizer measured using
an A schedule cannot be adjacent to a stabilizer measured using a C schedule
in the horizontal direction. If they were, qubits shared by both stabilizers
would interact with two-qubit gates in the same time steps. On the other hand,
C and A schedules can be adjacent to each other in the vertical direction (see
the legend at the bottom of Fig. 2).

Figure 4: Example layout of 16 logical patches with routing overhead used for
performing arbitrary multi-qubit Pauli measurements via lattice surgery. In
the top figure, we illustrate the logical patches prior to performing the
Pauli measurements. We illustrate 4 unit cells, with each unit cell (shown
with a dashed line) containing 4 surface code patches and some routing space.
Some additional edge padding (shown in green) is also need for routing space.
In the bottom figure, we illustrate the merged patch that is obtained after
measuring a logical $Y\otimes Y\otimes X\otimes Y\otimes X\otimes Z$ Pauli
operator. The gate scheduling presented in Fig. 3 can be used for performing
the three $Y$ measurements.

Unlike the standard surface code gate scheduling where all $X$-type
stabilizers use the A schedule and $Z$-type stabilizers use the B schedule (or
vice-versa), the gate scheduling for measuring $Y\otimes Y$ includes some
regions where the A schedule is applied uniformly. Consequently, there will be
single failures resulting in weight-two data qubit errors which are parallel
to the logical $X_{L}$ or $Z_{L}$ operators of the merged patch. For a given
quantum algorithm, the $d_{x}$ and $d_{z}$ distances of logical patches are
chosen such that a single logical data qubit error is very unlikely during the
course of the entire computation. It is important to note that the merged
lattices of a twist-based protocol with distances $d_{x}^{\prime}$ and
$d_{z}^{\prime}$ for measuring $Y$ operators will have $d_{x}^{\prime}\geq
d_{x}$ and $d_{z}^{\prime}\geq d_{z}$ . In other words, the distances of the
merged patches will be larger than the distances required for the logical
patches prior to the merged. Therefore, even though our gate scheduling has
the property that some weight-two errors arising from single failures will be
parallel to $X_{L}$ or $Z_{L}$ logical operators, the increased effective
distances during lattice surgery protocols will ensure that $d_{x}$ and
$d_{z}$ distances of the un-merged logical patches remain unchanged when
performing twist-based lattice surgery, which we observe numerically. There
are, however, some subtleties when performing twist-based lattice surgery that
affect the minimum required value of $d_{x}$ (see Appendix B for details).

We now provide a generalization of the gate scheduling shown in Fig. 2 used
for twist-based lattice surgery. In Fig. 3, we illustrate the gate scheduling
required to measure the logical Pauli operator $P=Y\otimes Y\otimes Y\otimes
Y$. The inclusion of a second pair of $Y$ operators has the feature that all
stabilizers of the merged patch in the routing space between the four twist
defects are measured using the C schedule. As was the case in Fig. 2, the
presence of twist defects requires the measurement of elongated stabilizers
along vertical strips located between the twist defects in the routing space.
In order to respect the nearest neighbor connectivity constraints imposed by
many quantum hardware architectures, additional ancilla qubits need to be used
to measure the elongated stabilizers and weight-five operators. However, an
important feature of the circuit in Fig. 3 is that the gate scheduling imposes
the need for different syndrome measurement circuits for the twist defects on
the left strip compared to those on the right strip. More details are provided
in Appendix A with the circuits shown in Fig. 7.

We remark that the gate scheduling shown in Fig. 3 can be extended to measure
arbitrary multi-qubit Pauli operators such as the one shown in Fig. 4. In
particular, Fig. 4 provides the minimal routing space requirements to perform
arbitrary multi-qubit Pauli measurements for logical patches placed on a two-
dimensional grid with qubits afflicted by a biased noise model. We assess the
routing overhead by considering an individual unit cell of 4 logical patches
shown in Fig. 4. Each unit cell uses $8d_{x}d_{z}$ physical qubits (which
includes yellow and grey vertices) for the four logical patches and contains a
total of $2(3d_{x}+2)(2d_{z}+d_{x}+4)$ physical qubits. The factor $3d_{x}+2$
is the height of the unit cell. The factor $2d_{z}+d_{x}+4$ is the width of
the unit cell. Note with the width factor needs $2(d_{z}+1)$ to account for
the two patches and $d_{x}+2$ for the routing space between patches. It
suffices to use a distance proportional to $d_{x}$ (rather than $d_{z}$)
because when merging our lattice surgery patches, the effective distance is
maintained. This leads to a multiplicative routing overhead of

$\displaystyle
O_{(d_{z},d_{x})}=\frac{2(3d_{x}+2)(2d_{z}+d_{x}+4)}{8d_{x}d_{z}}\approx\frac{3}{2}.$
(2)

where the approximation holds for large asymmetric codes $d_{z}\gg d_{x}\gg
4$. Eq. 2 corresponds to the asymptotic routing overhead since there is extra
routing space required shown as green edge padding in Fig. 4. However, the
cost of edge padding (as a fraction of total costs) vanishes with the number
of logical qubits. The routing overhead can be reduced further if not every
logical qubit is ready to participate in lattice surgery (e.g. see the core-
cache model of Ref. [17]).

###  II.2 Performance comparison between twist-based and twist-free lattice
surgery

Suppose we wish to measure a multi-qubit Pauli operator $P$ using lattice
surgery. The parity of the multi-qubit Pauli measurement is given by a product
of stabilizers in the routing space. For instance, for the $P=Y\otimes
Y\otimes Y\otimes Y$ measurement in Fig. 3, the parity of the measurement is
given by the product of all $X$-type stabilizers and twist defects in the
routing space, in addition to domain wall stabilizers with the $X$-component
of the operator incident to the routing space. In what follows, we will refer
to timelike failures as a collection of failure mechanisms which can result in
the wrong parity outcome of a multi-qubit Pauli measurement implemented via
lattice surgery. A logical timelike failure occurs when the incorrect parity
of a multi-qubit Pauli is obtained after performing error correction over the
full syndrome history of a lattice surgery protocol.

Due to timelike failures in addition to spacelike failures resulting in data
qubit errors which anticommute with $P$, the measurement of stabilizers in the
routing space needs to be repeated $d_{m}$ times where $d_{m}$ is determined
from the noise model and size of the computation. In particular, in a Pauli-
based computation requiring the measurement of multi-qubit Pauli operators
$\\{P_{1},\cdots,P_{\mu}\\}$, in Ref.[17] it was shown that $d_{m}$ can be
chosen to satisfy $\mu La(bp)^{(d_{m}+1)/2}\leq\delta$ where we require each
multi-qubit Pauli measurement to fail with probability no greater than
$\delta$. Here $L$ is the worst case area of the routing space used for
lattice surgery, $\\{a,b\\}$ are constants and $p$ quantifies the failure
probability of all physical operations on the qubits.

The goal of this section is to quantify the relative performance of twist-
based lattice surgery to a lattice surgery protocol free of twist defects.
Such a comparison will allow us to quantify the extra algorithm runtime costs
associated with twist defects. In particular, the weight-five stabilizers and
elongated stabilizers have more fault locations compared to the weight-four
stabilizers of the surface code and will thus make timelike failures more
likely when measuring multi-qubit Pauli operators containing $Y$ terms. In
performing the comparison, we use the following biased circuit-level
depolarizing noise model

  1. 1.

Each single-qubit gate location is followed by a Pauli $Z$ error with
probability $\frac{p}{3}$ and Pauli $X$ and $Y$ errors each with probability
$\frac{p}{3\eta}$.

  2. 2.

Each two-qubit gate is followed by a $\\{Z\otimes I,I\otimes Z,Z\otimes Z\\}$
error with probability $p/15$ each, and a $\\{X\otimes I,I\otimes X,X\otimes
X,Z\otimes X,Y\otimes I,Y\otimes X,I\otimes Y,Y\otimes Z,X\otimes Z,Z\otimes
Y,X\otimes Y,Y\otimes Y\\}$ each with probability $\frac{p}{15\eta}$.

  3. 3.

With probability $\frac{2p}{3\eta}$, the preparation of the $|{0}\rangle$
state is replaced by $|{1}\rangle=X|{0}\rangle$. Similarly, with probability
$\frac{2p}{3}$, the preparation of the $|{+}\rangle$ state is replaced by
$|{-}\rangle=Z|{+}\rangle$.

  4. 4.

With probability $\frac{2p}{3\eta}$, a single-qubit $Z$ basis measurement
outcome is flipped. With probability $\frac{2p\alpha}{3}$, a single-qubit
$X$-basis measurement outcome is flipped.

  5. 5.

Lastly, each idle gate location is followed by a Pauli $Z$ with probability
$\frac{p}{3}$, and a $\\{X,Y\\}$ error each with probability
$\frac{p}{3\eta}$.

In performing our simulations, we consider two regimes for $X$-basis
measurement errors. The first is for $\alpha=1$ and the second is for
$\alpha=10$. All simulations are performed using $\eta=100$, so that $Z$
errors are one hundred times more likely than $X$ and $Y$ errors. In what
follows, we use a MWPM algorithm [24] on graphs with weighted edges to correct
errors arising on the logical patches and in the routing space during a
lattice surgery protocol. In particular, we use the decoding algorithm
described in Section III of Ref.[17].

Figure 5: Plot of the timelike logical failure rates of a $Y\otimes Y$
measurement implemented by lattice surgery with twist defects for various
values of $d_{z}$, $d_{m}$ and $r_{s}$ with $\alpha=10$. The results are
obtained by preforming $10^{7}$ Monte Carlo simulations using the noise model
described in Section II.2. The solid lines correspond to the best fit
polynomial of Eq. 6. Our fits closely match the data for physical error rates
$p\lesssim 7\times 10^{-3}$. Larger values of $p$ require the inclusion of
higher order contributions to the polynomials in Eqs. 3 and 4.

(a)  (b)

Figure 6:  (a) Ratio of $d^{(\alpha)}_{m}(Y)/d^{(\alpha)}_{m}(Z)$ for
$\alpha=10$ and various values of the target logical error rate $\delta$ such
that both $P^{(YY)}_{L;\alpha}(p)\leq\delta$ and
$P^{(ZZ)}_{L;\alpha}(p)\leq\delta$. The area of the routing space of the
$Z\otimes Z$ measurement is taken to be identical to that of the $Y\otimes Y$
measurement. (b) Same as (a) but with $\alpha=1$. All values were obtained by
fixing $r_{s}=d_{x}=7$ and $d_{z}=31$. For large $d_{z}$, the results have
very little senstivity to the chosen values of $d_{x}$, $d_{z}$ and $r_{s}$.

For the twist-free simulation of lattice surgery, we consider a
$P_{1}=Z\otimes Z$ measurement due to the presence of domain walls at the
boundaries of the logical patches and routing space. To gain some intuition on
the expected scaling of the timelike logical failure rate (i.e. failures which
result in the wrong interpretation of the parity of the $P_{1}$ measurement),
suppose that the stabilizers of the merged patch for measuring $Z\otimes Z$
via lattice surgery are measured $d_{m}$ times. Suppose further that starting
in the first syndrome measurement round of the merged patch, a string of
$(d_{m}+1)/2$ consecutive measurement errors occur on one of the stabilizers
in the routing space encoding the parity of the $Z\otimes Z$ measurement.
Since the series of measurement errors begin in the first round, the inferred
parity of the $P_{1}$ will be incorrect. Further, the minimum-weight path
connecting the highlighted vertices222A vertex $v^{(k)}_{j}$ of the matching
graph used to perform MWPM encodes the parity of the measurement outcome of a
given stabilizer $g_{j}$ in round $k$. The vertex $v^{(k)}_{j}$ is highlighted
if the measurement outcome of $g_{j}$ changes between consecutive syndrome
measurement rounds $k-1$ and $k$. will not pass through the parity vertices in
the first syndrome round thus resulting in a logical timelike failure (see
Ref.[17] for more details). Additionally, the number of fault locations where
timelike failures can occur is proportional to the area of the qubits in the
routing space. As such, we propose the following ansatz for the timelike
logical failure rate of a $Z\otimes Z$ measurement:

$\displaystyle P^{ZZ}_{L}(p)=a_{1}r_{s}dz(b_{1}p)^{(d_{m}+1)/2},$ (3)

where $d_{z}r_{s}$ is the area of the routing space between the two domain
walls (see Fig. 2), and $\\{a_{1},b_{1}\\}$ are constants.

For the measurement of the operator $P_{2}=Y\otimes Y$, we expect a similar
scaling to the one provided in Eq. 3. However, as can be seen in Figs. 2 and
3, measuring logical $Y$ operators using twist defects results in narrow
vertical strips of length $r_{s}$ which contain elongated stabilizers. Given
the extra fault locations of both twist defects and elongated stabilizers, we
consider the following ansatz for timelike logical failures

$\displaystyle P^{YY}_{L}(p)=P^{ZZ}_{L}(p)+a_{2}r_{s}(b_{2}p)^{(d_{m}+1)/2}.$
(4)

In Eq. 4, $P^{ZZ}_{L}(p)$ is given by Eq. 3 with $r_{s}dz$ replaced by the
area of the routing space used for the $Y\otimes Y$ measurement. In other
words, the additional “cost” of performing twist-based lattice surgery is an
additive error contribution proportional to the height $r_{s}$ containing
twist defects and elongated stabilizers. For a multi-qubit Pauli measurement
$P=P_{1}\otimes P_{2}\otimes\cdots\otimes P_{k}$ containing $t\leq k$ $Y$
terms, we expect the timelike failure probability to scale as

$\displaystyle
P^{P}_{L}(p)=P^{\tilde{P}}_{L}(p)+ta_{2}r_{s}(b_{2}p)^{(d_{m}+1)/2},$ (5)

for some constants $\\{a_{2},b_{2}\\}$ where $\tilde{P}=Z_{1}\otimes
Z_{2}\otimes\cdots\otimes Z_{k}$. In Eq. 5, we assume that the merged surface
code patch for the $P$ measurement has the same area as the merged surface
code patch for the $\tilde{P}$ measurement.

Performing full circuit-level simulations using the biased noise model and
decoding algorithm described above, we obtained the following best fit
polynomials describing the timelike logical failure rates using the ansatzes
of Eqs. 3 and 4

$\displaystyle P^{YY}_{L;\alpha=10}(p)=$ $\displaystyle
0.0365r_{s}(d_{x}+d_{z})(49.44p)^{(d_{m}+1)/2}$
$\displaystyle+0.0514r_{s}(88.145p)^{(d_{m}+1)/2},$ (6)

and

$\displaystyle P^{YY}_{L;\alpha=1}(p)=$ $\displaystyle
0.0162r_{s}(d_{x}+d_{z})(22.43p)^{(d_{m}+1)/2}$
$\displaystyle+0.0280r_{s}(36.345p)^{(d_{m}+1)/2}.$ (7)

The first term in Eqs. 6 and 7 can be used to extract the best fit polynomials
for $Z\otimes Z$ lattice surgery with a routing space area given by
$r_{s}(d_{x}+d_{z})$. In Fig. 5, we show how the polynomial in Eq. 6 fits the
data obtained from our Monte Carlo simulations for various values of $d_{z}$,
$d_{m}$ and $r_{s}$ (with fixed $d_{x}=7$).

Now suppose that we wish to implement a quantum algorithm so that all lattice
surgery operations fail with probability no more than $\delta$. Hence we must
have that $P^{(P)}_{L}\leq\delta$ which will fix the required value of $d_{m}$
for each multi-qubit Pauli measurement. Using the results of Eqs. 6 and 7, in
Fig. 6, we plot the ratios $d^{(\alpha)}_{m}(Y)/d_{m}^{(\alpha)}(Z)$ for
$\alpha=10$ and $\alpha=1$. Here $d^{(\alpha)}_{m}(Y)$ corresponds to the
minimum value of $d_{m}$ such that $P^{(YY)}_{L;\alpha}(p)\leq\delta$. Note
that in computing $d^{(\alpha)}_{m}(Y)$, the extension of the logical patch to
obtain a horizontal $Y$ boundary is done simultaneously with the gauge fixing
step as explained in Appendix C. As such, $d^{(\alpha)}_{m}(Y)$ counts all
syndrome measurement rounds from the gauge fixing step until the round when
the patches are split. Similarly, $d^{(\alpha)}_{m}(Z)$ corresponds to the
minimum value of $d_{m}$ such that $P^{(ZZ)}_{L;\alpha}(p)\leq\delta$ for a
lattice surgery patch where the routing space has the same area as the one
used for a $Y\otimes Y$ measurement. Hence, the ratio
$d^{(\alpha)}_{m}(Y)/d_{m}^{(\alpha)}(Z)$ allows us to quantify the extra
multiplicative time cost of measuring $Y\otimes Y$ via lattice surgery using
twist defects compared to a lattice surgery protocol for measuring $Z\otimes
Z$ which does not require the use of twist defects. A few remarks are in
order.

First, the ratio $d^{(\alpha)}_{m}(Y)/d_{m}^{(\alpha)}(Z)$ is highly
insensitive to the chosen values of $d_{x}$, $r_{s}$ and $d_{z}$. As such, the
plots in Fig. 6 were obtained by fixing $d_{z}=31$ and $d_{x}=r_{s}=7$. We
chose the value $d_{x}=7$ since for the biased noise model considered here, it
was shown in Ref.[17] that $d_{x}=7$ was sufficient to implement the Hubbard
model [25, 26] for lattice sizes $L\leq 32$.

Second, comparing the results in Fig. 6a to those in Fig. 6b, it can be seen
that higher measurement failure rates increase the runtime for performing
lattice surgery with twist defects. Further, for physical noise rates
$p\approx 10^{-3}$, the ratio $d^{(\alpha)}_{m}(Y)/d_{m}^{(\alpha)}(Z)\approx
1.2$ when $\alpha=10$. However, $d^{(\alpha)}_{m}(Y)/d_{m}^{(\alpha)}(Z)$
increases fairly quickly as $p$ approaches the $10^{-2}$ regime which is near
the threshold for logical timelike failures.

It can be seen in Fig. 6b that the ratio $d^{(1)}_{m}(Y)/d^{(1)}_{m}(Z)$ for
$p=10^{-3}$ increases when going from $\delta=10^{-15}$ to $\delta=10^{-10}$.
The absolute values of $d^{(1)}_{m}(Y)$ and $d^{(1)}_{m}(Z)$ are larger when
$\delta=10^{-15}$. However, for both values of $\delta$, we only require
$d^{(1)}_{m}(Y)=d^{(1)}_{m}(Z)+1$ to achieve the desired target logical
failure rates. As such, the fraction $d^{(1)}_{m}(Y)/d^{(1)}_{m}(Z)$ is larger
when the absolute values of $d^{(1)}_{m}(Y)$ and $d^{(1)}_{m}(Z)$ decrease.

Lastly, we remark that for multi-qubit Pauli measurements requiring more than
two $Y$ terms, the ratios $d^{(\alpha)}_{m}(Y)/d^{(\alpha)}_{m}(Z)$ obtained
in Fig. 6 would only increase in a meaningful way for very large values of $t$
when using the result of Eq. 5 due to the exponential scaling of the second
term. As such, for the noise rates considered in Fig. 6, there could be rare
cases where a multi-qubit Pauli measurement containing a very large number of
$Y$ terms would benefit from a twist-free approach such as the one considered
in [17].

##  III Conclusion

In Ref.[17], the twist-free scheme for measuring multi-qubit Pauli operators
containing $Y$ terms results in an approximately $2\times$ slowdown in
algorithm runtime due to the need to sequentially measure multi-qubit Pauli
operators containing pure $X$ terms, followed by a multi-qubit Pauli
measurement containing pure $Z$ terms. Our results thus suggest that, assuming
a hardware architecture satisfying the connectivity constraints described in
Fig. 1, twist-based lattice surgery will outperform the twist-free version for
physical noise rates $p\lesssim 5\cdot 10^{-3}$. However, for noise rates
close to the threshold value $\sim 10^{-2}$, we expect twist-free based
lattice surgery to achieve lower algorithm runtime relative to lattice surgery
protocols using twist defects to measure $Y$ operators. An open question is
whether high threshold surface code implementations are possible using
homogeneous architectures and less connectivity as was assumed in Fig. 1.

The above conclusions also depend on the noise model. For instance, comparing
Figs. 6a and 6b, it is clear that higher measurement failure rates results in
longer $Y\otimes Y$ measurements compared to $Z\otimes Z$ measurements with an
identical area. As such, for noise models where measurement and two-qubit gate
failures are very high relative to other failure mechanisms, runtimes of
twist-free lattice surgery protocols could potentially be smaller compared
twist-based lattice surgery protocols.

##  Appendix A Stabilizer measurement circuits for twist defects in the bulk

(a)  (b)

Figure 7:  (a) Circuit used to measure the weight-five stabilizers of the
twist defects located on the left vertical strip of Fig. 3. A GHZ state is
prepared, and the parity of the stabilizer measurement outcome is given by the
product of the two $X$-basis measurement outcomes. (b) Second type of circuit
used to measure the weight-five stabilizers of the twist defects located on
the right vertical strip in Fig. 3. In this case, the $X$-basis measurement
outcome gives the parity of the stabilizer measurement. A correction
$P_{1}^{m_{1}}$ (or equivalently $P_{2}^{m_{1}}$) is applied based on the
$m_{1}$ $Z$-basis measurement outcome. For both circuits, $P_{1}P_{2}$ is the
stabilizer being measured.

In this appendix, we describe the two types of circuits used to measure
elongated checks and the weight-five stabilizers corresponding to twist
defects on both the left and right vertical strips in the routing space of
Fig. 3. We presented one such example in Fig. 1 and here give a more general
procedure. Such circuits are shown in Figs. 7a and 7b, where
$|{\overline{\psi}}\rangle$ is the encoded state protecting the data during
lattice surgery. $P_{1}$ and $P_{2}$ are Pauli operators with $P_{1}P_{2}$
corresponding to the stabilizer being measured.

Figure 8:  In (a) and (b), we show two identical surface code patches obtained
after performing a $Y\otimes Y$ measurement by lattice surgery. The width of
both patches is $d_{x}+d_{z}$. (a) We consider a failure arising at the
controlled-$Y$ gate for measuring the top twist defect during the first
syndrome measurement round of the merged patch. The failure results in an
$X\otimes X$ error on two data qubits as shown in the figure. Since the
measurement of the twist defect is random during the first round of the merge,
and no changes are detected in subsequent rounds (assuming no other faults),
only the vertex corresponding to the blue $Z$-type stabilizer which anti-
commutes with the error is highlighted. (b) A weight-one $X$ error occurs on
the data qubit shown in the figure resulting in the same syndrome measurement
outcome as the one obtained in (a). Since both types of failures have the same
syndrome measurement outcome and are parallel to a logical $X$ operator of the
surface code patch, a single failure on this lattice can lead to a logical
fault. (c) Patch for measuring $Y\otimes Y$ with width $d_{x}+d_{z}+1$. The
patch uses extra padding to allow both leading order failures considered in
this example to have distinct syndromes. Such a setting thus requires the
logical patches to have width $d_{x}+1$ prior to performing lattice surgery.

Without loss of generality, assume the data qubits is in an eigenstate of
$P_{1}P_{2}$ so that
$P_{1}P_{2}|{\overline{\psi}}\rangle=\pm|{\overline{\psi}}\rangle$. For the
circuit in Fig. 7a, it is straightforward to show that the state prior to the
measurements is given by
$|{\psi}\rangle_{f}=(|{0,0}\rangle\pm|{1,1}\rangle)/\sqrt{2}|{\overline{\psi}}\rangle$.
The ancilla state $(|{0,0}\rangle\pm|{1,1}\rangle)/\sqrt{2}$ is a eigenstate
of $X\otimes X$ with eigenvalue $\pm 1$. As such, the product of the two
$X$-basis measurement outcomes of the ancilla qubits gives the stabilizer
measurement outcome.

For the circuit in Fig. 7b, the state prior to the measurement is given by

$\displaystyle|{\psi}\rangle_{f}=(|{0,0}\rangle+|{0,1}\rangle
P_{2}+|{1,0}\rangle P_{1}+|{1,1}\rangle P_{1}P_{2})|{\overline{\psi}}\rangle$
(8)

which we can express as

$\displaystyle|{\psi}\rangle_{f}$
$\displaystyle=|{0}\rangle(|{0}\rangle+|{1}\rangle
P_{1}P_{2})|{\overline{\psi}}\rangle+|{1}\rangle(|{0}\rangle P_{1}+|{1}\rangle
P_{2})|{\overline{\psi}}\rangle$
$\displaystyle=|{0}\rangle(|{0}\rangle+|{1}\rangle
P_{1}P_{2})|{\overline{\psi}}\rangle+P_{1}|{1}\rangle(|{0}\rangle+|{1}\rangle
P_{2})|{\overline{\psi}}\rangle$
$\displaystyle=|{0}\rangle|{\pm}\rangle|{\overline{\psi}}\rangle+P_{1}|{1}\rangle|{\pm}\rangle|{\overline{\psi}}\rangle$
(9)

Therefore, measuring the second ancilla qubit in the $X$ basis will reveal the
desired $\pm 1$ eigenvalue. However, we also have a $P_{1}$ Pauli correction
required depending on the value of the first ancilla qubit measured the $Z$
basis.

Lastly, we point out that using flag based methods [27, 28, 29, 30, 31, 32,
33, 34, 7, 35, 36, 37, 38, 39] to measure the elongated checks and weight-five
twist defects would require an extra two-qubit gate between the ancillas
instead of a single CNOT. As such, an extra idling time would be required
resulting in slower algorithm runtimes.

##  Appendix B Minimum distance requirement of twist-based lattice surgery

In this appendix, we show that twist-based lattice surgery protocols require
extra padding to correct arbitrary $X$ errors arising from $(d_{x}-1)/2$
failures.

An example of a weight-one $X$ error being indistinguishable from a weight-two
$X$ error (both arising from a single failure with probabilities proportional
to $p$) for a lattice surgery protocol measuring $Y\otimes Y$ is shown in Fig.
8. The lattices in Fig. 8(a) and (b) have width $d_{x}+d_{z}$ where $d_{x}=3$
and $d_{z}=9$. The lattice in Fig. 8(c) has extra padding making its width
$d_{x}+d_{z}+1$. For the figure containing the lattices of width
$d_{x}+d_{z}$, consider first the lattice in Fig. 8(a). A weight-two $X$ data
qubit error occurs during the first syndrome measurement round of the merged
patch (i.e. the first syndrome measurement round when gauge fixing) due to a
controlled-$Y$ gate failure used for measuring the top twist defect. The error
anticommutes with the weight-five yellow plaquette in addition to a blue
weight-four $Z$-type stabilizer. However, the measurement outcome of the
weight-five operator is random in the first round of the merge, and no change
in measurement outcomes are observed in subsequent syndrome measurement
rounds. As such, only the vertex associated with the weight-four $Z$-type
stabilizer in the first round of the merge is highlighted. The observed
syndrome measurement outcome is identical to the one that would be obtained if
a weight-one $X$ error, as shown in Fig. 8(b), occurred during the first round
of the merge. Since both a weight-one and weight-two $X$ errors result in the
same syndrome measurement history, and $d_{x}=3$, this example shows that a
single failure occurring during the first syndrome measurement round when
merging the surface code patches to measure $Y\otimes Y$ can lead to a logical
failure. However, by increasing the $d_{x}$ distance by one using extra
padding, as shown in Fig. 8(c), such failure mechanisms can be distinguished.

More generally, suppose we perform lattice surgery using twist defects to
measure $Y$ operators and the initial logical patches prior to the merge have
odd distance $d_{x}$. In such settings, fewer than $(d_{x}+1)/2$ failures
occurring during the first syndrome measurement round of the merged patch can
result in a logical $X$ error. To ensure that up to $(d_{x}+1)/2$ failures
never result in a logical failure, the logical patches can always be padded
with an extra column of stabilizers thus increasing their $d_{x}$ distance by
one. Depending on the noise bias and size of the quantum algorithm, the extra
padding might not be necessary. For instance, the simulations performed in
Section II.2 with a noise bias of $\eta=100$ used the odd distance $d_{x}=7$
which is sufficient for implementing the Hubbard model with lattice sizes
$L\leq 32$. Further, even though for odd distances $d_{x}$ the logical $X$
failure probability scales as $\binom{N}{(d_{x}-1)/2}p^{(d_{x}-1)/2}$, the
combinatorial coefficient $\binom{N}{(d_{x}-1)/2}$ is very small relative to
the combinatorial coefficient of higher order failure mechanisms since only
$(d_{x}-1)/2$ failures in the first round of the merged patch at very
specialized regions near the twist defects can lead to a logical failure.

Figure 9: Illustration showing an efficient protocol for measuring $Y\otimes
Y$ fault-tolerantly. In (a), we illustrate the stabilizers for the initial
configuration of the logical patches including single qubit $Z$ for
$|{0}\rangle$ states. In (b), we show the stabilizers of the merged patched
obtained via lattice surgery. In (c), we show the stabilizers of the sub-
system code that (a) and (b) can be regarded as a gauge fixing of.

##  Appendix C Fault tolerance proof

Given a rectangular logical patch, in Ref. [14] Litinski showed that the Pauli
$Y$ operator can be measured in several steps. We start with two separate
surface code patches, the patch to be measured and a $|{0_{L}}\rangle$
ancilla. The next step is to extend the patch by moving the corner to express
a minimum weight representative of the logical $Y$ operator along a straight
line. Afterwords, a twist defect is used to measure $Z\otimes Y$ with an
ancilla prepared in a logical $|{0}\rangle$ state. The last step implements
destructive measurements on qubits in the ancilla region in order to return to
the original code space. Litinski argued that the first and second steps
require $d$ rounds of error correction, and all other steps require
effectively zero time. We will refer to the second step as the extension step.
If the extension step is required for a single $Y$ logical measurement, it
would seem natural to prefer this for $Y\otimes Y$ and more general logical
measurements. However, the extension step effectively doubles the execution
time for lattice surgery and also demands additional routing space.

Here we argue that the extension step can be skipped while retaining all the
fault-tolerance properties of lattice surgery at the phenomenological level.
We borrow the gauge-fixing ideas of Ref. [12] and apply them to the example of
a $Y\otimes Y$ measurement as sketched in Fig. 9.

The initial state of Fig. 9(a) has some set of stabilizers
$\mathcal{S}_{\mathrm{old}}$ that includes all the stabilizer generators for
the two logical patches. Note the data qubits in the routing space prepared in
the $|{0}\rangle$ state. Unconventionally, but crucial to our proof, we regard
the $Z$ Pauli for each $|{0}\rangle$ qubit as being part of the stabilizer
$\mathcal{S}_{\mathrm{old}}$. This further allows us to choose an unusual
representative for the $Y_{L1}$ and $Y_{L2}$ logical operators (each differs
by a $Z$ from $\mathcal{S}_{\mathrm{old}}$ relative to the standard
representatives for $Y_{L1}$ and $Y_{L2}$).

The merged state of Fig. 9(b) illustrates the stabilizers
$\mathcal{S}_{\mathrm{new}}$ during the merge step (having skipped any
extension step). Multiplying the stabilizers with white vertices gives our
representative for $Y_{L1}\otimes Y_{L2}$ from the initial configuration and
therefore these lattice surgery operations do measure the desired logical
operator. If we had not included the single-qubit $Z$ operators in
$\mathcal{S}_{\mathrm{old}}$, we would not have measured $Y_{L1}\otimes
Y_{L2}$, so this is the key formal trick to prove fault-tolerance.

Lastly, Ref. [12] prescribes that we consider the sub-system code with
stabilizer
$\tilde{\mathcal{S}}=\mathcal{S}_{\mathrm{old}}\cap\mathcal{S}_{\mathrm{new}}$
and gauge group
$\tilde{\mathcal{G}}=\langle\mathcal{S}_{\mathrm{old}},\mathcal{S}_{\mathrm{new}}\rangle$.
The protocol is then (phenomenologically) fault-tolerant provided that this
sub-system code retains the distance of the initial code. We illustrate the
local generators for $\tilde{\mathcal{S}}$ in Fig. 9(c). The logical operators
for the sub-system code must commute with the stabilizer group and not be
contained in the gauge group. Examining Fig. 9(c) one finds that the code
distance is indeed maintained at $d_{z}$ for pure $Z$ errors and at least
$d_{x}$ for all other types of errors.

## References

  * Dennis  _et al._ [2002] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory, Journal of Mathematical Physics 43, 4452 (2002).
  * Fowler  _et al._ [2012] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Physical Review A 86, 032324 (2012).
  * Jochym-O’Connor and Laflamme [2014] T. Jochym-O’Connor and R. Laflamme, Using concatenated quantum codes for universal fault-tolerant quantum gates, Phys. Rev. Lett. 112, 010505 (2014).
  * Yoder  _et al._ [2016] T. J. Yoder, R. Takagi, and I. L. Chuang, Universal fault-tolerant gates on concatenated stabilizer codes, Phys. Rev. X 6, 031039 (2016).
  * Chamberland  _et al._ [2016] C. Chamberland, T. Jochym-O’Connor, and R. Laflamme, Thresholds for universal concatenated quantum codes, Phys. Rev. Lett. 117, 010501 (2016).
  * Chamberland  _et al._ [2017] C. Chamberland, T. Jochym-O’Connor, and R. Laflamme, Overhead analysis of universal concatenated quantum codes, Phys. Rev. A 95, 022313 (2017).
  * Chamberland  _et al._ [2020a] C. Chamberland, A. Kubica, T. J. Yoder, and G. Zhu, Triangular color codes on trivalent graphs with flag qubits, New Journal of Physics 22, 023019 (2020a).
  * Beverland  _et al._ [2021] M. E. Beverland, A. Kubica, and K. M. Svore, Cost of universality: A comparative study of the overhead of state distillation and code switching with color codes, PRX Quantum 2, 020341 (2021).
  * Raussendorf  _et al._ [2006] R. Raussendorf, J. Harrington, and K. Goyal, A fault-tolerant one-way quantum computer, Annals of Physics 321, 2242 (2006).
  * Horsman  _et al._ [2012] C. Horsman, A. G. Fowler, S. Devitt, and R. Van Meter, Surface code quantum computing by lattice surgery, New J. Phys. 14, 123011 (2012).
  * Litinski and Oppen [2018] D. Litinski and F. v. Oppen, Lattice Surgery with a Twist: Simplifying Clifford Gates of Surface Codes, Quantum 2, 62 (2018).
  * Vuillot  _et al._ [2019] C. Vuillot, L. Lao, B. Criger, C. G. Almudéver, K. Bertels, and B. M. Terhal, Code deformation and lattice surgery are gauge fixing, New J. Phys. 21, 033028 (2019).
  * Fowler and Gidney [2018] A. G. Fowler and C. Gidney, Low overhead quantum computation using lattice surgery, arXiv preprint arXiv:1808.06709 (2018).
  * Litinski [2019] D. Litinski, A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery, Quantum 3, 128 (2019).
  * Chamberland  _et al._ [2020b] C. Chamberland, K. Noh, P. Arrangoiz-Arriola, E. T. Campbell, C. T. Hann, J. Iverson, H. Putterman, T. C. Bohdanowicz, S. T. Flammia, A. Keller, G. Refael, J. Preskill, L. Jiang, A. H. Safavi-Naeini, O. Painter, and F. G.S.L. Brandao, Building a fault-tolerant quantum computer using concatenated cat codes, arXiv preprint arXiv:2012.04108 (2020b).
  * Yoder and Kim [2017] T. J. Yoder and I. H. Kim, The surface code with a twist, Quantum 1, 2 (2017).
  * Chamberland and Campbell [2021] C. Chamberland and E. T. Campbell, Universal quantum computing with twist-free and temporally encoded lattice surgery, arXiv e-prints (2021), arXiv:2109.02746 .
  * Tuckett  _et al._ [2019] D. K. Tuckett, A. S. Darmawan, C. T. Chubb, S. Bravyi, S. D. Bartlett, and S. T. Flammia, Tailoring surface codes for highly biased noise, Phys. Rev. X 9, 041031 (2019).
  * Bonilla Ataides  _et al._ [2021] J. P. Bonilla Ataides, D. K. Tuckett, S. D. Bartlett, S. T. Flammia, and B. J. Brown, The XZZX surface code, Nature Communications 12, 2172 (2021).
  * Tuckett  _et al._ [2020] D. K. Tuckett, S. D. Bartlett, S. T. Flammia, and B. J. Brown, Fault-tolerant thresholds for the surface code in excess of $5\%$ under biased noise, Phys. Rev. Lett. 124, 130501 (2020).
  * Darmawan  _et al._ [2021] A. S. Darmawan, B. J. Brown, A. L. Grimsmo, D. K. Tuckett, and S. Puri, Practical quantum error correction with the XZZX code and Kerr-cat qubits, arXiv e-prints (2021), 2104.09539 [quant-ph] .
  * Higgott and Breuckmann [2021] O. Higgott and N. P. Breuckmann, Subsystem codes with high thresholds by gauge fixing and reduced qubit overhead, Phys. Rev. X 11, 031039 (2021).
  * Tomita and Svore [2014] Y. Tomita and K. M. Svore, Low-distance surface codes under realistic quantum noise, Phys. Rev. A 90, 062320 (2014).
  * Edmonds [1965] J. Edmonds, Paths, trees, and flowers, Canadian Journal of mathematics 17, 449 (1965).
  * Hubbard [1963] J. Hubbard, Electron correlations in narrow energy bands, Proc. R. Soc. Lond. , A276238–257 (1963).
  * Campbell [2021] E. T. Campbell, Early fault-tolerant simulations of the hubbard model, Quantum Science and Technology 7, 015007 (2021).
  * Chao and Reichardt [2018a] R. Chao and B. W. Reichardt, Quantum error correction with only two extra qubits, Phys. Rev. Lett. 121, 050502 (2018a).
  * Chao and Reichardt [2018b] R. Chao and B. W. Reichardt, ault-tolerant quantum computation with few qubits, npj Quantum Information 4, 2056 (2018b).
  * Chamberland and Beverland [2018] C. Chamberland and M. E. Beverland, Flag fault-tolerant error correction with arbitrary distance codes, Quantum 2, 53 (2018).
  * Tansuwannont  _et al._ [2020] T. Tansuwannont, C. Chamberland, and D. Leung, Flag fault-tolerant error correction, measurement, and quantum computation for cyclic calderbank-shor-steane codes, Phys. Rev. A 101, 012342 (2020).
  * Reichardt [2020] B. W. Reichardt, Quantum Sci. Technol. 6, 015007 (2020).
  * Chamberland and Cross [2019] C. Chamberland and A. W. Cross, Fault-tolerant magic state preparation with flag qubits, Quantum 3, 143 (2019).
  * Chamberland and Noh [2020] C. Chamberland and K. Noh, Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits, npj Quantum Information 6, 91 (2020).
  * Chamberland  _et al._ [2020c] C. Chamberland, G. Zhu, T. J. Yoder, J. B. Hertzberg, and A. W. Cross, Topological and subsystem codes on low-degree graphs with flag qubits, Phys. Rev. X 10, 011022 (2020c).
  * Chao and Reichardt [2020] R. Chao and B. W. Reichardt, Flag fault-tolerant error correction for any stabilizer code, PRX Quantum 1, 010302 (2020).
  * Tansuwannont and Leung [2021] T. Tansuwannont and D. Leung, Fault-tolerant quantum error correction using error weight parities, Phys. Rev. A 104, 042410 (2021).
  * Prabhu and Reichardt [2021] P. Prabhu and B. W. Reichardt, Fault-tolerant syndrome extraction and cat state preparation with fewer qubits, arXiv e-prints , arXiv:2108.02184 (2021).
  * Postler  _et al._ [2021] L. Postler, S. Heußen, I. Pogorelov, M. Rispler, T. Feldker, M. Meth, C. D. Marciniak, R. Stricker, M. Ringbauer, R. Blatt, P. Schindler, M. Müller, and T. Monz, Demonstration of fault-tolerant universal quantum gate operations, arXiv e-prints , arXiv:2111.12654 (2021).
  * Tansuwannont and Leung [2021] T. Tansuwannont and D. Leung, Achieving fault tolerance on capped color codes with few ancillas, arXiv e-prints , arXiv:2106.02649 (2021).