format: text

text:
# Proceedings of HLT/NAACL 2003 Learning to Paraphrase: An Unsupervised Approach Using Multiple-Sequence Alignment

## 1 Introduction

> This is a late parrot! It’s a stiff! Bereft of life, it rests in peace! If you hadn’t nailed him to the perch he would be pushing up the daisies! Its metabolical processes are of interest only to historians! It’s hopped the twig! It’s shuffled off this mortal coil! It’s rung down the curtain and joined the choir invisible! This is an EX-PARROT! — Monty Python, “Pet Shop”

A mechanism for automatically generating multiple paraphrases of a given sentence would be of significant practical import for text-to-text generation systems. Applications include summarization \[Knight and Marcu, 2000\] and rewriting \[Chandrasekar and Bangalore, 1997\]: both could employ such a mechanism to produce candidate sentence paraphrases that other system components would filter for length, sophistication level, and so forth.111Another interesting application, somewhat tangential to generation, would be to expand existing corpora by providing several versions of their component sentences. This could, for example, aid machine-translation evaluation, where it has become common to evaluate systems by comparing their output against a bank of several reference translations for the same sentences \[Papineni et al., 2002\]. See ?) and ?) for other uses of such data. Not surprisingly, therefore, paraphrasing has been a focus of generation research for quite some time \[McKeown, 1979, Meteer and Shaked, 1988, Dras, 1999\].

One might initially suppose that sentence-level paraphrasing is simply the result of word-for-word or phrase-by-phrase substitution applied in a domain- and context-independent fashion. However, in studies of paraphrases across several domains \[Iordanskaja, Kittredge, and Polguere, 1991, Robin, 1994, McKeown, Kukich, and Shaw, 1994\], this was generally not the case. For instance, consider the following two sentences (similar to examples found in ?)):

| After the latest Fed rate cut, stocks rose across the board. |
| --- |
| Winners strongly outpaced losers after Greenspan cut interest rates again. |

Observe that “Fed” (Federal Reserve) and “Greenspan” are interchangeable only in the domain of US financial matters. Also, note that one cannot draw one-to-one correspondences between single words or phrases. For instance, nothing in the second sentence is really equivalent to “across the board”; we can only say that the entire clauses “stocks rose across the board” and “winners strongly outpaced losers” are paraphrases. This evidence suggests two consequences: (1) we cannot rely solely on generic domain-independent lexical resources for the task of paraphrasing, and (2) sentence-level paraphrasing is an important problem extending beyond that of paraphrasing smaller lexical units.

Our work presents a novel knowledge-lean algorithm that uses multiple-sequence alignment (MSA) to learn to generate sentence-level paraphrases essentially from unannotated corpus data alone. In contrast to previous work using MSA for generation \[Barzilay and Lee, 2002\], we need neither parallel data nor explicit information about sentence semantics. Rather, we use two comparable corpora, in our case, collections of articles produced by two different newswire agencies about the same events. The use of related corpora is key: we can capture paraphrases that on the surface bear little resemblance but that, by the nature of the data, must be descriptions of the same information. Note that we also acquire paraphrases from each of the individual corpora; but the lack of clues as to sentence equivalence in single corpora means that we must be more conservative, only selecting as paraphrases items that are structurally very similar.

Our approach has three main steps. First, working on each of the comparable corpora separately, we compute lattices — compact graph-based representations — to find commonalities within (automatically derived) groups of structurally similar sentences. Next, we identify pairs of lattices from the two different corpora that are paraphrases of each other; the identification process checks whether the lattices take similar arguments. Finally, given an input sentence to be paraphrased, we match it to a lattice and use a paraphrase from the matched lattice’s mate to generate an output sentence. The key features of this approach are:

Focus on paraphrase generation. In contrast to earlier work, we not only extract paraphrasing rules, but also automatically determine which of the potentially relevant rules to apply to an input sentence and produce a revised form using them.

Flexible paraphrase types. Previous approaches to paraphrase acquisition focused on certain rigid types of paraphrases, for instance, limiting the number of arguments. In contrast, our method is not limited to a set of a priori-specified paraphrase types.

Use of comparable corpora and minimal use of knowledge resources. In addition to the advantages mentioned above, comparable corpora can be easily obtained for many domains, whereas previous approaches to paraphrase acquisition (and the related problem of phrase-based machine translation \[Wang, 1998, Och, Tillman, and Ney, 1999, Vogel and Ney, 2000\]) required parallel corpora. We point out that one such approach, recently proposed by ?), also represents paraphrases by lattices, similarly to our method, although their lattices are derived using parse information.

Moreover, our algorithm does not employ knowledge resources such as parsers or lexical databases, which may not be available or appropriate for all domains — a key issue since paraphrasing is typically domain-dependent. Nonetheless, our algorithm achieves good performance.

## 2 Related work

Previous work on automated paraphrasing has considered different levels of paraphrase granularity. Learning synonyms via distributional similarity has been well-studied \[Pereira, Tishby, and Lee, 1993, Grefenstette, 1994, Lin, 1998\]. ?) and ?) identify phrase-level paraphrases, while ?) and ?) acquire structural paraphrases encoded as templates. These latter are the most closely related to the sentence-level paraphrases we desire, and so we focus in this section on template-induction approaches.

?) extract inference rules, which are related to paraphrases (for example, X wrote Y implies X is the author of Y), to improve question answering. They assume that paths in dependency trees that take similar arguments (leaves) are close in meaning. However, only two-argument templates are considered. ?) also use dependency-tree information to extract templates of a limited form (in their case, determined by the underlying information extraction application). Like us (and unlike Lin and Pantel, who employ a single large corpus), they use articles written about the same event in different newspapers as data.

Our approach shares two characteristics with the two methods just described: pattern comparison by analysis of the patterns’ respective arguments, and use of non-parallel corpora as a data source. However, extraction methods are not easily extended to generation methods. One problem is that their templates often only match small fragments of a sentence. While this is appropriate for other applications, deciding whether to use a given template to generate a paraphrase requires information about the surrounding context provided by the entire sentence.

## 3 Algorithm

#### Overview

We first sketch the algorithm’s broad outlines. The subsequent subsections provide more detailed descriptions of the individual steps.

The major goals of our algorithm are to learn:

* recurring patterns in the data, such as X (injured/wounded) Y people, Z seriously, where the capital letters represent variables;
* pairings between such patterns that represent paraphrases, for example, between the pattern X (injured/wounded) Y people, Z of them seriously and the pattern Y were (wounded/hurt) by X, among them Z were in serious condition.

Figure 1 illustrates the main stages of our approach. During training, pattern induction is first applied independently to the two datasets making up a pair of comparable corpora. Individual patterns are learned by applying multiple-sequence alignment to clusters of sentences describing approximately similar events; these patterns are represented compactly by lattices (see Figure 3). We then check for lattices from the two different corpora that tend to take the same arguments; these lattice pairs are taken to be paraphrase patterns.

Once training is done, we can generate paraphrases as follows: given the sentence “The surprise bombing injured twenty people, five of them seriously”, we match it to the lattice X (injured/wounded) Y people, Z of them seriously which can be rewritten as Y were (wounded/hurt) by X, among them Z were in serious condition, and so by substituting arguments we can generate “Twenty were wounded by the surprise bombing, among them five were in serious condition” or “Twenty were hurt by the surprise bombing, among them five were in serious condition”.

### 3.1 Sentence clustering

Our first step is to cluster sentences into groups from which to learn useful patterns; for the multiple-sequence techniques we will use, this means that the sentences within clusters should describe similar events and have similar structure, as in the sentences of Figure 2. This is accomplished by applying hierarchical complete-link clustering to the sentences using a similarity metric based on word n-gram overlap ($`n=1,2,3,4`$). The only subtlety is that we do not want mismatches on sentence details (e.g., the location of a raid) causing sentences describing the same type of occurrence (e.g., a raid) from being separated, as this might yield clusters too fragmented for effective learning to take place. (Moreover, variability in the arguments of the sentences in a cluster is needed for our learning algorithm to succeed; see below.) We therefore first replace all appearances of dates, numbers, and proper names222Our crude proper-name identification method was to flag every phrase (extracted by a noun-phrase chunker) appearing capitalized in a non-sentence-initial position sufficiently often.  with generic tokens. Clusters with fewer than ten sentences are discarded.

### 3.2 Inducing patterns

In order to learn patterns, we first compute a multiple-sequence alignment (MSA) of the sentences in a given cluster. Pairwise MSA takes two sentences and a scoring function giving the similarity between words; it determines the highest-scoring way to perform insertions, deletions, and changes to transform one of the sentences into the other. Pairwise MSA can be extended efficiently to multiple sequences via the iterative pairwise alignment, a polynomial-time method commonly used in computational biology \[Durbin et al., 1998\].333Scoring function: aligning two identical words scores 1; inserting a word scores -0.01, and aligning two different words scores -0.5 (parameter values taken from ?)). The results can be represented in an intuitive form via a word lattice (see Figure 3), which compactly represents (n-gram) structural similarities between the cluster’s sentences.

To transform lattices into generation-suitable patterns requires some understanding of the possible varieties of lattice structures. The most important part of the transformation is to determine which words are actually instances of arguments, and so should be replaced by slots (representing variables). The key intuition is that because the sentences in the cluster represent the same type of event, such as a bombing, but generally refer to different instances of said event (e.g. a bombing in Jerusalem versus in Gaza), areas of large variability in the lattice should correspond to arguments.

To quantify this notion of variability, we first formalize its opposite: commonality. We define backbone nodes as those shared by more than 50% of the cluster’s sentences. The choice of 50% is not arbitrary — it can be proved using the pigeonhole principle that our strict-majority criterion imposes a unique linear ordering of the backbone nodes that respects the word ordering within the sentences, thus guaranteeing at least a degree of well-formedness and avoiding the problem of how to order backbone nodes occurring on parallel “branches” of the lattice.

Once we have identified the backbone nodes as points of strong commonality, the next step is to identify the regions of variability (or, in lattice terms, many parallel disjoint paths) between them as (probably) corresponding to the arguments of the propositions that the sentences represent. For example, in the top of Figure 3, the words “southern city, “settlement of NAME”,“coastal resort of NAME”, etc. all correspond to the location of an event and could be replaced by a single slot. Figure 3 shows an example of a lattice and the derived slotted lattice; we give the details of the slot-induction process in the Appendix.

### 3.3 Matching lattices

Now, if we were using a parallel corpus, we could employ sentence-alignment information to determine which lattices correspond to paraphrases. Since we do not have this information, we essentially approximate the parallel-corpus situation by correlating information from descriptions of (what we hope are) the same event occurring in the two different corpora.

Our method works as follows. Once lattices for each corpus in our comparable-corpus pair are computed, we identify lattice paraphrase pairs, using the idea that paraphrases will tend to take the same values as arguments \[Shinyama et al., 2002, Lin and Pantel, 2001\]. More specifically, we take a pair of lattices from different corpora, look back at the sentence clusters from which the two lattices were derived, and compare the slot values of those cross-corpus sentence pairs that appear in articles written on the same day on the same topic; we pair the lattices if the degree of matching is over a threshold tuned on held-out data. For example, suppose we have two (linearized) lattices slot1 bombed slot2 and slot3 was bombed by slot4 drawn from different corpora. If in the first lattice’s sentence cluster we have the sentence “the plane bombed the town”, and in the second lattice’s sentence cluster we have a sentence written on the same day reading “the town was bombed by the plane”, then the corresponding lattices may well be paraphrases, where slot1 is identified with slot4 and slot2 with slot3.

