text:
# Cartier Isomorphism for Toric Varieties

## 1. Introduction

In \[Car57\], Cartier introduces an operation on the de Rham complex for varieties defined over a field of positive characteristic. In the case of a smooth variety this yields a complete description of the cohomology of the de Rham complex. To formulate the result let $`X`$ be a smooth variety over a perfect field then for all $`a0`$ the Cartier operator

$$C:^𝒶(_{}\mathcal{\Omega }_𝒳^{})\stackrel{}{}\mathcal{\Omega }_𝒳^𝒶$$

is an isomorphism. Here $`F:X\stackrel{}{}X`$ denotes the Frobenius morphism on $`X`$ and $`^𝒶`$ denotes the $`a^{\text{th}}`$ cohomology sheaf of $`F_{}\mathrm{\Omega }_X^{}`$. If the variety is not smooth, not much is known about the properties of the Cartier operator and the poor behaviour of the de Rham complex in this case makes its study difficult. If one substitutes the de Rham complex with the Zariski-de Rham complex the situation is better. For example, the Zariski differentials, though not locally free, are reflexive and there is a natural duality pairing between them.

We show how to extend the Cartier operator in a natural way to the Zariski differentials. Using a description of the Zariski-de Rham complex due to Danilov \[Dan78\] we show that this newly defined Cartier operator is an isomorphism for toric varieties. Moreover, it is induced by a split injection

As described in \[BT97\] such a result yields the Bott vanishing theorem and the degeneration of the Hodge to de Rham spectral sequence for projective toric varieties.

Finally we will give an obstruction to the surjectivity of the Cartier map to show that in general it can not be an isomorphism.

The author would like to thank Karen Smith for invaluable discussions and the referee for a careful reading and valuable comments.

### 1.1. Notation and Generalities

Fix a perfect field $`k`$ of characteristic $`p>0`$. All schemes will be noetherian $`k`$-schemes unless otherwise stated. $`X`$ denotes a noetherian $`k`$-scheme. By an $`𝒪_𝒳`$-module we always mean a coherent sheaf of $`𝒪_𝒳`$-modules.

###### Definition 1.1.

The *absolute Frobenius* of $`X`$ is the endomorphism

$$F_X:XX$$

which is the identity on the level of the topological space and the $`p^{\text{th}}`$ power map on the structure sheaf.

For $`x𝒪_𝒳`$ and $`\lambda k`$ one has $`F_X^{}(\lambda x)=\lambda ^px^p=F_k(\lambda )F_X^{}(x)`$ where $`F_k`$ is just the Frobenius morphism for $`k`$. Thus $`F_X`$ is *not* a morphism of $`k`$-schemes unless $`k=𝔽_p`$. Setting $`X^{}=X\times _{F_k}k`$ we get by the universal property of the fiber product that $`F_X`$ can be factored through $`X^{}`$.

This map is called the relative Frobenius and we simply denote it by $`F:X\stackrel{}{}X^{}`$. Note that as $`𝔽_p`$-schemes $`X`$ and $`X^{}`$ are isomorphic. For an $`𝒪_𝒳`$-module $``$ we denote the pushforward under $`F`$ by $`F_{}`$.

For every map $`\varphi :X\stackrel{}{}Y`$ of noetherian $`k`$-schemes we get a commutative diagram:

This follows by construction of the relative Frobenius as the unique solution to a mapping problem and the fact that we have a square like this for the absolute Frobenius. Thus, in particular, the functor $`F_{}`$ commutes with $`\varphi _{}`$.

For a $`k`$-algebra $`R`$ we adopt the same notation: The (absolute) Frobenius $`F_R:R\stackrel{}{}R`$ is just the $`p^{\text{th}}`$ power map. Setting $`R^{}=R_Fk`$ we get similarly a relative ($`k`$-linear) Frobenius map $`F:R^{}\stackrel{}{}R`$. Again one sees that $`R`$ and $`R^{}`$ are isomorphic as rings, only their $`k`$-algebra structure is different. By $`F_{}M`$ we denote the $`R`$-module $`M`$ viewed as an $`R^{}`$-module via the relative Frobenius.

### 1.2. The smooth case

In this section we will review the construction in the smooth case which we will extend later to the Zariski-de Rham complex on normal varieties.

The object of study is the algebraic de Rham complex $`\mathrm{\Omega }_{X/k}^{}=\mathrm{\Omega }_X^{}`$ (cf. \[EV92\]). The key observation is that the differential on $`F_{}\mathrm{\Omega }_X^{}`$ is $`𝒪_𝒳^{}`$-linear by the Leibniz rule: $`dF^{}(x1)=dx^p=0`$ for all $`x𝒪_𝒳`$. This gives the cohomology objects of the de Rham complex $`^𝒶(_{}\mathcal{\Omega }_{𝒳/𝒮}^{})`$ the structure of $`𝒪_𝒳^{}`$-modules.

###### Proposition 1.2 (Cartier, \[Car57\]).

Let $`X`$ be a noetherian $`k`$-scheme. There is a unique map of $`𝒪_𝒳^{}`$-modules

$$C^1:\mathrm{\Omega }_X^{}^1^\mathcal{1}(_{}\mathcal{\Omega }_𝒳^{})$$

called the *inverse Cartier operator* such that for a local section $`x𝒪_𝒳`$ one has

$$C^1(d(x1))=x^{p1}dx\text{ in }^\mathcal{1}.$$

For all $`a0`$ this $`C^1`$ induces maps

$$\stackrel{a}{}C^1:\mathrm{\Omega }_X^{}^a^𝒶(_{}\mathcal{\Omega }_𝒳^{}).$$

The following result completely describes the cohomology of the de Rham complex on a smooth $`k`$-scheme.

###### Theorem 1.3 (Cartier, \[Car57\], see also \[Kat70\]).

Let $`X`$ be a smooth $`k`$-scheme. Then the inverse Cartier operator is an isomorphism for all $`a0`$. I.e.

$$^𝒶(_{}\mathcal{\Omega }_𝒳^{})\mathcal{\Omega }_𝒳^{}^𝒶.$$

###### Remark 1.4.

The most striking application of the Cartier isomorphism is as the main ingredient of Deligne and Illusie’s algebraic proof of the Kodaira vanishing theorem. For $`X`$ smooth and under an additional assumption ($`X`$ lifts to characteristic $`p^2`$ and $`pdimX`$) they show in \[DI87\] that the inverse Cartier operator is induced by a map

$$\mathrm{\Omega }_X^{}^a[a]\stackrel{}{}F_{}\mathrm{\Omega }_X^{}$$

in the derived category of $`𝒪_𝒳^{}`$-modules. Taking hypercohomology one sees that this implies the degeneration of the Hodge to de Rham spectral sequence $`H^a(\mathrm{\Omega }_X^b)^{a+b}(\mathrm{\Omega }_X^{})`$. Such a result implies the Kodaira vanishing theorem as shown by Esnault and Viehweg in \[EV86\]. For details on this circle of ideas we refer the reader to the original article \[DI87\] and the excellent book \[EV92\].

### 1.3. Reflexive sheaves

In our approach to generalize the Cartier operator reflexive sheaves play a central role. Here we review some properties and for completeness most of the proofs are given, too.

Let $`X`$ be a normal scheme and $``$ be a $`𝒪_𝒳`$-module. We denote the dual of $``$ by $`^{}=𝓂_{𝒪_𝒳}(,𝒪_𝒳)`$. There is a natural map from $``$ to its double dual $`^{}`$ which sends a section $`s`$ to the map $`f_s`$ whose value on the map $`\lambda :\stackrel{}{}𝒪_𝒳`$ is $`f_s(\lambda )=\lambda (s)`$. The module $``$ is called reflexive if the natural map to its double dual is an isomorphism. The module $`^{}`$ is also called the reflexive hull of $``$. It is reflexive \[EG85\] and universal with respect to this property: every map $`\stackrel{}{}𝒩`$ with $`𝒩`$ reflexive factors canonically through the natural map from $``$ to $`^{}`$.

Recall the following local version of the adjointness of $`f^{}`$ and $`f_{}`$ for a map of schemes $`f:X\stackrel{}{}Y`$.

###### Lemma 1.5.

Let $`f:X\stackrel{}{}Y`$ be a map of schemes, $``$ an $`𝒪_𝒳`$-module and $`𝒢`$ an $`𝒪_𝒴`$-module. There is a natural isomorphism

$$\mathrm{\Phi }:f_{}om_{𝒪_𝒳}(f^{}𝒢,)\stackrel{}{}𝓂_{𝒪_𝒴}(𝒢,𝒻_{}).$$

To see there is a globally defined map let $`\varphi _U`$ for $`UY`$ be a local section of the left hand side. Composing the natural map $`𝒢|_𝒰\stackrel{}{}𝒻_{}𝒻^{}𝒢|_𝒰=(𝒻_{}𝒻^{}𝒢)|_𝒰`$ with $`f_{}(\varphi _U):f_{}f^{}𝒢|_𝒰\stackrel{}{}𝒻_{}|_𝒰`$ we get the desired local section of the right hand side. Since no choices were made this defines the global map $`\mathrm{\Phi }`$. An inverse of $`\mathrm{\Phi }`$ can be established similarly using the natural map $`f^{}f_{}\stackrel{}{}`$.

###### Lemma 1.6.

Let $`X`$ be a normal scheme and let $`i:UX`$ the inclusion of an open set $`U`$ such that $`\mathrm{codim}(X,XU)2`$. If $``$ is a reflexive $`𝒪_𝒰`$-module then $`i_{}`$ is the unique reflexive $`𝒪_𝒳`$-module which agrees with $``$ on $`U`$.

###### Proof.

First we show that $`i_{}`$ is reflexive by showing that $`i_{}`$ commutes with dualizing. For this we need the easily verifiable facts that for the given setting $`i_{}𝒪_𝒰=𝒪_𝒳`$ and $`i^{}i_{}=(𝒾_{})|_𝒰=`$. Now use the local adjointness Lemma 1.5 in the following calculation.

$$\begin{array}{cc}\hfill (i_{})^{}& =om_{𝒪_𝒳}(i_{},𝒪_𝒳)=𝓂_{𝒪_𝒳}(𝒾_{},𝒾_{}𝒪_𝒰)\hfill \\ & =i_{}om_{𝒪_𝒰}(i^{}i_{},𝒪_𝒰)\hfill \\ & =i_{}^{}\hfill \end{array}$$

Thus $`(i_{})^{}𝒾_{}^{}𝒾_{}`$ which shows that $`i_{}`$ is reflexive.
For the uniqueness part let $`𝒩`$ be a reflexive $`𝒪_𝒳`$-module such that its restriction to $`U`$ is $``$. A similar application of the adjointness lemma shows that

$$\begin{array}{cc}\hfill 𝒩^{}& =om_{𝒪_𝒳}(𝒩,𝒪_𝒳)=𝒾_{}𝓂_{𝒪_𝒰}(𝒾^{}𝒩,𝒪_𝒰)\hfill \\ & =i_{}(𝒩|_𝒰)^{}=𝒾_{}^{}\hfill \end{array}$$

and dualizing this equality we get $`𝒩^{}𝒾_{}^{}`$ which shows that $`𝒩𝒾_{}`$ since both are reflexive. ∎

###### Lemma 1.7.

Let $`f:X\stackrel{}{}Y`$ be a flat morphism of noetherian normal schemes and let $``$ be a reflexive $`𝒪_𝒴`$-module. Then $`f^{}`$ is a reflexive $`𝒪_𝒳`$-module.

###### Proof.

First we establish a natural map $`f^{}^{}\stackrel{}{}(𝒻^{})^{}`$. Then we show by a local calculation that this is an isomorphism whenever $`f`$ is flat. Thus dualizing commutes with $`f^{}`$ and therefore $`f^{}`$ preserves reflexivity.

For the first part notice that quite generally, for any, not necessarily flat, $`f`$ and $`𝒪_𝒴`$-modules $``$ and $`𝒩`$ we get:

$$f^{}om_{𝒪_𝒴}(,𝒩)\stackrel{}{}𝒻^{}𝓂_{𝒪_𝒴}(,𝒻_{}𝒻^{}𝒩)\stackrel{}{}𝒻^{}𝒻_{}𝓂_{𝒪_𝒳}(𝒻^{},𝒻^{}𝒩)$$

The first map is composition with the natural map $`𝒩\stackrel{}{}𝒻_{}𝒻^{}𝒩`$ and the second map is the local adjointness Lemma 1.5. Composing this with the natural map $`f^{}f_{}om_{𝒪_𝒳}(f^{},𝒻^{}𝒩)\stackrel{}{}𝓂_{𝒪_𝒳}(𝒻^{},𝒻^{}𝒩)`$ gives the desired map.

To see that this is an isomorphism when $`f`$ if flat we reduce to checking on stalks. Thus it remains to show that for a flat map of local noetherian rings $`R\stackrel{}{}S`$ and finitely generated $`R`$-modules $`M`$ and $`N`$

($``$)
$$S_R\mathrm{Hom}_R(M,N)\stackrel{}{}\mathrm{Hom}_S(S_RM,S_RN).$$

which sends $`sf`$ to the map $`s^{}ms^{}sf(m)`$ is an isomorphism (this, of course, is the same as the map above). The case $`M=R`$ is easily verified since both sides are canonically isomorphic to $`S_RN`$ and the above map is then the identity. Since tensor and $`\mathrm{Hom}`$ both commute with finite direct sums ($``$1.3) is an isomorphism for f.g. free $`R`$-modules. Now let $`F\stackrel{}{}G\stackrel{}{}M\stackrel{}{}0`$ be a free presentation of $`M`$. Applying $`\mathrm{Hom}`$ and tensor (exact!) to this presentation in both orders we get a diagram:

The vertical maps to the right are isomorphisms since $`F`$ and $`G`$ are free. Thus by the 5-Lemma the left map is an isomorphism, too. ∎

###### Corollary 1.8.

Let $`f:X\stackrel{}{}Y`$ be faithfully flat and $``$ be an $`𝒪_𝒳`$-module. Then $``$ is reflexive if and only if $`f^{}`$ is reflexive.

## 2. Cartier operator for normal schemes

