# Neural Grapheme-to-Phoneme Conversion with Pre-trained Grapheme Models

###### Abstract

Neural network models have achieved state-of-the-art performance on grapheme-
to-phoneme (G2P) conversion. However, their performance relies on large-scale
pronunciation dictionaries, which may not be available for a lot of languages.
Inspired by the success of the pre-trained language model BERT, this paper
proposes a pre-trained grapheme model called grapheme BERT (GBERT), which is
built by self-supervised training on a large, language-specific word list with
only grapheme information. Furthermore, two approaches are developed to
incorporate GBERT into the state-of-the-art Transformer-based G2P model, i.e.,
fine-tuning GBERT or fusing GBERT into the Transformer model by attention.
Experimental results on the Dutch, Serbo-Croatian, Bulgarian and Korean
datasets of the SIGMORPHON 2021 G2P task confirm the effectiveness of our
GBERT-based G2P models under both medium-resource and low-resource data
conditions.

Index Terms—  grapheme-to-phoneme conversion, pre-trained grapheme model,
self-supervised training, Transformer

##  1 Introduction

The grapheme-to-phoneme (G2P) conversion task is predicting the pronunciation
of words from their spellings. Considering that a pronunciation dictionary can
never cover all possible words in a language, G2P conversion is essential for
any applications that depend on the mapping relationship between the spoken
and written forms of a language, such as TTS and ASR [1, 2, 3].

Many studies have been conducted on G2P conversion. In early years, joint
n-gram models [4], joint sequence models [5] and wFST [6] were proposed.
Recently, neural networks such as LSTM [7] and Transformer [8] have showed
powerful ability on G2P conversion. The Transformer-based models have achieved
state-of-the-art performance in many benchmarks [8, 9]. Some imitation
learning based methods [10] also achieved comparable performance to the
Transformer model. Nevertheless, building neural G2P models usually relies on
a large, language-specific pronunciation dictionary, which may not be
available for a lot of languages. One approach to address this issue is cross-
lingual modeling. An early work is a wFST-based system [11]. Subsequently,
multilingual neural networks [12] and pre-trained G2P models of high-resource
languages [13] showed better cross-lingual G2P modeling ability. Another
approach is utilizing multimodal data. Route et al. [14] found that additional
audio supervision can help the G2P model to learn a more optimal intermediate
representation of graphemes. However, these studies mainly focused on
utilizing the data resources of other languages or other modals to improve the
performance of limited-resource G2P conversion, which do not explore better
grapheme representations for G2P in an unsupervised way.

Therefore, this paper proposes a pre-trained grapheme model named grapheme
BERT (GBERT) to improve the Transformer-based G2P model. The design of GBERT
is inspired by the language model BERT [15], which provides contextual word
representations and has achieved great successes in various NLP tasks, such as
machine translation [16] and text summarization [17]. Similarly, GBERT is
designed to capture the contextual relationship among the graphemes in a word,
which is essential for the G2P task since the same grapheme may have different
pronunciations due to different contexts. Following BERT, GBERT is a multi-
layer Transformer encoder and is pre-trained by self-supervised learning on a
large, language-specific word list with only grapheme information. The pre-
training task of GBERT is a masked grapheme prediction task, i.e, predicting
the masked graphemes from the seen graphemes in a word. Furthermore, two
approaches are developed to improve the Transformer-based G2P model with
GBERT. They are fine-tuning GBERT and fusing GBERT into the Transformer model
by attention [16]. Experiments were conducted on the Dutch, Serbo-Croatian,
Bulgarian and Korean datasets of the SIGMORPHON 2021 G2P task [18]. The
results show that fusing GBERT by attention can reduce the word error rate
(WER) and phone error rate (PER) of G2P under a medium-resource condition,
while fine-tuning GBERT is effective for most languages under a low-resource
condition. It should be noted that a concurrent work T5G2P [19] also mentions
the pre-trained grapheme model can help the G2P conversion. The difference is
that the T5G2P uses an encoder-decoder framework which captures contextual
relationship between graphemes and autoregressive information of graphemes in
the pre-training stage and only uses a directly fine-tuning method.

Fig. 2: The architecture of GBERT-fused model, which fuses GBERT into the
Transformer-based G2P model and is adapted from [16]. Fig. 1: The masked
grapheme prediction task for pre-training GBERT. Here is an example of the
English word _drollery_. The ``_'' denotes the mask token.

##  2 Proposed Method

In this section, we first introduce our proposed pre-trained grapheme model
GBERT in Section 2.1. Then, we show the details of fine-tuning GBERT for G2P
in Section 2.2 and the details of fusing GBERT into the Transformer-based G2P
model [16] in Section 2.3.

###  2.1 Grapheme BERT (GBERT)

Following BERT [15], the model architecture of GBERT is a multi-layer
bidirectional Transformer encoder where each input token can see all input
tokens. GBERT differs from BERT in that the input to GBERT is the grapheme
sequence in a single word while the input to BERT is the wordpiece sequence in
a single sentence or two sentences. The two-sentence input of BERT is designed
to cope with the downstream tasks based on sentence pairs. However, this paper
focuses on the single-word G2P task and thus we only consider the grapheme
seqeunces in single words.

GBERT is pre-trained using a masked grapheme prediction task, i.e., masking
some percentage of the input graphemes at random and predicting those masked
graphemes from the seen ones. An illustration is shown in Fig. 1. These mask
inputs (``_'') are replaced by mask tokens (80% of the ratio), random
graphemes (10% of the ratio) or original graphemes (10% of the ratio) to
eliminate the mismatch between the pre-training task and the downstream G2P
task, i.e, the mask tokens will not be encountered in the G2P task.

###  2.2 Fine-tuning GBERT for G2P Conversion

Fine-tuning a pre-trained language model is a typical way to apply pre-trained
representations to downstream tasks. Since GBERT is a pre-trained Transformer
encoder while the vanilla Transformer includes an encoder and a decoder, fine-
tuning GBERT means that we replace the encoder in the vanilla Transformer with
GBERT and train the new model in an end-to-end manner. Moreover, Liu and
Lapata [17] found that using different learning rates for the pre-trained
encoder and the randomly initialized decoder can lead to better convergence.
We also leveraged this trick in our implementation.

###  2.3 Fusing GBERT into Transformer-based G2P Model

In addition to fine-tuning, another approach to integrate pre-trained language
models is utilizing them as feature extractors, which may work better than the
fine-tuning approach when the downstream tasks can not be easily represented
by a Transformer encoder architecture [15]. One example is the BERT-fused
model [16], which adopts a multi-head attention [20] and a drop net to
adaptively control how each encoder and decoder layer of the vanilla
Transformer model interacts with the output features of BERT. Since this
method worked better than fine-tuning BERT and a naïve feature-based method in
the medium-resource machine translation task, it is adapted in this paper to
fuse GBERT into the Transformer-based G2P model, aiming to achieve better
results in the medium-resource G2P scenario. An illustration is shown in Fig.
2, where GBERT replaces the BERT in the original BERT-fused model [16].

As shown in Fig. 2, the GBERT-fused model consists of $L$ encoder layers and
$L$ decoder layers in addition to GBERT. For the $l$-th encoder layer, its
input includes the output of the $(l-1)$-th encoder layer (or the embeddings
of the grapheme sequence when $l=1$) as well as the contextual grapheme
representations provided by GBERT. For the $l$-th decoder layer, its input
includes the hidden states of the $(l-1)$-th decoder layer, the output of the
last encoder layer and the contextual grapheme representations of GBERT.
Specifically, in each encoder layer, an additional GBERT-Enc attention module
is added to the original Transformer encoder layer in order to adaptively
control how this layer interacts with the GBERT representations. In each
decoder layer, there is a similar GBERT-Dec attention module for a similar
purpose. Moreover, a drop net is used to regularize the network training,
outputting one of the two inputs or their average results during training and
outputting the average results during inference. More details can be found in
the original paper of the BERT-fused model [16].

Table 1: The four languages used in our experiments.

Language | Language Family | Script Type | Word Example
---|---|---|---
Dutch | Germanic | Latin | afnemer
Serbo-Croatian | South Slavic | Latin | buđenje
Bulgarian | East Slavic | Cyrillic | абоната
Korean | Koreanic | Hangul | 가치관

##  3 Experiments

###  3.1 Datasets

Experiments were conducted on the datasets of the SIGMORPHON 2021 G2P task
[18]. The four most difficult languages (i.e., the languages with the highest
word error rates) among all ten languages in the medium-resource subtask of
the SIGMORPHON 2021 task was chosen, according to the G2P performance of the
official baseline [21]. As listed in Table 1, they belong to different
language families and have different script types. In the official settings,
8000, 1000 and 1000 pronunciation records were used for training, validation
and test for each language. Following Elsaadany and Suter [22], Korean letters
were decomposed into single-sound letters with hangul-
jamo111https://github.com/jonghwanhyeon/hangul-jamo, e.g., 가감 $\rightarrow$ ㄱ
ㅏ ㄱ ㅏ ㅁ.

A _medium-resource_ G2P task and a _low-resource_ G2P task were designed based
on the datasets of these four languages. For the medium-resource task, the
training, validation and test sets were the same as the official settings. For
the low-resource task, we randomly sampled 1000 records from the original
training set to form a smaller training set for each language, and used the
original validation and test sets. Thus, the test set performance of these two
tasks can be compared directly.

In addition, the word list for each language was collected from WikiPron [23]
for GBERT pre-training. The words in the validation and test sets of the G2P
tasks were excluded and the final word lists for these four languages in Table
1 contained 27.0k, 35.0k, 43.1k, and 14.1k words respectively. For each
language, 90% of the words were used to train the monolingual GBERT and the
remaining 10% were used for validation.

Table 2: The WER and PER results (%) of different models on our medium-
resource and low-resource G2P tasks.

