# Large-Scale Evaluation of Keyphrase Extraction Models

Ygor Gallina<EMAIL_ADDRESS>LS2N, Université de
NantesNantesFrance ,  Florian Boudin<EMAIL_ADDRESS>LS2N,
Université de NantesNantesFrance and  Béatrice Daille  beatrice.daille@univ-
nantes.fr LS2N, Université de NantesNantesFrance

(2020)

###### Abstract.

Keyphrase extraction models are usually evaluated under different, not
directly comparable, experimental setups. As a result, it remains unclear how
well proposed models actually perform, and how they compare to each other. In
this work, we address this issue by presenting a systematic large-scale
analysis of state-of-the-art keyphrase extraction models involving multiple
benchmark datasets from various sources and domains. Our main results reveal
that state-of-the-art models are in fact still challenged by simple baselines
on some datasets. We also present new insights about the impact of using
author- or reader-assigned keyphrases as a proxy for gold standard, and give
recommendations for strong baselines and reliable benchmark datasets.

Keyphrase generation, natural language processing, evaluation

††copyright: acmcopyright††journalyear: 2020††doi:
10.1145/1122445.1122456††conference: JCDL ’20: ACM/IEEE Joint Conference on
Digital Libraries; August 01–05, 2020; Xi’an, Shaanxi, China††booktitle: JCDL
’20: ACM/IEEE Joint Conference on Digital Libraries, August 01–05, 2020,
Xi’an, Shaanxi, China††isbn: 978-1-4503-XXXX-X/20/06††ccs: Information systems
Digital libraries and archives††ccs: Information systems Information
retrieval††ccs: Computing methodologies Information extraction

##  1\. Introduction

Keyphrases are single or multi-word lexical units that represent the main
concepts in a document (Evans and Zhai, 1996). They are particularly useful
for indexing, searching and browsing digital libraries (Barker et al., 1972;
Zhai, 1997; Gutwin et al., 1999; Witten et al., 2009), and have proven
themselves as effective features in many downstream natural language
processing tasks (Hulth and Megyesi, 2006; Litvak and Last, 2008; Berend,
2011). Still, most documents do not have assigned keyphrases, and manual
annotation is simply not a feasible option (Mao and Lu, 2017). There is
therefore a great need for automated methods to assign relevant keyphrases to
documents.

Automatic keyphrase extraction111Also referred to as keyphrase generation or
keyphrase annotation. – that is, the task of extracting keyphrases either from
the content of the document or from a controlled vocabulary – has received
much attention from the research community (Kim et al., 2010; Gollapalli et
al., 2015; Augenstein et al., 2017). Thus, many keyphrase extraction models
were proposed over the last years, ranging from early statistics-based models
(Witten et al., 1999), to popular graph-based ranking models (Mihalcea and
Tarau, 2004), and recent neural models (Meng et al., 2017). However, because
of the great discrepancies in experimental setups among past studies, it is
very difficult to compare and contrast the effectiveness of these models, and
even more so to assess the progress of the field as a whole.

More specifically, we observe striking differences in how models are
parameterized, evaluated and compared in previous work. To name just a few
examples, experiments are most often conducted on different benchmark
datasets, all of which differ in domain, size, language or quality of the gold
standard (that is, reference keyphrases supplied by authors, readers or
professional indexers). This not only makes the reported results hard to
contrast, but also has a profound impact on trained model performance (Gallina
et al., 2019). In addition, and since there is no consensus as to which
evaluation metric is most reliable for keyphrase extraction (Zesch and
Gurevych, 2009; Hussey et al., 2012; Hasan and Ng, 2014), diverse measures are
commonly seen in the literature, thus preventing any further direct
comparisons. Moreover, the evaluation of missing keyphrases – that is, gold
keyphrases that do not occur in the content of the document – is still an open
question and there is little agreement on whether they should be included or
not (Kim et al., 2010).

We strongly believe that this lack of empirical rigor is a real hindrance to
progress on keyphrase extraction, and that a systematic comparison of existing
models under the same conditions is needed to fully understand how they
actually perform. In this work, we resolve this issue by conducting the first
large-scale study on automatic keyphrase extraction. More precisely, we
present an extensive comparative analysis of state-of-the-art keyphrase
extraction models involving 9 benchmark datasets from various domains. To
ensure controlled, fair and reliable experiments, we embarked upon the
difficult process of re-implementing all of the models presented in this
paper222Link to the code will appear here after the review period. and pre-
processing the datasets in a unified and systematic way333Link to the datasets
will appear here after the review period..

Using these new large-scale experimental results, we seek to better understand
how well state-of-the-art models perform across sources, domains and
languages. We also go further than prior work and investigate the following
research questions:

  1. (1)

How much progress have we made on keyphrase extraction since early models?

  2. (2)

What is the impact of using non-expert gold standards, that is, author- or
reader-assigned keyphrases, when training and evaluating keyphrase extraction
models?

  3. (3)

Which baselines and benchmark datasets should be included in future work for a
better understanding of the pros and cons of a newly proposed model?

##  2\. Benchmark Datasets

Benchmark datasets for evaluating automatic keyphrase extraction cover a wide
range of sources ranging from scientific articles and web pages to twitter and
email messages. We collected 9 of the most widely used datasets which we
believe are representative of the different sources and domains found in
previous work. Detailed statistics for each selected dataset are shown in
Table 2. They are grouped into three categories that are outlined below:

Scientific articles:

Among the selected datasets, three are composed of full-text scientific
publications: ACM (Krapivin et al., 2009) and SemEval (Kim et al., 2010) about
computer science, and PubMed (Schutz, 2008) from the medical domain. Not
surprisingly, they contain only a small number of documents due to copyright
reasons. These datasets provide author-assigned keyphrases which serve as a
reasonable, but far from perfect, proxy for expert annotations. In the case of
SemEval, student annotators were hired to extend gold annotation labels.

Paper abstracts:

Scientific abstracts, often referred to as bibliographic records, are arguably
the most prevalent documents for benchmarking keyphrase extraction. They are
readily available in great quantities and come with author-assigned keyphrases
that can be used as gold standard. We gathered three datasets, all dealing
with the computer science domain: Inspec (Hulth, 2003), WWW (Caragea et al.,
2014) and KP20k (Meng et al., 2017). It is worth noting that with more than
half a million documents, KP20k is the largest dataset to date and one of the
few that is large enough to train neural models.

News articles:

News texts are the last source of documents present among the collected
datasets. Similar to paper abstracts, online news are available in large
quantities and can be easily mined from the internet. We selected the
following three datasets: DUC-2001 (Wan and Xiao, 2008), 500N-KPCrowd (Marujo
et al., 2012) and KPTimes (Gallina et al., 2019). The first two datasets
provide reader-assigned keyphrases, while KPTimes supplies indexer-assigned
key-phrases extracted from metadata and initially intended for search engines.
It is interesting to observe that only two datasets in our study, namely
Inspec and KPTimes, provide gold keyphrases annotated by professional
indexers.

Dataset | Ann. | Train | Test | #words | #kp | %abs
---|---|---|---|---|---|---
5pt. PubMed (Schutz, 2008) | $A$ | - | 1 320 | 5 323 | 5.4 | 16.9
ACM (Krapivin et al., 2009) | $A$ | - | 2 304 | 9 198 | 5.3 | 16.3
SemEval (Kim et al., 2010) | $A\cup R$ | 144 | 100 | 7 961 | 14.7 | 19.7
Scientific articles (avg.) | 7 494 | 8.5 | 17.6
5pt. Inspec (Hulth, 2003) | $I$ | 1 000 | 500 | 135 | 9.8 | 22.4
WWW (Caragea et al., 2014) | $A$ | - | 1 330 | 164 | 4.8 | 52.0
KP20k (Meng et al., 2017) | $A$ | 530K | 20K | 176 | 5.3 | 42.6
Paper abstracts (avg.) | 158 | 6.6 | 39.0
5pt. DUC-2001 (Wan and Xiao, 2008) | $R$ | - | 308 | 847 | 8.1 | 3.7
KPCrowd (Marujo et al., 2012) | $R$ | 450 | 50 | 465 | 46.2 | 11.2
KPTimes (Gallina et al., 2019) | $I$ | 260K | 10K | 921 | 5.0 | 54.7
News articles (avg.) | 744 | 19.8 | 23.2

Table 1. Statistics of the datasets. Gold annotation is supplied by authors
($A$), readers ($R$) or professional indexers ($I$). The number of documents
in the training and testing splits are shown. The average number of keyphrases
(#kp) and words (#words) per document, and the ratio of missing keyphrases
(%abs) are computed on the test set.

Datasets containing scientific articles or abstracts rely primarily on author-
assigned keyphrases as gold standard. They therefore exhibit similar
properties for the average number of ground truth keyphrases per document
($\approx 5$). On the other hand, articles are on average significantly longer
than abstracts ($\approx 7500$ words vs. $\approx 160$ words respectively) and
consequently reveal a much smaller fraction of missing keyphrases ($\approx
18\%$ vs. $\approx 39\%$ respectively). Datasets with reader-assigned
keyphrases exhibit the lowest numbers of missing keyphrases, which can be
explained by the fact that readers appear to produce gold-standard annotations
in an extractive fashion (Wang et al., 2015). We also confirmed this
empirically by computing the ratio of missing keyphrases in the author-
assigned ($24\%$) and reader-assigned ($17.5\%$) gold annotations of the
SemEval dataset.

In contrast, the opposite trend is observed for KPTimes that comes with gold
standards annotated by professional indexers and that shows the highest
percentage of missing keyphrases ($54.7\%$). This indicates the the more
abstractive nature of indexer-assigned keyphrases. Put differently, it is
known that non-expert annotations are less constrained and may include seldom-
used variants or misspellings (Sood et al., 2007), whereas indexers strive to
rely on a consistent terminology and assign the same keyphrase to all
documents for a given topic, even when it does not occur in these documents.

To investigate this further, we looked at how many variants of an index term,
in this case “artificial neural network”, could be found in the author-
assigned keyphrases of KP20k. All in all, we found dozens of variants for this
term, including “neural network”, “neural network (nns)”, “neural net”,
“artificial neural net” or “nn”. This apparent lack of annotation consistency
intuitively has two consequences: 1) it makes it harder for supervised
approaches to learn a good model, 2) it makes automatic evaluation much less
reliable as it is based on exact string matching.

It is important to stress that datasets containing scientific articles may
contain noisy texts. Indeed, most articles were automatically converted from
PDF format to plain text and thus are likely to contain irrelevant pieces of
text (e.g. muddled sentences, equations). Previous work show that noisy inputs
undermine the overall performance of keyphrase extraction models (Boudin et
al., 2016). In this study, we do not insist on a perfect input and we are
aware that reported results may be improved with an increase in pre-processing
effort.

##  3\. Models

Roughly speaking, previous works on keyphrase extraction can be divided into
two groups depending on whether they adopt a supervised learning procedure or
not. This section starts by introducing the baselines we will use in our
experiments, and then proceeds to describe the state-of-the-art keyphrase
extraction models we re-implemented sorted into the aforementioned two groups.

###  3.1. Baselines

