text:
# Analysis of Absorbing Times of Quantum Walks

## 1 Introduction

Random walks, or often called Markov chains, on graphs have found a number of applications in various fields, not only in natural science such as physical systems and mathematical modeling of life phenomena but also in social science such as financial systems. Also in computer science, random walks have been applied to various problems such as 2-SAT, approximation of the permanent , and estimation of the volume of convex bodies . Schöning’s elegant algorithm for 3-SAT  and its improvement  are also based on classical random walks. Moreover, one of the most advantageous points of classical random walks as a useful algorithmic tool is that they use only simple local transitions to obtain global properties of the instance.

Thus, it is natural to consider quantum generalization of classical random walks, which may be very useful in constructing efficient quantum algorithms, for which only a few general algorithmic tools have been developed, including Fourier sampling and amplitude amplification. There have been considered two types of quantum walks: one is a discrete-time walk discussed by Watrous , Ambainis, Bach, Nayak, Vishwanath, and Watrous , Aharonov, Ambainis, Kempe, and Vazirani , and Moore and Russell , and the other is a continuous-time one by Farhi and Gutmann , Childs, Farhi, and Gutmann , and Moore and Russell . All of these studies demonstrate that the behaviors of quantum walks are quite different from classical ones. In the theory of classical random walks, one of the important measures is the mixing time, which is the time necessary to have the probability distribution of the particle be sufficiently close to the stationary distribution. Unfortunately, Aharonov, Ambainis, Kempe, and Vazirani  showed a rather negative result that discrete-time quantum walks can be at most polynomially faster than classical ones in view of mixing time. As for continuous-time quantum walks, Farhi and Gutmann  and Childs, Farhi, and Gutmann  claimed that quantum walks propagate exponentially faster than classical ones. Furthermore, a recent result by Child, Cleve, Farhi, Deotto, and Spielman  has shown an example of a black-box problem in which continuous time quantum walks can provide an exponential speedup to all classical algorithms (not necessarily limited to random walks).

This paper focuses on the discrete-time type of quantum walks and introduces two new criteria for propagation speed of discrete-time quantum walks: absorbing probability and absorbing time. A number of properties of quantum walks are investigated in view of these criteria. In particular, the behaviors of Hadamard walks on the line and symmetric walks on the hypercube are discussed through the results of numerical simulation experiments. In our simulations, quantum walks on the hypercube appear exponentially faster than classical ones in absorbing time under certain situations. More precisely, such a speedup would happen in the case the absorbing vertex is located “near” to the antipodal vertex of the initial vertex. Several theoretical analyses are also given on classical and quantum symmetric walks on the hypercube.

The remainder of this paper is organized as follows. Section 2 reviews the formal definition of (discrete-time) quantum walks, and introduces new criteria for propagation speed of quantum walks. Section 3 and Section 4 deal with a number of numerical simulations on Hadamard walks on the line and symmetric walks on the hypercube, respectively. Section 5 gives several theoretical analyses on symmetric walks on the hypercube. Finally, we conclude with Section 6, which summarizes our results.

## 2 Definitions

In this section, we give a formal definition of quantum walks. As mentioned in the previous section, there exist two types of quantum generalizations of classical random walks: discrete-time quantum walks and continuous-time quantum walks. Here we only give a definition of discrete-time ones, which this paper treats. We also introduce new criteria of absorbing probability and absorbing time for propagation speed of quantum walks.

### 2.1 Discrete-Time Walks

In direct analogy to classical random walks, one may try to define quantum walks as follows: at each step, the particle moves in all directions with equal amplitudes. However, such a walk is impossible for a discrete-time model since the evolution of whole quantum system would not be always unitary. Indeed Meyer  proved the impossibility of such discrete-time quantum walks on a lattice. Here we review the definition of discrete-time quantum walks on graphs according to .

Let $`G=(V,E)`$ be a graph where $`V`$ is a set of vertices and $`E`$ is a set of edges. For theoretical convenience, we assume that $`G`$ is $`d`$-regular (i.e. each vertex of the graph $`G`$ is connected to exactly $`d`$ edges). For each vertex $`vV`$, label each edge connected to this vertex with a number between $`1`$ and $`d`$ such that, for each $`a\{1,\mathrm{},d\}`$, the directed edges labeled $`a`$ form a permutation. In other words, for each vertex $`vV`$, not only label each outgoing edge $`(v,w)E`$ with a number between $`1`$ and $`d`$ but also label each incoming edge $`(w,v)E`$ with a number between $`1`$ and $`d`$, where $`w`$ is a vertex in $`V`$ and $`wv`$. In the case that $`G`$ is a Cayley graph, the labeling of a directed edge simply corresponds to the generator associated with the edge. An example of a Cayley graph and its labeling are in Figure 1.

Let $`_V`$ be the Hilbert space spanned by $`\{|vvV\}`$, and let $`_A`$ be the auxiliary Hilbert space spanned by $`\{|a1ad\}`$. We think of this auxiliary Hilbert space as a “coin space”.

###### Definition 1 ()

Let $`C`$ be a unitary operator on $`_A`$ which we think of as a “coin-tossing operator”, and let a shift operator $`S`$ on $`_A_V`$ be defined as $`S|a,v=|a,w`$ where $`w`$ is the $`a`$th neighbor of vertex $`v`$. One step of transition of the quantum walk on the graph $`G`$ is defined by a unitary operator $`W=S(CI_V)`$ where $`I_V`$ is the identity operator on $`_V`$. We call such a walk a discrete-time quantum walk.

More generally, we relax the restriction on the exact form of the quantum walk operator $`W`$ and define general quantum walks such that $`W`$ respects only the structure of the graph $`G`$. In other words, we require that, in the superposition $`W|a,v`$ for each $`a\{1,\mathrm{},d\}`$ and $`vV`$, only basis states $`|a^{},v^{}`$ for $`a^{}\{1,\mathrm{},d\},v^{}\mathrm{neighbor}(v)\{v\}`$ have non-zero amplitudes, where $`\mathrm{neighbor}(v)`$ is the set of vertices adjacent to $`v`$. Thus the graph $`G`$ does not need to be $`d`$-regular and the particle at $`v`$ in the quantum walk moves to one of the vertices adjacent to $`v`$ or stays at $`v`$ in one step.

### 2.2 Criteria of Propagation Speed

One of the properties of random or quantum walks we investigate is how fast they spread over a graph. In order to evaluate it, a criterion “mixing time” has been considered traditionally. However, Aharonov, Ambainis, Kempe, and Vazirani  showed that, in view of mixing time, discrete-time quantum walks can be at most polynomially faster than classical ones. To seek the possibility of quantum walks being advantageous to classical ones, this paper introduces another two new criteria of propagation speed of quantum walks: absorbing probability and absorbing time. Let us consider the set of absorbing vertices such that the particle is absorbed if it reaches a vertex in this set. This is done by considering a measurement that is described by the projection operators over $`_A_V`$: $`P=I_A_{v\mathrm{absorb}(V)}|vv|`$ and $`P^{}=I_A_{v\mathrm{absorb}(V)}|vv|`$, where $`\mathrm{absorb}(V)V`$ is the set of the absorbing vertices and $`I_A`$ is the identity operator over $`_A`$.

By using density operators, one step of transition of a discrete-time quantum walk can be described by a completely positive (CP) map $`\mathrm{\Lambda }`$ as follows:

$$\mathrm{\Lambda }:\rho \rho ^{}=IP\rho PI+WP^{}\rho P^{}W^{},$$

where $`\rho `$ and $`\rho ^{}`$ are density operators over the entire system of the quantum walk, $`W`$ is a unitary operator corresponding to one step of transition of the quantum walk, and $`I`$ is the identity operator on $`_A_V`$.

Now, we give a formal definition of absorbing probability.

###### Definition 2

Absorbing probability of a quantum walk is the probability that the particle which starts at the initial vertex eventually reaches one of the absorbing vertices. More formally, it is defined as

$$𝑃𝑟𝑜𝑏=\underset{t=0}{\overset{\mathrm{}}{}}p(t),$$

where $`p(t)`$ is the probability that the particle reaches one of the absorbing vertices at time $`t`$ for the first time.

Let $`|\psi _0`$ be the initial state of the system, and let $`\rho _0=|\psi _0\psi _0|`$. Then $`p(t)=\mathrm{tr}(\mathrm{\Lambda }^t(\rho _0)P)\mathrm{tr}(\mathrm{\Lambda }^{t1}(\rho _0)P)`$ since $`\mathrm{tr}(\mathrm{\Lambda }^t(\rho _0)P)`$ and $`\mathrm{tr}(\mathrm{\Lambda }^{t1}(\rho _0)P)`$ are the probabilities that the particle is absorbed by the time $`t`$ and $`t1`$, respectively. Here we allowed a little abuse of a notation $`\mathrm{\Lambda }`$ such that $`\mathrm{\Lambda }^2(\rho )=\mathrm{\Lambda }(\mathrm{\Lambda }(\rho ))`$, $`\mathrm{\Lambda }^3(\rho )=\mathrm{\Lambda }(\mathrm{\Lambda }^2(\rho ))`$, …, $`\mathrm{\Lambda }^t(\rho )=\mathrm{\Lambda }(\mathrm{\Lambda }^{t1}(\rho ))`$, and so on.

Next, we give a formal definition of nominal absorbing time.

###### Definition 3

Nominal absorbing time of a quantum walk is the expected time to have the particle which starts at the initial vertex eventually reach one of the absorbing vertices. More formally, it is defined as

$$𝑇𝑖𝑚𝑒_{\mathrm{nom}}=\underset{t=0}{\overset{\mathrm{}}{}}tp(t),$$

where $`p(t)`$ is the probability that the particle reaches one of the absorbing vertices at time $`t`$ for the first time.

Even though nominal absorbing time is bounded polynomial in the size of the graph instance, the quantum walk may not be efficient from a viewpoint of computational complexity if absorbing probability is exponentially small, because we need repeating the walk $`O(1/p)`$ times to have a total absorption probability of $`O(1)`$ in the case the probability of absorption is $`p`$. Thus we cannot regard nominal absorbing time as a criterion of how fast a quantum walk spreads over a graph. Instead, we use the following real absorbing time as a criterion of the propagation speed of quantum walks.

###### Definition 4

Real absorbing time of a quantum walk is defined as

$$𝑇𝑖𝑚𝑒_{\mathrm{real}}=\frac{𝑇𝑖𝑚𝑒_{\mathrm{nom}}}{𝑃𝑟𝑜𝑏}=\frac{_{t=0}^{\mathrm{}}tp(t)}{_{t=0}^{\mathrm{}}p(t)},$$

where $`p(t)`$ is the probability that the particle reaches one of the absorbing vertices at time $`t`$ for the first time.

In what follows, we may refer to this real absorbing time as absorbing time in short, when it is not confusing.

## 3 Hadamard Walks on the Line

### 3.1 The Model

We start with the model of discrete-time quantum walks on the line, which was introduced and discussed by Ambainis, Bach, Nayak, Vishwanath, and Watrous . Note that the line can be regarded as a Cayley graph of the Abelian group $``$ with generators $`+1`$ and $`1`$, denoted by “$`\mathrm{R}`$” and “$`\mathrm{L}`$”, respectively. Thus, the shift operator $`S`$ is defined as

