Deep Syntactic Processing by Combining Shallow Methods

We present a novel approach for finding discontinuities that outperforms previously published results on this task. Rather than using a deeper grammar formalism, our system combines a simple unlexicalized PCFG parser with a shallow pre-processor. This pre-processor, which we call a trace tagger, does surprisingly well on detecting where discontinuities can occur without using phase structure information.

Introduction
In this paper, we explore a novel approach for finding long-distance dependencies. In particular, we detect such dependencies, or discontinuities, in a two-step process: (i) a conceptually simple shallow tagger looks for sites of discontinuties as a preprocessing step, before parsing; (ii) the parser then finds the dependent constituent (antecedent).
Clearly, information about long-distance relationships is vital for semantic interpretation. However, such constructions prove to be difficult for stochastic parsers (Collins et al., 1999) and they either avoid tackling the problem (Charniak, 2000;Bod, 2003) or only deal with a subset of the problematic cases (Collins, 1997). Johnson (2002) proposes an algorithm that is able to find long-distance dependencies, as a postprocessing step, after parsing. Although this algorithm fares well, it faces the problem that stochastic parsers not designed to capture non-local dependencies may get confused when parsing a sentence with discontinuities. However, the approach presented here is not susceptible to this shortcoming as it finds discontinuties before parsing.
Overall, we present three primary contributions. First, we extend the mechanism of adding gap variables for nodes dominating a site of discontinuity (Collins, 1997). This approach allows even a context-free parser to reliably recover antecedents, given prior information about where discontinuities occur. Second, we introduce a simple yet novel finite-state tagger that gives exactly this information to the parser. Finally, we show that the combination of the finite-state mechanism, the parser, and our new method for antecedent recovery can competently analyze discontinuities.
The overall organization of the paper is as follows. First, Section 2 sketches the material we use for the experiments in the paper. In Section 3, we propose a modification to a simple PCFG parser that allows it to reliably find antecedents if it knows the sites of long-distance dependencies. Then, in Section 4, we develop a finite-state system that gives the parser exactly that information with fairly high accuracy. We combine the models in Section 5 to recover antecedents. Section 6 discusses related work.

Annotation of empty elements
Different linguistic theories offer various treatments of non-local head-dependent relations (referred to by several other terms such as extraction, discontinuity, movement or long-distance dependencies). The underlying idea, however, is the same: extraction sites are marked in the syntactic structure and this mark is connected (co-indexed) to the control- The experiments reported here rely on a training corpus annotated with non-local dependencies as well as phrase-structure information. We used the Wall Street Journal (WSJ) part of the Penn Treebank (Marcus et al., 1993), where extraction is represented by co-indexing an empty terminal element (henceforth EE) to its antecedent. Without committing ourselves to any syntactic theory, we adopt this representation.
Following the annotation guidelines (Bies et al., 1995), we distinguish seven basic types of EEs: controlled NP-traces (NP), PROs (PRO), traces of A -movement (mostly wh-movement: WH), empty complementizers (COMP), empty units (UNIT), and traces representing pseudo-attachments (shared constituents, discontinuous dependencies, etc.: PSEUDO) and ellipsis (ELLIPSIS). These labels, however, do not identify the EEs uniquely: for instance, the label WH may represent an extracted NP object as well as an adverb moved out of the verb phrase. In order to facilitate antecedent recovery and to disambiguate the EEs, we also annotate them with their parent nodes. Furthermore, to ease straightforward comparison with previous work (Johnson, 2002), a new label CLAUSE is introduced for COMP-SBAR whenever it is followed by a moved clause WH-S. Table 1 summarizes the most frequent types occurring in the development data, Section 0 of the WSJ corpus, and gives an example for each, following Johnson (2002).
For the parsing and antecedent recovery experiments, in the case of WH-traces  controlled NP-traces (NP-NP), we follow the standard technique of marking nodes dominating the empty element up to but not including the parent of the antecedent as defective (missing an argument) with a gap feature (Gazdar et al., 1985;Collins, 1997). 1 Furthermore, to make antecedent co-indexation possible with many types of EEs, we generalize Collins' approach by enriching the annotation of non-terminals with the type of the EE in question (eg. WH-NP) by using different gap+ features (gap+WH-NP; cf. Figure 1). The original nonterminals augmented with gap+ features serve as new non-terminal labels.
In the experiments, Sections 2-21 were used to train the models, Section 0 served as a development set for testing and improving models, whereas we present the results on the standard test set, Section 23.

Parsing with empty elements
The present section explores whether an unlexicalized PCFG parser can handle non-local dependencies: first, is it able to detect EEs and, second, can it find their antecedents? The answer to the first question turns out to be negative: due to efficiency reasons and the inappropriateness of the model, detecting all types of EEs is not feasible within the parser. Antecedents, however, can be reliably recovered provided a parser has perfect knowledge about EEs occurring in the input. This shows that the main bottleneck is detecting the EEs and not finding their antecedents. In the following section, therefore, we explore how we can provide the parser with information about EE sites in the current sentence without relying on phrase structure information.

Method
There are three modifications required to allow a parser to detect EEs and resolve antecedents. First, it should be able to insert empty nodes. Second, it must thread the gap+ variables to the parent node of the antecedent. Knowing this node is not enough, though. Since the Penn Treebank grammar is not binary-branching, the final task is to decide which child of this node is the actual antecedent.
The first two modifications are not difficult conceptually. A bottom-up parser can be easily modified to insert empty elements (c.f. Dienes and Dubey (2003)). Likewise, the changes required to include gap+ categories are not complicated: we simply add the gap+ features to the nonterminal category labels.
The final and perhaps most important concern with developing a gap-threading parser is to ensure it is possible to choose the correct child as the antecedent of an EE. To achieve this task, we employ the algorithm presented in Figure 2. At any node in the tree where the children, all together, have more gap+ features activated than the parent, the algorithm deduces that a gap+ must have an antecedent. It then picks a child as the antecedent and recursively removes the gap+ feature corresponding to its EE from the non-terminal labels. The algorithm has a shortcoming, though: it cannot reliably handle cases when the antecedent does not c-command its EE. This mostly happens with PSEUDOs (pseudo-attachments), where the algorithm gives up and (wrongly) assumes they have no antecedent.
Given the perfect trees of the development set, the antecedent recovery algorithm finds the correct antecedent with 95% accuracy, rising to 98% if PSEUDOs are excluded. Most of the remaining mistakes are caused either by annotation errors, or by binding NP-traces (NP-NP) to adjunct NPs, as opposed to subject NPs.
The parsing experiments are carried out with an unlexicalized PCFG augmented with the antecedent recovery algorithm. We use an unlexicalized model to emphasize the point that even a simple model detects long distance dependencies successfully. The parser uses beam thresholding (Goodman, 1998) to for a tree T , iterate over nodes bottom-up for a node with rule P C 0 as an antecedent pick a k such that k ¥ ¦ j and C k dominates an E E of type e if no such j or k exist, return no antecedent else bind the E E dominated by C k to the antecedent C j Figure 2: The antecedent recovery algorithm. ensure efficient parsing. PCFG probabilities are calculated in the standard way (Charniak, 1993). In order to keep the number of independently tunable parameters low, no smoothing is used. The parser is tested under two different conditions. First, to assess the upper bound an EEdetecting unlexicalized PCFG can achieve, the input of the parser contains the empty elements as separate words (PERFECT). Second, we let the parser introduce the EEs itself (INSERT).

Evaluation
We evaluate on all sentences in the test section of the treebank. As our interest lies in trace detection and antecedent recovery, we adopt the evaluation measures introduced by Johnson (2002). An EE is correctly detected if our model gives it the correct label as well as the correct position (the words before and after it). When evaluating antecedent recovery, the EEs are regarded as four-tuples, consisting of the type of the EE, its location, the type of its antecedent and the location(s) (beginning and end) of the antecedent. An antecedent is correctly recovered if all four values match the gold standard. The precision, recall, and the combined F-score is presented for each experiment. Missed parses are ignored for evaluation purposes.