To compare the set of argument values of two lattices, we simply count their word overlap, giving double weight to proper names and numbers and discarding auxiliaries (we purposely ignore order because paraphrases can consist of word re-orderings).

### 3.4 Generating paraphrase sentences

Given a sentence to paraphrase, we first need to identify which, if any, of our previously-computed sentence clusters the new sentence belongs most strongly to. We do this by finding the best alignment of the sentence to the existing lattices.444 To facilitate this process, we add “insert” nodes between backbone nodes; these nodes can match any word sequence and thus account for new words in the input sentence. Then, we perform multiple-sequence alignment where insertions score -0.1 and all other node alignments receive a score of unity. If a matching lattice is found, we choose one of its comparable-corpus paraphrase lattices to rewrite the sentence, substituting in the argument values of the original sentence. This yields as many paraphrases as there are lattice paths.

## 4 Evaluation

All evaluations involved judgments by native speakers of English who were not familiar with the paraphrasing systems under consideration.

We implemented our system on a pair of comparable corpora consisting of articles produced between September 2000 and August 2002 by the Agence France-Presse (AFP) and Reuters news agencies. Given our interest in domain-dependent paraphrasing, we limited attention to 9MB of articles, collected using a TDT-style document clustering system, concerning individual acts of violence in Israel and army raids on the Palestinian territories. From this data (after removing 120 articles as a held-out parameter-training set), we extracted 43 slotted lattices from the AFP corpus and 32 slotted lattices from the Reuters corpus, and found 25 cross-corpus matching pairs; since lattices contain multiple paths, these yielded 6,534 template pairs.555The extracted paraphrases are available at http://www.cs.cornell.edu/Info/Projects/
NLP/statpar.html

### 4.1 Template Quality Evaluation

Before evaluating the quality of the rewritings produced by our templates and lattices, we first tested the quality of a random sample of just the template pairs. In our instructions to the judges, we defined two text units (such as sentences or snippets) to be paraphrases if one of them can generally be substituted for the other without great loss of information (but not necessarily vice versa). 666We switched to this “one-sided” definition because in initial tests judges found it excruciating to decide on equivalence. Also, in applications such as summarization some information loss is acceptable. Given a pair of templates produced by a system, the judges marked them as paraphrases if for many instantiations of the templates’ variables, the resulting text units were paraphrases. (Several labelled examples were provided to supply further guidance).

To put the evaluation results into context, we wanted to compare against another system, but we are not aware of any previous work creating templates precisely for the task of generating paraphrases. Instead, we made a good-faith effort to adapt the DIRT system \[Lin and Pantel, 2001\] to the problem, selecting the 6,534 highest-scoring templates it produced when run on our datasets. (The system of ?) was unsuitable for evaluation purposes because their paraphrase extraction component is too tightly coupled to the underlying information extraction system.) It is important to note some important caveats in making this comparison, the most prominent being that DIRT was not designed with sentence-paraphrase generation in mind — its templates are much shorter than ours, which may have affected the evaluators’ judgments — and was originally implemented on much larger data sets.777To cope with the corpus-size issue, DIRT was trained on an 84MB corpus of Middle-East news articles, a strict superset of the 9MB we used. Other issues include the fact that DIRT’s output needed to be converted into English: it produces paths like “N:of:N $``$tide$``$ N:nn:N”, which we transformed into “Y tide of X” so that its output format would be the same as ours.  The point of this evaluation is simply to determine whether another corpus-based paraphrase-focused approach could easily achieve the same performance level.

In brief, the DIRT system works as follows. Dependency trees are constructed from parsing a large corpus. Leaf-to-leaf paths are extracted from these dependency trees, with the leaves serving as slots. Then, pairs of paths in which the slots tend to be filled by similar values, where the similarity measure is based on the mutual information between the value and the slot, are deemed to be paraphrases.

We randomly extracted 500 pairs from the two algorithms’ output sets. Of these, 100 paraphrases (50 per system) made up a “common” set evaluated by all four judges, allowing us to compute agreement rates; in addition, each judge also evaluated another “individual” set, seen only by him- or herself, consisting of another 100 pairs (50 per system). The “individual” sets allowed us to broaden our sample’s coverage of the corpus.888Each judge took several hours at the task, making it infeasible to expand the sample size further. The pairs were presented in random order, and the judges were not told which system produced a given pair.

As Figure 4 shows, our system outperforms the DIRT system, with a consistent performance gap for all the judges of about 38%, although the absolute scores vary (for example, Judge 4 seems lenient). The judges’ assessment of correctness was fairly constant between the full 100-instance set and just the 50-instance common set alone.

In terms of agreement, the Kappa value (measuring pairwise agreement discounting chance occurrences999One issue is that the Kappa statistic doesn’t account for varying difficulty among instances. For this reason, we actually asked judges to indicate for each instance whether making the validity decision was difficult. However, the judges generally did not agree on difficulty. Post hoc analysis indicates that perception of difficulty depends on each judge’s individual “threshold of similarity”, not just the instance itself. ) on the common set was 0.54, which corresponds to moderate agreement \[Landis and Koch, 1977\]. Multiway agreement is depicted in Figure 4 — there, we see that in 86 of 100 cases, at least three of the judges gave the same correctness assessment, and in 60 cases all four judges concurred.

### 4.2 Evaluation of the generated paraphrases

Finally, we evaluated the quality of the paraphrase sentences generated by our system, thus (indirectly) testing all the system components: pattern selection, paraphrase acquisition, and generation. We are not aware of another system generating sentence-level paraphrases. Therefore, we used as a baseline a simple paraphrasing system that just replaces words with one of their randomly-chosen WordNet synonyms (using the most frequent sense of the word that WordNet listed synonyms for). The number of substitutions was set proportional to the number of words our method replaced in the same sentence. The point of this comparison is to check whether simple synonym substitution yields results comparable to those of our algorithm. 101010 We chose not to employ a language model to re-rank either system’s output because such an addition would make it hard to isolate the contribution of the paraphrasing component itself.

For this experiment, we randomly selected 20 AFP articles about violence in the Middle East published later than the articles in our training corpus. Out of 484 sentences in this set, our system was able to paraphrase 59 (12.2%). (We chose parameters that optimized precision rather than recall on our small held-out set.) We found that after proper name substitution, only seven sentences in the test set appeared in the training set,111111Since we are doing unsupervised paraphrase acquisition, train-test overlap is allowed. which implies that lattices boost the generalization power of our method significantly: from seven to 59 sentences. Interestingly, the coverage of the system varied significantly with article length. For the eight articles of ten or fewer sentences, we paraphrased 60.8% of the sentences per article on average, but for longer articles only 9.3% of the sentences per article on average were paraphrased. Our analysis revealed that long articles tend to include large portions that are unique to the article, such as personal stories of the event participants, which explains why our algorithm had a lower paraphrasing rate for such articles.

All 118 instances (59 per system) were presented in random order to two judges, who were asked to indicate whether the meaning had been preserved. Of the paraphrases generated by our system, the two evaluators deemed 81.4% and 78%, respectively, to be valid, whereas for the baseline system, the correctness results were 69.5% and 66.1%, respectively. Agreement according to the Kappa statistic was 0.6. Note that judging full sentences is inherently easier than judging templates, because template comparison requires considering a variety of possible slot values, while sentences are self-contained units.

Figure 5 shows two example sentences, one where our MSA-based paraphrase was deemed correct by both judges, and one where both judges deemed the MSA-generated paraphrase incorrect. Examination of the results indicates that the two systems make essentially orthogonal types of errors. The baseline system’s relatively poor performance supports our claim that whole-sentence paraphrasing is a hard task even when accurate word-level paraphrases are given.

## 5 Conclusions

We presented an approach for generating sentence level paraphrases, a task not addressed previously. Our method learns structurally similar patterns of expression from data and identifies paraphrasing pairs among them using a comparable corpus. A flexible pattern-matching procedure allows us to paraphrase an unseen sentence by matching it to one of the induced patterns. Our approach generates both lexical and structural paraphrases.

Another contribution is the induction of MSA lattices from non-parallel data. Lattices have proven advantageous in a number of NLP contexts \[Mangu, Brill, and Stolcke, 2000, Bangalore, Murdock, and Riccardi, 2002, Barzilay and Lee, 2002, Pang, Knight, and Marcu, 2003\], but were usually produced from (multi-)parallel data, which may not be readily available for many applications. We showed that word lattices can be induced from a type of corpus that can be easily obtained for many domains, broadening the applicability of this useful representation.

## Acknowledgments

We are grateful to many people for helping us in this work. We thank Stuart Allen, Itai Balaban, Hubie Chen, Tom Heyerman, Evelyn Kleinberg, Carl Sable, and Alex Zubatov for acting as judges. Eric Breck helped us with translating the output of the DIRT system. We had numerous very useful conversations with all those mentioned above and with Eli Barzilay, Noemie Elhadad, Jon Kleinberg (who made the “pigeonhole” observation), Mirella Lapata, Smaranda Muresan and Bo Pang. We are very grateful to Dekang Lin for providing us with DIRT’s output. We thank the Cornell NLP group, especially Eric Breck, Claire Cardie, Amanda Holland-Minkley, and Bo Pang, for helpful comments on previous drafts. This paper is based upon work supported in part by the National Science Foundation under ITR/IM grant IIS-0081334 and a Sloan Research Fellowship. Any opinions, findings, and conclusions or recommendations expressed above are those of the authors and do not necessarily reflect the views of the National Science Foundation or the Sloan Foundation.

## Appendix

In this appendix, we describe how we insert slots into lattices to form slotted lattices.

Recall that the backbone nodes in our lattices represent words appearing in many of the sentences from which the lattice was built. As mentioned above, the intuition is that areas of high variability between backbone nodes may correspond to arguments, or slots. But the key thing to note is that there are actually two different phenomena giving rise to multiple parallel paths: argument variability, described above, and synonym variability. For example, Figure 6(b) contains parallel paths corresponding to the synonyms “injured” and “wounded”. Note that we want to remove argument variability so that we can generate paraphrases of sentences with arbitrary arguments; but we want to preserve synonym variability in order to generate a variety of sentence rewritings.

To distinguish these two situations, we analyze the split level of backbone nodes that begin regions with multiple paths. The basic intuition is that there is probably more variability associated with arguments than with synonymy: for example, as datasets increase, the number of locations mentioned rises faster than the number of synonyms appearing. We make use of a synonymy threshold $`s`$ (set by held-out parameter-tuning to 30), as follows.

* If no more than $`s`$% of all the edges out of a backbone node lead to the same next node, we have high enough variability to warrant inserting a slot node.
* Otherwise, we incorporate reliable synonyms121212While our original implementation, evaluated in Section 4, identified only single-word synonyms, phrase-level synonyms can similarly be acquired by considering chains of nodes connecting backbone nodes. into the backbone structure by preserving all nodes that are reached by at least $`s`$% of the sentences passing through the two neighboring backbone nodes.

Furthermore, all backbone nodes labelled with our special generic tokens are also replaced with slot nodes, since they, too, probably represent arguments (we condense adjacent slots into one). Nodes with in-degree lower than the synonymy threshold are removed under the assumption that they probably represent idiosyncrasies of individual sentences. See Figure 6 for examples.