Model | Dutch | Serbo-Croatian | Bulgarian | Korean
---|---|---|---|---
WER | PER | WER | PER | WER | PER | WER | PER
_medium-resource_ |  |  |  |  |  |  |  |
IL [21] | 17.7 ± 1.3 | - | 38.9 ±1.2 | - | 19.7 ± 1.7 | - | 18.9 ± 0.8 | -
Transformer | 16.86 ± 0.14 | 3.49 ± 0.05 | 39.50 ± 0.71 | 7.94 ± 0.14 | 20.72 ± 2.70 | 3.84 ± 0.74 | 19.26 ± 0.48 | 3.39 ± 0.10
GBERT w/o fine-tuning | 19.98 ± 0.66 | 4.61 ± 0.48 | 43.92 ± 0.97 | 9.53 ± 0.75 | 23.24 ± 2.54 | 4.17 ± 0.40 | 23.06 ± 0.30 | 4.92 ± 0.15
GBERT fine-tuning | 16.18 ± 0.23 | 3.59 ± 0.39 | 39.08 ± 1.05 | 7.83 ± 0.21 | 18.88 ± 2.31 | 3.42 ± 0.33 | 19.80 ± 0.62 | 3.52 ± 0.12
GBERT attention | 15.86 ± 0.21 | 3.38 ± 0.07 | 37.64 ± 0.71 | 7.67 ± 0.20 | 18.60 ± 1.92 | 3.42 ± 0.34 | 17.94 ± 0.71 | 3.16 ± 0.13
_low-resource_ |  |  |  |  |  |  |  |
Transformer | 34.30 ± 0.66 | 9.39 ± 0.42 | 68.86 ± 1.08 | 15.41 ± 0.16 | 33.06 ± 1.90 | 6.07 ± 0.35 | 29.72 ± 0.77 | 6.79 ± 0.35
GBERT w/o fine-tuning | 34.56 ± 0.72 | 9.13 ± 0.60 | 69.70 ± 0.69 | 15.88 ± 0.65 | 41.87 ± 0.89 | 9.15 ± 0.88 | 42.76 ± 1.04 | 12.66 ± 0.29
GBERT fine-tuning | 28.96 ± 0.69 | 6.94 ± 0.61 | 63.12 ± 0.76 | 13.29 ± 0.57 | 30.86 ± 1.66 | 5.30 ± 0.36 | 32.78 ± 1.21 | 8.43 ± 0.11
GBERT attention | 35.28 ± 0.66 | 9.41 ± 0.33 | 68.14 ± 0.68 | 15.06 ± 0.29 | 31.98 ± 1.32 | 5.76 ± 0.35 | 29.78 ± 0.60 | 6.81 ± 0.30

###  3.2 Implementation

The GBERT for each language was a 6-layer Transformer encoder. Other
hyperparameters of GBERT followed previous work [22]. The ratio of masked
graphemes in a word was set as 20% for pre-training GBERT, which was higher
than the ratio of masked words (15%) in BERT since we expected enough masked
graphemes in short words. Our source code is released
222https://github.com/ldong1111/GraphemeBERT. Evaluating the pre-trained GBERT
models on the validation set of each language, the prediction accuracies of
the masked graphemes were 53.48%, 58.43%, 80.66% and 40.63%, respectively. We
can observe that they were all much higher than the accuracy of random
prediction ($\sim$ 2%), which shows the contextual relationship among
graphemes in a word.

Finally, we compared five models as follows.

  * •

Imitation learning (IL) [21] This baseline model adopted a neural transducer
[24] that operated over explicit edit actions with imitation learning, and
achieved similar performance to the Transformer model in the SIGMORPHON 2020
G2P task [10, 22]. We did not reimplement this model and just reported the
single-model results in the paper of IL model [21] on our medium-resource G2P
task.

  * •

Transformer This baseline model adopted a Transformer-based architecture [20]
and was implemented by us following previous work [22]. The model
hyperparameters were tuned for different tasks of different languages,
according to the performance on the validation set.

  * •

GBERT w/o fine-tuning This model followed the proposed method in Section 2.2
except that the parameters of GBERT were frozen when tuning other model
parameters.

  * •

GBERT fine-tuning This model followed the proposed method in Section 2.2. Like
previous work [17], different learning rates were used for the pre-trained
GBERT encoder and the randomly initialized Transformer decoder during fine-
tuning. Both learning rates were selected from 1e-3, 5e-4, 3e-4, 1e-4, 1e-5
based on the performance of the validation set for different tasks.

  * •

GBERT attention This model followed the proposed method in Section 2.3 and had
the same hyperparameters as the baseline Transformer model.

###  3.3 Evaluation Metrics

Word error rate (WER) and phoneme error rate (PER) were used as the evaluation
metrics in our experiments. WER is the percentage of words whose predicted
phoneme sequences were not identical to the gold references. PER is the sum of
the Levenshtein distance between the predicted and the reference phoneme
sequences, divided by the sum of the reference lengths on the test set. The
lower the WER and PER, the better the performance.

We conducted each experiment five times with different random seeds and
reported the mean and standard deviation of the five results for each model.
Note that the results of the IL model were quoted and 10 repetitions were used
by its authors [21]. Thus, its standard deviations can not be compared with
other models.

###  3.4 Results

Table 2 shows the WER and PER results of different models on our medium-
resource and low-resource G2P tasks. The Transformer baseline implemented by
us outperformed the IL baseline on the medium-resource task of Dutch, but was
not as good as IL on the other three languages. For the GBERT w/o fine-tuning
model, its performance was much worse than the Transformer baseline in almost
all experiments, especially for Korean. This indicates that the grapheme
representations derived from the pre-trained GBERT can not provide all the
necessary information for G2P conversion.

On the medium-resource G2P task, the GBERT fine-tuning model significantly
outperformed its counterpart without fine-tuning for all four languages, and
achieved lower WERs and PERs than the Transformer baseline for all languages
except Korean. The GBERT attention model obtained the lowest WERs and PERs
among all five models for all languages. All these results demonstrate the
effectiveness of our proposed methods of fine-tuning GBERT or fusing GBERT
into Transformer for the medium-resource G2P task. Although the GBERT
attention model also adopted GBERT as a feature extractor, just like the GBERT
w/o fine-tuning model, its advantage is that not only GBERT representations
but also the original input of the Transformer-based G2P model is utilized by
attention modules.

On the low-resource G2P task, the performance of all models decreased
significantly compared to the medium-resource scenario, indicating the
importance of training data amount to the state-of-the-art neural G2P models.
The GBERT fine-tuning model also outperformed the GBERT w/o fine-tuning model
for all four languages and outperformed the Transformer baseline for all
languages except Korean. However, the GBERT attention model performed better
than the Transformer baseline only for Serbo-Croatian and Bulgarian, and
performed not as good as the GBERT fine-tuning model for Dutch, Serbo-Croatian
and Bulgarian. These results show that the method of fusing GBERT into
Transformer may be more sensitive to the amount of training data than the
method of fine-tuning GBERT because the former has a more complex model
structure. The reason that our proposed method did not achieve satisfactory
performance for Korean on the low-resource G2P task may be that the mask
prediction accuracy of Korean was much lower than that of the other three
languages as shown in Section 3.2, i.e., the contextual relationship among
graphemes in Korean was weaker than that in the other three languages.

Table 3: The influence of the masked grapheme ratio for pre-training GBERT on
the performance of the GBERT attention model for the medium-resource Dutch G2P
task.

Mask Ratio (%) | Mask Accuracy (%) | WER (%) | PER (%)
---|---|---|---
15 | 53.01 | 16.34 ± 0.43 | 3.51 ± 0.08
20 | 53.48 | 15.86 ± 0.21 | 3.38 ± 0.07
30 | 51.32 | 15.88 ± 0.30 | 3.40 ± 0.08

An additional experiment was conducted to investigate the influence of the
masked grapheme ratio for pre-training GBERT on the performance of our
proposed methods. The GBERT attention model for the medium-resource Dutch G2P
task was taken as an example, and the results are shown in Table 3. We can
observe that the higher mask ratios (20% and 30%) achieved lower WER and PER
than the original ratio of 15% in BERT. One possible reason is that the
average number of graphemes in a word is much smaller than the average number
of words in a sentence and the grapheme space is much more compact than the
word space. Thus, low mask ratios may constrain the model from discovering the
contextual relationship among graphemes.

###  3.5 GBERT-based Transfer Learning For G2P Conversion

We also conducted an experiment to explore GBERT-based transfer learning,
where the G2P data of another high-resource language was used to improve the
performance of the low-resource G2P task. In this experiment, Dutch was
selected as the low-resource language and English was chosen as the high-
resource language since they belong to the same Germanic language family and
have the same Latin script type. The supervised training data of English
contained 33,344 word-pronunciation pairs from the high-resource subtask of
the SIGMORPHON 2021 task.

First, a bilingual GBERT was pre-trained by mixing 49.1k English words from
WikiPron and the Dutch word list mentioned in Section 3.1. Following a variant
of BERT [25], we added a language embedding to the input tokens of GBERT to
distinguish different languages. Then, neural G2P models were built using the
supervised training data of both English and Dutch. Following previous work
[22], the words prefixed with a language tag were used as model inputs. The
results of different models are shown in Table 4.

Table 4: The WER and PER results (%) of different models by transfer learning
with high-resource English G2P data on the low-resource Dutch G2P task.

Model | WER | PER
---|---|---
Transformer | 24.54 ± 0.53 | 5.09 ± 0.22
GBERT w/o fine-tuning | 33.30 ± 0.89 | 7.89 ± 0.25
GBERT fine-tuning | 23.42 ± 0.82 | 4.84 ± 0.16
GBERT attention | 23.36 ± 0.82 | 4.76 ± 0.25