For schemes that are not smooth, the de Rham complex is not very well behaved and it seems convenient to consider the Zariski-de Rham complex instead. In order to define the sheaves of Zariski differentials we assume that the variety $`X`$ is normal.

### 2.1. Zariski-de Rham complex

###### Definition 2.1.

Let $`X`$ be a normal $`k`$-scheme and let

$$i:UX$$

be the inclusion of the smooth locus. The *Zariski-de Rham complex* is the pushforward of the de Rham complex on $`U`$ and is denoted by $`\stackrel{~}{\mathrm{\Omega }}_X^{}=i_{}\mathrm{\Omega }_U^{}`$.

The objects of the Zariski-de Rham complex are just $`\stackrel{~}{\mathrm{\Omega }}_X^a=i_{}\mathrm{\Omega }_U^a`$ and are called the Zariski sheaves of differential $`a`$-forms. Normality of $`X`$ guarantees that the Zariski sheaves are reflexive by Lemma 1.6. Equivalently, one can define $`\stackrel{~}{\mathrm{\Omega }}_X^a`$ as the unique reflexive $`𝒪_𝒳`$-module which agrees with $`\mathrm{\Omega }_X^a`$ on the smooth locus (i.e $`\stackrel{~}{\mathrm{\Omega }}_X^a`$ is the double dual or reflexive hull of $`\mathrm{\Omega }_X^a`$ and the natural map $`\mathrm{\Omega }_X^a\stackrel{}{}i_{}i^{}\mathrm{\Omega }_X^a=\stackrel{~}{\mathrm{\Omega }}_X^a`$ is identified with the double dualizing map). With this in mind one can take any open smooth $`U`$ with codimension $`XU`$ greater than or equal to two in the above definition. The differential on $`\stackrel{~}{\mathrm{\Omega }}_X^{}`$ is just the pushforward $`i_{}(d)`$ of the ordinary differential on $`\mathrm{\Omega }_U^{}`$. The Zariski sheaf of 1-forms $`\stackrel{~}{\mathrm{\Omega }}_X^1`$ satisfies a universal property similar to the universal property for the sheaf of Kähler differentials.

###### Proposition 2.2.

Every derivation $`\delta :𝒪_𝒳\stackrel{}{}`$ to a reflexive $`𝒪_𝒳`$-module $``$ factors uniquely through $`i_{}d:𝒪_𝒳\stackrel{}{}\stackrel{~}{\mathcal{\Omega }}_𝒳^\mathcal{1}`$.

###### Proof.

Observe that the derivation $`i_{}d`$ is the compostition of the universal derivation $`d:𝒪_𝒳\stackrel{}{}\mathcal{\Omega }_𝒳^\mathcal{1}`$ with the double dualizing map $`\mathrm{\Omega }_X^1\stackrel{}{}\stackrel{~}{\mathrm{\Omega }}_X^1`$. By the universal properties of these maps the proposition is immediate. ∎

Note that, if $`X=\mathrm{Spec}(R)`$ is affine, the Zariski sheaf is the sheaf associated to the finitely generated $`R`$-module $`\mathrm{\Gamma }(X,\stackrel{~}{\mathrm{\Omega }}_X^a)=\mathrm{\Gamma }(U,\mathrm{\Omega }_U^a)`$. The Zariski-de Rham complex shares many of the good properties of the de Rham complex on a smooth variety. For example, if $`X`$ is $`n`$-dimensional, the next proposition shows that the perfect pairing between $`\mathrm{\Omega }_U^a`$ and $`\mathrm{\Omega }_U^{na}`$ translates into a perfect pairing for the Zariski sheaves.

###### Proposition 2.3 (Danilov \[Dan78\]).

Let $`X`$ be a n-dimensional normal $`k`$-scheme. There is a natural isomorphism $`\stackrel{~}{\mathrm{\Omega }}_X^aom_{𝒪_𝒳}(\stackrel{~}{\mathrm{\Omega }}_X^{na},\stackrel{~}{\mathrm{\Omega }}_X^n)`$.

###### Proof.

Applying $`i_{}`$ to the duality on the smooth locus and using the local version of the adjointness of $`i_{}`$ and $`i^{}`$ we get

$$\begin{array}{cc}\hfill \stackrel{~}{\mathrm{\Omega }}_X^a& =i_{}\mathrm{\Omega }_U^a=i_{}om_{𝒪_𝒰}(\mathrm{\Omega }_U^{na},\mathrm{\Omega }_U^n)=i_{}om_{𝒪_𝒰}(i^{}i_{}\mathrm{\Omega }_U^{na},\mathrm{\Omega }_U^n)\hfill \\ & =om_{𝒪_𝒳}(i_{}\mathrm{\Omega }_U^{na},i_{}\mathrm{\Omega }_U^n)=om_{𝒪_𝒳}(\stackrel{~}{\mathrm{\Omega }}_X^{na},\stackrel{~}{\mathrm{\Omega }}_X^n)\hfill \end{array}$$

#### 2.1.1. Stability under étale morphisms

A morphism of sheaves $`f:Y\stackrel{}{}X`$ is called *étale* if it is flat and unramified. Just as the sheaves of Kähler differentials are preserved under étale maps so are the Zariski sheaves.

###### Lemma 2.4.

Let $`X`$ be normal and $`f:Y\stackrel{}{}X`$ étale. Then

$$f^{}\stackrel{~}{\mathrm{\Omega }}_X^a\stackrel{~}{\mathrm{\Omega }}_Y^a.$$

###### Proof.

Note that by \[Mil80, Prop. 3.17(b)\] $`Y`$ is normal thus the Zariski sheaves are defined on $`Y`$. Now $`f^{}\stackrel{~}{\mathrm{\Omega }}_X^a=f^{}(\mathrm{\Omega }_{X}^{a}{}_{}{}^{})=(f^{}\mathrm{\Omega }_X^a)^{}=\stackrel{~}{\mathrm{\Omega }}_Y^a`$ using Lemma 1.7 and $`f^{}\mathrm{\Omega }_X^a\mathrm{\Omega }_Y^a`$ by étaleness of $`f`$. ∎

Another important observation is that the Frobenius commutes with étale pull back, i.e. $`F_{}f^{}𝒻^{}_{}`$ for all $`𝒪_𝒳`$-modules $``$.

###### Lemma 2.5.

Let $`X`$ and $`Y`$ be $`k`$-varieties and $`f:Y\stackrel{}{}X`$ an étale morphism. Then

is a fiber square, i.e. $`YY^{}\times _X^{}X`$.

###### Proof.

First assume that $`f`$ is finite and étale. Then by the above diagram and the universal property of the fiber product we have a natural map $`Y\stackrel{}{}Y^{}\times _X^{}X`$. To check this map is an isomorphism one reduces to the case where $`X`$ (and therefore $`Y`$) is affine. Since $`Y^{}\times _X^{}XY\times _{F_X}X`$ one further reduces to the case of the absolute Frobenius. Thus it remains to show that for a finite étale morphism of $`k`$-algebras $`R\stackrel{}{}S`$ we have $`(F_S)_{}SS_{F_R}(F_R)_{}R`$. This is done in \[HH90, page 50\].
In general an étale map can be factored into a finite ètale map followed by an open immersion: $`f:Y\stackrel{}{}U\stackrel{}{}X`$. It remains to check the statement for the open immersion $`U\stackrel{}{}X`$. As before one reduces to the case of the absolute Frobenius. As topological spaces $`U\times _{F_X}X`$ and $`U`$ are the same and a simple local calculation shows that they are isomorphic as $`k`$-schemes. ∎

With this at hand we can apply \[Har73, Proposition III.9.3\] and get:

###### Corollary 2.6.

Let $``$ be an $`𝒪_𝒳`$-module and $`f:Y\stackrel{}{}X`$ étale. Then $`f^{}F_{}_{}𝒻^{}`$.

Since similar in spirit to the above and used later we note here a Lemma which shows that $`F_{}`$ commutes with completion. For this we consider the local case.

###### Lemma 2.7.

Let $`(R,m)`$ be a local $`k`$-algebra, essentially of finite type over $`k`$. Then $`\widehat{R}R_R^{}\widehat{R}^{}`$. Here, $`\widehat{R}`$ denotes the $`m`$-adic completion of $`R`$.

###### Proof.

As in the previous Lemma $`R_R^{}\widehat{R}^{}R_{F_R}\widehat{R}`$ and we reduce to the case of the absolute Frobenius. Now it follows from the definition of completion:

$$R_{F_R}\widehat{R}=R_{F_R}\underset{}{\mathrm{lim}}\frac{R}{m^i}\underset{}{\mathrm{lim}}\frac{R}{R_{F_R}m^i}=\underset{}{\mathrm{lim}}\frac{R}{(m^i)^{[p]}R}=\widehat{R}$$

In the last equality we used that the sequence $`(m^i)^{[p]}`$ is cofinal with $`m^i`$ and therefore they both have the same limit. ∎

An easy calculation with the equation of the last Lemma shows that for any $`R`$-module $`M`$ $`F_{}`$ commutes with completion, i.e. $`F_{}\widehat{M}\widehat{R}^{}_R^{}F_{}M`$.

### 2.2. Cartier operator on Zariski differentials

The Cartier isomorphism on the smooth scheme $`U^{}`$ gives after applying $`i_{}`$ an isomorphism

$$i_{}C^1:\stackrel{~}{\mathrm{\Omega }}_X^{}^a\stackrel{}{}i_{}^𝒶(_{}\mathcal{\Omega }_𝒰^{}).$$

To obtain an analog of the Cartier operator for the Zariski sheaves it remains to construct natural maps

$$\varphi _a:^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{})𝒾_{}^𝒶(_{}\mathcal{\Omega }_𝒰^{})$$

for all $`a0`$. This is obtained with the help of the following general Lemma.

###### Lemma 2.8.

Let $`𝒜^{}`$ be a complex in an abelian category and $`G`$ a left exact functor of abelian categories. One has natural maps

$$\varphi _a:^𝒶(𝒢𝒜^{})\stackrel{}{}𝒢^𝒶(𝒜^{})$$

for all $`a0`$.

###### Proof.

To see this denote by $`𝒵^𝒶`$, $`^𝒶`$ the cycles and boundaries of $`𝒜^{}`$ (resp. $`𝒵_𝒢^𝒶`$, $`_𝒢^𝒶`$ for $`G𝒜^{}`$). By the left exactness of $`G`$ we get $`𝒵_𝒢^𝒶𝒢𝒵^𝒶`$. Applying $`G`$ to the sequence $`0\stackrel{}{}𝒵^𝒶\stackrel{}{}𝒜^𝒶\stackrel{}{}^{𝒶+\mathcal{1}}\stackrel{}{}\mathcal{0}`$ and arranging with the equivalent sequence for $`G𝒜^{}`$ in the diagram

we see that (Snake Lemma) the vertical arrow to the right is an injection. Now, using the equivalent diagram for the short exact sequence defining cohomology

together with the Snake Lemma gives the dotted vertical arrow to the right. Furthermore, $`\varphi _a`$ is injective if and only if $`_𝒢^𝒶\stackrel{}{}𝒢^𝒶`$ is an isomorphism and surjective if and only if the map $`G𝒵^𝒶\stackrel{}{}𝒢^𝒶(𝒜^{})`$ is surjective. ∎

Since $`i_{}`$ is left exact we can apply this construction to the complex $`F_{}\mathrm{\Omega }_U^{}`$ and therefore obtain natural maps $`\varphi _a:^𝒶(𝒾_{}_{}\mathcal{\Omega }_𝒰^{})𝒾_{}^𝒶(_{}\mathcal{\Omega }_𝒰^{})`$ for all $`a0`$. Since $`F_{}`$ commutes with $`i_{}`$ the first term is just $`^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{})`$

By the Cartier isomorphism on the smooth locus $`^𝒶(_{}\mathcal{\Omega }_𝒰^{})`$ is isomorphic to $`\mathrm{\Omega }_U^{}^a`$ which is a locally free and therefore reflexive $`𝒪_𝒰^{}`$-module. By Lemma 1.6 $`i_{}^𝒶(_{}\mathcal{\Omega }_𝒰^{})`$ is a reflexive $`𝒪_𝒳^{}`$-module. Thus, by the universal property of the reflexive hull, the map $`\varphi _a`$ factors through the natural map from $`^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{})`$ to its double dual:

By the uniqueness part of Lemma 1.6 the diagonal map has to be an isomorphism since $`\varphi _a`$ is an isomorphism on $`U^{}`$. If we use this natural isomorphism to identify $`i_{}^𝒶(_{}\mathcal{\Omega }_𝒰^{})`$ with the double dual of $`^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{})`$ the map $`\varphi _a`$ becomes nothing but double dualizing. Composing $`\varphi _a`$ with the inverse of $`i_{}C^1`$ we get:

###### Proposition 2.9.

For all $`a0`$ the Cartier isomorphism on $`U`$ induces a natural $`𝒪_𝒳^{}`$-linear map

$$\stackrel{~}{C}:^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{})\stackrel{~}{\mathcal{\Omega }}_𝒳^{}^𝒶.$$

By construction, $`\stackrel{~}{C}`$ is an isomorphism if and only if the map $`\varphi _a`$ is. This in turn is the case if and only if $`^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{})`$ is reflexive. This observation is key for the proof of the next Proposition.

###### Proposition 2.10.

Let $`f:Y\stackrel{}{}X`$ étale. If the Cartier operator $`\stackrel{~}{C}_X`$ on $`X`$ is an isomorphism then so is $`\stackrel{~}{C}_Y`$ on $`Y`$. If in addition $`f`$ is finite, then the reverse implication also holds.

###### Proof.

With the above observation we only have to show that if $`^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{})`$ is reflexive then so is $`^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒴^{})`$. Since an étale map is flat we can apply Lemma 1.7 to see that the reflexivity of $`^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{})`$ implies that $`f^{}^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{})`$ is reflexive. By flatness $`f^{}`$ commutes with taking cohomology and thus

$$f^{}^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{})=^𝒶(𝒻^{}_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{}).$$

By Corollary 2.6 $`f^{}F_{}\stackrel{~}{\mathrm{\Omega }}_X^a=F_{}f^{}\stackrel{~}{\mathrm{\Omega }}_X^a`$ which by 2.4 is just $`F_{}\stackrel{~}{\mathrm{\Omega }}_Y^a`$.
If $`f`$ is also finite then it is faithfully flat and an application of Corollary 1.8 yields the reverse implication. ∎