$$\begin{array}{ccc}S|\mathrm{R},v\hfill & =& |\mathrm{R},v+1,\hfill \\ S|\mathrm{L},v\hfill & =& |\mathrm{L},v1,\hfill \end{array}$$

where $`v`$ is the vertex at which the particle is located.

Recall that the particle doing a classical random walk determines a direction to move randomly at each step. In the quantum case, therefore, it is quite natural to set a coin-tossing operator $`C`$ as the Hadamard operator

$$H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill 1\end{array}\right).$$

We call this quantum walk an Hadamard walk on the line. A number of properties were shown in  on this model, including several different aspects of Hadamard walks from their classical counterparts.

This paper considers the following process for some fixed $`m`$ , which is slightly different from the model above.

1. Initialize the system in the state $`|\text{R},0`$, that is, let the particle be located at vertex $`0`$ at time $`0`$, with the chirality being R.
2. 1. Apply $`W=S(HI_{})`$.
    2. Measure the system according to $`\{\mathrm{\Pi }_m,\mathrm{\Pi }_m^{}\}`$ such that $`\mathrm{\Pi }_m=I_2|mm|`$ and $`\mathrm{\Pi }_m^{}=I_2(I_{}|mm|)`$, where $`I_2`$ is the two-dimensional identity operator (i.e. measure the system to observe whether the particle is located at the vertex $`m`$ or not).
3. If the particle is observed to be located at the vertex $`m`$ after the measurement, the process terminates, otherwise it repeats Step 2.

### 3.2 Numerical Simulations

Let $`r_m`$ be absorbing probability that the particle is eventually absorbed by the boundary at the vertex $`m`$. Figure 2 illustrates the relation between $`m`$ (in $`x`$-axis) and $`r_m`$ (in $`y`$-axis). From Figure 2, we conjecture that $`lim_m\mathrm{}r_m=1/2`$.

Next, let us consider a more general model of Hadamard walks whose coin-tossing operator is defined as the matrix

$$H_p=\left(\begin{array}{cc}\sqrt{p}& \sqrt{1p}\\ \sqrt{1p}& \sqrt{p}\end{array}\right),$$

instead of $`H`$. Figure 3 illustrates the relation between $`p`$ (in $`x`$-axis) and $`lim_{n+\mathrm{}}r_m`$ (in $`y`$-axis) for these generalized Hadamard walks.

Although we have not yet derived a closed form for $`r_m`$, we conjecture the following.

###### Conjecture 1

For a generalized Hadamard walk with a coin-tossing operator $`H_p`$,

$$\underset{m\mathrm{}}{lim}r_m=\frac{\mathrm{sin}^1(2p1)}{\pi }+\frac{1}{2}.$$

Remark This conjecture was proved very recently by Bach, Coppersmith, Goldschen, Joynt, and Watrous .

## 4 Symmetric Walks on the $`n`$-Dimensional Hypercube

### 4.1 The Model

Next we consider the discrete-time quantum walks on the graph $`G`$ of the $`n`$-dimensional hypercube, which was introduced and discussed by Moore and Russell . Note that the $`n`$-dimensional hypercube can be regarded as a Cayley graph of the Abelian group $`_2^n`$ with generators $`g_1,g_2,\mathrm{},g_n`$ such that $`g_1^2=g_2^2=\mathrm{}=g_n^2=e`$. Thus, the shift operator $`S`$ is defined as $`S|a,v=|a,vg_a`$, where $`a\{1,\mathrm{},n\}`$ is a label and $`v_2^n`$ is a vertex at which the particle is located. Figure 4 illustrates the case with the $`3`$-dimensional hypercube.

A coin-tossing operator $`C`$ is set as the Grover’s diffusion operator :

$$D=\left(\begin{array}{cccc}\frac{2}{n}1& \frac{2}{n}& \mathrm{}& \frac{2}{n}\\ \frac{2}{n}& \frac{2}{n}1& \mathrm{}& \frac{2}{n}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ \frac{2}{n}& \frac{2}{n}& \mathrm{}& \frac{2}{n}1\end{array}\right).$$

Notice that coin-tossing operators in this model should obey the permutation symmetry of the hypercube. Among such operators, the Grover’s diffusion operator is the one farthest away from the identity operator under the standard operator norm (see  for detailed discussions). We call this quantum walk a symmetric walk on the $`n`$-dimensional hypercube. A number of properties were shown in  on the mixing time of this model in comparison with the classical case.

The process of this quantum walk is defined as follows:

1. Initialize the system in the state $`|1,0`$. That is, let the particle be located at the vertex $`0`$ at time $`0`$, with the labeling being $`1`$.
2. For every chosen number $`t`$ of steps, apply $`W^t`$ to the system, where $`W=S(DI_{_2^n})`$, and then observe the location of the particle.

### 4.2 Numerical Simulations

Figure 5 illustrates the relation between the dimension $`n`$ of the hypercube (in $`x`$-axis) and absorbing time of quantum walks (in $`y`$-axis). One can see that, if the absorbing vertex is located at random, absorbing time averaged over all choices of the absorbing vertex increases exponentially with respect to $`n`$. This is similar to the classical case for which the absorbing time is theoretically analyzed in the next section. However, if the absorbing vertex is located at $`(1,1,\mathrm{},1)`$, absorbing time seems to increase polynomially (quadratically, more precisely) with respect to $`n`$. This may suggest a striking contrast between quantum and classical symmetric walks on the $`n`$-dimensional hypercube that propagation between a particular pair of vertices is exponentially faster in the quantum case.

Table 1 shows the relation between (nominal and real) absorbing time of the quantum walk on the $`8`$-dimensional hypercube and Hamming distance between the initial vertex and the absorbing vertex. One can see the following:

* absorbing probability is large if the absorbing vertex is located near the initial vertex or is located far from the initial vertex, while it is small if the absorbing vertex is located in the “middle” of the hypercube relative to the initial vertex,
* nominal absorbing time has values of almost the same order except for the trivial case that Hamming distance is $`0`$,
* nominal absorbing time is small, but real absorbing time is large, in the case of small absorbing probability.

In the classical case, the shorter Hamming distance between the initial vertex and the absorbing vertex is, the sooner the particle reaches the absorbing vertex, which meets our intuition. In the quantum case, however, our simulation result above is quite counter-intuitive.

From our simulation results illustrated by Figure 5 and Table 1, we conjecture the following for the quantum case.

###### Conjecture 2

Absorbing probability of quantum walks on the $`n`$-dimensional hypercube is $`\mathrm{min}\{1,\frac{n}{\left(\genfrac{}{}{0pt}{}{n}{i}\right)}\}`$, where $`i`$ represents Hamming distance between the initial vertex and the absorbing vertex.

###### Conjecture 3

Nominal absorbing time of quantum walks on the $`n`$-dimensional hypercube is $`O(n^2)`$ independent of the location of the absorbing vertex, except for the trivial case that the initial vertex is the absorbing vertex.

###### Conjecture 4

Real absorbing time of quantum walks on the $`n`$-dimensional hypercube is $`\frac{n^2n+2}{2}`$ if Hamming distance between the initial vertex and the absorbing vertex is $`1`$, $`O(n^2)`$ if Hamming distance is $`n`$, and $`\mathrm{\Theta }(2^n)`$ if Hamming distance is close to $`\frac{n}{2}`$.

Remark Kempe  recently showed that real absorbing time of quantum walks on the $`n`$-dimensional hypercube is bounded polynomial in $`n`$ if Hamming distance between the initial vertex and the absorbing vertex is $`n`$.

## 5 Theoretical Analyses of Symmetric Walks

### 5.1 Classical Symmetric Walks

First we state a property on the absorbing time of classical symmetric walks on the $`n`$-dimensional hypercube.

###### Proposition 5

Absorbing time of classical symmetric walks on the $`n`$-dimensional hypercube is $`\mathrm{\Theta }(2^n)`$ independent of the location of the absorbing vertex, except for the trivial case that the initial vertex is the absorbing vertex.

Proof.  Recall that the particle doing a classical random walk determines a direction to move randomly at each step. Thus this walk obeys the permutation symmetry of the hypercube and the vertices of the hypercube can be grouped in sets indexed by $`i\{0,\mathrm{},n\}`$, each of which is a set of vertices whose Hamming distance from the initial vertex is $`i`$.

Let $`s_i`$ be absorbing time for the case that Hamming distance between the initial vertex and the absorbing vertex is $`i`$. Then, the following equations are satisfied:

$$\begin{array}{ccc}s_0& =& 0,\hfill \\ s_1& =& \frac{1}{n}s_0+\frac{n1}{n}s_2+1,\hfill \\ s_2& =& \frac{2}{n}s_1+\frac{n2}{n}s_3+1,\hfill \\ & \mathrm{}& \\ s_{n1}& =& \frac{n1}{n}s_{n2}+\frac{1}{n}s_n+1,\hfill \\ s_n& =& s_{n1}+1,\hfill \end{array}A\left(\begin{array}{c}s_0\\ s_1\\ s_2\\ \mathrm{}\\ s_{n1}\\ s_n\end{array}\right)=\left(\begin{array}{c}0\\ 1\\ 1\\ \mathrm{}\\ 1\\ 1\end{array}\right),$$

where

$$A=(a_{ij})=\left(\begin{array}{ccccccc}1& 0& & & & & \\ \frac{1}{n}& 1& \frac{n1}{n}& & & & \\ & \frac{2}{n}& 1& \frac{n2}{n}& & & \\ & & \mathrm{}& \mathrm{}& \mathrm{}& & \\ & & & \mathrm{}& \mathrm{}& \mathrm{}& \\ & & & & \frac{n1}{n}& 1& \frac{1}{n}\\ & & & & & 1& 1\end{array}\right).$$

Let a matrix $`B=(b_{ij})`$ such that