Results
The main results for the two conditions are summarized in  In the PERFECT case, when the sites of the empty elements are known before parsing, only about 1.6% of the parses are missed and average parsing time goes down to 2 5 seconds per sentence. More importantly, the overall precision and recall of antecedent recovery is 91.4%.

Discussion
The result of the experiment where the parser is to detect long-distance dependencies is negative. The parser misses too many parses, regardless of the beam size. This cannot be due to the lack of smoothing: the model with perfect information about the EE-sites does not run into the same problem. Hence, the edges necessary to construct the required parse are available but, in the INSERT case, the beam search loses them due to unwanted local edges having a higher probability. Doing an exhaustive search might help in principle, but it is infeasible in practice. Clearly, the problem is with the parsing model: an unlexicalized PCFG parser is not able to detect where EEs can occur, hence necessary edges get low probability and are, thus, filtered out.
The most interesting result, though, is the difference in speed and in antecedent recovery accuracy between the parser that inserts traces, and the parser which uses perfect information from the treebank about the sites of EEs. Thus, the question  naturally arises: could EEs be detected before parsing? The benefit would be two-fold: EEs might be found more reliably with a different module, and the parser would be fast and accurate in recovering antecedents. In the next section we show that it is indeed possible to detect EEs without explicit knowledge of phrase structure, using a simple finite-state tagger.

Detecting empty elements
This section shows that EEs can be detected fairly reliably before parsing, i.e. without using phrase structure information. Specifically, we develop a finite-state tagger which inserts EEs at the appropriate sites. It is, however, unable to find the antecedents for the EEs; therefore, in the next section, we combine the tagger with the PCFG parser to recover the antecedents.

Method
Detecting empty elements can be regarded as a simple tagging task: we tag words according to the existence and type of empty elements preceding them. For example, the word Sasha in the sentence Sam said COMP-SBAR Sasha snores.
will get the tag EE=COMP-SBAR, whereas the word Sam is tagged with EE=* expressing the lack of an EE immediately preceding it. If a word is preceded by more than one EE, such as to in the following example, it is tagged with the concatenation of the two EEs, i.e., EE=COMP-WHNP PRO-NP.  Although this approach is closely related to POStagging, there are certain differences which make this task more difficult. Despite the smaller tagset, the data exhibits extreme sparseness: even though more than 50% of the sentences in the Penn Treebank contain some EEs, the actual number of EEs is very small. In Section 0 of the WSJ corpus, out of the 46451 tokens only 3056 are preceded by one or more EEs, that is, approximately 93.5% of the words are tagged with the EE=* tag. The other main difference is the apparently nonlocal nature of the problem, which motivates our choice of a Maximum Entropy (ME) model for the tagging task (Berger et al., 1996). ME allows the flexible combination of different sources of information, i.e., local and long-distance cues characterizing possible sites for EEs. In the ME framework, linguistic cues are represented by (binary-valued) features ( f i ), the relative importance (weight, λ i ) of which is determined by an iterative training algorithm. The weighted linear combination of the features amount to the log-probability of the label (l) given the context (c):

It would have been too late
where Z¨c is a context-dependent normalizing factor to ensure that p¨l © c be a proper probability distribution. We determine weights for the features with a modified version of the Generative Iterative Scaling algorithm (Curran and Clark, 2003).
Templates for local features are similar to the ones employed by Ratnaparkhi (1996) for POS-tagging (Table 3), though as our input already includes POStags, we can make use of part-of-speech information as well. Long-distance features are simple hand-written regular expressions matching possible sites for EEs (Table 4). Features and labels occurring less than 10 times in the training corpus are ignored.
Since our main aim is to show that finding empty elements can be done fairly accurately without using a parser, the input to the tagger is a POS-tagged corpus, containing no syntactic information. The best label-sequence is approximated by a bigram Viterbi-search algorithm, augmented with variable width beam-search.

Results
The results of the EE-detection experiment are summarized in Table 5. The overall unlabeled F-score is 85 3%, whereas the labeled F-score is 79 1%, which amounts to 97 9% word-level tagging accuracy.
For straightforward comparison with Johnson's results, we must conflate the categories PRO-NP and NP-NP. If the trace detector does not need to differentiate between these two categories, a distinction that is indeed important for semantic analysis, the overall labeled F-score increases to 83 0%, which outperforms Johnson's approach by 4%.

Discussion
The success of the trace detector is surprising, especially if compared to Johnson's algorithm which uses the output of a parser. The tagger can reliably detect extraction sites without explicit knowledge of the phrase structure. This shows that, in English, extraction can only occur at well-defined sites, where local cues are generally strong.
Indeed, the strength of the model lies in detecting such sites (empty units, UNIT; NP traces, NP-NP) or where clear-cut long-distance cues exist (WH-S, COMP-SBAR). The accuracy of detecting uncon-EE Prec.
Rec.  trolled PROs (PRO-NP) is rather low, since it is a difficult task to tell them apart from NP traces: they are confused in 10 15% of the cases. Furthermore, the model is unable to capture for. . . to+INF constructions if the noun-phrase is long.

F-score
The precision of detecting long-distance NP extraction (WH-NP) is also high, but recall is lower: in general, the model finds extracted NPs with overt complementizers. Detection of null WHcomplementizers (COMP-WHNP), however, is fairly inaccurate (48 8% F-score), since finding it and the corresponding WH-NP requires information about the transitivity of the verb. The performance of the model is also low (59 5%) in detecting movement sites for extracted WH-adverbs (WH-ADVP) despite the presence of unambiguous cues (where, how, etc. starting the subordinate clause). The difficulty of the task lies in finding the correct verb-phrase as well as the end of the verb-phrase the constituent is extracted from without knowing phrase boundaries.
One important limitation of the shallow approach described here is its inability to find the antecedents of the EEs, which clearly requires knowledge of phrase structure. In the next section, we show that the shallow trace detector and the unlexicalized PCFG parser can be coupled to efficiently and successfully tackle antecedent recovery.

Combining the models
In Section 3, we found that parsing with EEs is only feasible if the parser knows the location of EEs before parsing. In Section 4, we presented a finite-state tagger which detects these sites before parsing takes place. In this section, we validate the two-step approach, by applying the parser to the output of the trace tagger, and comparing the antecedent recovery accuracy to Johnson (2002).

Method
Theoretically, the 'best' way to combine the trace tagger and the parsing algorithm would be to build a unified probabilistic model. However, the nature of the models are quite different: the finite-state model is conditional, taking the words as given. The parsing model, on the other hand, is generative, treating the words as an unlikely event. There is a reasonable basis for building the probability models in different ways. Most of the tags emitted by the EE tagger are just EE=*, which would defeat generative models by making the 'hidden' state uninformative. Conditional parsing algorithms do exist, but they are difficult to train using large corpora (Johnson, 2001). However, we show that it is quite effective if the parser simply treats the output of the tagger as a certainty. Given this combination method, there still are two interesting variations: we may use only the EEs proposed by the tagger (henceforth the NOINSERT model), or we may allow the parser to insert even more EEs (henceforth the INSERT model). In both cases, EEs outputted by the tagger are treated as separate words, as in the PERFECT model of Section 3.

Results
The NOINSERT model did better at antecedent detection (see Table 6) than the INSERT   Comparing our results to Johnson (2002), we find that the NOINSERT model outperforms that of Johnson by 4.6% (see Table 7). The strength of this system lies in its ability to tell unbound PROs and bound NP-NP traces apart.

Discussion
Combining the finite-state tagger with the parser seems to be invaluable for EE detection and antecedent recovery. Paradoxically, taking the combination to the extreme by allowing both the parser and the tagger to insert EEs performed worse. While the INSERT model here did have wider coverage than the parser in Section 3, it seems the real benefit of using the combined approach is to let the simple model reduce the search space of the more complicated parsing model. This search space reduction works because the shallow finitestate method takes information about adjacent words into account, whereas the context-free parser does not, since a phrase boundary might separate them.