Comparing Table 4 with the low-resource results in Table 2, we can see that
the WERs and PERs of all systems degraded significantly after transfer
learning. Different from the low-resource results in Table 2, the GBERT
attention model achieved the lowest WER and PER among all four models. This
indicates that the GBERT attention model can benefit from the increased
training data from similar high-resource languages, and our proposed GBERT-
based methods can also be combined with the transfer learning strategy to
obtain better performance.

##  4 Conclusion

In this paper, we have proposed a pre-trained grapheme model GBERT that
outputs contextual grapheme representations. The training of GBERT requires
only easily accessible word lists. In addition, two methods, namely fine-
tuning GBERT and fusing GBERT into Transformer, have been developed to enhance
the state-of-the-art Transformer-based G2P model with GBERT. Experiments on
the Dutch, Serbo-Croatian, Bulgarian and Korean datasets of the SIGMORPHON
2021 G2P task show that the method of fusing GBERT can reduce the WER and PER
of all languages on the medium-resource G2P task, while the method of fine-
tuning GBERT can improve the G2P performance of most languages on the low-
resource G2P task. In the future, we intend to improve the pre-trained
grapheme model by developing new architectures and loss functions, and
utilizing phrase-level or sentence-level training data.

## References

  * [1] Isaac Elias, Heiga Zen, Jonathan Shen, Yu Zhang, Ye Jia, Ron J Weiss, and Yonghui Wu,  ``Parallel tacotron: Non-autoregressive and controllable TTS,''  in ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2021, pp. 5709–5713.
  * [2] Changfeng Gao, Gaofeng Cheng, Runyan Yang, Han Zhu, Pengyuan Zhang, and Yonghong Yan,  ``Pre-training transformer decoder for end-to-end ASR model with unpaired text data,''  in ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2021, pp. 6543–6547.
  * [3] Ryo Masumura, Naoki Makishima, Mana Ihori, Akihiko Takashima, Tomohiro Tanaka, and Shota Orihashi,  ``Phoneme-to-Grapheme Conversion Based Large-Scale Pre-Training for End-to-End Automatic Speech Recognition,''  in Proc. Interspeech 2020, 2020, pp. 2822–2826.
  * [4] Lucian Galescu and James F Allen,  ``Pronunciation of proper names with a joint n-gram model for bi-directional grapheme-to-phoneme conversion,''  in Seventh International Conference on Spoken Language Processing, 2002.
  * [5] Maximilian Bisani and Hermann Ney,  ``Joint-sequence models for grapheme-to-phoneme conversion,''  Speech communication, vol. 50, no. 5, pp. 434–451, 2008.
  * [6] Josef R Novak, Nobuaki Minematsu, and Keikichi Hirose,  ``WFST-based grapheme-to-phoneme conversion: Open source tools for alignment, model-building and decoding,''  in Proceedings of the 10th International Workshop on Finite State Methods and Natural Language Processing, 2012, pp. 45–49.
  * [7] Shubham Toshniwal and Karen Livescu,  ``Jointly learning to align and convert graphemes to phonemes with neural attention models,''  in 2016 IEEE Spoken Language Technology Workshop (SLT). IEEE, 2016, pp. 76–82.
  * [8] Sevinj Yolchuyeva, Géza Németh, and Bálint Gyires-Tóth,  ``Transformer based grapheme-to-phoneme conversion,''  Proc. Interspeech 2019, pp. 2095–2099, 2019.
  * [9] Kyle Gorman, Lucas FE Ashby, Aaron Goyzueta, Arya D McCarthy, Shijie Wu, and Daniel You,  ``The SIGMORPHON 2020 shared task on multilingual grapheme-to-phoneme conversion,''  in Proceedings of the 17th SIGMORPHON Workshop on Computational Research in Phonetics, Phonology, and Morphology, 2020, pp. 40–50.
  * [10] Peter Makarov and Simon Clematide,  ``CLUZH at SIGMORPHON 2020 shared task on multilingual grapheme-to-phoneme conversion,''  Association for Computational Linguistics, 2020.
  * [11] Aliya Deri and Kevin Knight,  ``Grapheme-to-phoneme models for (almost) any language,''  in Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2016, pp. 399–408.
  * [12] Ben Peters, Jon Dehdari, and Josef van Genabith,  ``Massively multilingual neural grapheme-to-phoneme conversion,''  in Proceedings of the First Workshop on Building Linguistically Generalizable NLP Systems, 2017, pp. 19–26.
  * [13] Eric Engelhart, Mahsa Elyasi, and Gaurav Bharaj,  ``Grapheme-to-phoneme transformer model for transfer learning dialects,''  arXiv preprint arXiv:2104.04091, 2021.
  * [14] James Route, Steven Hillis, Isak Czeresnia Etinger, Han Zhang, and Alan W Black,  ``Multimodal, multilingual grapheme-to-phoneme conversion for low-resource languages,''  in Proceedings of the 2nd Workshop on Deep Learning Approaches for Low-Resource NLP (DeepLo 2019), 2019, pp. 192–201.
  * [15] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova,  ``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), 2019, pp. 4171–4186.
  * [16] Jinhua Zhu, Yingce Xia, Lijun Wu, Di He, Tao Qin, Wengang Zhou, Houqiang Li, and Tieyan Liu,  ``Incorporating BERT into neural machine translation,''  in International Conference on Learning Representations, 2019.
  * [17] Yang Liu and Mirella Lapata,  ``Text summarization with pretrained encoders,''  in EMNLP-IJCNLP, 2019, pp. 3730–3740.
  * [18] Lucas FE Ashby, Travis M Bartley, Simon Clematide, Luca Del Signore, Cameron Gibson, Kyle Gorman, Yeonju Lee-Sikka, Peter Makarov, Aidan Malanoski, Sean Miller, et al.,  ``Results of the second sigmorphon shared task on multilingual grapheme-to-phoneme conversion,''  in Proceedings of the 18th SIGMORPHON Workshop on Computational Research in Phonetics, Phonology, and Morphology, 2021, pp. 115–125.
  * [19] Markéta Řezáčková, D Tihelka, and J Švec,  ``T5g2p: Using text-to-text transfer transformer for grapheme-to-phoneme conversion,''  Proc. Interspeech 2021, pp. 6–10, 2021.
  * [20] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin,  ``Attention is all you need,''  in Advances in neural information processing systems, 2017, pp. 5998–6008.
  * [21] Simon Clematide and Peter Makarov,  ``Cluzh at sigmorphon 2021 shared task on multilingual grapheme-to-phoneme conversion: variations on a baseline,''  in Proceedings of the 18th SIGMORPHON Workshop on Computational Research in Phonetics, Phonology, and Morphology, 2021, pp. 148–153.
  * [22] Omnia ElSaadany and Benjamin Suter,  ``Grapheme-to-phoneme conversion with a multilingual transformer model,''  in Proceedings of the 17th SIGMORPHON Workshop on Computational Research in Phonetics, Phonology, and Morphology, 2020, pp. 85–89.
  * [23] Jackson L Lee, Lucas FE Ashby, M Elizabeth Garza, Yeonju Lee-Sikka, Sean Miller, Alan Wong, Arya D McCarthy, and Kyle Gorman,  ``Massively multilingual pronunciation modeling with wikipron,''  in Proceedings of the 12th language resources and evaluation conference, 2020, pp. 4223–4228.
  * [24] Roee Aharoni and Yoav Goldberg,  ``Morphological inflection generation with hard monotonic attention,''  in Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2017, pp. 2004–2015.
  * [25] Kaitao Song, Xu Tan, Tao Qin, Jianfeng Lu, and Tie-Yan Liu,  ``MASS: Masked sequence to sequence pre-training for language generation,''  in International Conference on Machine Learning. PMLR, 2019, pp. 5926–5936.


# Forging quantum data: classically defeating an $\mathsf{IQP}$-based quantum
test

Gregory D. Kahanamoku-Meyer<EMAIL_ADDRESS>of Physics, University
of California at Berkeley, Berkeley, CA 94720

###### Abstract

In 2009, Shepherd and Bremner proposed a “test of quantum capability” [1] that
is attractive because the quantum machine’s output can be verified efficiently
by classical means. While follow-up papers [2, 3] gave evidence that directly
simulating the quantum prover is classically hard, the security of the
protocol against other (non-simulating) classical attacks has remained an open
question. In this paper, I demonstrate that the protocol is not secure against
classical provers. I describe a classical algorithm that can not only convince
the verifier that the (classical) prover is quantum, but can in fact can
extract the secret key underlying a given protocol instance. Furthermore, I
show that the algorithm is efficient in practice for problem sizes of hundreds
of qubits. Finally, I provide an implementation of the algorithm, and give the
secret vector underlying the “$25 challenge” posted online by the authors of
the original paper.

##  1 Introduction

Tests of quantum speedup (or “quantum supremacy” tests) have generated
excitement recently as several experiments reach the cusp of demonstrating
quantum computational power in the laboratory. In the past decade, numerous
protocols have been designed for the purpose of demonstrating a quantum
speedup in solving some (possibly contrived) mathematical problem. A
difficulty of many of them, however, is that the quantum machine’s output is
difficult to _verify_. In many cases, the best known algorithm for checking
the solution is equivalent to solving the full problem classically. This
presents a serious issue for validation of the quantum results, because by
definition the supremacy regime is that where a classical solution is
hard.111In fact, in e.g. the Google team’s recent paper [4], checking the
solution is _harder_ than simply solving the problem classically.