$$b_{ij}=\{\begin{array}{cc}1\hfill & \text{if }j=1,\hfill \\ 0\hfill & \text{if }i=1,j2,\hfill \\ \left(\genfrac{}{}{0pt}{}{n}{j1}\right)_{l=0}^{\mathrm{min}(i,j)2}\frac{1}{\left(\genfrac{}{}{0pt}{}{n1}{l}\right)}\hfill & \text{if }i,j2,\hfill \end{array}$$

and let $`c_{ik}=_{j=1}^{n+1}a_{ij}b_{jk}`$. After some calculations, we have the following.

* In the case $`i=1`$, $`c_{ik}=b_{1k}=1`$ if $`k=1`$, otherwise $`c_{ik}=0`$.
* In the case $`i=n+1`$, $`c_{ik}=b_{nk}+b_{n+1,k}=1`$ if $`k=n+1`$, otherwise $`c_{ik}=0`$.
* In the case $`2in`$, $`c_{ik}=\frac{i1}{n}b_{i1,k}+b_{ik}\frac{ni+1}{n}b_{i+1,k}=1`$ if $`k=i`$, otherwise $`c_{ik}=0`$.

Therefore, $`AB`$ is the identity matrix, and thus $`B=A^1`$. It follows that

$$s_{i1}=\underset{j=2}{\overset{n+1}{}}b_{ij}=\{\begin{array}{cc}0\hfill & \text{if }i=1,\hfill \\ _{j=2}^{n+1}\left(\left(\genfrac{}{}{0pt}{}{n}{j1}\right)_{l=0}^{\mathrm{min}(i,j)2}\frac{1}{\left(\genfrac{}{}{0pt}{}{n1}{l}\right)}\right)\hfill & \text{if }i2.\hfill \end{array}$$

From this, it is obvious that $`s_i`$ increases monotonously with respect to $`i`$. For $`i1`$, we have

$$2^n1=\underset{j=2}{\overset{n+1}{}}\left(\genfrac{}{}{0pt}{}{n}{j1}\right)s_i<3\underset{j=2}{\overset{n+1}{}}\left(\genfrac{}{}{0pt}{}{n}{j1}\right)=3(2^n1),$$

since $`1_{l=0}^{\mathrm{min}(i,j)2}\frac{1}{\left(\genfrac{}{}{0pt}{}{n1}{l}\right)}<3`$. Thus we have the assertion. $`\mathrm{}`$

This result might be counterintuitive in some sense, since the vertices at small Hamming distance, say 1, from the initial vertex may seem easy to find. However, the following will give an intuitive explanation of this behavior: after one step, the probability of going away from the absorbing vertex is $`11/n`$, which is much higher than the probability $`1/n`$ of finding it.

### 5.2 Quantum Symmetric Walks

In our simulation results in the previous section, quantum symmetric walks on the hypercube behave in a manner quite different from classical ones. In particular, it is remarkable that in the quantum case propagation between a particular pair of vertices seems exponentially faster than in the classical case. Here we try to describe absorbing time of quantum symmetric walks on the $`n`$-dimensional hypercube as a function of $`n`$. The results in this subsection do not give a simple characterization of the absorbing time of the quantum walk on the hypercube, but at least simplify its numerical calculation considerably.

The following lemma states that we do not need to keep track of the amplitudes of all basis states for symmetric quantum walks on the hypercube.

###### Lemma 6

For a symmetric quantum walk on the $`n`$-dimensional hypercube with the initial vertex $`o`$, define sets $`\{F_i\}`$ and $`\{B_i\}`$ as follows:

$`F_i`$ $`=`$ $`\{(a,v)\mathrm{Ham}(v,o)=i,\mathrm{Ham}(vg_a,o)=i+1\},`$
$`B_i`$ $`=`$ $`\{(a,v)\mathrm{Ham}(v,o)=i,\mathrm{Ham}(vg_a,o)=i1\},`$
where $`\mathrm{Ham}(x,y)`$ denotes the Hamming distance between $`x`$ and $`y`$. Let two unit vectors $`|f_i`$ and $`|b_i`$ in $`_A_V`$ be defined by

$$\begin{array}{cccc}|f_i\hfill & =& \frac{1}{\sqrt{|F_i|}}\underset{(a,v)F_i}{}|a,v\hfill & \text{for }i=0,\mathrm{},n1,\hfill \\ |b_i\hfill & =& \frac{1}{\sqrt{|B_i|}}\underset{(a,v)B_i}{}|a,v\hfill & \text{for }i=1,\mathrm{},n.\hfill \end{array}$$

Then, a transition step of symmetric quantum walks is given by the following $`2n\times 2n`$ unitary matrix:

$$U_n=\left(\begin{array}{cccccccccc}0& \frac{n2}{n}& \frac{\sqrt{4n4}}{n}& & & & & & & \\ 1& 0& 0& & & & & & & \\ 0& 0& 0& \frac{n4}{n}& \frac{\sqrt{8n16}}{n}& & & & & \\ & \frac{\sqrt{4n4}}{n}& \frac{n2}{n}& 0& 0& & & & & \\ & & & 0& 0& \frac{n6}{n}& \mathrm{}& & & \\ & & & \frac{\sqrt{8n16}}{n}& \frac{n4}{n}& \mathrm{}& \mathrm{}& & & \\ & & & & & \mathrm{}& \mathrm{}& \frac{n2}{n}& \frac{\sqrt{4n4}}{n}& \\ & & & & & \mathrm{}& \frac{n4}{n}& 0& 0& 0\\ & & & & & & & 0& 0& 1\\ & & & & & & & \frac{\sqrt{4n4}}{n}& \frac{n2}{n}& 0\end{array}\right)$$

with the order of bases $`|f_0,|b_1,|f_1,\mathrm{},|b_{n1},|f_{n1},|b_n`$.

Proof.  First, we calculate $`|F_i|`$ and $`|B_i|`$. The number of vertices $`v`$ satisfying $`\mathrm{Ham}(v,o)=i`$ is $`\left(\genfrac{}{}{0pt}{}{n}{i}\right)`$, and for such $`v`$, the number of labels $`a`$ satisfying $`\mathrm{Ham}(vg_a,o)=i+1`$ is $`ni`$. Therefore, the number of basis vectors in $`F_i`$ is $`(ni)\left(\genfrac{}{}{0pt}{}{n}{i}\right)`$. Similarly, the number of basis vectors in $`B_i`$ is $`i\left(\genfrac{}{}{0pt}{}{n}{i}\right)`$.

Now, after applying a coin-tossing operator (which is the Grover’s diffusion operator) to $`|f_i`$, we have

$`(CI)|f_i`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{|F_i|}}}{\displaystyle \underset{(a,v)F_i}{}}\left({\displaystyle \frac{2}{n}}{\displaystyle \underset{1bn}{}}|b,v|a,v\right)`$
$`=`$ $`{\displaystyle \frac{1}{\sqrt{|F_i|}}}\left({\displaystyle \frac{2(ni)}{n}}{\displaystyle \underset{(a,v)B_i}{}}|a,v+{\displaystyle \frac{n2i}{n}}{\displaystyle \underset{(a,v)F_i}{}}|a,v\right).`$
Then, the shift operator is applied to this vector to have

$`S(CI)|f_i`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{|F_i|}}}\left({\displaystyle \frac{2(ni)}{n}}{\displaystyle \underset{(a,v)F_{i1}}{}}|a,v+{\displaystyle \frac{n2i}{n}}{\displaystyle \underset{(a,v)B_{i+1}}{}}|a,v\right)`$ (1)
$`=`$ $`\sqrt{{\displaystyle \frac{|F_{i1}|}{|F_i|}}}{\displaystyle \frac{2(ni)}{n}}|f_{i1}+\sqrt{{\displaystyle \frac{|B_{i+1}|}{|F_i|}}}{\displaystyle \frac{n2i}{n}}|b_{i+1}`$
$`=`$ $`{\displaystyle \frac{\sqrt{4ni4i^2}}{n}}|f_{i1}+{\displaystyle \frac{n2i}{n}}|b_{i+1}.`$
Similarly, the coin-tossing operator and shift operator are applied in sequence to the state $`|b_i`$ to have

$$S(CI)|b_i=\frac{n2i}{n}|f_{i1}+\frac{\sqrt{4ni4i^2}}{n}|b_{i+1}.$$
(2)
The lemma holds immediately from (1) and (2). $`\mathrm{}`$

The following is immediate from Lemma 6.

###### Corollary 7

One step of transition of symmetric quantum walks on the $`n`$-dimensional hypercube with the absorbing vertex located at $`(1,1,\mathrm{},1)`$ is described by a CP map $`\mathrm{\Lambda }:\rho _t\rho _{t+1}=U_nP_n^{}\rho _tP_n^{}U_n^{}+I_nP_n\rho _tP_nI_n`$, where $`\rho _t`$ and $`\rho _{t+1}`$ are density operators of the system at time $`t`$ and $`t+1`$, respectively, $`I_n`$ is the $`2n\times 2n`$ identity matrix, $`P_n`$ is a $`2n\times 2n`$ projection matrix whose $`(2n,2n)`$-element is 1 and all the others are 0, and $`P_n^{}=I_nP_n`$.

By this corollary, we can do numerical simulations for much larger $`n`$, say $`n=500`$. Figure 6 illustrates the relation between the dimension $`n`$ of the hypercube (in $`x`$-axis) and absorbing time of quantum walks (in $`y`$-axis) for larger $`n`$. One can see that absorbing time is close to $`1.25n^{1.5}`$.

In what follows, we focus on the case that the absorbing vertex is at $`(1,1,\mathrm{},1)`$.

Since both absorbing probability and nominal absorbing time are defined as power series, and time evolution of the quantum walk is described by a CP map (hence by a linear operator), it is significant to investigate the properties of the matrix corresponding to time evolution operator and its eigenvalues in order to study behaviors of absorbing time with respect to the dimension $`n`$. First, we prove the following lemma.

###### Lemma 8

Every eigenvalue of $`U_nP_n^{}`$ has its absolute value of less then $`1`$, where $`P_n^{}=I_nP_n`$.

Proof.  It is obvious that every eigenvalue of $`U_nP_n^{}`$ has its absolute value of at most $`1`$.

Suppose that there exists an eigenvalue $`\lambda `$ of $`U_nP_n^{}`$ such that $`|\lambda |=1`$. Let $`𝒆`$ be the eigenvector of $`U_nP_n^{}`$ corresponding to $`\lambda `$. Then the $`2n`$th element of $`𝒆`$ is $`0`$ and $`P_n^{}𝒆=𝒆`$, since applying the projection operator $`P_n^{}`$ changes the $`2n`$th element of $`𝒆`$ into $`0`$ and $`|\lambda |=1`$. Thus we have $`U_n𝒆=\lambda 𝒆`$, which implies that $`𝒆`$ is an eigenvector of $`U_n`$. However, it is easy to check by calculation that, in every eigenvector of $`U_n`$, the $`2n`$th element of it is not $`0`$, which is a contradiction. $`\mathrm{}`$

By using Lemma 8, exact values of absorbing probability and absorbing time can be described for quantum walks on the $`n`$-dimensional hypercube with the absorbing vertex located at $`(1,1,\mathrm{},1)`$.

###### Proposition 9

Let $`X_n`$ be the $`2n\times 2n`$ symmetric matrix satisfying $`X_nU_nP_n^{}X_nP_n^{}U_n^{}=\rho _0`$, where $`P_n^{}=I_nP_n`$ and $`\rho _0`$ is the initial density operator of a $`2n\times 2n`$ matrix whose $`(1,1)`$-element is $`1`$ and all the other elements are $`0`$. Then the absorbing time of quantum walks on the $`n`$-dimensional hypercube with the absorbing vertex located at $`(1,1,\mathrm{},1)`$ is $`\mathrm{tr}X_n1`$.

Proof.  Let $`p(t)`$ denote the probability that the particle reaches the absorbing vertex $`(1,1,\mathrm{},1)`$ at time $`t`$ for the first time. Then we have

$`p(t)`$ $`=`$ $`\mathrm{tr}\left((U_nP_n^{})^t\rho _0(P_n^{}U_n^{})^tP_n\right)`$
$`=`$ $`\mathrm{tr}\left((U_nP_n^{})^t\rho _0(P_n^{}U_n^{})^t(U_nP_n^{})^{t+1}\rho _0(P_n^{}U_n^{})^{t+1}\right).`$
From Lemma 8, both absorbing probability and nominal absorbing time are convergent series. Thus we have the following.