Having strong baselines to compare with is a prerequisite for contrasting the
results of proposed models. In previous studies, various baselines were
considered, complicating the analysis and interpretation of the reported
results. Our stance here is to establish three baselines, each associated with
a particular feature that is commonly used in keyphrase extraction models. All
baselines are also unsupervised, allowing their use and performance analysis
on any of the benchmark datasets

Keyphrase position is a strong signal for both unsupervised and supervised
models, simply because texts are usually written so that the most important
ideas go first (Marcu, 1997). In single document summarization for example,
the lead baseline –that is, the first sentences from the document–, while
incredibly simple, is still a competitive baseline (Kedzie et al., 2018).
Similar to the lead baseline, we propose the FirstPhrases baseline that
extracts the first $N$ keyphrase candidates from a document. We are not aware
of any previous work reporting that baseline, yet, as we will see in §5, it
achieves remarkably good results.

Graph-based ranking models for keyphrase extraction are, perhaps, the most
popular models in the literature. Therefore, as a second baseline, we use
TextRank (Mihalcea and Tarau, 2004), which weights keyphrase candidates using
a random walk over a word-graph representation of the document. In a nutshell,
TextRank defines the importance of a word in terms of how it relates to other
words in the document, and ranks candidates according to the words they
contain.

The third baseline, TF$\times$IDF (Salton and Buckley, 1988), have been
repeatedly used in previous comparative studies (Kim et al., 2010; Meng et
al., 2017, inter alia). In contrast with the other two baselines that do no
require any resources whatsoever (beyond the document itself), TF$\times$IDF
makes use of the statistics collected from unlabelled data to weight keyphrase
candidates. As such, it often gives better results, in some cases even on par
with state-of-the-art models (Ye and Wang, 2018).

###  3.2. Unsupervised models

Annotated data are not always available or easy to obtain, which motivates the
further development of unsupervised models for keyphrase extraction. Besides,
looking back at previous work, most attempts to address this problem employ
unsupervised approaches. In this study, we selected three recent state-of-the-
art models based on their reported performance.

The first model we investigate is PositionRank (Florescu and Caragea, 2017), a
graph-based model that incorporates two features (position and frequency) into
a biased PageRank algorithm. This model operates at the word level, and
assigns a score to each candidate using the sum of its individual word scores.
As such, it suffers from over-generation errors444These errors occur when a
model correctly outputs a keyphrase because it contains an important word, but
at the same time erroneously predicts other keyphrases because they contain
the same word. (Hasan and Ng, 2014), but still achieves good performance on
short texts.

The second model we consider, MPRank (Boudin, 2018), relies on a multipartite
graph representation to enforce topical diversity while ranking keyphrase
candidates. It includes a mechanism to incorporate keyphrase selection
preferences in order to introduce a bias towards candidates occurring first in
the document. MultipartiteRank was shown to consistently outperform other
unsupervised graph-based ranking models.

Both aforementioned models only exploit the document itself to extract
keyphrases. The third model we include, EmbedRank (Bennani-Smires et al.,
2018), leverages sentence embeddings for ranking keyphrase candidates.
Candidates are weighted according to their cosine distance to the document
embedding, while diversity in the selected keyphrases is promoted using
Maximal Marginal Relevance (MMR) (Goldstein and Carbonell, 1998). Despite its
simplicity, this model was shown to outperform other unsupervised models on
short texts (abstracts and news).

###  3.3. Supervised models

Supervised models can be further divided into two categories, depending on
whether they rely on a neural network or not.

Traditional supervised models treat the keyphrase extraction problem as a
binary classification task. Here, we include such a model, namely Kea (Witten
et al., 1999), in order to precisely quantify the performance gap with recent
neural-based models. KEA uses a Naive Bayes classifier trained on a set of
only two handcrafted features we have elected as baseline features: the
TF$\times$IDF score of the candidate and the normalized position of its first
occurrence in the document. Previous work has reported confusing and
conflicting results555On SemEval, (Meng et al., 2017) report an F@10 score of
$2.6$ while (Boudin, 2016) report a score of $19.3$. for Kea, raising
questions about how it actually performs.

Neural models for keyphrase extraction rely on an encoder-decoder architecture
(Cho et al., 2014; Sutskever et al., 2014) with an attention mechanism
(Bahdanau et al., 2014; Luong et al., 2015). Training these models require
large amounts of annotated training data, and is therefore only possible on
the KP20k and KPTimes datasets. The second supervised model we include in this
study is CopyRNN (Meng et al., 2017), an encoder-decoder model that
incorporates a copying mechanism (Gu et al., 2016) in order to be able to
predict phrases that rarely occur. When properly trained, this model was shown
to be very effective in extracting keyphrases from scientific abstracts.

The third supervised model we use, CorrRNN (Chen et al., 2018), extends the
aforementioned model by introducing correlation constraints. It employs a
coverage mechanism (Tu et al., 2016) that diversifies attention distributions
to increase topic coverage, and a review mechanism to avoid generating
duplicates. As such, it produces more diverse and less redundant keyphrases.

Note that only neural models have the ability to generate missing keyphrases,
which in theory gives them a clear advantage over the other models.

##  4\. Experimental settings

In addition to the variation in the choice of benchmark datasets and
baselines, there are also major discrepancies in parameter settings and
evaluation metrics between previous studies. For example, there is no point in
contrasting the results in (Meng et al., 2017), (Florescu and Caragea, 2017)
and (Teneva and Cheng, 2017), three papers about keyphrase extraction
published in the same year at ACL, since neither benchmark datasets, parameter
settings nor evaluation metrics are comparable. To address this problem, we
use the same pre-processing tools, parameter settings and evaluation procedure
across all our experiments.

| Scientific articles | Paper abstracts | News articles
---|---|---|---
| PubMed | ACM | SemEval | Inspec | WWW | KP20k | DUC-2001 | KPCrowd | KPTimes
Model | $\text{F}@10$ | MAP | $\text{F}@10$ | MAP | $\text{F}@10$ | MAP | $\text{F}@10$ | MAP | $\text{F}@10$ | MAP | $\text{F}@10$ | MAP | $\text{F}@10$ | MAP | $\text{F}@10$ | MAP | $\text{F}@10$ | MAP
FirstPhrases | 15.4 | 14.7 | 13.6 | 13.5 | 13.8 | 10.5 | 29.3 | 27.9 | 10.2 |  09.8 | 13.5 | 12.6 | 24.6 | 22.3 | 17.1 | 16.5 |  09.2 |  08.4
TextRank |  01.8 |  01.8 |  02.5 |  02.4 |  03.5 |  02.3 | 35.8 | 31.4 |  08.4 |  05.6 | 10.2 |  07.4 | 21.5 | 19.4 |  07.1 |  09.5 |  02.7 |  02.5
TF$\times$IDF | 16.7 | 16.9 | 12.1 | 11.4 | 17.7 | 12.7 | 36.5 | 34.4 |  09.3 | 10.1 | 11.6 | 12.3 | 23.3 | 21.6 | 16.9 | 15.8 |  09.6 |  09.4
PositionRank |  04.9 |  04.6 |  05.7 |  04.9 |  06.8 |  04.1 | 34.2 | 32.2 | 11.6† |  08.4 | 14.1† | 11.2 | 28.6† | 28.0† | 13.4 | 12.7 |  08.5 |  06.6
MPRank | 15.8 | 15.0 | 11.6 | 11.0 | 14.3 | 10.6 | 30.5 | 29.0 | 10.8† | 10.4 | 13.6† | 13.3† | 25.6 | 24.9† | 18.2 | 17.0 | 11.2† | 10.1†
EmbedRank |  03.7 |  03.2 |  02.1 |  02.1 |  02.5 |  02.0 | 35.6 | 32.5 | 10.7† |  07.7 | 12.4 | 10.0 | 29.5† | 27.5† | 12.4 | 12.4 |  04.0 |  03.3
Kea | 18.6† | 18.6† | 14.2† | 13.3 | 19.5† | 14.7† | 34.5 | 33.2 | 11.0† | 10.9† | 14.0† | 13.8† | 26.5† | 24.5† | 17.3 | 16.7 | 11.0† | 10.8†
CopyRNN | 24.2† | 25.4† | 24.4† | 26.3† | 20.3† | 13.8 | 28.2 | 26.4 | 22.2† | 24.9† | 25.4† | 28.7† | 10.5 |  07.2 |  08.4 |  04.2 | 39.3† | 50.9†
CorrRNN | 20.8† | 19.4† | 21.1† | 20.5† | 19.4 | 10.9 | 27.9 | 23.6 | 19.9† | 20.3† | 21.8† | 22.7 | 10.5 |  06.5 |  07.8 |  03.2 | 20.5† | 20.3†

Table 2. Performance of keyphrase extraction models. † indicates significance
over the baselines.

###  4.1. Parameter settings

We pre-process all the texts using the Stanford CoreNLP suite (Manning et al.,
2014) for tokenization, sentence splitting and part-of-speech (POS) tagging.
All non-neural models operate on a set of keyphrase candidates, extracted from
the input document. Selecting appropriate candidates is particularly important
since it determines the upper bound on recall, and the amount of irrelevant
candidates that models will have to deal with. For a fair and meaningful
comparison, we use the same candidate selection heuristic across models. We
follow the recommendation by Wang et al. (2014) and select the sequences of
adjacent nouns with one or more preceding adjectives of length up to five
words. Candidates are further filtered by removing those shorter than 3
characters or containing non-alphanumeric symbols.

We implemented the neural models in PyTorch (Paszke et al., 2017) using
AllenNLP (Gardner et al., 2018), and the non-neural models using the pke
toolkit (Boudin, 2016). As neural models require large amounts of annotated
data to be trained, we trained our models on the KP20k dataset for both
scientific papers and abstracts, and on KPTimes for news texts. We compute
Document Frequency (DF) counts and learn Kea models on training sets. For
datasets without training splits, we apply a leave-one-out cross-validation
procedure on the test sets for calculating DF counts and training models. We
use the optimal parameters suggested by the authors for each model, and
leverage pre-trained sentence embeddings666https://github.com/epfml/sent2vec
for EmbedRank. We also found out that the training set of KP20k contains a
non-negligible number of documents from the test sets of other datasets. We
removed those documents prior to training.

###  4.2. Evaluation metrics

Although there is no consensus as to which metric is the most reliable for
keyphrase extraction, a popular evaluation strategy is to compare the top $k$
extracted keyphrases against the gold standard. We adopt this strategy and
report the f-measure at the top 10 extracted keyphrases. In previous work, we
often see differences in how gold standards are handled during evaluation. For
example, some studies evaluate their models on the present and missing
portions of the gold standard separately (Meng et al., 2017; Ye and Wang,
2018; Chen et al., 2018, inter alia), whereas other work use the entire gold
standard (Florescu and Caragea, 2017; Boudin, 2018, inter alia). We chose the
latter because recent models, in addition to extracting keyphrases from the
content of the document, are able to generate missing keyphrases. Following
common practice, gold standard and output keyphrases are stemmed to reduce the
number of mismatches. One issue with the f-measure is that the ranks of the
correct keyphrases are not taken into account. To evaluate the overall ranking
performance of the models, we also report the Mean Average Precision (MAP)
scores of the ranked lists of keyphrases. We use the Student’s paired t-test
to assess statistical significance at the $0.05$ level.