## 3. Cartier isomorphism for toric varieties

In this section we give the proof that the Cartier map is an isomorphism for affine toric varieties over $`k`$. The main ingredient is a description of the Zariski-de Rham complex due to Danilov \[Dan78\]. An interesting aspect of the given proof is that it is analogous to Danilov’s proof of a Poincaré type lemma for toric varieties which says that the Zariski-de Rham complex is a resolution of the constant sheaf $`k`$. Thus, as in the smooth case, the Cartier isomorphism can be viewed as a characteristic $`p`$ analog of the Poincaré lemma, both determining the cohomology of the de Rham complex. Furthermore, using the results of the previous section on the stability of the Cartier isomorphism under étale morphisms we conclude that also for toroidal varieties the Cartier operator is an isomorphism.

### 3.1. Affine toric varieties

First we recall some notation from toric geometry, for a more detailed introduction to toric geometry see \[Ful93\] or \[Dan78\]. Let $`N^n`$ be a lattice, $`M=N^{}`$ the dual lattice and we denote $`M_{}`$ by $`M_{}`$. The identification of $`N`$ with $`^n`$ allows us to consider the elements of $`N`$ as $`n`$-tuples of integers, similarly for $`M`$.

By a cone in $`N`$ we mean a subset $`\sigma N_{}`$ of the form $`\sigma =\{r_1v_1+\mathrm{}+r_sv_s|r_i0\}`$ for some $`v_i`$ in $`N`$. The dual cone of $`\sigma `$ in $`M`$ is $`\sigma ^{}=\{uM_{}|(u,v)0,\text{ for all }v\sigma \}`$ where $`(,)`$ is induced from the natural pairing between the dual lattices $`M`$ and $`N`$. A face of $`\sigma `$ is any set $`\sigma u^{}`$ for some $`u\sigma ^{}`$ and is a cone in $`N`$. For cones $`\tau `$ and $`\tau ^{}`$ in $`M_{}`$ $`(\tau \tau ^{})`$ denotes the set of all $`tt^{}`$ for $`t\tau `$ and $`t^{}\tau ^{}`$.

Let $`\sigma ^{}`$ be a cone in $`M_{}`$. Let $`k`$ be a perfect field and let $`A=k[\sigma ^{}M]`$ be the affine semigroup ring corresponding to $`\sigma `$, i.e. $`A`$ is the $`k`$-subalgebra of $`k[x_1,x_1^1,\mathrm{},x_n,x_n^1]`$ generated by the monomials $`x^m=x_1^{m_1}\mathrm{}x_n^{m_n}`$ for $`m\sigma ^{}`$. $`X=X_\sigma =\mathrm{Spec}(A)`$ denotes the corresponding affine toric variety. Note that $`A`$ carries a natural $`M`$-grading where the generator $`x^m`$ corresponding to $`m\sigma ^{}M`$ of $`A`$ is given degree $`m`$. As is well known $`X`$ is normal \[Ful93\] and we have the notion of Zariski differentials defined above. As before we denote by $`U`$ its smooth locus. Since $`X`$ is affine $`\stackrel{~}{\mathrm{\Omega }}_X^a`$ is the sheaf associated to some $`A`$-module, which we will call $`\stackrel{~}{\mathrm{\Omega }}_A^a`$.

#### 3.1.1. Danilov’s description

There is a nice description of the modules $`\stackrel{~}{\mathrm{\Omega }}_A^a`$ due to Danilov \[Dan78\] which we will give next.

Let $`V`$ denote the vector space $`M_{}k`$. For each codimension one face $`\tau `$ of $`\sigma ^{}`$ define a subspace $`V_\tau V`$.

$$V_\tau =(M(\tau \tau ))_{}k$$

For every $`m\sigma ^{}`$ we define a subspace $`V_mV`$:

$$V_m=\underset{\tau m}{}V_\tau $$

where $`\tau `$ is ranging over the codimension one faces of $`\sigma ^{}`$ containing $`m`$.

###### Proposition 3.1.

$`\stackrel{~}{\mathrm{\Omega }}_A^a`$ is isomorphic to the graded $`A`$-submodule $`V_\sigma ^a`$ of the $`M`$-graded $`A`$-module $`^aV_kA`$ with degree $`mM`$ piece

$$V_\sigma ^a(m)=\stackrel{a}{}V_mx^m.$$

The isomorphism is given by the following degree preserving map of graded $`A`$-modules

For the proof see \[Dan78, p. 110\]. With this identification of $`\stackrel{~}{\mathrm{\Omega }}_A^a`$ with $`V_\sigma ^a`$ the differential $`d:\stackrel{~}{\mathrm{\Omega }}_A^a\stackrel{}{}\stackrel{~}{\mathrm{\Omega }}_A^{i+1}`$ on the piece of degree $`m`$ is given by wedging with $`m1`$. Thus the degree $`m`$ part of the complex $`\stackrel{~}{\mathrm{\Omega }}_X^{}`$ is just

The key observation is that this complex is exact whenever $`m1`$ is a nonzero element of the vector space $`V_m`$.

If the characteristic of $`k`$ is zero this is the case if and only if $`m0`$. Thus the only degree on which the complex is not exact is degree $`0M`$. Assuming that the cone $`\sigma ^{}`$ does not contain any linear subspace we see that $`V_0=0`$ and therefore in degree zero we just get $`^0V_0=k`$. This was Danilovs proof of the Poincaré lemma for the Zariski-de Rham complex on an affine toric variety:

###### Poincare Lemma (\[Dan78\]).

If the characteristic of $`k`$ is zero and $`\sigma ^{}`$ is a cone with vertex (i.e. $`\sigma ^{}`$ does not contain a linear subspace) then

is exact, i.e. $`\stackrel{~}{\mathrm{\Omega }}_A^{}`$ is a resolution of $`k`$.

Back to the case when the characteristic of $`k`$ is greater than zero. Then we get the following analog of 1.3 for affine toric varieties.

###### Theorem 3.2.

If $`k`$ has characteristic $`p>0`$ then the map

$$\varphi :\stackrel{~}{\mathrm{\Omega }}_A^{}^a[a]F_{}\stackrel{~}{\mathrm{\Omega }}_A^{}$$

sending $`(m^{}1)x^m`$ to $`(m^{}1)x^{pm}`$ is a split injection and induces an isomorphism $`C^1:\stackrel{~}{\mathrm{\Omega }}_A^{}^a\stackrel{}{}^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒜^{})`$.

###### Proof.

As already in the statement of this Theorem we make use of the identification in 3.1 without further mentioning.

By definition $`\varphi `$ is additive. Noting that $`A^{}=A_{F_k}k`$ and $`\stackrel{~}{\mathrm{\Omega }}_A^{}^a=\stackrel{~}{\mathrm{\Omega }}_A^a_{F_k}k`$ it is easily checked that $`\varphi `$ is also $`A^{}`$-linear. Since $`m1=0`$ if and only if $`mpM`$ we see that the cohomology lives exclusively in degrees $`pm`$ for $`mM`$; in these degrees the differential (wedging with $`pm1=0`$) is the zero map. $`\varphi `$ maps the graded piece of degree $`m`$ isomorphically to the graded piece of degree $`pm`$. Thus the image of $`\varphi `$ is exactly the graded pieces of degree $`pm`$ for $`mM`$ which is the cohomology of $`F_{}\stackrel{~}{\mathrm{\Omega }}_A^{}`$. Thus $`^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒜^{})`$ is isomorphic to the graded $`A^{}`$-submodule of degree $`pM`$ pieces of $`F_{}\stackrel{~}{\mathrm{\Omega }}_A^a`$ and therefore $`\varphi `$ is also split. Using 3.1 one easily verifies that $`d\varphi =0`$, i.e $`\varphi `$ is a map of complexes.

It remains to show that the above defined map actually is an inverse of the Cartier operator. Using the description of 3.1 we see that for all $`m\sigma ^{}`$ $`\varphi (dx^m1)=x^{(p1)m}dx^m`$ which is just the defining property of the inverse Cartier map from which $`\stackrel{~}{C}`$ was constructed. ∎

Since checking that the Cartier operator $`\stackrel{~}{C}`$ is an isomorphism is a local matter we get as an immediate Corollary:

###### Corollary 3.3.

Let $`X`$ be a toric variety over a perfect field $`k`$. Then the Cartier operator

$$\stackrel{~}{C}:^𝒶(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{})\stackrel{~}{\mathcal{\Omega }}_𝒳^{}^𝒶$$

is an isomorphism.

Theorem 3.2 for *affine* toric varieties is much stronger than what we just established for the toric case. Not only is the Cartier map an isomorphism but also it is induced by a split injection $`\stackrel{~}{\mathrm{\Omega }}_X^{}^a\stackrel{}{}F_{}\stackrel{~}{\mathrm{\Omega }}_X^a`$. This stronger statement can still be achieved for toric varieties in general (not necessarily affine). The key point is that one has to ensure that the map $`\varphi `$ defined locally on the affine toric pieces as above patches to give a global map of sheaves.

For simplicity of notation we assume in the following discussion that $`k=𝔽_p`$. Notice that the description of $`\stackrel{~}{\mathrm{\Omega }}_X^a`$ in Lemma 3.1 localizes. I.e. if $`\tau `$ is a face of $`\sigma `$ then $`X_\tau `$ is an open subset of $`X_\sigma `$ and we have an inclusion $`\stackrel{~}{\mathrm{\Omega }}_{X_\sigma }^a\stackrel{~}{\mathrm{\Omega }}_{X_\tau }^a`$. This corresponds to the inclusion $`V_\sigma ^aV_\tau ^a`$. The reason for this is that the map $`V_\sigma ^a\stackrel{~}{\mathrm{\Omega }}_{X_\sigma }^a`$ is induced from the map $`^aV\stackrel{}{}\stackrel{~}{\mathrm{\Omega }}_{T_N}^a`$ for *any* cone $`\sigma `$ in $`N`$, here $`T_N`$ is the $`n`$-dimensional torus.

Now let $`X`$ be the toric variety associated to a fan $`\mathrm{\Sigma }`$ in $`N`$ (cf. \[Ful93\]). The torus $`T_N`$ is an open subset of $`X`$ and also of each affine toric piece $`X_\sigma `$ of $`X`$ for $`\sigma \mathrm{\Sigma }`$. Thus $`\stackrel{~}{\mathrm{\Omega }}_{X_\sigma }^a\stackrel{~}{\mathrm{\Omega }}_{T_N}^a`$ and the map $`\varphi _\sigma :\stackrel{~}{\mathrm{\Omega }}_{X_\sigma }^a\stackrel{}{}F_{}\stackrel{~}{\mathrm{\Omega }}_{X_\sigma }^a`$ is induced from the corresponding map for the torus $`T_N`$ ($`T_N`$ is the toric variety associated the cone $`\{0\}N`$). This shows that the maps $`\varphi _\sigma `$ agree on the intersections of their domains and thus give rise to a globally defined map $`\varphi `$ as required. We just proved (well, sketched a proof of) the following Proposition.

###### Proposition 3.4.

Let $`X`$ be a toric variety over a perfect field $`k`$. Then the Cartier operator is an isomorphism and is induced by a split injection

$$0\stackrel{}{}\underset{a}{}\stackrel{~}{\mathrm{\Omega }}_X^{}^a[a]\stackrel{}{}F_{}\stackrel{~}{\mathrm{\Omega }}_X^{}.$$

The existence of a split injection inducing the Cartier operator was already shown by Buch, Thomsen, Lauritzen and Mehta in \[BT97\] using the existence of natural liftings of characteristic $`p`$ toric varieties to toric varieties over $`/p^2`$, along with liftings of Frobenius. Their methods though do not yield any information on whether the Cartier operator is an isomorphism, but are sufficient to imply Bott vanishing and the degeneration of the Hodge to de Rham spectral sequence for projective toric varieties.

### 3.2. Toroidal varieties

With the help of Proposition 2.10 we can extend the results from the previous section to a important class of varieties: toroidal embeddings.

###### Definition 3.5.

A normal scheme $`X`$ locally of finite type over a field $`k`$ will be called *weakly toroidal* if for each point $`xX`$ there is a neighborhood $`U(x)`$ of $`x`$ and a diagram

where $`Z(x)`$ is an affine toric variety, $`f`$ is étale and $`g`$ is finite and étale.

This class of varieties includes the class of toroidal embeddings as defined in \[TE73\]. We have the following Theorem.

###### Theorem 3.6.

Let $`X`$ be weakly toroidal. Then the Cartier operator $`\stackrel{~}{C}`$ on $`X`$ is an isomorphism.

###### Proof.

To see that the Cartier operator on $`X`$ is an isomorphism is a local issue so we can assume that there is a diagram

with $`Z`$ affine toric, both maps étale and $`g`$ also finite. On the toric variety $`Z`$ the Cartier operator is an isomorphism and thus by 2.10 it is an isomorphism on $`Y`$, and again by 2.10, it is an isomorphism on $`X`$. ∎

## 4. An Obstruction to surjectivity

The last section shows that the Cartier operator is an isomorphism in the case of toroidal embeddings and it is natural to ask what is the exact class of varieties for which the Cartier operator is an isomorphism. It seems too much to hope that it would be an isomorphism for all normal varieties. And in fact there is a necessary and sufficient condition for $`\stackrel{~}{C}`$ to be a surjection at the top level, i.e. for $`\stackrel{~}{C}:^𝒹(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{})\stackrel{}{}\stackrel{~}{\mathcal{\Omega }}_𝒳^𝒹`$ where $`d`$ is the dimension of $`X`$.