Related Work
Excluding Johnson (2002)'s pattern-matching algorithm, most recent work on finding headdependencies with statistical parser has used statistical versions of deep grammar formalisms, such as CCG (Clark et al., 2002) or LFG (Riezler et al., 2002). While these systems should, in theory, be able to handle discontinuities accurately, there has not yet been a study on how these systems handle such phenomena overall.
The tagger presented here is not the first one proposed to recover syntactic information deeper than part-of-speech tags. For example, supertagging (Joshi and Bangalore, 1994) also aims to do more meaningful syntactic pre-processing. Unlike supertagging, our approach only focuses on detecting EEs.
The idea of threading EEs to their antecedents in a stochastic parser was proposed by Collins (1997), following the GPSG tradition (Gazdar et al., 1985). However, we extend it to capture all types of EEs.

Conclusions
This paper has three main contributions. First, we show that gap+ features, encoding necessary information for antecedent recovery, do not incur any substantial computational overhead.
Second, the paper demonstrates that a shallow finite-state model can be successful in detecting sites for discontinuity, a task which is generally understood to require deep syntactic and lexical-semantic knowledge. The results show that, at least in English, local clues for discontinuity are abundant. This opens up the possibility of employing shallow finite-state methods in novel situations to exploit non-apparent local information.
Our final contribution, but the one we wish to emphasize the most, is that the combination of two orthogonal shallow models can be successful at solving tasks which are well beyond their individual power. The accent here is on orthogonality -the two models take different sources of information into account. The tagger makes good use of adjacency at the word level, but is unable to handle deeper recursive structures. A context-free grammar is better at finding vertical phrase structure, but cannot exploit linear information when words are separated by phrase boundaries. As a consequence, the finitestate method helps the parser by efficiently and reliably pruning the search-space of the more complicated PCFG model. The benefits are immediate: the parser is not only faster but more accurate in recovering antecedents. The real power of the finite-state model is that it uses information the parser cannot.


extfieldsofstudy:
Computer Science
Medicine
Physics
Biology

text:
Hierarchy Measures in Complex Networks

Using each node's degree as a proxy for its importance, the topological hierarchy of a complex network is introduced and quantified. We propose a simple dynamical process used to construct networks which are either maximally or minimally hierarchical. Comparison with these extremal cases as well as with random scale-free networks allows us to better understand hierarchical versus modular features in several real-life complex networks. For random scale-free topologies the extent of topological hierarchy is shown to smoothly decline with $\gamma$ -- the exponent of a degree distribution -- reaching its highest possible value for $\gamma \leq 2$ and quickly approaching zero for $\gamma>3$.