###  4.3. Replicability of results

In Table 3, we compare the results of our re-implementations against those
reported in the original papers. We note that all models show comparable
results. We observe the largest differences with original scores for CopyRNN
($+2$) and CorrRNN ($-4.3$) that can be easily explained by minor differences
in training parameters.

Model | Dataset (metric) | Orig. | Ours
---|---|---|---
PositionRank | WWW (F$@$8) | 12.3 | 11.7
MPRank | SemEval-2010 (F$@$10) | 14.5 | 14.3
EmbedRank | Inspec (F$@$10) | 37.1 | 35.6
CopyRNN | KP20k (F$@$10 on present) | 26.2 | 28.2
CorrRNN | ACM (F$@$10 on present) | 27.8 | 23.5
Table 3. Original vs. re-implementation scores.

##  5\. Results

Results are presented in Table 2. First of all, we notice that no model
significantly outperforms the baselines on all datasets. This is rather
surprising, as one would expect that neural models would be consistently
better than a simple TF$\times$IDF model for example. Rather, we see that the
TF$\times$IDF baseline is very competitive on long documents, while the
FirstPhrases baseline performs remarkably well, especially on news texts.
Still, overall, CopyRNN achieves the best performance with, in the case of
KPTimes, MAP scores exceeding 50%. When we look at only unsupervised models,
MPRank achieves the best results across datasets. Also, it comes as no
surprise that Kea exhibits strong performance across datasets because it
combines two effective features, as demonstrated by the results of the
TF$\times$IDF and FirstPhrases baselines. Conversely, despite the addition of
mechanisms for promoting diversity in the output, CorrRNN is almost always
outperformed by CopyRNN, suggesting that the added correlation constraints are
not effective at filtering out spurious keyphrases.

In light of the above, we can now answer the following question: “How much
progress have we made since early models?”. It is clear that neural-based
models are the new state-of-the-art for keyphrase extraction, achieving F@10
scores up to three times that of previous models. That being said, CopyRNN,
which is the best overall model, fails to consistently outperform the
baselines on all datasets. One reason for that is the limited generalization
ability of neural-based models (Meng et al., 2017; Chen et al., 2018; Gallina
et al., 2019), which means that their performance degrades on documents that
differ from the ones encountered during training. This is besides confirmed by
the extremely low performance of these models on DUC-2001 and KPCrowd. Much
more work needs to be done in tackling this issue if neural models are to
substitute for older supervised models. Perhaps most disappointing is the fact
that state-of-the-art unsupervised models are still challenged by the
TF$\times$IDF baseline. Here, we suspect the reasons are twofold. First, the
models we have investigated do not use in-domain data which may not only limit
their performance, but also, as in the case of EmbedRank that uses out-of-
domain (Wikipedia) data, be detrimental to their performance. Second, unlike
neural generative models, they are not able to produce keyphrases that do not
occur in the source document, further limiting their potential effectiveness.

As outlined in §2, gold standards provided by lay annotators, such as authors
and readers, exhibit strong inconsistency issues. One might therefore wonder
“What is the impact of non-expert annotations on training and evaluating
keyphrase extraction models?”. Intuitively, models evaluated against these
annotations are likely to receive lower scores because they make training more
difficult (that is, assigning different keyphrases to documents about the same
topic may confuse the model) while increasing the number of false negatives
during evaluation. This is exactly what we observe in Table 2 where the best
scores for Inspec and KPTimes, whose gold standards are provided by
professional indexers, are higher in magnitude than those of the other
datasets. Precisely quantifying how much impact lay annotations have on
performance is no easy task as it implies a double-annotation process by both
expert and non-expert annotators. Luckily enough, a small sample of documents
from Inspec are also found in KP20k, allowing us to compare the performance of
keyphrases models between both annotation types. Results are shown in Table 4.
First, we see that overall performance is nearly cut in half when evaluating
against author-provided gold standard, suggesting that reported scores in
previous studies are arguably underestimated. Second, neural models again do
not show their superiority against indexer-assigned keyphrases, which
advocates the need for more experiments on datasets that include expert
annotations.

| $\text{F}@10$ | MAP
---|---|---
Model | I | A | I | A
FirstPhrases | 25.8 | 13.7 | 26.1 | 13.2
TextRank | 33.4 | 12.2 | 29.6 |  09.3
TF$\times$IDF | 34.6 | 14.2 | 33.3 | 16.1
PositionRank | 32.9 | 15.9 | 31.0 | 13.0
MPRank | 26.4 | 13.8 | 27.6 | 13.6
EmbedRank | 34.3 | 15.3 | 31.3 | 11.5
Kea | 32.5 | 15.2 | 31.9 | 15.9
CopyRNN | 33.7 | 28.9‡ | 29.8 | 33.8‡
CorrRNN | 28.6 | 25.3 | 24.2 | 28.2
Avg. | 31.3 | 17.2 | 29.4 | 17.2
Table 4. Results on a subset of 55 documents from Inspec for indexer (I) and
author (A) gold annotations. ‡ indicates significance over every other model.
Figure 1. Average number of keyphrases in common between model outputs.

The third question we want to address in this study is “Which baselines and
benchmark datasets should be included in future work for a better
understanding of the pros and cons of a newly proposed model?”. Having strong
baselines to compare with is of utmost importance, and our results give an
indication of which model is relevant. When properly trained, neural models
drastically outperform all other models and represent the state-of-the-art.
Since CopyRNN achieve the best results, it should be included in future work
for comparison. In an unsupervised setting, or in a data-sparse scenario where
neural models can not be applied, the picture is less clear. To help us
understand which model is worth investigating, we conducted an additional set
of experiments aimed at comparing the outputs from all models in a pairwise
manner. The motivation behind these experiments is that including multiple
models that behave similarly is of limited interest. Similarities between
model outputs, viewed in terms of the number of keyphrases in common, are
graphed as a heatmap in Figure 1. Overall, we observe different patterns for
each source of documents. The shorter the document is, the more similar
outputs are, which is mostly due to a smaller search space (that is, a smaller
number of keyphrase candidates). We note that the three best unsupervised
models, namely FirstPhrases, MPRank and TF$\times$IDF, generate very similar
keyphrases (up to 42% identical). Considering this, and given their reported
performances (Table 2), we argue that TF$\times$IDF (or KEA if seed training
data is available) should be considered as strong unsupervised baseline in
subsequent work.

These recommendations of baselines also affect the choice of which benchmark
datasets one has to use. As neural models are data-hungry, KP20k and KPTimes
are the default options for paper abstracts and news articles. For scientific
articles, we recommend using SemEval for two reasons: 1) it is widely used by
existing studies; and 2) it provides a double-annotated gold standard (author-
and reader-assigned keyphrases) that alleviates annotation inconsistencies to
some extent.

Our experiments highlight several issues in evaluating keyphrase extraction
models with existing benchmark datasets. Another way of assessing the
effectiveness of these models would be to explore their impact on other tasks
as an extrinsic evaluation. To the best of our knowledge, there is no
previously published research on that matter despite many downstream tasks
that already benefit from keyphrase information such as article recommendation
(Collins and Beel, 2019) or browsing interfaces (Gutwin et al., 1999) in
digital libraries. This points to an interesting future direction that allows
for a deeper understanding of the limitations of current models.

##  6\. Conclusion

This paper presents a large scale evaluation of keyphrase extraction models
conducted on multiple benchmark datasets from different sources and domains.
Results indicate that keyphrase extraction is still an open research question,
with state-of-the-art neural-based models still challenged by simple baselines
on some datasets. We hope that this work will serve as a point of departure
for more rigorous analysis and evaluation of proposed keyphrase extraction
models. We provide all the code and data on a public repository777Link to the
repository will appear here after the review period., as well as a public
leaderboard to facilitate the comparison between models.