To simplify the notation we assume $`k=𝔽_p`$. Let $`(R,m)`$ be a normal Cohen-Macaulay local domain of dimension $`d`$, essentially of finite type over $`k`$. Then $`R`$ is called $`F`$-injective if the Frobenius $`F:R\stackrel{}{}F_{}R`$ induces an injection on local cohomology $`H_m^d(R)\stackrel{}{}H_m^d(F_{}R)`$. To relate this to the Cartier operator on $`X=\mathrm{Spec}R`$ we denote the global sections of $`\stackrel{~}{\mathrm{\Omega }}_X^d`$ by $`\omega _R`$ which by normality is a canonical module for $`R`$. Since the Cartier operator $`\mathrm{\Gamma }(X,^𝒹(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{}))\stackrel{}{}\omega _{}`$ is surjective if and only if its composition with the natural surjection $`F_{}\omega _R\stackrel{}{}\mathrm{\Gamma }(X,^𝒹(_{}\stackrel{~}{\mathcal{\Omega }}_𝒳^{}))\stackrel{}{}\omega _{}`$ is surjective we consider now the map $`C:F_{}\omega _R\stackrel{}{}\omega _R`$ to which we also refer to as the Cartier map. This map is surjective iff its $`m`$-adic completion $`\widehat{C}:\widehat{R}F_{}\omega _R\stackrel{}{}\widehat{R}\omega _R`$ is a surjective map of $`\widehat{R}`$-modules by the faithfully flatness of completion. By the remark after Lemma 2.7 $`F_{}`$ commutes with completion and by \[BH98, 3.3.5\] $`\widehat{R}\omega _R`$ is a canonical module for $`\widehat{R}`$. Thus $`\widehat{R}\omega _R\omega _{\widehat{R}}`$ and $`\widehat{R}F_{}\omega _RF_{}\omega _{\widehat{R}}`$. Let $`E`$ denote the injective hull of the residue field of $`\widehat{R}`$ and take the Matlis dual of the completed Cartier map $`\widehat{C}`$ to get

$$\mathrm{Hom}_{\widehat{R}}(\omega _{\widehat{R}},E)\stackrel{}{}\mathrm{Hom}_{\widehat{R}}(F_{}\omega _{\widehat{R}},E).$$

Note that, since $`F`$ is a finite map $`F_{}\omega _{\widehat{R}}\mathrm{Hom}_{\widehat{R}}(F_{}\widehat{R},\omega _{\widehat{R}})`$ (cf. \[BH98, 3.3.7\]). This together with the local duality theorem \[BH98, 3.5.8\] shows that the last map is just

$$H_{\widehat{m}}^d(\widehat{R})\stackrel{}{}H_{\widehat{m}}^d(F_{}\widehat{R})$$

where we can leave out the completion and get the map induced by the Frobenius $`F:H_m^d(R)\stackrel{}{}H_m^d(F_{}R)`$. Summarizing we get the following Proposition.

###### Proposition 4.1.

Let $`(R,m)`$ be a local Cohen-Macaulay domain essentially of finite type over $`k`$. Then the Cartier map $`C:F_{}\omega _R\stackrel{}{}\omega _R`$ is surjective if and only if $`R`$ is $`F`$-injective.

One implication of this Proposition was already noticed by Mehta and Shrinivas in \[MS97\] where they use the Cartier operator on the top spot to obtain information about the singularities of the variety.


format: text

text:
# Quantum Computation of Jones’ Polynomials

## I Introduction

Quantum algorithms have proven to be more efficient than classical algorithms in solving a number of problems qcom . For instance, Shor’s quantum algorithm can factor numbers exponentially faster than classical algorithms. Grover’s search algorithm does not change the complexity class, but provides significant speed up for large databases. We would like to explore the power of quantum algorithms in the context of knot theory.

Classification of knots and links in a three-dimensional space is one of the open problems. Jones introduced a recursive procedure for determining a polynomial relation for these knots and links. Jones’ polynomials do classify some knots and links jon . There are other generalized polynomials which improve the classification but none of them have achieved complete classification lika . It is known that the evaluation of Jones’ polynomial classically is a $`\mathrm{\#}𝒫`$ hard problem jaeg . Hence it will be interesting to study the computation of knot and link polynomials using a quantum algorithm.

There are diverse approaches in physics to obtain polynomials for knots and links. Following Alexander’s theorem, any knot can be viewed as a closure or capping of an $`n`$-strand braid. Therefore the polynomials for knots and links can be determined by studying representation theory of braid groups $`_n`$. The common ingredient in these approaches is to find different representations of braid groups $`_n`$. We now present a brief summary of some of these approaches:

1) N-state vertex models which are two-dimensional statistical mechanical models where the bonds of the square lattice carry spin $`n/2`$ representations of $`SU(2)`$. The number of possible states of spin $`n/2`$ is denoted by $`N=n+1`$. The properties of these models are described by the so-called $`R`$-matrix which is an $`N^2\times N^2`$ matrix. The number of nonzero elements in the $`R`$-matrix for $`N`$-state vertex models is given by $`m=_{s=1}^{N1}2s^2+N^2`$. In the literature, the vertex models are referred to either as $`N`$-state vertex model or $`m`$-vertex models; both are equivalent. For example, 2-state vertex models carry spin $`1/2`$ on the lattice bonds and they are equivalently called as six-vertex models where “six” denotes the number of non-zero $`R`$-matrix elements. In Ref. Wad , braid group representations and knot polynomials from the $`R`$-matrices of $`N=2,3,4`$-state vertex models were obtained.

2) Chern-Simons gauge theory is a topological field theory which provides a natural framework for the study of knots and links witt . The knot polynomials are given by the expectation value of Wilson loop observables. In particular, the Jones’ polynomial corresponds to the Wilson loop carrying spin $`1/2`$ representation in $`SU(2)`$ Chern-Simons theory. Clearly, arbitrary representations of any compact gauge group $`G`$ can result in generalized polynomials rama . The polynomials are in the variable $`q`$ which is a function of the coupling constant $`k`$ and the rank of the gauge group. The field theoretic polynomials were obtained by exploiting the connection between Chern-Simons theory on a three-manifold with boundary and the corresponding Wess-Zumino-Witten conformal field theory (WZW) on the boundary. The polynomials crucially depended on various representations of the monodromy or braiding matrices in the WZW models.

Recently, Freedman et al. Free1  have attempted simulation of topological field theories by quantum computers. The topological quantum computation proposed in Refs. Free1 -Free3  is at a mathematically abstract level. It exploits the connection between fractional quantum Hall states and Chern-Simons theory at the appropriate integer coupling $`k`$.

3) State sum method of obtaining bracket polynomials Kauff1 ; Kauff2 . In Ref. Kauff1 , the construction of a unitary representation has been shown for the three-strand braid $`_3`$. Further within this approach, it has been shown that it is not possible for a quantum computer to evaluate the knot polynomial. However, for a specific choice of the polynomial variable, the linking number can be determined Kauff2 .

Our aim is to determine the Jones’ polynomial for any knot or link obtained from braids using a quantum algorithm. For this purpose, we need to determine matrix representation for braid generators. We will recapitulate the construction of braid group representation from the six-vertex model. Then, we can determine the eigenvalues and eigenstates for these braid generators. This exercise suggests that we can associate product of unitary operators for any braid word. Hence the unitary transformations, corresponding to any braid word, can be implemented using quantum gates. It is important to stress that the quantum computation in this paper is crucially dependent on the mapping of any braid word to a product of unitary operators.

The polynomials for knots and links can be directly computed by choosing a suitable eigenbasis of the braiding matrices. Essentially, a quantum algorithm will determine the probability of finding unitarily evolved initial state ($`|in`$) in a final state ($`|out`$):

$$P_K=|out|𝐔_B|in|^2$$
(1)
where $`𝐔_B`$ represents the series of unitary operators corresponding to the braid word. For the braiding matrices obtained from the six-vertex model, the above matrix element gives the modulus-square of the Jones’ polynomial (up to an overall constant).

This paper is organized as follows. In Section II, we present a general method to find representation of braid groups using N-state vertex models. We discuss in detail the six-vertex model, braiding eigenvalues and eigenstates. Using these eigenstates, we evaluate Jones’ polynomial. In Section III, we present a method to perform the evaluation of the modulus-square of the Jones’ polynomial as a quantum computation by considering any knot or link as a composition of cups, a series of braiding operations and caps. In the concluding section, we summarize the results obtained and discuss the significance of the quantum algorithm.

## II N-state Vertex Model

In this section, we review the construction of braid group representations from N-state vertex models Wad . In order to compare the eigenstates of the braiding operator with the qubit states, the six-vertex model (spin $`1/2`$ on the bonds of the square lattice) is relevant. Hence, we shall present the explicit form of the $`R`$-matrix and the braid matrix for the six-vertex model.

As mentioned in the introduction, vertex models are two-dimensional statistical mechanical models with the spins $`n/2`$ lying on the bonds of a square lattice. The properties of these models are described by the $`R`$-matrix elements between edge states $`(m_1,m_2)`$ and $`(n_1,n_2)`$: $`R_{m_1m_2}^{n_1n_2}(u)`$ where $`u`$ is the spectral parameter. Here $`m_1,m_2,n_1,n_2`$ take values $`n/2,n/21,\mathrm{}n/2`$. The integrability condition of these models requires the following equations to be satisfied:

$`X_i(u)X_{i+1}(u+v)X_i(v)=`$ $`X_{i+1}(v)X_i(u+v)X_{i+1}(u),`$ (2)
$`X_i(u)X_j(v)=`$ $`X_j(v)X_i(u)|ij|>1,`$ (3)
where $`X_i(u)`$s are called Yang-Baxter operators and the relation (2) is called Yang-Baxter equation. The explicit form of $`X_i(u)`$ in terms of the $`R`$-matrix elements is given by

$$X_i(u)=\underset{m_1m_2n_1n_2}{}R_{m_1m_2}^{n_1n_2}(u)I^{(1)}I^{(2)}\mathrm{}E_{n_2m_1}^iE_{n_1m_2}^{i+1}\mathrm{}I^{(n)},$$
(4)
where $`I^{(j)}`$ is the identity acting at the $`j`$-th position and $`E`$ is a matrix such that $`(E_{n_1m_2})_{pq}=\delta _{n_1p}\delta _{m_2q}`$. The solution to Eq. (2) can be written in a compact form kaul2 :

$$R_{m_1m_2}^{n_1n_2}(u)=\underset{J=0}{\overset{n}{}}\left\{\begin{array}{ccc}\frac{n}{2}& \frac{n}{2}& J\\ n_1& n_2& m\end{array}\right\}\lambda _J(u)\left\{\begin{array}{ccc}\frac{n}{2}& \frac{n}{2}& J\\ m_2& m_1& m\end{array}\right\}$$
(5)
where the terms in parenthesis are the quantum Clebsch-Gordan coefficients (q-CG) pas  which are nonzero if and only if $`m`$ takes a value in the range $`m=J,J+1,\mathrm{}+J`$ and satisfies the condition $`m_1+m_2=m=n_1+n_2`$. Here $`\lambda _J(u)`$ is given by

$$\lambda _J(u)=\underset{s=J+1}{\overset{j_1+j_2}{}}\mathrm{sinh}(s\mu +u)\underset{l=|j_1j_2|+1}{\overset{J}{}}\mathrm{sinh}(l\mu u),$$
(6)
where the q-CG coefficient variable $`q=e^{2\mu }`$. These solutions are spectral parameter dependent solutions. The explicit form of the $`R`$-matrix for the six-vertex model is

| $`n_1n_2`$ | $`(\frac{1}{2}\frac{1}{2})`$ | $`(\frac{1}{2}\frac{1}{2})`$ | $`(\frac{1}{2}\frac{1}{2})`$ | $`(\frac{1}{2}\frac{1}{2})`$ |
| --- | --- | --- | --- | --- |
| $`m_1m_2`$ |  |  |  |  |
| $`(\frac{1}{2}\frac{1}{2})`$ | $`sinh(\mu u)`$ | 0 | 0 | 0 |
| $`(\frac{1}{2}\frac{1}{2})`$ | 0 | $`sinh(u)`$ | $`e^usinh(\mu )`$ | 0 |
| $`(\frac{1}{2}\frac{1}{2})`$ | 0 | $`e^usinh(\mu )`$ | $`sinh(u)`$ | 0 |
| $`(\frac{1}{2}\frac{1}{2})`$ | 0 | 0 | 0 | $`sinh(\mu u)`$ |

We are interested in the construction of braid group representations from these Yang-Baxter operators $`X_i(u)`$ Wad . The defining relations of the braid group generators are exactly same as Eqs. (2,3) in the absence of the spectral parameter. In other words, the braid group generators $`b_i_n`$ (spectral parameter independent operators) are obtained from $`X_i(u)`$ by taking the spectral parameter $`u\mathrm{}`$:

$$\underset{u\mathrm{}}{lim}X_i(u)=b_i.$$
(7)
Let us define a quantity $`\sigma _{m_1m_2}^{n_1n_2}`$ as follows:

$$\underset{u\mathrm{}}{lim}R_{m_1m_2}^{n_1n_2}=\sigma _{m_2m_1}^{n_1n_2}.$$
(8)
The explicit form of the $`\sigma _{m_1,m_2}^{n_1n_2}`$-matrix elements in this limit turns out to be:

| $`n_1n_2`$ | $`(\frac{1}{2}\frac{1}{2})`$ | $`(\frac{1}{2}\frac{1}{2})`$ | $`(\frac{1}{2}\frac{1}{2})`$ | $`(\frac{1}{2}\frac{1}{2})`$ |
| --- | --- | --- | --- | --- |
| $`m_1m_2`$ |  |  |  |  |
| $`(`$1/2 1/2$`)`$ | $`1`$ | 0 | 0 | 0 |
| $`(`$1/2 -1/2 $`)`$ | 0 | $`0`$ | $`q^{\frac{1}{2}}`$ | 0 |
| $`(`$-1/2 1/2$`)`$ | 0 | $`q^{\frac{1}{2}}`$ | $`1q`$ | 0 |
| $`(`$-1/2 -1/2$`)`$ | 0 | 0 | 0 | $`1`$ |

The above matrix elements indicate that we can choose a basis for the $`n`$-strand braid as $`|m_1m_2\mathrm{}m_im_{i+1}\mathrm{}m_n`$ where $`m_i`$’s take values $`\pm \frac{1}{2}`$ which are the two possible quantum states of the spins $`s_i`$’s $`\frac{1}{2}`$. Hence $`m_i`$ denotes a single qubit basis and the above basis state is an $`n`$-qubit basis state. From Eq. (4), we can write the action of the braiding operator $`b_i`$ on such an $`n`$-qubit state:

$$b_i|m_1m_2\mathrm{}m_im_{i+1}\mathrm{}m_n=\underset{n_i,n_{i+1}}{}\sigma _{m_im_{i+1}}^{n_in_{i+1}}|m_1m_2\mathrm{}n_in_{i+1}\mathrm{}m_n,$$
(9)
where $`n_i,n_{i+1}`$ take values $`\pm \frac{1}{2}`$. Clearly, this equation is not an eigenvalue equation of the braiding operator. We need to diagonalise the $`\sigma _{m_1m_2}^{n_1n_2}`$ matrix to determine the eigenbasis of the braiding operator $`b_i`$. As we did in the case of Eq. (5), we can diagonalize the spectral parameter independent $`\sigma _{m_1m_2}^{n_1n_2}`$ using the quantum Clebsch-Gordan coefficients matrix. The corresponding eigenstates will be similar to the coupled states obtained from uncoupled states using quantum $`CG`$-coefficient matrix pas :

$$|J_im)=\underset{m_i,m_{i+1}}{}\left\{\begin{array}{ccc}s_i& s_{i+1}& J_i\\ m_i& m_{i+1}& m\end{array}\right\}|m_i,m_{i+1},$$
(10)
where $`s_i,s_{i+1}`$ are the spin $`\frac{1}{2}`$ states and $`J_is_is_{i+1}=0,1`$. Thus we obtain a $`2`$-qubit state $`|J_im)`$ which may be an entangled state.

The form of the diagonal $`\sigma `$ matrix in the coupled basis is:

| $`|Jm)`$ | $`|\mathrm{1\hspace{0.33em}1})`$ | $`|\mathrm{1\hspace{0.33em}0})`$ | $`|11)`$ | $`|\mathrm{0\hspace{0.33em}0})`$ |
| --- | --- | --- | --- | --- |
| $`|Jm)`$ |  |  |  |  |
| $`|\mathrm{1\hspace{0.33em}1})`$ | $`\lambda _1`$ | 0 | 0 | 0 |
| $`|\mathrm{1\hspace{0.33em}0})`$ | 0 | $`\lambda _1`$ | 0 | 0 |
| $`|11)`$ | 0 | 0 | $`\lambda _1`$ | 0 |
| $`|\mathrm{0\hspace{0.33em}0})`$ | 0 | 0 | 0 | $`\lambda _0`$ |

where $`\lambda _1=1`$ and $`\lambda _0=q`$. These eigenvalues are equal up to an overall normalization to the eigenvalues of the Wess-Zumino-Witten model monodromy matrices.

We observe that the eigenvalues of the $`\sigma `$ matrix on the coupled states $`|Jm)`$ depend only on $`J`$ and not on $`m`$. Therefore, we can suppress the $`m`$ dependence on the eigenstates of the braiding operator and equivalently write it as a tensor product state involving the spin $`\frac{1}{2}`$ placed on the bonds of the six-vertex model. That is,

$$|J_im)|J_i=|(s_is_{i+1})_{J_i}.$$
(11)
Even though we have explicitly diagonalized the $`\sigma `$ matrix, we must remember that all the braid group generators $`b_i`$’s cannot be simultaneously diagonalized. The spectral parameter independent form of Eqs. (2,3) are the defining relations of the braid group $`_n`$ which implies that we can simultaneously diagonalize either $`b_{2i}`$’s or $`b_{2i+1}`$’s.

### II.1 Representation Theory of Braid Groups in Knot Theory

In this subsection, we would like to address the eigenvectors and eigenvalues of braid generators from the viewpoint of obtaining polynomial invariants of knots from platting or capping of braids.

It is well known that knots from braids are not unique. That is, braids related by Markov moves I and II give rise to the same knot. These two moves indeed completely remove the non-uniqueness. So the construction of polynomial invariants for knots must be such that the polynomial does not change under Markov moves. One such procedure for knots obtained from closure of braids has been presented in Wad .

We will use the eigenstates of the braiding operators to directly compute the polynomial invariant for any knot obtained from closure or capping of an $`n`$-strand braid. In order to remove the non-uniqueness due to Markov moves, we place orientations on the strands of the braid. Further, we introduce a correction factor to the braid eigenvalues obtained from six-vertex model such that the polynomial does not change under Markov moves I and II. The correction factor on braiding eigenvalues depends on the relative orientations between the two strands. For right-handed half-twists between strands of parallel orientation, the braiding eigenvalues $`\lambda _J^{(+)}`$ are

$$\lambda _0^{(+)}=q^{3/2};\lambda _1^{(+)}=q^{1/2}.$$
(12)
Similarly, for right-handed half twists between strands of antiparallel orientation, the braiding eigenvalues $`\lambda _J^{()}`$ are

$$\lambda _0^{()}=1;\lambda _1^{()}=q^1.$$
(13)
The eigenvalues for left-handed half-twists are inverse of the right-handed half-twists eigenvalues.

Suppose we consider any knot obtained from capping of a $`2n`$-strand oriented braid. Clearly, capping is possible if the number of outgoing strands is equal the number of incoming strands in the oriented braid. In other words, the quantum states $`m_i`$’s on the strands (9) should be such that

$$\underset{i=1}{\overset{2n}{}}m_i=0.$$
(14)
Therefore to study knots from braids, only the subspace of the states $`|m_1m_2\mathrm{}m_{2n}`$ satisfying Eq. (14) needs to be considered. Hence the construction of the eigenstates of braiding operators should be consistent with Eq. (14).

We will now present the eigenstates of the braiding matrices which will enable direct evaluation of knot polynomials. For a $`2n`$-strand oriented braid, we can write the most general eigenbasis of braiding operators $`b_{2i+1}`$ with eigenvalue $`\lambda _{j_{2i+1}}`$, for all $`i`$’s, as:

$$\begin{array}{cc}\hfill |\varphi _{(\{J_{2i+1}\},\{l_i\})}=& |(\mathrm{}(\mathrm{}((s_1s_2)_{J_1}(s_3s_4)_{J_3})_{l_1}\hfill \\ & \mathrm{}(s_{2i+1}s_{2i+2})_{J_{2i+1}})_{l_i}\mathrm{}(s_{2n1}s_{2n})_{J_{2n1}})_0\hfill \end{array}$$
(15)
Recall that the appropriate braiding eigenvalues (12,13) need to be substituted depending on the relative orientations of the two strands involved in braiding and the handedness. The brackets within the basis kets should be identified with the notation in Eq. (11). That is, $`|(s_1s_2)_{J_1}=|J_1`$, $`|((s_1s_2)_{J_1}(s_3s_4)_{J_3})_{l_1}=|(J_1J_3)_{l_1}`$, and so on. Note that the final combined state in the above basis is chosen to be spin $`0`$ which is essential to satisfy the condition (14) to describe knots from closure or capping of braids.

In the similar fashion, we can write a different eigenbasis for braiding operators $`b_{2i}`$ with eigenvalue $`\lambda _{J_{2i}}`$ for all $`i`$’s:

$$\begin{array}{cc}\hfill |\stackrel{~}{\varphi }_{(\{J_{2i}\},\{r_i\})}=& |((\mathrm{}(\mathrm{}((s_1(s_2s_3))_{J_2})_{r_1}\mathrm{}\hfill \\ & (s_{2i}s_{2i+1})_{J_{2i}})_{r_{i1}}\mathrm{}(s_{2n2}s_{2n1})_{J_{2n2}})_{r_{n2}}s_{2n})_0\hfill \end{array}$$
(16)
In order to achieve the final spin $`0`$ state, we require $`r_{n2}=\frac{1}{2}`$. Incidentally, these two bases are equivalent to the conformal blocks in Wess-Witten conformal field theory.

The two different bases (15,16) are related by an orthogonal (unitary) duality matrix $`a_{(\{J_{2i+1}\},\{l_i\}),(\{J_{2i}\},\{r_i\})}`$

$$|\varphi _{(\{J_{2i+1}\},\{l_i\})}=a_{(\{J_{2i+1}\},\{l_i\}),(\{J_{2i}\},\{r_i\})}|\stackrel{~}{\varphi }_{(\{J_{2i}\},\{r_i\})}.$$
(17)
The duality matrix can be written in terms of products of $`SU(2)_q`$ quantum-Racah coefficient matrices kal :

$`a_{(\{J_{2i+1}\},\{l_i\}),(\{J_{2i}\},\{r_i\})}`$ $`=`$ $`{\displaystyle \underset{t_1,\mathrm{}t_{n2}}{}}{\displaystyle \underset{i=1}{\overset{n2}{}}}\left(a_{t_iJ_{2i+1}}\left[\begin{array}{cc}l_{i1}& s_{2i+1}\\ s_{2i+2}& l_i\end{array}\right]{\displaystyle \underset{m=0}{\overset{n2}{}}}a_{t_ir_{i1}}\left[\begin{array}{cc}t_{i1}& J_{2i}\\ r_i& s_{2m}\end{array}\right]\right)`$ (18)
$`{\displaystyle \underset{m=0}{\overset{n2}{}}}a_{l_iJ_{2i+2}}\left[\begin{array}{cc}t_m& s_{2m+2}\\ s_{2m+3}& t_{m+1}\end{array}\right]`$
where the closed form expression for the quantum-Racah coefficient matrix is Res

$`a_{jl}\left[\begin{array}{cc}s_1& s_2\\ s_3& s_4\end{array}\right]`$ $`=`$ $`(1)^{s_1+s_2+s_3+s_4}\sqrt{[2j+1][2l+1]}\mathrm{\Delta }(s_1,s_2,j)\mathrm{\Delta }(s_3,s_4,j)\mathrm{\Delta }(s_1,s_4,l)\mathrm{\Delta }(s_2,s_3,l)`$
$`\times {\displaystyle \underset{m0}{}}(1)^m[m+1]!\{[ms_1s_2j]![ms_3s_4j]![ms_1s_4l]!`$
$`\times [ms_2s_3l]![s_1+s_2+s_3+s_4m]![s_1+s_3+j+lm]!`$
$`\times [s_2+s_4+j+lm]!\}^1`$ (19)
where $`\mathrm{\Delta }(a,b,c)=\sqrt{\frac{[a+b+c]![ab+c]![a+bc]!}{[a+b+c+1]!}}`$ and the number in square brackets represents the $`q`$-number defined as

$$[x]=\frac{q^{x/2}q^{x/2}}{q^{1/2}q^{1/2}}.$$

With this detailed background on the representation theory of braid groups, we are now in a position to evaluate Jones’ polynomial for any knot or link.

### II.2 Evaluation of Jones’ polynomial

Consider any knot or link as shown in Fig. 1 which is technically called platting or capping of braids.

The knot type is determined by the braiding region denoted as the shaded region in Fig. 1. It involves a sequence of braiding operations which is usually written as a braid word with appropriate orientations. Taking the initial state and final state as $`|\varphi _{(\{0\},\{0\})}`$, the following matrix element

$$V_K=\varphi _{(\{0\},\{0\})}|𝐁|\varphi _{(\{0\},\{0\})}$$
(20)
gives the Jones’ polynomial (up to an overall normalisation). To see the polynomial form in variable $`q`$, we can substitute the eigenvalues of the braiding generators and the unitary duality matrices elaborated in the previous subsection.

For the variable $`q`$ being root of unity, we can equivalently denote the sequence of braiding operations $`𝐁_{2n}`$ as a product of unitary $`2^{2n}\times 2^{2n}`$ matrices. We will now illustrate this mapping for two examples involving four-strand and six-strand braids. As shown in Fig.2(a), the braid word

$$B_a=b_2^3\widehat{b}_{1}^{}{}_{}{}^{2}\widehat{b}_{3}^{}{}_{}{}^{2}b_2^3_4,$$

where $`\widehat{b}_i`$ denotes braiding between anti-parallely oriented $`i`$-th strand and $`i`$+1-th strand and $`b_j`$ denotes braiding between parallely oriented $`j`$-th strand and $`j`$+1-th strand. Following the rules of the representation theory of braids, the braid-word in Fig. 2(a) will be mapped to a product of $`2^4\times 2^4`$ unitary matrices as follows:

$$B_a𝐔_{B_a}=\left(\{𝐚𝐟(𝐛_\mathrm{𝟐})𝐚^{}𝐠(𝐛_\mathrm{𝟏},𝐛_\mathrm{𝟑})𝐚𝐡(𝐛_\mathrm{𝟐})𝐚^{}\}_{2\times 2}\mathrm{𝟏}_{14\times 14}\right)_{2^4\times 2^4}$$
(21)
where $`𝐚`$ is the duality matrix and the matrix elements of the matrices $`𝐟(𝐛_\mathrm{𝟐})`$, $`𝐠(𝐛_\mathrm{𝟏},𝐛_\mathrm{𝟑})`$ and $`𝐡(𝐛_\mathrm{𝟐})`$, for the braid word $`B_a`$, will be

$$𝐟(𝐛_\mathrm{𝟐})_{J_1J_2}=\delta _{J_1J_2}(\lambda _{J_2}^{(+)})^3,𝐠(𝐛_\mathrm{𝟏},𝐛_\mathrm{𝟑})_{J_1,J_2}=\delta _{J_1J_2}(\lambda _{J_1}^{()})^4,𝐡(𝐛_\mathrm{𝟐})_{J_1J_2}=\delta _{J_1J_2}(\lambda _{J_2}^{(+)})^3.$$
(22)
The entries in these diagonal matrices are functions of the braiding eigenvalues. The relative orientations and the number of crossings between the respective braids are incorporated in writing the functional form. If $`q`$ is a root of unity, these diagonal matrices are unitary. Thus we see that the braid word $`B_a_4`$ can be equivalently represented as a product of unitary $`2^4\times 2^4`$ matrices.

Similarly, the braid word $`B_b`$ corresponding to Fig. 2(b) will be

$$B_b=(b_2^1b_4)(\widehat{b}_{1}^{}{}_{}{}^{2}\widehat{b}_{3}^{}{}_{}{}^{3}\widehat{b}_{5}^{}{}_{}{}^{2})(\widehat{b}_2\widehat{b}_{4}^{}{}_{}{}^{2})b_1\widehat{b}_2_6.$$

The equivalent description involving product of $`2^6\times 2^6`$ unitary matrices will be