Using each node's degree as a proxy for its importance, the topological hierarchy of a complex network is introduced and quantified. We propose a simple dynamical process used to construct networks which are either maximally or minimally hierarchical. Comparison with these extremal cases as well as with random scale-free networks allows us to better understand hierarchical versus modular features in several real-life complex networks. For random scale-free topologies the extent of topological hierarchy is shown to smoothly decline with γ -the exponent of a degree distribution -reaching its highest possible value for γ ≤ 2 and quickly approaching zero for γ > 3. Networks recently came to the focus of attention of the complex systems research. Indeed, most complex systems have an underlying network serving as a "backbone" for its dynamical processes. The large-scale topological organization of a particular complex network is related to both its functional role and historical background. Thus it is important to develop quantitative tools allowing one to detect and measure significant features in the topology of a given network. The hierarchical organization is a common feature of many complex systems. As an example of a hierarchy one might think of the organizational structure of a large company. The defining feature of a hierarchical organization is the existence of a hierarchical path connecting any two of its nodes. It can be thought of as a trajectory of a request initiated at one of the nodes and reaching its destination node through the "chain of command". Such a request first goes up the steps of the hierarchy until it reaches the first common boss of its sender and recipient after which it descend the hierarchical levels down to the destination node. In most real-life complex systems the simple tree-like hierarchical network may be augmented by "shortcuts" bypassing the chain of command. Such non-hierarchical shortcuts make the task of detecting the hierarchical structure much more non-trivial. The question we want to address in this work is how to detect and measure the extent of the hierarchy manifested in the topology of a given complex network.
Real world networks often have very broad degree distribution [1] and thus the degree in itself gives a sensible characteristic of a node which has to be preserved in any randomized version of a network [2,3]. In fact, in a number of systems nodes with higher degrees are on average more important than their lower degree counterparts. For example, for the Internet the number of hardwired connections a given Autonomous System serves as a proxy of its importance with the most connected nodes being global Internet Service Providers. For WWW the in-degree of a web page can serve as a measure of its popularity and hence importance; highly connected hubairports of airline networks typically located in large cities, etc. In what follows we use the degree of a node as a proxy for its rank in the hierarchy based on the relative importance of nodes. Thus we propose a way to couple a local topological quantity, the degree, to a global structure, hierarchy: Thereby we define and quantify topological hierarchy as a way to characterize networks beyond their degree distribution and its two point correlation function [3,4,12]. However, we would like to point out that our methods could be generalized to hierarchies defined in terms of any other characteristic of individual nodes, being it wealth, mass, or some other appropriate quantity.
We quantify the hierarchical topology of a network using the concept of a hierarchical path [5,6]: a path between two nodes in a network is called hierarchical if it consists of an "up path" -where one is allowed to step from node i to node j only if their degrees k i , k j satisfy k i ≤ k j followed by a "down path" -where only steps to nodes of lower or equal degree are allowed. Either up or down path is allowed to have zero length. This definition of a hierarchical path follows the above mentioned trajectory of a request which is first forwarded up and then descends down the levels of a hierarchy quantified by k i . It is also similar to the definition proposed in [5] and [6]. The length of the shortest hierarchical path between a given pair of nodes can be either: 1) equal to the length of the shortest path between these nodes; 2) longer than it; 3) not exist at all if these two nodes cannot be connected by any hierarchical path. The fraction of pairs in each of these three categories is denoted as F , S, and U = 1 − F − S correspondingly. Equivalently, the hierarchical fraction F can be viewed as a fraction of shortest paths in the network that are hierarchical, while S as the probability of finding a non-hierarchical shortcut -a path shorter than the shortest hierarchical path between a pair of nodes.
We analyzed in detail the hierarchical structure of several real-life complex networks: 1) The Internet consisting of autonomous systems (AS) hardwired to each other [7] (6474 nodes, 1572 edges); 2) The largest connected component of the yeast protein interaction network [8] (2839 nodes, 4220 edges); 3) The largest connected component of the E-mail mutual correspondence network (25151 nodes, 19963 edges) [9]; 4) The network of CEOs (executive company directors); two directors are connected if they both belong to at least one common board of directors (6193 nodes, 43077 edges) [10]. To have a reference point, we compare these networks with their random connected counterparts in which the degree of every individual node is strictly preserved. In practice this is done by multiple edge-rewiring moves [3,4] where two links between two randomly selected pairs of nodes are rewired with the constraint that one only accepts moves in which no double links are created, and where the network remains connected. We find that the randomized version of the Internet, characterized by F r = 0.99, is almost as hierarchical as the real Internet, where F = 0.95. The same is true for the E-mail network (F r = 0.98 vs F = 0.97) and the CEO network (F r = 0.84 vs F = 0.78). On the other hand, the randomized protein interaction network, F r = 0.88, is significantly more hierarchical than the real one, F = 0.33. This anti-hierarchical feature of the protein interaction network reflects a topology where highly connected nodes are placed on the periphery, and not in the center of the network [3].
We also found that a small reduction in F for the Internet compared to its randomized counterpart is mainly due to an increase in the number of non-hierarchical shortcuts, S = 0.02 (S r =0). This feature is even more pronounced for the yeast protein network, with S = 0.17 (S r = 0.02). One of the possible explanation for this phenomena can be the natural tendency toward shorter distances and thus toward faster and more specific signaling.
As was shown above, a random network with a given degree distribution provides a useful benchmark for the extent of hierarchy in real-life complex networks. It is interesting also to consider the extreme cases: that is to construct networks that are the most or alternatively the least hierarchical for a given degree distribution. This is important for positioning real networks not only with the respect to its random counterpart, but also with respect to the extreme limits the network of a given degree distribution can achieve.
Similar to a randomized version, the maximally hierarchal version of a network is generated by multiple rewirings of pairs of edges. One has to add however a particular preference for reconnection: At each step one selects two pairs of connected nodes and attempts to connect the node with the highest among these four nodes to the node of the next highest degree in this subset. The remaining two nodes are then linked together (multiple links are forbidden, and the network should always remain connected).
The maximally anti-hierarchal version of a network can be constructed by the same algorithm but with the opposite preference of reconnection: the node with the highest degree is linked with that with the lowest degree. In Figs. 1a,c we show the maximally hierarchical respectfully anti-hierarchical networks with the same node degree distribution as a random network, shown in Fig. 1b. We have found that applying the above algorithm to all four empirical networks it is possible to achieve the limits where F =1 for maximal hierarchy and F ≈ 0 for maximal anti-hierarchy.
As one can see from Fig. 1, the maximally hierarchical or anti-hierarchical networks show strong correlations between degrees of connected nodes [11] that can be quantified through either the correlation profile [3] or the assortativity measure, r introduced in Ref. [12]. We consider a modified assortativity measure, similar to the one used in Ref. [12], but here defined as r AD = ln( kikj kikj r ), where k i k j is the average over all pairs i and j of nearestneighbor nodes in the network and k i k j r is the average of k i k j in an ensemble of randomized networks generated as described above [3,4]. We find the maximally hierarchical topology to be always assortative (r AD > 0), while the maximal anti-hierarchical topology -disassortative (r AD < 0). For example, for a network with the node degree distribution f (k) ∝ 1/k 2.5 , r AD = 0.14 and −1.24 for the maximal hierarchy and the anti-hierarchy respectively. For comparison,the protein-protein interactions in yeast, which are well described by f (k) ∝ 1/k 2.5 , has r AD = −0.82. We further stress that assortativity and hierarchical topology are in general not prerequisites for each other.
Motivated by the abundance of real-life networks characterized by a broad, often scale-free, degree distribution (as it is the case for the empirical networks we are considering here), we quantified the hierarchical fraction F as a function of the exponent γ in random scale-free networks with a power law degree distribution f (k) ∝ 1/k γ . Such networks were constructed by first generating a set of  FIG. 2: a) The fraction of shortest paths that are also hierarchical, F and b) The fraction of non-hierarchical shortcuts, S, as a function of γ for three system sizes, N = 300, 1000, 3000. The shadowed area in a) corresponds to error estimates for a network of size N = 3000.
power-law distributed degrees of individual nodes, then linking the edges to create a single-component network, and finally randomizing the resulting network using the algorithm of Ref. [4], which preserves individual degrees and connectedness of the network. Fig. 2a shows F vs γ measured in random scale-free networks for different system sizes. The decrease from F = 1 to F ∼ 0 happens as γ grows from 2 to 3 with a smooth transition around γ ∼ 2.6 that weakly depends on the system size. We remark that for γ ≤ 2, F = 1 and is nearly independent on the upper cutoff of the degree distribution, which is required in this case. Fig. 2b shows S vs γ in random scale-free networks. One can see that S → 0 as γ → 2 and 3. Indeed, as γ → 2 the largest hubs become dominant and the typical distance in a network approaches 2 (almost any pair of nodes are connected via at least one hub). This makes most shortest paths via a hub to be hierarchical. In the limit γ → 3, the topology of the network is very close to a tree, which in its turn implies that the number of alternative paths approaches zero, and thus again S → 0.
We have seen that as γ approaches 2 almost all pairs of nodes tend to have at least one hierarchical paths connecting them ( F → 1 and hence U == 1 − F − S → 0). The existence of hierarchical paths connecting most pairs of nodes means that at the very least the majority of nodes have at least one neighbor with a degree higher then their own.
Let us first calculate the probability that a given edge is attached to a node with degree larger than k Here for γ < 2 one can only have a scale-free distributions below an upper cutoff K. Thus in the absence of degreedegree correlations the probability that a node of degree k has at least one neighbor of degree higher than itself is given by The probability P (k neighbor ≥ k) for a node of degree k to have a neighbor of degree k neighbor > k in an infinitely large scale free network, that is not necessarily connected, as function of a) -exponent γ and b) -degree of the node k for γ = 2.5, 3 and 4.
In Figure 3 we plot this probability of having a boss (neighbor with a higher degree) as a function of γ for three different values of the degree k, Fig. 3a, and as a function of k for different values of γ, Fig. 3b. For γ ≤ 2 both low and high degree nodes always have a higher connected neighbor and for γ > 3 the high k nodes nearly never have a boss. For 2 < γ < 3, low connected nodes often have no higher connected neighbors (see Fig. 3b), but as P (k neighbor > k) → 1 for increasing k there is a hierarchical core of highly connected nodes. In popular terms, at these intermediate values of γ many low degree nodes escape the hierarchy, while medium and highly connected nodes have bosses. Above γ = 3, P (k neighbor > k) decreases to zero with degree. Thus for these high values of γ a network becomes modular with each of the modules centered around a local hub. Figure 4a shows the possible values of F for hierarchies and anti-hierarchies for γ ∈ (2, 3). One can see that even the networks of narrow degree distribution can be organized hierarchically (see upper limit for F for γ = 3) as well as networks of broad degree could be rearranged to suppress "self-hierarchical" features (see lower limit for F for γ = 2).
In Figure 4a we summarize the results of our study of real and random scale-free networks by displaying the hierarchical fraction F observed in real world networks (black dots) relative to its value for the random scale-free networks with the corresponding value of γ (solid line). As discussed above the Internet, e-mail and CEO networks are about as hierarchical as their random scale-free counterparts, while that of protein-protein interactions in yeast is significantly anti-hierarchical. Dark shaded regions in this figure correspond to the range between maximally hierarchical and respectively anti-hierarchical networks for a given value of γ.
Another interesting aspect is the impact the hierarchical structure has on the overall robustness of the network. In Figure 4b we show the average size of the largest  FIG. 4: a) Possible hierarchical organizations of networks, dark-shadowed area shows the limits for the average values, and light-shadowed area are the corresponding limits including possible variations from sample to sample in a random scale-free network with N = 10 3 nodes. The black dots show values of the hierarchical fraction F and the degree exponent γ for the Internet, E-mail, Yeast Protein Interaction and CEO networks discussed in the text. The solid line follows F vs γ in random scale-free networks. b) The results of the robustness analysis for maximally hierarchical (H), random (R) and anti-hierarchical (AH) scale-free networks with γ = 2.5. The effect of the intentional attack by deletion of the single most connecting node or edge in the network is reflected in the reduced size SLC of the largest connected component after such an attack. The probability P break for a network to break up following the removal of a randomly selected node or edge shows how sensitive it is to a random, non-intentional failure.
connected component S LC of the scale-free network with γ = 2.5 and N = 1000 after the intentional attack, consisting of choosing and removing a single edge (left column) or node (right column) in such a way as to minimize the S LC in the resulting network. The smaller is the average S LC the more vulnerable is the network with respect to attacks. To characterize the robustness of a network with respect to random failures we specify the likelihood P break that a removal of the single node/edge disconnects the network. We find that anti-hierarchical topologies are most vulnerable with respect to attacks on their edges while hierarchical topologies are sensitive to node attacks. Apart from that, hierarchies are most vulnerable to random failures.
In summary, we have discussed hierarchical organization manifested in topology of complex networks, and demonstrated how it can be used to characterize possible network architectures beyond the degree distribution of their nodes. We quantified the hierarchal structure as the fraction of shortest paths that are also hierarchical. It was found that this quantity approaches its max-imum value for marginally divergent scale-free networks γ ≤ 2. It was also shown that anti-hierarchy is naturally related to modular features of networks. Finally we found that hierarchal as well as anti-hierarchical network topologies have implications for signaling and robustness against various types of attacks and malfunctions, with anti-hierarchies being quite reliable against the most types of perturbations.