Figure 3 shows an example of a lattice and the slotted lattice derived via the process just described.


text:
# Regge calculus from discontinuous metrics

## Abstract

Regge calculus is considered as a particular case of the more general system where the linklengths of any two neighbouring 4-tetrahedra do not necessarily coincide on their common face. This system is treated as that one described by metric discontinuous on the faces. In the superspace of all discontinuous metrics the Regge calculus metrics form some hypersurface. Quantum theory of the discontinuous metric system is assumed to be fixed somehow in the form of quantum measure on (the space of functionals on) the superspace. The problem of reducing this measure to the Regge hypersurface is addressed. The quantum Regge calculus measure is defined from a discontinuous metric measure by inserting the $`\delta `$-function-like phase factor. The requirement that this reduction would respect natural physical properties (positivity, well-defined continuum limit, absence of lattice artefacts) put rather severe restrictions and allows to define practically uniquely this phase factor.

Since the idea had been put forward that Regge calculus should be formulated in terms of the areas of the triangles rather than the edge lengths  the so-called area Regge calculus model was of a certain interest . In this model the areas of the 2-faces (triangles) are treated as independent variables. Thereby configuration space of the theory becomes larger, and ordinary Regge calculus corresponds only to some subset (hypersurface) in this space. Despite of this, the equations of motion of the theory get simplified. In particular, a kind of the area Regge calculus, area tensor-connection one  possesses the set of commuting constraints (in the continuous time limit) and can be quantised resulting in the finite expectation values for areas . The problem is how to pass from areas to lengths. The constraints enforcing areas to be expressible in terms of the edge lengths have been discussed in . Now the problem is dynamical one, e. g. given the Feynman path integral on the configuration space of area Regge calculus, how could we define such an integral on the subspace corresponding to the usual length-based Regge calculus?

In the area Regge calculus the two 4-simplices $`\sigma ^4`$ sharing a given 3-face $`\sigma ^3`$ do not necessarily have coinciding linklengths on this face, only the 4 conditions equating the areas of the triangles $`\sigma ^2`$ on this 3-face are required. One can go further and discuss the 4-simplices with completely independent lengths, i. e. impose no conditions at all. Area Regge calculus will be a particular case of this configuration. Introducing metric tensor $`g_{\lambda \mu }`$ one can say that it is discontinuous on the 3-faces. Regge calculus is then specified by setting continuity conditions on the induced 3-face metric $`g_{ab}^{}`$ on the 3-faces $`\sigma ^3`$,

$$\mathrm{\Delta }_{\sigma ^3}g_{ab}^{}\stackrel{\mathrm{def}}{=}g_{ab}^{}(\sigma _1^4)g_{ab}^{}(\sigma _2^4)=0$$
(1)
where $`\sigma _1^4`$, $`\sigma _2^4`$ are the two 4-simplices sharing the 3-face $`\sigma ^3`$ = $`\sigma _1^4\sigma _2^4`$. (At the same time the normal-to-face metric $`g^{}`$ is discontinuous thus providing nonzero angle defects).

The conditions (1) define some hypersurface $`\mathrm{\Gamma }_{\mathrm{cont}}`$ in the superspace of simplicial (piecewise-flat) metrics including discontinuous ones. Suppose quantum theory on this superspace is fixed in the form of the Feynman path integral. That is, a quantum measure is given. The measure can be viewed as a linear functional $`\mu (\mathrm{\Psi })`$ on the space of the functionals $`\mathrm{\Psi }(\{g\})`$ on the superspace. To pass to the quantum theory on the hypersurface $`\mathrm{\Gamma }_{\mathrm{cont}}`$ we use some analogy with the quantum-mechanical notion of the ”state”, although full analogy is absent since we do not mean decomposing the spacetime into space and time. In our case the functionals $`\mathrm{\Psi }(\{g\})`$ are intended to describe the states. (Rather these could be considered as analogs of quantum-mechanical $`\mathrm{\Phi }^{}\mathrm{\Phi }`$.) We are interested in the particular case of these with support on $`\mathrm{\Gamma }_{\mathrm{cont}}`$ of the form

$$\mathrm{\Psi }(\{g\})=\psi (\{g\})\delta _{\mathrm{cont}}(\{g\})$$
(2)
where $`\delta _{\mathrm{cont}}(\{g\})`$ is (many-dimensional) $`\delta `$-function with support on $`\mathrm{\Gamma }_{\mathrm{cont}}`$. Generally derivatives of $`\delta `$-function also ensure given support, but these would violate positivity in what follows. If the measure can be defined on such the functionals then we define the measure on $`\mathrm{\Gamma }_{\mathrm{cont}}`$,

$$\mu _{\mathrm{cont}}()=\mu (\delta _{\mathrm{cont}}(\{g\})).$$
(3)
To construct $`\delta _{\mathrm{cont}}`$ first reveal irreducible set of the constraints on the metric of the type of (1) in terms of linklengths. For that consider all the 4-simplices containing the given link, i. e. the star of the link. The surface of the star is topologically the 2-sphere and is depicted in the Fig. 1.

In this picture the $`k`$-simplices $`\sigma ^k`$ mean the 4D $`k+1`$-simplices $`\mathrm{O}^{}\sigma ^k`$, in particular, the considered link $`\mathrm{O}^{}\mathrm{O}`$ is represented here by the vertex O, and it’s length squared defined in the 4-simplex, say, $`\mathrm{O}^{}\mathrm{OABC}`$ is denoted here by $`s_{\mathrm{O}(\mathrm{ABC})}`$. The fact that these values are the same in all the 4-simplices $`\mathrm{O}^{}\sigma ^k`$ is taken into account by the product of $`\delta `$-functions over all the links on the 2-sphere Fig.1,

$$\underset{\sigma ^2\mathrm{O}}{}\delta (\mathrm{\Delta }_{\sigma ^2}s_\mathrm{O})$$
(4)
where $`\mathrm{\Delta }_{\mathrm{OAB}}s_\mathrm{O}`$ = $`s_{\mathrm{O}(\mathrm{ABC})}`$ \- $`s_{\mathrm{O}(\mathrm{ABG})}`$, etc. This product containes redundant $`\delta `$-functions connected with occurence of cycles enclosing separate links $`\sigma ^1`$ = OA, OB, …(corresponding to vertices on the 2-sphere Fig.1). To exclude cycles, draw some (2D in our picture) cut $`H_\mathrm{O}^{(2)}`$ in the star of the point O consisting of the triangles and passing through each radial link. By definition, $`H_\mathrm{O}^{(2)}`$ is a collection of the triangles on which continuity conditions for $`s_\mathrm{O}`$ should not be imposed. This cut should be chosen in such a way that it, first, would not consist of components intersecting only at the point O (in order that cycles in the compliment of the cut in the star were absent indeed), and, second, would not divide interior of the star into the disconnected components (otherwise $`s_\mathrm{O}`$ in these components would be allowed to be different). In other words, intersection of $`H_\mathrm{O}^{(2)}`$ with the 2-sphere $`S_\mathrm{O}^{(2)}`$ of Fig.1 should be (poligonal) continuous line without self-intersections.

To cancel redundant $`\delta `$’s in (4) one should divide (4) by many-dimensional $`\delta `$-function which would express continuity of $`s_\mathrm{O}`$ on $`H_\mathrm{O}^{(2)}`$. A sufficient condition for such the continuity is expressed by the product of $`\delta `$-functions over all the vertices on the 2-sphere Fig.1,

$$\underset{\sigma ^1\mathrm{O}}{}\delta (\mathrm{\Delta }_{\sigma ^1}s_\mathrm{O}).$$
(5)
Here $`\mathrm{\Delta }_{\sigma ^1}s_\mathrm{O}`$ $`\stackrel{\mathrm{def}}{=}`$ $`\mathrm{\Delta }_{\sigma ^2(\sigma ^1)}s_\mathrm{O}`$ where $`\sigma ^2(\sigma ^1)`$ is a one of the two triangles in $`H_\mathrm{O}^{(2)}`$ containing $`\sigma ^1`$, $`H_\mathrm{O}^{(2)}`$ $``$ $`\sigma ^2(\sigma ^1)`$ $``$ $`\sigma ^1`$.

In turn, (5) containes redundant $`\delta `$-functions (more accurately, one such function). Indeed, the number of edges in the continuous line without intersections $`H_\mathrm{O}^{(2)}`$ $``$ $`S_\mathrm{O}^{(2)}`$ is by one smaller than the number of vertices through which the line passes. This means that $`\sigma ^2(\sigma ^1)`$ involved in the definition of (5) above is not one-to-one correspondence, and there is a pair of the two neighbouring radial links, $`\sigma _1^1`$, $`\sigma _2^1`$, the edges of the same triangle $`\sigma ^2(\sigma _1^1)`$ = $`\sigma ^2(\sigma _2^1)`$ so that the $`\delta `$-function of $`\mathrm{\Delta }_{\sigma _1^1}s_\mathrm{O}`$ = $`\mathrm{\Delta }_{\sigma _2^1}s_\mathrm{O}`$ enters (5) twice. Therefore one should divide (5) by

$$\delta (\mathrm{\Delta }_\mathrm{O}s_\mathrm{O})$$
(6)
where $`\mathrm{\Delta }_\mathrm{O}s_\mathrm{O}`$ $`\stackrel{\mathrm{def}}{=}`$ $`\mathrm{\Delta }_{\sigma _1^1}s_\mathrm{O}`$ = $`\mathrm{\Delta }_{\sigma _2^1}s_\mathrm{O}`$. Again situation can be described as occurence of some reminder cycle, now in the cut $`H_\mathrm{O}^{(2)}`$ itself treated in some generalised way taking into account the number of times the cut passes the same triangle, and (6) just serves to cancel effect of this cycle. Such the cut OBABCDE…passing OAB twice is just shown in Fig.1.

The resulting $`\delta `$-function stating unambiguity of $`s_\mathrm{O}`$ looks like

$$\underset{\sigma ^2\mathrm{O}}{}\delta (\mathrm{\Delta }_{\sigma ^2}s_\mathrm{O})\left(\underset{\sigma ^1\mathrm{O}}{}\delta (\mathrm{\Delta }_{\sigma ^1}s_\mathrm{O})\right)^1\delta (\mathrm{\Delta }_\mathrm{O}s_\mathrm{O}).$$
(7)
Here the number of $`\delta `$-functions is $`L`$ $``$ $`P`$ \+ 1 where $`L`$, $`P`$ are the numbers of the links and vertices on the 2-sphere Fig.1, respectively. In some functional integral these are to be integrated over

$$\mathrm{d}s_{\mathrm{O}(\mathrm{ABC})}\mathrm{d}s_{\mathrm{O}(\mathrm{ACD})}\mathrm{d}s_{\mathrm{O}(\mathrm{ADE})}\mathrm{},$$
(8)
the overall number of integrations being $`T`$, the number of the triangles on the 2-sphere Fig.1. As a result, we are left with $`T`$ $``$ $`L`$ \+ $`P`$ $``$ 1 = 1 integration as it follows from the Euler characteristic 2 for the 2-sphere.

Upon restoring the 4D notations the eq. (7) reads