## References

  * (1)
  * Augenstein et al. (2017) Isabelle Augenstein, Mrinal Das, Sebastian Riedel, Lakshmi Vikraman, and Andrew McCallum. 2017\.  SemEval 2017 Task 10: ScienceIE - Extracting Keyphrases and Relations from Scientific Publications. In _Proceedings of the 11th International Workshop on Semantic Evaluation (SemEval-2017)_. Association for Computational Linguistics, Vancouver, Canada, 546–555.  http://www.aclweb.org/anthology/S17-2091
  * Bahdanau et al. (2014) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014\.  Neural machine translation by jointly learning to align and translate.  _arXiv preprint arXiv:1409.0473_ (2014).
  * Barker et al. (1972) Frances H Barker, Douglas C Veal, and Barry K Wyatt. 1972\.  Comparative efficiency of searching titles, abstracts, and index terms in a free-text data base.  _Journal of Documentation_ 28, 1 (1972), 22–36.
  * Bennani-Smires et al. (2018) Kamil Bennani-Smires, Claudiu Musat, Andreea Hossmann, Michael Baeriswyl, and Martin Jaggi. 2018\.  Simple Unsupervised Keyphrase Extraction using Sentence Embeddings. In _Proceedings of the 22nd Conference on Computational Natural Language Learning_. Association for Computational Linguistics, Brussels, Belgium, 221–229.  http://www.aclweb.org/anthology/K18-1022
  * Berend (2011) Gábor Berend. 2011\.  Opinion Expression Mining by Exploiting Keyphrase Extraction. In _Proceedings of 5th International Joint Conference on Natural Language Processing_. Asian Federation of Natural Language Processing, Chiang Mai, Thailand, 1162–1170.  http://www.aclweb.org/anthology/I11-1130
  * Boudin (2016) Florian Boudin. 2016\.  pke: an open source python-based keyphrase extraction toolkit. In _Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: System Demonstrations_. The COLING 2016 Organizing Committee, Osaka, Japan, 69–73.  http://aclweb.org/anthology/C16-2015
  * Boudin (2018) Florian Boudin. 2018\.  Unsupervised Keyphrase Extraction with Multipartite Graphs. In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_. Association for Computational Linguistics, New Orleans, Louisiana, 667–672.  http://www.aclweb.org/anthology/N18-2105
  * Boudin et al. (2016) Florian Boudin, Hugo Mougard, and Damien Cram. 2016\.  How Document Pre-processing affects Keyphrase Extraction Performance. In _Proceedings of the 2nd Workshop on Noisy User-generated Text (WNUT)_. The COLING 2016 Organizing Committee, Osaka, Japan, 121–128.  http://aclweb.org/anthology/W16-3917
  * Caragea et al. (2014) Cornelia Caragea, Florin Adrian Bulgarov, Andreea Godea, and Sujatha Das Gollapalli. 2014\.  Citation-Enhanced Keyphrase Extraction from Research Papers: A Supervised Approach. In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Association for Computational Linguistics, Doha, Qatar, 1435–1446.  http://www.aclweb.org/anthology/D14-1150
  * Chen et al. (2018) Jun Chen, Xiaoming Zhang, Yu Wu, Zhao Yan, and Zhoujun Li. 2018.  Keyphrase Generation with Correlation Constraints. In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, Brussels, Belgium, 4057–4066.  http://www.aclweb.org/anthology/D18-1439
  * Cho et al. (2014) Kyunghyun Cho, Bart van Merrienboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014\.  Learning Phrase Representations using RNN Encoder–Decoder for Statistical Machine Translation. In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Association for Computational Linguistics, Doha, Qatar, 1724–1734.  http://www.aclweb.org/anthology/D14-1179
  * Collins and Beel (2019) Andrew Collins and Jöran Beel. 2019.  Document Embeddings vs. Keyphrases vs. Terms for Recommender Systems: A Large-Scale Online Evaluation. In _19th ACM/IEEE Joint Conference on Digital Libraries, JCDL 2019, Champaign, IL, USA, June 2-6, 2019_. 130–133.  https://doi.org/10.1109/JCDL.2019.00027
  * Evans and Zhai (1996) David A. Evans and Chengxiang Zhai. 1996.  Noun Phrase Analysis in Large Unrestricted Text for Information Retrieval. In _Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics, Santa Cruz, California, USA, 17–24.  https://doi.org/10.3115/981863.981866
  * Florescu and Caragea (2017) Corina Florescu and Cornelia Caragea. 2017.  PositionRank: An Unsupervised Approach to Keyphrase Extraction from Scholarly Documents. In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Association for Computational Linguistics, Vancouver, Canada, 1105–1115.  http://aclweb.org/anthology/P17-1102
  * Gallina et al. (2019) Ygor Gallina, Florian Boudin, and Beatrice Daille. 2019\.  KPTimes: A Large-Scale Dataset for Keyphrase Generation on News Documents. In _Proceedings of the 12th International Conference on Natural Language Generation_. Association for Computational Linguistics, Tokyo, Japan, 130–135.  https://doi.org/10.18653/v1/W19-8617
  * Gardner et al. (2018) Matt Gardner, Joel Grus, Mark Neumann, Oyvind Tafjord, Pradeep Dasigi, Nelson F. Liu, Matthew Peters, Michael Schmitz, and Luke Zettlemoyer. 2018.  AllenNLP: A Deep Semantic Natural Language Processing Platform. In _Proceedings of Workshop for NLP Open Source Software (NLP-OSS)_. Association for Computational Linguistics, Melbourne, Australia, 1–6.  https://doi.org/10.18653/v1/W18-2501
  * Goldstein and Carbonell (1998) Jade Goldstein and Jaime Carbonell. 1998.  SUMMARIZATION: (1) USING MMR FOR DIVERSITY- BASED RERANKING AND (2) EVALUATING SUMMARIES. In _Proceedings of the TIPSTER Text Program: Phase III_. Association for Computational Linguistics, Baltimore, Maryland, USA, 181–195.  https://doi.org/10.3115/1119089.1119120
  * Gollapalli et al. (2015) Sujatha Das Gollapalli, Cornelia Caragea, Xiaoli Li, and C. Lee Giles (Eds.). 2015.  _Proceedings of the ACL 2015 Workshop on Novel Computational Approaches to Keyphrase Extraction_.  Association for Computational Linguistics, Beijing, China.  http://www.aclweb.org/anthology/W15-36
  * Gu et al. (2016) Jiatao Gu, Zhengdong Lu, Hang Li, and Victor O.K. Li. 2016\.  Incorporating Copying Mechanism in Sequence-to-Sequence Learning. In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Association for Computational Linguistics, Berlin, Germany, 1631–1640.  http://www.aclweb.org/anthology/P16-1154
  * Gutwin et al. (1999) Carl Gutwin, Gordon Paynter, Ian Witten, Craig Nevill-Manning, and Eibe Frank. 1999\.  Improving Browsing in Digital Libraries with Keyphrase Indexes.  _Decis. Support Syst._ 27, 1-2 (Nov. 1999), 81–104.  https://doi.org/10.1016/S0167-9236(99)00038-X
  * Hasan and Ng (2014) Kazi Saidul Hasan and Vincent Ng. 2014.  Automatic Keyphrase Extraction: A Survey of the State of the Art. In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Association for Computational Linguistics, Baltimore, Maryland, 1262–1273.  http://www.aclweb.org/anthology/P14-1119
  * Hulth (2003) Anette Hulth. 2003\.  Improved Automatic Keyword Extraction Given More Linguistic Knowledge. In _Proceedings of the 2003 Conference on Empirical Methods in Natural Language Processing_ , Michael Collins and Mark Steedman (Eds.). 216–223.  http://www.aclweb.org/anthology/W03-1028.pdf
  * Hulth and Megyesi (2006) Anette Hulth and Beáta B. Megyesi. 2006.  A Study on Automatically Extracted Keywords in Text Categorization. In _Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics, Sydney, Australia, 537–544.  https://doi.org/10.3115/1220175.1220243
  * Hussey et al. (2012) Richard Hussey, Shirley Williams, Richard Mitchell, and Ian Field. 2012.  A comparison of automated keyphrase extraction techniques and of automatic evaluation vs. human evaluation.  _International Journal on Advances in Life Sciences_ 4, 3 and 4 (2012), 136–153.  http://centaur.reading.ac.uk/32266/
  * Kedzie et al. (2018) Chris Kedzie, Kathleen McKeown, and Hal Daume III. 2018\.  Content Selection in Deep Learning Models of Summarization. In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, Brussels, Belgium, 1818–1828.  http://www.aclweb.org/anthology/D18-1208
  * Kim et al. (2010) Su Nam Kim, Olena Medelyan, Min-Yen Kan, and Timothy Baldwin. 2010.  SemEval-2010 Task 5 : Automatic Keyphrase Extraction from Scientific Articles. In _Proceedings of the 5th International Workshop on Semantic Evaluation_. Association for Computational Linguistics, Uppsala, Sweden, 21–26.  http://www.aclweb.org/anthology/S10-1004
  * Krapivin et al. (2009) Mikalai Krapivin, Aliaksandr Autaeu, and Maurizio Marchese. 2009.  _Large dataset for keyphrases extraction_.  Technical Report. University of Trento.
  * Litvak and Last (2008) Marina Litvak and Mark Last. 2008.  Graph-Based Keyword Extraction for Single-Document Summarization. In _Coling 2008: Proceedings of the workshop Multi-source Multilingual Information Extraction and Summarization_. Coling 2008 Organizing Committee, Manchester, UK, 17–24.  http://www.aclweb.org/anthology/W08-1404
  * Luong et al. (2015) Thang Luong, Hieu Pham, and Christopher D. Manning. 2015\.  Effective Approaches to Attention-based Neural Machine Translation. In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, Lisbon, Portugal, 1412–1421.  http://aclweb.org/anthology/D15-1166
  * Manning et al. (2014) Christopher D. Manning, Mihai Surdeanu, John Bauer, Jenny Finkel, Steven J. Bethard, and David McClosky. 2014.  The Stanford CoreNLP Natural Language Processing Toolkit. In _Association for Computational Linguistics (ACL) System Demonstrations_. 55–60.  http://www.aclweb.org/anthology/P/P14/P14-5010
  * Mao and Lu (2017) Yuqing Mao and Zhiyong Lu. 2017.  MeSH Now: automatic MeSH indexing at PubMed scale via learning to rank.  _Journal of Biomedical Semantics_ 8, 1 (17 Apr 2017), 15.  https://doi.org/10.1186/s13326-017-0123-3
  * Marcu (1997) Daniel Marcu. 1997\.  The Rhetorical Parsing of Unrestricted Natural Language Texts. In _Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics, Madrid, Spain, 96–103.  https://doi.org/10.3115/976909.979630
  * Marujo et al. (2012) Luís Marujo, Anatole Gershman, Jaime Carbonell, Robert Frederking, and JoaÌfo P. Neto. 2012\.  Supervised Topical Key Phrase Extraction of News Stories using Crowdsourcing, Light Filtering and Co-reference Normalization. In _Proceedings of the Eight International Conference on Language Resources and Evaluation (LREC’12)_ (23-25), Nicoletta Calzolari (Conference Chair), Khalid Choukri, Thierry Declerck, Mehmet Uğur Doğan, Bente Maegaard, Joseph Mariani, Asuncion Moreno, Jan Odijk, and Stelios Piperidis (Eds.). European Language Resources Association (ELRA), Istanbul, Turkey.
  * Meng et al. (2017) Rui Meng, Sanqiang Zhao, Shuguang Han, Daqing He, Peter Brusilovsky, and Yu Chi. 2017\.  Deep Keyphrase Generation. In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Association for Computational Linguistics, 582–592.  https://doi.org/10.18653/v1/P17-1054
  * Mihalcea and Tarau (2004) Rada Mihalcea and Paul Tarau. 2004.  TextRank: Bringing Order into Texts. In _Proceedings of EMNLP 2004_ , Dekang Lin and Dekai Wu (Eds.). Association for Computational Linguistics, Barcelona, Spain, 404–411.
  * Paszke et al. (2017) Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017\.  Automatic differentiation in pytorch. In _NIPS 2017 Workshop Autodiff_.
  * Salton and Buckley (1988) Gerard Salton and Christopher Buckley. 1988.  Term-weighting approaches in automatic text retrieval.  _Information Processing & Management_ 24, 5 (1988), 513 – 523.  https://doi.org/10.1016/0306-4573(88)90021-0
  * Schutz (2008) Alexander Thorsten Schutz. 2008\.  Keyphrase extraction from single documents in the open domain exploiting linguistic and statistical methods.  _Master’s thesis, National University of Ireland_ (2008).
  * Sood et al. (2007) Sanjay Sood, Sara Owsley, Kristian J. Hammond, and Larry Birnbaum. 2007.  TagAssist: Automatic Tag Suggestion for Blog Posts. In _Proceedings of the First International Conference on Weblogs and Social Media, ICWSM 2007, Boulder, Colorado, USA, March 26-28, 2007_.  http://www.icwsm.org/papers/paper10.html
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014\.  Sequence to Sequence Learning with Neural Networks.  In _Advances in Neural Information Processing Systems 27_ , Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (Eds.). Curran Associates, Inc., 3104–3112.  http://papers.nips.cc/paper/5346-sequence-to-sequence-learning-with-neural-networks.pdf
  * Teneva and Cheng (2017) Nedelina Teneva and Weiwei Cheng. 2017.  Salience Rank: Efficient Keyphrase Extraction with Topic Modeling. In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_. Association for Computational Linguistics, Vancouver, Canada, 530–535.  http://aclweb.org/anthology/P17-2084
  * Tu et al. (2016) Zhaopeng Tu, Zhengdong Lu, Yang Liu, Xiaohua Liu, and Hang Li. 2016.  Modeling Coverage for Neural Machine Translation. In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Association for Computational Linguistics, Berlin, Germany, 76–85.  https://doi.org/10.18653/v1/P16-1008
  * Wan and Xiao (2008) Xiaojun Wan and Jianguo Xiao. 2008.  Single Document Keyphrase Extraction Using Neighborhood Knowledge. In _Proceedings of the 23rd National Conference on Artificial Intelligence - Volume 2_ _(AAAI’08)_. AAAI Press, 855–860.  http://dl.acm.org/citation.cfm?id=1620163.1620205
  * Wang et al. (2014) Rui Wang, Wei Liu, and Chris McDonald. 2014.  How Preprocessing Affects Unsupervised Keyphrase Extraction. In _Computational Linguistics and Intelligent Text Processing_ , Alexander Gelbukh (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 163–176.
  * Wang et al. (2015) Rui Wang, Wei Liu, and Chris McDonald. 2015.  Using Word Embeddings to Enhance Keyword Identification for Scientific Publications. In _Databases Theory and Applications_ , Mohamed A. Sharaf, Muhammad Aamir Cheema, and Jianzhong Qi (Eds.). Springer International Publishing, Cham, 257–268.
  * Witten et al. (2009) Ian H Witten, David Bainbridge, and David M Nichols. 2009\.  _How to build a digital library_.  Morgan Kaufmann.
  * Witten et al. (1999) Ian H. Witten, Gordon W. Paynter, Eibe Frank, Carl Gutwin, and Craig G. Nevill-Manning. 1999.  KEA: Practical Automatic Keyphrase Extraction. In _Proceedings of the Fourth ACM Conference on Digital Libraries_ _(DL ’99)_. ACM, New York, NY, USA, 254–255.  https://doi.org/10.1145/313238.313437
  * Ye and Wang (2018) Hai Ye and Lu Wang. 2018\.  Semi-Supervised Learning for Neural Keyphrase Generation. In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, Brussels, Belgium, 4142–4153.  http://www.aclweb.org/anthology/D18-1447
  * Zesch and Gurevych (2009) Torsten Zesch and Iryna Gurevych. 2009.  Approximate Matching for Evaluating Keyphrase Extraction. In _Proceedings of the International Conference RANLP-2009_. Association for Computational Linguistics, Borovets, Bulgaria, 484–489.  http://www.aclweb.org/anthology/R09-1086
  * Zhai (1997) Chengxiang Zhai. 1997\.  Fast Statistical Parsing of Noun Phrases for Document Indexing. In _Fifth Conference on Applied Natural Language Processing_. Association for Computational Linguistics, Washington, DC, USA, 312–319.  https://doi.org/10.3115/974557.974603


Q-Map: Quantum Circuit Implementation of Boolean Functions

Hassan Hajjdiab1,*, Ashraf Khalil2, Hichem Eleuch3,4,5,

1 Computer Science and Software Engineering Department, Concordia University,
Montreal, Quebec, Canada; Email<EMAIL_ADDRESS>

2 College of Technological Innovation, Zayed University, Abu Dhabi, UAE;
Email<EMAIL_ADDRESS>

3 Department of applied physics and astronomy, University of Sharjah, Sharjah,
UAE; Email<EMAIL_ADDRESS>

4 College of Arts and Sciences, Abu Dhabi University, Abu Dhabi 59911, UAE

5 Institute for Quantum Science and Engineering, Texas A&M University, College
Station, TX 77843, USA

*Author to whom correspondence should be addressed

###### Abstract

Quantum computing has gained attention in recent years due to the significant
progress in quantum computing technology. Today many companies like IBM,
Google and Microsoft have developed quantum computers and simulators for
research and commercial use. The development of quantum techniques and
algorithms is essential to exploit the full power of quantum computers. In
this paper we propose a simple visual technique (we call Q-Map) for quantum
realisation of classical Boolean logic circuits. The proposed method utilises
concepts from Boolean algebra to produce a quantum circuit with minimal number
of quantum gates.

## Introduction

The advancement of quantum computing hardware and software intrigues
researchers to develop quantum algorithms in areas such as cryptography, image
processing, algorithms, finance [10, 15, 13, 6] and many other areas. One main
advantage of quantum computers compared to classical computers is the
processing power. The quantum computer can process computationally expensive
tasks exponentially faster than the classical computer. While classical
algorithms are limited in complexity to $O(n)$, a quantum search algorithm
proposed by Grover [8] uses $O(\sqrt{n})$ for unsorted list of $n$ items. Shor
[23] proposed a quantum algorithm to factor an integer $n$ in polynomial of
log $n$ time complexity. At this point, there is no classical algorithm that
can solve number factorisation in polynomial time.The RSA cryptographic system
[20] is based on prime number factorisation, and thus with quantum computers
an RSA encrypted message can be decrypted in polynomial time complexity.
Hallgen [9] presented a polynomial-time quantum algorithm to solve the Pell-
Fermat equation [3] ( also known as the Pells equation 111Pell-Fermat equation
is: $x^{2}-dy^{2}=1$ and the goal is to find pairs of integers $(x,y)$ to
satisfy the equation). In classical algorithm there is no know polynomial time
solution and the problem is know to be NP complete [4]. Recently, a group of
scientists at Google AI Quantum [2] used $53$ qubit quantum computer to sample
the output of a pseudo-random quantum circuit [18]. The results were compared
with the sate-of-the art super computer that needs 10,000 years while the 53
qubit quantum computer needs $200$ seconds.

Another advantage of quantum computers is low energy consumption. In
computation, energy consumption is correlated with reversibility of the
computation. Irreversibly is equivalent to information erasure. For the case
of an AND gate of output 0, we may say that we cannot uniquely identify the
input, the AND operation resulted in erasure of information and thus consumed
energy [14]. As demonstrated by Landauer [14], classical binary computers
mainly dissipate energy during information erasure at the rate of $KT\ln 2$
per bit erased, where $K$ is the Boltzmann constant and $T$ is the temperature
in Kelvins. At room temperature (300 Kelvin), each bit erasure will cost
around $3\times 10^{-21}Jouls$. This number appears to be too small, however
the digital binary computer is composed of huge number of Boolean logic gate
operations at the hardware level which results in significant consumption of
energy. On the other hand, quantum computers utilise quantum gates which are
all reversible gates and thus quantum computation do not result in energy
consumption.

In this paper we propose a simple visual technique (we call Q-Map) for quantum
realisation of classical Boolean logic circuits. Classical boolean computation
can be described in terms of classical boolean functions. To perform classical
computations using a quantum computer, the classical boolean function need to
be synthesised using reversible functions.

## Overview of classical and Quantum gates

A Boolean function with $n$ inputs and $m$ outputs is defined as:
$\mathcal{B}_{n,m}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{f|f:\mathbb{B}^{n}\rightarrow\mathbb{B}^{m}\\}$,
where the Boolean values are denoted by
$\mathbb{B}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{0,1\\}$.

A function $f\in\mathcal{B}_{n,n}$ is reversible if it is bijective [21], each
input map exactly to one output and the number of inputs is equal to the
number of outputs.
Classical Binary computers are, in essence, composed of irreversible logic
gates. Other than the NOT gate, the binary logic gates are irreversible gates
( see Figure 1 ). For example the classic AND gate is irreversible, for an
output of 0 the input could be 00, 01 or 10 and cannot be uniquely identified.

Figure 1: Basic Boolean gates, only the NOT gate is reversible

.

Figure 2: Commonly used quantum gates

On the other hand, a quantum bit (or qubit) x represents a unit of information
and can be described in a two dimensional quantum system as follows:

$\ket{x}=\left[\begin{array}[]{c}c_{0}\\\ c_{1}\end{array}\right]$ where
$\sqrt{{\left|c_{0}\right|}^{2}+{\left|c_{1}\right|}^{2}}=1$

The quantum states of $\ket{0}$ and $\ket{1}$ are represented by the vectors
$\ket{0}=\left[\begin{array}[]{c}1\\\ 0\end{array}\right]$ and
$\ket{1}=\left[\begin{array}[]{c}0\\\ 1\end{array}\right]$

The qubit can be in an ”on” or ”off” states as in the classical Boolean
computers or in any combination of the ”on-off” states :
$\textbf{x}=\alpha\ket{0}+\beta\ket{1}$ , where
$\sqrt{\alpha^{2}+\beta^{2}}=1$. To represent a classical digital system the
qubit $\ket{0}$ and $\ket{1}$ are sufficient. Figure 2 shows the commonly used
quantum gates, all quantum gates are reversible and the input can be
reconstructed from the output by applying the gate twice. Figure 3 shows an
example using the Toffoli gate, the input can be reconstructed by applying the
Toffolli gate twice.

Figure 3: All quantum gates are reversible gates, the input can be recovered
by applying the same gate twice. The figure above shows an example using the
Toffoli gate, we can reconstruct the input by applying the Toffolli gate
twice.

In this paper we propose a technique to implement a binary logic circuit using
a quantum gates, and thus only the $\ket{0}$ and $\ket{1}$ states of the qubit
are utilised. In classical Boolean circuits, the NAND gate is a universal gate
and all other Boolean gates could be constructed using one or more NAND
gates[27]. Any Boolean logic circuit can be designed using reversible quantum
gates, the logic gates presented in Figure 1 can be constructed using a
combination of the NOT, CNOT and Toffoli gates, thus the NOT-CNOT-Tofolli
gates form a universal basis for quantum circuit implementation [19, 31, 5].
Figure 4 shows quantum reconstruction of the NAND gate using a Toffoli gate,
the quantum equivalent requires an extra bit ( i.e ancillary bit ).The rest of
the boolean gates can be synthesised using the NOT-CNOT-Tofolli bases.

Figure 4: Reconstruction of the logic NAND gate using the Toffolli gate, all
Boolean logic gates can be reconstructed using quantum gates.

Thus any Boolean function can be synthesised by simply replacing each Boolean
gate by its quantum counterpart. However this approach is hardly efficient and
leads to a significant number of ancillary bits [17, 30]. In literature
several approaches have been proposed [12, 7, 25, 24, 29, 28] to synthesise a
given Boolean function with minimal number of ancillary bits. Most of the
approaches rely on heuristic methods to minimise the costs of the resulting
circuits using complex function manipulation [11]. In this paper we present an
exact method to realise the quantum implementation of any classical binary
system. The technique (we call Q-Map) is analogous to the Karnaugh Map [27]
for classical logic gate minimisation technique. The main contribution of this
paper is as follows:

  * •

We propose a visual method to synthesise any Boolean functions without having
to resort to complex function decomposition and manipulation.

  * •

We demonstrate the algorithm by implementing the 4-bit Gray Code Encoder using
QISKIT.

##  Quantum-Map technique

In our proposed approach, the problem is modelled as a quantum circuit with
$n$ input quantum bits ($\ket{q_{0},q_{1},...,q_{n-1}}$) that represents the
initial state of every qubit and $n$ output quantum bits
($\ket{q_{0}^{{}^{\prime}},q_{1}^{{}^{\prime}},...,q_{n-1}^{{}^{\prime}}}$)
that represent the final state of each bit (see Fig. 5 (a)). The quantum
circuit is further decomposed into a series of $n$ cascaded stages . Each
stage is a quantum circuit with $n$ input qubits represented by the vector
$\textbf{V}_{i}$ and $n$ output qubits represented by the vector
$\textbf{V}_{i}^{{}^{\prime}}$ where qubit $\ket{q_{i}}$ is altered and the
rest of the qubits are unaltered, the stages are presented in Fig. 5 (b).

(a) Quantum Circuit

(b) The Quantum circuit is decomposed into $n$ stages.

Figure 5: (a) The quantum circuit is composed of the present state vector
$\ket{q_{0}q_{1}q_{2}q_{3}\dots q_{n-1}}$ and the next state vector
$\ket{q_{0}^{{}^{\prime}}q_{1}^{{}^{\prime}}q_{3}{{}^{\prime}}\dots
q_{n-1}^{{}^{\prime}}}$ (b) The circuit is decomposed into $n$ cascaded
stages, for stage $\textbf{U}_{q_{i}}$ only qubit $q_{i}$ is changed to its
next state $q_{i}^{{}^{\prime}}$ all other qubits are unaltered.

The relationship between the input vector and the output qubit at stage $i$ is
defined by a control function
$\textbf{U}_{q_{i}}:\mathbb{B}^{n}\longrightarrow\mathbb{B}^{n}$ as follows:

$\textbf{V}_{i}\stackrel{{\scriptstyle\textbf{U}_{q_{i}}}}{{\longrightarrow}}\textbf{V}_{i}^{{}^{\prime}}$
(1)

Where $\textbf{U}_{q_{i}}$ is a control function that computes a new value at
the target output $q_{i}$ and leaves all other variables unaltered. Equation 1
can be expanded as:

$\boxed{\begin{array}[]{rcl}\ket{q_{0}q_{1}q_{2}q_{3}\dots
q_{n-1}}&\stackrel{{\scriptstyle\textbf{U}_{q_{0}}}}{{\longrightarrow}}&\ket{q_{0}^{{}^{\prime}}q_{1}q_{2}q_{3}\dots
q_{n-1}}\\\ \ket{q_{0}^{{}^{\prime}}q_{1}q_{2}q_{3}\dots
q_{n-1}}&\stackrel{{\scriptstyle\textbf{U}_{q_{1}}}}{{\longrightarrow}}&\ket{q_{0}^{{}^{\prime}}q_{1}^{{}^{\prime}}q_{2}q_{3}\dots
q_{n-1}}\\\ \ket{q_{0}^{{}^{\prime}}q_{1}^{{}^{\prime}}q_{2}q_{3}\dots
q_{n-1}}&\stackrel{{\scriptstyle\textbf{U}_{q_{2}}}}{{\longrightarrow}}&\ket{q_{0}^{{}^{\prime}}q_{1}^{{}^{\prime}}q_{2}^{{}^{\prime}}q_{3}\dots
q_{n-1}}\\\ \vdots&\vdots&\vdots\\\
\ket{q_{0}^{{}^{\prime}}q_{1}^{{}^{\prime}}\dots
q_{n-2}^{{}^{\prime}}q_{n-1}}&\stackrel{{\scriptstyle\textbf{U}_{q_{n-1}}}}{{\longrightarrow}}&\ket{q_{0}^{{}^{\prime}}q_{1}^{{}^{\prime}}\dots
q_{n-2}^{{}^{\prime}}q_{n-1}^{{}^{\prime}}}\end{array}}$ (2)

As presented in Equation 2, the input vector
$\textbf{V}_{0}=\ket{q_{0}q_{1}q_{2}q_{3}\dots q_{n-1}}$ includes all qubits,
thus the quantum circuit $\textbf{U}_{q_{0}}$ will calculate
$q_{0}^{{}^{\prime}}$ (i.e the next state of $q_{0}$) as a function of $n$
qubits. The output vector
$\textbf{V}_{0}^{{}^{\prime}}=\ket{q_{0}^{{}^{\prime}}q_{1}q_{2}q_{3}\dots
q_{n-1}}$ is an $n$ qubit vector where only qubit $q_{0}$ is changed to
$q_{0}^{{}^{\prime}}$ based on value of the control function
$\textbf{U}_{q_{0}}$ and the rest of the qubits are unchanged. To calculate
$q_{1}^{{}^{\prime}}$, the output qubit from the previous stage will be used.
In general, the input vector for any stage $k$ is the vector
$\textbf{V}_{k}=\ket{q_{0}^{{}^{\prime}}q_{1}^{{}^{\prime}}\dots
q_{k-1}^{{}^{\prime}}q_{k}\dots q_{n-1}}$ and the output is the vector
$\textbf{V}^{{}^{\prime}}_{k}=\ket{q_{0}^{{}^{\prime}}q_{1}^{{}^{\prime}}\dots
q_{k-1}^{{}^{\prime}}q_{k}^{{}^{\prime}}\dots q_{n-1}}$.

To calculate $\textbf{U}_{q_{i}}$ for each stage, we follow a function
minimisation approach inspired by the Karnaugh Map technique [27] for Boolean
function minimisation. Our proposed approach starts by building a logic map
for the function to be minimised we call it the Quantum Map (Q-Map). The Q-Map
is a two-dimensional array of cells used to represent a switching function.
The switching function $T(q_{i})$, presented in Table 1, represents the toggle
state of a qubit from the present state $q_{i}$ to the next state
$q^{{}^{\prime}}_{i}$ (i.e toggle from $\ket{0}$ to $\ket{1}$ or from
$\ket{1}$ to $\ket{0}$). The function $T(q_{i})$ can be represented as the
logical XOR of the current state $q_{i}$ with the next state
$q_{i}^{{}^{\prime}}$ as presented in Table 1.

Table 1: Toggle function to represent change of state Present Sate $q_{i}$ |  Next State $q_{i}^{{}^{\prime}}$ |  Toggle function $T(q_{i})=q_{i}\oplus q_{i}^{{}^{\prime}}$
---|---|---
$\ket{0}$ |  $\ket{0}$ |  $\ket{0}$
$\ket{0}$ |  $\ket{1}$ |  $\ket{1}$
$\ket{1}$ |  $\ket{0}$ |  $\ket{1}$
$\ket{1}$ |  $\ket{1}$ |  $\ket{0}$

$T(q_{i})$ is a function of $n$ qubits denoted by $\ket{q_{0}q_{1}\dots
q_{n-1}}$, the Q-Map of the stage $\textbf{U}_{q_{i}}$ is composed of two
vectors $\textbf{S}_{1}=\ket{q_{n-1}\dots q_{k}}$ and
$\textbf{S}_{2}=\ket{q_{k-1}\dots q_{0}}$ with a row for each assignment of
$\textbf{S}_{1}$ for a total of $2^{n-k-1}$ and with a column for each
assignment of $\textbf{S}_{2}$ for a total of $2^{k}$ columns. Similar to the
Karnaugh Map, the adjacency condition is established by labelling the rows and
the columns such that for any $2^{r}$ adjacent rows ( or columns) differ only
in $r$ variables. Fig. 6 shows the Q-Map to find the quantum circuit with four
variables. In each cell the corresponding value of the switching function
$T(q_{i})$ is inscribed. Using the Q-Map, a minimal expression $T(q_{i})$ is
calculated for each qubit. And finally the quantum circuit is implemented
using the $\bf{NOT-CNOT-Toffoli}$ quantum gate basis.

(a) $T(q_{0})$ = $\textstyle f(q_{0},q_{1},q_{2},q_{3})$

(b) $T(q_{1})$ = $f(q_{0}^{{}^{\prime}},q_{1},q_{2},q_{3})$

(c) $T(q_{2})$ = $f(q_{0}^{{}^{\prime}},q_{1}^{{}^{\prime}},q_{2},q_{3})$

(d) $T(q_{3})$ =
$f(q_{0}^{{}^{\prime}},q_{1}^{{}^{\prime}},q_{2}^{{}^{\prime}},q_{3})$

Figure 6: Quantum maps with four variables. In each cell the corresponding
value of $T(q_{i})$ is inscribed.

To demonstrate our proposed approach, we present a quantum circuit
implementation of the Gray Code to Binary converter. The details of proposed
algorithm with the reversible circuit implementation are presented in the next
section.

## Implementation of the Gray Code Encoder

In this section we demonstrate the technique by implementing the Gray Code to
Binary converter. The Gray Code is used in many applications such as position
control systems, communications and many other areas [16]. The Gray code
provides a binary code that changes by one bit only when it changes from one
state to the next. The Gray code and the corresponding decimal unsigned binary
equivalent is shown in Table 2.

Table 2: Gray code to Binary converter truth table.  Present State |  Next State
---|---
$\textbf{q}_{3}\ \textbf{q}_{2}\ \textbf{q}_{1}\ \textbf{q}_{0}$ |  ${\textbf{q}_{3}^{{}^{\prime}}\ \textbf{q}_{2}^{{}^{\prime}}\ \textbf{q}_{1}^{{}^{\prime}}\ \textbf{ q}_{0}^{{}^{\prime}}}$
${0\quad 0\quad 0\quad 0}$ |  ${0\quad 0\quad 0\quad 0}$
${0\quad 0\quad 0\quad 1}$ |  ${0\quad 0\quad 0\quad 1}$
${0\quad 0\quad 1\quad 1}$ |  ${0\quad 0\quad 1\quad 0}$
${0\quad 0\quad 1\quad 0}$ |  ${0\quad 0\quad 1\quad 1}$
${0\quad 1\quad 1\quad 0}$ |  ${0\quad 1\quad 0\quad 0}$
${0\quad 1\quad 1\quad 1}$ |  ${0\quad 1\quad 0\quad 1}$
${0\quad 1\quad 0\quad 1}$ |  ${0\quad 1\quad 1\quad 0}$
${0\quad 1\quad 0\quad 0}$ |  ${0\quad 1\quad 1\quad 1}$
${1\quad 1\quad 0\quad 0}$ |  ${1\quad 0\quad 0\quad 0}$
${1\quad 1\quad 0\quad 1}$ |  ${1\quad 0\quad 0\quad 1}$
${1\quad 1\quad 1\quad 1}$ |  ${1\quad 0\quad 1\quad 0}$
${1\quad 1\quad 1\quad 0}$ |  ${1\quad 0\quad 1\quad 1}$
${1\quad 0\quad 1\quad 0}$ |  ${1\quad 1\quad 0\quad 0}$
${1\quad 0\quad 1\quad 1}$ |  ${1\quad 1\quad 0\quad 1}$
${1\quad 0\quad 0\quad 1}$ |  ${1\quad 1\quad 1\quad 0}$
${1\quad 0\quad 0\quad 0}$ |  ${1\quad 1\quad 1\quad 1}$

The first step starts by building the switching function $T(q_{i})$ for each
quantum bit as described in Table 1. The function $T(q_{i})$ for each qubit is
calculated as:

$\displaystyle T(q_{0})=q_{0}\oplus q_{0}^{{}^{\prime}}$ (3) $\displaystyle
T(q_{1})=q_{1}\oplus q_{1}^{{}^{\prime}}$ (4) $\displaystyle
T(q_{2})=q_{2}\oplus q_{2}^{{}^{\prime}}$ (5) $\displaystyle
T(q_{3})=q_{3}\oplus q_{3}^{{}^{\prime}}$ (6)

The result is presented in Table 3

Table 3: Gray Code to binary converter: Q-Map functions are calculated as the XOR of the present and next states.  Present State |  Next State | Toggle Functions
---|---|---
$\textbf{q}_{3}\ \textbf{q}_{2}\ \textbf{q}_{1}\ \textbf{q}_{0}$ |  ${\textbf{q}_{3}^{{}^{\prime}}\ \textbf{q}_{2}^{{}^{\prime}}\ \textbf{q}_{1}^{{}^{\prime}}\ \textbf{ q}_{0}^{{}^{\prime}}}$ |  $\textbf{T}({\textbf{q}_{3}})$ |  $\textbf{T}({\textbf{q}_{2}})$ |  $\textbf{T}({\textbf{q}_{1}})$ |  $\textbf{T}({\textbf{q}_{0}})$
${0\quad 0\quad 0\quad 0}$ |  ${0\quad 0\quad 0\quad 0}$ |  ${0}$ |  ${0}$ |  ${0}$ |  ${0}$
${0\quad 0\quad 0\quad 1}$ |  ${0\quad 0\quad 0\quad 1}$ |  ${0}$ |  ${0}$ |  ${0}$ |  ${0}$
${0\quad 0\quad 1\quad 1}$ |  ${0\quad 0\quad 1\quad 0}$ |  ${0}$ |  ${0}$ |  ${0}$ |  ${1}$
${0\quad 0\quad 1\quad 0}$ |  ${0\quad 0\quad 1\quad 1}$ |  ${0}$ |  ${0}$ |  ${0}$ |  ${1}$
${0\quad 1\quad 1\quad 0}$ |  ${0\quad 1\quad 0\quad 0}$ |  ${0}$ |  ${0}$ |  ${1}$ |  ${0}$
${0\quad 1\quad 1\quad 1}$ |  ${0\quad 1\quad 0\quad 1}$ |  ${0}$ |  ${0}$ |  ${1}$ |  ${0}$
${0\quad 1\quad 0\quad 1}$ |  ${0\quad 1\quad 1\quad 0}$ |  ${0}$ |  ${0}$ |  ${1}$ |  ${1}$
${0\quad 1\quad 0\quad 0}$ |  ${0\quad 1\quad 1\quad 1}$ |  ${0}$ |  ${0}$ |  ${1}$ |  ${1}$
${1\quad 1\quad 0\quad 0}$ |  ${1\quad 0\quad 0\quad 0}$ |  ${0}$ |  ${1}$ |  ${0}$ |  ${0}$
${1\quad 1\quad 0\quad 1}$ |  ${1\quad 0\quad 0\quad 1}$ |  ${0}$ |  ${1}$ |  ${0}$ |  ${0}$
${1\quad 1\quad 1\quad 1}$ |  ${1\quad 0\quad 1\quad 0}$ |  ${0}$ |  ${1}$ |  ${0}$ |  ${1}$
${1\quad 1\quad 1\quad 0}$ |  ${1\quad 0\quad 1\quad 1}$ |  ${0}$ |  ${1}$ |  ${0}$ |  ${1}$
${1\quad 0\quad 1\quad 0}$ |  ${1\quad 1\quad 0\quad 0}$ |  ${0}$ |  ${1}$ |  ${1}$ |  ${0}$
${1\quad 0\quad 1\quad 1}$ |  ${1\quad 1\quad 0\quad 1}$ |  ${0}$ |  ${1}$ |  ${1}$ |  ${0}$
${1\quad 0\quad 0\quad 1}$ |  ${1\quad 1\quad 1\quad 0}$ |  ${0}$ |  ${1}$ |  ${1}$ |  ${1}$
${1\quad 0\quad 0\quad 0}$ |  ${1\quad 1\quad 1\quad 1}$ |  ${0}$ |  ${1}$ |  ${1}$ |  ${1}$

The second step is to establish the Q-Map for each qubit. Figure 7 (a) shows
the Q-Map to evaluate ${q_{0}}$ given the values of the input ${q_{1}}$,
${q_{2}}$ and $q_{3}$. A value of $1$ in the Q-Map represents the state of
${q_{1}}$, $q_{2}$ and ${q_{3}}$ when ${q_{0}}$ toggles its state. Thus
${q_{0}}$ will toggle its state when the following expression is true:

$\displaystyle
T(q_{0})=\overline{q}_{3}\overline{q}_{2}q_{1}\oplus\overline{q}_{3}q_{2}\overline{q}_{1}\oplus
q_{3}\overline{q}_{2}\overline{q}_{1}\oplus q_{3}q_{2}q_{1}$ (7)

Figure 7 (b) shows the Q-Map to find $T(q_{1})$. The expression is calculated
based on inputs $q_{3}$, $q_{2}$ and $q_{0}^{{}^{\prime}}$ as follows:

$\displaystyle T(q_{1})=q_{3}\overline{q}_{2}\oplus\overline{q}_{3}q_{2}$ (8)

Figure 7 (c) shows the Q-Map to find $T(q_{2})$. The expression is calculated
based on inputs $q_{3}$, $q_{1}^{{}^{\prime}}$ and $q_{0}^{{}^{\prime}}$ as
follows:

$\displaystyle T(q_{2})=q_{3}$ (9)

Finally, figure 7 (d) shows the Q-Map to find $T(q_{3})$. The expression is
calculated based on the inputs $q_{2}^{{}^{\prime}}$, $q_{1}^{{}^{\prime}}$
and $q_{0}^{{}^{\prime}}$ as follows:

(a) $T(q_{0})=f(q_{0},q_{1},q_{2},q_{3})$

(b) $T(q_{1})=f(q_{0}^{{}^{\prime}},q_{1},q_{2},q_{3})$

(c) $T(q_{2})=f(q_{0}^{{}^{\prime}},q_{1}^{{}^{\prime}},q_{2},q_{3})$

(d)
$T(q_{3})=f(q_{0}^{{}^{\prime}},q_{1}^{{}^{\prime}},q_{2}^{{}^{\prime}},q_{3})$

Figure 7: Q-Map representing the switching function for qubits $q_{0}$,
$q_{1}$, $q_{2}$ and $q_{3}$, $T(q_{i})$ is written in Exclusive-OR Sum-of-
Product form (ESOP)

Notice here we use the XOR ($\oplus$) operation and the function $T(q_{i})$ is
represented in Exclusive-OR Sum-of-Product form (ESOP) form since the qubit
will toggle only if we have an odd number of true terms. For even number of
true terms the qubit will retain its initial state. In classical Boolean
function minimisation using Karnaugh Map the logic OR ($+$) operation is used
and the function is expressed in Sum of Product (SOP) form since the Boolean
function will be true if any of the terms is true and so group overlap is
allowed.

In our proposed Q-Map approach group overlap is not allowed, this makes all
terms in every function $T(q_{i})$ mutually exclusive and only one term can be
true at one instant of time. Thus the XOR ($\oplus$) operation can be replaced
by the OR ($+$) operation and the function $T(q_{i})$ can be represented in
the Sum of Product (SOP) form. Since each Q-Map in Figure 7 contains no
overlapping groups, the functions can be represented in Sum of Product (SOP)
form as follows:

$\boxed{\begin{array}[]{rcl}T(q_{0})&=&\overline{q}_{3}\overline{q}_{2}q_{1}+\overline{q}_{3}q_{2}\overline{q}_{1}+q_{3}\overline{q}_{2}\overline{q}_{1}+q_{3}q_{2}q_{1}\\\
T(q_{1})&=&q_{3}\overline{q}_{2}+\overline{q}_{3}q_{2}\\\ T(q_{2})&=&q_{3}\\\
T(q_{3})&=&0\end{array}}$ (10)

The functions presented in Equation 10 can be realised by a reversible circuit
with only four lines (i.e. $O(n)$ lines) using the NOT-CNOT-Toffoli bases with
Multi-Control Toffolli gates [22]. This means that the implementation is
efficient and no temporary lines (also referred as ancilla) are needed. The
quantum circuit can be implemented using CNOT and two and three input Toffoli
gates as shown in Figure 8.

The quantum circuit is also simulated using QISKIT open-source framework
simulator for quantum circuit [1, 26]. In QISKIT, the Toffoli gate is composed
of two control inputs and one output. To implement the circuit in Figure 8, we
redesigned the quantum circuit to include 2-input Toffoli gates; however an
additional ancillary qubit is needed to store the intermediate values. The
design with 2-input Toffoli gates is presented in Figure 9. The code to
simulate the qunatum gray to binary converter is presented in Figure 11.

The Q-Map algorithm can be summarised as follows:

  * Step 1: For each qubit $q_{i}$ build the toggle function $T(q_{i})=q_{i}\oplus q_{i}^{{}^{\prime}}$ as the logical Exclusive-OR of the present state $q_{i}$ and the final state $q_{i}^{{}^{\prime}}$.

  * Step 2 :Establish the Q-Map of the switching function $T(q_{i})$ as a function of the $n$ qubits $(q_{0}^{{}^{\prime}},q_{1}^{{}^{\prime}},\dots,q_{i-1}^{{}^{\prime}},q_{i}\dots,q_{n-1})$ .

  * Step 3: In each cell inscribe the value of $T(q_{i})$ in the Q-Map.

  * Step 4: Find the expression of $T(q_{i})$ in Sum-Of-Product form using the Q-Map such that:
1\. Groups should be as large as possible
2\. Group Overlapping is not allowed

  * Step 5: For each expression $T(q_{i})$ use the CNOT-NOT-Toffoli bases to implement the corresponding quantum circuit.

Figure 8: Implementation of the Quantum circuit using 2 and 3 input Toffoli
and CNOT gates Figure 9: Implementation of the Quantum circuit using 2-input
Toffoli and CNOT gates

Figure 10: Implementation of the Quantum circuit using QISKIT

q = QuantumRegister(5) c = ClassicalRegister(5) grayEncoder =
QuantumCircuit(q,c) # Reset input qbit q[0], q[1], q[2],q[3]
grayEncoder.reset(q[0]) grayEncoder.reset(q[1]) grayEncoder.reset(q[2])
grayEncoder.reset(q[3]) #Reset ancillary qbit q[4] grayEncoder.reset(q[4])
#========== calculate T(q0) ================= grayEncoder.x(q[2]) # NOT gate
grayEncoder.x(q[3]) # NOT gate grayEncoder.ccx(q[2],q[3],q[4]) # TOFOLLI gate
grayEncoder.ccx(q[1],q[4],q[0]) grayEncoder.ccx(q[2],q[3],q[4]) # TOFOLLI gate
grayEncoder.x(q[2]) # NOT gate #—————————————- grayEncoder.ccx(q[2],q[3],q[4])
# TOFOLLI gate grayEncoder.x(q[1]) # not grayEncoder.ccx(q[1],q[4],q[0])
grayEncoder.ccx(q[2],q[3],q[4]) # TOFOLLI gate grayEncoder.x(q[3]) # not
#————————————- grayEncoder.x(q[2]) # not grayEncoder.ccx(q[2],q[3],q[4]) #
TOFOLLI gate grayEncoder.ccx(q[1],q[4],q[0]) grayEncoder.x(q[1]) # not
grayEncoder.ccx(q[2],q[3],q[4]) # TOFOLLI gate grayEncoder.x(q[2]) # not
#——————– grayEncoder.ccx(q[2],q[3],q[4]) # TOFOLLI gate
grayEncoder.ccx(q[1],q[4],q[0]) grayEncoder.ccx(q[2],q[3],q[4]) # TOFOLLI gate
#=========== calculate T(q1) ================= grayEncoder.x(q[2]) # not
grayEncoder.ccx(q[2],q[3],q[1]) # TOFOLLI gate grayEncoder.x(q[2]) # not
#——————————— grayEncoder.x(q[3]) # not grayEncoder.ccx(q[2],q[3],q[1]) #
TOFOLLI gate grayEncoder.x(q[3]) # NOT gate #=========== calculate T(q2)
================= grayEncoder.cx(q[3],q[2]) # CNOT gate

Figure 11: Code to implement of the Quantum circuit in Fig. 10

## Q-Map optimisation

In classical boolean function minimsation using the Karnaugh map, the entry
inscribed in every cell indicates the value of the boolean function at the
corresponding state. However in our proposed approach, the entry inscribed in
each cell in the Q-map indicates change of state of the function. An entry of
$1$ in th Q-map indicates that the function must change state (i.e toggle) and
a value of $0$ indicates the function must remain in the same state. Thus
including the $1^{\prime}s$ in the Q-map in an odd number of groups will
result in one change of state and including the $0^{\prime}s$ in even number
of groups will result in no change of state. This property of the Q-map could
be used in our advantage to maximise the number of Q-map cells in each group
and produce a more simplified expression that minimises the quantum cost of
the design.

The optimised Q-Map algorithm can be summarised as follows:

  * Step 1: For each qubit $q_{i}$ build the toggle function $T(q_{i})=q_{i}\oplus q_{i}^{{}^{\prime}}$ as the logical Exclusive-OR of the present state $q_{i}$ and the final state $q_{i}^{{}^{\prime}}$.

  * Step 2 :Establish the Q-Map of the switching function $T(q_{i})$ as a function of the $n$ qubits $(q_{0}^{{}^{\prime}},q_{1}^{{}^{\prime}},\dots,q_{i-1}^{{}^{\prime}},q_{i}\dots,q_{n-1})$ .

  * Step 3: In each cell inscribe the value of $T(q_{i})$ in the Q-Map.

  * Step 4: Find the expression of $T(q_{i})$ in Sum-Of-Product form using the Q-Map such that:

    1. 1.

Groups should be as large as possible and may include $1^{\prime}s$ and
$0^{\prime}s$.

    2. 2.

Every $1$ must be included in an odd number of groups

    3. 3.

If a $0$ is included, it must be included in an even number of groups

  * Step 5: For each expression $T(q_{i})$ use the CNOT-NOT-Toffoli bases to implement the corresponding quantum circuit.

To demonstrate the idea, we re-evaluate the functions produces in the Q-map of
Figure 7 as shown in Figure 12 and the functions presented in Eq. 10 can be
replaced by :

$\boxed{\begin{array}[]{rcl}T(q_{0})&=&\overline{q}_{3}q_{1}+q_{3}\overline{q}_{1}+q_{2}\\\
T(q_{1})&=&q_{3}+q_{2}\\\ T(q_{2})&=&q_{3}\\\ T(q_{3})&=&0\end{array}}$ (11)

Other alternative designs are possible, for example, $T(q_{1})$ can be also
written as $\bar{q_{2}}+\bar{q_{3}}$.

(a) $T(q_{0})=f(q_{0},q_{1},q_{2},q_{3})$

(b) $T(q_{1})=f(q_{0}^{{}^{\prime}},q_{1},q_{2},q_{3})$

(c) $T(q_{2})=f(q_{0}^{{}^{\prime}},q_{1}^{{}^{\prime}},q_{2},q_{3})$

(d)
$T(q_{3})=f(q_{0}^{{}^{\prime}},q_{1}^{{}^{\prime}},q_{2}^{{}^{\prime}},q_{3})$

Figure 12: Optimised Q-Map representing the switching function for qubits
$q_{0}$, $q_{1}$, $q_{2}$ and $q_{3}$, $T(q_{i})$. Every entry of $1$ must be
included in an odd number of groups and an entry of $0$ must be included in an
even number of groups.

Based on the functions in Eq.11, the quantum circuit can be designed as
presented in Figure 13 and the corresponding QISKIT code is shown in Figure
14. The optimised approach re-designed the quantum circuit with no ancillary
bits and significantly reduced the number of quantum gates.

Figure 13:  Implementation of the optimised Quantum circuit using QISKIT

q = QuantumRegister(4) c = ClassicalRegister(4) grayEncoder =
QuantumCircuit(q,c)

# Reset input qbit q[0], q[1], q[2],q[3] grayEncoder.reset(q[0])
grayEncoder.reset(q[1]) grayEncoder.reset(q[2]) grayEncoder.reset(q[3])

#========== calculate T(q0) ================= grayEncoder.cx(q[2],q[0]) # CNOT
gate (T(q0) = q2) grayEncoder.x(q[3]) # NOT gate
grayEncoder.ccx(q[1],q[3],q[0]) # TOFOLLI gate (T(q0) = q1.!q3)
grayEncoder.x(q[3]) # NOT gate grayEncoder.x(q[1]) # NOT gate
grayEncoder.ccx(q[1],q[3],q[0]) # TOFOLLI gate T(q0) = !q1. q3
grayEncoder.x(q[1]) # NOT gate

#=========== calculate T(q1) ================= grayEncoder.cx(q[2],q[1]) #
TOFOLLI gate T(q1) = q2 grayEncoder.cx(q[3],q[1]) # TOFOLLI gate T(q1) = q3

#=========== calculate T(q2) ================= grayEncoder.cx(q[3],q[2]) #
CNOT gate

Figure 14: Code to implement of the Quantum circuit in Fig. 13

## Conclusion

In this paper we propose a visual method for quantum realisation of classical
Boolean logic functions. The proposed method utilise concepts from Boolean
algebra to produce a quantum circuit with minimal number of quantum gates. The
proposed technique is composed of three steps: (1) for each quantum bit
$q_{i}$ build a switching function $T(q_{i})$, (2) establish the Q-Map for
$T(q_{i})$ and (3) using the Q-Map find the quantum expression to implement
the switching function using the NOT-CNOT-Toffoli quantum gate basis.The
proposed method is demonstrated by implementing the Gray-Code Encoder.

## References

  * 1. Learn quantum computation using qiskit, May 2023.
  * 2. F. Arute et al.  Quantum supremacy using a programmable superconducting processor.  Nature, 574:505–510, 2019.
  * 3. E. Barbeau.  Pell’s Equation.  Problem Books in Mathematics. Springer, 2003.
  * 4. J. Buchmann and H. C. Williams.  On the existence of a short proof for the value of the class number and regulator of a real quadratic field.  in: Richard A. Mollin (ed.), Number Theory and Applications, (NATO — Advanced Study Institute, Banff, 1988 ) Dordrecht: Kluwer, pages 327–345, 1989.
  * 5. T. T. E. Fredkin.  Conservative logic.  International Journal of Theoretical Physics, 21:219–253, 1982\.
  * 6. D. J. Egger, C. Gambella, J. Marecek, S. McFaddin, M. Mevissen, R. Raymond, A. Simonetto, S. Woerner, and E. Yndurain.  Quantum computing for finance: State-of-the-art and future prospects.  IEEE Transactions on Quantum Engineering, 1:1–24, 2020.
  * 7. K. Fazel, M. A. Thornton, and J. E. Rice.  Esop-based toffoli gate cascade generation.  2007 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, pages 206–209, 2007.
  * 8. L. K. Grover.  Quantum mechanics helps in searching for a needle in a haystack.  Phys. Rev. Lett., 79:325–328, Jul 1997.
  * 9. S. Hallgren.  Polynomial-time quantum algorithms for pell’s equation and the principal ideal problem.  J. ACM, 54(1):4:1–4:19, Mar. 2007.
  * 10. H. Iqbal and W. O. Krawec.  High-dimensional semiquantum cryptography.  IEEE Transactions on Quantum Engineering, 1:1–17, 2020.
  * 11. G. D. James.  The representation theory of the symmetric groups, volume 682.  Springer, 2006.
  * 12. P. Kerntopf.  A new heuristic algorithm for reversible logic synthesis.  In Proceedings of the 41st Annual Design Automation Conference, DAC ’04, page 834–837, New York, NY, USA, 2004. Association for Computing Machinery.
  * 13. T. Krauss and J. McCollum.  Solving the network shortest path problem on a quantum annealer.  IEEE Transactions on Quantum Engineering, 1:1–12, 2020.
  * 14. R. Landauer.  Irreversibility and heat generation in the computing process.  IBM Journal of Research and Development, 44(1.2):261–269, Jan 2000\.
  * 15. S.-Y. Ma, A. Khalil, H. Hajjdiab, and H. Eleuch.  Quantum dilation and erosion.  Applied Sciences, 10(11), 2020.
  * 16. T. K. Moon.  Error Correction Coding: Mathematical Methods and Algorithms, 2nd Edition.
  * 17. R. D. Nabila Abdessaied.  Reversible and Quantum Circuits.
  * 18. C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, A. Megrant, B. Chiaro, A. Dunsworth, K. Arya, R. Barends, B. Burkett, Y. Chen, Z. Chen, A. Fowler, B. Foxen, M. Giustina, R. Graff, E. Jeffrey, T. Huang, J. Kelly, P. Klimov, E. Lucero, J. Mutus, M. Neeley, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. C. White, H. Neven, and J. M. Martinis.  A blueprint for demonstrating quantum supremacy with superconducting qubits.  Science, 360(6385):195–199, 2018.
  * 19. M. A. Nielsen and I. L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, 2010.
  * 20. R. L. Rivest, A. Shamir, and L. Adleman.  A method for obtaining digital signatures and public-key cryptosystems.  Commun. ACM, 21(2):120–126, Feb. 1978.
  * 21. K. Rosen.  Discrete Mathematics and Its Applications.
  * 22. V. Shende, A. Prasad, I. Markov, and J. Hayes.  Synthesis of reversible logic circuits.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22(6):710–722, 2003.
  * 23. P. W. Shor.  Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.  SIAM J. Comput., 26(5):1484–1509, Oct. 1997.
  * 24. M. Soeken, L. Tague, G. W. Dueck, and R. Drechsler.  Ancilla-free synthesis of large reversible functions using binary decision diagrams.  Journal of Symbolic Computation, 73:1–26, 2016.
  * 25. M. Soeken, R. Wille, C. Otterstedt, and R. Drechsler.  A synthesis flow for sequential reversible circuits.  In Proceedings of the 2012 IEEE 42nd International Symposium on Multiple-Valued Logic, ISMVL ’12, page 299–304, USA, 2012. IEEE Computer Society.
  * 26. A. tA v, M. S. ANIS, Abby-Mitchell, H. Abraham, AduOffei, R. Agarwal, G. Agliardi, M. Aharoni, V. Ajith, I. Y. Akhalwaya, and et. al.  Qiskit: An open-source framework for quantum computing, 2021.
  * 27. R. J. Tocci and N. S. Widmer.  Digital systems:.  Prentice Hall, Upper Saddle River, N.J., 9th edition edition, 2004.
  * 28. A. D. Vos and Y. V. Rentergem.  Young subgroups for reversible computers.  Advances in Mathematics of Communications, 2(2):183–200, 2008.
  * 29. R. Wille and R. Drechsler.  Bdd-based synthesis of reversible logic for large functions.  In Proceedings of the 46th Annual Design Automation Conference, DAC ’09, page 270–275, New York, NY, USA, 2009. Association for Computing Machinery.
  * 30. C. P. Williams.  Explorations in Quantum Computing, Second Edition.  Texts in Computer Science. Springer, 2011.
  * 31. N. S. Yanofsky and M. A. Mannucci.  Quantum Computing for Computer Scientists.  Cambridge University Press, New York, NY, USA, 1 edition, 2008.