On Dequantization of Fedosov's Deformation Quantization

To each natural deformation quantization on a Poisson manifold M we associate a Poisson morphism from the formal neighborhood of the zero section of the cotangent bundle to M to the formal neighborhood of the diagonal of the product M x M~, where M~ is a copy of M with the opposite Poisson structure. We call it dequantization of the natural deformation quantization. Then we"dequantize"Fedosov's quantization.

Introduction
Quantization relates to geometric structures of classical mechanics their algebraic quantum counterparts. However, between the classical and quantum worlds there is a world of "semiclassical" objects that are still of geometric nature but which inherit certain properties of quantum structures. There is a large and important class of such semiclassical objects, symplectic groupoids, introduced independently by Karasëv [17], Weinstein [22], and Zakrzewski [24]. Symplectic groupoids were extensively studied as geometric objects (see [6] and references therein). In [5] Cattaneo and Felder constructed a symplectic groupoid based on the Poisson sigma model whose perturbative quantization yields the Kontsevich star-product (see [4]). In what follows we associate to each natural star-product (see the definition in Section 2) on a Poisson manifold M a formal geometric object, (T * M, Z), the formal neighborhood of the zero section Z of the cotangent bundle T * M endowed with the "source" and "target" mappings to M which are a Poisson and anti-Poisson morphisms respectively (we give the necessary terminology related to the formal neighborhoods in the Appendix). This object can be thought of as a "formal symplectic groupoid" at least if M is symplectic. We call it "dequantization" of the initial starproduct. The goal of this paper is to calculate the source and target mappings associated to a Fedosov star-product. These mappings can be described independently in terms of the (formal) geometric structure of Fedosov's quantization revealed by Emmrich and Weinstein in [10].
Acknowledgments. We are very grateful to Hovhannes Khudaverdian, Simon Lyakhovich, and Boris Tsygan for stimulating discussions and to Abilene Christian University for supporting our research.

Natural Deformation Quantizations
Let (M, {·, ·}) be a Poisson manifold. Denote by C ∞ (M) [[ν]] the space of formal series in ν with coefficients from C ∞ (M). As introduced in [1], a formal differentiable deformation quantization on M is an associative algebra structure on C ∞ (M) [[ν]] with the ν-linear and νadically continuous product * (named star-product) given on f, g ∈ C ∞ (M) by the formula where C r , r ≥ 0, are bidifferential operators on M, C 0 (f, g) = f g and C 1 (f, g) − C 1 (g, f ) = i{f, g}. We adopt the convention that the unit of a star-product is the unit constant. Two differentiable star-products ], * ′ ) of the form B = 1 + νB 1 + ν 2 B 2 + . . . , where B r , r ≥ 1, are differential operators on M. The existence and classification problem for deformation quantization was first solved in the non-degenerate (symplectic) case (see [7], [21], [11] for existence proofs and [12], [19], [8], [2], [23] for classification) and then Kontsevich [18] showed that every Poisson manifold admits a deformation quantization and that the equivalence classes of deformation quantizations can be parameterized by the formal deformations of the Poisson structure. It turns out that all the explicit constructions of star-products enjoy the following property: for all r ≥ 0 the bidifferential operator C r in (1) is of order not greater than r in both arguments (the most important examples are Fedosov star-products on symplectic manifolds and the Kontsevich star-product on R n endowed with an arbitrary Poisson bracket). The star-products with this property were called natural by Gutt and Rawnsley in [14], where general properties of such star-products were studied (before these star-products were said to be of Vey type).
Remark. In this Letter the word "formal" is used very often in different contexts. In order to avoid unnecessary confusion, from now on we will call the objects that are formal series in the formal parameter ν ν-formal.

Dequantization of a natural deformation quantization
Let D = D(M) denote the algebra of differential operators with smooth complex-valued coefficients on a real manifold M. It has a natural filtration with respect to the order of differential operators, 0 ⊂ D 1 ⊂ D 2 ⊂ . . . . The symbol mapping Symb r : D r → C ∞ (T * M) maps the operators of order not greater than r to the functions on T * M that are homogeneous polynomials of degree r on the fibres. The kernel of Symb r is D r−1 . If {x k , ξ l } are local coordinates on T * M (as usual, {ξ l } are fibre coordinates dual to the base coordinates {x k }) and an operator X ∈ D r has the leading term X J ∂ J where J runs over the multi-indices of order r and ∂ k = ∂/∂x k , then Symb r (X) = X J ξ J . Denote by {·, ·} T * M the natural Poisson bracket on T * M . In local coordinates For two arbitrary differential operators X ∈ D k and Y ∈ D l it is well known that XY ∈ D k+l , [X, Y ] ∈ D k+l−1 and For each point x ∈ M denote by D x the space of all distributions supported at x. It is known that D x consists of the linear combinations of partial derivatives of the Dirac distribution δ x . The space D x has also a natural filtration 0 ⊂ D x 0 ⊂ D x 1 ⊂ . . . with respect to the order of distributions. The symbol mapping Symb r : D x r → C[ξ] maps the distributions of order not greater than r to homogeneous polynomials on T * x M of degree r. Consider the mapping A → A x which maps an operator A to the distribution A x such that (A x , φ) = (Aφ)(x), where φ is a test function. This mapping maps D r onto D x r . Moreover, the symbol of A x is the restriction of the symbol of A to the fibre T * x M, Symb r (A x )(ξ) = Symb r (A)(x, ξ). Thus the symbol of A is completely determined by the symbols of all A x .
It follows from (2) that for A, B ∈ N Thus the mapping σ : A → σ(A) is a homomorphism from the algebra N to the algebra C ∞ (T * M , Z). Notice that the kernel of the mapping σ is νN . It follows from (3) that for two natural ν-formal differential operators A, B ∈ N the ν-formal differential operator (1/iν)[A, B] is natural and ] denote by L f and R g the operators of left * -multiplication by f and of right * -multiplication by g respectively, so that L f g = f * g = R g . The associativity of * is equivalent to the fact that [L f , R g ] = 0.
A star-product * on M is natural iff for any f, g ∈ C ∞ (M) [[ν]] the operators L f , R g are natural. For a given natural star-product * we introduce the following mappings S, T : Since the kernel of σ is νN , then for f = f 0 + νf 1 + . . . we have that Sf = Sf 0 and T f = T f 0 . Now we will show that the mapping S : (4): Similarly, the mapping T : where M is a copy of the manifold M endowed with the opposite Poisson bracket −{·, ·}. Since for any f, g ∈ C ∞ (M) the operators L f and R g commute, we have from (5) that Thus we can combine the mappings S and T into a single Poisson morphism S⊗T : .
The operator C 1 of a natural star-product * can be written for f, g ∈ C ∞ (M) as . Since both S and T are homomorphisms with respect to the point-wise products in C ∞ (M) and C ∞ (T * M , Z), we observe that for f ∈ C ∞ (M) the formal series in ξ, Sf and T f , can be written as Sf = f (s) and T f = f (t), where f (s) and f (t) are the compositions of the Taylor expansion of f at x = (x 1 , . . . , x n ) (treated as a formal series) with the formal series s = (s 1 , . . . , s n ) and t = (t 1 , . . . , t n ), respectively. The Poisson mapping S⊗T is induced by the formal mapping s×t : (x, ξ) → (s(x, ξ), t(x, ξ)). Notice that t k − s k = 1 2 ω kl ξ l (mod ξ 2 ). Therefore (see the Appendix) if M is symplectic then the mapping s × t is a formal symplectic diffeomorphism of (T * M , Z) onto (M × M , M diag ) such that its restriction to the zero section Z is the identity morphism onto the diagonal M diag (both Z and M diag are copies of M). Since M diag is a Lagrangian manifold in M × M , it is well known that there exists a symplectic diffeomorphism of a tubular neighborhood of M diag to a tubular neighborhood of Z in T * M which is the identity morphism from