$$\underset{\sigma ^3\mathrm{O}^{}\mathrm{O}}{}\delta (\mathrm{\Delta }_{\sigma ^3}s_{\mathrm{O}^{}\mathrm{O}})\left(\underset{\sigma ^2\mathrm{O}^{}\mathrm{O}}{}\delta (\mathrm{\Delta }_{\sigma ^2}s_{\mathrm{O}^{}\mathrm{O}})\right)^1\delta (\mathrm{\Delta }_{\mathrm{O}^{}\mathrm{O}}s_{\mathrm{O}^{}\mathrm{O}}).$$
(9)
Take the product of these expressions over all the links $`\mathrm{O}^{}\mathrm{O}`$. Rearranging, we have for separate factors

$$\underset{\sigma ^1}{}\underset{\sigma ^k\sigma ^1}{}\delta (\mathrm{\Delta }_{\sigma ^k}s_{\sigma ^1})=\underset{\sigma ^k}{}\underset{\sigma ^1\sigma ^k}{}\delta (\mathrm{\Delta }_{\sigma ^k}s_{\sigma ^1})=\underset{\sigma ^k}{}\delta ^{k\frac{k+1}{2}}(\mathrm{\Delta }_{\sigma ^k}S_{\sigma ^k})$$
(10)
thus expressing these in terms of the discontinuities of the edge component metric $`S_{\sigma ^k}`$  induced on the $`k`$-simplex and being simply collection of $`k\frac{k+1}{2}`$ it’s edge lengths squared. The total product thus reads

$$\underset{\sigma ^3}{}\delta ^6(\mathrm{\Delta }_{\sigma ^3}S_{\sigma ^3})\left(\underset{\sigma ^2}{}\delta ^3(\mathrm{\Delta }_{\sigma ^2}S_{\sigma ^2})\right)^1\underset{\sigma ^1}{}\delta (\mathrm{\Delta }_{\sigma ^1}S_{\sigma ^1}).$$
(11)
Some remark should be made concerning the middle factor in this expression where the metric discontinuity $`\mathrm{\Delta }_{\sigma ^2}S_{\sigma ^2}`$ for the different components of metric $`S_{\sigma ^2}`$, in principle, may turn out to be defined between the different pairs of the neighbouring 4-simplices containing the given triangle $`\sigma ^2`$, if one uses the above construction. Namely, for each $`\sigma ^2`$ containing the given $`\sigma ^1`$ we take $`\sigma ^3`$, one of the two 3-faces containing $`\sigma ^2`$ and belonging to the 3D cut $`H_{\sigma ^1}^{(3)}`$ in the star of the link $`\sigma ^1`$ (the above $`H_\mathrm{O}^{(2)}`$ in 3D language). On this $`\sigma ^3`$ the considered discontinuity of the $`\sigma ^2`$-metric just should be taken. However, as we see, the choice of this $`\sigma ^3`$ depends (by means of $`H_{\sigma ^1}^{(3)}`$) on the edge $`\sigma ^1`$ of this triangle, i.e. may be different for the different components. Fortunately, it is possible to change the choice of this 3-face not violating the result so that it would become the same for the edges of a given triangle. Indeed, singularity connected with the cycle enclosing the triangle is contained in the product of the type $`\delta (s_1s_2)\delta (s_2s_3)\mathrm{}\delta (s_Ns_1)`$ over all $`N`$ 3-faces containing the triangle and can be cancelled by dividing it by any of the factors yielding the same result. Thereby definition of the discontinuity of the metric induced on the triangle can be adjusted to be the same for all the metric components.

The form (11) looks suitable for setting requirements which would help to fix a factor multiplying the $`\delta `$ functions in the measure. A natural assumption is that the result of implementing continuity condition for the induced $`k`$-metric across a $`k`$-face should not depend on the real form and size of the $`k`$-face, only on the hyperplane spanned by this face. This assumption looks natural if we consider Regge links as imaginary objects only used for the needs of triangulation on some smooth background metric. Of course, something like ”interaction” of the Regge links may exist, but this is supposed to be introduced by ”physical” part of the theory by which we mean the theory of discontinuous metric distributions already fixed somehow in the form of the functional integral, while what do we consider here is a kind of kinematical phase factor in which we are trying to minimize any dynamical effect especially introduced ”by hand”. It is convenient to rewrite corresponding $`\delta `$ function in terms of metric tensor $`g_{\lambda \mu }`$ and of a set of $`k`$ 4-vectors $`\tau _a^\lambda `$ defining the $`k`$-face and the induced metric on it, $`g_{ab}^{}`$ = $`\tau _a^\lambda \tau _b^\mu g_{\lambda \mu }`$. Then it is clear that the required factor is determinant of $`g_{ab}^{}`$ raised to the power $`\frac{1}{2}(k+1)`$, i. e. the $`(k+1)`$-th power of the $`k`$-face volume $`V_{\sigma ^k}`$. The resulting $`\delta `$ factor reads

$$[\mathrm{det}(\tau _a^\lambda \tau _b^\mu g_{\lambda \mu })]^{\frac{k+1}{2}}\delta ^{k\frac{k+1}{2}}(\tau _a^\lambda \tau _b^\mu \mathrm{\Delta }_{\sigma ^k}g_{\lambda \mu })=V_{\sigma ^k}^{k+1}\delta ^{k\frac{k+1}{2}}(\mathrm{\Delta }_{\sigma ^k}S_{\sigma ^k}).$$
(12)
It is invariant w.r.t. the deformations of the $`k`$-face keeping it placed in a fixed $`k`$-plane (the metric $`g_{\lambda \mu }`$ being fixed) $`\tau _a^\lambda `$ $``$ $`m_a^b\tau _b^\lambda `$ with arbitrary $`k`$ $`\times `$ $`k`$ matrix $`m`$. This property looks natural also from the viewpoint of existence of the continuum limit and, in particular, of absence of the lattice artefacts if we do not want to introduce these artefacts ”by hand”.

The final answer reads

$`\delta _{\mathrm{cont}}`$ $`=`$ $`{\displaystyle \underset{\sigma ^3}{}}V_{\sigma ^3}^4\delta ^6(\mathrm{\Delta }_{\sigma ^3}S_{\sigma ^3})\left({\displaystyle \underset{\sigma ^2}{}}V_{\sigma ^2}^3\delta ^3(\mathrm{\Delta }_{\sigma ^2}S_{\sigma ^2})\right)^1{\displaystyle \underset{\sigma ^1}{}}V_{\sigma ^1}^2\delta (\mathrm{\Delta }_{\sigma ^1}S_{\sigma ^1})`$ (13)
$`=`$ $`{\displaystyle \underset{\sigma ^3}{}}V_{\sigma ^3}^4{\displaystyle \underset{\sigma ^2}{}}V_{\sigma ^2}^3{\displaystyle \underset{\sigma ^1}{}}V_{\sigma ^1}^2{\displaystyle \underset{\sigma ^1,\sigma ^3\sigma ^1}{\overset{}{}}}\delta (\mathrm{\Delta }_{\sigma ^3}s_{\sigma ^1})`$
where the prime on the product means that the redundant $`\delta `$’s are omitted.

Consider consequences of taking a more simple expression for $`\delta _{\mathrm{cont}}`$. For example, take in (13) only the primed product of $`\delta `$-functions and only slightly change it according to the recipe (12) at $`k`$ = 1 considering argument of each $`\delta `$-function there as discontinuity of the induced 1-metric (the length squared) across the 1-face (the link). Correspondingly, multiply each function by $`s_{\sigma ^1}`$. Consider the star of a given link $`\mathrm{O}^{}\mathrm{O}`$, i. e. Fig. 1 in 3D language. The eq. (9) turns out to be multiplied by $`(T1)`$-th power of $`s_{\mathrm{O}^{}\mathrm{O}}`$, $`T`$ being the number of the 4-simplices containing this link. Upon integrating out the $`\delta `$-functions we are left with the factor

$$s_{\mathrm{O}^{}\mathrm{O}}^{T1}\mathrm{d}s_{\mathrm{O}^{}\mathrm{O}}$$
(14)
in the measure corresponding to the $`s_{\mathrm{O}^{}\mathrm{O}}`$-dependence. Suppose the partial integration in the functional integral over $`\mathrm{d}s_{\mathrm{O}^{}\mathrm{O}}`$ is made, and we are interested in the dependence on the distance between any two neighbouring vertices, say A and B, in the star of our link. Confluence of these two vertices together will lead to changing the index in (14) by $`2`$. That is, there is discontinuity at the point $`s_{\mathrm{AB}}`$= 0. This contradicts to our assumption on Regge links aspurely triangulation objects on some smooth background metricsince then tending A to B would be smooth process.

This ”no-go” example advises to view our result (13) from a more general position. The issuing point are already discussed $`\delta `$-factors of the type of (12) invariant w.r.t. changing the form of the $`k`$-face. For a given $`k`$-face $`\sigma ^k`$ these factors can differ by the choice $`i`$ = 1, …, $`n_k`$ of the 3-face $`\sigma ^3`$ = $`\sigma _i^3(\sigma ^k)`$ $``$ $`\sigma ^k`$ across which discontinuity of the metric is defined. As we have discussed just now, the number of such factors per $`k`$-face $`n_k`$ should be fixed not depending on the neighbourhood of the $`k`$-face, and general form of $`i`$-th factor for all the $`k`$-faces looks like

$$\delta _{ik}=\underset{\sigma ^k}{}V_{\sigma ^k}^{k+1}\delta ^{k\frac{k+1}{2}}(\mathrm{\Delta }_{\sigma _i^3(\sigma ^k)}S_{\sigma ^k}),$$
(15)
$`i`$ = 1, …, $`n_k`$, $`n_3`$ = 1 of which the overall factor is constructed,

$$\delta _{\mathrm{cont}}=\delta _{13}^{\epsilon _{13}}\underset{i=1}{\overset{n_2}{}}\delta _{12}^{\epsilon _{12}}\underset{i=1}{\overset{n_1}{}}\delta _{i1}^{\epsilon _{i1}}$$
(16)
where $`\epsilon _{ik}`$ are some integers. These integers being larger than 1 or negative may have sense if, as above, upon formal cancellation of the $`\delta `$’s in the numerator and denominator we come to the well defined expression which in this case should take the form

$$\delta _{\mathrm{cont}}=\left(\underset{\sigma ^3}{}V_{\sigma ^3}^4\right)^{\epsilon _{13}}\left(\underset{\sigma ^2}{}V_{\sigma ^2}^3\right)^{_{i=1}^{n_2}\epsilon _{i2}}\left(\underset{\sigma ^1}{}V_{\sigma ^1}^2\right)^{_{i=1}^{n_1}\epsilon _{i1}}\underset{\sigma ^1,\sigma ^3\sigma ^1}{\overset{}{}}\delta (\mathrm{\Delta }_{\sigma ^3}s_{\sigma ^1}).$$
(17)
Original number of the length variables associated to the link is the number of the 4-simplices in the star of the link or the number of the triangles $`T`$ on the 2-sphere Fig. 1. The final number of the variables with taking into account $`\delta `$-functions should be 1,

$$TL\epsilon _{13}P\underset{i=1}{\overset{n_2}{}}\epsilon _{i2}\underset{i=1}{\overset{n_1}{}}\epsilon _{i1}=1.$$
(18)
Comparing this to the Euler characteristic equation for the 2-sphere we return to the eq. (13).

This discussion admits extension to arbitrary spacetime dimensionality $`d`$, here without rigorous topological proof, however. The formula (13) is naturally generalised to