$$\begin{array}{c}\begin{array}{c}𝑃𝑟𝑜𝑏=\underset{t=0}{\overset{\mathrm{}}{}}p(t)=\underset{t=0}{\overset{\mathrm{}}{}}\mathrm{tr}\left((U_nP_n^{})^t\rho _0(P_n^{}U_n^{})^t(U_nP_n^{})^{t+1}\rho _0(P_n^{}U_n^{})^{t+1}\right)\hfill \\ =\mathrm{tr}\rho _0=1,\hfill \end{array}\hfill \\ \\ \begin{array}{c}𝑇𝑖𝑚𝑒_{\mathrm{nom}}=\underset{t=0}{\overset{\mathrm{}}{}}tp(t)=\underset{t=0}{\overset{\mathrm{}}{}}t\mathrm{tr}\left((U_nP_n^{})^t\rho _0(P_n^{}U_n^{})^t(U_nP_n^{})^{t+1}\rho _0(P_n^{}U_n^{})^{t+1}\right)\hfill \\ =\mathrm{tr}\left(\underset{t=0}{\overset{\mathrm{}}{}}(U_nP_n^{})^{t+1}\rho _0(P_n^{}U_n^{})^{t+1}\right)=\mathrm{tr}(U_nP_n^{}X_nP_n^{}U_n^{})=\mathrm{tr}X_n1.\hfill \end{array}\hfill \end{array}$$

It follows that real absorbing time is $`\mathrm{tr}X_n1`$. $`\mathrm{}`$

Another characterization of values of the absorbing time is given by the following proposition.

###### Proposition 10

Let $`f_n(x)`$ be a power series of $`x`$ defined as

$$f_n(x)=\underset{t=0}{\overset{\mathrm{}}{}}a_tx^t=\frac{2^{n1}(n1)!}{n^{n1}}\frac{x^{n+1}}{det(xI_nU_nP_n^{})}.$$

Then the absorbing time of quantum walks on the $`n`$-dimensional hypercube with the absorbing vertex located at $`(1,1,\mathrm{},1)`$ is $`_{t=0}^{\mathrm{}}t|a_t|^2`$.

Proof.  Let $`b_n|=(0\mathrm{}01)`$ and $`|f_0=(10\mathrm{}0)^T`$. Then $`b_n|(U_nP_n^{})^t|f_0`$ gives the amplitude that the particle reaches the absorbing vertex $`(1,1,\mathrm{},1)`$ at time $`t`$ for the first time. Consider a power series of $`x`$, $`g_n(x)=_{t=0}^{\mathrm{}}b_n|(U_nP_n^{})^t|f_0x^t`$. We prove that this $`g_n(x)`$ is equivalent to $`f_n(x)`$.

Note that $`g_n(x)=(0\mathrm{}01)(_{t=0}^{\mathrm{}}(xU_nP_n^{})^t)(10\mathrm{}0)^T`$, which is equal to the $`(2n,1)`$-element of $`(I_nxU_nP_n)^1`$. Thus we have for $`x0`$,

$$g_n(x)=\frac{x^{2n}}{det\left(xI_nU_nP_n^{}\right)}(1)^{2n+1}\mathrm{\Delta }_{1,2n},$$

where $`\mathrm{\Delta }_{1,2n}`$ is a minor of $`xI_nU_nP_n^{}`$ with respect to $`(1,2n)`$.

It is straightforward to show that $`\mathrm{\Delta }_{1,2n}=\frac{2^{n1}(n1)!}{n^{n1}}\frac{1}{x^{n1}}`$, and thus

$$g_n(x)=\frac{2^{n1}(n1)!}{n^{n1}}\frac{x^{n+1}}{det\left(xI_nU_nP_n^{}\right)}=f_n(x).$$

By the definition of $`g_n(x)`$, each coefficient $`a_t`$ of $`x^t`$ in the power series $`f_n(x)`$ corresponds to the amplitude that the particle reaches the absorbing vertex $`(1,1,\mathrm{},1)`$ at time $`t`$ for the first time. Since the absorbing probability is $`1`$ from the proof of Proposition 9, the real absorbing time is $`𝑇𝑖𝑚𝑒_{\mathrm{real}}=_{t=0}^{\mathrm{}}t|a_t|^2`$. $`\mathrm{}`$

## 6 Conclusions

This paper focused on the absorbing probability and time of quantum walks through numerical simulations and theoretical analyses on Hadamard walks on the line and symmetric walks on the hypercube.

In our numerical simulations, quantum walks behaved in manners quite different from classical walks. In particular, quantum walks on the hypercube appeared exponentially faster than classical ones in absorbing time under certain situations. For some of our conjectures based on these numerical results, recent papers  subsequent to ours have given theoretical proofs.

As for our theoretical analyses on symmetric walks on the hypercube, the authors believe that they are quite useful in simplifying numerical calculations of the absorbing time of them.

## Acknowledgements

The authors would like to thank Jun Hasegawa and Takashi Yamada for their help in our numerical simulations. The authors would also like to thank anonymous referees for their helpful comments.


format: text

text:
# Pulling Knotted Polymers

## Abstract

We compare Monte Carlo simulations of knotted and unknotted polymers whose ends are connected to two parallel walls. The force $`f`$ exerted on the polymer is measured as a function of the separation $`R`$ between the walls. For unknotted polymers of several monomer numbers $`N`$, the product $`fN^\nu `$ is a simple function of $`R/N^\nu `$, where $`\nu 0.59`$. By contrast, knotted polymers exhibit strong finite size effects which can be interpreted in terms of a new length scale related to the size of the knot. Based on this interpretation, we conclude that the number of monomers forming the knot scales as $`N^t`$, with $`t=0.4\pm 0.1`$.

Entanglements are unavoidable in long polymers and influence their properties catenanes . Knots are found in proteins taylor , and present an obstacle that needs to be overcome in the transcription of DNA alberts . An increasing number of experiments can now probe the detailed properties of knotted molecules dna . Micro–manipulation techniques mechsing  enable direct measurements of mechanical properties of a single molecule, and it is even possible to probe the behavior of artificially knotted DNA arai . However, incorporation of topological constraints into the statistical mechanics of polymers topcon  remains a difficult theoretical challenge since the resulting partition of phase space into accessible and inaccessible regions cannot be easily implemented. Nevertheless, some progress has been made in understanding the role of knots in loop polymers; e.g. the relative probabilities for appearance of different knots in self–avoiding (SA) loops knotprob  has been characterized. However, much less is known about the typical shapes and physical properties of knots.

As a topological feature, a knot can be rigorously identified only by specifying the entire shape of a closed chain (ring). However, it is natural to identify a segment where the knot is located, and consequently to talk about its size and statistics. It is natural to pull on the ends of a string to see if a small knot remains in the middle. Our eyes tend to identify knotted segments in this manner, as exemplified by the grey–shaded monomers of the polymers in Fig. 1. While pulling on a string makes tight knots, the question of whether in a random unforced chain the knot is spread over the whole curve, or localized (tight) on a small portion, is still not fully resolved. Several recent works metzler  show that knots in SA walks confined to a two-dimensional (2D) plane are strongly localized, i.e. the mean number of monomers in the knotted region $`N_k`$ does not depend on the total number of monomers $`N`$. Studies of three–dimensional (3D) knotted polymers are hampered by the difficulty of identifying the knotted region. Katritch et al. katritch  examined the size distribution of knots in 3D random rings, by removing segments of the ring, attaching them to infinite straight lines, and checking if the resulting structures were knotted. Although the method has a certain probability to fail (i.e., the procedure itself may create or remove a knot), it nevertheless suggests that knots in such rings are localized. By contrast, some studies largeknots  had earlier indicated that for moderate $`N`$, the radius of gyration $`R_g`$ of a knot is strongly influenced by its complexity, leading to the conclusion that the knots might be spread out over the entire loop stretch . More recent numerical results janse ; orlandini  provide evidence that $`R_g`$ is asymptotically independent of the knot type, hinting that knots are localized.

Since correlation functions of SA walks are power laws, it is reasonable to expect that the distribution of the number of monomers $`n`$ forming a knot is also a power law, i.e. $`p(n)=Cn^{t2}`$. For $`t<1`$ the normalization coefficient $`C`$ is determined by the microscopic (short distance) properties of the chain, while for $`0<t<1`$, the expectation value of the mean knot size $`N_k`$ depends on the total length, growing as $`N^t`$. In such a case, we say that the knot is weakly localized. For $`t<0`$, the knot is strongly localized in the sense that $`N_k`$ is determined by the microscopic cutoff. In this paper, we attempt to quantify the tightness of knots in 3D polymers by comparing the force–extension relations of knotted and unknotted chains. As in Ref. orlandini , we find similarities between the statistical properties of knotted chains and those of shorter unknotted chains, a consequence of the fact that knotted segments are statistically denser than unknotted ones. Using the reduction in the effective number of monomers as an operational definition of knot size, we find $`N_kN^t`$, with $`t=0.4\pm 0.1`$.

Much of the current understanding of the scaling properties of long polymers is based on renormalization group ideas rgpolymers . The $`N\mathrm{}`$ limit in polymers corresponds to approaching a fixed point similar to that describing criticality in thermal phase transitions. In particular, it can be shown that for a polymer with either free ends or forming a closed loop (without any further restrictions on topology)

$$R_g=aN^\nu \mathrm{\Phi }(\frac{N_0}{N},\frac{N_1}{N},\mathrm{})AaN^\nu \left[1BN^\mathrm{\Delta }\right],$$
(1)
where $`a`$ is a microscopic length–scale (of the order of monomer diameter or bond length), while $`\nu 0.59`$ (in 3D) is a system independent (universal) exponent. The function $`\mathrm{\Phi }`$ includes corrections to the leading power–law due to irrelevant variables, which can be interpreted as additional length scales $`\{N_i\}`$. Keeping only the largest such correction for large $`N`$ leads to the second part of the above equation. The dimensionless constants $`A`$ and $`B`$ are again system specific, while $`\mathrm{\Delta }0.5`$ in 3D is universal rgpolymers . If the leading correction comes from, say, the argument $`N_0/N`$ of $`\mathrm{\Phi }`$, the corresponding length–scale grows as $`N_0N^{t_0}`$, with $`\mathrm{\Delta }=1t_0`$.

For very long polymers, the correction term in Eq. (1) is irrelevant, and the dependence of many physical properties on the number of monomers $`N`$ can be cast in terms of a dependence on $`R_g`$ degennes . For example, consider the force $`f`$ needed to stretch a polymer between two parallel walls at a distance $`R`$. We can construct two dimensionless quantities, $`fR_g/k_BT`$ and $`R/R_g`$ ($`T`$ is the temperature and $`k_B`$ is the Boltzmann constant), which must be functionally related. It is thus convenient to introduce variables $`f^{}faN^\nu /k_BT`$ and $`R^{}R/aN^\nu `$, and express the force–extension relation in the form

$$f^{}=G(R^{}).$$
(2)
Simple arguments degennes  can now be used to determine the asymptotic behaviors of $`G(R^{})`$: For a large stretching force, the distance $`R`$ between the ends of the polymer must be proportional to $`N`$. Conversely, in a strongly compressed state ($`RR_g`$), the force must be proportional to $`N`$. These limiting behaviors can be reconciled with Eq. (2) only if degennes

