text:
# Preliminary version; to appear in Natural Language Engineering, 2003 Mostly-Unsupervised Statistical Segmentation of Japanese Kanji Sequences

## 1 Introduction

Because Japanese is written without delimiters between words (the analogous situation in English would be if words were written without spaces between them), accurate word segmentation to recover the lexical items is a key first step in Japanese text processing. Furthermore, word segmentation can also be used as a more directly enabling technology in applications such as extracting new technical terms, indexing documents for information retrieval, and correcting optical character recognition (OCR) errors \[Wu and Tseng,1993, Nagao and Mori,1994, Nagata,1996a, Nagata,1996b, Sproat et al.,1996, Fung,1998\].

Typically, Japanese word segmentation is performed by morphological analysis based on lexical and syntactic knowledge. However, character sequences consisting solely of kanji (Chinese-derived characters, as opposed to hiragana or katakana, the other two types of Japanese characters) pose a major challenge to morphologically-based segmenters for several reasons.

First and most importantly, lexico-syntactic morphological analyzers are vulnerable to the unknown word problem, where terms from the domain at hand are not in the lexicon; hence, these analyzers are not robust across different domains, unless effort is invested to modify their databases accordingly. The problem with kanji sequences is that they often contain domain terms and proper nouns, which are likely to be absent from general lexicons: Fung \[Fung,1998\] notes that 50-85% of the terms in various technical dictionaries are composed at least partly of kanji. Domain-dependent terms are quite important for information retrieval, information extraction, and text summarization, among other applications, so the development of segmentation algorithms that can efficiently adapt to different domains has the potential to make substantial impact.

Another reason that kanji sequences are particularly challenging for morphological analyzers is that they often consist of compound nouns, so syntactic constraints are not applicable. For instance, the sequence , whose proper segmentation is (president $`|`$ both-of-them $`|`$ business $`|`$ general manager, i.e., a president as well as a general manager of business), could be incorrectly segmented as (president $`|`$ subsidiary business $`|`$ (the name) Tsutomu $`|`$ general manager); since both alternatives are four-noun sequences, they cannot be distinguished by part-of-speech information alone.

An additional reason that accuracy on kanji sequences is an important aspect of the total segmentation process is that they comprise a significant portion of Japanese text, as shown in Figure 1.

Since sequences of more than 3 kanji generally consist of more than one word, at least 21.2% of 1993 Nikkei newswire consists of kanji sequences requiring segmentation; and long sequences are the hardest to segment \[Takeda and Fujisaki,1987\].

As an alternative to lexico-syntactic and supervised approaches, we propose a simple, efficient segmentation method, the tango algorithm, which learns mostly from very large amounts of unsegmented training data, thus avoiding the costs of encoding lexical or syntactic knowledge or hand-segmenting large amounts of training data. Some key advantages of tango are:

* A very small number of pre-segmented training examples (as few as 5 in our experiments) are needed for good performance.
* For long kanji strings, the method produces results rivalling those produced by Juman 3.61 \[Kurohashi and Nagao,1999\] and Chasen 1.0 \[Matsumoto et al.,1997\], two morphological analyzers in widespread use. For instance, we achieve on average 5% higher word precision and 6% better morpheme recall.
* No domain-specific or even Japanese-specific rules are employed, enhancing portability to other tasks and applications.

We stress that we explicitly focus on long kanji sequences, not only because they are important, but precisely because traditional knowledge-based techniques are expected to do poorly on them. We view our mostly-unsupervised algorithm as complementing lexico-syntactic techniques, and envision in the future a hybrid system in which our method would be applied to long kanji sequences and morphological analyzers would be applied to other sequences for which they are more suitable, so that the strengths of both types of methods can be integrated effectively.

### 1.1 Paper organization

This paper is organized as follows. Section 2 describes our mostly-unsupervised, knowledge-lean algorithm. Section 3 describes the morphological analyzers Juman and Chasen; comparison against these methods, which rely on large lexicons and syntactic information, forms the primary focus of our experiments.

In Section 4, we give the details of our experimental framework, including the evaluation metrics we introduced. Section 5 reports the results of our experiments. In particular, we see in Section 5.1 that the performance of our statistics-based algorithm rivals that of Juman and Chasen. In order to demonstrate the usefulness of the particular simple statistics we used, in Section 5.2 we show that our algorithm substantially outperforms a method based on mutual information and t-score, sophisticated statistical functions commonly used in corpus-based natural language processing.

We discuss related work in section 6, and conclude in section 7.

## 2 The TANGO Algorithm

Our algorithm, tango (Threshold And maximum for N-Grams that Overlap111Also, (tan-go bun-katsu) is Japanese for “word segmentation”.), employs character $`n`$-gram counts drawn from an unsegmented corpus to make segmentation decisions. We start by illustrating the underlying motivations, using the example situation depicted in Figure 2: “A B C D W X Y Z” represents a sequence of eight kanji characters, and the goal is to determine whether there should be a word boundary between D and W.

The main idea is to check whether $`n`$-grams that are adjacent to the proposed boundary, such as the 4-grams $`s_L=`$“A B C D” and $`s_R=`$“W X Y Z”, tend to be more frequent than $`n`$-grams that straddle it, such as the 4-gram $`t_1=`$ “B C D W”. If so, we have evidence of a word boundary between D and W, since there seems to be relatively little cohesion between the characters on opposite sides of this gap.

The $`n`$-gram orders used as evidence in the segmentation decision are specified by the set $`N`$. For instance, our example in Figure 2 shows a situation where $`N=\{4\}`$, indicating that only 4-grams are to be used. We thus pose the six questions of the form, “Is $`\mathrm{\#}(s_d)>\mathrm{\#}(t_j)`$?”, where $`\mathrm{\#}(x)`$ denotes the number of occurrences of $`x`$ in the (unsegmented) training corpus, $`d\{L,R\}`$, and $`j\{1,2,3\}`$. If $`N=\{2,4\}`$, then two more questions (Is “$`\mathrm{\#}(\text{C D})>\mathrm{\#}(\text{D W})`$?” and “Is $`\mathrm{\#}(\text{W X})>\mathrm{\#}(\text{D W})`$?”) are used as well. Each affirmative answer makes it more reasonable to place a segment boundary at the location under consideration.

More formally, fix a location $`k`$ and an $`n`$-gram order $`n`$, and let $`s_L^n`$ and $`s_R^n`$ be the non-straddling $`n`$-grams just to the left and right of it, respectively. For $`j\{1,2,\mathrm{},n1\}`$, let $`t_j^n`$ be the straddling $`n`$-gram with $`j`$ characters to the right of location $`k`$. We define $`I_>(y,z)`$ to be the indicator function that is 1 when $`y>z`$, and 0 otherwise — this function formalizes the notion of “question” introduced above.

tango works as follows. It first calculates the fraction of affirmative answers separately for each $`n`$-gram order $`n`$ in $`N`$, thus yielding a “vote” for that order $`n`$:

$$v_n(k)=\frac{1}{2(n1)}\underset{d\{L,R\}}{}\underset{j=1}{\overset{n1}{}}I_>(\mathrm{\#}(s_d^n),\mathrm{\#}(t_j^n)).$$

Note that in locations near the beginning or end of a sequence, not all the $`n`$-grams may exist (e.g., in Figure 2, there is no non-straddling 4-gram to the left of the A-B gap), in which case we only rely on comparisons between the existing relevant $`n`$-grams — since we are dealing with long kanji sequences, each location will have at least one $`n`$-gram adjacent to it and one $`n`$-gram straddling it, for reasonable values of $`n`$.

Then, tango averages together the votes of each $`n`$-gram order:

$$v_N(k)=\frac{1}{|N|}\underset{nN}{}v_n(k).$$

Hence, $`v_N(k)`$, or “total vote”, represents the average amount of evidence, according to the participating $`n`$-gram lengths, that there should be a word boundary placed at location $`k`$.

After $`v_N(k)`$ is computed for every location, boundaries are placed at all locations $`\mathrm{}`$ such that either:

1. $`v_N(\mathrm{})>v_N(\mathrm{}1)`$ and $`v_N(\mathrm{})>v_N(\mathrm{}+1)`$, or
2. $`v_N(\mathrm{})t`$, a threshold parameter.

That is, a segment boundary is created if and only if the total vote is either (1) a local maximum, or (2) exceeds threshold $`t`$ (see Figure 3). The second condition is necessary for the creation of single-character words, since local maxima by definition cannot be adjacent. Note that the use of a threshold parameter also allows a degree of control over the granularity of the segmentation: low thresholds encourage shorter segments.

One may wonder why we only consider comparisons between $`n`$-grams of the same length. The underlying reason is that counts for longer $`n`$-grams can be more unreliable as evidence of true frequency; that is, the sparse data problem is worse for higher-order $`n`$-grams. Because they are potentially unreliable, we do not want longer $`n`$-grams to dominate the segmentation decision; but since there are more overlapping higher-order $`n`$-grams than lower-order ones, we compensate by treating the different orders separately. Furthermore, counts for longer $`n`$-grams tend to be smaller than for shorter ones, so it is not clear that directly comparing counts for different-order $`n`$-grams is meaningful. One could use some sort of normalization technique, but one of our motivations was to come up with as simple an algorithm as possible.222While simplicity is itself a virtue, an additional benefit to it is that having fewer variables reduces the need for parameter-training data.

While of course we do not make any claims that this method has any psychological validity, it is interesting to note that recent studies \[Saffran, Aslin, and Newport,1996, Saffran,2001\] have shown that infants can learn to segment words in fluent speech based only on the statistics of neighboring syllables. Such research lends credence to the idea that simple co-occurrence statistics contain much useful information for our task.

### 2.1 Implementation Issues

In terms of implementation, both the count acquisition phase (which can be done off-line) and the testing phase are efficient. Computing $`n`$-gram statistics for all possible values of $`n`$ simultaneously can be done in $`O(m\mathrm{log}m)`$ time using suffix arrays, where $`m`$ is the training corpus size \[Manber and Myers,1993, Nagao and Mori,1994, Yamamoto and Church,2001\].333Nagao and Mori \[Nagao and Mori,1994\] and Yamamoto and Church \[Yamamoto and Church,2001\] use suffix arrays in the service of unsupervised term extraction, which is somewhat related to the segmentation problem we consider here. However, if the set $`N`$ of $`n`$-gram orders is known in advance, conceptually simpler algorithms suffice. For example, we implemented an $`O(m\mathrm{log}m)`$ procedure that explicitly stores the $`n`$-gram counts in a table. (Memory allocation for count tables can be significantly reduced by omitting $`n`$-grams occurring only once and assuming the count of unseen $`n`$-grams to be one. For instance, the kanji $`n`$-gram table for $`N=\{2,3,4,5,6\}`$ extracted from our 150-megabyte corpus was 18 megabytes in size, which fits easily in memory.) In the application phase, tango’s running time is clearly linear in the test corpus size if $`|N|`$ is treated as a constant, since the algorithm is quite simple.

We observe that some pre-segmented data is necessary in order to set the parameters $`N`$ and $`t`$. However, as described below, very little such data was required to get good performance; we therefore deem our algorithm to be “mostly unsupervised”.

## 3 Morphological Analyzers: Chasen and Juman

In order to test the effectiveness of tango, we compared it against two different types of methods, described below. The first type, and our major “competitor”, is the class of morphological analyzers, represented by Chasen and Juman – our primary interest is in whether the use of large amounts of unsupervised data can yield information comparable to that of human-developed grammars and lexicons. (We also compared tango against the mostly-unsupervised statistical algorithm developed by Sun et al. \[Sun, Shen, and Tsou,1998\], described in Section 5.2.1.)

Chasen 1.0444 http://cactus.aist-nara.ac.jp/lab/nlt/chasen.html \[Matsumoto et al.,1997\] and Juman 3.61555 http://pine.kuee.kyoto-u.ac.jp/nl-resource/juman-e.html \[Kurohashi and Nagao,1999\] are two state-of-the-art, publically-available, user-extensible systems. In our experiments, the grammars of both systems were used as distributed (indeed, they are not particularly easy to make additions to; creating such resources is a difficult task). The sizes of Chasen’s and Juman’s default lexicons are approximately 115,000 and 231,000 words, respectively.

An important question that arose in designing our experiments was how to enable morphological analyzers to make use of the parameter-training data that tango had access to, since the analyzers do not have parameters to tune. The only significant way that they can be updated is by changing their grammars or lexicons, which is quite tedious (for instance, we had to add part-of-speech information to new entries by hand). We took what we felt to be a reasonable, but not too time-consuming, course of creating new lexical entries for all the bracketed words in the parameter-training data (see Section 4.2). Evidence that this was appropriate comes from the fact that these additions never degraded test set performance, and indeed improved it in some cases. Furthermore, our experiments showed that reducing the amount of training data hurt performance (see Section 5.3), indicating that the information we gave the analyzers from the segmented training data is useful.

It is important to note that in the end, we are comparing algorithms with access to different sources of knowledge. Juman and Chasen use lexicons and grammars developed by human experts. Our algorithm, not having access to such pre-compiled knowledge bases, must of necessity draw on other information sources (in this case, a very large unsegmented corpus and a few pre-segmented examples) to compensate for this lack. Since we are interested in whether using simple statistics can match the performance of labor-intensive methods, we do not view these information sources as conveying an unfair advantage, especially since the annotated training sets were small, available to the morphological analyzers, and disjoint from the test sets.

## 4 Experimental Framework

In this section, we describe our experimental setup. Section 4.1 gives details on the data we used and how training proceeded. Section 4.2 presents the annotation policies we followed to segment the test and parameter-training data. Section 4.3 describes the evaluation measures we used; these include fairly standard measures, such as precision and recall, and novel measures, based on the notion of compatible brackets, that we developed to overcome some of the shortcomings of the standard measures in the case of evaluating segmentations.

### 4.1 Data and Training Procedures

Our experimental data was drawn from 150 megabytes of 1993 Nikkei newswire; Figure 1 gives some statistics on this corpus. Five 500-sequence held-out subsets were obtained from this corpus for parameter training and algorithm testing; the rest of the data served as the unsegmented corpus from which we derived character $`n`$-gram counts. The five subsets were extracted by randomly selecting kanji sequences of at least ten characters in length – recall from our discussion above that long kanji sequences are the hardest to segment \[Takeda and Fujisaki,1987\]. As can be seen from Figure 4, the average sequence length was around 12 kanji. The subsets were then annotated following the segmentation policy outlined in Section 4.2 below; as Figure 4 shows, the average word length was between two and three kanji characters. Finally, each of these five subsets was randomly split into a 50-sequence parameter-training set and a 450-sequence test set. Any sequences occurring in both a test set and its corresponding parameter-training set were discarded from the parameter-training set in order to guarantee that these sets were disjoint (recall that we are especially interested in the unknown word problem); typically, no more than five sequences needed to be removed.

Parameter training for our algorithm consisted of trying all nonempty subsets of $`\{2,3,4,5,6\}`$ for thetango set of $`n`$-gram orders $`N`$ and all values in $`\{.05,.1,.15,\mathrm{},1\}`$ for the threshold $`t`$. In cases where two parameter settings gave the same training-set performance, ties were deterministically broken by preferring smaller cardinalities of $`N`$, shorter $`n`$-grams in $`N`$, and larger threshold values, in that order.

The results for Chasen and Juman reflect the lexicon additions described in Section 3.

### 4.2 Annotation Policies for the Held-Out Sets

To obtain the gold-standard annotations, the five held-out sets were segmented by hand. This section describes the policies we followed to create the segmentations. Section 4.2.1 gives an overview of the basic guidelines we used. Section 4.2.2 goes into further detail regarding some specific situations in Japanese.

#### 4.2.1 General policy

The motivation behind our annotation policy is Takeda and Fujisaki’s \[Takeda and Fujisaki,1987\] observation that many kanji compound words consist of two-character stem words together with one-character prefixes and suffixes. To handle the question of whether affixes should be treated as separate units or not, we devised a two-level bracketing scheme, so that accuracy can be measured with respect to either level of granularity without requiring re-annotation. At the word level, stems and their affixes are bracketed together as a single unit. At the morpheme level, stems are divided from their affixes. For example, the sequence (telephone) would have the segmentation (\[\[phone\]\[device\]\]) because (phone) can occur on its own, but (-device) can appear only as an affix.

We observe that both the word level and the morpheme level are important in their own right. Loosely speaking, word-level segments correspond to discourse entities; they appear to be a natural unit for native Japanese speakers (see next paragraph), and seem to be the right granularity for document indexing, question answering, and other end applications. On the other hand, morpheme-level brackets correspond to strings that cannot be further divided without loss of meaning — for instance, if one segments into (electricity) and (speech), the meaning of the phrase becomes quite different. Wu \[Wu,1998\] argues that indivisible units are the proper output of segmentation algorithms; his point is that segmentation should be viewed as a pre-processing step that can be used for many purposes.

Three native Japanese speakers participated in the annotation process: one (the first author) segmented all the held-out data based on the above rules, and the other two reviewed666We did not ask the other two to re-annotate the data from scratch because of the tedium of the segmentation task. 350 sequences in total. The percentage of agreement with the first person’s bracketing was 98.42%: only 62 out of 3927 locations were contested by a verifier. Interestingly, all disagreement was at the morpheme level.

#### 4.2.2 Special situations

It sometimes happens that a character that can occur on its own serves as an affix in a particular case. Our decision was to annotate such characters based on their role. For example, although both (Nagano) and (city) can appear as individual words, (the city of Nagano) is bracketed as , since here serves as a suffix. As a larger example, here is the annotation of a full sequence appearing in our datasets:

(\[elementary school\]\[building interior\]\[\[sports\]\[area\]\]\[construction\], i.e. construction of an elementary-school indoor arena). Each bracket encloses a noun. Here, is treated as an affix and thus bracketed as a morpheme, although it can also appear as an independent word as well. On the other hand, has not been placed in its own segment even though it is by itself also a word (small) – otherwise, we would get small school rather than the intended elementary school.

Numeric strings (i.e., sequences containing characters denoting digits) such as (one-nine-nine-three-year, the year 1993), are another grey area. In fact, Chasen and Juman appear to implement different segmentation policies with respect to this type of character sequence. The issue arises not just from the digit characters (should each one be treated as an individual segment, or should they be aggregated together?), but also classifiers. In Japanese, classifiers are required after numbers to indicate the unit or type of the quantity. That is, one must say (transfer777This word is two kanji characters long.-car-three-ten-$``$car-unit$``$, thirty imported cars); omitting the classifier so as to literally say “thirty imported cars” (\*) is not permissible.

Our two-level bracketing scheme makes the situation relatively easy to handle. In our annotations, the word level forms a single unit out of the digit characters and subsequent classifier. At the morpheme level, the characters representing the actual number are treated as a single unit, with the classifier serving as suffix. For instance, is segmented as (\[\[one-nine-nine-three\]\[year\]\]). Also, to even out the inconsistencies of the morphological analyzers in their treatment of numerics, we altered the output of all the algorithms tested, including our own, so as to conform to our bracketing; hence, our numerics segmentation policy did not affect the relative performance of the various methods. Since in practice it is easy to implement a post-processing step that concatenates together number kanji, we do not feel that this change misrepresents the performance of any of the algorithms. Indeed, in our experience the morphological analyzers tended to over-segment numeric sequences, so this policy is in some sense biased in their favor.

### 4.3 Evaluation Metrics

We used a variety of evaluation metrics in our experiments. These include the standard metrics of word precision, recall, and F measure; and morpheme precision, recall, and F measure. Furthermore, we developed two novel metrics, the compatible brackets and all-compatible brackets rates, which combine both levels of annotation brackets.

#### 4.3.1 Word and morpheme precision, recall, and F

Precision and recall are natural metrics for word segmentation. Treating a proposed segmentation as a non-nested bracketing (e.g., “$`|`$AB$`|`$C$`|`$” corresponds to the bracketing “\[AB\]\[C\]”), word precision ($`P`$) is defined as the percentage of proposed brackets that exactly match word-level brackets in the annotation; word recall ($`R`$) is the percentage of word-level annotation brackets that are proposed by the algorithm in question; and word F combines precision and recall via their harmonic mean: $`F=2PR/(P+R)`$. See Figure 5 for some examples of word precision and recall errors.

The morpheme metrics are all defined analogously to their word counterparts. See Figure 5 for examples of morpheme precision and recall errors.

#### 4.3.2 Compatible-brackets and all-compatible brackets rates

Word-level and morpheme-level accuracy are natural performance metrics. However, they are clearly quite sensitive to the test annotation, which is an issue if there are ambiguities in how a sequence should be properly segmented. According to Section 4.2, there was 100% agreement among our native Japanese speakers on the word level of segmentation, but there was a little disagreement at the morpheme level. Also, the authors of Juman and Chasen may have constructed their default dictionaries using different notions of word and morpheme than the definitions we used in annotating the data. Furthermore, the unknown word problem leads to some inconsistencies in the morphological analyzers’ segmentations. For instance, well-known university names are treated as single segments by virtue of being in the default lexicon, whereas other university names are divided into the name and the word “university”.

We therefore developed two more robust metrics, adapted from measures in the parsing literature, that penalize proposed brackets that would be incorrect with respect to any reasonable annotation. These metrics account for two types of errors. The first, a crossing bracket, is a proposed bracket that overlaps but is not contained within an annotation bracket \[Grishman, Macleod, and Sterling,1992\]. Crossing brackets cannot coexist with annotation brackets, and it is unlikely that another human would create them.888The situation is different for parsing, where attachment decisions are involved. The second type of error, a morpheme-dividing bracket, subdivides a morpheme-level annotation bracket; by definition, such a bracket results in a loss of meaning. See Figure 5 for some examples of these types of errors.

We define a compatible bracket as a proposed bracket that is neither crossing nor morpheme-dividing. The compatible brackets rate is simply the compatible brackets precision, i.e., the percent of brackets proposed by the algorithm that are compatible brackets. Note that this metric accounts for different levels of segmentation simultaneously.

We also define the all-compatible brackets rate, which is the fraction of sequences for which all the proposed brackets are compatible. Intuitively, this function measures the ease with which a human could correct the output of the segmentation algorithm: if the all-compatible brackets rate is high, then the errors are concentrated in relatively few sequences; if it is low, then a human doing post-processing would have to correct many sequences.

It is important to note that neither of the metrics based on compatible brackets should be directly optimized in training, because an algorithm that simply brackets an entire sequence as a single word will be given a perfect score. Instead, we apply it only to measure the quality of test results derived by training to optimize some other criterion. Also, for the same reason, we only compare brackets rates for algorithms with reasonably close precision, recall, and/or F measure. Thus, the compatible brackets rates and all-compatible brackets rates should be viewed as auxiliary goodness metrics.

## 5 Experimental Results

We now report average results for all the methods over the five test sets using the optimal parameter settings for the corresponding training sets. In all performance graphs, the “error bars” represent one standard deviation.

The section is organized as follows. We first present our main experiment, reporting the results of comparison of tango to Chasen and Juman (Section 5.1). We see that our mostly-unsupervised algorithm is competitive with and sometimes surpasses their performance. Since these experiments demonstrate the promise of using a purely statistical approach, Section 5.2 describes our comparison against another mostly-unsupervised algorithm, sst \[Sun, Shen, and Tsou,1998\]. These experiments show that our method, which is based on very simple statistics, can substantially outperform methods based on more sophisticated functions such as mutual information. Finally, Section 5.3 goes into further discussion and analysis.

### 5.1 Comparison Against Morphological Analyzers

#### 5.1.1 Word and morpheme accuracy results

To produce word-level segmentations from Juman and Chasen, we altered their output by concatenating stems with their affixes, as identified by the part-of-speech information the analyzers provided.

Figure 6 shows word accuracy for Chasen, Juman, and our algorithm for parameter settings optimizing word precision, recall, and F-measure rates. As can be seen, in this case the choice of optimization criterion did not matter very much. tango achieves more than five percentage-points higher precision than Juman and Chasen. tango’s recall performance is also respectable in comparison to the morphological analyzers, falling (barely) between that of Juman and that of Chasen. Combined performance, as recorded by the F-measure, was about the same as Juman, and 4.22 percentage points higher than Chasen.

We also measured morpheme precision, recall, and F measure, all defined analogously to their word counterparts. Figure 7 shows the results. Unlike in the word accuracy case, the choice of training criterion clearly affected performance.

We see that tango’s morpheme precision was slightly lower than that of Chasen, and noticeably worse than for Juman. However, when we optimize for precision, the results for all three metrics are on average quite close to Chasen’s. tango’s recall results are substantially higher than for the morphological analyzers when recall was its optimization criterion. In terms of combined performance, tuning our algorithm for the F-measure achieves higher F-measure performance than Juman and Chasen, with the performance gain due to enhanced recall.

Thus, overall, we see that our method yields results rivalling those of morphological analyzers.

#### 5.1.2 Compatible brackets results

Figure 8 depicts the compatible brackets and all-compatible brackets rates for Chasen, Juman, and tango, using the three word accuracy metrics as training criteria for our method. tango does better on the compatible brackets rate and the all-compatible brackets rates than the morphological analyzers do, regardless of training optimization function used.

The results degrade if morpheme accuracies are used as training criteria, as shown in Figure 9. Analysis of the results shows that most of the errors come from morpheme-dividing brackets: the parameters optimizing morpheme recall and F-measure are $`N=\{2\}`$ and $`t=.5`$, which leads to a very profligate policy in assigning boundaries.

#### 5.1.3 Discussion

Overall, we see that our algorithm performs very well with respect to the morphological analyzers when word accuracies are used for training. At the morpheme level, the relative results for our algorithm in comparison to Chasen and Juman are mixed; recall and F are generally higher, but at the price of lower compatible brackets rates. The issue appears to be that single-character segments are common at the morpheme level because of affixes. The only way our algorithm can create such segments is by the threshold value, but too low a threshold causes precision to drop.

A manual (and quite tedious) analysis of the types of errors produced in the first test set reveals that the major errors our algorithm makes are mis-associating affixes (e.g., wrongly segmenting as ) and fusing single-character words to their neighbors (e.g. wrongly segmenting as ). Both of these are mistakes involving single characters, a problem just discussed. Another common error was the incorrect concatenation of family and given names, but this does not seem to be a particularly harmful error. On the other hand, the morphological analyzers made many errors in segmenting proper nouns, which are objects of prime importance in information extraction and related tasks, whereas our algorithm made far fewer of these mistakes.

In general, we conclude that tango produces high-quality word-level segmentations rivaling and sometimes outperforming morphological analyzers, and can yield morpheme accuracy results comparable to Chasen, although the bracket-metrics quality of the resultant morpheme-level segmentations is not as good. The algorithm does not fall prey to some of the problems in handling proper nouns that lexico-syntactic approaches suffer. Developing methods for improved handling of single-character morphemes would enhance the method, and is a direction for future work.

### 5.2 Comparison against sst

We further evaluated our algorithm by comparing it against another mostly-unsupervised algorithm: that of Sun, Shen, and Tsou \[Sun, Shen, and Tsou,1998\] (henceforth sst), which, to our knowledge, is the segmentation technique most similar to the one we have proposed. Our goal in these experiments was to investigate the null hypothesis that any reasonable $`n`$-gram-based method could yield results comparable to Chasen and Juman.

sst also performs segmentation without using a grammar, lexicon, or large amounts of annotated training data; instead, like tango, it relies on statistics garnered from an unsegmented corpus. Although Sun et al. implemented their method on Chinese (which also lacks space delimiters) instead of Japanese, they designed sst to be able to account for “two common construction types in Chinese word formation: ‘2 characters + 1 character’ and ‘1 character + 2 characters” (pg. 1269). As pointed out in Section 4.2.1 above, Japanese kanji compound words often have a similar structure \[Takeda and Fujisaki,1987\]; hence, we can apply sst to kanji as well, after appropriate parameter training.

#### 5.2.1 The sst Algorithm

Like our algorithm, sst seeks to determine whether a given location constitutes a word boundary by looking for evidence of cohesion (or lack thereof) between the characters bordering the location. Recall the situation described by Figure 2: we have the character sequence “A B C D W X Y Z”, and must decide whether the location between D and W should be a boundary. The evidence sst uses comes from two sources. The first is the (pointwise or Fano) mutual information999This function (and its more probabilistically-motivated cousin the Shannon or average mutual information \[Cover and Thomas,1991\]) has a long and distinguished history in natural language processing. In particular, it has been used in other segmentation algorithms \[Sproat and Shih,1990, Wu and Su,1993, Lua,1995\]; interestingly, Magerman and Marcus \[Magerman and Marcus,1990\] also used a variant of the mutual information to find constituent boundaries in English. between D and W: $`mi(\mathrm{D},\mathrm{W})=\mathrm{log}(p(\mathrm{D},\mathrm{W})/(p(\mathrm{D})p(\mathrm{W}))).`$ The other statistic is the difference in t-score \[Church and Hanks,1990\] for the two trigrams CDW and DWX straddling the proposed boundary:

$$dts(\mathrm{D},\mathrm{W})=\frac{p(\mathrm{W}|\mathrm{D})P(\mathrm{D}|\mathrm{C})}{\sqrt{\mathrm{var}(p(\mathrm{W}|\mathrm{D}))+\mathrm{var}(p(\mathrm{D}|\mathrm{C}))}}\frac{p(\mathrm{X}|\mathrm{W})P(\mathrm{W}|\mathrm{D})}{\sqrt{\mathrm{var}(p(\mathrm{X}|\mathrm{W}))+\mathrm{var}(p(\mathrm{W}|\mathrm{D}))}}$$

Note that both the mutual information and the difference in t-score can be computed from character bigram statistics alone, as gathered from an unsegmented corpus.

Segmentation decisions are made based on a threshold $`\theta `$ on the mutual information, and on thresholds for the first and secondary local maxima and minima of the difference in t-score. There are six such free extremum parameters. In addition, we treated $`\theta `$ as another free parameter in our re-implementation; Sun et al. simply set it to the same value (namely, 2.5) that Sproat and Shih \[Sproat and Shih,1990\]) used. These seven parameters together yield a rather large parameter search space. For our implementation of the parameter training phase (Sun et al.’s paper does not give details), we set each of the six extremum thresholds101010The values to be thresholded are defined to be non-negative. to all the values in the set $`\{0,50,100,150,200\}`$ and the mutual information threshold111111It is the case that the pointwise mutual information can take on a negative value, but this indicates that the two characters occur together less often than would be expected under independence assumptions. Therefore, since the threshold is used to determine locations that should not be boundaries, non-negative thresholds suffice.  to all values in the set $`\{0,1.25,2.5,3.75,5\}`$. Ties in training set performance — which were plentiful in our experiments — were broken by choosing smaller parameter values. We used the same count tables (i.e. with singleton $`n`$-grams deleted and unseen $`n`$-grams given a count of one) as for tango.

While local extrema and thresholds also play a important role in our method, we note that sst is considerably more complex than the algorithm we have proposed. Also observe that it makes use of conditional probabilities, whereas we simply compare frequencies.

#### 5.2.2 sst Results

Figures 10 and 11 show the word and morpheme accuracy results.121212Church and Hanks \[Church and Hanks,1990\] actually suggested using two different ways to estimate the probabilities used in the t-score: the maximum likelihood estimate (MLE) and the expected likelihood estimate (ELE). According to Sun (personal communication), the MLE was used in the original implementation, although Church and Hanks suggested that the ELE would be better. We experimented with both, finding that they gave generally similar results. For consistency with Sun et al.’s experiments, we plot the MLE results only. The only case in which using the ELE rather than the MLE made a substantial difference was in morpheme precision, which improved by five percentage points (not enough to change the relative performance rankings).  Clearly, sst does not perform as well as Juman at either level of segmentation granularity. Since the accuracy results are so much lower than the other algorithms, we do not apply the brackets metrics, for the reasons discussed above.

It is clear that our algorithm outperforms sst, even though sst uses much more sophisticated statistics. Note that we incorporate $`n`$-grams of different orders, whereas sst essentially relies only on character bigrams, so at least some of the gain may be due to our using more sources of information from the unsegmented training corpus. We do not regard this as an unfair advantage because incorporating higher-order $`n`$-grams is easy to do for our method, and adds no conceptual overhead, whereas extending the mutual information to trigrams and larger $`n`$-grams can be a complex procedure \[Magerman and Marcus,1990\].

Stepping back, though, we note that our goal is not to emphasize the comparison with the particular algorithm sst, especially since it was developed for Chinese rather than Japanese. Rather, what we conclude from these experiments is that it is not necessarily easy for weakly-supervised statistical algorithms to do as well as morphological analyzers, even if they are given large amounts of unsegmented data as input and even if they employ well-known statistical functions. This finding further validates the tango algorithm.

### 5.3 Further Explorations

Given tango’s good performance in comparison to Chasen and Juman, we examined the role of the amount of parameter-training data tango is given as input, and investigated the contributions of the algorithm’s two parameters.

#### 5.3.1 Minimal human effort is needed.

In contrast to our mostly-unsupervised method, morphological analyzers need a lexicon and grammar rules built using human expertise. The workload in creating dictionaries on the order of hundreds of thousands of words (the size of Chasen’s and Juman’s default lexicons) is clearly much larger than annotating the small parameter-training sets for our algorithm. tango also obviates the need to segment a large amount of parameter-training data because our algorithm draws almost all its information from an unsegmented corpus. Indeed, the only human effort involved in our algorithm is pre-segmenting the five 50-sequence parameter training sets, which took only 42 minutes.131313Annotating all the test data for running comparison experiments takes considerably longer. In contrast, previously proposed supervised approaches to Japanese segmentation have used annotated training sets ranging from 1000-5000 sentences \[Kashioka et al.,1998\] to 190,000 sentences \[Nagata,1996a\].

To test how much annotated training data is actually necessary, we experimented with using miniscule parameter-training sets: five sets of only five strings each (from which any sequences repeated in the test data were discarded). It took only 4 minutes to perform the hand segmentation in this case.

Figure 12 shows the results. For instance, we see that training tango on five training sequences yielded 6.18 percentage points higher precision than using Juman with the same five training sequences; thus, our algorithm is making very efficient use of even very small training sets. The third data column proves that the information we provide Juman from the annotated training data does help, in that using smaller training sets results in lower performance. According to the fourth data column, performance doesn’t change very much if our algorithm gets only five training sequences instead of 50. Interestingly, the last column shows that if our algorithm has access to only five annotated sequences when Juman has access to ten times as many, we still achieve better precision and comparable F-measure.

#### 5.3.2 Both the local maximum and threshold conditions contribute.

Recall that in our algorithm, a location $`k`$ is deemed a word boundary if the evidence $`v_N(k)`$ is either (1) a local maximum or (2) at least as big as the threshold $`t`$. It is natural to ask whether we really need two conditions, or whether just one would suffice.141414Goldsmith \[Goldsmith,2001\] notes that the “peaks vs. threshold” question (for different functions) has arisen previously in the literature on morphology induction for European languages; see page 158 of that paper for a short summary. For instance, while $`t`$ is necessary for producing single-character segments, perhaps it also causes many recall errors, so that performance is actually better when the threshold criterion is ignored.

We therefore studied whether optimal performance could be achieved using only one of the conditions. Figure 13 shows that in fact both contribute to producing good segmentations. Indeed, in some cases, both are needed to achieve the best performance; also, each condition when used in isolation yields suboptimal performance with respect to some performance metrics.

## 6 Related Work

### 6.1 Japanese Segmentation

Many previously proposed segmentation methods for Japanese text make use of either a pre-existing lexicon \[Yamron et al.,1993, Matsumoto and Nagao,1994, Takeuchi and Matsumoto,1995, Nagata,1997, Fuchi and Takagi,1998\] or a substantial amount of pre-segmented training data \[Nagata,1994, Papageorgiou,1994, Nagata,1996a, Kashioka et al.,1998, Mori and Nagao,1998, Ogawa and Matsuda,1999\]. Other approaches bootstrap from an initial segmentation provided by a baseline algorithm such as Juman \[Matsukawa, Miller, and Weischedel,1993, Yamamoto,1996\].

Unsupervised, non-lexicon-based methods for Japanese segmentation do exist, but often have limited applicability when it comes to kanji. Both Tomokiyo and Ries \[Tomokiyo and Ries,1997\] and Teller and Batchelder\[Teller and Batchelder,1994\] explicitly avoid working with kanji characters. Takeda and Fujisaki \[Takeda and Fujisaki,1987\] propose the short unit model, a type of Hidden Markov Model with linguistically-determined topology, for segmenting certain types of kanji compound words; in our five test datasets, we found that 13.56% of the kanji sequences contain words that the short unit model cannot handle.

Ito and Kohda’s \[Ito and Kohda,1995\] completely unsupervised statistical algorithm extracts high-frequency character $`n`$-grams as pseudo-lexicon entries; a standard segmentation algorithm is then used on the basis of the induced lexicon. But the segments so derived are only evaluated in terms of perplexity and intentionally need not be linguistically valid, since Ito and Kohda’s interest is not in word segmentation but in language modeling for speech.

### 6.2 Chinese Segmentation

There are several varieties of statistical Chinese segmentation algorithms that do not rely on syntactic information or a lexicon, and hence could potentially be applied to Japanese. One vein of work relies on the mutual information \[Sproat and Shih,1990, Lua and Gan,1994\]; sst can be considered a more sophisticated variant of these since it also incorporates t-scores. There are also algorithms that leverage pre-segmented training data \[Palmer,1997, Dai, Loh, and Khoo,1999, Teahan et al.,2000, 1\].151515Brent and Tao’s algorithm can, in principle, work with no annotated data whatsoever. However, their experiments show that at least 4096 words of segmented training data were required to achieve precision over 60%. Finally, the unsupervised, knowledge-free algorithms of Ge, Pratt, and Smyth \[Ge, Pratt, and Smyth,1999\] and Peng and Schuurmans \[Peng and Schuurmans,2001\] both require use of the EM algorithm to derive the most likely segmentation; in contrast, our algorithm is both simple and fast.

## 7 Conclusion

In this paper, we have presented tango, a simple, mostly-unsupervised algorithm that segments Japanese sequences into words based on statistics drawn from a large unsegmented corpus. We evaluated performance on kanji with respect to several metrics, including the novel compatible brackets and all-compatible brackets rates, and found that our algorithm could yield performances rivaling that of lexicon-based morphological analyzers. Our experiments also showed that a similar previously-proposed mostly-unsupervised algorithm could not yield comparable results.

Since tango learns effectively from unannotated data, it represents a robust algorithm that is easily ported to other domains and applications. We view this research as a successful application of the (mostly) unsupervised learning paradigm: high-quality information can be extracted from large amounts of raw data, sometimes by relatively simple means.

On the other hand, we are by no means advocating a purely statistical approach to the Japanese segmentation problem. We have explicitly focused on long sequences of kanji as being particularly problematic for morphological analyzers such as Juman and Chasen, but these analyzers are well-suited for other types of sequences. We thus view our method, and mostly-unsupervised algorithms in general, as complementing knowledge-based techniques, and conjecture that hybrid systems that rely on the strengths of both kinds of methods will prove to be the most effective in the future.

## Acknowledgments

We thank Michael Oakes, Hirofumi Yamamoto, and the anonymous referees for very helpful comments. We would like to acknowledge Takashi Ando and Minoru Shindoh for reviewing the annotations, and Sun Maosong for advice in implementing the algorithm of Sun et al. \[Sun, Shen, and Tsou,1998\]. Thanks to Stuart Shieber for reference suggestions. A preliminary version of this work was published in the proceedings of NAACL 2001; we thank the anonymous reviewers of that paper for their comments. This research was conducted while the first author was a graduate student at Cornell University. This material is based on work supported in part by a grant from the GE Foundation and by the National Science Foundation under ITR/IM grant IIS-0081334.


format: text

text:
# Topological complexity, contact order and protein folding rates

## I INTRODUCTION

The search for correlations between the protein folding kinetics and the native state equilibrium properties (i.e. chain length and stability) presents a major challenge for those working in the field of protein folding, both in theory and experiments. Progress has been significantly hindered by difficulty analyzing the folding of protein molecules larger than about 100 amino acids, whose kinetics is widely believed to be based on some multiexponential mechanism . By contrast, for smaller proteins whose folding kinetics is close to single exponential, there seems to be some consensus as to the dependence of the folding time, $`t`$, on native state stability .

Experiment and theory appear to be at odds with each other over the dependence of the folding time on the number $`N`$ of amino acids in the folding unit. Recent Monte Carlo (MC) simulations  of a simple lattice model have proposed that, for two-state proteins, a scaling law of the type $`tN^\lambda `$, $`\lambda 5`$, appropriately describes the dependence of the folding time on the chain length, $`N`$; a weaker dependence ($`\lambda 4`$) has been previously reported in Ref.6 for the same model Hamiltonian and distribution of contact energies, and in Ref.7 for a two-letter alphabet model that, apart from the commonly used isotropic contact interactions, also considers orientation-dependent interactions. However, available experimental data shows no correlation between $`t`$ and $`N`$ .

We examine here the influence of the native state geometric properties on the protein folding kinetics in the context of MC simulation. One simple parameter of the geometry which has already attracted attention is contact order, measuring the average length of the backbone loops connecting contacting pairs of residues in the structure . Formally, the relative contact order, $`CO`$, is defined as

$$CO=\frac{1}{LN}\underset{i,j}{\overset{N}{}}\mathrm{\Delta }_{i,j}|ij|,$$
(1)
where $`N`$ is the total number of amino acid residues in the protein, $`L`$ is the total number of contacts, and $`\mathrm{\Delta }_{i,j}=1`$ if residues $`i`$ and $`j`$ are in contact and is 0 otherwise. $`|ij|`$ is the backbone separation between residues $`i`$ and $`j`$. High values of $`CO`$ are associated with protein structures where amino acid residues interact on average with others that are far away in sequence (long-range interactions), while those displaying predominantly local interactions are of low contact order.

A high correlation was found between the $`CO`$ parameter, and the folding rates for the protein set considered in Ref.3: proteins with ’low’ contact order tend to fold faster than proteins with ’high’ contact order. This finding strongly supports the view that native geometry strongly influences the kinetics of the rate-limiting step in the two-state mechanism of small protein molecules ($`N<100`$), determining their folding rates.

The connection between $`CO`$ and the dominant range of residue interactions brings back the controversial issue of the importance of local (and non-local) contacts in the dynamics of protein folding. An argument against local contacts is that they might increase the ’roughness’ of the energy landscape, and therefore the stability of the unfolded state . On the other hand, an argument supporting local interactions is based on the idea that they might provide the ideal substrate for the development of nucleation or initiation sites, small local sequence substructures forming in an early stage of folding and driving the subsequent pathway . Moreover, the formation of non-local contacts in early folding is entropically costly as it restricts the number of conformations available to the folding unit .

The limited amount of experimental information available  suggests that investigating this problem within the scope of theoretical models could give more insight.

## II MODEL AND METHODS

To achieve this goal we consider a simple three dimensional lattice model of a protein molecule whose Hamiltonian is given by the contact approximation,

$$H(\{\sigma _i\},\{\stackrel{}{r_i}\})=\underset{i>j}{\overset{N}{}}ϵ(\sigma _i,\sigma _j)\mathrm{\Delta }(\stackrel{}{r_i}\stackrel{}{r_j}),$$
(2)
where $`\{\sigma _i\}`$ stands for an amino acid sequence ($`\sigma _i`$ being the chemical identity of bead $`i`$) while $`\{\stackrel{}{r_i}\}`$ is the set of bead coordinates that define a certain conformation. The contact function, $`\mathrm{\Delta }`$, equals $`1`$ if beads $`i`$ and $`j`$ are in contact but not covalently linked, and is $`0`$ otherwise. We follow many previous studies in taking the interaction parameters $`ϵ`$ from the $`20\times 20`$ Miyazawa-Jerningan matrix derived from the distribution of contacts in native proteins . Our folding simulations follow the standard MC Metropolis algorithm  and the kink-jump MC move set (end-move, corner-flip, and crankshaft).

## III NUMERICAL RESULTS

### A Contact order and homopolymer kinetics

We have explored the distribution of the relative contact order parameter over a population of 2000 maximally compact target geometries found by homopolymer relaxation . This distribution is shown in Figures 1(a)-(e) for each of the studied chain lengths $`N=36`$,$`48`$,$`54`$,$`64`$ and $`80`$, which are all commensurate with folding to fill a simple cuboid. There is only a slight shift in the modal contact order with chain length, from $`0.19`$ for $`N=36`$,$`48`$ down to $`0.17`$ for higher $`N`$. However, the target fraction in the histogram tail ($`CO0.22`$) is significantly smaller for $`N54`$ than for shorter chains. Interestingly, the values of $`CO`$ found for these lattice proteins span approximately the same range as those found in real kinetically characterized single domain proteins ($`0.0745CO0.2120`$) .

We have also checked the intrinsic kinetic accessibility of the compact configurations obtained, by measuring the time $`t_{col}`$ for these configurations to be reached under homopolymer relaxation. Figure 1(f) shows there is no evident correlation between $`t_{col}`$ and CO .

### B Finding the optimal folding temperature

To investigate the relationship between protein folding and contact order, (at least) 20 target conformations for each chain length, were selected so as to sample uniformly across the range of contact order. For each target an ensemble of 100 designed sequences was prepared by using the design method developed by Shakhnovich and Gutin  based on random heteropolymer theory, and simulated annealing techniques. The average trained sequence energy, $`<E>`$, is shown in Table I along with the standard deviation of the energy distribution, $`\sigma `$. Except for $`N=54`$, the chemical composition of the designed sequences was the same as the one used in Ref.5. In that study it was shown that the optimal folding temperature, $`T_{fold}(N)`$, defined as the temperature that minimizes the folding time, is close to a self-averaging parameter.

Since the Shakhnovich and Gutin design scheme preserves the overall sequence chemical composition we can safely use for 36 and 48 bead long sequences studied here the $`T_{fold}(36)`$ and $`T_{fold}(48)`$ found in Ref.5.

For the longer $`N`$, and most particularly $`N=80`$, foldicity, defined as the fraction of successful folding runs over the total number of attempted runs, was for the vast majority of the targets less than unity. This forced us to define the optimal folding temperature, $`T_{fold}(N)`$, is such cases as the temperature which optimized foldicity rather than the temperature which minimized the folding time. The case $`N=48`$ sits at the margin and provides confirmation that the two approaches to $`T_{fold}(N)`$ are not in conflict, as shown in Figure. 2.

### C Contact order and folding kinetics

After determining $`T_{fold}(N)`$ we ran a MC folding simulation for every designed sequence. The simulations proceeded until $`\tau _{max}(N)`$ MC steps or until folding was observed. The value of $`\tau _{max}(N)`$ was chosen such that it was much longer than the typical folding time of the studied sequences.

Fig. 3 shows the dependence of the folding time, $`t`$, on the contact order parameter for chain lengths $`N=36`$ and $`N=48`$. The folding time was computed as the mean first passage time averaged over 100 simulation runs. In either case the points are close to be uniformly distributed suggesting no correlation between the $`CO`$, and the folding time for these chain lengths. Here and elsewhere error bars indicate $`\pm `$ one standard error in the mean.

Figures 4(a)-(c) show the dependence of foldicity on $`CO`$ for $`N=54,64`$ and $`N=80`$ respectively. The results presented in Figures. 4(d)-(f) show, for the same chain lengths, the dependence of the estimated folding time on the relative contact order paramenter. Two distinct scenarios emerge from the analysis of the graphs:

1. For $`CO0.17`$ there is no correlation between foldicity (or folding time) and the relative contact order parameter;
2. For $`CO>0.17`$, a general trend towards decreasing foldicity with increasing relative contact order can be observed. In this regime, a considerably strong positive correlation of $`r=0.70,0.70`$ and $`0.79`$, between $`t`$ and $`CO`$, shows up for chain lengths $`N=54,64`$ and $`80`$ respectively.

## IV DISCUSSION AND CONCLUSIONS

The ’turning point’ value of $`CO=0.17`$ is actually the peak of the homopolymer relaxation histogram distribution as previously discussed. This means that $`CO`$ and folding time are positively correlated only for proteins with predominantly non-local contacts. We interpret this result as a consequence of the properties of the move set used to explore the conformational space together with the ruggedness of the energy landscape. As seen in section III A, kink-jump dynamics does not favour the formation of high $`CO`$ structures in homopolymers. In proteins, when the native structure is of high $`CO`$, it will be difficult to escape from kinetic traps associated with local energy minima and structures of lower $`CO`$. This confirms and explains our previous findings  according to which the folding performance achievable is strongly sensitive to target conformation for chain lengths $`N80`$.

The comparison of the simulation’s results with the experimental data set of 24 two-state proteins, with chain length ranging from 41 to 154 amino acids, reported in Ref.3 is hindered by the fact that the proteins considered in Ref.3 fail to exhibit the scaling of folding time with chain length which is typical of lattice model simulations. However, a strong correlation ($`r=0.80`$) is also found between $`CO`$ and the folding times. Moreover, this correlation is considerably improved ($`r=0.97`$) if only long protein chains ($`N80`$) are considered.

As a general conclusion, we might say that results on lattice models encourage the idea that the contact order of the native structure plays a significant role in determining the folding rate. The match with the correlation between the $`CO`$ and the folding time found from the analysis of experimental data suggests that lattice polymer dynamics with local moves does capture the key dynamical features of real protein folding.

It would be interesting to know if similar results can be found in the scope of ’off-lattice’ models, where one would expect proteins with high helical content to be better folders.

###### Acknowledgements.

P.F.N.F would like to thank Dr. A. Nunes for helpful suggestions, and Programa Praxis XXI for financial support.


text:
# Simulation of Markovian quantum dynamics on quantum logic networks

## I Introduction

Quantum computing offers a new perspective in simulating physical systems. While the simulation of a larger quantum system is intractable for a classical computer, it should be possible of course on a quantum computer. Quantum computers are, from a theoretical point of view, highly simplified quantum systems. A simulation of a real physical system on such an arrangement is therefore also interesting necessarily because of the usefulness of the simulation result, but also because it may reveal fundamental aspects of the real physical system, which may be obscure otherwise.

Maybe the most general problem of this kind would be the simulation of general quantum operations, the most general dynamics a quantum system can undergo. The idea is to represent the initial state of the system on a quantum bit array, and supplement it with another array embodying the environment. Subjecting this system to the effect of a quantum logic network, and dropping the environment bits, the resulting state of the data should be obtained. Naturally, having infinite resources, i.e. arbitrary number of “environment” bits, any operation can be carried out by realizing a unitary representation of the process. For a system with a $`k`$ dimensional Hilbert space, this requires a $`k^2`$ dimensional environment. Lloyd conjectured , that a general quantum operation on a system with a $`k`$ dimensional Hilbert-space can be simulated with a $`k`$-dimensional environment, which may be in a mixed sate initially. This conjecture was falsified by Terhal et al. , who give bounds to the dimensionality of the environment required to simulate certain quantum operations on a single qubit system. Zalka and Rieffel give a simpler proof via explicit construction of counterexamples. More optimal possibilities for the simulation, such as closed loop schemes were discussed in detail in Refs. .

Programmable quantum gate arrays or quantum processors  provide another possible approach to the problem. In this case, the parameters of the dynamics should be stored in the initial state of the “environment” (which play a role of the “program register” - see below). The quantum processor has two input registers, one storing the state of the system to be simulated (the “data register”), while the other contains the data of the operation to be performed. After the operation of the circuit, the remains of the program state in the program register may either be dropped or be subjected to a measurement. The latter is the probabilistic regime of the quantum processor. The result is accepted, if the measurement yields a given result. It was shown by Hillery et al. , that in this case, any operation can be implemented, though some of them with quite low probability of success. Recently Vidal et al.  have presented a probabilistic scheme implementing unitary transformations with rather high probability.

In this paper we restrict ourselves to the “deterministic” case, that is, the remains of the program register are dropped. Hillery et al.  have studied the possibility of implementing general quantum maps in such a scheme. They have shown, that there are certain limitations, e.g., an amplitude damping channel cannot be implemented. In addition to this, we show that different quantum circuits such as quantum teleportation  can be used as a programmable quantum circuit for some purpose, as it is related to a phase damping channel .

We focus here on a specific subset of quantum operations, namely Markovian dynamics. These processes are the most important ones in the description of quantum decoherence. The question of simulating Markovian dynamics in the quantum computing context was investigated by Bacon et al. . As one of their main results, these authors provide a decomposition rule to build more complex dynamics from simpler “primitive” operations. On the other hand, Bacon et al. apply the formalism of Gorini, Kossakowski and Sudarshan (GKS) , providing an excellent framework for the treatment of Markovian processes. We approach the problem of simulating Markovian dynamics differently in a way that is related to programmable quantum gate arrays. We restrict ourselves to single qubit dynamics, with a single qubit program register. We intend to simulate the *generator* of Markovian dynamics on a programmable quantum logic array, as the generator characterizes the time evolution completely in this case. A single run of the processor simulates an *infinitesimal* time step. As a further restriction we require that the length *infinitesimal time step* should be encoded into the initial state of the program register.

The paper is organized as follows: in Section II we review some definitions concerning Markovian dynamics, introducing Lindbladians, the generators of the dynamics. The standard GKS matrix-representation introduced by Gorini, Kossakowski and Shudarsan in Ref.  is reviewed, and a practical recipe is given for finding the GKS matrix from of a Lindbladian operator in the one-qubit case, utilizing the affine representation. In Section III we describe the general idea of simulating a generator, as understood in this paper. Section IV describes a reversible scheme capable of simulating a phase damping channel about an arbitrary axis. A geometrical interpretation of the result is also given. In Section V we discuss an application of Bennett’s teleportation scheme in this context. In section VI the results are summarized and conclusions are drawn.

## II Markovian dynamics of a qubit

In this Section we review the definition of Markovian semigroup and its generators very briefly. The most general operation, that a state of a qubit can undergo is described by a completely positive linear, trace preserving map acting on the set of density operators, also called a superoperator. This may be written in the Krauss-representation as

$$(\varrho )=\underset{k}{}E_k\varrho E_k^{}$$
(1)
where the $`E_k`$-s are positive operators such that $`E_k^{}E_k=1`$.

In order to introduce Markovian processes, one equips the set of superoperators with a continuous parameter $`t`$ which is called the time. Stationary and Markovian dynamics obey the property

$$_{t_1}_{t_2}=_{t_1+t_2},$$
(2)
with $`t_1,t_2>0`$. The set of superoperators with property (2) form a one-parameter semigroup, the Markovian semigroup. We also require the property

$$_0=\widehat{1},$$
(3)
(where $`\widehat{1}`$ stands for the identity superoperator) to hold.

The property in Eq. (2) enables us to define the generators of the semigroup as

$$\widehat{L}(\varrho )=\underset{t0+0}{lim}\frac{_t(\varrho )\varrho }{t}.$$
(4)
The operator $`\widehat{L}`$ is the infinitesimal generator of the time evolution:

$$_t=\mathrm{exp}(\widehat{L}t)=\underset{n\mathrm{}}{lim}\left(\widehat{1}\frac{t}{n}\widehat{L}\right)^n,$$
(5)
from which follows, that

$$\frac{\varrho (t)}{t}=\widehat{L}[\varrho (t)]$$
(6)
known as the master equation.

Let us consider an operator $`\widehat{L}`$ acting on the Hilbert space of a qubit. The question arises, under what condition can this operator represent a generator of the dynamical semigroup. The answer was given by Lindblad , and by Gorini, Kossakowski and Sudarshan (GKS) . We use the notation of the latter authors. According to this, the most general form of a generator of a Markovian semigroup reads

$$\widehat{L}(\varrho )=i[\widehat{H},\varrho ]+\frac{1}{2}\underset{i,j=1}{\overset{3}{}}C_{i,j}([\widehat{\sigma }_i\varrho ,\widehat{\sigma }_j]+[\widehat{\sigma }_i,\varrho \widehat{\sigma }_j]),$$
(7)
where the $`\widehat{\sigma }`$-s are the Pauli-matrices. The first contribution on the right hand size describes a possible unitary evolution, the Hamiltonian $`\widehat{H}`$ being a Hermitian matrix which can be chosen to be traceless without the loss of generality. The second contribution describes the stochastic part of the evolution. The Hermitian positive semidefinite matrix $`C_{i,j}`$ is called the GKS matrix, and it contains all the information on the nature of the dynamics. Note that in order to preserve the trace of the density matrix, $`\widehat{L}\varrho `$ should be traceless. In fact, Eq. (7) describes the most general linear operator taking $`\varrho `$ to a traceless matrix.

In the following we describe how to extract the Hamiltonian $`\widehat{H}`$ and the GKS matrix $`C`$, if one is given an arbitrary function of a single-qubit density matrix $`\varrho ^{}=\widehat{L}\varrho `$ In order to do so we utilize the relation between the GKS matrix and the affine representation described also in .

A generic density matrix can be expanded on the basis of the three Pauli-matrices and the unit operator, obtaining its usual real 3-vector representation $`\underset{¯}{r}`$ displayable on the unit radius Bloch sphere:

$$\underset{¯}{r}=\left(\begin{array}{c}r_1\\ r_2\\ r_3\end{array}\right),r_i=\text{tr}(\varrho \widehat{\sigma }_i),$$
(8)
so that

$$\varrho =\frac{1}{2}\left(\widehat{1}+\underset{i=1}{\overset{3}{}}r_i\widehat{\sigma }_i\right).$$
(9)
Direct calculation shows that the real 3-vector $`\widehat{L}[\underset{¯}{r}]`$ corresponding to the most general $`\widehat{L}\varrho `$ in Eq. (7) reads

$$\widehat{L}[\underset{¯}{r}]=\left(\begin{array}{ccc}0& h_3& h_2\\ h_3& 0& h_1\\ h_2& h_1& 0\end{array}\right)\underset{¯}{r}+\left(\begin{array}{ccc}2(C_{22}+C_{33})& C_{12}+C_{21}& C_{13}+C_{31}\\ C_{12}+C_{21}& 2(C_{11}+C_{33})& C_{23}+C_{32}\\ C_{13}+C_{31}& C_{23}+C_{32}& 2(C_{11}+C_{22})\end{array}\right)\underset{¯}{r}+2i\left(\begin{array}{c}C_{23}C_{32}\\ C_{31}C_{13}\\ C_{12}C_{21}\end{array}\right),$$
(10)
where

$$\widehat{H}=\frac{1}{2}\underset{i=1}{\overset{3}{}}h_i\widehat{\sigma }_i.$$
(11)
Thus $`\widehat{L}`$ appears as an affine linear mapping in the 3 space, the above mapping is called the affine representation of $`\widehat{L}`$.

If we are now given an arbitrary function $`\varrho ^{}`$, which is traceless and depends on the components of the arbitrary density matrix $`\varrho `$ linearly, we can find the corresponding $`\underset{¯}{r^{}}`$ according to Eq. (8) as a function of the components of $`\underset{¯}{r^{}}`$ representing $`\varrho `$. This is a linear inhomogenous operator, which can be always decomposed into a sum of a homogenous antisymmetric operator, a homogenous symmetric operator and a vector representing the inhomogenity. For qubits, this decomposition of the affine representation of the generator is quite meaningful: according to Eq. (10), the information on the unitary part of the generator, i.e. the Hamiltonian is encoded into the antisymmetric part of this operator, while the real and imaginary parts can be found from the symmetric part and the inhomogenity respectively.

In the absence of the inhomogenity the generator is zero for the identity operator:

$$\widehat{L}\widehat{I}=0,$$
(12)
thus it describes a unital evolution, which preserves the identity operator. The inhomogenity appears in the complex part of the elements of the GKS matrix: for qubits, real GKS matrices correspond to unital dynamics.

Thus equipped with Eq. (10), we have the recipe how to find the standard GKS form of a generator of a dynamical semigroup for a quantum bit.

## III Simulation of infinitesimal generators

We intend to simulate the infinitesimal generator $`L\widehat{\varrho }`$ of Markovian dynamics, on a single quantum bit. This can be understood in several ways. As an elementary step we consider the application of a quantum processor: an arrangement of quantum logic gates, and possibly measurements, acting on the qubit in argument, and certain ancillary systems. The ancillary systems can be used as a “program register”: their state can influence the action of the processor on the qubit in argument, which constitutes a “data bit” in this context.

The next question might be, how to interpret the time. A possible generic approach would be to regard the single run of the processor as a *finite* time step $`\mathrm{\Delta }t`$. The repeated application of the processor on the data bit results then in a discrete time evolution. One can then examine if this is a stroboscopic version of some valid continuous time evolution, and search for the proper master equation. This approach will be discussed elsewhere. Here we adopt a simpler interpretation: we expect a single run of processor to simulate an *infinitesimal* time step:

$$\varrho _{\text{out}}=\varrho _{\text{in}}+\widehat{L}\varrho _{\text{in}}dt+𝒪(dt^2),$$
(13)
where $`dt`$ should be encoded in the $`|\mathrm{\Psi }_{\text{prog}}`$ of the program register. The entire evolution can then be approximated with some accuracy by running this process many many times. This implements the equidistant first order Euler method of solving Eq. (6), but time step, and thereby the *accuracy* is encoded quantum mechanically. Of course, the simulation is completely accurate if $`dt0`$, and the number of repetitions tends to infinity. We remark here, that simulation of decoherence mechanisms with an array of quantum gates has proven to be fruitful in other problems too .

Physically, the simulation scheme can be envisaged as a simple collision model: The data qubit is represented by a physical system localized in space. It interacts with flying program bits represented by e.g. spin of particles emerging from an oven. Each program bit causes the system to evolve a small time step further.

It follows from Eq. (13), that there must exist a program state, for which $`dt=0`$, and thus $`\varrho _{\text{out}}=\varrho _{\text{in}}`$, in the quantum processor terminology we would say the processor implements the unit operator. It is a natural requirement for this kind of semigroup simulation. Thus our scheme is to some extent similar to the idea of simulating a reservoir with beam-splitters of transmittance around unity in quantum optics  or a quantum homogenization processes as described in Ref. .

## IV A scheme without a measurement

First we consider a simple deterministic scheme with a single ancillary qubit, as depicted in Fig. 1.

The first bit contains the program, which is most generally

$$|\mathrm{\Psi }_{\text{prog}}=\sqrt{1\epsilon }e^{i\chi }|0+\sqrt{\epsilon }|1,0\epsilon 1,\chi \text{real}.$$
(14)
We don’t consider mixed program states here, we want to study how decoherence associated with Markovian processes appears purely quantum-mechanically, and a mixed program state would imply some prescribed classical stochasticity. The input data is in bit 2, in the state $`\varrho _{\text{in}}`$. After the operation of the processor, the contents of the program register are dropped, and bit 2 contains the output

$$\varrho _{\text{out}}=\text{Tr}_1\left(\widehat{U}(|\mathrm{\Psi }_{\text{prog}}\mathrm{\Psi }_{\text{prog}}|\varrho _{\text{in}})U^{}\right)$$
(15)
which is passed for further processing.

To have the identity operator implemented, there should be a program state for which $`\varrho _{\text{out}}=\varrho _{\text{in}}`$ holds. We chose this to be the program state $`|0`$. The most general processor that is possible under such circumstances is a controlled U gate:

$$\widehat{U}=\left(\begin{array}{cc}\widehat{1}& 0\\ 0& \widehat{U}_2\end{array}\right)$$
(16)
The lower right corner is an $`SU(2)`$ block:

$$\widehat{U}_2=\left(\begin{array}{cc}\mathrm{cos}(\frac{\theta }{2})e^{i\frac{\varphi +\psi }{2}}& \mathrm{sin}(\frac{\theta }{2})e^{i\frac{\varphi \psi }{2}}\\ \mathrm{sin}(\frac{\theta }{2})e^{i\frac{\varphi \psi }{2}}& \mathrm{cos}(\frac{\theta }{2})e^{i\frac{\varphi +\psi }{2}}\end{array}\right),$$
(17)
where we use the standard Euler angle parametrization in the $`y`$ convention .

Now we can evaluate Eq. (13) with a generic input data state of Eq. (9), and program of Eq. (14), to obtain the effect of a single run of the processor. Note that due to the orthogonality of the program states corresponding to $`\widehat{1}`$ and $`\widehat{U}_2`$ (which is a consequence of the unitarity of $`\widehat{U}`$), Eq. (15) simplifies to

$$\varrho _{\text{out}}=(1\epsilon )\varrho _{\text{in}}+\epsilon \widehat{U}_2\varrho _{\text{in}}\widehat{U}_2^{}.$$
(18)
Thus from the point of view of the effect on the input state, the quantum circuit does nothing else than apply the unitary operation $`\widehat{U}_2`$ on the input state, with the probability $`\epsilon `$. The difference is that if the operation is realized by the quantum circuit, then the information which disappears from the system will be stored in the dropped quantum state of the program register. In the other case the information will be entirely classical, one bit per infinitesimal timestep: we can be aware, whether the operation $`\widehat{U}_2`$ was carried out or not. Note that in both of the cases the process is reversible, provided that we have the appropriate information at hand.

According to Eq. (18), we can write

$$\varrho _{\text{out}}=\varrho _{\text{in}}+(\widehat{U}_2\varrho _{\text{in}}\widehat{U}_2^{}\varrho _{\text{in}})\epsilon .$$
(19)
Thus we identify $`\epsilon =dt`$, and comparing with Eq. (13) we get

$$\widehat{L}\varrho _{\text{in}}=\widehat{U}_2\varrho _{\text{in}}\widehat{U}_2^{}\varrho _{\text{in}}.$$
(20)
The transformation on the Bloch ball corresponding to $`\widehat{U}_2\varrho \widehat{U}_2^{}`$ is a rotation of the vector $`\underset{¯}{r}`$ corresponding to $`\varrho `$

$$\underset{¯}{r}^{}=(\theta ,\varphi ,\psi )\underset{¯}{r},$$
(21)
where $``$ is the appropriate element of the adjoint representation of $`SU(2)`$:

$$(\theta ,\varphi ,\psi )=\left(\begin{array}{ccc}\mathrm{sin}\varphi \mathrm{sin}\psi +\mathrm{cos}\theta \mathrm{cos}\varphi \mathrm{cos}\psi & \mathrm{cos}\theta \mathrm{cos}\varphi \mathrm{sin}\psi \mathrm{sin}\varphi \mathrm{cos}\psi & \mathrm{sin}\theta \mathrm{cos}\varphi \\ \mathrm{cos}\theta \mathrm{sin}\varphi \mathrm{cos}\psi +\mathrm{cos}\varphi \mathrm{sin}\psi & \mathrm{cos}\varphi \mathrm{cos}\psi \mathrm{cos}\theta \mathrm{sin}\varphi \mathrm{sin}\psi & \mathrm{sin}\theta \mathrm{sin}\varphi \\ \mathrm{sin}\theta \mathrm{cos}\psi & \mathrm{sin}\theta \mathrm{sin}\psi & \mathrm{cos}\theta \end{array}\right)SO(3).$$
(22)
For the generator in Eq. (20) we have thus

$$\widehat{L}[\underset{¯}{r}]=\left((\theta ,\varphi ,\psi )\widehat{1}\right)\underset{¯}{r}.$$
(23)
This can be compared with Eq. (10) to extract the properties of the generator. The transformation in Eq. (23) is homogenous, thus the generated dynamics is unital.

As for the coherent part of the evolution, we get the Hamiltonian

$$\widehat{H}=\left(\begin{array}{cc}\mathrm{sin}(\varphi +\psi )\mathrm{cos}^2\frac{\theta }{2}& \frac{i}{2}\mathrm{sin}\theta \left(e^{i\varphi }+e^{i\psi }\right)\\ \frac{i}{2}\mathrm{sin}\theta \left(e^{i\varphi }+e^{i\psi }\right)& \mathrm{sin}(\varphi +\psi )\mathrm{cos}^2\frac{\theta }{2}\end{array}\right)$$
(24)
This is zero if $`\varphi +\psi =(2k+1)\pi `$ or $`\theta =\pi +2k\pi `$ holds, which is equivalent to $`\text{tr}U_2=0`$. Thus in case of traceless unitaries, we obtain a purely stochastic evolution in the sense that it lacks the Hamiltonian part.

Evaluating the symmetric part of Eq. (22), and comparing with (10), we obtain the GKS matrix

$$C_{\theta ,\varphi ,\psi }=\left(\begin{array}{ccc}\mathrm{sin}^2\frac{\theta }{2}\mathrm{sin}^2\frac{\varphi \psi }{2}& \frac{1}{2}\mathrm{sin}^2\frac{\theta }{2}\mathrm{sin}(\psi \varphi )& \frac{1}{4}\mathrm{sin}\theta (\mathrm{cos}\varphi \mathrm{cos}\psi )\\ \frac{1}{2}\mathrm{sin}^2\frac{\theta }{2}\mathrm{sin}(\psi \varphi )& \mathrm{sin}^2\frac{\theta }{2}\mathrm{cos}^2\frac{\varphi \psi }{2}& \frac{1}{4}\mathrm{sin}\theta (\mathrm{sin}\varphi +\mathrm{sin}\psi )\\ \frac{1}{4}\mathrm{sin}\theta (\mathrm{cos}\varphi \mathrm{cos}\psi )& \frac{1}{4}\mathrm{sin}\theta (\mathrm{sin}\varphi +\mathrm{sin}\psi )& \mathrm{cos}^2\frac{\theta }{2}\mathrm{sin}^2\frac{\varphi +\psi }{2}\end{array}\right)$$
(25)
Specifically, if $`\widehat{U}_2`$ is traceless because $`\psi =\pi \varphi `$ holds, we obtain from Eq. (25) the following GKS matrix:

$$C_{\theta ,\varphi }=\left(\begin{array}{ccc}\mathrm{sin}^2\frac{\theta }{2}\mathrm{cos}^2\varphi & \frac{1}{2}\mathrm{sin}^2\frac{\theta }{2}\mathrm{sin}(2\varphi )& \frac{1}{2}\mathrm{sin}\theta \mathrm{cos}\varphi \\ \frac{1}{2}\mathrm{sin}^2\frac{\theta }{2}\mathrm{sin}2\varphi & \mathrm{sin}^2\frac{\theta }{2}\mathrm{sin}^2\varphi & \frac{1}{2}\mathrm{sin}\theta \mathrm{sin}\varphi \\ \frac{1}{2}\mathrm{sin}\theta \mathrm{cos}\varphi & \frac{1}{2}\mathrm{sin}\theta \mathrm{sin}\varphi & \mathrm{cos}^2\frac{\theta }{2}\end{array}\right)$$
(26)
The matrix in Eq. (26) can be interpreted as follows. Consider a unitary operator $`𝒰SU(2)`$ acting on the qubit’s Hilbert space, and a superoperator $``$, which describes unitary evolution described by the GKS matrix $`C`$. According to Ref.  *unitary conjugation* of a superoperator $``$, that is,

$$^{}=𝒰^{}𝒰,$$
(27)
where $`𝒰(\varrho )=𝒰\varrho 𝒰^{}`$ yields another superoperator describing Markovian dynamics as well. The resulting GKS matrix is

$$C^{}=C^T,$$
(28)
where $``$ is the element of $`SO(3)`$, the adjoint representation of $`SU(2)`$ corresponding to $`𝒰`$, and the $`T`$ stands for transposition. Thus $``$ is a real 3-rotation, which can be visualized as a rotation in the Bloch-sphere picture. The effect of unitary conjugation is to apply the same operation on a transformed basis. In the actual case, the matrix in Eq. (26) can be rewritten as

$$C_{\theta ,\varphi }=(\theta /2,\varphi ,\psi )\left(\begin{array}{ccc}0& & \\ & 0& \\ & & 1\end{array}\right)^T(\theta /2,\varphi ,\psi ).$$
(29)
The matrix between the two rotations defines a phase damping about the $`z`$ axis. Thus the process is a phase damping about an axis pointing towards the spherical polar angles $`\theta /2,\varphi `$. In fact the rotation $`U_2`$ moves the $`z`$ axis to the direction described by the spherical polar angles $`\theta /2,\varphi `$, so the direction of the phase damping is “half way” between the $`z`$ axis, and its transform by $`U_2`$. Note that the angle $`\psi `$ is irrelevant in Eq. (29), as it does not influence the polar angle of the rotated $`z`$ axis. The phase damping channel has a single direction which is special, thus it is necessarily described by two parameters. In the case if $`\widehat{U}_2`$ is traceless because $`\theta =\pi +2k\pi `$ is satisfied, we obtain a phase damping channel about an axis in the $`xy`$ plane. We can conclude that the controlled-U gate with a traceless $`U_2`$ is capable of simulating a generator of an arbitrary phase damping channel in our scheme.

Returning to the generic GKS matrix in Eq. (25) we find that $`\text{rank}C_{\theta ,\varphi ,\psi }=1`$, thus this general GKS matrix also describes a phase damping channel, physically the same process as in the traceless case. The only difference is that the evolution is now accompanied by a coherent part, generated by the Hamiltonian in Eq. (24).

## V Control via teleportation

In this Section we briefly describe another simulation scheme based on Bennett’s quantum teleportation. It is depicted in Fig. 2

The initial state $`\varrho `$ impinges at the input of a teleportation arrangement. Two additional qubits are prepared in an entangled state

$$|\mathrm{\Psi }_{\text{prog}}=\sqrt{1\epsilon }|B_0+\sqrt{\epsilon }\left(\alpha _1|B_1+\alpha _2|B_2+\alpha _3|B_3\right),$$
(30)
with $`|\alpha _1|^2+|\alpha _2|^2+|\alpha _3|^2=1`$, which serves as the *program state*. We use the notation

$`|B_0={\displaystyle \frac{1}{\sqrt{2}}}\left(|0|1|1|0\right);`$ (31)
$`|B_1={\displaystyle \frac{1}{\sqrt{2}}}\left(|0|0|1|1\right);`$ (32)
$`|B_2={\displaystyle \frac{1}{\sqrt{2}}}\left(|0|0+|1|1\right);`$ (33)
$`|B_3={\displaystyle \frac{1}{\sqrt{2}}}\left(|0|1+|1|0\right).`$ (34)
for the elements of the Bell basis. Then the usual Bennett teleportation is carried out: a Bell state measurement on the two appropriate qubits is carried out, and depending on the result, the appropriate unitary transformation $`\widehat{\sigma }_i`$ (the identity operator or one of the Pauli operators) is carried out.

For $`\epsilon =0`$ we have $`|\mathrm{\Psi }_{\text{prog}}=|B_0`$, the state $`\varrho `$ is simply teleported: the identity operator is implemented. However, for nonzero $`\epsilon `$ we obtain

$$\varrho ^{}=(1\epsilon )\varrho +\epsilon \left(|\alpha _1|^2\widehat{\sigma }_1\varrho \widehat{\sigma }_1+|\alpha _2|^2\widehat{\sigma }_2\varrho \widehat{\sigma }_2+|\alpha _3|^2\widehat{\sigma }_3\varrho \widehat{\sigma }_3\right)$$
(35)
as a “teleported” state. Thus the scheme is essentially equivalent to a random application of the Pauli operators. Setting $`dt=\epsilon `$ as in the previous Section, we can define

$$\widehat{L}\varrho =|\alpha _1|^2\widehat{\sigma }_1\varrho \sigma _1+|\alpha _2|^2\widehat{\sigma }_2\varrho \sigma _2+|\alpha _3|^2\widehat{\sigma }_3\varrho \sigma _3\varrho .$$
(36)
A straightforward calculation shows that the corresponding GKS matrix reads

$$𝒞(\alpha _1,\alpha _2,\alpha _3)=\left(\begin{array}{ccc}|\alpha _1|^2& & \\ & |\alpha _2|^2& \\ & & |\alpha _3|^2\end{array}\right).$$
(37)
We have obtained a GKS matrix of rank 3, describing a generic Pauli channel. In this case we have the parameters of the dynamics encoded into the program state, too.

It is worth noting here that this second scheme is indeed irreversible. However, the same process could be simulated in a similar reversible framework as in Section IV, utilizing two ancillary qubits, and the universal programmable quantum gate array in Ref. .

## VI Summary

We have investigated quantum computational schemes for the simulation of a generator of Markovian dynamics on a qubit, where the value of the infinitesimal time step is encoded in a quantum state at the input of the device. We have described the capabilities of the arrangement if the ancilla to be applied is restricted to a single qubit by characterizing the most general Lindbladian that can be simulated. We have found that under these restrictions, a phase damping about an arbitrary axis can be simulated. We have also investigated a the Bennett quantum teleportation scheme as a possible quantum circuit for performing a similar task.

The inevitable advantage of this method compared with a classical simulation of quantum dynamics is that it works for any, even unknown initial state, which may emerge as an output of another quantum calculation.

The analysis can be carried out for systems ancillas of larger size but in that case, the number of parameters grows, and the problem is less transparent. We remark that for instance, the two-qubit program state enables non-unital dynamics as well.

We believe that the study of simple quantum systems such as those described here facilitates the understanding decoherence in general.

###### Acknowledgements.

This work was supported by the European Union projects QGATES and CONQUEST, by the Slovak Academy of Sciences via the project CE-PI, by the project APVT-99-012304, and by the Research Fund of Hungary (OTKA) under contract No. T034484.