Fedosov Star Products
Fedosov's construction of star-products can be trivially generalized to the following setting (see [3], [9], [16], [20]). Let Λ jk be a global tensor field on a symplectic manifold (M, ω) such that ω jk = (1/2)(Λ jk − Λ kj ) is the nondegenerate Poisson tensor on M inverse to the symplectic form ω. Assume that ∇ is an affine connection (possibly with torsion) which respects Λ jk , i.e. ∇Λ jk = 0. For each x ∈ M we associate to the tangent space T x M a formal associative algebra W x whose elements are formal series where {y k } are linear coordinates on T x M, α is a multi-index, and the standard multi-index notation is used. The product in W x is given by the formula Taking the union of algebras W x we obtain a bundle W of algebras. The fibre product (7) is extended to the sections of the bundle W ⊗ Λ of W -valued differential forms on M by means of the usual exterior product of differential forms. Introduce the gradings deg ν , deg a , deg s on the sections of W ⊗ Λ by defining it on the generators as follows: All other gradings of the generators are set to zero. The product • on the sections of W ⊗ Λ is bigraded with respect to the total grading Deg = 2 deg ν + deg s and the grading deg a . The connection ∇ is extended to the sections of W as follows: where Γ l jk are the Christoffel symbols of ∇. Introduce the Fedosov operators δ and δ −1 on the sections of W ⊗ Λ. Assume that a section a ∈ Γ(W ⊗ Λ) is homogeneous w.r.t. all the gradings introduced above with deg s a = p and deg a a = q. Set Define the elements T := 1 2 ω sα T α kl y s dx k ∧ dx l and R := is the curvature of the connection ∇.
The following two theorems are minor modifications of the standard statements of Fedosov's theory adapted to the case of affine connections with torsion. We shall denote the Deg-homogeneous component of degree k of an element a ∈ Γ(W ⊗ Λ) by a (k) and its deg s -homogeneous component of degree l by a l .
The Fedosov connection D is a deg a -graded derivation of the algebra Γ(W ⊗ Λ). Therefore Fedosov's algebra W D := ker D ∩ Γ(W ) is a subalgebra of (Γ(W ), •). can be calculated recursively w.r.t. the total degree Deg as follows: is a star-product on M.
is a differential operator of order k − l.

Formal geometric version of Fedosov's construction
In this section we describe the formal geometric structure obtained from Fedosov's quantization by "setting ν to zero". This structure was discovered in [10] and later used in [13] as the first step of the BRST quantization procedure that yields Fedosov's quantization (conversion of the second class constraints to the first class constraints).
For a section w = w(x, ν, y) ∈ Γ(W ) denote by w ∨ = w| ν=0 the ν-free part of w. Denote by W ∨ the ν-free part of the bundle W . Each fibre ] is an algebra with respect to the pointwise product. The smooth sections of W ∨ can be canonically identified with the elements of C ∞ (T M, Z) (abusing notations we denote by Z also the zero section of T M). For two sections a, b ∈ Γ(W ) we have from (1) and (7): Proof. Since the mapping In local coordinates on M set κ k = τ (x k ) ∨ . It follows from Proposition 1 that the mapping C ∞ (M) ∋ f → τ (f ) ∨ is induced by the dual (formal) Poisson morphism κ : (x, y) → κ(x, y) from (T M, Z) to M, that is τ (f ) ∨ (x, y) = f (κ(x, y)) (which is understood as above as a composition of formal series).
The following theorem is the ν-free version of Theorem 1. It provides an independent way of calculating r ∨ and introduces a "ν-free Fedosov connection" D ∨ on W ∨ . Denote by Ξ a the formal Hamiltonian vector field on T M corresponding to a section a of W ∨ with respect to the fibrewise Poisson bracket (10).
Equation (11) is obtained from (8) with the use of (9) and an obvious identity r • r = 1 2 [r, r] • . Notice that r ∨ depends only on the ν-free part ω of the Abelian curvature ω + Ω of Fedosov's quantization.
Theorem 5. For f ∈ C ∞ (M) the element τ (f ) ∨ can be calculated recursively w.r.t. the symmetric degree deg s as follows: Since the mapping τ : f → τ (f ) from C ∞ (M) [[ν]] to Γ(W ) is given by a ν-formal ν-linear differential operator, the value of τ (f ) at a given arbitrary point x ∈ M is determined only by the ν-formal ∞-jet of f at x. In [23] it was proved that the mapping τ is actually a bijection of the space of ν-formal ∞-jets of functions at x onto the fibre W x . Below we will prove a "formal geometric" version of this statement which is equivalent to the statement itself.

Proposition 2. For an arbitrary point
x establishes a bijection between the space of ∞-jets of functions at x and W ∨ x . Proof. The statement of the proposition is equivalent to the statement that the restriction of the dual (formal) mapping κ : (T M, Z) → M to the fibre W ∨ x is a formal diffeomorphism between (W ∨ x , 0) and (M, x). The latter statement follows from the fact that κ k = x k + y k (mod y 2 ) which can be obtained from Theorem 5.