$$\delta _{\mathrm{cont}}^{(d)}=\delta _{d1}^{(d)}(\delta _{d2}^{(d)})^1\delta _{d3}^{(d)}\mathrm{}(\delta _1^{(d)})^{(1)^d}$$
(19)
where

$$\delta _k^{(d)}=\underset{\sigma ^k}{}V_{\sigma ^k}^{k+1}\delta ^{k\frac{k+1}{2}}(\mathrm{\Delta }_{\sigma ^{d1}(\sigma ^k)}S_{\sigma ^k}).$$
(20)
This form ensures the required number 1 of the independent length variables per link upon taking into account the $`\delta `$-functions. Indeed, let $`N_k^{(d)}(\sigma ^1)`$ denotes the number of $`k`$-simplices containing the link $`\sigma ^1`$. Then the considered number of the independent length variables being read off from (19) is

$$N_d^{(d)}(\sigma ^1)N_{d1}^{(d)}(\sigma ^1)+\mathrm{}+(1)^dN_2^{(d)}(\sigma ^1)+(1)^{d+1}.$$
(21)
At the same time $`N_k^{(d)}(\sigma ^1)`$ can be viewed as the number of $`(k2)`$-simplices on the surface of the star of the link $`\sigma ^1`$ which possesses topology of the $`(d2)`$-sphere, and (21) is just topology invariant, namely, Euler characteristic for the $`(d2)`$-sphere minus 1 , i. e. just 1.

Thus, the assumption that in quantum theory Regge calculus is a kind of state of a more general quantised system where discontinuous metrics are allowed leads, in the natural physical assumptions of positivity and nonsingularity in the continuum limit, to the unique version of the Regge calculus quantum measure. Universality of the result is also seen from extendability to the arbitrary spacetime dimensionality and from the deep connection with the (local) topological properties of the spacetime.

The result obtained can be applied to the area Regge calculus. (The quantum measure in this theory can be identically rewritten by inserting some $`\delta `$-functions as the measure in the theory of discontinuous metrics.) A particular feature of the phase factor $`\delta _{\mathrm{cont}}`$ is that it is invariant w.r.t. the overall rescaling linklengths. Therefore one can think that cutoff properties of the original area Regge calculus measure at small or large distances hold also for the usual (length-based) Regge calculus measure obtained with the help of the present construction, and finite expectation values of areas  would mean also finite expectation values of the linklengths .

Another application is to the ordinary Regge calculus action,

$$\underset{\sigma ^2}{}V_{\sigma ^2}\phi _{\sigma ^2}.$$
(22)
Here angle defect $`\phi _{\sigma ^2}`$ is defined by the dihedral angles of separate 4-simplices $`\sigma ^4`$ containing $`\sigma ^2`$ and naturally extends to the case of discontinuous metric when separate 4-simplices become completely independent. Also the area $`V_{\sigma ^2}`$ can be treated as area of any of the 4-simplices containing $`\sigma ^2`$. Thus, (22) can be extended in many ways to the discontinuous metric so that it becomes a sum of independent terms referred to separate 4-simplices. It is natural to write down quantum measure for such the ultralocal system as the product of the measures for separate 4-simplices. Since there is one-to-one correspondence between the number of the linklengths of a 4-simplex $`\sigma ^4`$ and the number of the components of the metric $`g_{\lambda \mu }`$ = $`const`$ inside $`\sigma ^4`$, there is also correspondence between possible 4-simplex measures and possible local measures at a point in the continuum theory. Thereby quantisation of the action (22) in the framework of our approach is formally defined, and the question is whether contours of integration in the path integral exist such that it would converge as in the quantised area Regge calculus model mentioned above.

The present work was supported in part by the Russian Foundation for Basic Research through Grant No. 03-02-17612, through Grant No. 00-15-96811 for Leading Scientific Schools and by the Ministry of Education Grant No. E00-3.3-148.


text:
# Optical Limits on Precursor Emission from Gamma-Ray Bursts with Known Redshift

## 1 Introduction

Constraints on the character and occurrence of precursor emission from gamma-ray bursts (GRBs) offer insight into the nature of the explosions. On timescales of hours to seconds before a burst, precursor emission could occur from the central engines themselves, by, for example, blackbody emission from the early fireball (Li & Paczyński, 1998; Lloyd & Petrosian, 1999; Lyutikov & Usov, 2000; Daigne & Mochkovitch, 2002) or a pre-fireball created in the merger of neutron stars (Rosswog & Ramirez-Ruiz, 2002). If GRBs were to occur from stellar disruption around a massive black hole (Carter, 1992), then thermal precursors ($`T50`$ eV) which decay as power-laws (e.g., Li et al., 2002) might be expected if other stars are disrupted by the same black hole.

If GRBs arise from the death of massive stars, the progenitor star (or its companion, if the progenitor is in a binary system) could produce precursor emission in the form of novae or supernovae (SNe). A precursor SN is a generic prediction of the so-called “supranova” scenario (Vietri & Stella, 1998, 1999). In the supranova scenario, a massive stellar progenitor explodes to produce an SN, leaving behind a supermassive spinning neutron star. The neutron star eventually collapses to form a black hole and a GRB. Vietri & Stella (1998) posited the supranova picture as a means to pre-evacuate the space around the GRB explosion and avoid baryonic contamination to the relativistic blastwave. Aside from this theoretical consideration, the supranova scenario is attractive for two observational reasons. First, the sequence of events in this scenario is a natural means to explain transient X-ray features attributed to dense sub-relativistic matter streaming away at distance of $`10^{14}`$–1017 cm from the explosion site (e.g., Piro et al., 2000; Amati et al., 2000; Reeves et al., 2002). Second, the gas behind the SN shock can be thermalized by the time the GRB fireball sweeps through, leading to an apparent constant density medium in afterglow modeling (Königl & Granot, 2002; Inoue et al., 2003). This would then explain why GRBs from massive stars would typically not show evidence for a wind-blown medium surrounding most bursts (e.g., Chevalier & Li, 1999; Panaitescu & Kumar, 2001). While the significance of some of the X-ray features has been questioned (e.g., Rutledge & Sako, 2003) and winds are generally not ruled out statistically through afterglow modeling (Panaitescu & Kumar, 2001), the possibility of a precursor SN on timescales of days (Davies et al., 2002) to years is a prime motivation to search for precursor emission from GRBs.

As summarized in Hudec et al. (1994), archival photographic plate searches (e.g., Schaefer, 1983) for optical precursors (in the context of recurrence of counterpart emission) revealed only a few genuine astrophysical sources, with no definitive establishment of a physically-associated precursor to any GRB. Using pre-images of the fields of seven Burst and Transient Source Experiment (BATSE) GRBs from the Explosive Transient Camera, Krimm et al. (1996) found no precursors to $`V6`$ mag. Greiner et al. (1995) presented eight upper limits to precursor emission, at $`V=1113`$ mag, within 12 hrs preceding BATSE bursts. Had a genuine transient been found before a GRB, the large GRB error boxes (typically much larger than tens of sq. arcminutes) would have required an association based upon probabilistic arguments. Since the chance for unrelated transients to occur in GRB error boxes is non-negligible, the large BATSE error boxes all but prevented an unambiguous association with the GRBs themselves.

Since 1997, over forty GRBs have been localized to the sub-arcsecond level by way of transient afterglow emission. This, coupled with the growing number of large-area survey projects ($`>\pi `$ steradian), dramatically increases the likelihood of deep pre-imaging of GRB positions. Pre-imaging from near-Earth asteroid surveys allowed Gal-Yam et al. (2002) to show that the transient optical source SDSS J124602.54+011318.8 was not an orphan afterglow (Vanden Berk et al., 2002), but instead was a rare class of AGN. Recently, Heyl (2003) suggested that with an increased frequency of GRB localizations from Swift (Gehrels, 2000) and very deep large-field optical imaging surveys such as the Sloan Digital Sky Survey (SDSS; York et al. 2000) and PanSTARRS (Kaiser & PanSTARRS Team, 2002), constraints could routinely be placed on SN (or, more generally, SN-like) precursors to GRBs.

Other than progenitor scenarios where a SN precedes a GRB, we stress that few models exist that make specific predictions (e.g., of light curves, spectra, start times relative the GRB) for precursor emission. To this end, we have undertaken an exploratory study of public pre-imaging to search for any optical precursor transients at GRB positions. Here, we present pre-imaging observations of 11 GRBs. By focusing on those bursts with known redshift we can translate the derived upper limits into absolute magnitudes in co-moving time. In most bursts, the upper limit to optical precursor emission is $``$3–5 magnitudes brighter than the brightest supernovae known, but comparable to afterglow brightnesses. These derived upper limits are consistent with the known (fainter) brightnesses of the respective GRB host galaxies, later found at the transient positions.

## 2 Observations and Analysis

Most of the pre-imaging data presented herein were obtained by the NEAT program (Pravdo et al., 1999). From December 1995 to February 1999, the NEAT camera was mounted on the 1-m GEODSS telescope in Haleakala, Maui, Hawaii. From February 2000 onward, the camera was then mounted on the Maui Space Surveillance Site (MSSS) 1.2-m telescope. Another NEAT camera began operation on the Oschin 48 inch Schmidt telescope at Palomar Observatory. Briefly, the NEAT imager on Palomar consists of three 4080 $`\times `$ 4080 1.0′′/pixel CCD arrays covering approximately 1.13 $`\times `$ 1.13 deg2. Typical exposure times are 20–60 seconds and the images are unfiltered, giving a broad spectral response from 4000–9000 Å. A 60 second exposure reaches $`V1921`$ mag (3 $`\sigma `$), depending on sky brightness. We also examined the Digital Sky Survey II (DSS-II) scans of the photographic Palomar Sky Survey (Lasker et al., 1998).

For the 30 GRBs with a known redshift, we queried the public NEAT data archive111See http://skyview.gsfc.nasa.gov/skymorph/; Pravdo et al. (1998), retrieving all data which predated the respective burst trigger date. Imaging data for 11 GRBs were found in the NEAT archive, all with at least one epoch of high enough quality to produce good photometry. The amount of available data for each GRB ranged from 3 to 80 individual 8$`\times `$ 8 images with exposure times between 20 sec and 150 sec. The data for each GRB were first aligned with sub-pixel accuracy to the same astrometric grid using bi-linear interpolation. A triangle matching algorithm was used to determine a transformation between each frame and a common reference image by taking into account translation, rotation, and magnification. A WCS astrometric solution was fit to the aligned images using reference stars from the USNO-A2.0 astrometric catalog starting from the approximate center-of-field and plate scale. The photometric zeropoint for each image was estimated in the $`R`$\- and $`B`$-band by comparison with the magnitudes given in the USNO-A2.0. While the photometric errors on individual catalog magnitudes is large ($`0.25`$ mag), a number of stars typically larger than 100 was utilized in order to accurately derive the photometric zeropoint for each frame. The individual images were photometered at the known position of the OT using apertures of radius $`1.2\times `$FWHM of the seeing (Howell, 1989) and local sky subtraction based on an annulus of radii 15 and 30 pixels. Photometric limits were estimated for each image by analyzing the histogram of flux in 1500 apertures of radius $`1.2\times `$FWHM of the seeing placed randomly within the image. Iterative sigma clipping was used to reject flux values contaminated by stars in order to determine the errors due to the sky background. The standard deviation of the Gaussian distribution of the sky background aperture flux values was used with the previously determined photometric zeropoint to estimate the photometric upper limits for each image. The aperture fluxes were measured at the OT position in both the individual epoch images and the stacked images. Tables 2 and 1 summarize the upper limits for all the NEAT imaging. A subset of the NEAT data on four of these bursts have been presented previously (Wood-Vasey et al., 2002; Wood-Vasey, 2002, 2003a; Wood-Vasey et al., 2003). Our photometric measurements of the same data agree with those reports to within 0.5 mag.