Figure 1: Mean time to extract the secret vector $\boldsymbol{s}$ from
$X$-programs constructed as described in [1]. Shaded region is the first to
third quartile of the distribution of runtimes. We observe that the time is
polynomial and fast in practice even up to problem sizes of hundreds of
qubits. See Section 3.2 for a discussion of the
$\mathcal{O}\left(n^{2}\right)$ scaling. The data points were computed by
applying the algorithm to 1000 unique $X$-programs at each problem size. The
secret vector was successfully extracted for every $X$-program tested.
Experiments were completed using one thread on an Intel 8268 "Cascade Lake"
processor.

In 2009, Shepherd and Bremner introduced an efficiently-verifiable protocol
[1] that places only meager requirements on the quantum device, making it a
good candidate for near-term hardware. It requires only sampling from a
quantum circuit in which the gates all commute (a class introduced by those
authors as $\mathsf{IQP}$). Furthermore, the authors demonstrate in follow-up
papers [2, 3] that classically sampling from the distribution should be hard,
suggesting a “black-box” approach to cheating classically (by simply
simulating the quantum device) is indeed computationally difficult, and only a
couple hundred qubits would be required to make a classical solution
intractable.

Importantly, however, the classical verifier in [1] doesn’t actually check
whether the prover’s samples come from the correct distribution (in fact, [3]
suggests doing such a check efficiently is not possible). Instead, the
sampling task is designed such that bitstrings from its distribution will be
orthogonal to some secret vector $\boldsymbol{s}$ with high probability, and
it is this property that is checked. A question that has remained open is
whether a classical machine could generating samples satisfying the
orthogonality check _without actually simulating the distribution_. In this
paper I show that the answer is yes. I give an explicit algorithm that can
extract the secret vector $\boldsymbol{s}$ underlying an instance of the
protocol, thus making it trivial to generate orthogonal samples that pass the
verifier’s test. The main results of this paper are a statement of the
algorithm, a proof that a single iteration of it will extract the secret
vector $\boldsymbol{s}$ with probability $\nicefrac{{1}}{{2}}$ (Theorem
3.1)222This probability can be made arbitrarily close to 1 by repetition., and
empirical results demonstrating that it is efficient in practice (summarized
in Figure 1).

The following is a summary of the paper’s structure. In Section 2, I review
some points from the original paper [1] that are especially relevant to the
analysis here. In Section 3 I describe the algorithm to extract the secret
key, and therefore break the protocol’s security against classical provers.
There I also discuss briefly my implementation of the algorithm. In Section 4
I discuss related protocols, and provide the secret key underlying the “$25
challenge” posted to the web by the authors of the original paper.

##  2 Background

#### Overview of protocol

At the core of the protocol in [1] is a sampling problem. The classical
verifier generates a Hamiltonian $H_{P}$ consisting of a sum of products of
Pauli $X$ operators, and asks the quantum prover to sample the probability
distribution arising from the state $e^{iH_{P}\pi/8}\left|0^{\otimes
n}\right\rangle$. The Hamiltonian is not exactly random, but instead is
designed such that the samples $\left\\{\boldsymbol{x}_{i}\right\\}$ are
biased such that $\boldsymbol{x}_{i}\cdot\boldsymbol{s}=0$333This inner
product is over $\mathbb{F}_{2}$; all arithmetic in this paper is modulo 2
unless otherwise noted. with high probability for some secret vector
$\boldsymbol{s}$. The classical verifier, with knowledge of $\boldsymbol{s}$,
can quickly check that the samples have such a bias. Since $\boldsymbol{s}$
should be only known to the verifier, it is conjectured in [1] that the only
efficient way to generate such samples is by actually doing the evolution. In
Section 3 I show that it is possible to extract $\boldsymbol{s}$ classically
from just the description of the Hamiltonian.

#### X-programs

A Hamiltonian of the type used in this protocol can be described by a
rectangular matrix of binary numbers, for which each row corresponds to a
Hamiltonian term. Given such a matrix $P$ (called an “$X$-program”), the
Hamiltonian is

$H_{P}=\sum_{i}\prod_{j}X^{P_{ij}}$ (2.1)

In words, a 1 in $P$ at row $i$ and column $j$ corresponds to the inclusion of
a Pauli $X$ operator on the $j^{\mathrm{th}}$ site in the $i^{\mathrm{th}}$
term of the Hamiltonian. The $X$-program also has one additional parameter
$\theta$, which is the “action”—the integrated energy over time for which the
Hamiltonian will be applied.

I note here that the original paper discusses _matroids_ rather than matrices.
The perspective of this paper is that we have been given an explicit matrix
$P$ acting as a canonical representative for the relevant matroid; it will be
sufficient here to simply discuss $P$ as a matrix, and I will do so for the
rest of the paper.

#### Embedding a bias and verifying the output

In order to bias the output distribution along $\boldsymbol{s}$, a submatrix
with special properties is embedded within the matrix $P$. For a vector
$\boldsymbol{x}$ and matrix $P$, we can define the submatrix
$P_{\boldsymbol{x}}$ as that which is generated by deleting all rows of $P$
that are orthogonal to $\boldsymbol{x}$. Under this notation, our relevant
submatrix is $P_{\boldsymbol{s}}$ where $\boldsymbol{s}$ is the secret vector.
For the output distribution to be appropriately biased, [1] suggests that
$P_{\boldsymbol{s}}$ should correspond to the generator matrix of an error-
correcting code—in particular, the authors suggest using a quadratic residue
code and setting the action $\theta=\nicefrac{{\pi}}{{8}}$. As described
below, this choice leads to a gap between the quantum and classical
probabilities of generating samples orthogonal to $\boldsymbol{s}$ (for the
best known classical strategy in [1]). The verifier’s check is simply to
request a large number of samples, and then determine if the fraction
orthogonal to $\boldsymbol{s}$ is too large to have likely been generated by
the classical distribution.

In the two Facts below, I recall the probabilities from [1] corresponding to
that paper’s quantum and classical strategies. The reasoning behind the
classical strategy (Fact 2.2) is crucial to the rest of this paper; it is
worth understanding its proof before moving on to the algorithm in Section 3.

######  Fact 2.1.

Quantum strategy

Let $P$ be an $X$-program which has an embedded submatrix $P_{\boldsymbol{s}}$
for some secret vector $\boldsymbol{s}$, such that $P_{\boldsymbol{s}}$ is the
generator matrix for a quadratic residue code up to permutation of rows. Let
$\boldsymbol{X}$ be a random variable representing the distribution of
bitstrings from an $n$-qubit quantum state
$e^{iH_{P}\pi/8}\left|0\right\rangle$ measured in the $Z$ basis, where $H_{P}$
is defined as in Equation 2.1. Then,

$\Pr\left[\boldsymbol{X}\cdot\boldsymbol{s}=0\right]=\cos^{2}\left(\frac{\pi}{8}\right)\approx
0.85\cdots$ (2.2)

###### Proof.

The proof is contained in [1]. ∎

######  Fact 2.2.

Classical strategy of [1]

Let $\boldsymbol{d},\boldsymbol{e}$ be two bitstrings of length $n$ (the
length of a row of $P$). Define $P_{\boldsymbol{d},\boldsymbol{e}}$ as the
matrix generated by deleting the rows of $P$ orthogonal to $\boldsymbol{d}$ or
$\boldsymbol{e}$.444In [1], $P_{\boldsymbol{d},\boldsymbol{e}}$ is written as
$P_{\boldsymbol{d}}\cap P_{\boldsymbol{e}}$. Let
$\boldsymbol{y}=\sum_{\boldsymbol{p}_{i}\in
P_{\boldsymbol{d},\boldsymbol{e}}}\boldsymbol{p}_{i}$ be the vector sum of the
rows of $P_{\boldsymbol{d},\boldsymbol{e}}$. Letting $\boldsymbol{Y}$ be the
random variable representing the distribution of $\boldsymbol{y}$ when
$\boldsymbol{d}$ and $\boldsymbol{e}$ are chosen uniformly at random, then

$\Pr\left[\boldsymbol{Y}\cdot\boldsymbol{s}=0\right]=\nicefrac{{3}}{{4}}$
(2.3)

###### Proof.

With $\boldsymbol{y}$ defined as above, we have

$\boldsymbol{y}\cdot\boldsymbol{s}=\sum_{\boldsymbol{p}_{i}\in
P_{\boldsymbol{d},\boldsymbol{e}}}\boldsymbol{p}_{i}\cdot\boldsymbol{s}$ (2.4)

By defintion, $\boldsymbol{p}_{i}\cdot\boldsymbol{s}=1$ if
$\boldsymbol{p}_{i}\in P_{\boldsymbol{s}}$. Therefore
$\boldsymbol{y}\cdot\boldsymbol{s}$ is equivalent to simply counting the
number of rows in both $P_{\boldsymbol{s}}$ and
$P_{\boldsymbol{d},\boldsymbol{e}}$, or equivalently, counting the rows in
$P_{\boldsymbol{s}}$ for which $\boldsymbol{p}\cdot\boldsymbol{d}$ and
$\boldsymbol{p}\cdot\boldsymbol{e}$ are both 1. We can express this using the
matrix-vector products of $P_{\boldsymbol{s}}$ with $\boldsymbol{d}$ and
$\boldsymbol{e}$:

$\displaystyle\boldsymbol{y}\cdot\boldsymbol{s}$
$\displaystyle=\sum_{\boldsymbol{p}_{i}\in
P_{\boldsymbol{s}}}\left(\boldsymbol{p}\cdot\boldsymbol{d}\right)\left(\boldsymbol{p}\cdot\boldsymbol{e}\right)$
(2.5) $\displaystyle=\left(P_{\boldsymbol{s}}\
\boldsymbol{d}\right)\cdot\left(P_{\boldsymbol{s}}\ \boldsymbol{e}\right)$
(2.6)

Considering that $P_{\boldsymbol{s}}$ is the generator matrix for an error
correcting code, I denote $c_{\boldsymbol{d}}=P_{\boldsymbol{s}}\
\boldsymbol{d}$ as the encoding of $\boldsymbol{d}$ under
$P_{\boldsymbol{s}}$. In this notation, we have