Dequantization of a Fedosov star-product
Introduce a bilinear pairing ·, · on the bundle W as follows: for For a section w ∈ Γ(W ) introduce ν-formal differential operators and τ (f ) l−2m = m. It follows from (7) that this contribution is nonzero only if j − 2k = l − 2m. Then it equals (12) ν where J and K are multi-indices. The deg ν -grading of term (12) is is natural and depends only on the value w(x), therefore its σ-symbol depends only on w ∨ (x). Thus (Sf )( Fix an arbitrary coordinate neighborhood (U, {x k }) on M. As usual, {y k } are the corresponding fibre coordinates on T U. Introduce a νformal differential operator Z p on U by the formula For w = y p we get from (7) and (13) that Since ω pq = 1 2 (Λ pq − Λ qp ) we get from (14) and (15) that L[y p ]−R[y p ] = ω pq Z q and therefore Z q = ω qp (L[y p ] − R[y p ]), where (ω qp ) is inverse to (ω pq ). It follows from Proposition 3 that Z p is a natural operator. We denote by ζ p = ζ p (x, ξ) ∈ C ∞ (U) [[ξ]] the σ-symbol of Z p , ζ p = σ(Z p ). Since for f ∈ C ∞ (U) the expansion of τ (f ) into Deg-homogeneous components is of the form τ (f ) = f (x) + ∂f ∂x k y k + . . . , we obtain that Z p = iν ∂ ∂x p (mod ν 2 ), whence ζ p = ξ p (mod ξ 2 ). The following proposition is a direct consequence of Proposition 4 and formulas (14) and (15).
where s k = s k (x, ζ), t l = t l (x, ζ) and ξ p = ξ p (x, ζ) is given by Theorem 6. The check is based on the formula ∂κ p (x, y) ∂y k ω pq (κ(x, y)) ∂κ q (x, y) ∂y l = ω kl (x), which can be derived from the fact that the mapping (x, y) → κ(x, y) is a Poisson morphism from (T M, Z) to M.

Appendix
In the Appendix we briefly introduce terminology related to formal neighborhoods and their morphisms.
Let X be an N-dimensional real manifold and Y its n-dimensional submanifold. Denote by I the ideal in the algebra C ∞ (X) of functions vanishing on Y . Denote I ∞ = ∞ k=1 I k . The algebra of jets C ∞ (X)/I ∞ can be thought of as "the algebra of smooth functions on the formal neighborhood of Y in X". We use the notation C ∞ (X, Y ) := C ∞ (X)/I ∞ . Locally this algebra is modelled as follows. Let (U, {x k }) be a coordinate neighborhood in X such that U ∩ Y is given by the equations x n+1 = 0, . . . , x N = 0. Then C ∞ (U, U ∩ Y ) is isomorphic to the algebra of formal series C ∞ (U ∩ Y )[[x n+1 , . . . , x N ]]. If f ∈ C ∞ (U) is a representative of an element in C ∞ (U, U ∩ Y ), the corresponding formal series in C ∞ (U ∩ Y )[[x n+1 , . . . , x N ]] is the Taylor expansion of f (x) at the points of U ∩ Y with respect to the (formal) parameters x n+1 , . . . , x N .
If E is a vector bundle with the zero section Z, the algebra C ∞ (E, Z) can be naturally identified with the formal series of the form φ 0 + φ 1 + . . . , where φ r ∈ C ∞ (E) is a homogeneous polynomial of degree r on each fibre.
A local model for a formal neighborhood of the diagonal in the Cartesian square of an n-dimensional manifold M, C ∞ (M × M, M diag ), can be obtained by taking two copies of coordinates {s k } and {t k } on a neighborhood U ⊂ M so that the diagonal (U × U) ∩ M diag is given by the equations t k − s k = 0. Then we can use the coordinates {s 1 , . . . , s n , t 1 − s 1 , . . . , t n − s n } to model locally C ∞ (M × M, M diag ) as above.
A morphism Ψ : C ∞ (X, P ) → C ∞ (Y, Q) can be described locally as follows. Let U ⊂ X and V ⊂ Y be two coordinate neighborhoods with the coordinates (x, η) and (y, θ) respectively, where U ∩ P is defined by the equations η = 0 and V ∩ Q is defined by θ = 0. Suppose that x k = x k (y, θ) and η l = η l (y, θ) are formal series in θ with coefficients in C ∞ (V ∩ Q) such that η = 0 (mod θ). These data define a morphism f (x(y, θ), η(y, θ)) and subsequent Taylor expansion with respect to the formal parameters θ. We can think of Ψ as of a mapping induced by the mapping ψ : (y, θ) → (x(y, θ), η(y, θ)). Let x k (y, θ) = φ k (y) (mod θ) and η m (y, θ) = χ m n (y)θ n (mod θ 2 ). The mapping ψ is invertible if φ : V ∩Q → U ∩P is a diffeomorphism and the matrix (χ m n ) is invertible.


extfieldsofstudy:
Physics
Computer Science
Medicine

text:
Description of a quantum convolutional code

We describe a quantum error correction scheme aimed at protecting a flow of quantum information over long distance communication. It is largely inspired by the theory of classical convolutional codes which are used in similar circumstances in classical communication. The particular example shown here uses the stabilizer formalism, which provides an explicit encoding circuit. An associated error estimation algorithm is given explicitly and shown to provide the most likely error over any memoryless quantum channel, while its complexity grows only linearly with the number of encoded qubits.

We describe a quantum error correction scheme aimed at protecting a flow of quantum information over long distance communication. It is largely inspired by the theory of classical convolutional codes which are used in similar circumstances in classical communication. The particular example shown here uses the stabilizer formalism, which provides an explicit encoding circuit. An associated error estimation algorithm is given explicitly and shown to provide the most likely error over any memoryless quantum channel, while its complexity grows only linearly with the number of encoded qubits. In recent years, the discovery and development of quantum computation and communication has shed new light on quantum physics. The potential applications of these new fields encompass a wide variety of subjects, ranging from unconditionally secure secret key generation protocols [1] to efficient integer factoring algorithms [2] or enhancement of communication complexity [3]. However, the practical realization of such protocols and algorithms remains a very involved task mainly because of the inherent instability of quantum superpositions [4] as well as intrinsic imprecisions of the physical devices that process quantum information. These errors wipe out the quantum superpositions together with entanglement, which are usually seen as key resources of the power of quantum algorithms and protocols [5]. Hence, protecting the quantum nature of information became one of the most important challenges to prove the feasibility of quantum computers. The discovery of quantum error correction schemes [6,7] notably opened the future of large scale quantum information processing: a certain, but unfortunately very small, degree of imprecision can be tolerated at each step of a quantum transformation and still allow a speed-up over classical information processing [8,9]. However, building a fault-tolerant quantum computer remains largely out of reach of the present day practical realizations, principally because of the large number of physical qubits required to account for the error correction.
On the other hand, quantum cryptography and more generally the field of quantum communication seems more promising in a near future. Some quantum key distribution protocols have been implemented and the associated devices seem to be close to commercialization [10]. Within this context, we construct a new family of codes -quantum convolutional codes -aimed at protecting a stream of quantum information in a long distance communication. They are the correct generalization to the quantum domain of their classical analogues, and hence inherit their most important properties. First, they have a maximum likelihood error estimation algorithm for all memoryless channels with a complexity growing linearly with the number of encoded qubits. This is an impor-tant issue since finding the most likely error -a strategy which allows to determine the most likely sent codeword -is in general a hard task: for a generic family of block codes with constant rate, the maximum likelihood error estimation algorithm has a complexity growing exponentially with the number of encoded qubits. Hence, generic block codes rapidly require to employ suboptimal error estimation procedures which, as a consequence, do not exploit the whole error correcting capabilities of the code. Moreover, our algorithm can easily handle variations in the properties of the communication channel (i.e. a change in the single qubit error probabilities). The second advantage of quantum convolutional codes is their ability to perform the encoding of the qubits online (i.e. as they arrive in the encoder). Thus, it is not necessary to wait for all the qubits to be ready to start sending the encoded state through the communication channel: it reduces the overall processing time of the qubits which is an additional source of decoherence. Note that an attempt at defining quantum convolutional codes has been made some time ago [11,12], but missed some crucial points concerning the error estimation algorithm as well as error propagation properties.
In this letter, we deal with a specific example drawn from our general theory. We construct a quantum convolutional code achieving a rate equal to 1/5: we explain how to encode and decode a stream of qubits efficiently, and we expose the maximum likelihood error estimation algorithm. This will give all the necessary intuition to understand how to generalize the present results to a wider framework [13].
Description of the code -The particular code we wish to present is best described by using the stabilizer formalism [14]. This provides a simple way to understand the encoding and decoding operations. Moreover, the error syndromes can be easily identified, which considerably simplifies the description of the error estimation algorithm. We use the following standard notations for the Pauli operators acting on a single qubit: so that ZX = Y . The identity matrix will be denoted by I. Since convolutional codes are designed to deal with a stream of information qubits, the number of generators of the stabilizer group will possibly be infinite. However in practice, transmission starts and ends at a given time, which means that we only consider generators made of a finite number of Pauli operators. The code subspace is described by the generators of its stabilizer group, S. These generators are given by: It is easy to check that all the generators commute and are independent. Thus, the code subspace (i.e. the largest common eigenspace of the generators with eigenvalue +1) is non-trivial. An important point to address when considering stabilizer codes is the ability to manipulate encoded information. Namely, we want to find the encoded Pauli operators X i , Z i corresponding to logical qubit i. These operators must satisfy the following relations: where N (S) denotes the normalizer of S. Equation (3) states that the encoded Pauli operators leave the code subspace globally invariant, but have a non-trivial action on its elements, while the Equations (4-6) ensure that manipulating qubit i does not affect other qubits. There exists a great choice of different sets of such operators, however they are not equivalent in the perspective of effectively manipulating the encoded quantum information in an easy way: in practice only those with a small number of terms different from the identity are useful. For our particular example, such set exists and has a structure invariant by a shift of five qubits: Hence, a unitary transformation on a single encoded qubit will in general be implemented by a unitary transformation on five physical qubits. At this point, one can wonder what in this code differs from a generic block code. The answer to this question comes from the particular structure of the stabilizer generators: beside M 0 and M ∞ , the generators of the stabilizer group can be casted into sets of constant size (e.g. four), each set acting on a fixed number (e.g. seven) of consecutive qubits. In addition, each set has a fixed overlap (e.g. of two qubits) with the set immediately before and immediately after. This very peculiar structure defines quantum convolutional codes and we can prove [13] that this implies the possibility of online encoding and the existence of an efficient error estimation algorithm.
Encoding circuit -As explained in D. Gottesman's Ph.D. thesis [14], there are various ways to realize the encoding into the code subspace. However, for convolutional codes, they are not equivalent: standard encoding circuits usually require to wait until the last 'to-beprotected' qubit has been obtained before sending the encoded state. In this section, we explain how to take advantage of the structure of the stabilizer generators to overcome this limitation and encode the qubits online. We first exhibit a map from the computational basis of the 'to-be-protected' qubits to a basis of the code subspace. As a second step, we derive the quantum circuit implementing this map in a unitary way.
More precisely, consider the following set of states: where P = i (I + M i )/ √ 2 is the projection operator onto the code subspace. Since Z i commutes with all the generators of the stabilizer group, the following equation holds for any element of the set: In practice, to encode a stream of qubits q i , we first add to it ancillary qubits in the |0 state such that the 'to-be-protected' qubit i is now at the position 5i + 1. Then, we need to implement P for these specific input states as a unitary transformation onto the whole Hilbert space. This can be done in full generality as explained in [14], and gives the encoding circuit of Fig. 1. From this simple example, it is easy to understand that the possibility of online encoding for quantum convolutional codes is a consequence of the finite extension of the support of the generators of the stabilizer group and of the encoded Pauli operators. Also note that alternative encoding methods can be found and can be relevant when considering some specific applications, but these issues are beyond the scope of this letter.
Error propagation and online decoding -Due to their very specific nature, convolutional codes propagate information contained in a given qubit to its successors (see again Fig. 1). During the decoding process (i.e. the inverse of encoding) this can actually become a problem: an error affecting a finite number of qubits before decoding can propagate through the decoding circuit and finally affect an infinite number of qubits. Such error is called catastrophic. It is worth mentioning that this issue is to the quantum domain: classical convolutional encoders might have catastrophic errors [15,16]. Fortunately, in both cases, non-catastrophic encoders exist. More precisely, given a specific encoder one can find a procedure to determine whether it has catastrophic errors or not. For classical codes this is a well known result established by Massey and Sain [17]. For the quantum domain, we can show [13] that the circuit of noncatastrophic encoders fulfills the following requirement: its gates form a finite number of layers and commute with each other inside a layer. The idea behind this theorem is simple. In general, an error affecting some qubits will propagate to all the other qubits involved in a gate with the erroneous ones. When those qubits are further used in other gates the error continues to propagate until no more gates are applied. The commutation relation together with the finiteness of the number of layers ensures that, for any finite size error, only a finite number of gates will enter in the propagation process. Thus all errors are non-catastrophic. Fig. 2 illustrates this 'pearl-necklace' structure for our example, and thus proves that our rate 1/5 quantum convolutional code is non-catastrophic.
Moreover, it can be shown that this condition implies the existence of a forward decoding scheme: there is no need to wait for the last qubit to start decoding (see Fig. 2). For non-catastrophic codes, both encoding and decoding can be done online [13].
Maximum likelihood error estimation -An error correcting code aims at protecting information sent over a noisy communication channel by letting the receiver infer which error possibly affected the information. This is the role of the error estimation algorithm. On average, the correct information is most often retrieved when the estimated error coincides with the most likely error. Thus, it is both of theoretical and practical relevance to have an efficient maximum likelihood error estimation algorithm for our quantum convolutional codes. In this section, we exhibit such algorithm. It is indeed the quantum analogue of the well-known Viterbi algorithm for classical convolutional codes. The Viterbi algorithm realizes a maximum likelihood error estimation on all memoryless channels with a complexity linear in the number of encoded bits. This explains why classical convolutional codes are so widely used for reducing the noise on communication channels.
Our algorithm for quantum convolutional codes processes the information obtained through the syndrome in order to infer the most likely error. The circuit for obtaining the syndromes follows the usual phase estimation scheme: an ancillary qubit is prepared in the |0 state; undergoes a Hadamard transform; controls the application of one of the generator M i of the stabilizer group; again undergoes a Hadamard transform; and is finally measured in the {|0 , |1 } basis. Then, the algorithm updates a list of maximum likelihood error candidates by looking at a small number of syndromes at a time, and by taking local decisions. It is preceded and followed by appropriate initialization and termination steps.
The initialization step lists all error candidates, {E 0 j } j , for the first two qubits which are compatible with the syndrome M 0 . There are exactly 8 = 4 2 /2 of them (there are 4 2 different operators with support on the first two qubits, but the constraint associated with M 0 divides this set into two equal parts). This list constitutes the input of the main loop of the algorithm. At step i, the algorithm constructs a list of some most likely error candidates, {E i j } j compatible with the syndromes M 0 to M 4i . Each candidate E i j is thus specified only on qubits 1 to 5i+2. The crucial point of the algorithm is to maintain a fixed size of this list, and hence to avoid the exponential blow up that would arise when listing all error candidates compatible with these syndromes. More precisely, E i j is a most likely candidate whose restriction on qubit 5i + 1 and 5i + 2 is prescribed by the index j running over the set of 16 possible errors affecting those two qubits. The computation of any error candidate E i+1 k is easily achieved provided {E i j } j : consider the set of all possible extensions of the error candidates E i j to qubit 5i + 3 to 5i + 7 with the prescribed error k at position 5i + 6 and 5i + 7. It is easy to check that any such element is now compatible with syndromes M 0 to M 4(i+1) . The specific candidate E i+1 k is chosen to be the most likely operator among the elements of the latter set (in case of tie, one is chosen at random). This procedure is continued until reaching M ∞ , which again selects half of the candidates. The termination of the algorithm outputs the most likely candidate among the remaining ones. This constitutes the most likely error given the value of all the syndromes for the received stream of qubits [13].
The main property used to prove this fact is related to the structure of the generators of the stabilizer group: the value of the syndromes associated to M 4i+1 to M 4i+4 depend on the syndromes M 0 to M 4i only through the error operators at position 5i+1 and 5i+2. Thus, taking a sequence of local decisions allows to construct a list of error candidates among which one will coincide with the most likely error until qubit 5i + 2 while maintaining a linear complexity of the algorithm as the number of encoded qubits increases. Note that, the error maximizing the likelihood is known when the last syndrome is measured. Hence, it is in principle necessary to wait till the end of the transmission to actually correct the estimated error. However, as for the classical Viterbi algorithm, numerical simulations show that the different candidates at a given step coincide with the most likely error except on their last few positions. Thus, in practice it is possible to estimate the error online. In addition, we want to stress, that without increasing its complexity, this algorithm can take into account all memoryless quantum channels even if the single qubit error probabilities are not constant in time. For example, one could imagine that the qubits are photons sent through an optical fiber, and that the probabilities are evaluated by sending probe photons containing no useful information. Finally, as the codes described here are the exact translation to the quantum setting of the classical convolutional codes, one can also derive suboptimal error estimation algorithms (for their classical analogues see [15,16]). Most importantly, quantum convolutional codes can be decoded iteratively and allow quantum turbo decoding [13].
Conclusion -In this letter, we presented the theory of quantum convolutional codes by an example. We gave explicitly the associated encoding and decoding circuits, as well as a low complexity maximum likelihood error estimation algorithm. We believe that such codes could be used to reduce errors for long distance quantum communications provided that we are able to perform a small and fixed number quantum gates with good fidelity. Moreover, the tools developed for quantum convolutional codes can be used to translate other families of classical codes to the quantum domain, like for instance low density parity check codes.