Figure 1 shows the stacked preimages of the individual fields surrounding all 11 GRBs. Before making a stacked image of a given field, individual exposures are visually inspected for the presence of defects near the known position of the burst and excluded if defects or cosmic-rays are found. We photometered the 11 stacked images at the position of the GRB and find the $`R`$-band upper limits presented in Table 1 and for individual epochs in Table 2. We report $`3\sigma `$ upper limits on the photometry of the individual epoch images and $`2\sigma `$ upper limits for the stacked images. At this level we statistically expect to have no false positive detections for the stacked images and at most a few false-positives in the individual epoch photometry. The histogram of the rms-normalized individual epoch flux measurements is shown in Figure 3. The expected distribution from purely Gaussian errors is also plotted. This figure indicates that our estimations of the photometric errors are reasonably accurate, with a tendency to over estimate local sky values, leading to a greater number of negative flux values. A single epoch detection at the $`5\sigma `$ level shown in Figure 3 is attributed to an observation in very poor seeing of GRB 020813. The OT position for this GRB is in a crowded region with several bright stars within a few NEAT pixels making accurate photometry very difficult in poor seeing. We find upper limits consistent with the known fainter brightness of the GRB host galaxies.

## 3 Results

As seen in Table 1, there are no significant detections of precursor emission at the positions of the 11 GRBs for which a search was conducted. To place this in the context of physically meaningful quantities, we translate the upper limits to an approximate absolute magnitude in the restframe $`B`$-band using a cosmological $`k`$-correction. This $`k`$-correction is derived assuming an intrinsic source spectrum of $`f_\nu (\lambda )\lambda ^{+1}`$, which approximates the typical median $`B`$-$`R`$ colors of the photometric calibration objects in the GRB fields (in §3.1.2, we vary this assumed precursor spectrum). We use the zeropoints, zpB,R, and effective wavelengths, $`\lambda _{B,R}`$, of the photometric bandpasses from Fukugita et al. (1995). We convert the extinction corrected upper limit, $`m_R`$, in the $`R`$-band to absolute magnitude in the $`B`$-band, as

$$M_B(z)m_RDM(z)2.5\mathrm{log}\left(\frac{\mathrm{zp}_R}{\mathrm{zp}_B}\frac{\lambda _B(1+z)}{\lambda _R}\right)2.5\mathrm{log}(1+z),$$

where $`DM(z)`$ is the distance modulus to the burst at redshift $`z`$, computed assuming $`H_0=65`$ km s-1 Mpc-1, $`\mathrm{\Omega }_m=0.3`$, and $`\mathrm{\Omega }_\mathrm{\Lambda }`$ = 0.7. The third term accounts for the assumed spectrum of the precursor and the last term accounts for the intrinsically smaller bandpass in the restframe. We also find $`M_B(z)`$ by using the equivalent $`B`$-band upper limits and average the two results. Since the NEAT spectral response is broad and the intrinsic precursor spectrum is unconstrained, we expect the systematic uncertainty in the subsequent $`M_B`$ measurements to be at least $``$ 0.3 mag, and probably greater for the higher redshift bursts. If the precursor spectra are significantly more red (blue) than $`f_\nu (\lambda )\lambda ^{+1}`$, then the quoted upper limits will be systematically too deep (shallow), especially for bursts at high redshift.

Figure 4 shows the aggregate absolute magnitude upper limits from the 11 bursts with pre-imaging from NEAT and the DSS-II. The observation time before the burst is given in the co-moving frame of the host galaxies, i.e., the time-dilation has been removed by dividing the observed time by (1 + $`z`$). Our limits are supplemented with a few others from the literature (shown as unfilled symbols). The early upper limit on GRB 030329 (5.6 hours before the burst) is from the RAPTOR experiment (Vestrand et al., 2003; Wren & Vestrand, 2003). The other limits are 030329 (Wood-Vasey et al., 2003), 030226 (Wood-Vasey, 2003b), and 021211 (Wood-Vasey, 2002). The deepest limit on GRB 030329 was reported by Wood-Vasey et al. (2003) from NEAT imaging, but we were unfortunately unable to find such images in the archive to confirm the result. In addition, a 3 minute exposure at the position of GRB 030226 was obtained by Castro-Tirado et al. (2003) using the BOOTES experiment (Castro-Tirado et al., 1999) starting 1.5 minutes before the burst trigger. The upper limit of $`R11.5`$ mag (not shown in Figure 4) implies any precursor would have been $`M_B>34.6`$ mag at the redshift of that GRB.

### 3.1 Limits on Precursor Emission

#### 3.1.1 GRB 030329

At a redshift of $`z=0.1685`$ (Greiner et al., 2003), corresponding to a distance modulus of $`DM`$ = 39.70 mag, GRB 030329 is the nearest known “cosmological” GRB. Its proximity allowed several groups to study the photometric and spectral properties of the associated supernova with unprecedented detail (Stanek et al., 2003; Chornock et al., 2003; Hjorth et al., 2003; Henden et al., 2003; Kawabata et al., 2003). Though this firm detection of a nearly contemporaneous SN suggests a single event destroyed the progenitor—rendering unlikely the possibility of a similar precursor event—it is still of interest to know what limits can be placed on the occurrence of a similar precursor.

At this redshift, a bright supernova-like precursor \[$`M_B`$(peak) = $`20`$ mag\] would have peaked at $`V19.7`$ mag and could have remained above our nominal single epoch magnitude limit of $`V21`$ mag for $``$2–3 weeks. Since there are temporal gaps in the data, particularly between 30–300 days before the GRB, it is certainly possible that a bright precursor could have been missed by the pre-imaging. However, three upper limits less than 30 days before the burst exclude such a bright SN-like precursor preceding the GRB by $``$45–10 days.

#### 3.1.2 SN-like Precursors

To estimate how restrictive the entire data set is to SN-like precursors, we created a Monte Carlo test by assuming that every GRB in the sample had the same precursor at some random explosion date less than 1000 days before the burst. The working hypothesis is that a GRB with a SN-like precursor would be of type Ib/Ic and so we use SN 1998bw as a template. Owing to the extreme deficit of flux blueward of $``$3000 Å of Ib/Ic SNe, we only use precursor photometry from bursts that originated from $`z<1.2`$. Since SNe generally appear red in $`BV`$, especially after the peak, we recalculated the apparent absolute magnitude limits in Table 2 using a source spectrum with $`f_\nu \lambda ^{2.5}`$. Synthetic SN light curves were created from the $`B`$-band data of SN 1998bw published in Galama et al. (1998) and McKenzie & Schaefer (1999). For a given peak brightness (allowed to vary from $`15`$ to $`35`$ mag) we randomly selected 1000 explosion dates before the GRB and then constructed a set of synthetic light curves, noting the frequency of synthetic precursors brighter than at least one of the detection limits. For simplicity we assumed no correlation in peak brightness with light curve shape.

For two different distributions of starting times, we computed the probability that the precursor would have been found in the NEAT data, taking the ratio of the number of “detected” sources in the Monte Carlo to the total number in the simulation. The result is seen in Figure 5. For uniformly random explosion dates before the GRB, almost all SN-like precursors brighter than (peak) $`M_B25`$ mag would have been detected at some point during the 3 years before the GRBs in the sample. For both preburst SN explosion date distributions, the limits on SNe with 1998bw-like peak magnitudes ($`M_B=18.88`$ mag; McKenzie & Schaefer 1999) is not very strong. Following Figure 5, there is only about 10–30% chance that such SNe would have been detected. Therefore, though there are specific time windows when SNe could not have occurred before the GRBs in the sample, we cannot rule out the possibility that a SN with brightness comparable to 1998bw (or 2003dh) occurred for all GRBs but was missed due to the sparse sampling of the data.

#### 3.1.3 Power-Law Precursors

GRB precursors could, of course, be of a different physical nature than supernovae. We have also tested the detection sensitivity to decaying power-law precursors. We used a model for the flux of the precursor as $`f_\nu (tt_0)^\beta `$ (for $`t>t_0+1`$ day), with the magnitude of the source at one day since $`t_0`$ of $`M_B`$(1 day). As above, we simulated 1000 precursors with a characteristic start time $`t_0`$ less than 1000 days before the GRB set. The spectral index of the precursor was assumed to be $`1`$, for consistency with the conversion of apparent magnitude to absolute $`B`$-band magnitude. For a range of decay indices, $`\beta `$, and $`M_B`$(1 day), we found the probability of detection using the results in Table 2.

Figure 6 shows the results for two different probability distributions of $`t_0`$. The lines of 0.95 and 0.99 show the equivalent windows for detection of most such transients. For example, if all precursors have $`\beta =1`$ and $`M_B`$(1 day) $`=30`$ mag, then there is greater than a 99% chance that the NEAT set would have detected at least one such precursor if it occurred less than 1000 days before the GRB. Precursors that fade more quickly easily evade detection in the sample. For example, only about 5% of precursors with $`M_B`$(1 day) $`20`$ mag and $`\beta <1.5`$ would be detected in the current sample. Thus, there is little constraint on the existence of faint precursors generated from tidal disruption around a massive black hole ($`\beta =5/3`$; Li et al. 2002).

It is of interest to compare the brightness sensitivity of power-law precursors to known afterglow brightnesses. Following from the GRB 030329 afterglow measurement of Fitzgerald & Orosz (2003) and the extinction measurement in Bloom et al. (2003b), the restframe extinction corrected $`B`$-band magnitude of the afterglow was $`M_B`$(1 day) $`23.7`$, fairly typical of other long-duration GRBs. Though there were deviations from a power-law, the secular decay after 0.5 days was approximately $`\beta =2`$ (Price et al., 2003). Following from Figure 6, had a precursor – perhaps of a similar physical origin as GRB afterglows (a ”foreglow”) – with the same parameters occurred for all bursts at some time less than 1000 days before the GRB, there is only a 50% chance that such precursors would be seen in the NEAT imaging.

## 4 Discussion and Conclusions

The non-detection of at least some power-law precursors—at magnitudes comparable to afterglow brightnesses—supports the notion that GRBs are due to explosive catastrophic events rather than due to recurrent activity (e.g., from an AGN, Gal-Yam et al. 2002). For consistency with all the limits presented herein, precursor theories must now posit optical precursor emission fainter than $`M_B25`$ mag ($`t_{\mathrm{obs}}t_{\mathrm{GRB}}<1`$ day). From the analysis in §3, we can also rule out the possibility that SN-like precursors with $`M_B`$(peak) $`<25`$ and explosion dates less than 1000 days after the bursts occurred for all GRBs in the sample. Likewise, we exclude the possibility that all GRBs in the sample had a precursor with $`M_B`$(1 day) $`<25`$ and a slowly fading ($`\beta <1`$) power-law light curve. It is possible that a subset of GRBs had precursors at least this bright. While providing the strongest comprehensive precursor limits thus far, despite the nearly 200 photometric pre-imaging measurements of 11 GRBs, the NEAT data are not very sensitive to realistic precursor brightnesses. Even if all GRBs had extremely bright \[$`M_B`$(peak) $`20`$\] SN-like precursors, these would have been missed with an $``$80% probability. Similarly, more than half of precursors with similar power-laws and brightnesses as GRB afterglows would have been missed. Figure 7 shows how various precursors could have been detected or could have evaded detection.