$$𝐔_{B_b}=[\left(𝐚𝐟(𝐛_\mathrm{𝟐},𝐛_\mathrm{𝟒})𝐚^{}𝐠(𝐛_\mathrm{𝟏},𝐛_\mathrm{𝟑},𝐛_\mathrm{𝟓})𝐚𝐡(𝐛_\mathrm{𝟐},𝐛_\mathrm{𝟒})𝐚^{}𝐟_\mathrm{𝟏}(𝐛_\mathrm{𝟏})𝐚𝐠_\mathrm{𝟏}(𝐛_\mathrm{𝟐})𝐚^{}\right)_{5\times 5}\mathrm{𝟏}_{59\times 59}]_{2^6\times 2^6}$$
(23)
where the duality matrix elements are denoted as $`a_{(J_1,J_3,J_5=l_1),(J_2,J_4,r_1)}`$ and the remaining $`5\times 5`$ diagonal matrices for the braid word $`B_b`$ will be

$`𝐟(𝐛_\mathrm{𝟐},𝐛_\mathrm{𝟒})_{(J_2^{},J_4^{},r_1^{}),(J_2,J_4,r_1)}`$ $`=`$ $`\delta _{J_2^{}J_2}\delta _{J_4^{},J_4}\delta _{r_1^{},r_1}(\lambda _{J_2}^{(+)})^1\lambda _{J_4}^{(+)}`$
$`𝐠(𝐛_\mathrm{𝟏},𝐛_\mathrm{𝟑},𝐛_\mathrm{𝟓})_{(J_1^{},J_3^{},J_5^{}),(J_1,J_3,J_5)}`$ $`=`$ $`\delta _{J_1^{}J_1}\delta _{J_3^{},J_3}\delta _{J_5^{},J_5}(\lambda _{J_1}^{()})^2(\lambda _{J_3}^{()})^3(\lambda _{J_5}^{()})^2`$
$`𝐡(𝐛_\mathrm{𝟐},𝐛_\mathrm{𝟒})_{(J_2^{},J_4^{},r_1^{}),(J_2,J_4,r_1)}`$ $`=`$ $`\delta _{J_2^{}J_2}\delta _{J_4^{},J_4}\delta _{r_1^{},r_1}\lambda _{J_2^{}}^{()}(\lambda _{J_4^{}}^{()})^2`$
$`𝐟_\mathrm{𝟏}(𝐛_\mathrm{𝟏})_{(J_1^{},J_3^{},J_5^{}),(J_1,J_3,J_5)}`$ $`=`$ $`\delta _{J_1^{}J_1}\delta _{J_3^{},J_3}\delta _{J_5^{},J_5}\lambda _{J_1^{}}^{(+)}`$
$`𝐠_\mathrm{𝟏}(𝐛_\mathrm{𝟐})_{(J_2^{},J_4^{},r_1^{}),(J_2,J_4,r_1)}`$ $`=`$ $`\delta _{J_2^{}J_2}\delta _{J_4^{},J_4}\delta _{r_1^{},r_1}\lambda _{J_2^{}}^{()}.`$ (24)
In a similar fashion, we can find the unitary representation $`𝐔_B`$ for any braid word $`B_{2n}`$ in terms of products of $`2^{2n}\times 2^{2n}`$ unitary matrices involving duality matrices $`[a_{(\{J_{2i+1}\},\{l_i\}),(\{J_{2i}\},\{r_i\})}\mathrm{𝟏}]_{\mathrm{𝟐}^{\mathrm{𝟐}𝐧}\times \mathrm{𝟐}^{\mathrm{𝟐}𝐧}}`$ and diagonal braiding matrices. These unitary representations play the role of quantum gates in the quantum computation of Jones’ polynomial.

## III Quantum Computation

In this section, we attempt to compute the Jones’ polynomials, for knots and links obtained from platting or capping of $`2n`$ strand braid as shown in Fig. 1, through a quantum algorithm. We have already elaborated in the previous section that we can associate $`𝐔_B`$ (product of unitary matrices) for every braid word $`B_{2n}`$. The quantum algorithm involves the following steps:
Step 1: Let the initial $`2n`$-qubit state be $`|0`$ ($`|cup`$).
Step 2: We perform the sequence of unitary operations $`𝐔_B`$ corresponding to the braid word $`B_{2n}`$ in Fig. 1. The unitarily transformed state will be

$$|\mathrm{\Psi }=𝐔_B|0.$$
(25)
Step 3: Finally, we determine the probablity of the unitarily evolved state $`|\mathrm{\Psi }`$ in a specific final state $`|f`$ as

$$|f|𝐔_B|0|^2.$$
(26)
Taking the final state to be $`|cap=|0`$, we get the modulus square of the Jones’ polynomial (up to an overall normalisation)$`V_K`$ (20).

For a subclass of knots(links) called achiral knots(links), $`V_K`$ is unchanged under $`qq^1`$. In other words, the matrix element $`0|U_B|0`$ will be real. For these achiral knots and links, the quantum algorithm directly gives the Jones’ polynomial (up to an overall normalisation).

## IV Summary and Discussions

In this paper, we have presented matrix representations for braiding matrices from six-vertex models. We have discussed the representation theory of braids, namely, the eigenbasis and eigenvalues of the braid generators obtained from six-vertex models. The explicit evaluation of Jones’ polynomial, for any knot/link from braids, is presented. From the evaluation, we have shown that we can associate a series of unitary operators for any braid word. This is the significant result of the paper enabling quantum computation. We have demonstrated a quantum algorithm, involving these unitary operators, which can determine the modulus square of the Jones’ polynomial for any knot or link. The algorithm gives Jones’ polynomial for achiral knots and links.

We must realize that the quantum computation essentially determines the probablity of unitarily evolved initial state in a specific final state. Further, the number of unitary operators is dependent on the braid word and at most equal to twice the length of the braid word.

Acknowledgments: We would like to thank L.H. Kauffman for comments and queries which significantly helped us to improve the paper. We would also like to thank Umasankar for going over the manuscript and suggesting corrections.


text:
# Quantum random walks with decoherent coins

## I Introduction

In the classical discrete random walk, a particle is located at one of a set of definite positions (such as the set of integers on the line). In response to a random event—for example, the flipping of a coin—the particle moves either right or left. This process is iterated, and the motion of the particle is analyzed statistically. These systems provide good models for diffusion and other stochastic processes.

Considerable work has been done recently on quantum random walks, which are unitary (and hence reversible) systems designed as analogues to the usual classical case. There are two general approaches to the problem: continuous Farhi and Gutmann (1998); Childs et al. (2002a, b) and discrete Aharonov et al. (1993); Meyer (1996); Nayak and Vishwanath (2000); Aharonov et al. (2001); Ambainis et al. (2001); Meyer and Blumer (2001); Moore and Russell (2001); MacKay et al. (2002); Kempe (2002); Konno et al. (2002); Konno (2002a, b); Travaglione and Milburn (2002); Du et al. (2002); Yamasaki et al. (2002); Sanders et al. (2002); Dür et al. (2002); Bach et al. (2002); Kendon and Tregenna (2002a) unitary walks. This paper is exclusively concerned with the discrete walk. In this discrete case, we introduce an extra “coin” degree of freedom (usually a single quantum bit) into the system. Just as in the classical random walk, the outcome of a “coin flip” determines which way the particle moves; but in the quantum case, both the “flip” of the coin and the conditional motion of the particle are unitary transformations. Different possible classical paths can interfere with each other.

In this paper we look at quantum walks on the infinite line. The particle is initially at position $`x=0`$ and is free to travel off to infinity in either direction. We will look at both the probability distribution in $`p(x,t)=x|\rho _t|x`$, and at the long-time behavior of the moments $`\widehat{x}`$ and $`\widehat{x}^2\widehat{x}^2`$ as functions of $`t`$.

For a classical random walk, $`p(x,t)`$ has the form of a binomial distribution, with a width which spreads like $`\sqrt{t}`$; the variance $`\overline{x^2}\overline{x}^2`$ grows linearly with time. The variance in the quantum walk, by contrast, grows quadratically with time; and the distribution $`p(x,t)`$ has a complicated, oscillatory form. Both of these are effects of interference between the possible paths of the particle.

It should be possible to recover the classical behavior as some kind of limit of the quantum system. There are two obvious ways to regain the classical result. If the quantum “coin” is measured at every step, then the record of the measurement outcomes singles out a particular classical path. By averaging over all possible measurement records, one recovers the usual classical behavior MacKay et al. (2002).

Alternatively, rather than re-using the same coin every time, one could replace it with a new quantum coin for each flip. After a time $`t`$ one would have accumulated $`t`$ coins, all of them entangled with the position of the particle. By measuring them, one could reconstruct an unique classical path; averaging over the outcomes would once again produce the classical result.

These two approaches, which are equivalent in the classical limit, give two different routes from quantum to classical Brun et al. (2002a). We might increase the number of coins used to generate the walk, cycling among $`M`$ different coins, in the limit using a new coin at each step. Or we might weakly measure the coin after each step, reaching the classical limit with strong, projective measurements. This is equivalent to having a coin which is subject to decoherence.

In another paper Brun et al. (2002b) we have considered the quantum random walk with multiple coins. In this case, the quantum behavior remains qualitatively unchanged until we reach the limit of a new coin for each step, at which point classical behavior is recovered.

In this paper, we consider the quantum random walk with a single coin subject to decoherence. We will see that in this case, the behavior is qualitatively quite different from the unitary quantum random walk. The usual classical solution is recovered in the limit where the coin decoheres completely every step; but even with weaker decoherence, the variance of the position distribution grows linearly with time, rather than quadratically (as in the unitary case).

In section II we present an analytical result for the moments of the decoherent walk, and compare them to the results from direct numerical simulations. In section III, we see how the probability distribution $`p(x,t)`$ changes as we introduce decoherence. Finally, in section IV we summarize our results and state conclusions.

## II Moments of the decoherent walk

### II.1 The unitary walk on the line

Let us now consider a fairly general quantum random walk on the line. The particle degree of freedom has a basis of position eigenstates $`\{|x\}`$ where $`x`$ can be any integer. The position operator is $`\widehat{x}`$, and $`\widehat{x}|x=x|x`$. We will assume that the particle begins the walk at the origin, in state $`|0`$. The walk is driven by a separate “coin” degree of freedom: a $`D`$-dimensional system with an initial state $`|\mathrm{\Phi }_0`$. Let $`\widehat{𝒫}_\mathrm{R},\widehat{𝒫}_\mathrm{L}`$ be two orthogonal projectors on the Hilbert space of the “coin,” such that $`\widehat{𝒫}_\mathrm{R}+\widehat{𝒫}_\mathrm{L}=\widehat{I}`$. These represent the two possible outcomes of the coin flip: Heads or Tails, Right or Left. We also define a unitary transformation $`\widehat{U}`$ which “flips” the coin by rotating a coin showing heads or tails into a superposition of the two. One step of the quantum random walk is given by the unitary operator

$$\widehat{E}\left(\widehat{S}\widehat{𝒫}_\mathrm{R}+\widehat{S}^{}\widehat{𝒫}_\mathrm{L}\right)\left(\widehat{I}\widehat{U}\right),$$
(II.1)
where $`\widehat{S},\widehat{S}^{}`$ are unitary shift operators on the particle position:

$$\widehat{S}|x=|x+1,\widehat{S}^{}|x=|x1.$$
(II.2)
The full initial state of the system (particle and “coin”) is

$$|\mathrm{\Psi }_0=|0|\mathrm{\Phi }_0.$$
(II.3)
We can identify the eigenvectors $`|k`$ of $`\widehat{S},\widehat{S}^{}`$,

$$|k=\underset{x}{}\mathrm{e}^{ikx}|x,$$
(II.4)
with eigenvalues

$`\widehat{S}|k`$ $`=`$ $`\mathrm{e}^{ik}|k,`$
$`\widehat{S}^{}|k`$ $`=`$ $`\mathrm{e}^{+ik}|k.`$ (II.5)
The inverse transformation is

$$|x=_\pi ^\pi \frac{dk}{2\pi }\mathrm{e}^{ikx}|k.$$
(II.6)
In particular, the initial state of the particle is

$$|0=_\pi ^\pi \frac{dk}{2\pi }|k.$$
(II.7)
These state vectors $`|k`$ are not renormalizable, but if used with caution they greatly simplify the calculations. In the $`k`$ basis, the evolution operator becomes

$`\widehat{E}\left(|k|\mathrm{\Phi }\right)`$ $`=`$ $`|k\left(\mathrm{e}^{ik}\widehat{𝒫}_\mathrm{R}+\mathrm{e}^{ik}\widehat{𝒫}_\mathrm{L}\right)\widehat{U}|\mathrm{\Phi },`$ (II.8)
$``$ $`|k\widehat{U}_k|\mathrm{\Phi },`$
where $`\widehat{U}_k`$ is also a unitary operator.

The usual case considered in the literature has taken the coin to be a simple two-level system, and the “flip” operator $`\widehat{U}`$ to be the usual Hadamard transformation $`\widehat{H}`$:

$`\widehat{H}|R`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{2}}}\left(|R+|L\right),`$
$`\widehat{H}|L`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{2}}}\left(|R|L\right).`$ (II.9)
The projectors are $`\widehat{𝒫}_\mathrm{R}=|RR|`$, $`\widehat{𝒫}_\mathrm{L}=|LL|`$. The walk on the line in this case has been exactly solved by Nayak and Vishwanath Nayak and Vishwanath (2000).

For the present, we will continue without assuming a particular form for $`\widehat{U}`$, $`\widehat{𝒫}_\mathrm{R}`$ or $`\widehat{𝒫}_\mathrm{L}`$. Later we will specialize to make comparison to numerical simulations.

### II.2 Decoherence

We now generalize to allow for decoherence. Suppose that before each unitary “flip” of the coin, a completely positive map is performed on the coin (note, NOT on both the coin and the particle). This map is given by a set of operators $`\{\widehat{A}_n\}`$ on the coin degree of freedom which satisfy

$$\underset{n}{}\widehat{A}_n^{}\widehat{A}_n=\widehat{I}.$$
(II.10)
A density operator $`\chi `$ for the coin degree of freedom is transformed