$\displaystyle\boldsymbol{y}\cdot\boldsymbol{s}$
$\displaystyle=\boldsymbol{c}_{\boldsymbol{d}}\cdot\boldsymbol{c}_{\boldsymbol{e}}$
(2.7)

Now, we note that the quadratic residue code (for which $P_{\boldsymbol{s}}$
is a generator matrix) has the property that any two codewords
$\boldsymbol{c}_{\boldsymbol{d}}$ and $\boldsymbol{c}_{\boldsymbol{e}}$ have
$\boldsymbol{c}_{\boldsymbol{d}}\cdot\boldsymbol{c}_{\boldsymbol{e}}=0$ iff
either $\boldsymbol{c}_{\boldsymbol{d}}$ or $\boldsymbol{c}_{\boldsymbol{e}}$
has even parity.555This can be seen from the fact that the extended quadratic
residue code, created by adding a single parity bit, is self-dual (and all
extended codewords have even parity). [1] Half of the quadratic residue code’s
words have even parity and $\boldsymbol{c}_{\boldsymbol{d}}$ and
$\boldsymbol{c}_{\boldsymbol{e}}$ are random codewords, so the probability
that either of them has even parity is $\nicefrac{{3}}{{4}}$. Thus, the
probability that $\boldsymbol{y}\cdot\boldsymbol{s}=0$ is
$\nicefrac{{3}}{{4}}$, proving the fact. ∎

In the next section, we show that the classical strategy just described can be
improved.

##  3 Algorithm

The classical strategy described in [1] and reproduced in Fact 2.2 above
generates vectors that are orthogonal to $\boldsymbol{s}$ with probability
$\nicefrac{{3}}{{4}}$. The key to this paper is that it is possible to
_correlate_ the vectors generated by that strategy, such that with probability
$\nicefrac{{1}}{{2}}$ one may generate a large set of vectors that _all_ are
orthogonal to $\boldsymbol{s}$. When that happens, they form a system of
linear equations that can be solved to yield $\boldsymbol{s}$. Finally, with
knowledge of $\boldsymbol{s}$ it is trivial to generate samples that pass the
verifier’s test.

To generate such a correlated set, we follow a modified version of the
original classical strategy. Instead of choosing random bitstrings for both
$\boldsymbol{d}$ and $\boldsymbol{e}$, we hold $\boldsymbol{d}$ constant, only
choosing new values for $\boldsymbol{e}$ for each vector. Crucially, if the
encoding $c_{\boldsymbol{d}}$ of $\boldsymbol{d}$ under $P_{\boldsymbol{s}}$
has even parity, _all_ of the generated vectors $\boldsymbol{m}_{i}$ will have
$\boldsymbol{m}_{i}\cdot\boldsymbol{s}=0$. (See Theorem 3.1). This will happen
with probability $\nicefrac{{1}}{{2}}$ over our choice of $\boldsymbol{d}$
(whenever $\boldsymbol{c}_{\boldsymbol{d}}=P_{\boldsymbol{s}}\ \boldsymbol{d}$
has even parity).

In practice, it is more convenient to do the linear solve if all
$\boldsymbol{m}_{i}\cdot\boldsymbol{s}=1$ instead of 0. This can be
accomplished by adding a vector $\boldsymbol{m}^{*}$ with
$\boldsymbol{m}^{*}\cdot\boldsymbol{s}=1$ to each $\boldsymbol{m}_{i}$. It
turns out that
$\boldsymbol{m}^{*}=\sum_{\boldsymbol{p}\in\mathrm{rows}\left(P\right)}\boldsymbol{p}$
has this property; see proof of Theorem 3.1.

The explicit algorithm for extracting the vector $\boldsymbol{s}$ is given in
Algorithm 1.

  1. 1.

Let
$\boldsymbol{m}^{*}=\sum_{\begin{subarray}{c}\boldsymbol{p}\in\mathrm{rows}\left(P\right)\end{subarray}}\boldsymbol{p}$.

  2. 2.

Pick
$\boldsymbol{d}\stackrel{{\scriptstyle\$}}{{\leftarrow}}\left\\{0,1\right\\}^{n}$.

  3. 3.

Generate a large number (say $2n$) of vectors $\boldsymbol{m}_{i}$, forming
the rows of a matrix $M$. For each:

    1. (a)

Pick
$\boldsymbol{e}\stackrel{{\scriptstyle\$}}{{\leftarrow}}\left\\{0,1\right\\}^{n}$

    2. (b)

Let
$\boldsymbol{m}_{i}=\boldsymbol{m}^{*}+\sum_{\begin{subarray}{c}\boldsymbol{p}\in\mathrm{rows}\left(P\right)\\\
\boldsymbol{p}\cdot\boldsymbol{d}=\boldsymbol{p}\cdot\boldsymbol{e}=1\end{subarray}}\boldsymbol{p}$

  4. 4.

Via linear solve, find the set of vectors
$\left\\{\boldsymbol{s}_{i}\right\\}$ satisfying
$M\boldsymbol{s}_{i}=\boldsymbol{1}$, where $\boldsymbol{1}$ is the vector of
all ones.

  5. 5.

For each candidate vector $\boldsymbol{s}_{i}$:

    1. (a)

Extract $P_{\boldsymbol{s}_{i}}$ from $P$ by deleting the rows of $P$
orthogonal to $\boldsymbol{s}_{i}$

    2. (b)

If $P_{\boldsymbol{s}_{i}}$ has the properties of a quadratic residue code up
to row reordering (i.e. codewords have
$\mathrm{wt}\left(\boldsymbol{c}\right)\in\left\\{-1,0\right\\}\left(\bmod
4\right)$), return $\boldsymbol{s}$ and exit.

  6. 6.

No candidate vector $\boldsymbol{s}$ was found; return $\bot$.

Algorithm 1 ExtractKey$\left(P\right)$
The algorithm to extract the secret vector $\boldsymbol{s}$ from an
$X$-program $P$. $n$ is the number of columns in the $X$-program, and
$\stackrel{{\scriptstyle\$}}{{\leftarrow}}$ means “select uniformly from the
set.”

###  3.1 Analysis

######  Theorem 3.1.

On input an $X$-program $P$ containing a unique embedded submatrix
$P_{\boldsymbol{s}}$ that is a generator matrix for the quadratic residue code
(up to rearrangement of its rows), Algorithm 1 will output the corresponding
vector $\boldsymbol{s}$ with probability $\frac{1}{2}$.

###### Proof.

If $\boldsymbol{s}$ is contained in the set
$\left\\{\boldsymbol{s}_{i}\right\\}$ generated in step 3 of the algorithm,
the correct vector $\boldsymbol{s}$ will be output via the check in step 4
because there is a unique submatrix $P_{\boldsymbol{s}}$ corresponding to the
quadratic residue code. $\boldsymbol{s}$ will be contained in
$\left\\{\boldsymbol{s}_{i}\right\\}$ as long as $M$ satisfies the equation
$M\boldsymbol{s}=\boldsymbol{1}$. Thus we desire to show that
$M\boldsymbol{s}=\boldsymbol{1}$ with probability $\nicefrac{{1}}{{2}}$.

Each row of $M$ is

$\boldsymbol{m}_{i}=\boldsymbol{m}^{*}+\bar{\boldsymbol{m}}_{i}$ (3.1)

for a vector $\bar{\boldsymbol{m}}_{i}$ defined as

$\bar{\boldsymbol{m}}_{i}=\sum_{\begin{subarray}{c}\boldsymbol{p}\in\mathrm{rows}\left(P\right)\\\
\boldsymbol{p}\cdot\boldsymbol{d}=\boldsymbol{p}\cdot\boldsymbol{e}=1\end{subarray}}\boldsymbol{p}$
(3.2)

Here I will show that $\boldsymbol{m}^{*}\cdot\boldsymbol{s}=1$ always and
$\bar{\boldsymbol{m}}_{i}\cdot\boldsymbol{s}=0$ for all $i$ with probability
$\nicefrac{{1}}{{2}}$, implying that $M\boldsymbol{s}=\boldsymbol{1}$ with
probability $\nicefrac{{1}}{{2}}$.

First I show that $\boldsymbol{m}^{*}\cdot\boldsymbol{s}=1$.
$\boldsymbol{m}^{*}$ is the sum of all rows of $P$, so we have

$\boldsymbol{m}^{*}\cdot\boldsymbol{s}=\sum_{\begin{subarray}{c}\boldsymbol{p}\in\mathrm{rows}\left(P\right)\end{subarray}}\boldsymbol{p}\cdot\boldsymbol{s}=\sum_{\begin{subarray}{c}\boldsymbol{p}\in\mathrm{rows}\left(P_{\boldsymbol{s}}\right)\end{subarray}}1$
(3.3)

We see that the inner product is equal to the number of rows in the submatrix
$P_{\boldsymbol{s}}$. This submatrix is a generator matrix for the quadratic
residue code, which has a number of rows equal to a prime $q>2$; the number of
rows is odd and thus

$\boldsymbol{m}^{*}\cdot\boldsymbol{s}=1$ (3.4)

Now I turn to showing that $\bar{\boldsymbol{m}}_{i}\cdot\boldsymbol{s}=0$ for
all $i$ with probability $\nicefrac{{1}}{{2}}$. In the proof of Fact 2.2, it
was shown that for any two vectors $\boldsymbol{d}$ and $\boldsymbol{e}$,
vectors $\bar{\boldsymbol{m}}_{i}$ generated by summing rows
$\boldsymbol{p}_{i}$ of $P$ for which
$\boldsymbol{d}\cdot\boldsymbol{p}_{i}=\boldsymbol{e}\cdot\boldsymbol{p}_{i}=1$
have