Since GRB hosts are known to be forming stars vigorously, novae and SNe should not be uncommon in such hosts. If the star-formation rate in a GRB host is 40 $`M_{}`$ yr-1 then the canonical SN rate is about 1 yr-1 from somewhere within the host. At spatial resolutions of $`12`$ arcseconds (such as from NEAT), the best astrometric localizations of a precursor should be $`200`$ milliarcseconds ($`1`$-$`\sigma `$). This corresponds to a 3-$`\sigma `$ localization uncertainty 4 kpc in projection at a redshift of $`z=0.5`$, larger than the exponential scale lengths of all GRB hosts measured to-date (Bloom et al., 2002). Therefore, any precursor emission could be easily confused with an unrelated SN somewhere in the host (this essentially extends the confusion problem encountered by plate archive studies from the arcminute to the sub-arcsecond level). This disturbing possibility motivates the additional need for high spatial resolution in pre-imaging surveys. To this end, future deep wide-field imaging surveys, such as PanSTARRS, should be sufficient: a precursor detected with a signal–to–noise of 30 at the Nyquist-sample resolution of PanSTARRS (0.6′′) will result in a positional confusion about 100 times smaller than with NEAT. This means that if PanSTARRS detects an apparent precursor to a GRB within the host galaxy (say one year before the burst), a significant association with the GRB itself should be possible for even the most vigorously star forming host galaxies.

The quality and quantity of “pre-observations” of transient locations will dramatically improve with the increasing size of the National Virtual Observatory222See http://www.us-vo.org/. Digital imaging surveys, such as RAPTOR (Vestrand et al., 2003) and BOOTES (Castro-Tirado et al., 1999), have already presented limits acquired a few hours before bursts to the $`R`$ 12–15 mag level (e.g., Castro-Tirado et al., 2003; Wren & Vestrand, 2003). Deeper surveys such as SDSS should be searched systematically for pre-imaging observations of GRB locations. Identification of precursors with SDSS will have the added benefit of color information, yielding important clues about the physical nature of precursors, should any be detected.

The higher localization rates of Swift will increase the likelihood of deeper pre-imaging with the next generation of large-area surveys (Heyl, 2003). With the advent of large synoptic imaging programs (LSS and PanSTARRS), with the primary science goals to detect near-earth asteroids, the deepest and most frequent imaging will be at low ecliptic latitudes. This observing strategy will be well-matched to satellite missions like HETE-II (Ricker et al., 2002) which preferentially localize GRBs anti-solar. Thus, the rates of deep pre-imaging may be higher than those predicted by Heyl (2003). If some sub-population of bursts originate from within the Galaxy or in the local group (such as, potentially, short bursts and supernovae-GRBs), then, as has been demonstrated with a handful of SNe (see Van Dyk et al. 2003), space-based pre-imaging might someday retroactively resolve the progenitors directly.

We are exceedingly gratefully to the NEAT team (S. Pravdo, D. R. Rabinowitz, E. F. Helin, K. Lawrence, T. McGlynn, L. Angelini, and N. White) for making images public and so readily accessible. Without their dedication to this wonderful experiment and user-friendly archive, none of this work would be possible. We thank S. Kulkarni for bringing to our attention a concern from P. Kumar about the possibility of misidentifying the origin of an SN bump after a GRB, due to confusion with unrelated supernovae in the host galaxies; our discussion of precursor confusion follows from that concern. We would also like to thank S. Kulkarni, B. Paczyński, and D. Fox for helpful comments on the manuscript. J.S.B. is supported by a Junior Fellowship to the Harvard Society of Fellows and by a generous research grant from the Harvard-Smithsonian Center for Astrophysics. C.B. would like to thank the Berkeley DEEP team for their hospitality during the completion of this work. We thank our physics teacher at Bethlehem Central High School, Mr. Neff. We would also like to thank an anonymous referee for their excellent suggestions for improvements to our original manuscript.


text:
# Optimal realization of the transposition maps

## 1 Introduction

The formulation of no-go theorems in quantum information has given new insight in the structure of the quantum theory itself. The most relevant examples are given by the no-cloning , no-broadcasting , no-deleting  theorems, along with the impossibility of measuring the wave-function of a single system , and the debated quantum bit-commitment .

A transformation which is not allowed by quantum mechanics naturally poses the problem of investigating about the best approximation that one can achieve in principle. Remarkably, the optimal approximation of a forbidden transformation may be related to the optimal procedure to perform some information tasks. For example, universal cloning is deeply related to the optimal eavesdropping in cryptographic channels . Moreover, one can infer from the structure of the optimal approximation of unphysical maps a number of properties about different topics in quantum mechanics, such as state estimation  and signaling .

In this Letter we provide the optimal approximation of the transposition for pure states both in finite and infinite dimensional Hilbert spaces. Transposition—in particular, partial transposition—plays a major role in separability criteria for bipartite states . It is the simplest example of a positive map, which is not completely positive. In fact, such a map is antilinear and for qubits it is related to the more familiar $`U`$-not transformation that maps any arbitrary state to its orthogonal. Of course, for systems with higher dimension the $`U`$-not map is not uniquely defined, because more than one state is orthogonal to a given one, whereas the transposition map depends on a choice of basis.

The paper is organized as follows. In Sec. II we derive the optimal transposition map for pure states in terms of fidelity for the case of arbitrary finite dimensional Hilbert spaces. The derivation is obtained by means of group representation theory. In Sec. III we give explicitly a unitary realization of the optimal map for any dimension. Such a unitary realization provides also the optimal quantum cloning from one to two copies. This result proves that the recent experimental scheme proposed in Ref. , where the optimal $`U`$-not and two optimal clones are created for qubits simultaneously by the same machine, can be generalized to quantum systems with arbitrary dimension. Section III is devoted to the continuous variables case. Similarly, as for the cloning map, one has to restrict the covariance group under which the map is universal. We consider the case of Weyl-Heisenberg group, which provides the optimal transposition map for coherent and squeezed states.

## 2 Optimal transposition for finite dimension

It is well known that the transposition map

$$\rho \rho ^T$$
(1)
is not physical since it is not completely positive (CP). As stated in the introduction the problem naturally arises to find the optimal physical. i.e. CP map $``$ whose output has maximal fidelity with the transposed input. We consider pure input states, for which the fidelity writes

$$F=\mathrm{Tr}\left[\rho ^T(\rho )\right].$$
(2)
We settle here some useful notation that will be used along the paper. A generic vector in the bipartite Hilbert space $``$, with $`\text{dim}()=d`$, can be expanded on a fixed factorized orthonormal basis as $`_{i,j=1}^d\mathrm{\Psi }_{ij}|i|j`$. This naturally defines a one to one correspondence between vectors in $``$ and linear operators in $`()`$. The operator $`\mathrm{\Psi }=_{ij}\mathrm{\Psi }_{ij}|ij|`$ can be used to label the state as follows

$$|\mathrm{\Psi }=\underset{i,j=1}{\overset{d}{}}\mathrm{\Psi }_{ij}|i|j.$$
(3)
In this framework one can easily verify the useful identities

$`AC|B=|ABC^T,`$
$`\mathrm{Tr}_1[|AB|]=A^TB^{},`$
$`\mathrm{Tr}_2[|AB|]=AB^{},`$ (4)
where $`T`$ and $``$ denote transposition and complex conjugation with respect to the orthonormal basis $`\{|i\}`$. The set of possible maps $``$ can be parametrized using the isomorphism  between CP maps and positive operators

$`R_{}=|II|,`$
$`(\rho )=\mathrm{Tr}_2[(I\rho ^T)R_{}].`$ (5)
Using Eq. (5), the expression for the fidelity writes

$$F=\mathrm{Tr}[(\rho ^T\rho ^T)R_{}],$$
(6)
where $`R_{}`$ is a positive operator that satisfies the constraint

$$\mathrm{Tr}_1[R_{}]=I_2,$$
(7)
because of the trace-preserving condition of the map $``$. We pose the further constraint that $``$ is universal, namely that it is covariant under the action of the group $`\mathrm{SU}(d)`$. On physical grounds this means that we restrict attention to maps that equally well approximate the transposition, independently of the input pure state. The covariance property for the transposition map reads

$$(U\rho U^{})=U^{}(\rho )U^T,U\mathrm{SU}(d),$$
(8)
and this is equivalent to the following condition on $`R_{}`$

$$(U^{}U^{})R_{}(U^TU^T)=R_{}.$$
(9)
Since for $`\mathrm{SU}(d)`$ the representation $`U^{}U^{}`$ can be decomposed into two inequivalent irreducible representations supported by the totally symmetric and totally antisymmetric subspaces of $``$, according to Schur’s lemma, condition (9) implies the following form for $`R_{}`$

$$R_{}=c_AP_A+c_sP_S.$$
(10)
The operators $`P_S`$ and $`P_A`$ are the projectors on the totally symmetric and totally antisymmetric spaces, respectively, and can be written as

$`P_S={\displaystyle \frac{1}{2}}(I+E),`$
$`P_A={\displaystyle \frac{1}{2}}(IE),`$ (11)
where $`E`$ denotes the swap operator on $``$, namely $`E|\varphi |\psi =|\psi |\varphi `$ for all $`\varphi ,\psi `$. The trace-preserving condition in Eq. (7), along with the positivity constraint rewrite

$`c_S{\displaystyle \frac{d+1}{2}}+c_A{\displaystyle \frac{d1}{2}}=1,`$
$`c_S,c_A0.`$ (12)
Due to the covariance condition, the fidelity F is independent of the input state $`\rho `$. Using Eq. (10) one has

$$F=c_S\mathrm{Tr}[(\rho ^T\rho ^T)P_S]+c_A\mathrm{Tr}[(\rho ^T\rho ^T)P_A]=c_S.$$
(13)
Upon maximizing $`c_S`$ with the constraints in Eq. (12), the optimal map is obtained for

$$c_S=\frac{2}{d+1},c_A=0.$$
(14)
Correspondingly, one has $`R_{}=\frac{2}{d+1}P_S`$, and hence

$$(\rho )=\frac{2}{d+1}\mathrm{Tr}_2[(I\rho ^T)P_S]=\frac{1}{d+1}(I+\rho ^T).$$
(15)
The optimal fidelity is then given by

$$F=\frac{2}{d+1}\mathrm{Tr}[(\rho ^T\rho ^T)P_S]=\frac{2}{d+1}.$$
(16)
The state in Eq. (15) coincides with the anticlone state of Ref.  for the universal cloning machine from one to two copies. Moreover, the map $``$ is the same as the “structural physical approximation” of the transposition of Ref. . Here, we proved the optimality of $``$ without assumptions, thus also showing that the anticlone corresponds to the optimal transposed state.

A Kraus decomposition of the map $``$ can be obtained by diagonalizing $`R_{}`$ as follows