$$\chi \chi ^{}=\underset{n}{}\widehat{A}_n\chi \widehat{A}_n^{}.$$
(II.11)
If we apply this to a general density operator for the joint particle/coin system

$$\rho =\frac{dk}{2\pi }\frac{dk^{}}{2\pi }|kk^{}|\chi _{kk^{}},$$
(II.12)
then after one step the state becomes

$$\rho \rho ^{}=\frac{dk}{2\pi }\frac{dk^{}}{2\pi }|kk^{}|\underset{n}{}\widehat{U}_k\widehat{A}_n\chi _{kk^{}}\widehat{A}_n^{}\widehat{U}_k^{}^{}.$$
(II.13)
The initial state is

$$\rho _0=\frac{dk}{2\pi }\frac{dk^{}}{2\pi }|kk^{}||\mathrm{\Phi }_0\mathrm{\Phi }_0|.$$
(II.14)
Let the quantum random walk proceed for $`t`$ steps. Then the state evolves to

$$\rho _t=\frac{dk}{2\pi }\frac{dk^{}}{2\pi }|kk^{}|\underset{n_1,\mathrm{},n_t}{}\widehat{U}_k\widehat{A}_{n_t}\mathrm{}\widehat{U}_k\widehat{A}_{n_1}|\mathrm{\Phi }_0\mathrm{\Phi }_0|\widehat{A}_{n_1}^{}\widehat{U}_k^{}^{}\mathrm{}\widehat{A}_{n_t}^{}\widehat{U}_k^{}^{}.$$
(II.15)
We define the superoperator $`_{kk^{}}`$ on the coin degree of freedom

$$\frac{dk}{2\pi }\frac{dk^{}}{2\pi }|kk^{}|\underset{n}{}\widehat{U}_k\widehat{A}_n\chi _{kk^{}}\widehat{A}_n^{}\widehat{U}_k^{}^{}\frac{dk}{2\pi }\frac{dk^{}}{2\pi }|kk^{}|_{kk^{}}\chi _{kk^{}}.$$
(II.16)
In terms of the superoperator,

$$\rho _t=\frac{dk}{2\pi }\frac{dk^{}}{2\pi }|kk^{}|_{kk^{}}^t|\mathrm{\Phi }_0\mathrm{\Phi }_0|.$$
(II.17)
Note that for $`k=k^{}`$ this superoperator preserves the trace. This implies that

$$\mathrm{Tr}\left\{_{kk}^n\widehat{O}\right\}=\mathrm{Tr}\left\{\widehat{O}\right\},$$
(II.18)
for any operator $`\widehat{O}`$. This identity will prove useful later.

The probability to reach a point $`x`$ at time $`t`$ is

$`p(x,t)`$ $`=`$ $`\mathrm{Tr}\left\{|xx|\rho _t\right\}=x|\rho _t|x`$ (II.19)
$`=`$ $`{\displaystyle \frac{1}{(2\pi )^2}}{\displaystyle 𝑑k𝑑k^{}k|xx|k^{}\mathrm{Tr}\left\{_{kk^{}}^t|\mathrm{\Phi }_0\mathrm{\Phi }_0|\right\}}`$
$`=`$ $`{\displaystyle \frac{1}{(2\pi )^2}}{\displaystyle 𝑑k𝑑k^{}\mathrm{e}^{ix(kk^{})}\mathrm{Tr}\left\{_{kk^{}}^t|\mathrm{\Phi }_0\mathrm{\Phi }_0|\right\}}.`$
### II.3 Moments of position

Eq. (II.19) for $`p(x,t)`$ will be difficult to evaluate, in general. However, we can get considerably further by restricting our interest to the moments of this distribution.

$`\widehat{x}^m_t`$ $`=`$ $`{\displaystyle \underset{x}{}}x^mp(x,t)`$ (II.20)
$`=`$ $`{\displaystyle \frac{1}{(2\pi )^2}}{\displaystyle \underset{x}{}}x^m{\displaystyle 𝑑k𝑑k^{}\mathrm{e}^{ix(kk^{})}\mathrm{Tr}\left\{_{kk^{}}^t|\mathrm{\Phi }_0\mathrm{\Phi }_0|\right\}}.`$
We can then invert the order of operations and do the $`x`$ sum first. This sum can be exactly carried out in terms of derivatives of the delta function:

$$\frac{1}{2\pi }\underset{x}{}x^m\mathrm{e}^{ix(kk^{})}=(i)^m\delta ^{(m)}(kk^{}).$$
(II.21)
Inserting this result back into our expression for $`\widehat{x}^m_t`$ yields

$$\widehat{x}^m_t=\frac{(i)^m}{2\pi }𝑑k𝑑k^{}\delta ^{(m)}(kk^{})\mathrm{Tr}\left\{_{kk^{}}^t|\mathrm{\Phi }_0\mathrm{\Phi }_0|\right\}.$$
(II.22)
We can then integrate this by parts.

In carrying out this integration by parts, we will need

$`{\displaystyle \frac{d}{dk}}\mathrm{Tr}\left\{_{kk^{}}\widehat{O}\right\}`$ $`=`$ $`\mathrm{Tr}\left\{(d_{kk^{}}/dk)\widehat{O}\right\}`$ (II.23)
$`=`$ $`{\displaystyle \underset{n}{}}\mathrm{Tr}\left\{(d\widehat{U}_k/dk)\widehat{A}_n\widehat{O}\widehat{A}_n^{}\widehat{U}_k^{}^{}\right\},`$
where

$`{\displaystyle \frac{d\widehat{U}_k}{dk}}`$ $`=`$ $`i(\widehat{𝒫}_0\widehat{𝒫}_1)\widehat{U}_ki\widehat{Z}\widehat{U}_k`$
$`{\displaystyle \frac{d\widehat{U}_k^{}}{dk}}`$ $`=`$ $`i\widehat{U}_k^{}(\widehat{𝒫}_0\widehat{𝒫}_1)i\widehat{U}_k^{}\widehat{Z}`$
$`\widehat{Z}`$ $`=`$ $`\widehat{𝒫}_\mathrm{R}\widehat{𝒫}_\mathrm{L}=\widehat{I}2\widehat{𝒫}_\mathrm{L}.`$ (II.24)
Substituting this back into (II.23) we get

$`{\displaystyle \frac{d}{dk}}\mathrm{Tr}\left\{_{kk^{}}\widehat{O}\right\}`$ $`=`$ $`i\mathrm{Tr}\left\{\widehat{Z}_{kk^{}}\widehat{O}\right\},`$ (II.25)
$`=`$ $`i\mathrm{Tr}\left\{(_{kk^{}}\widehat{O})\widehat{Z}\right\},`$
$`=`$ $`{\displaystyle \frac{d}{dk^{}}}\mathrm{Tr}\left\{_{kk^{}}\widehat{O}\right\}.`$
Making use of (II.18) and (II.25), when we carry out the integration by parts for the first moment we get

$$\widehat{x}_t=\frac{1}{2\pi }\underset{j=1}{\overset{t}{}}𝑑k\mathrm{Tr}\left\{\widehat{Z}_{kk}^j|\mathrm{\Phi }_0\mathrm{\Phi }_0|\right\}.$$
(II.26)
We can simplify our notation slightly by defining

$$_k_{kk}.$$
(II.27)
We can carry out a similar integration by parts to get the second moment:

$`\widehat{x}^2_t`$ $`=`$ $`{\displaystyle \frac{1}{2\pi }}{\displaystyle }dk[{\displaystyle \underset{j=1}{\overset{t}{}}}{\displaystyle \underset{j^{}=1}{\overset{j}{}}}\mathrm{Tr}\left\{\widehat{Z}_k^{jj^{}}(\widehat{Z}_k^j^{}|\mathrm{\Phi }_0\mathrm{\Phi }_0|)\right\}`$ (II.28)
$`+{\displaystyle \underset{j=1}{\overset{t}{}}}{\displaystyle \underset{j^{}=1}{\overset{j1}{}}}\mathrm{Tr}\left\{\widehat{Z}_k^{jj^{}}((_k^j^{}|\mathrm{\Phi }_0\mathrm{\Phi }_0|)\widehat{Z})\right\}].`$
Note that this form is rather similar to that for a correlation function.

For the unitary walk Brun et al. (2002a, b), we were able to separate the expressions for the moments into oscillatory and nonoscillatory terms, and consider only the nonoscillatory terms for the long-time limit. In the present case, this will not work; because of the presence of decoherence, the oscillations are damped. However, the long-time limit still simplifies in another way. If we think of $`_k`$ as a linear transformation, all its eigenvalues must clearly obey $`|\lambda |1`$ in order for it to be completely positive. In finding the long-time limit, we need pick out only those components of the expressions (II.26) and (II.28) which do not die away at large $`t`$.

### II.4 The Hadamard walk with decoherence

To get any further than this, we need to specialize to a particular model. Let’s choose the standard two-dimensional “coin” and the Hadamard walk as described above. This makes our operator $`\widehat{U}_k`$

$$\widehat{U}_k=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}\mathrm{e}^{ik}& \mathrm{e}^{ik}\\ \mathrm{e}^{ik}& \mathrm{e}^{ik}\end{array}\right).$$
(II.29)
We need also to pick a particular form for the decoherence. I will choose the decoherence produced by the three operators

$`\widehat{A}_0=\sqrt{p}|RR|,`$
$`\widehat{A}_1=\sqrt{p}|LL|,`$
$`\widehat{A}_2=\sqrt{1p}\widehat{I}.`$ (II.30)
This resembles a coin which has a probability $`p`$ per step of being measured; however, this is equivalent to a large class of other decoherence models, such as pure dephasing

$`\widehat{A}_0^{}={\displaystyle \frac{1}{\sqrt{2}}}\left(\mathrm{e}^{i\theta }|RR|+\mathrm{e}^{i\theta }|LL|\right),`$
$`\widehat{A}_1^{}={\displaystyle \frac{1}{\sqrt{2}}}\left(\mathrm{e}^{i\theta }|RR|+\mathrm{e}^{i\theta }|LL|\right),`$ (II.31)
or weak measurement

$`\widehat{A}_0^{\prime \prime }=\sqrt{q}|RR|+\sqrt{1q}|LL|,`$
$`\widehat{A}_1^{\prime \prime }=\sqrt{1q}|RR|+\sqrt{q}|LL|.`$ (II.32)
All three of these decoherence processes represent the same completely positive map on the density matrix; one can transform from one to the other by invoking the relationships between the parameters

$$1p=\mathrm{cos}2\theta =2\sqrt{q(1q)}.$$
(II.33)
We will generally use the first in our derivations, for simplicity; but the second is more convenient for numerical calculations. Note that this equivalence applies to the average behavior over all outcomes; for a single sequence of outcomes, the conditional dynamics of these three decoherence (or weak measurement) models can look quite different.

In the absence of decoherence, the Hadamard walk exhibits a linear drift in $`\widehat{x}`$ and a quadratic growth in the variance $`\widehat{x}^2\widehat{x}^2`$. We plot these moments in figure 1.

Because $`_k`$ is linear, we can represent it as a matrix acting on the space of two-by-two operators. A convenient representation is to write

$$\widehat{O}=r_0\widehat{I}+r_1\sigma _1+r_2\sigma _2+r_3\sigma _3,$$
(II.34)
where $`\sigma _{1,2,3}=\sigma _{x,y,z}`$ are the usual Pauli matrices. We can then represent $`\widehat{O}`$ by a column vector

$$\widehat{O}\left(\begin{array}{c}r_0\\ r_1\\ r_2\\ r_3\end{array}\right).$$
(II.35)
The action of $`_k`$ on $`\widehat{O}`$ is then given by

$$_k\widehat{O}\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& (1p)\mathrm{sin}2k& \mathrm{cos}2k\\ 0& 0& (1p)\mathrm{cos}2k& \mathrm{sin}2k\\ 0& 1p& 0& 0\end{array}\right)\left(\begin{array}{c}r_0\\ r_1\\ r_2\\ r_3\end{array}\right).$$
(II.36)
Note that since $`r_0=\mathrm{Tr}\{\widehat{O}\}`$, it is unaffected by $`_k`$, which is trace-preserving. So the only nontrivial dynamics result from the three-by-three submatrix

$$M_k\left(\begin{array}{ccc}0& (1p)\mathrm{sin}2k& \mathrm{cos}2k\\ 0& (1p)\mathrm{cos}2k& \mathrm{sin}2k\\ 1p& 0& 0\end{array}\right).$$
(II.37)
We also need to know the effects of left-multiplying and right-multiplying by $`\widehat{Z}`$. These are given by the two matrices

$$Z_L\left(\begin{array}{cccc}0& 0& 0& 1\\ 0& 0& i& 0\\ 0& i& 0& 0\\ 1& 0& 0& 0\end{array}\right),Z_R\left(\begin{array}{cccc}0& 0& 0& 1\\ 0& 0& i& 0\\ 0& i& 0& 0\\ 1& 0& 0& 0\end{array}\right).$$
(II.38)
Finally, taking the trace picks out the 0 component of the column vector and drops the rest.

Let us take these expressions and apply them to equation (II.26) for the first moment. In the integrand, the initial density matrix for the coin is multiplied $`j`$ times by $`_k`$, then left-multiplied by $`\widehat{Z}`$, and finally the trace is taken. Given the above expression for $`Z_L`$, we see that this is the same as multiplying the three-vector $`(r_1,r_2,r_3)`$ $`j`$ times by $`M_k`$ and then keeping only the $`r_3`$ component of the result. This gives us the new expression:

$`\widehat{x}_t`$ $`=`$ $`{\displaystyle \frac{1}{2\pi }}{\displaystyle 𝑑k\left(\begin{array}{ccc}0& 0& 1\end{array}\right)\left[\underset{j=1}{\overset{t}{}}M_k^j\right]\left(\begin{array}{c}r_1\\ r_2\\ r_3\end{array}\right)}`$ (II.39)
$`=`$ $`{\displaystyle \frac{1}{2\pi }}{\displaystyle 𝑑k\left(\begin{array}{ccc}0& 0& 1\end{array}\right)\left[(1M_k)^1(M_kM_k^{t+1})\right]\left(\begin{array}{c}r_1\\ r_2\\ r_3\end{array}\right)}.`$
The eigenvalues of $`M_k`$ are complicated, but fortunately we don’t need to evaluate them. All we need to know is that all of them obey $`0<|\lambda |<1`$ (where both these inequalities are strict). In the long time limit, therefore, $`M_k^{t+1}0`$, and the moment becomes approximately