$\bar{\boldsymbol{m}}_{i}\cdot\boldsymbol{s}=0\text{ iff
}\boldsymbol{c}_{\boldsymbol{d}}\text{ or
}\boldsymbol{c}_{\boldsymbol{e}}\text{ has even parity}$ (3.5)

where $\boldsymbol{c}_{\boldsymbol{d}}$ and $\boldsymbol{c}_{\boldsymbol{e}}$
are the encodings under $P_{\boldsymbol{s}}$ of $\boldsymbol{d}$ and
$\boldsymbol{e}$ respectively. If $\boldsymbol{d}$ is held constant for all
$i$, and $\boldsymbol{d}$ happened to be chosen such that
$\boldsymbol{c}_{\boldsymbol{d}}=P_{\boldsymbol{s}}\ \boldsymbol{d}$ has even
parity, then $\bar{\boldsymbol{m}}_{i}\cdot\boldsymbol{s}=0$ for all $i$ by
Equation 3.5. Because half of the codewords of the quadratic residue code have
even parity, for $\boldsymbol{d}$ selected uniformly at random we have
$\bar{\boldsymbol{m}}_{i}\cdot\boldsymbol{s}=0$ for all $i$ with probability
$\nicefrac{{1}}{{2}}$.

I have shown that $\boldsymbol{m}^{*}\cdot\boldsymbol{s}=1$ always and
$\bar{\boldsymbol{m}}_{i}\cdot\boldsymbol{s}=0$ for all $i$ with probability
$\nicefrac{{1}}{{2}}$. Therefore we have

$\Pr_{\boldsymbol{d}}\left[\boldsymbol{m}_{i}\cdot\boldsymbol{s}=1\ \forall\
i\right]=\nicefrac{{1}}{{2}}$

Thus $M\boldsymbol{s}=\boldsymbol{1}$ with probability $\nicefrac{{1}}{{2}}$.
The algorithm will output $\boldsymbol{s}$ whenever
$M\boldsymbol{s}=\boldsymbol{1}$, proving the theorem. ∎

Having established that the algorithm outputs $\boldsymbol{s}$ with high
probability (that can be made arbitrarily close to 1 by repetition), we now
turn to analyzing its runtime.

######  Claim 3.1.

(empirical) Algorithm 1 halts in $\mathcal{O}\left(n^{3}\right)$ time on
average.

All steps of the algorithm except for step 4 have
$\mathcal{O}\left(n^{3}\right)$ scaling by inspection. The obstacle preventing
Claim 3.1 from trivially holding is that it is hard to make a rigorous
statement about how large the set of candidate vectors
$\left\\{\boldsymbol{s}_{i}\right\\}$ is. Because
$\left|\left\\{\boldsymbol{s}_{i}\right\\}\right|=2^{n-\mathrm{rank}\left(M\right)}$,
we’d like to show that on average, the rank of $M$ is close to or equal to
$n$. It seems reasonable that this would be the case: we are generating the
rows of $M$ by summing rows from $P$, and $P$ must have full rank because it
contains a rank-$n$ error correcting code. But the rows of $P$ summed into
each $\boldsymbol{m}_{i}$ are not selected independently—they are always
related via their connection to the vectors $\boldsymbol{d}$ and
$\boldsymbol{e}$, and it’s not clear how these correlations affect the linear
independence of the resulting $\boldsymbol{m}_{i}$.

Figure 2: (a) The average number of candidate vectors checked before the
secret vector $\boldsymbol{s}$ was found, when the algorithm was applied to
1000 unique $X$-programs at each problem size tested. We observe that the
number of vectors to check is constant in $n$. (b) The number of unconstrained
degrees of freedom $n-\mathrm{rank}\left(M\right)$ for matrices $M$ generated
in step 3 of Algorithm 1, for “good” choices of $\boldsymbol{d}$ such that
$M\boldsymbol{s}=\boldsymbol{1}$. The rapidly decaying tail implies that it is
rare for any more than a few degrees of freedom to remain unconstrained. The
blue bars represent the distribution over 1000 unique $X$-programs of size
$n=245$. The algorithm was then re-run on the $X$-programs that had
$n-\mathrm{rank}\left(M\right)>4$ to generate the orange bars.

Despite the lack of a proof, empirical evidence supports Claim 3.1 when the
algorithm is applied to $X$-programs generated in the manner described in [1].
Figure 2(a) shows the average number of candidate keys checked by the
algorithm before $\boldsymbol{s}$ is found, as a function of problem size. The
value is constant, demonstrating that the average size of the set
$\left\\{\boldsymbol{s}_{i}\right\\}$ does not scale with $n$. Furthermore,
the value is small—only about 4. This implies that $M$ usually has high rank.
In Figure 2(b) I plot explicitly the distribution of the rank of the matrix
$M$ over 1000 runs of the algorithm on unique $X$-programs of size $n=245$.
The blue bars (on the left of each pair) show the distribution over all
$X$-programs tested, and the sharply decaying tail supports the claim that
low-rank $M$ almost never occur.

A natural next question is whether there is some feature of the $X$-programs
in that tail that causes $M$ to be low rank. To investigate that question, the
algorithm was re-run 100 times on each of the $X$-programs that had
$n-\mathrm{rank}\left(M\right)>4$ in the blue distribution. The orange bars of
Figure 2(b) (on the right of each pair) plot the distribution of
$n-\mathrm{rank}\left(M\right)$ for that second run. The similarity of the
blue and orange distributions demonstrates that the rank of $M$ is not
correlated between runs; that is, the low rank of $M$ in the first run was not
due to any feature of the input $X$-programs. From a practical perspective,
this data suggests that if the rank of $M$ is found to be unacceptably low,
the algorithm can simply be re-run with new randomness and the rank of $M$ is
likely to be higher the second time.

###  3.2 Implementation

An implementation of Algorithm 1 in the programming language Julia is
available online at github.com/GregDMeyer/IQPwn. In that repository is also
code for generating the figures in this paper. Figure 1 shows the runtime of
this implementation for various problem sizes. Experiments were completed
using one thread on an Intel 8268 "Cascade Lake" processor.

Note that Figure 1 shows $\mathcal{O}\left(n^{2}\right)$ scaling, rather than
$\mathcal{O}\left(n^{3}\right)$ from Claim 3.1. This is due to data-level
parallelism in the implementation. $\mathbb{Z}_{2}^{n}$ vectors are stored as
the bits of 64-bit integers, so operations like vector addition can be
performed on 64 elements at once via bitwise operations. Furthermore, with AVX
SIMD CPU instructions, those operations can be applied to multiple 64-bit
integers in one CPU cycle. Thus, for $n$ of order 100, the ostensibly
$\mathcal{O}\left(n\right)$ vector inner products and vector sums are
performed in constant time, removing one factor of $n$ from the runtime. The
tests in Figure 1 were performed on a CPU with 512 bit vector units.

##  4 Discussion

#### Modifications to the protocol

A natural question is whether it is possible to modify the original protocol
such that this attack is not successful. Perhaps $P$ can be engineered such
that either 1) it is not possible to generate a large number of vectors that
all have a known inner product with $\boldsymbol{s}$, or 2) the rank of the
matrix $M$ formed by these generated vectors will never be sufficiently high
to allow solution of the linear system.

For 1), our ability to generate many vectors orthogonal to $\boldsymbol{s}$
relies on the fact that the extended quadratic residue code is even and self-
dual. These characteristics imply that if $P_{\boldsymbol{s}}\ \boldsymbol{d}$
has even parity, _all_ of our subsequently generated vectors will have
$\boldsymbol{m}_{i}\cdot\boldsymbol{s}=0$. Building $P$ via a code without the
self-dual property would remove this possibility, though the challenge is to
do so while still maintaining the bias in the quantum case, and without
opening up a new avenue to discovering $\boldsymbol{s}$. I leave that pursuit
open.

For 2), the main obstacle is that the matrix $P$ _must_ have rank $n$ because
embedded in it is a code of rank $n$. The only hope is to somehow engineer the
matrix such that linear combinations generated in the specific way described
above will not be linearly independent. It’s not at all clear how one would do
that, and furthermore, adding structure to the previously-random extra rows of
$P$ runs the risk of providing even more information about the secret vector
$\boldsymbol{s}$. Perhaps one could _prove_ that the rank of $M$ will be large
even for worst-case inputs $P$—this would also be an interesting future
direction.

#### Protocols with provable hardness

The attack described in this paper reiterates the value of building protocols
for which _passing the check itself_ , rather than just simulating the quantum
device, can be shown to be hard under well-established complexity-theoretic
assumptions. For example, the protocol given in [5] is secure under the
hardness assumption of Learning With Errors. Unfortunately, such rigorous
results come with a downside, which is an increase in the size and complexity
of circuits that must be run on the quantum device. Exploring simplified
protocols that are provably secure is an interesting area for further
research.

#### Complexity theoretic implications

Conjecture 3.2 of [1] supposes whether the language of matroids with a hidden
sub-matroid is $\mathsf{NP}$-complete. In rough terms, it asks if a
$\mathsf{BPP}$ machine can efficiently decide whether a given matrix $P$
contains a hidden submatrix $P_{\boldsymbol{s}}$ corresponding to a generator
matrix for the quadratic residue code (up to permutations of rows). The
results in this paper cannot make a strong statement about this conjecture; I
have only empirically established that Algorithm 1 halts in polynomial time in
the average case. It’s possible that there exist some class of worst-case
instances of $P$ for which the algorithm is not efficient; this would be an
interesting area for further research.

#### The $25 challenge

At quantumchallenges.wordpress.com, the authors of [1] posed a challenge. They
posted a specific instance of the matrix $P$, and offered $25 to anyone who
could send them samples passing the verifier’s check. The secret vector
$\boldsymbol{s}$ corresponding to their challenge matrix $P$ is (encoded as a
base-64 string):

    BilbHzjYxrOHYH4OlEJFBoXZbps4a54kH8flrRgo/g==