$$G(R^{})\{\begin{array}{cc}R_{}^{}{}_{}{}^{\nu /(1\nu )}\hfill & \mathrm{for}\mathrm{R}^{}1,\hfill \\ R_{}^{}{}_{}{}^{11/\nu }\hfill & \mathrm{for}\mathrm{R}^{}1.\hfill \end{array}$$
(3)
In the large force regime this gives $`RaN(fa/k_BT)^{(1\nu )/\nu }=aN_b^\nu (N/N_b)`$ (omitting dimensionless prefactors), with $`N_b(k_BT/fa)^{1/\nu }`$. Thus, the polymer can be viewed as a linear sequence of $`N/N_b`$ blobs, each of size $`aN_b^\nu `$ and consisting of $`N_b`$ monomers pincus . On length–scales smaller than the blob size, the external forces are not significant, while on the length–scales larger the polymer is essentially linear. (An analogous blob picture is also available for the compressed regime degennes .)

We employed Monte Carlo (MC) simulations to measure such force–extension relations. Our model chains were composed of hard spheres of diameter $`0.75a`$ connected by “tethers” restricting the distance between adjacent spheres to be smaller than $`a`$, with no additional energy costs. The end–monomers were fixed to two infinite parallel walls a distance $`R`$ apart. An elementary MC step consisted of an attempt to move a randomly chosen sphere a distance $`0.16a`$ in a random direction. ($`N`$ such attempts constitute one MC time unit.) With such parameters the chain cannot cross itself, and its topology is preserved by the impenetrable walls. The force $`f`$ was calculated from the probability densities of contacts between spheres, and the probability densities of having stretched tethers, as described in Ref. farago .

We studied chains of lengths $`N=225`$, 335, 500, and 750, in both unknotted (simply connected), and knotted (connected via a single trefoil) states remark . Fig. 1 depicts two different configurations of the knotted chains, where the region in which the knot is “concentrated” has been lighter shaded. For each $`R`$ and $`N`$ our simulations lasted about $`10^8`$ MC time units, which is considerably longer than the estimated Rouse relaxation time doi\_edwards . We verified that during the relaxation period the knot is able to diffuse from one side to the other. Open and closed symbols in Fig. 2 depict the results for unknotted and knotted chains, respectively.

It is important to note that the usual derivation of Eqs. (1)-(3) is not for a specified polymer topology, but rather for an ensemble of polymers that includes all possible topologies. However, relations of this type are also likely to be valid for polymers of fixed topology, albeit with a different scaling function in Eq. (1). The collapse of the data for unknotted polymers (open symbols) of different lengths in Fig. 2 confirms this expectation. Indeed, the quality of the collapse indicates that subleading corrections are negligble for $`R^{}<2`$. We have taken advantage of this observation to construct an analytic fit to the scaling function $`G`$, as depicted by the solid line in this figure. For $`R^{}>2`$ the polymer with $`N=335`$ forms more than six blobs, each containing less than 55 monomers. For such small blobs, finite size effects begin to appear, as we observe a roughly 10% deviation in the right–most data points in Fig. 2. Note that a deviation of this magnitude is expected from Eq. 1, with $`B1`$.

As expected, for a given $`f^{}`$ the knotted polymer (solid symbols in Fig. 2) has a significantly smaller $`R^{}`$ than its unknotted counterpart. However, the scaled difference becomes less pronounced for larger $`N`$, and the results for longer chains approach those of the unknotted chain. The absence of data collapse indicates the appearance of strong finite size corrections in a parameter range where the unknotted chains show no such effect. We would like to associate this feature with the emergence of a new size scale due to the knot. If a string with a knot is fully stretched, its maximal length is reduced by the size of the resulting tight knot. While the knots in our simulations are far from tight, we shall still describe the influence of the knot as a reduction in the number of monomers $`N`$ by the ‘size of the knot’ $`N_k`$. If the knotted chain of length $`N`$ is equivalent to an unknotted chain of length $`NN_k`$, its force–extension curves must satisfy $`fa(NN_k)^\nu /k_BT=G[R/a(NN_k)^\nu ]`$, where $`G`$ is the scaling function obtained before for unknotted polymers (solid line in Fig. 2). Naturally, this definition will not work with a single $`N_k`$, since our knots are not tight. However, each solid data point in Fig. 2 can be moved to the previously obtained solid line by choosing an appropriate $`N_k(f^{},N)`$. This can be regarded as our operational definition of the size of the knot for a given $`f`$ and $`N`$.

If the force–extension curves for knotted polymers are to be consistent with the standard finite size corrections discussed in connection with Eq. (1), we must have

$$f^{}=G_k(R^{},\frac{N_0}{N},\mathrm{})G(R^{})\left[1+g(R^{})N^{\mathrm{\Delta }_k}\right].$$
(4)
Based on the numerical results, we have assumed that the leading scaling function $`G`$ is the same for knotted and unknotted polymers, but allowed for different corrections, such as a new exponent $`\mathrm{\Delta }_k`$. For Eq. (4) to be consistent with our definition of knot size, we must have $`N_k(f^{},N)=H(f^{})N^t`$. The exponent $`t=1\mathrm{\Delta }_k`$ gives the scaling of the number of monomers in a knot (in the absence of force) via $`N_kN^t`$. General scaling considerations do not restrict the shape of $`H(f^{})`$. However, from the “blob picture” of a strongly stretched chain, we know that the polymer is essentially linear beyond the blob size $`N_b`$ (and consequently not knotted on such scale), while within a blob it is undisturbed by the external forces. We thus expect the knot size to be determined by $`N_b`$ (as if this is the entire length of the polymer), i.e. $`N_kN_b^t=N^t/f_{}^{}{}_{}{}^{t/\nu }`$, and $`H(f^{})1/f_{}^{}{}_{}{}^{t/\nu }`$ for $`f^{}1`$. Similar behavior occurs mkk  in force–extension characteristics of polymers in which a sliding constriction (or slip-link sliplink ) creates a loop, somewhat reminiscent of a topological constraint. In the latter, the size of the loop under strong tension is equal to the size of a loop in unstressed polymers of size $`N_b`$.

While our range of extensions is too limited to test the asymptotic behavior of $`H(f^{})`$, we can estimate the exponent $`t`$ from the value at which the functions $`N_k/N^t`$ exhibit the best collapse, i.e. are least sensitive to $`N`$. Fig. 3 depicts the optimal collapse with $`t=0.4`$, which is characterized by a $`\chi ^2`$ value of $`0.35`$. For $`t=0.3`$ and $`t=0.5`$ we have $`\chi ^21`$, serving as a criterion for the error in $`t`$, and our estimate of $`t=0.4\pm 0.1`$. This is somewhat smaller than the value that can be deduced from Ref. orlandini . The corresponding finite–size correction exponent is $`\mathrm{\Delta }_k=0.6`$. We note that this is close to the best numerical estimate $`\mathrm{\Delta }0.56`$, for the dominant correction to scaling when considering all topologies li , and within errors, also is consistent with the estimate $`\mathrm{\Delta }0.48`$ obtained by field theoretic techniquesguida . Is this more than simple coincidence? The standard field theory for polymers is based on an expansion around four dimensions that does not incorporate topological constraints. Assuming that the analytic continuation of this theory to three dimension also tells us about knots, how can such effects be anticipated in the perturbative expansion? If knots do indeed appear with subleading sizes in 3D, their effects could be anticipated in corrections to scaling, in which case $`\mathrm{\Delta }_k=\mathrm{\Delta }`$. This conjecture is bolstered by $`\mathrm{\Delta }\mathrm{\Delta }_k1`$ for knots confined to 2D metzler ; li .

In summary, by comparing force–extension relations of unknotted and knotted polymers of several lengths, we observe strong finite-size corrections in the latter, which we attribute to the knot size $`N_k`$. Scaling analysis and data collapse suggest a power law $`N_kN^t`$, with $`t=0.4\pm 0.1`$. Thus unlike 2D ‘flat knots’ metzler , the 3D knot sizes grow with the length of the polymer (although as a diminishing fraction of the whole length). Since a single knot is only weakly localized and “knows” about the size of the chain, it is interesting to investigate chains with several knots which may interact with each other. This, however, requires simulations with much larger chains.

We thank C. Jeppesen for helpful comments. Simulations were performed at High Performance Computing Unit of the Inter University Computation Center of Israel. This work was supported by the National Science Foundation (DMR-01-18213 and PHY99-07949) and the US-Israel Binational Science Foundation (1999-007). OF acknowledges the support of the MRL Program of the National Science Foundation (DMR00-80034).


text:
# Single Dish Polarization Calibration

## 1 Introduction

The polarization properties of astronomical sources are interesting for a number of reasons. They can be used, for example, in determining the physical processes at work; thermal sources are not polarized, whereas non-thermal sources may have a significant degree of polarization. The rotation measure of a source can be used to determine magnetic field strengths; for example pulsar rotation measures are used to derive magnetic maps of the Galaxy. However, the degree of polarization in astronomical sources is often small, particularly circular polarization, and so careful calibration is necessary before the results can be interpreted.

Recent papers on polarization calibration of radio telescopes include those by Hamaker et al. (1996) and Britton (2000). The Hamaker et al. (1996) paper lays down the mathematical foundations which are subsequently used by Sault et al. (1996) to construct a method for instrumental calibration of a radio interferometer. Their method is routinely applied to data from the Australia Telescope Compact Array and incorporated in the software package miriad. In this paper, I will use the approach of Hamaker et al. (1996) to develop a method for calibration of single dish data. This method is particularly useful for observations of pulsars. In the final section of the paper I apply the method to observations of the pulsar PSR J1359–6038 using the 20-cm multibeam receiver on the Parkes radio telescope and discuss the results.

## 2 Representation

Following Hamaker et al. (1996) I describe the propagation of an electromagnetic wave in the $`xyz`$ coordinate system by

$$e_2=<\left(\begin{array}{c}e_x\\ e_y\end{array}\right)>$$
(1)
where the axis of propagation is the $`z`$ axis, and $`e_x`$ and $`e_y`$ are complex. The coherency properties of the electric field can be expressed in $`xy`$ coordinates by the coherency matrix (Born & Wolf 1964)

$$e=<\left(\begin{array}{c}e_xe_x^{}\\ e_xe_y^{}\\ e_ye_x^{}\\ e_ye_y^{}\end{array}\right)>$$
(2)
where the $``$ denotes the complex conjugate. The electromagnetic field is converted to electric voltage in the feed of a radio telescope which, in the case of linear feeds, consists of two input probes aligned along $`x`$ and $`y`$. A correlator multiplies and averages these voltages to produce the voltage vectors

$$v_2=<\left(\begin{array}{c}v_x\\ v_y\end{array}\right)>;v=<\left(\begin{array}{c}v_xv_x^{}\\ v_xv_y^{}\\ v_yv_x^{}\\ v_yv_y^{}\end{array}\right)>$$
(3)
Generally, one is interested in the (true) Stokes parameters, $`I`$, $`Q`$, $`U`$ and $`V`$ which in combination form the Stokes vector $`e^S`$. One can express $`e^S`$ in terms of the electric field vector, $`e`$, by

$$e^S=\left(\begin{array}{c}I\\ Q\\ U\\ V\end{array}\right)=Te;T=\left(\begin{array}{cccc}\hfill 1& \hfill 0& \hfill 0& \hfill 1\\ \hfill 1& \hfill 0& \hfill 0& \hfill 1\\ \hfill 0& \hfill 1& \hfill 1& \hfill 0\\ \hfill 0& \hfill i& \hfill i& \hfill 0\end{array}\right)$$
(4)
The propagation of the radiation from the astrophysical source of interest to the output from the correlator can be described in the following way (Hamaker et al. 1996). Let the effects of Faraday Rotation (both through the interstellar medium and the ionosphere) and parallactic angle rotation be combined into the matrix $`R`$. We let the matrix $`F`$ represent the feed response (including gains, phases and leakage terms). Hence the voltages at the two probes can be described by

$$v_2=FR$$
(5)
and the correlator voltage vector is given by

$$v=(FF^{})(RR^{})T^1e^S$$
(6)
where $``$ denotes the Kronecker (or outer) product (Hamaker et al. 1996). The rotation matrix, $`R`$, and the feed response matrix, $`F`$, are given by Hamaker et al. (1996) as

$$R=\left(\begin{array}{cc}\hfill \mathrm{cos}\varphi & \hfill \mathrm{sin}\varphi \\ \hfill \mathrm{sin}\varphi & \hfill \mathrm{cos}\varphi \end{array}\right);F=\left(\begin{array}{cc}\hfill G& \hfill B\\ \hfill C& \hfill H\end{array}\right)$$
(7)
where each of $`B`$, $`C`$, $`G`$ and $`H`$ are complex terms. It is important to note that Hamaker et al. (1996) have shown that such a formalism does not involve any approximations, although often, as below, the matrices are then expanded only to first order.

In this formalism, however, unlike that of Britton (2000), there is no direct physical association of the variables $`B`$, $`C`$, $`G`$ and $`H`$. $`B`$ and $`C`$ can be thought of as ‘leakage’ terms; they describe the leakage of the opposite polarization into either receptor. The real parts of $`G`$ and $`H`$ relate to the sensitivity of the two probes and the difference in the imaginary parts of $`G`$ and $`H`$ relates to the phase offset between the two channels (often called ‘instrumental phase’ for a pair of linear receptors). However, this is not strictly correct, as $`G`$ and $`H`$ also mixed with the leakage terms (Hamaker et al. 1996).

Expanding equation 6 and ignoring (for now) the effects of rotation we thus obtain

$$\left(\begin{array}{c}v_{xx^{}}\\ v_{xy^{}}\\ v_{yx^{}}\\ v_{yy^{}}\end{array}\right)=\frac{1}{2}\left(\begin{array}{cccc}\hfill GG^{}& \hfill GB^{}& \hfill BG^{}& \hfill BB^{}\\ \hfill GC^{}& \hfill GH^{}& \hfill BC^{}& \hfill BH^{}\\ \hfill CG^{}& \hfill CB^{}& \hfill HG^{}& \hfill HB^{}\\ \hfill CC^{}& \hfill CH^{}& \hfill HC^{}& \hfill HH^{}\end{array}\right)\left(\begin{array}{cccc}\hfill 1& \hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 0& \hfill 1& \hfill i\\ \hfill 0& \hfill 0& \hfill 1& \hfill i\\ \hfill 1& \hfill 1& \hfill 0& \hfill 0\end{array}\right)\left(\begin{array}{c}I\\ Q\\ U\\ V\end{array}\right)$$
(8)
where the scaling factor 1/2 arises from the determinant of $`T`$. Multiplying the two 4x4 matrices together we arrive at

$$\left(\begin{array}{c}v_{xx^{}}\\ v_{xy^{}}\\ v_{yx^{}}\\ v_{yy^{}}\end{array}\right)=\frac{1}{2}\left(\begin{array}{cccc}\hfill GG^{}+BB^{}& \hfill GG^{}BB^{}& \hfill GB^{}+BG^{}& \hfill i(GB^{}BG^{})\\ \hfill GC^{}+BH^{}& \hfill GC^{}BH^{}& \hfill GH^{}BC^{}& \hfill i(GH^{}+BC^{})\\ \hfill CG^{}+HB^{}& \hfill CG^{}HB^{}& \hfill CB^{}+HG^{}& \hfill i(CB^{}+HG^{})\\ \hfill CC^{}+HH^{}& \hfill CC^{}HH^{}& \hfill CH^{}HC^{}& \hfill i(CH^{}HC^{})\end{array}\right)\left(\begin{array}{c}I\\ Q\\ U\\ V\end{array}\right)$$
(9)
## 3 Measured Stokes Parameters

Using equation 9 above and defining the measured Stokes parameters in the case of linear feeds by

$`I_m`$ $`=`$ $`v_{xx^{}}+v_{yy^{}}`$ (10)
$`Q_m`$ $`=`$ $`v_{xx^{}}v_{yy^{}}`$
$`U_m`$ $`=`$ $`v_{xy^{}}+v_{yx^{}}`$
$`iV_m`$ $`=`$ $`v_{xy^{}}v_{yx^{}}`$
we can express the measured Stokes parameters in terms of the true Stokes parameters as follows:

$`I_m`$ $`=`$ $`{\displaystyle \frac{1}{2}}I(g_1^2+g_2^2+h_1^2+h_2^2)+{\displaystyle \frac{1}{2}}Q(g_1^2+g_2^2h_1^2h_2^2)+`$
$`U(g_1b_1+g_2b_2h_1c_1h_2c_2)+V(g_1b_2g_2b_1+h_1c_1h_2c_2)`$
$`Q_m`$ $`=`$ $`{\displaystyle \frac{1}{2}}I(g_1^2+g_2^2h_1^2h_2^2)+{\displaystyle \frac{1}{2}}Q(g_1^2+g_2^2+h_1^2+h_2^2)+`$
$`U(g_1b_1+g_2b_2+h_1c_1+h_2c_2)+V(g_1b_2g_2b_1h_1c_2+h_2c_1)`$
$`U_m`$ $`=`$ $`I(h_1b_1+h_2b_2g_1c_1g_2c_2)+Q(g_1c_1g_2c_2h_1b_1h_2b_2)+`$
$`U(g_1h_1+g_2h_2)+V(g_1h_2g_2h_1)`$
$`V_m`$ $`=`$ $`I(g_1c_2g_2c_1+h_1b_2h_2b_1)+Q(g_1c_2+g_2c_1h_1b_2+h_2b_1)+`$
$`U(g_1h_2+g_2h_1)+V(g_1h_1+g_2h_2)`$
where all second order terms in $`B`$ and $`C`$ have been omitted. Somewhat unconventionally I have defined each complex term above by e.g. $`G=g_1+ig_2`$ rather than $`G=g_1e^{ig_2}`$ to simplify the notation. Note that these parameters are assumed to be time-independent but will not, in general, be frequency independent. In a perfect system one has $`b_1=b_2=0`$, $`c_1=c_2=0`$, $`g_1=h_1=1`$ and $`g_2=h_2=0`$ and hence the measured Stokes parameters are identically equal to the true Stokes parameters (ignoring the effects of rotation of Stokes $`Q`$ into $`U`$ along the line of sight).

If the gains and instrumental phase have been solved for by some other method, as is often the case, (e.g. through observations of a polarized calibration signal injected directly into the feed), then $`g_1=h_1=1`$ and $`g_2=h_2=0`$ and equation 3 simplifies to:

$`I_m`$ $`=`$ $`I+U(b_1c_1)+V(b_2+c_2)`$ (12)
$`Q_m`$ $`=`$ $`Q+U(b_1+c_1)+V(b_2c_2)`$
$`U_m`$ $`=`$ $`U+I(b_1c_1)Q(b_1+c_1)`$
$`V_m`$ $`=`$ $`V+I(b_2+c_2)Q(b_2c_2)`$
We also note, as Britton (2000) has done, that a relationship holds between the measured and true Stokes parameters via

$$I_m^2Q_m^2U_m^2V_m^2=K(I^2Q^2U^2V^2)$$
(13)
where $`K`$ is time-invariant and is related to the determinant of the matrix in Equation 11. This expression, the so-called invariant interval, is not frequency-invariant however, as it depends on the (frequency dependent) terms in the $`F`$ matrix. Britton’s idea of using the invariant interval for timing purposes has been used to great effect by van Straten et al. (2001).

## 4 Effects of feed rotation

It is sometimes stated that performing a (short) observation, rotating the feed through 90$`^{}`$and observing again and summing the two observations has the effect of cancelling the effect of the leakage parameters. However, this is not the case, even to first order. The effect of feed rotation effectively converts $`Q`$ to $`Q`$ and $`U`$ to $`U`$. To sum the two observations one essentially averages the sum of the two values of $`I_m`$ and $`V_m`$ and averages the differences of the two $`Q_m`$ and $`U_m`$ measurements. Assuming the gains are correctly calibrated, then using equation 12 above, one obtains:

$`I_m`$ $`=`$ $`I+V(b_2+c_2)`$ (14)
$`Q_m`$ $`=`$ $`Q+U(b_1+c_1)`$
$`U_m`$ $`=`$ $`UQ(b_1+c_1)`$
$`V_m`$ $`=`$ $`V+I(b_2+c_2)`$
and the total linear polarization is thus

$`L_m`$ $`=`$ $`L\sqrt{1+(b_1+c_1)^2}`$ (15)
These last two equations show that the measured Stokes parameters are now a better approximation to the true Stokes parameters than a single observation would yield. However, even though the error in $`I_m`$ and $`L_m`$ are likely to be small, the error in $`V_m`$ can potentially be large if $`V`$ is small and $`b_2+c_2`$ is significant. The error in the position angle of the linear polarization will be of order $`\mathrm{tan}^1(b_1+c_1)`$.

A further potentially interesting measurement is to subtract $`V_m`$ from one observation with that from an observation where the feed is rotated through 90$`^{}`$. In this case one obtains

$`V_m`$ $`=`$ $`Q(b_2c_2)`$ (16)
If Q is large, one can then obtain $`b_2c_2`$ directly.

## 5 Effects of observing a polarized calibration signal

It is often the case that a cal probe is included in the receiver package. This probe usually injects a signal between the two (linear) probes at an angle of 45$`^{}`$to both. The cal thus has $`I=U`$ and $`Q=V=0`$. Imagine now that the two probes have identical gains and there is no instrumental rotation (i.e. we can set $`g_1=h_1=1`$ and $`g_2=h_2=0`$). Then, if the leakage terms are present, observations of the cal will yield a signal

$`v_{xx^{}}`$ $`=`$ $`{\displaystyle \frac{1}{2}}U(1+2b_1)`$ (17)
$`v_{yy^{}}`$ $`=`$ $`{\displaystyle \frac{1}{2}}U(12c_1)`$
$`V_m`$ $`=`$ $`U(b_2+c_2)`$
The first two expressions look like gain difference between the two probes, and the presence of $`V`$ looks like instrumental rotation of $`U`$ into $`V`$. Hence, even though we started with a system with perfect gains and phases, we derive using equation 12:

$`g_1`$ $`=`$ $`{\displaystyle \frac{1}{1+2b_1}}`$ (18)
$`h_1`$ $`=`$ $`{\displaystyle \frac{1}{12c_1}}`$
$`h_2`$ $`=`$ $`b_2+c_2`$
and hence the system looks impure! One then re-observes the cal (or any other pure U signal) with these terms in equation 3 and one obtains:

$`I_m`$ $`=`$ $`U\left(1{\displaystyle \frac{b_1}{(1+2b_1)^2}}+{\displaystyle \frac{c_1}{(1+2c_1)^2}}+{\displaystyle \frac{1}{2}}b_2^2{\displaystyle \frac{1}{2}}c_2^2\right)`$ (19)
$`Q_m`$ $`=`$ $`U\left({\displaystyle \frac{b_1}{(1+2b_1)^2}}+{\displaystyle \frac{c_1}{(1+2c_1)^2}}+{\displaystyle \frac{1}{2}}b_2^2{\displaystyle \frac{1}{2}}c_2^2\right)`$
$`U_m`$ $`=`$ $`U\left({\displaystyle \frac{b_1+2b_1^2c_1+2c_1^2+1}{(1+2b_1)(12c_1)}}+b_2(b_2+c_2)\right)`$
$`V_m`$ $`=`$ $`U\left({\displaystyle \frac{2b_2(c_1+b_1)}{(1+2b_1)(12c_1)}}b_1(b_2+c_2)\right)`$
This implies that one does not, in general, measure a pure $`U`$ signal in spite of the calibration procedure.

## 6 Circular Feeds

The Parkes radio telescope has receivers with linear feeds. However, many other telescopes have circular feed systems. To apply this method to receivers with circular feeds one needs to change the Stokes vector $`e^S`$ to

$$e^S=\left(\begin{array}{c}I\\ V\\ Q\\ U\end{array}\right)$$
(20)
and equation 10 to read

$`I_m`$ $`=`$ $`v_{rr^{}}+v_{ll^{}}`$ (21)
$`V_m`$ $`=`$ $`v_{rr^{}}v_{ll^{}}`$
$`Q_m`$ $`=`$ $`v_{rl^{}}+v_{lr^{}}`$
$`iU_m`$ $`=`$ $`v_{rl^{}}v_{lr^{}}`$
The algebra can then be worked through to obtain expressions for the measured Stokes parameters in terms of the true parameters as in equation 3.

## 7 Application

From equation 3 it can be seen there are 4 measured quantities (the Stokes parameters) and a total of 12 unknowns. These 12 unknowns comprise the 4 leakage parameters ($`b_1`$, $`b_2`$, $`c_1`$, $`c_2`$), the 4 gain terms ($`g_1`$, $`g_2`$, $`h_1`$, $`h_2`$), the total intensity, linear and circular polarization of the source and an unknown angle $`\varphi `$ which deals with rotation along the line of sight such that $`Q=L\mathrm{cos}\varphi `$ and $`U=L\mathrm{sin}\varphi `$. This angle is made up of the intrinsic position angle of the source, the rotation measure through the interstellar medium and ionosphere, the parallactic angle and the feed angle(s) with respect to some reference frame. Of these angles, only the ionospheric rotation measure and the parallactic angle are time variable. Unless some independent measurement can be made of the ionosphere, this introduces unwanted noise into the calibration matrices. Ignoring this, rotating the feed relative to the sky (for example as naturally occurs with a feed mounted on an alt-az telescope) can be used to determine the 12 unknowns. Provided we have sufficient independent measurements of the Stokes parameters at a variety of parallactic angles, we can, in principle, determine all the unknowns. Sault et al. (1996) show that observations of an unpolarized source will yield only 9 of the unknowns, but that observations of a strongly linearly polarized source can determine all 12.

Pulsars make ideal sources for (self-)calibration as they are generally highly linearly polarized and have a reasonable degree of circular polarization. Furthermore, the polarization changes across the pulse profile and one can thus use the information in multiple phase bins at a given pointing to help solve for the unknowns. The main drawback to using pulsars as calibrators is that they scintillate which implies that the total intensity, $`I`$, can vary significantly on timescales of order minutes. The fractional polarization is not affected by scintillation, however, and therefore to overcome this problem one is forced to normalise the measured Stokes parameters by $`I_m`$ at the expense of being unable to measure the true value of $`I`$. Unfortunately this procedure introduces errors as, of course, $`I_m`$ is not equal to $`I`$. In practice these errors will be small unless the source is highly polarized and $`b_1c_1`$ is large.

A previous method for calibration of pulsar signals was given in the Appendix of Stinebring et al. (1984) and is still in use (e.g. Weisberg et al. 1999). However, their method involves a number of simplifications and assumptions which, in my view, are incorrect in some cases and which are, in any case, no longer necessary to make. Any least squares fitting algorithm can easily solve for 12 unknowns with $``$100 data points in a matter of seconds and the full equations should thus be used.

Data on PSR J1359–6038 were collected on two separate occasions in July and Novmeber 2000. Each observing session lasted approximately 10 days and we obtained 65 and 66 independent observations covering the whole parallactic angle range available (approximately $`\pm `$94$`^{}`$). These data were taken using the 64-m Parkes telescope using the centre beam of the multibeam receiver at a central observing frequency of 1318 MHz and with a total bandwidth of 128 MHz. At the start of the observing session observations were made of the flux calibrator Hydra A to obtain the system equivalent flux density. Then, a 90 sec observation of the cal signal was made followed immediately by a 3 min observation of the pulsar. The pulsar observation was calibrated for differential gain and phase in the two probes based on the results from the cal observation and flux calibrated from the observations of Hydra A. Pulse profiles were formed in each of $`I_m`$, $`Q_m`$, $`U_m`$ and $`V_m`$ with 256 phase-bins per profile and 8 frequency channels across the 128 MHz total bandwidth. $`Q_m`$, $`U_m`$ and $`V_m`$ were then normalised by $`I_m`$.

Figure 1 shows the measured (normalised) Stokes parameters as a function of parallatic angle from data taken in November 2000 from the peak of the pulse profile in one of the frequency channels centered at 1365 MHz. It can clearly be seen that the circular polarization, $`V_m`$, varies significantly with parallactic angle and that the variations are in phase with the variations in $`Q_m`$. The deviation in $`V_m`$ is very large with a peak-to-peak amplitude of about 0.2. The implication of this (from equation 12) is that $`b_2c_2`$ is of this order, given that $`Q_m`$ is about unity.

It was shown in section 5, that observations of the cal induces subsequent errors in the observed Stokes parameters. These errors can be removed by (re-)solving for the gains and phase terms (although nominally the cal observations are used to set these) using equation 3. Practically, however, I set $`g_1=1`$ and $`h_1=0`$ and leave them fixed; $`g_2`$ and $`h_2`$ then measure the relative gain and phase differences between the two probes. I then used a least squares fitting algorithm (in this case the Levenberg-Maquart Method; LMM) to minimise the residuals of $`(|Q_mQ|+|U_mU|+|V_mV|)`$ and solve for the 9 unknowns from equation 3 given the data (remembering that $`I_m`$ is fixed at 1, all the observed Stokes parameters are normalised by $`I_m`$ and $`g_1=1`$, $`h_1=0`$). The result of the fitting is shown in the Figure. At this particular frequency, $`b_1=0.0`$, $`b_2=0.05`$, $`c_1=0.02`$ and $`c_2=0.12`$. Given this and the discussion in Section 4, rotating the feed through 90$`^{}`$and observing again still induces a leakage of I into V of order 7%, about the same size as the true V signal in many pulsars. As pointed out, an independent measurement of $`b_2c_2`$ can be obtained in this way, and confirms the measurements derived above.

At this point, all the parameters of the matrix form of Equation 11 have effectively been determined. The true Stokes parameters can then be obtained by multiplying the observed Stokes parameters with the inversion of this matrix. This can be achieved with e.g. the numerical recipes routine lubksb.

Figure 2 shows the rotation measure of the pulsar as a function of parallactic angle prior to polarization calibration. There are clear systematics in the data with sinusoidal variations of $``$10 rad m-2 about a mean of 35 rad m-2. These are due to the frequency dependency of the leakage terms $`B`$ and $`C`$. Figure 3 shows the effects of the calibration. The mean rotation measure is now 16 rad m-2 and the systematic effects are largely absent.

## 8 Conclusions

Using the excellent Hamaker et al. (1996) paper as a mathematical foundation, I have derived the matrices linking the true Stokes parameters to the observed Stokes parameters for single dish observations. It is then a computationally trivial task to solve for the terms in this matrix by least squares minimisation and thus provide a polarization calibration of the feed and receiver system.

## Acknowledgments

I would like to thank M. Kesteven for fruitful discussions and a careful reading of this manuscript and R. Manchester for discussion on the calibration procedure used at Parkes. The referee, M. Britton, made a valuable contribution to improving the paper. A. Karastergiou and L. Nicastro provided assistance with the observations.

## References

Born, M. Wolf, E. 1964, Principles of Optics. Pergamon Press.
Britton, M. 2000, ApJ, 532, 1240
Hamaker, J. P., Bregman, J. D. Sault, R. J. 1996, A&ASS, 117, 137
Sault, R. J., Hamaker, J. P. Bregman, J. D. 1996, A&ASS, 117, 149
Stinebring, D. R., Cordes, J. M., Rankin, J. M., Weisberg, J. M. Boriakoff, V. 1984, ApJSS, 55, 247
van Straten, W., Bailes, M., Britton, M., Kulkarni, S. R., Anderson, S. B., Manchester, R. N., Sarkissian, J. 2001, Nature, 452, 158.
Weisberg et al., 1999, ApJSS, 121, 171


text:
# A simple formula for the average gate fidelity of a quantum dynamical operation

## Abstract

This note presents a simple formula for the average fidelity between a unitary quantum gate and a general quantum operation on a qudit, generalizing the formula for qubits found by Bowdrey et al \[Phys. Lett. A 294, 258 (2002)\]. This formula may be useful for experimental determination of average gate fidelity. We also give a simplified proof of a formula due to Horodecki et al \[Phys. Rev. A 60, 1888 (1999)\], connecting average gate fidelity to entanglement fidelity.

Characterizing the quality of quantum channels and quantum gates is a central task of quantum computation and quantum information Nielsen and Chuang (2000). The purpose of this note is to present a simple formula for the average fidelity of a quantum channel or quantum gate.

The average fidelity of a quantum channel described by a trace-preserving quantum operation $``$ Nielsen and Chuang (2000) is defined by

$`\overline{F}(){\displaystyle 𝑑\psi \psi |(\psi )|\psi },`$ (1)
where the integral is over the uniform (Haar) measure $`d\psi `$ on state space, normalized so $`𝑑\psi =1`$. We assume $``$ acts on a qudit, that is, a $`d`$-dimensional quantum system, with $`d`$ finite. We use the notational convention that $`\psi `$ indicates either $`|\psi `$ or $`|\psi \psi |`$, with the meaning determined by context. $`\overline{F}()`$ quantifies how well $``$ preserves quantum information, with values close to one indicating information is preserved well, while values close to zero indicate poor preservation. $`\overline{F}()`$ may be extended to a measure of how well $``$ approximates a quantum gate, $`U`$,

$`\overline{F}(,U){\displaystyle 𝑑\psi \psi |U^{}(\psi )U|\psi }.`$ (2)
Note that $`F(,U)=1`$ if and only if $``$ implements $`U`$ perfectly, while lower values indicate that $``$ is a noisy implementation of $`U`$. Note that $`\overline{F}(,U)=\overline{F}(𝒰^{})`$, where $`𝒰^{}(\rho )U^{}\rho U`$, and $``$ denotes composition.

The paper is structured as follows. First, we state and provide a simple proof of a result of M., P. and R. Horodecki connecting $`\overline{F}()`$ to the entanglement fidelity introduced in Schumacher (1996). We then use the Horodecki’s result to obtain an explicit formula for the average fidelity $`\overline{F}(,U)`$. The paper concludes with a discussion of how the formula for $`\overline{F}(,U)`$ may be useful for experimentally quantifying the quality of quantum gates and quantum channels.

The present work is a development of the paper of Bowdrey et al Bowdrey et al. (2002), who obtained a simple formula for $`\overline{F}(,U)`$ when $``$ and $`U`$ act on qubits. This paper generalizes to the case where $``$ and $`U`$ act on qudits. Related results were also obtained by Fortunato *et al* Fortunato et al. (2002a, b) who found a simple and experimentally useful formula for the entanglement fidelity; Fortunato et al. (2002b) had also rediscovered the connection between average fidelity and entanglement fidelity proved in Horodecki et al. (1999), for the special case of a qubit, thus enabling them to recover the results of Bowdrey et al. (2002).

To define entanglement fidelity, imagine $``$ acts on one half of a maximally entangled state. That is, if $``$ acts on a qudit labelled $`Q`$, then imagine another qudit, $`R`$, with $`RQ`$ initially in the maximally entangled state $`\varphi `$. The entanglement fidelity is defined to be the overlap between $`\varphi `$ before and after the application of $``$ 111Our definition is a special case of Schumacher (1996), which also considered non-maximally entangled states of $`RQ`$., $`F_\mathrm{e}()\varphi |()(\varphi )|\varphi ,`$ where $``$ denotes the identity operation on system $`R`$. The entanglement fidelity is thus a measure of how well entanglement with other systems is preserved by the action of $``$. Using the fact that any two maximally entangled states on $`RQ`$ are related by a unitary on system $`R`$ alone, it follows that the value of the entanglement fidelity does not depend upon which maximally entangled state $`\varphi `$ between $`R`$ and $`Q`$ is used in the definition of entanglement fidelity Schumacher (1996).

M., P., and R. Horodecki have presented a beautiful formula Horodecki et al. (1999) connecting $`\overline{F}()`$ to $`F_\mathrm{e}()`$:

$`\overline{F}()={\displaystyle \frac{dF_\mathrm{e}()+1}{d+1}}.`$ (3)
We now give a proof of Eq. (3), substantially simplifying the proof in Horodecki et al. (1999). The first step is to define a new, “twirled” operation $`_T`$, $`_T(\rho )𝑑UU^{}(U\rho U^{})U`$, where the integral is over the normalized uniform (Haar) measure $`dU`$ on the space of $`d\times d`$ unitary matrices. Note that $`_T`$ is a trace-preserving quantum operation. Next, we argue that twirling does not change the average fidelity, since

$`\overline{F}(_T)`$ $`=`$ $`{\displaystyle 𝑑\psi 𝑑U\psi |U^{}(U\psi U^{})U|\psi }`$ (4)
$`=`$ $`{\displaystyle 𝑑U𝑑\psi \psi |U^{}(U\psi U^{})U|\psi }`$ (5)
$`=`$ $`{\displaystyle 𝑑U\overline{F}()}=\overline{F}(),`$ (6)
where Eq. (6) follows from Eq. (5) by the change of variables $`|\psi ^{}U|\psi `$. A similar argument shows that twirling does not change the entanglement fidelity, for if $`\varphi `$ was the maximally entangled state of $`RQ`$ then 222Note that $`U`$ and $``$ act on system $`Q`$ alone in these expressions, with the identity action on $`R`$ implicit.

$`F_\mathrm{e}(_T)`$ $`=`$ $`{\displaystyle 𝑑U\varphi |U^{}\left(U\varphi U^{}\right)U|\varphi }`$ (7)
$`=`$ $`{\displaystyle 𝑑UF_\mathrm{e}()}=F_\mathrm{e}(),`$ (8)
where we used the fact that $`U|\varphi `$ is also maximally entangled, and the independence of $`F_\mathrm{e}()`$ from the specific maximally entangled state used in the definition.

Until now, our proof of Eq. (3) has not deviated substantially from Horodecki et al. (1999), and is included for completeness. The simplification is in the next step, namely, showing that $`_T`$ is a depolarizing channel. That is, there is a $`p`$ such that $`_T(\rho )=pI/d+(1p)\rho `$ for all $`\rho `$. The proof of this fact in Horodecki et al. (1999) made use of an isomorphism between quantum operations and operators, while the following proof is direct. Note that for any unitary $`V`$,

$`V_T(\rho )V^{}={\displaystyle 𝑑UVU^{}(U\rho U^{})UV^{}}.`$ (9)
Making the change of variables $`WUV^{}`$ in the integral we obtain

$`V_T(\rho )V^{}=_T(V\rho V^{})`$ (10)
for all $`\rho `$ and $`V`$. Let $`P`$ be a one-dimensional projector, and $`QIP`$ be the projector onto the orthocomplementary space. Letting $`V`$ be block diagonal with respect to the spaces onto which $`P`$ and $`Q`$ project, we see that $`VPV^{}=P`$ and thus $`V_T(P)V^{}=_T(P)`$. It follows that $`_T(P)=\alpha P+\beta Q`$ for some $`\alpha `$ and $`\beta `$. Using $`Q=IP`$, this expression may be rewritten as $`_T(P)=pI/d+(1p)P`$, for some $`p`$, with $`p`$ possibly depending upon $`P`$. Using Eq. (10) again we see that this equation must hold with the same value of $`p`$ for any one-dimensional projector $`P`$. By linearity of $`_T`$ it follows that $`_T(\rho )=pI/d+(1p)\rho `$ for all $`\rho `$, that is, $`_T`$ is a depolarizing channel.

Finally, by direct calculation Eq. (3) is easily verified for depolarizing channels such as $`_T`$. Since $`\overline{F}()=\overline{F}(_T)`$ and $`F_\mathrm{e}()=F_\mathrm{e}(_T)`$ the result also holds for general channels, which completes the proof.

Our next goal is to find a simple expression for $`\overline{F}()`$ in terms of experimentally accessible quantities. Let $`\varphi =_j|j|j/\sqrt{d}`$ be a maximally entangled state of $`RQ`$. Suppose we introduce a basis of unitary operators $`U_j`$ for a qudit, with the $`U_j`$ orthogonal with respect to the Hilbert-Schmidt inner product. That is, $`\text{tr}(U_j^{}U_k)=\delta _{jk}d`$, and thus $`U_j/\sqrt{d}`$ forms an orthonormal operator basis. An example of such a set is operators of the form $`X^kZ^l`$ where the action of $`X`$ and $`Z`$ on computational basis states $`|0,\mathrm{},|d1`$ is defined by $`X|j|j1`$, where $``$ is addition modulo $`d`$, and $`Z|je^{2\pi ij/d}|j`$. Other examples of orthogonal unitary operator bases and general theory may be found in Knill (1996a, b); Klappenecker and Roetteler (2000).

Since $`U_j/\sqrt{d}`$ forms an orthonormal operator basis for a qudit, $`U_j^{}/\sqrt{d}`$ also forms an orthonormal operator basis, whence $`U_j^{}U_k/d`$ is an orthonormal operator basis for $`RQ`$. It follows that

$`|\varphi \varphi |={\displaystyle \underset{jk}{}}{\displaystyle \frac{U_j^{}U_k}{d}}{\displaystyle \frac{\text{tr}\left((U_j^{}U_k)^{}\varphi \right)}{d}}.`$ (11)
Note however that

$`\text{tr}\left((U_j^{}U_k)^{}\varphi \right)`$ $`=`$ $`\varphi |U_j^TU_k^{}|\varphi =\varphi |IU_k^{}U_j|\varphi ,`$
where we used the easily verified fact that $`(AI)|\varphi =(IA^T)|\varphi `$. Direct calculation shows that

$`\varphi |IU_k^{}U_j|\varphi ={\displaystyle \frac{\text{tr}(U_k^{}U_j)}{d}}=\delta _{jk}.`$ (13)
Substituting we obtain $`\varphi =_j(U_j^{}U_j)/d^2`$. It follows that the entanglement fidelity is given by

$`F_\mathrm{e}()`$ $`=`$ $`\varphi |(\varphi )|\varphi =\text{tr}(\varphi ^{}(\varphi ))`$ (14)
$`=`$ $`{\displaystyle \frac{_{jk}\text{tr}\left((U_j^{})^{}U_k^{}U_j^{}(U_k)\right)}{d^4}}`$ (15)
$`=`$ $`{\displaystyle \frac{_j\text{tr}\left(U_j^{}(U_j)\right)}{d^3}}.`$ (16)
(Compare also the related Eqs. (6) and (10) in Fortunato et al. (2002a), which were obtained by different techniques, and which can also serve as the basis for experimental determination of the entanglement fidelity, and thus of the average fidelity, c.f. Eqs. (17) and (18) and the surrounding discussion in Fortunato et al. (2002b).) Using this equation and Eq. (3) we obtain the following formula for the average gate fidelity

$`\overline{F}(,U)=\overline{F}(𝒰^{})={\displaystyle \frac{_j\text{tr}\left(UU_j^{}U^{}(U_j)\right)+d^2}{d^2(d+1)}}.`$ (17)
When $`d=2`$ and choosing the $`U_j`$ to be the Pauli matrices $`I,X,Y,Z`$ we obtain the result of Bowdrey et al. (2002),

$`\overline{F}(,U)={\displaystyle \frac{1}{2}}+{\displaystyle \frac{1}{12}}{\displaystyle \underset{j=1,2,3}{}}\text{tr}(U\sigma _jU^{}(\sigma _j)).`$ (18)
Eq. (17) is theoretically interesting as a simple, compact expression for the average gate fidelity, and may also be interesting for experiment. Suppose one wished to experimentally determine $`\overline{F}(,U)`$. One way is to determine $``$ directly via quantum process tomography Chuang and Nielsen (1997); Poyatos et al. (1997), as demonstrated in Nielsen et al. (1998), and then substitute into Eq. (17). However, process tomography is complex and its theoretical properties are not so easy to analyse. A more direct approach is to choose a set $`\rho _k`$ of quantum states which form an operator basis, and which may be experimentally prepared with high accuracy. For example, such a set may be obtained from the computational basis states $`|0,\mathrm{},|d1`$ and superpositions $`(|j\pm |k)/\sqrt{2}`$, where $`jk`$. Many other sets of states also suffice. Standard linear algebraic methods may be used to find co-efficients $`\alpha _{jk}`$ such that $`U_j=_k\alpha _{jk}\rho _k`$, whence Eq. (17) implies

$`\overline{F}(,U)={\displaystyle \frac{_{jk}\alpha _{jk}\text{tr}\left(UU_j^{}U^{}(\rho _k)\right)+d^2}{d^2(d+1)}}.`$ (19)
Using standard state tomography (see, e.g. Leonhardt (1997)) it is possible to determine $`(\rho _k)`$, and thus to determine $`\overline{F}(,U)`$.

In conclusion, we have obtained a simple formula for the average fidelity of a noisy quantum channel or quantum gate. This formula may be useful for experimentally characterizing quantum gates and channels. It would be interesting to generalize these results further to non-uniform starting distributions of states.

###### Acknowledgements.

Thanks to Jennifer Dodd, Gerard Milburn, Tobias Osborne, and Lorenza Viola for their comments on the manuscript.