$$\widehat{x}_t\frac{1}{2\pi }𝑑k\left(\begin{array}{ccc}0& 0& 1\end{array}\right)\left[(1M_k)^1M_k\right]\left(\begin{array}{c}r_1\\ r_2\\ r_3\end{array}\right).$$
(II.40)
Note that all $`t`$ dependence has vanished. Therefore, in the long time limit, the first moment tends to a constant.

As it happens, the matrix $`1M_k`$ is exactly invertible:

$$(1M_k)^1=\frac{1}{p(2p)}\left(\begin{array}{ccc}1+(1p)\mathrm{cos}2k& (1p)\mathrm{sin}2k& (1p)+\mathrm{cos}2k\\ (1p)\mathrm{sin}2k& 1(1p)\mathrm{cos}2k& \mathrm{sin}2k\\ (1p)(1+(1p)\mathrm{cos}2k)& (1p)^2\mathrm{sin}2k& 1+(1p)\mathrm{cos}2k\end{array}\right).$$
(II.41)
Inserting this and (II.37) into (II.40) yields

$`\widehat{x}_t`$ $``$ $`{\displaystyle \frac{1}{2\pi }}{\displaystyle 𝑑k\frac{1p}{p(2p)}\left[(1p)r_3+r_1+(r_3+(1p)r_1)\mathrm{cos}2k(1p)r_2\mathrm{sin}2k\right]}`$ (II.42)
$`=`$ $`{\displaystyle \frac{1p}{p(2p)}}\left[(1p)r_3+r_1\right]`$
$`=`$ $`{\displaystyle \frac{1p}{p(2p)}}\left[(1p)(|\alpha |^2|\beta |^2)+(\alpha ^{}\beta +\alpha \beta ^{})\right],`$
where the initial state of the coin is $`|\mathrm{\Phi }_0=\alpha |R+\beta |L`$.

In figure 2, we compare this result to the results of direct numerical simulation for the initial state $`|\mathrm{\Phi }_0=|R`$. As we can see, the first moment does tend to drift towards a constant value asymptotically. What variation there is is a result of statistical error in the Monte Carlo simulation rather than a poor fit.

The second moment is a somewhat more complicated calculation. Let us rewrite the equation (II.28) in terms of our four-by-four matrices:

$`\widehat{x}^2_t`$ $`=`$ $`{\displaystyle \frac{1}{2\pi }}{\displaystyle }dk[{\displaystyle \underset{j=1}{\overset{t}{}}}{\displaystyle \underset{j^{}=1}{\overset{j}{}}}\mathrm{Tr}\left\{\widehat{Z}_k^{jj^{}}(\widehat{Z}_k^j^{}|\mathrm{\Phi }_0\mathrm{\Phi }_0|)\right\}`$ (II.43)
$`+{\displaystyle \underset{j=1}{\overset{t}{}}}{\displaystyle \underset{j^{}=1}{\overset{j1}{}}}\mathrm{Tr}\left\{\widehat{Z}_k^{jj^{}}((_k^j^{}|\mathrm{\Phi }_0\mathrm{\Phi }_0|)\widehat{Z})\right\}]`$
$`=`$ $`t{\displaystyle \frac{1}{2\pi }}{\displaystyle 𝑑k\left(\begin{array}{cccc}1& 0& 0& 0\end{array}\right)\left[Z_L\underset{j=1}{\overset{t}{}}\underset{j^{}=1}{\overset{j1}{}}_k^{jj^{}}(Z_L+Z_R)_k^j^{}\right]\left(\begin{array}{c}1\\ r_1\\ r_2\\ r_3\end{array}\right)}`$
$`=`$ $`t{\displaystyle \frac{1}{2\pi }}{\displaystyle 𝑑k\left(\begin{array}{cccc}0& 0& 0& 1\end{array}\right)\left[\underset{j=1}{\overset{t}{}}\underset{j^{}=1}{\overset{j1}{}}_k^{jj^{}}(Z_L+Z_R)_k^j^{}\right]\left(\begin{array}{c}1\\ r_1\\ r_2\\ r_3\end{array}\right)}.`$
The initial $`t`$ term comes from the $`j=j^{}`$ components of (II.28), where the two factors of $`\widehat{Z}`$ cancel out.

Recall the block-diagonal form (II.36) of $`_k`$, and note that

$$(Z_L+Z_R)=\left(\begin{array}{cccc}0& 0& 0& 2\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 2& 0& 0& 0\end{array}\right)$$
(II.44)
is extremely sparse. In this case, it makes sense to separate the 0 and $`1,2,3`$ components of the expression:

$`\widehat{x}^2_t`$ $`=`$ $`t{\displaystyle \underset{j=1}{\overset{t}{}}}{\displaystyle \underset{j^{}=1}{\overset{j1}{}}}{\displaystyle \frac{1}{2\pi }}{\displaystyle }dk\left(\begin{array}{cccc}0& 0& 0& 1\end{array}\right)[_k^{jj^{}}(Z_L+Z_R)_k^j^{}\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)`$ (II.45)
$`+_k^{jj^{}}(Z_L+Z_R)_k^j^{}\left(\begin{array}{c}0\\ r_1\\ r_2\\ r_3\end{array}\right)].`$
We can drop the second term, because it will be cancelled in the inner product with $`\left(\begin{array}{cccc}0& 0& 0& 1\end{array}\right)`$. This means that $`\widehat{x}^2_t`$ has no dependence on the initial state! The remaining term becomes

$`\widehat{x}^2_t`$ $`=`$ $`t{\displaystyle \underset{j=1}{\overset{t}{}}}{\displaystyle \underset{j^{}=1}{\overset{j1}{}}}{\displaystyle \frac{1}{2\pi }}{\displaystyle 𝑑k\left(\begin{array}{cccc}0& 0& 0& 1\end{array}\right)_k^{jj^{}}\left(\begin{array}{c}0\\ 0\\ 0\\ 2\end{array}\right)}`$ (II.46)
$`=`$ $`t{\displaystyle \frac{1}{2\pi }}{\displaystyle 𝑑k\left(\begin{array}{ccc}0& 0& 1\end{array}\right)\left[\underset{j=1}{\overset{t}{}}\underset{j^{}=1}{\overset{j1}{}}M_k^{jj^{}}\right]\left(\begin{array}{c}0\\ 0\\ 2\end{array}\right)}`$
$`=`$ $`t{\displaystyle \frac{1}{2\pi }}{\displaystyle 𝑑k\left(\begin{array}{ccc}0& 0& 1\end{array}\right)}`$
$`\times \left[t(1M_k)^1M_k+(1M_k)^1M_k^t\right](1M_k)^1M_k\left(\begin{array}{c}0\\ 0\\ 2\end{array}\right).`$
In the long-time limit, we can drop the $`M_k^t`$ terms as negligible. We can thereby substitute the exact expressions (II.37) and (II.41) for the remaining matrices and simplify:

$`\widehat{x}^2_t`$ $`=`$ $`t+{\displaystyle \frac{1}{2\pi }}{\displaystyle }dk{\displaystyle \frac{1p}{p(2p)}}[2t(1p+\mathrm{cos}2k)`$ (II.47)
$`{\displaystyle \frac{1}{p(2p)}}(4(22p+p^2)\mathrm{cos}2k+(1p)(7+\mathrm{cos}4k))]`$
$`=`$ $`t\left(1+{\displaystyle \frac{2(1p)^2}{p(2p)}}\right){\displaystyle \frac{7(1p)^2}{p^2(2p)^2}}.`$
Thus, in the case of the decoherent coin the variance will grow linearly with time at long times, just as in the classical case, though the rate of growth will be greater than for the classical random walk. Note that as $`p1`$, $`\widehat{x}^2_tt`$, which is the classical result.

Because of the dependence of the first moment on the initial condition, the variance will have some residual dependence on the initial condition; but since this is only a constant it is quite unimportant. Upon comparison to the numerical results (see figure 3), we see that this analytical expression for the variance matches extremely well.

Since this approximation holds in the long-time limit, it is reasonable to ask how long is a “long time.” For weak decoherence ($`p1`$), the evolution exhibits the same behavior as the unitary walk for short times, with the second moment growing quadratically in time, and only switches over to linear growth past some critical timescale. This changeover is visible in figure 3.

We take the long-time approximation by neglecting the $`M_k^t`$ term in (II.46). If we examine $`M_k^2`$, we see that it can be written as $`(1p)`$ multiplying a matrix whose determinant is less than one. Therefore, if we want this term to be negligible, then

$$M_k^t<(1p)^{t/2}<ϵ$$
(II.48)
for some positive $`ϵ1`$. This implies that

$`p>(2/t)\mathrm{log}(1/ϵ)c/t`$ (II.49)
which implies in turn that the second moment of position will grow linearly at $`t>c/p`$, for a large enough constant $`c`$. For $`t<c/p`$ there will be a transition over to quadratic time dependence. For small $`p`$, equation (II.47) becomes

$$\widehat{x}^2_t==t(1+1/p)7/4p^2.$$
(II.50)
## III The position distribution

As mentioned before, Eq. (II.19) for $`p(x,t)`$ is difficult to evaluate analytically. It is straightforward, however, to solve this system numerically. Rather than solve for the density matrix $`\rho `$, we instead have used quantum trajectory techniques Carmichael (1993) to do a quantum Monte Carlo simulation, averaging over many runs to find both the distribution itself and its moments.

For the purposes of these simulations, it proved more convenient to use the form (II.31) for the decoherence process. We have therefore labeled the figures with the appropriate values of the dephasing parameter $`\theta `$ instead of $`p`$. In performing the simulations, after each step of the quantum walk we randomly applied either operator $`\sqrt{2}\widehat{A}_0^{}`$ or $`\sqrt{2}\widehat{A}_1^{}`$ from eq. (II.31) to the state, choosing them with equal probability. Because $`\sqrt{2}\widehat{A}_{0,1}^{}`$ are unitary operators, it was unnecessary to renormalize the state. We then found the mean probability distributions $`p(x)`$ by averaging over many runs; each distribution plotted in this paper represents an average over $`10000`$ runs of the Monte Carlo program. In figure 4 we see how the probability distribution changes as we go to the classical limit of complete decoherence at every step ($`\theta =\pi /4`$).

As we see from the figure, the presence of decoherence quickly wipes out the most conspicuous signs of interference: the peaks at $`\pm t/\sqrt{2}`$ and the oscillations in the distribution. A new peak, centered at $`t=0`$, makes its appearance, though for weak decoherence it does not have the usual binomial form. However, some residual effects of interference persist up until just short of the classical limit. In particular, the distribution is broadened, with long “tails,” and displaced somewhat from the central position. This is reflected in our long-time solution for the variance (II.47), which is higher in the quantum case than the classical except in the limit $`p1`$.

In the unitary case, interference effects cause the evolution to “remember” the starting state in a non-intuitive way. As we saw in figure 1, if we start the coin in state $`|R`$, the system retains a linear drift to the right for all time. If we had instead started in the state $`|L`$, the system would have drifted symmetrically to the left. This “memory” also makes the position distribution asymmetric, as we see in fig. 4a.

The presence of decoherence eliminates this effect at long times: the system “forgets” the initial conditions after a while. This effect will still persist at short times, however, and produce a tendency for the particle to move repeatedly in the same direction. No doubt this tendency produces the broadening in the position distribution and the significant tails.

## IV Conclusions

We have examined a possible route from quantum to classical for the quantum random walk: letting the quantum coin undergo decoherence with time. Using the long-time behavior of the position moments as a qualitative marker of classicality, we see that even very weak decoherence changes the growth of the variance from a quadratic to a linear function of time. Since the usual classical random walk has a linear growth of the variance, in a particular sense we can claim that the decoherent walk is indeed classical.

This situation is quite different from the quantum random walk with multiple coins Brun et al. (2002b); for that system, quadratic growth remained except in the limit of a new coin for every step. One might reasonably claim that the multicoin system remains “quantum” even in the limit of very large numbers of coins, while the decoherent system remains “classical” even in the limit of very weak noise.

In spite of this, some effects of interference are important even in the presence of decoherence. In particular, the variance grows more rapidly in the quantum than the classical case. This may reflect a tendency for the particle to be “biased” in one direction for short times, while interference effects enable it to “remember” its starting state. This is consistent with the position distributions, which are broader than the classical binomial distribution, and have nontrivial tails.

In the long time limit, the time dependence of the moments becomes tractable because the evolution superoperator has only one eigenvalue of modulus 1. All other components decay away exponentially with time. It is interesting to speculate whether a decoherence process with several modulus 1 eigenvalues might continue to exhibit quantum behavior. This is probably possible, at least for higher-dimensional coins.

We should emphasize that the system we have studied in this paper has decoherence only in the coin degree of freedom; any effects of decoherence on the particle are indirect. It might be arguably natural to include decoherence in the particle position as well. Such systems have been studied numerically, and exhibit interesting effects of their own Dür et al. (2002); Kendon and Tregenna (2002a, b).

###### Acknowledgements.

We would like to thank Bob Griffiths, Lane Hughston, Viv Kendon, Michele Mosca and Bruce Richmond for useful conversations. TAB acknowledges financial support from the Martin A. and Helen Chooljian Membership in Natural Sciences, and DOE Grant No. DE-FG02-90ER40542. AA was supported by NSF grant CCR-9987845, and by the State of New Jersey. HAC was supported by MITACS, The Fields Institute, and NSERC CRO project “Quantum Information and Algorithms.”


text:
# High-precision ϵ-expansions of massive four-loop vacuum bubbles

## Figure Captions

Figure 1: Four-loop vacuum bubble diagrams.

Figure 2: Three-loop self-mass diagram..

(S. Laporta, High-precision $`ϵ`$-expansions of massive four-loop vacuum bubbles).

.

.

(S. Laporta, High-precision $`ϵ`$-expansions of massive four-loop vacuum bubbles).

.

.

(S. Laporta, High-precision $`ϵ`$-expansions of massive four-loop vacuum bubbles)