The code used to extract the secret vector, as well as a set of samples that
should pass the check for their challenge matrix, can be found at
github.com/GregDMeyer/IQPwn. If you’d like to convert the above key into a
binary string, you can use the b64tobin script in the examples/ directory of
that repository.

#### Summary and outlook

In this paper, I have described a classical algorithm that passes the
interactive quantum test described in [1]. I have proven that a single
iteration of the algorithm will return the underlying secret vector with
probability $\nicefrac{{1}}{{2}}$, and empirically established that it is
efficient. The immediate implication of this result is that the protocol from
[1] in its original form is no longer effective as a test of quantumness.
While it may be possible to reengineer that protocol to thwart this attack,
this paper reiterates the value of proving the security of the verification
step. Protocols with provable security are valuable on their own, but can also
be used as building blocks for new, more complex results (see, for example,
classically verifiable quantum computation in [6] building off the protocol of
[5]). As quantum hardware begins to surpass the abilities of classical
machines, quantum cryptographic tools will play an important role in making
quantum computation available as a service. Establishing the security of these
protocols is an important first step.

#### Acknowledgements

The author is supported by the National Defense Science and Engineering
Graduate Fellowship (NDSEG).

## References

  * [1] Dan Shepherd and Michael J. Bremner.  Temporally unstructured quantum computation.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465(2105):1413–1439, May 2009.
  * [2] Michael J. Bremner et al.  Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations.  Physical Review Letters, 117(8):080501, August 2016.
  * [3] Michael J. Bremner et al.  Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467(2126):459–472, February 2011.
  * [4] Frank Arute et al.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, October 2019.
  * [5] Zvika Brakerski et al.  A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device.  arXiv:1804.00640 [quant-ph], January 2019.  arXiv: 1804.00640.
  * [6] Urmila Mahadev.  Classical Verification of Quantum Computations.  arXiv:1804.01082 [quant-ph], September 2018.  arXiv: 1804.01082.


CIPANP2018-Masubuchi

Measurements and Searches of Higgs boson
decays to two fermions

Tatsuya Masubuchi
on behalf of the ATLAS collaboration111Copyright 2018 CERN for the benefit of
the ATLAS Collaboration. CC-BY-4.0 license.

International Center for Elementary Particle Physics
The University of Tokyo, Japan

> The interaction of the Higgs boson to fermion is most fragile part in the
> Standard model. The Higgs decay to ditau ($H\rightarrow\tau\tau$) was
> observed and established in the LHC Run 1 data. This report presents recent
> measurements and searches of Higgs boson decay to two fermions. In
> particular this report focuses on results of the Higgs boson decays to
> third-generation ($H\rightarrow b\overline{b}$) and second-generation
> ($H\rightarrow c\overline{c}$, $H\rightarrow\mu\mu$) fermions using the LHC
> Run 2 data collected by the ATLAS experiment at the LHC.

> PRESENTED AT
>
>
>
>
> Thirteenth Conference on the Intersections of Particle and Nuclear Physics
> (CIPANP2018)
> Palm Springs, CA, USA, May 29 - June 3, 2018

##  1 Introduction

A Higgs boson was discovered in 2012 by the ATLAS and CMS collaborations [1,
2]. The properties of the discovered Higgs boson has been predominantly
measured using bosonic decay mode, $H\rightarrow\gamma\gamma$, $H\rightarrow
ZZ$ and $H\rightarrow WW$ in LHC Run 1 and Run 2 [3, 4, 5]. The measured
properties are compatible with the predictions of the Standard Model (SM)
within uncertainties. However, a great mystery on the interaction (Yukawa
coupling) between Higgs and fermions still remains in the Higgs sector of the
SM. It is important to experimentally measure Yukawa coupling for each fermion
and to test if the coupling is proportional to fermion mass to solve the
origin of the fermion mass and generation. Direct evidences for the coupling
of the Higgs boson to fermions were established via the decay to
$\tau$-leptons through the combination of ATLAS and CMS Run 1 [6] and recently
the Higgs production associated with top quarks [7]. Table 1 shows the
branching ratio of Higgs decay to fermion [8]. The coupling of Higgs boson to
bottom quark is not observed yet although the decay branching ratio is
dominant at $m_{H}=125$ GeV. In LHC Run 2 the observation of $H\rightarrow
b\overline{b}$ mode is one of big milestones in Higgs physics of the ATLAS
experiment [9].

$m_{H}=125$ GeV | $b\overline{b}$ | $\tau\tau$ | $c\overline{c}$ | $\mu\mu$
---|---|---|---|---
Branching Ratio | 58.2% | 6.27% | 2.89% | 0.023%
Table 1: The branching ratio of major Higgs decays to fermions at $m_{H}$=125
GeV.

Various theories beyond the Standard model (BSM) predict the deviation of
Yukawa couplings. The precise measurement of the coupling between the Higgs
and fermions might unveil the BSM and determine the physics model since
advocated BSM models predict different deviation patterns on the Yukawa
coupling.

##  2 Higgs decay to bottom quark pair

The decay of the SM Higgs boson to pairs of $b$-quarks is expected to have a
branching ratio of 58% at $m_{H}=125$ GeV, the largest among all decay modes.
At the LHC, the enormous backgrounds arising from multi-jet production make an
inclusive search extremely challenging. The most sensitive production modes
for $H\rightarrow b\overline{b}$ search are those where the Higgs boson is
produced in association with a $W$ or $Z$ boson. Their leptonic decay leads to
clean signatures that can be triggered by the high-$p_{\mathrm{T}}$
electron/muon or missing transverse energy ($E_{\mathrm{T}}^{\mathrm{miss}}$),
and can reject multi-jet background.

Another new approach using vector boson fusion (VBF) production has been
attempted. In order to enhance signal-to-background ratio in the VBF
production mode, a photon radiated from an internal $W^{\pm}$ boson or from an
incoming or outgoing quark is required.

###  2.1 Evidence for the $H\rightarrow b\overline{b}$ decay using Higgs boson
production in association with a $W$ or $Z$ boson

A search for the decay of Higgs boson to a pair of $b$-quarks using the Higgs
boson production in association with a $W$ or $Z$ boson is reported [10]. The
data used in this analysis were collected at a center-of-mass energy of 13 TeV
during 2015 and 2016 running period, and correspond to an integral luminosity
of 36.1 fb-1. Three main signatures are explored, $ZH\rightarrow\nu\nu
b\overline{b}$, $WH\rightarrow\ell\nu b\overline{b}$ and
$ZH\rightarrow\ell\ell b\overline{b}$. These channels are referred to as 0-,1-
and 2-lepton channels, based on the number of selected charged leptons. All
events are required to have at least two jets, and exactly two jets must pass
the $b$-tagging requirement. The event selection has been optimized for each
lepton channel. Anti-QCD selections using the angular correlations between
$E_{\mathrm{T}}^{\mathrm{miss}}$ and (di)jet-systems are applied to reduce
further multi-jet background to negligible level in the 0 lepton channel.
Dedicated identification and isolation requirements are required in the
charged lepton to reduce multi-jet background in the 1 lepton channel. The
reconstructed dilepton mass should be consistent with the $Z$ boson mass in
the 2 lepton channel. Selected events are categorized according to the
reconstructed vector boson’s transverse momentum $p_{\mathrm{T}}^{V}$ to
enhance signal-to-background ratio. In the 0- and 1-lepton channels a signal
region is defined, with $p_{\mathrm{T}}^{V}$$>150$ GeV. In the 2-lepton
channel two regions are considered, 75 GeV $<$ $p_{\mathrm{T}}^{V}$$<$ 150 GeV
and $p_{\mathrm{T}}^{V}$$>$ 150 GeV as shown in Figure 1. Events are further
split into two categories according to the jet multiplicity. In 0- and
1-lepton channels, events are considered with exactly two or three jets. In
the 2-lepton channel, events are considered with exactly two or three or more
jets.

The reconstructed dijet mass resolution is one of key ingredients to improve
search sensitivity in this analysis. Customized $b$-jet energy corrections are
applied in addition to general jet energy scale correction. Figure 1 shows
$m_{bb}$ distribution with various $b$-jet energy corrections. In particular,
the $ZH\rightarrow\ell\ell b\overline{b}$ event kinematics can be used to
constrain $b$-jet energy, with a kinematic likelihood due to no intrinsic
missing energy in the 2 lepton channel. This provides about 40% improvement of
the dijet mass resolution.

Figure 1: $p_{\mathrm{T}}^{V}$ distribution in 2 lepton, 2-jet signal region
(left). Comparison of the $m_{bb}$ distributions as additional correction are
applied to the jet energy scale for the 2-lepton channel in the 2-jet and
$p_{\mathrm{T}}^{V}$$>$ 150 GeV region (right) [10].

Another important ingredient is multivariate analysis. Multivariate
discriminants making use of boosted decision trees (BDTs) are constructed,
trained and evaluated in each lepton channel and analysis region separately.
In total eight signal regions and two $W$+jets control regions(CRs), which
enhances $W$+jets purity in the selection of low $m_{bb}$ and high
$m_{\mathrm{top}}$ in the 1 lepton channel and four top control regions
requiring different lepton flavor ($e\mu$) in the 2 lepton channel are fit
simultaneously. The BDT output distributions are used in the signal region,
while one bin distributions in $W$+jets CRs to determine background
normalization and $m_{bb}$ shape in top control regions are used. Experimental
and background modeling uncertainties are assigned in each signal region and
control region accordingly. Figure 2 shows fitted BDT output distributions.