$`R_{}={\displaystyle \frac{1}{d+1}}(I+E)={\displaystyle \frac{1}{d+1}}{\displaystyle \underset{mn}{}}(|mm||nn|+|mn||nm|)`$
$`={\displaystyle \frac{1}{2(d+1)}}{\displaystyle \underset{mn}{}}(|mn+|nm)(mn|+nm|)={\displaystyle \underset{mn}{}}|M_{mn}^SM_{mn}^S|,`$ (17)
where $`M_{mn}^S=\frac{1}{\sqrt{2(d+1)}}(|mn|+|nm|)`$. The Kraus decomposition is then given by

$$(\rho )=\underset{mn}{}M_{mn}^S\rho M_{mn}^S.$$
(18)
A Stinespring form of the map $``$ can be written for an ancilla in the Hilbert space $`^2`$ as follows

$$(\rho )=\mathrm{Tr}_{23}[V\rho V^{}],$$
(19)
where $`V`$ denotes the isometry

$$V=\underset{mn}{}M_{mn}^S|mn_{23}.$$
(20)
We can verify that $`V`$ is also an isometric extension for the realization of the optimal universal cloning from $`1`$ to $`2`$ copies. In fact, upon tracing out the system $`1`$, one obtains the optimal cloning map in the Werner expression

$$𝒞(\rho )=\mathrm{Tr}_1[V\rho V^{}]=\frac{2}{d+1}P_{S_{23}}(I_2\rho _3)P_{S_{23}}.$$
(21)
This result also shows that the recent experimental scheme proposed in Ref. , where the optimal $`U`$-not and two optimal clones are created for qubits simultaneously by the same machine, can be generalized to quantum systems with arbitrary dimension. Notice that the cloning map is basis independent, whereas the transposition map depends on the choice of the basis, which is reflected by the particular Stinespring extension.

In the following we explicitly derive a unitary realization of the optimal map in Eq. (15).

## 3 Unitary realization

The isometry in Eq. (20) provides the optimal universal transposition map or the optimal universal cloning from one to two copies, by tracing over the ancilla spaces 2 and 3 or the input space 1, respectively. Starting from the isometry $`V`$, we look for a unitary interaction $`U`$ between the system and a fixed preparation of the ancilla that dilates $`V`$. For the explicit construction of the unitary dilation $`U`$, we will follow the general framework of Ref. .

First, notice that we can rewrite Eq. (20) as

$`V`$ $`=`$ $`\sqrt{{\displaystyle \frac{2}{d+1}}}{\displaystyle \underset{m,n=0}{\overset{d1}{}}}|m{\displaystyle \frac{|m|n+|n|m}{2}}n|`$ (22)
$`=`$ $`\sqrt{{\displaystyle \frac{2}{d+1}}}{\displaystyle \underset{m,q=0}{\overset{d1}{}}}|m{\displaystyle \frac{|m|mq+|mq|m}{2}}mq|`$
$`=`$ $`\sqrt{{\displaystyle \frac{2}{d+1}}}\left(V_{0,0}+{\displaystyle \frac{1}{\sqrt{2}}}{\displaystyle \underset{q=1}{\overset{d1}{}}}V_{0,q}^{(S)}\right),`$
where we defined the operators

$`V_{p,p}`$ $`=`$ $`{\displaystyle \underset{k=0}{\overset{d1}{}}}|k|kp|kpkp|,`$
$`V_{p,q}^{(S)}`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{2}}}{\displaystyle \underset{k=0}{\overset{d1}{}}}|k(|kp|kq+|kq|kp)kq|,`$ (23)
with $`pq`$ and $`p,q=0,\mathrm{},d1`$. In order to construct a unitary realization $`U`$, we also define

$$V_{p,q}^{(A)}=\frac{1}{\sqrt{2}}\underset{k=0}{\overset{d1}{}}|k(|kp|kq|kq|kp)kq|.$$
(24)
One can easily verify that

$`V_{p,p}^{}V_{q,r}^{(S)}=V_{p,p}^{}V_{s,t}^{(A)}=V_{q,r}^{(S)}V_{s,t}^{(A)}=0,p,q,r,s,t=0,\mathrm{},d1`$
$`V_{p_1,p_1}^{}V_{p_2,p_2}=\delta _{p_1,p_2}I_{},p_1,p_2,`$
$`V_{q_1,r_1}^{(S)}V_{q_2,r_2}^{(S)}=\delta _{q_1,q_2}\delta _{r_1,r_2}I_{},q_1<r_1,q_2<r_2,`$
$`V_{s_1,t_1}^{(A)}V_{s_2,t_2}^{(A)}=\delta _{s1,t_2}\delta _{s_1,t_2}I_{},s_1<t_1,s_2<t_2,`$ (25)
namely, the three sets $`\{V_{p,p}\}`$, $`\{V_{p,q}^{(S)}\}_{p<q}`$ and $`\{V_{p,q}^{(A)}\}_{p<q}`$ are orthogonal sets of orthogonal isometries. Hence, the following operator

$$U=\underset{p=0}{\overset{d1}{}}V_{p,p}p|p|+\underset{\genfrac{}{}{0pt}{}{p,q=0}{p<q}}{\overset{d1}{}}V_{p,q}^{(S)}\frac{p|q|+q|p|}{\sqrt{2}}+\underset{\genfrac{}{}{0pt}{}{p,q=0}{p<q}}{\overset{d1}{}}V_{p,q}^{(A)}\frac{p|q|q|p|}{\sqrt{2}}$$
(26)
satisfies the unitary condition

$$U^{}U=UU^{}=I_{}(P_{S_{23}}+P_{A_{23}})=I_^3.$$
(27)
The optimal universal transposition map can be obtained as follows

$$(\rho )=\mathrm{Tr}_{2,3}[U(\rho |\varphi \varphi |)U^{}],$$
(28)
where $`|\varphi ^2`$ is the fixed normalized totally symmetric ancilla state

$$|\varphi =\sqrt{\frac{2}{d+1}}P_{S_{23}}\underset{r=0}{\overset{d1}{}}|0_2|r_3.$$
(29)
As noted above, the unitary $`U`$ provides the optimal universal cloning as well, namely one has

$$𝒞(\rho )=\mathrm{Tr}_1[U(\rho |\varphi \varphi |)U^{}].$$
(30)
For qubits, i.e. $`d=2`$, we obtain the network model of Ref. , with

$$U=\left(\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0\end{array}\right),$$
(31)
and $`|\varphi =\frac{1}{\sqrt{6}}(2|0_2|0_3+|0_2|1_3+|1_2|0_3)`$.

## 4 Continuous variables optimal transposition

In the limit of dimension $`d\mathrm{}`$, the fidelity $`F`$ for the universal transposition map goes to zero. However, as regards infinite dimensional systems one can look for transposition maps that are not universal, but covariant just for a group with reduced symmetry. The typical covariance group for infinite dimensional quantum systems is the Weyl-Heisenberg group, in the representation of displacement operators $`D(\alpha )=\mathrm{exp}(\alpha a^{}\alpha ^{}a)`$, with $`\alpha `$, and $`a`$ and $`a^{}`$ being the annihilation and creation operators. The covariant transposition map acts with the same fidelity over any state obtained from a given pure state by application of the displacement operator with arbitrary amplitude. Such a covariance condition reads

$$(D(\alpha )\rho D^{}(\alpha ))=D^{}(\alpha )(\rho )D^T(\alpha ),\alpha ,$$
(32)
which rewrites for the operator $`R_{}`$ as follows

$$[D^{}(\alpha )D^{}(\alpha ),R_{}]=0,\alpha .$$
(33)
The operator $`R_{}`$ can be expanded on the basis of displacement operators, which are a spanning set for Hilbert-Schmidt operators on $``$, namely

$$R_{}=_{}\frac{\mathrm{d}^2\alpha }{\pi }_{}\frac{\mathrm{d}^2\beta }{\pi }r(\alpha ,\beta )D(\alpha )D(\beta ).$$
(34)
The condition in Eq. (33) is then equivalent to

$`{\displaystyle _{}}{\displaystyle \frac{\mathrm{d}^2\alpha }{\pi }}{\displaystyle _{}}{\displaystyle \frac{\mathrm{d}^2\beta }{\pi }}r(\alpha ,\beta )\mathrm{e}^{\gamma (\alpha +\beta )\gamma ^{}(\alpha ^{}+\beta ^{})}D(\alpha )D(\beta )=`$
$`{\displaystyle _{}}{\displaystyle \frac{\mathrm{d}^2\alpha }{\pi }}{\displaystyle _{}}{\displaystyle \frac{\mathrm{d}^2\beta }{\pi }}r(\alpha ,\beta )D(\alpha )D(\beta ),\gamma ,`$ (35)
and this is possible for $`r(\alpha ,\beta )=\pi r(\alpha )\delta ^2(\alpha +\beta )`$, with $`r(\alpha )`$ complex function of $`\alpha `$, thus giving

$$R_{}=_{}\frac{\mathrm{d}^2\alpha }{\pi }r(\alpha )D(\alpha )D^{}(\alpha ).$$
(36)
The trace-preserving condition $`\mathrm{Tr}_1[R_{}]=I_2`$ corresponds to $`r(0)=1`$. Upon introducing the $`50/50`$ beam splitter operator $`V=\mathrm{exp}[\frac{\pi }{4}(a^{}bab^{})]`$, we can write

$$R_{}=V_{}\frac{\mathrm{d}^2\alpha }{\pi }r(\alpha )[D(\sqrt{2}\alpha )I]V^{}\frac{1}{2}V^{}(\xi \text{1}\text{1})V,$$
(37)
and $`R_{}`$ is positive if and only if the following operator

$$\xi _{}\frac{^2\alpha }{\pi }r\left(\frac{\alpha }{\sqrt{2}}\right)D(\alpha )$$
(38)
is positive. Since $`r(0)=1`$, then $`\text{Tr}[\xi ]=1`$, namely $`\xi `$ is a state. For the covariance condition in Eq. (33), the fidelity of the map with the state $`[D(\alpha )\rho D^{}(\alpha )]^\tau `$ is independent of $`\alpha `$ and just depends on the seed $`\rho `$. One has

$$F=\frac{1}{2}\mathrm{Tr}[(\rho ^\tau \rho ^\tau )V(\xi \text{1}\text{1})V^{}].$$
(39)
Equation (39) is linear in $`\xi `$, which lies in a convex set. The maximum fidelity is then achieved by a pure state $`\xi =|\chi \chi |`$, and the optimal map is given by

$$R_{}=\frac{1}{2}V(|\chi \chi |\text{1}\text{1})V^{}.$$
(40)
The vector $`|\chi `$ can be determined as the eigenvector corresponding to the maximum eigenvalue of the state

$$\mathrm{Tr}_2[V^{}(\rho ^\tau \rho ^\tau )V].$$
(41)
The explicit form of the map acting on a general state $`\sigma `$ is given by

$$(\sigma )=\frac{1}{2}\mathrm{Tr}_2[(\text{1}\text{1}\sigma ^\tau )V(|\chi \chi |\text{1}\text{1})V^{}],$$
(42)
and provides the optimal transposition for any pure state. We remind that $`|\chi `$ depends on the seed state $`\rho `$. Notice that for coherent states, namely for $`\rho =|00|`$, the optimal transposed state can be obtained as the anticlone from the optimal covariant cloning from one to two copies , with optimal fidelity $`F=1/2`$, generalizing the result for the finite dimensional case.

## Acknowledgments

This work has been sponsored by INFM through the project PRA-2002-CLON, and by EEC and MIUR through the cosponsored ATESIT project IST-2000-29681 and Cofinanziamento 2002.