Figure 2: The BDTVH output distribution in the 0-lepton (left), 1-lepton
(middle) and 2-lepton (right) for the 2-jet and $p_{\mathrm{T}}^{V}$$>$ 150
GeV region [10].

This complicated background modeling scheme has been validated with diboson
($VZ\rightarrow b\overline{b}$) background. The BDTs are re-trained with the
diboson process as signal. The observed signal strength is
$\mu_{VZ}^{b\overline{b}}=1.11^{+0.25}_{-0.22}$, which is consistent with the
SM. The observed significance is 5.8 standard deviations.

In the $VH\rightarrow b\overline{b}$ signal extraction a combined fit with Run
1 data [11] has been performed. The observed signal strength is
$\mu_{VH}^{b\overline{b}}=0.90^{+0.28}_{-0.26}$ as shown in Figure 3. The
observed significance is 3.6 standard deviations, to be compared to an
expectation of 4.0 standard deviations.

Figure 3: The fitted signal strength parameter for the $WH$ and $ZH$ processes
(left). Events yields as a function of $\log(S/B)$ for data, background and
the Higgs boson signal (right). The Higgs boson signal contribution is scaled
to $\mu=0.90$ [10].

###  2.2 Search for Higgs boson production via weak boson fusion and decaying
$b\overline{b}$ with a high-energy photon

The VBF production mode for the Higgs decay to pair of $b$-quarks is
challenging due to larger contributions from non-resonant $bbjj$ production
and difficulties in triggering on low-$p_{\mathrm{T}}$ $b$-jets. A novel study
that is requiring high-$p_{\mathrm{T}}$ photon [12] has been performed. The
presence of high-$p_{\mathrm{T}}$ photon provides a clean signature and
efficient triggering in the hadron collider. Furthermore, the background
diagrams suppress photon emission from gluon line and destructive interference
between diagrams with photon emission from the initial-state quark and the
final-state quark further reduces the background cross section as shown in
figure 4.

A dedicated trigger has been developed for VBF+photon analysis. The offline
event selections require one photon with $p_{\mathrm{T}}$ $>$ 30 GeV and at
least four jets with $p_{\mathrm{T}}$ $>$ 40 GeV and $|\eta|$ $<$ 4.5, and at
least two of them must be $b$-tagged in the central detector region
($|\eta|<2.5$). If more than two $b$-tagged jets were found, jets with highest
and second highest $b$-tagging discriminant output would be taken as a
Higgs($b\overline{b}$) system in the candidate events. The $b\overline{b}$
system must have $p_{\mathrm{T}}$ $>$ 80 GeV to reduce distortion of invariant
mass distribution and the dijet mass reconstructed from non-Higgs jets should
satisfy $m_{jj}>800$ GeV.

After offline event selection, a BDT discriminant is constructed from a set of
variables based on VBF topology ($m_{jj}$ , $\Delta\eta_{jj}$, jet width to
separate gluon jet from quark and so on). Figure 5 shows a BDT output
distribution. The BDT output is further split into three categories depending
on the BDT score. The signal extraction is performed by fitting the
$b\overline{b}$ invariant mass distributions of three BDT categories. Resonant
signals are modeled with Crystal ball functions and non-resonant backgrounds
are modeled with a second-order polynomial function. Figure 5 shows $m_{bb}$
distribution in the highest purity signal region. No significant excess over
background expectation is observed. An observed limit on signal strength is
4.0, to be compared with an expectation of $6.0^{+2.3}_{-1.7}$.

Figure 4: Representative leading-order Feynman diagrams for Higgs boson
production via vector boson fusion in association with a photon (left) and
non-resonant b anti-b production in association with a photon and jets
(middle, right) [12].

Figure 5: BDT output distribution (left). $m_{bb}$ distribution in the highest
BDT region [12].

##  3 Search for the Higgs boson decay to charm quark

A direct search for the Higgs decaying to a pair of charm quarks is reported
using the Higgs boson production in associated with a $Z$ boson, in the 2
lepton decay mode ($ZH\rightarrow\ell\ell c\overline{c}$) [13]. The analysis
strategy is similar to $ZH\rightarrow\ell\ell b\overline{b}$ analysis
discussed in Section 2.1. Direct $H\rightarrow c\overline{c}$ search is quite
challenging because it is difficult to separate $c$-jet from $b$-jet and
light-jet. However, dedicated flavor-tagging scheme is developed for
$H\rightarrow c\overline{c}$ search. Figure 6 shows an optimized $c$-tagging
working point, which has 41%, 25%, 5% $c$-tagging, $b$-tagging and light-
tagging efficiency, respectively. Analysis requires one or two $c$-tagged jet.
The final discriminant is fitted $m_{cc}$ distribution. Therefore, additional
$\Delta R_{cc}$ selection is applied to reduce background. Figure 6 shows
$m_{cc}$ distribution for the signal region with $p_{\mathrm{T}}^{V}$$>$ 150
GeV. An observed upper limit on $\sigma(pp\rightarrow ZH)\times
Br(H\rightarrow c\overline{c}$) is 2.7 pb, to be compared with an expectation
of $3.9^{+2.1}_{-1.1}$ pb at the 95% confidence level. The upper limit is
approximately 100 times higher than the SM expectation in the current data.

Figure 6: The $c$-jet tagging efficiency as a function of the $b$-jet and
light-jet (left). $m_{cc}$ distribution in the events with
$p_{\mathrm{T}}^{V}$$>$ 150 GeV (right) [13].

##  4 Search for the Higgs boson decay to dimuon

A direct search for the SM decaying to dimuon using the data corresponding to
an integrated luminosity of 36.1 fb-1is reported [14]. In the SM the branching
ratio of dimuon is extremely small, 0.022%. However, narrow dimuon mass peak
in the final state can be observed around 125 GeV. The targeted production
modes are gluon-fusion (ggF) and VBF which have first and second highest
production cross section. Due to large Drell-Yan irreducible background, it is
crucial to enhance signal-to-background ratio by the event categorization.
After opposite-sign dimuon and low $E_{\mathrm{T}}^{\mathrm{miss}}$and $b$-jet
veto selections, a BDT based on the VBF topology is constructed to
discriminate the VBF signal from the ggF and background. Figure 7 shows a BDT
distribution. The BDT distribution is split into three categories. Two VBF
categories, VBF tight and VBF loose are defined from BDT score. The remaining
low BDT events and events with less than two jets dominated by the ggF signal
are further subdivided according to $p_{\mathrm{T}}^{\mu\mu}$ and muon
$|\eta|$. To extract signal the $m_{\mu\mu}$ distributions of all signal
regions are fit simultaneously. Figure 7 shows $m_{\mu\mu}$ distribution in
the tight VBF category. No significant excess is observed in this search. An
observed (expected) upper limit on the signal strength at the 95% confidence
level is set to 3.0 (3.1).

Figure 7: The BDT output distribution (left). Dimuon mass distribution in the
tight VBF category (right) [14].

##  5 Conclusion

The several decay modes of Higgs to two fermions are searched using ATLAS Run
2 dataset at a center-of mass energy of $\sqrt{s}=13$ TeV in the proton-proton
collisions produced by the LHC. Two searches for $H\rightarrow b\overline{b}$
are performed using the production in associated with vector boson and VBF. An
excess over the expected background is observed with a significance of 3.6
standard deviations compared to an expectation of 4.0 in the combination with
Run 1 and Run 2 dataset. The measured signal strength with respect to the SM
expectation is found to be 0.90$\pm
0.18(\textrm{stat.})^{+0.21}_{-0.19}(\textrm{syst.})$. In the search using VBF
production, no significant excess is observed. 95% confidence level upper
limit on signal strength is set to 4.0, to be compared with expectation of
$6.0^{+2.3}_{-1.7}$.

Higgs decay to dimuon and $c\overline{c}$ (a pair of 2nd generation fermions)
are searched. No significant excess is observed in both searches. The observed
(expected) upper limit on signal strength at the 95% confidence level is set
to 3.0 (3.1) in the search for dimuon decay mode. An observed upper limit on
$\sigma(pp\rightarrow ZH)\times B(H\rightarrow c\overline{c}$) is set to 2.7
pb, to be compared with an expectation of $3.9^{+2.1}_{-1.1}$ pb at the 95%
confidence level in the search for the $c\overline{c}$ decay mode.

## References

  * [1] ATLAS Collaboration, Phys. Lett. B 716, 1 (2012)
  * [2] CMS Collaboration, Phys. Lett. B 716, 30 (2012)
  * [3] ATLAS Collaboration, Eur. Phys. J. C 76, no. 1, 6 (2016)
  * [4] ATLAS Collaboration, Eur. Phys. J. C 75, no. 10, 476 (2015) Erratum: [Eur. Phys. J. C 76, no. 3, 152 (2016)]
  * [5] ATLAS Collaboration, Phys. Lett. B 784, 345 (2018)
  * [6] ATLAS and CMS Collaborations, JHEP 1608, 045 (2016)
  * [7] CMS Collaboration, Phys. Rev. Lett. 120, no. 23, 231801 (2018)
  * [8] LHC Higgs Cross Section Working Group, doi:10.23731/CYRM-2017-002 arXiv:1610.07922 [hep-ph].
  * [9] ATLAS Collaboration, JINST 3, S08003 (2008).
  * [10] ATLAS Collaboration, JHEP 1712, 024 (2017)
  * [11] ATLAS Collaboration, JHEP 1501, 069 (2015)
  * [12] ATLAS Collaboration, ATLAS-CONF-2016-063,
(https://atlas.web.cern.ch/Atlas/GROUPS/PHYSICS/CONFNOTES/ATLAS-
CONF-2016-063/)

  * [13] ATLAS Collaboration, Phys. Rev. Lett. 120, no. 21, 211802 (2018)
  * [14] ATLAS Collaboration, Phys. Rev. Lett. 119, no. 5, 051802 (2017)