text:
# Controlling discrete quantum walks: coins and intitial states

## I Introduction

Quantum walks are analogs of classical random walks, designed primarily with the aim of finding quantum algorithms that are faster than classical algorithms for the same problem. There are two distinct types of quantum walks, corresponding to classical random walks with discrete or continuous time (but both taking place in a discrete space). Continuous time quantum walks were first introduced in 1997 by Farhi and Gutmann Farhi and Gutmann (1998). Discrete time quantum walks with a quantum coin appeared in the early 1990s in work by Y Aharonov et al. Aharonov et al. (1992), then were developed as quantum cellular automata by Meyer Meyer (1996a, b, c) in 1996. The first explicitly algorithmic context for coined quantum walks came from D Aharonov et al. Aharanov et al. (2001) and Ambainis et al. Ambainis et al. (2001) in 2000.

Two algorithms for quantum walks have recently been presented. Childs et al. Childs et al. (2002) prove that a continuous time quantum walk can find its way across a special type of graph exponentially faster than any classical algorithm, and Shenvi et al. Shenvi et al. (2003) prove that a discrete time, coined quantum walk can equal Grover’s search algorithm, by finding a marked item in an unsorted database with a quadratic speed up over the best known classical algorithm. These results are extremely promising, but still a long way from the diversity of problems that classical random walks provide the best known solutions for, such as approximating the permanent of a matrix Jerrum et al. (2001), finding satisfying assignments to Boolean expressions ($`k`$SAT with $`k>2`$) Schöning (1999), estimating the volume of a convex body Dyer et al. (1991), and graph connectivity Motwani and Raghavan (1995). Classical random walks underpin many standard methods in computational physics, such as Monte Carlo simulations, so a more efficient quantum alternative would presumably widen the potential application of quantum computers to problems in physics.

In much the same way as we now know almost everything about the properties and possible states of two qubits, though quantum computers will clearly need far more than two qubits to be useful, the simple quantum walk on a line has now been well studied, see for example Refs. Ambainis et al. (2001); Bach et al. (2002); Yamasaki et al. (2002); Kendon and Tregenna (2003); Brun et al. (2003a, b); Carteret et al. (2003), though there is no suggestion that it will lead to useful quantum walk algorithms by itself. The quantum walk on a cycle is a step closer to algorithms. The $`N`$-cycle is the Cayley graph of the cyclic group of size $`N`$, and in addition to proving that the coined quantum walk on a cycle has a time-averaged mixing time almost quadratically faster than a classical random walk, D Aharonov et al. Aharanov et al. (2001) also provided a lower bound on the time-averaged mixing times for quantum walks on general graphs of bounded degree, suggesting a quadratic improvement over classical random walks is the best that can be achieved. Moore and Russell Moore and Russell (2002) solved both discrete and continuous time quantum walks on the hypercube of size $`N`$, showing that both have an instantaneous mixing time linear in $`N`$, logarithmically faster than classical random walks. However, they also showed that time-averaged mixing times on the hypercube are slower than classical, the continuous time walk never mixes in the sense of the time-averaged definition. Kempe Kempe (2002) proved that a quantum walk can travel from one corner of a hypercube to the opposite corner exponentially faster than a classical random walk, however, there are other classical algorithms that can do this task efficiently so this does not provide a quantum advantage over classical. For a recent survey of quantum walks and a more complete list of references, see Kempe Kempe (2003).

So far, though the published literature on discrete and continuous time quantum walks tends to treat different problems, the evidence suggests that both can accomplish the same tasks. They are clearly not exactly equivalent, and the computational equivalence observed depends on choosing an appropriate form for the coin operator for the discrete time walks. This raises the possibility that different choices of coin operator could perform other useful tasks that aren’t easily accessible within the continuous time quantum walk model. In this paper, we present a study of the properties of different coin operators using both analytical and numerical methods. Our results are of interest both in themselves as examples of quantum dynamics, and as potential ingredients for quantum algorithms. The paper is organized as follows. After setting up our notation, we discuss the possibilities for graphs of degree two, three, and four in Secs. II, III, and IV respectively. In Sec. V we briefely mention graphs of higher degree and in Sec. VI we describe periodic quantum walks on cyclic graphs.

### I.1 Notation for a general quantum walk

A general coined quantum walk on a $`d`$-regular graph needs a coin Hilbert space, $`_d`$ with $`d`$ the degree of each vertex in the graph on which the walk takes place, and a position Hilbert space $`_N`$ with $`N`$ the number of vertices in the graph (which can be infinite). The dynamics of the walk are controlled by a coin flip operator $`𝐂`$ that acts on the coin Hilbert space, and a conditional shift operator $`𝐒`$ that shifts the particle position according to the state of the coin. Together, $`𝐔𝐒(𝐂𝐈_N)`$ is the unitary operator for one step of the walk. If the particle and coin start in state $`|\psi _0`$, the state of the system after $`t`$ steps of the walk is $`|\psi _t=𝐔^t|\psi _0`$.

A powerful technique for the solution of classical random walks that generalises well to the quantum case is that of Fourier transformation. When the walk occurs on the Cayley graph of some group, the quantum walk simplifies greatly on consideration of the Fourier space of the particle Aharanov et al. (2001); Ambainis et al. (2001). Quantum walks on the infinite line, $`N`$-cycle and the hypercube admit this type of solution. An alternative method using path counting (path integrals) was also presented in Ambainis et al. (2001) and further refined in Carteret et al. (2003).

## II Graphs of Degree Two

We will consider the simplest examples first, coined quantum walks on the line and the cycle. The walk on the line has already been analysed in detail and the equivalence of all unbiased coin operators noted by several authors Ambainis et al. (2001); Bach et al. (2002); Yamasaki et al. (2002). We first review these calculations, since the notation and results will be used in our analysis of the walk on the $`N`$-cycle.

### II.1 Quantum walk on an infinite line

The most general two dimensional unitary coin operator $`𝐂_2^{(\text{gen})}`$ can be written as a $`2\times 2`$ matrix

$$𝐂_2^{(\text{gen})}=\left(\begin{array}{cc}\sqrt{\rho }& \sqrt{1\rho }e^{i\theta }\\ \sqrt{1\rho }e^{i\varphi }& \sqrt{\rho }e^{i(\theta +\varphi )}\end{array}\right),$$
(1)
where $`0\theta ,\varphi \pi `$ are arbitrary angles, $`0\rho 1`$, and we have removed an irrelevant global phase so as to leave the leading diagonal element real. The Hadamard coin operator is obtained with $`\rho =1/2`$ and $`\theta =\varphi =0`$. The parameter $`\rho `$ thus controls the bias of the coin, $`\rho =1/2`$ being a fair coin that chooses each of the two possible directions $`|R`$ (right) and $`|L`$ (left) with equal probability. Trivial cases $`\rho =0`$,1 give oscillatory motion and uniform motion respectively. The Fourier transformation is performed only over the particle Hilbert space,

$$|\stackrel{~}{\psi }(k,t)=\underset{x}{}|\psi (x,t)e^{ikx}.$$
(2)
Here the state vectors $`|\psi (x,t)`$ and $`|\stackrel{~}{\psi }(k,t)`$ are two component vectors, with the first component being the amplitude of the right moving part and the second component being that of the left moving part, with $`k[0,2\pi )`$. Using the general form of the coin transition matrix for a one dimensional walk, Eq. (1), a single step of the walk becomes

$$|\stackrel{~}{\psi }(k,t+1)=𝐂_k^{(\text{gen})}|\stackrel{~}{\psi }(k,t),$$
(3)
where $`𝐂_k^{(\text{gen})}`$ is a $`2\times 2`$ matrix acting on the coin Hilbert space,

$$𝐂_k^{(\text{gen})}=\left(\begin{array}{cc}\sqrt{\rho }e^{ik}& \sqrt{1\rho }e^{i(k+\theta )}\\ \sqrt{1\rho }e^{i(k+\varphi )}& \sqrt{\rho }e^{i(k+\theta +\varphi )}\end{array}\right).$$
(4)
This matrix may be diagonalised, yielding eigenvalues

$$\lambda _k^\pm =\pm e^{i\delta }e^{\pm i\omega _k},$$
(5)
where $`\delta =(\theta +\varphi )/2`$ and

$$\mathrm{sin}(\omega _k)=\sqrt{\rho }\mathrm{sin}(k\delta ).$$
(6)
The associated eigenvectors are

$$|\stackrel{~}{\xi }_k^\pm =\frac{1}{n_k^\pm }\left(\begin{array}{c}e^{ik}\\ e^{i\theta }(\lambda _k^\pm \sqrt{\rho }e^{ik})/\sqrt{1\rho }\end{array}\right),$$
(7)
with the normalisation factor $`n_k^\pm `$ given by

$$(n_k^\pm )^2=2\left\{1\sqrt{\rho }\mathrm{cos}(k\delta \omega _k)\right\}/(1\rho )$$
(8)
For a general unbiased initial coin state, $`|\psi (x,0)=\sqrt{\eta }(|R+e^{i\alpha }\sqrt{1\eta }|L)|0`$, the Fourier components at $`t=0`$ can be found from Eq. (2),

$$|\stackrel{~}{\psi }(k,0)=\left(\begin{array}{c}\sqrt{\eta }\\ e^{i\alpha }\sqrt{1\eta }\end{array}\right)|kk.$$
(9)
Collecting all these pieces together, it is possible to write down the Fourier components at all later times $`t`$,

$$|\stackrel{~}{\psi }(k,t)=(𝐂_k^{(\text{gen})})^t|\stackrel{~}{\psi }(k,0.$$
(10)
Expressing $`𝐂_k^{(\text{gen})}`$ in terms of its eigenvalues and eigenvectors, $`(𝐂_k^{(\text{gen})})^t=(\lambda _k^+)^t|\stackrel{~}{\xi }_k^+\stackrel{~}{\xi }_k^+|+(\lambda _k^{})^t|\stackrel{~}{\xi }_k^{}\stackrel{~}{\xi }_k^{}|`$, gives

$`|\stackrel{~}{\psi }(k,t)`$ $`=`$ $`(\lambda _k^+)^t|\stackrel{~}{\xi }_k^+\stackrel{~}{\xi }_k^+|\stackrel{~}{\psi }(k,0)`$ (11)
$`+`$ $`(\lambda _k^{})^t|\stackrel{~}{\xi }_k^{}\stackrel{~}{\xi }_k^{}|\stackrel{~}{\psi }(k,0)`$
The coefficients of $`|\stackrel{~}{\xi }_k^\pm `$ are given by

$`(\lambda _k^\pm )^t`$ $`\stackrel{~}{\xi }_k^\pm |\stackrel{~}{\psi }(k,0)={\displaystyle \frac{(\lambda _k^\pm )^t}{n_k^\pm }}e^{ik}\{\text{}\sqrt{\eta }`$ (12)
$`\sqrt{{\displaystyle \frac{1\eta }{1\rho }}}e^{i(\theta +\alpha )}(\sqrt{\rho }e^{i(k\delta )}e^{i\omega _k})\}.`$
All the subsequent statistics for the probability distribution may be found by inverting the Fourier transform and applying standard methods from complex analysis Ambainis et al. (2001); Carteret et al. (2003). However, the question of the effect of the extra degrees of freedom $`\alpha `$ and $`\eta `$ pertaining to the quantum coin, and $`\varphi `$, $`\theta `$ and $`\rho `$ in the coin operator, may be answered directly from Eq. (12). The parameters $`\eta `$ and $`\rho `$ appear in a non-trivial way and thus affect the subsequent evolution of the walk, but the phase factor $`\alpha `$ occurs solely with the phase $`\theta `$ in the coin flip operator as the combination $`(\theta +\alpha )`$. The other influences on the evolution from the phases in the coin flip matrix come from the factor $`e^{i\delta t}`$ in the eigenvalues, which is a global phase and therefore doesn’t affect observable quantities, and from phases of $`e^{i(k\delta )}`$ (explicitly and in $`\omega _k`$), which disappear when $`k`$ is integrated over its full range during the inverse Fourier transform. Thus, for any given $`\theta `$ in the coin operator, one may choose an $`\alpha `$ so as to give the full range of possible evolutions. This has been noted by several authors, Ambainis et al. (2001); Bach et al. (2002); Yamasaki et al. (2002). For the walk on a line, without loss of generality, one may thus restrict the coin operator to one with real coefficients, and obtain the full range of behaviour by choosing different initial coin states. Further restricting to unbiased coins ($`\rho =1/2`$), the Hadamard coin

$$𝐂_2^{(\text{H})}=\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill 1\end{array}\right),$$
(13)
is thus the only possible type of coin for the quantum walk on a line.

The asymmetry of the distribution obtained for an initial coin state of $`|R`$ or $`|L`$ is now well-known, and is also obtained for unbiased initial states with $`\alpha =0`$ or $`\pi `$. However, it is possible to create an even more biased distribution using the Hadamard (unbiased) coin operator, by choosing a biased initial state with $`\eta 0.85`$, i.e., $`|\psi _0=(\sqrt{0.85}|R+\sqrt{0.15}|L)|0`$. This is shown in Fig. 1, along with the distributions for $`|R`$, and symmetric quantum and classical distributions for comparison. The asymmetry of the distribution can be quantified by examining the third moment, which we take about the origin, i.e., with reference to the initial location of the particle, normalised by the second moment, $`x^3/x^2^{3/2}`$. This quantity is just greater than one for the initial state with $`\eta 0.85`$, and around 0.7 for an initial state of $`|R`$ (obtained numerically, for analytic formulae see Konno Konno (2002, 2003), the value of $`\eta `$ comes from $`\mathrm{cos}(\pi /8)0.85`$). By simply changing the phase by $`\pi `$ to $`\sqrt{0.85}|R\sqrt{0.15}|L`$, the distribution becomes symmetric. Comparing this with the unbiased coin initial state $`(|R+i|L)/\sqrt{2}`$ that also gives a symmetric evolution, and noting that the Hadamard operator is real, so any component with phase $`i`$ remains orthogonal to any real component, we can see that there are two distinct ways of arriving at a symmetric quantum walk on a line. Initial states $`\sqrt{0.85}|R\sqrt{0.15}|L`$ (biased) and $`(|R+i|L)/\sqrt{2}`$ (symmetric) give almost identical probability distributions, but the former is obtained by interference and the latter by combining probabilities from two mirror image orthogonal components.

This gives us our first insights into how to use the coin to control the walk. The quadratic speed up in the spreading of the quantum walk over classical is unaffected by the choice of initial state or coin operator: the speed up comes solely from the coherent wave motion along the line. This is made clearest by noting that a maximally mixed initial coin state also produces a symmetric distribution like the previous two examples. We can then control whether (and to what degree) the waves will interfer constructively, destructively, or not at all, by choosing the phase and bias of the coin initial state.

### II.2 Quantum Walk on a $`N`$-Cycle

The walk on a $`N`$-cycle is the same as the walk on the line but with the particle position taken as $`x`$ (mod $`N`$). It is also amenable to solution in the Fourier basis. The finite state space of the particle gives rises to a discrete, finite momentum space defined by

$$|\stackrel{~}{\psi }_N(k,t)=\frac{1}{\sqrt{N}}\underset{x=0}{\overset{N}{}}|\psi _N(x,t)e^{2\pi ikx/N},$$
(14)
for $`k\{0,1,\mathrm{}N1\}`$. From here it is possible to proceed in a similar manner to that shown in Sec. II.1 for a walk on an infinite line. Equation (3) may be used again, with the discrete version of $`𝐂_k^{(\text{gen})}`$ given by

$$𝐂_k^{(N)}=\left(\begin{array}{cc}\sqrt{\rho }e^{2\pi ik/N}& \sqrt{1\rho }e^{i(2\pi k/N+\theta )}\\ \sqrt{1\rho }e^{i(2\pi k/N+\varphi )}& \sqrt{\rho }e^{i(2\pi k/N+\theta +\varphi )}\end{array}\right).$$
(15)
This may again be diagonalised, yielding eigenvalues

$$\lambda _k^\pm =\pm e^{i\delta }e^{\pm i\omega _k^{(N)}},$$
(16)
where now

$$\mathrm{sin}(\omega _k^{(N)})=\sqrt{\rho }\mathrm{sin}(2\pi k/N\delta ),$$
(17)
compare Eq. (6). The possible solutions for $`\omega _k^{(N)}`$ are bounded by $`\mathrm{sin}^1(\sqrt{\rho })`$, e.g., for $`\rho =1/2`$, there are two solutions for $`\omega _k^{(N)}`$ one in each of the regions $`[\pi /4,3\pi /4]`$ and $`[\pi /4,3\pi /4]`$. The first solution corresponds to $`\lambda _k^+`$ and the second to $`\lambda _k^{}`$.

Classically, a random walk on a cycle tends to a uniform distribution over all points on the cycle at long times. Since the quantum walk is unitary and reversible, it never reaches a uniform distribution, the initial state influences the particle’s dynamics at all later times. However, we can define a time-averaged distribution Aharanov et al. (2001) which does tend to a limiting value for large $`T`$,

$$\overline{P}(x,T)=\frac{1}{T}\underset{t=0}{\overset{T1}{}}P(x,t),$$
(18)
where $`P(x,t)=|U^t|\psi _N(x,0)|^2`$. It is proven in Aharanov et al. (2001) that

$`\underset{T\mathrm{}}{lim}\overline{P}(x,T)`$ $`=`$ $`{\displaystyle \underset{v,u\lambda _v=\lambda _u}{}}\psi _N(x,0)|\varphi _v^\pm \varphi _u^\pm |\psi _N(x,0)`$ (19)
$`\times `$ $`{\displaystyle \underset{a}{}}x,a|\varphi _v^\pm \varphi _u^\pm |x,a,`$
where the sum is taken only over degenerate eigenvectors of the position space evolution matrix $`𝐔`$, which are denoted by $`|\varphi _v^\pm `$, $`|\varphi _u^\pm `$, with eigenvalues $`\lambda _v^\pm =\lambda _u^\pm `$. The general initial state is once again $`|\psi _N(x,0)=\sqrt{\eta }(|R+e^{i\alpha }\sqrt{1\eta }|L)|0`$. For the walk on a $`N`$-cycle, the eigenvectors of $`𝐔`$ in the position basis are given by $`|\varphi _v^\pm =|\xi _k^\pm |\chi _k`$, where the $`|\xi _k^\pm `$ are the eigenvectors of the matrix $`𝐂_k^{(N)}`$ and $`|\chi _k=\frac{1}{\sqrt{N}}_xe^{2\pi ikx/N}|x`$, i.e., a discrete Fourier transform of the usual particle position basis states. (We omit labels of $`N`$ from $`|\xi _k^\pm `$ and $`|\chi _k`$ to keep the notation less cluttered.) The associated eigenvalues of $`𝐔`$ are (by construction) equal to those of the matrices $`𝐂_k^{(N)}`$, namely $`\lambda _k^\pm `$. Hence we can rewrite Eq. (19) in terms of the eigenvectors of $`𝐂_k^{(N)}`$,

$`\underset{T\mathrm{}}{lim}\overline{P}(x,T)`$ $`=`$ $`{\displaystyle \underset{a,k,j,b,c}{}}\psi _N(x,0)|\chi _k,\xi _k^b\chi _j,\xi _j^c|\psi _N(x,0)`$ (20)
$`\times `$ $`x,a|\chi _k,\xi _k^b\chi _j,\xi _j^c|x,a.`$
The sum is taken over $`k,j,b`$ and $`c`$ such that $`\lambda _k^b=\lambda _j^c`$. It was shown in Aharanov et al. (2001) that since the $`|\chi _k`$ induce a uniform distribution over the nodes, the limiting distribution will also be uniform if all eigenvalues are distinct. The eigenvalues are degenerate in the general case if there exist non-trivial solutions for

$$\mathrm{sin}(2\pi k/N\delta )=\mathrm{sin}(2\pi j/N\delta ).$$
(21)
This equation has solutions $`k=j`$ and $`k+j\text{(mod }N\text{)}=N/\pi (\delta +\pi /2)`$. The first is trivial, but whether the second solution has roots depends on the coin flip operator and on $`N`$. For example, when a Hadamard coin is used, $`\theta =\varphi =\delta =0`$ so the condition becomes $`k+j\text{(mod }N\text{)}=N/2`$ which has roots only for even $`N`$. Thus for a Hadamard walk, cycles with an odd number of nodes converge to the uniform distribution and those with an even number converge to a non-uniform distribution derived below. However, for a given $`N`$, the coin flip operator with $`(\delta +\pi /2)=\pi /N`$ gives roots when $`k+j\text{(mod }N\text{)}=1`$ which always has a solution, leading to a non-uniform limiting distribution. Conversely, if $`\delta `$ is not a rational multiple of $`\pi `$, there can be no solutions, and so the walk will always mix to the uniform distribution. Thus, by appropriate choice of coin operator, a walk on any size cycle can be made to converge either to a uniform or to a non-uniform probability distribution. This is in direct contrast to the classical case, in which the properties of the limiting distribution depend solely on the form of the graph.

We note that the limit as the cycle size $`N\mathrm{}`$ leads to the condition $`\delta =\pi /2`$ for a non-uniform limiting distribution. This gives $`\theta +\varphi =\pi `$, the simplest unbaised coin operator corresponding to this is

$$𝐂_2^{(\text{nu})}=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}\hfill 1& \hfill i\\ \hfill i& \hfill 1\end{array}\right).$$
(22)
However, the practical limit of infinite cycle size is the walk on a line, where the the opposite edges of the walk never meet, and conditions for non-uniform distributions are not meaningful.

It is possible to derive the limiting distribution when there exist degenerate eigenvalues of the evolution operator $`𝐔`$. In these cases, the summation in Eq. (20) contains two distinct types of terms, those for which $`k=j`$ and those for which $`j=N/\pi (\delta +\pi /2)k\mathrm{\Phi }k`$,

$`\underset{T\mathrm{}}{lim}`$ $`\overline{P}(x,T)={\displaystyle \underset{a,k,b}{}}[|\psi _N(x,0)|\chi _k,\xi _k^b|^2|x,a|\chi _k,\xi _k^b|^2`$ (23)
$`+`$ $`\psi _N(x,0)|\chi _k,\xi _k^b`$$`\chi _{\mathrm{\Phi }k},\xi _{\mathrm{\Phi }k}^b|\psi _N(x,0)`$
$`\times x,a|\chi _k,\xi _k^b\chi _{\mathrm{\Phi }k},\xi _{\mathrm{\Phi }k}^b|x,a].`$
Using $`|x|\chi _k|^2=1/N`$, $`_a|a|\xi _k^b|^2=1`$ and $`_{k,b}|\psi _N(x,0)|\chi _k,\xi _k^b|^2=1`$, the first term is easily seen to be the uniform distribution ($`1/N`$). In the second term, the factor that determines the form of the limiting distribution is

$$x|\chi _k\chi _{\mathrm{\Phi }k}|x=e^{4\pi ix/N(kN\delta /2\pi N/4)},$$
(24)
which controls the sign of the terms in the sums. When $`x=0`$, all the terms in the summation are positive, leading to a spike in the distribution about the origin. Similarly, if $`x=N/2`$, the phase of each term is $`2\pi (kN\delta /2\pi N/4)`$ so the terms add coherently (remember $`(N\delta /\pi N/2)`$ is an integer). Specifically, for the Hadamard coin, $`\delta =0`$ and the contribution to the sum is positive if $`N/2`$ is even, i.e., $`N`$ is divisible by four, or negative if $`N/2`$ is odd, leading to a minimum. The Hadamard case has been independently calculated in more detail by Bednarska et al. Bednarska et al. (2003), who also explore some possibilities for highly non-uniform limiting distributions generated by initial states superposing several particle positions.

The effects of different coin flip operators have received little attention in the literature to date, perhaps due to the minimal effect they have for a walk on a line. However, for quantum walks containing closed cycles, the choice of coin flip operator determines which phase the wavefronts have when they meet up with each other, selecting between whether constructive or destructive interference occurs. Note that in Kendon and Tregenna (2003) it was shown that decoherence in a walk on a cycle causes all initial states and coin operators to mix to the uniform distribution even while there is still a clear quantum speed up over the classical mixing times. The coherence required for non-uniform limiting distributions is thus much more stringent than that required for a quantum speed up of the mixing time over classical. This suggests that in order to use the effects non-uniform limiting distributions it will be more useful if they have properties that can be measured after relatively few steps of the walk, rather than waiting for long times.

## III Graphs of Degree Three

Regular lattices of degree three have been studied briefly numerically Mackay et al. (2002), where the spreading rate was shown to be faster than classical. The “glued trees” graph used for the algorithm presented in Ref. Childs et al. (2002) is also of degree three apart from the special start and end points that form the roots of the two binary trees, see Fig. 2.

This structure is highly symmetric, despite the random connections in the middle, and provided a symmetric initial state is used at the entrance node, the whole quantum walk process can be mapped to a walk on a line (the column positions shown in Fig. 2) with different biases in the probabilities for moving right or left at each step. Childs et al. Childs et al. (2002) use a continuous time walk for their algorithm, but if a three dimensional coin based on Grover’s diffusion operator with elements $`2/d\delta _{ij}`$,

$$𝐂_3^{(G)}=\frac{1}{3}\left(\begin{array}{ccc}\hfill 1& \hfill 2& \hfill 2\\ \hfill 2& \hfill 1& \hfill 2\\ \hfill 2& \hfill 2& \hfill 1\end{array}\right),$$
(25)
is used with a discrete walk, the amplitude also interfers constructively in the right way to reach the opposite root of the trees quickly with high probability Watrous (2002); Kendon and Tregenna (2003), see Fig. 3.

The Grover coin is biased but symmetric. The DFT (discrete Fourier transform) coin is unbiased, but asymmetric in that you cannot interchange the labels on the directions without changing the coin operator. For $`d=3`$, it looks like

$$𝐂_3^{(D)}=\frac{1}{\sqrt{3}}\left(\begin{array}{ccc}1& 1& 1\\ 1& e^{i\omega }& e^{i\omega }\\ 1& e^{i\omega }& e^{i\omega }\end{array}\right),$$
(26)
where $`e^{i\omega }`$ and $`e^{i\omega }`$ are the complex cube roots of unity, For $`d=2`$, the DFT coin reduces to the Hadamard coin, Eq. (13). If a DFT coin is used instead of a Grover coin on the “glued trees” graph, this keeps the amplitude near the starting point and the walk does not spread out even as far as a classical random walk, see Fig. 4. While this is not useful in the context of the “glued trees” problem, it is still highly non-classical behaviour, and with the right problem and initial coin state, the DFT coin operator may find its place in a useful quantum walk algorithm.

## IV Graphs of Degree Four

Quantum walks on regular two dimensional lattices have been investigated numerically by Mackay at al. Mackay et al. (2002). They found that the choice of coin operator gave different prefactors to the linear spreading rate of the quantum walk (compared to quadratic classically) and showed some different symmetries for different coin operators.

Here we present a more systematic (but by no means comprehensive) investigation of the effects of different unbiased coin operators combined with different initial states. We consider mainly an unbounded, regular, square lattice, but also consider the cases where the edges are joined in either normal periodic boundary conditions to give a torus, or twisted to give a Klein bottle.

### IV.1 Quantum Walk on a Two Dimensional Lattice

One obvious generalisation of a Hadamard coin to two spatial dimensions is to take two Hadamard coins, one for left or right ($`|L`$, $`|R`$), and one for up or down ($`|U`$, $`|D`$). As shown in Mackay et al. (2002), this simply produces the same pattern as the Hadamard coined walk on a line in both directions, because the coin operator does not mix the two directions in any way, see Fig. 5.

The standard deviation is the same for all choices of initial state that produce a symmetric distribution, even maximally mixed, and is $`\sqrt{2}`$ larger than the standard deviation for the walk on the line, as noted by Mackay et al. Mackay et al. (2002).

More interesting are the degree-4 DFT coin,

$$𝐂_4^{(\text{D})}=\frac{1}{2}\left(\begin{array}{cccc}\hfill 1& \hfill 1& \hfill 1& \hfill 1\\ \hfill 1& \hfill i& \hfill 1& \hfill i\\ \hfill 1& \hfill 1& \hfill 1& \hfill 1\\ \hfill 1& \hfill i& \hfill 1& \hfill i\end{array}\right),$$
(27)
and degree-4 Grover coin,

$$𝐂_4^{(\text{G})}=\frac{1}{2}\left(\begin{array}{cccc}\hfill 1& \hfill 1& \hfill 1& \hfill 1\\ \hfill 1& \hfill 1& \hfill 1& \hfill 1\\ \hfill 1& \hfill 1& \hfill 1& \hfill 1\\ \hfill 1& \hfill 1& \hfill 1& \hfill 1\end{array}\right),$$
(28)
(the only case where the Grover coin is unbiased), both used in Ref. Mackay et al. (2002). Typical results for these coins and a symmetric initial coin state

$`|\psi _0^{(\text{sym})}`$ $`=`$ $`{\displaystyle \frac{1}{2}}\left(|LD+i|LU+i|RD|RU\right)|0`$ (29)
$`=`$ $`{\displaystyle \frac{1}{2}}\left(|L+i|R\right)\left(|D+i|U\right)|0,`$
with the particle starting at the origin are shown in Figs. 6 and 7.

As noted in Sec. II, there is essentially only one type of coin operator for the quantum walk on a line, the Hadamard operator, with the full range of outcomes accessible by adjusting the coin initial state. For the walk on a two dimensional lattice, the situation is obviously more complicated: the three coins illustrated so far give distinctly different results whatever initial coin state is chosen. The full range of possibilities is determined by the SU(4) group structure of the unitary coin operator, but in order to sample the possibilities numerically, we chose to look at unbiased coins (all elements have modulus one half) and to further restrict those elements to be $`\pm 1/2`$ or $`\pm i/2`$. Choosing the leading diagonal entry to be $`+1/2`$ leads to a set of 640 such unitary coin operators, however, there is a high degree of redundancy if one groups all results that are the same apart from rotation or reflection. This can be done by using a simple initial state of (say) $`|RU`$, and recording the second moment of the distribution. The 640 coin operators then fall into just 10 types, with either 32, 64 or 128 coin operators of the original 640 in each type (more symmetric distributions have fewer variations). The Hadamard, Grover and DFT coin operators are all of different types.

We then varied the initial state of the coin, and looked for the maximum and minimum second moments. These always occured for symmetric distributions (zero first moment), the second moment is thus equal to the variance in these cases. Our results contradict those of Mackay et al., whose choices of initial states did not fully exploit the properties of the Grover coin. Out of the ten types, the Grover type coin can produce both the maximum and minimum possible second moments, meaning that depending on the initial state, it can either spread fastest or slowest from the starting point. The distributions make clear why, see Fig. 7. They have an imperfect circular symmetry on the square lattice, with a central spike, and a ring with something like the profile of the distribution of the walk on a line superimposed on it. The different initial states control how much of the distribution is in the central spike and how much is in the ring, leading to the minimum and maximum values of the standard deviation. In fact, most of the distribution ends up in the central spike, except for exactly the right choice of initial state,

$$|\psi _0^{(\text{G})}=\frac{1}{2}\left(|LD|LU|RD+|RU\right).$$
(30)
Figure 8 shows the distribution produced from this initial state, the contrast with Fig. 7 due to the absense of the central spike is striking (though note the vertical axes have different scales). Shenvi et al. exploit this property of the Grover operator in a different way in their quantum walk search algorithm Shenvi et al. (2003). Here they perturb the coin operator by applying a different operation just at one marked vertex. This causes an initially uniform particle distribution over the whole lattice to converge on the marked vertex, the reverse of a quantum walk starting at the origin and spreading out.

A DFT coin is not so symmetric (at most rotationally symmetric through $`\pi `$, whereas both Hadamard and Grover coin operators can produce distributions rotationally symmetric through $`\pi /2`$), but with the right choice of initial condition, it too can produce a ring shape with no central spikes, see Fig. 9.

The initial state that produces this distribution is

$$|\psi _0^{(\text{D})}=\frac{1}{2}\left(|LD+\frac{1i}{\sqrt{2}}|LU+|RD\frac{1i}{\sqrt{2}}|RU\right).$$
(31)
The results presented by Mackay et al. Mackay et al. (2002) did not test a sufficiently wide range of initial states to draw representative conclusions about the effects of entangled coins on the distributions obtained for the quantum walks. They attributed faster spreading to lack of entanglement between the coin directions. However, the differences we have found between Hadamard coins and Grover or DFT coins are not in the degree of spread per se, but in the extent to which this can be varied simply through varying the initial coin state. Both the Grover and DFT coins produce faster spreading than the Hadamard coins with the initial states noted above.

### IV.2 Cycles in two dimensions

By joining a square or rectangular section of a two dimensional lattice at opposite edges, the walk space becomes periodic in both directions. In one dimension there is only the $`N`$-cycle, but in two dimensions the edges can be joined directly, or twisted like a Möbius strip. This gives three structures that are two dimensional analogues of the $`N`$-cycle, a torus, a closed Möbius strip, and a Klein bottle, depending on whether none, one, or both pairs of the edges are joined twisted. Periodic boundary conditions of these types are easy to implement numerically. We tested a range of such structures using the same coins as for the walk on a lattice, and found similar results to those for a walk on a $`N`$-cycle with respect to mixing times and limiting distributions. Further results for two dimensional cycles are presented at the end of Sec. VI.

## V Graphs of higher degree

For completeness, we mention that the hypercube, first studied by Moore and Russell Moore and Russell (2002), and later found by Kempe Kempe (2002) to illustrate the possibility of an exponential speed up with quantum walks, uses a higher dimensional coin. A hypercube with $`2^N`$ vertices has exactly $`N`$ connections to each vertex and thus requires a $`N`$ dimensional coin Hilbert space. Shenvi et al. Shenvi et al. (2003) also based their quantum walk search algorithm on a hypercube, though as they note, other lattices, such as a square lattice, will do equally well. The symmetry of the hypercube with a Grover coin is such that with a symmetric initial state, the whole problem may be mapped to a walk on a line with a variable coin operator, in the same way as for the “glued trees” graph (see Sec. III). Consquently, there is a wide range of possibilities with less symmetric higher dimensional coins yet to be explored.

## VI Periodicity in Quantum Walks

Systematic study of a quantum walk on a $`N`$-cycle, (described in Sec. II.2), shows that among the smaller values of $`N`$, a number of completely periodic walks arise. This is the opposite property to mixing: here the walk returns exactly to its initial state after a finite number of steps $`\mathrm{\Omega }`$, whereupon it repeats the same set of steps and returns exactly again after $`2\mathrm{\Omega }`$ steps, and so on. There is no classical analogue of this property for random walks, since in the classical case the dynamics are not deterministic. A classical random walk on a cycle will return to its starting state at irregular, unpredictable times. Note too, that this periodicity is not connected with whether the limiting distribution is uniform or not, since here we are concerned with exact return to the initial state, rather than the time-averaged quantity in Eq. (18). Related ideas in continuous time walks have been studied by Ahmadi et al. Ahmadi et al. (2002), where they are concerned with exact instantaneous uniform mixing, rather than exact instantaneous return to the initial state.

Using a Hadamard coin, the “cycle” of size $`N=2`$ is trivially periodic, returning to its original state after two steps. A cycle of size $`N=4`$ has a period of eight steps. This was first noted by Travaglione and Milburn Travaglione and Milburn (2002). The cycle with $`N=8`$ has a period of 24 steps, but $`N=16`$ is chaotic and does not return to its initial state exactly even after many thousands of steps. This is illustrated in Fig. 10, where the probability of the particle being at its initial position is plotted as a function of the time step. A probability of one is an exact return to the initial state (modulo the coin state, which is not shown here, but does also, in fact, return to exactly the initial state). If the coin is allowed to be biased, then a few more periodic examples can be found, $`N=6`$ with period 12, and $`N=10`$ with period 60. With judicious choice of phases in place of the Hadamard phases of $`\theta =\varphi =0`$, $`N=3`$ has a period of 12, and $`N=5`$ has a period of 60, clearly related to $`N=6`$ and $`N=10`$ respectively, but these were the only odd-$`N`$ cycles we found. These results are summarised in Table 1.

The condition that must be satisfied for exact periodicity is obtained from Eq. (11), which also holds for the walk on a cycle if the appropriate forms for the eigenvalues and eigenvectors are substituted. The wavefunctions $`|\psi _t`$ at two different times, $`t`$ and $`t+\mathrm{\Omega }`$ are set equal, giving

$$(\lambda _k^\pm )^\mathrm{\Omega }=1k\{0,1\mathrm{}N1\}.$$
(32)
Using Eq. (16) gives

$`(\delta +\omega _k)\mathrm{\Omega }`$ $`=`$ $`2\pi j_+,`$
$`(\delta \omega _k+\pi )\mathrm{\Omega }`$ $`=`$ $`2\pi j_{},`$ (33)
where $`j_\pm `$ are integers. Substituting these into Eq. (17) gives

$$\mathrm{cos}\left(\frac{\pi j}{\mathrm{\Omega }}\right)=\sqrt{\rho }\mathrm{cos}\left(\frac{2\pi k}{N}\frac{\pi m}{\mathrm{\Omega }}\right)k,$$
(34)
where $`\rho `$ is the bias in the coin operator, $`m`$ is an integer specifying the relative phases in the coin operator through $`m\pi /\mathrm{\Omega }\pi /2=\delta =(\theta +\varphi )/2`$, $`k`$ is the integer Fourier variable, and $`j`$ is an integer that can be different for each $`k`$, but must be odd or even to match whether $`m`$ is odd or even. Clearly, the larger $`N`$ is, the harder it is to find solutions for Eq. (34) for all $`k`$ at the same time (apart from the trivial solutions for $`\rho =0`$ or 1). We do not know if we have found all possible solutions that give periodic quantum walks on a cycle, but we conjecture that there are only a finite number of such solutions and that we have found nearly all if not all of them.

We also studied periodicity on two dimensional cycles, as described in Sec. IV.2. With a Hadamard coin and a torus made from suitable small dimensions, periodicity is also obtained in the cases predictable from Table 1. For a closed Möbius strip or Klein bottle, the twisted dimension is only periodic if the size is half that in Table 1, because the twist causes the walk to traverse the cycle twice before returning to its initial state. The Grover coin shows the same periodicities as the Hadamard coin. However, a DFT coin only shows perodicity for a torus of dimensions $`4\times 4`$, and not at all on the twisted surfaces. This is due to the asymmetry of the DFT coin compared to the Grover and Hadamard coins. During the double circuit of the twisted surface, the wavefunction interfers with a mirror image of itself, so periodicity will only be observed with coins that produce suitably mirror symmetric distributions.

## VII Summary

We have studied discrete, coined quantum walks on regular lattices, in one and two spatial dimensions (graphs with vertices of degree two, three and four). Both the bias (away from equal probability of choosing each direction) and the phases in the coin operator, and the initial state of the coin, can be used to control the evolution of the quantum walk. In a quantum walk on a line, we have found a biased initial state of the coin which produces a higher degree of asymmetry than the simple $`|L`$ or $`|R`$ initial states. The same bias produces a symmetric distribution when combined with the opposite phase between the coin components. This illustrates two distinct ways to obtain the same symmetric distribution, by interference, and by combination of two orthogonal biased distributions each a mirror image of the other. In a quantum walk on a cycle, we have determined the condition for mixing to a uniform limiting distribution, for a general coin operator and initial state. Non-uniform limiting distributions are highly sensitive to decoherence, so to make use of the properties of such walks, it will be best to measure effects that occur after a reasonably short number of steps of the walk. Quantum walks of degree three have a more interesting choice of coin operators, an example in which a Grover coin solves a problem (“glued trees”) efficiently, while a DFT coin stays nearer the starting point than even a classical random walk illustrate the range of possibilities to be explored. Numerical study of regular lattices in two dimensions (degree-4 graphs) show that the Grover and DFT coins have interesting properties independent of the symmetry of the lattice (circular spreading on a square lattice). Suitable choice of initial state makes the Grover coin spread fastest or slowest out of all the coin operators tested, in contrast to the conclusions in Mackay et al. (2002), where only a few initial states were tested. Finally, a small set of exactly periodic quantum walks on cycles of sizes 2, 3, 4, 5, 6, 8, and 10 have been found, and the condition on which this exact periodicity depends derived. Such periodicities are of interest in their own right, and we also suggest that it may be possible to exploit them to pick out small scale regularities in larger structures.

###### Acknowledgements.

We thank Julia Kempe, Peter Knight, and Jiannis Pachos for useful discussions. VK thanks the Mathematical Science Research Institute in Berkeley, CA, for hospitality during the Quantum Computing Program in Fall 2002, and the participants of that programme for many stimulating discussions. BT and VK funded by the UK Engineering and Physical Sciences Research Council.


format: text

text:
# The Chandra Detection of Galactic Center X-ray Features G359.89-0.08 and G359.54+0.18

## 1 Introduction

The central region of our Galaxy hosts many unique and filamentary radio features (e.g., Yusef-Zadeh, Morris, & Chance 1984; Morris & Serabyn 1996; Ekers et al. 1983; Anantharamaiah et al. 1991). Most prominent of these are the non-thermal filaments (NTFs), the brightest of which extend for up to 20′ ($``$50 pc at the 8.0 kpc distance of the Galactic center (GC)). Radio polarization measurements show that the NTFs represent synchrotron radiation from relativistic particles on local magnetic fields (Yusef-Zadeh & Morris 1987; Lang, Morris & Echevarria 1999).

These NTFs are oriented in directions essentially perpendicular (within $``$20$`\mathrm{°}`$) to the Galactic plane and are thought to trace a large-scale poloidal magnetic field configuration in the GC region. However, the origin of the magnetic field arrangement in the GC, and the source of particles and their acceleration in the NTFs remain unclear (e.g., Morris & Serabyn 1996). Less extensive versions of these NTFs are also apparent throughout the GC region, and show the same physical characteristics, but on smaller scales (Ho et al. 1985; Morris & Yusef-Zadeh 1989; Lang, Morris & Echevarria 1999; LaRosa et al. 2000; LaRosa, Lazio & Kassim 2001).

We have detected three elongated X-ray features in the recent Chandra X-ray Observatory GC survey (GCS), which covers the central $``$300 pc along the Galactic plane (Wang, Gotthelf & Lang 2002a). Most interestingly, we find that the elongated X-ray features are apparently associated with either NTFs or NTF-like radio sources. These apparent associations, if confirmed, have strong implications for understanding the nature of the radio NTFs. In particular, if these X-ray features are also due to synchrotron emission, they directly trace the sites where relativistic particles are freshly accelerated (because the X-ray particles have an extremely short lifetime). Identifying such features would allow us to locate the origin of the particle acceleration in the mysterious radio NTFs.

The analysis of one of these X-ray features, G0.13-0.11 has already been presented (Wang, Lu, & Lang 2002b). A detailed study of the morphology and spectrum of the X-ray and radio emission suggest that G0.13-0.11 represents the leading-edge of a pulsar wind nebula (PWN), produced by a pulsar moving in a strong magnetic field environment. The main body of this PWN is traced by a radio protrusion that may also be related to the well-known nonthermal Radio Arc NTF (Yusef-Zadeh et al. 1984). Here, we present the analysis and interpretation of two similarly-shaped X-ray features, G359.89-0.08 and G359.54+0.18. It should be noted that recently, Sakano et al. (2002) have presented Chandra and XMM-Newton data on G359.89-0.08. This source has also been recorded by Baganoff et al. (2003) in their paper on the Chandra observation of the central 15′ (38 pc) of the Galaxy. However, neither of the two papers has provided a complete physical interpretation of the detected X-ray emission in this unusual elongated X-ray feature. In this paper, we present the detection ($`\mathrm{\S }`$2), analysis ($`\mathrm{\S }`$3) and discussion ($`\mathrm{\S }`$4$``$$`\mathrm{\S }`$6) of the X-ray emission in the features G359.89-0.08 and G359.54+0.18.

## 2 X-ray Observation and Data Reduction

The X-ray data of G359.89-0.08 were obtained using the Advanced CCD Imaging Spectrometer (ACIS-I) onboard the Chandra X-ray Observatory in two observations pointed at Sgr A: OBS#242 was taken on 1999 September 21 with a total exposure time of 51.1 ks; OBS#1561 consists of a series of short exposures from 2000 October 26 to 2001 September 28 with a total integration time of 49.8 ks. G359.89-0.08 is on the ACIS-I2 chip, with an off-axis angle of 3$`\stackrel{}{\mathrm{.}}`$7. G359.54+0.18 was covered by two of the Chandra GC Survey observations (OBS#2268, and #2275) (Wang et al. 2002a). OBS#2268 observation was made on 2001 July 20 with a total integration time of 11.0 ks, and OBS#2275 was made on 2001 July 20, with a total integration time of 12.0 ks. The diffuse X-ray emission feature is located on the ACIS-I0 chip in OBS#2268, with an offset of 3$`\stackrel{}{\mathrm{.}}`$5 from the aimpoint, and in OBS#2273, the feature is located on the ACIS-I3 chip, with an offset of 7′ from the aimpoint.

We calibrated the data using the most recent version of the Chandra data processing software CIAO. After excluding time intervals of high background we obtained 40.2 ks net exposure for OBS #242, 35.7 ks for OBS #1561, 10.9 ks for OBS # 2268, and 11.6 ks for OBS#2275. While the pointing astrometry of OBS #242 is better than 1$`\mathrm{}`$ (Baganoff et al. 2003) and thus no additional calibration is required, we corrected offsets, 0$`\stackrel{}{\mathrm{.}}`$64 and 2$`\stackrel{}{\mathrm{.}}`$05 in the R.A. and Dec, for OBS #1561, and -0$`\stackrel{}{\mathrm{.}}`$11 and 2$`\stackrel{}{\mathrm{.}}`$12 in the R.A. and Dec, for OBS # 2268 and #2275, using the online web tool (http://asc.harvard.edu/cal/ASPECT/fix\_offset/fix\_offset.cgi). The data from OBS #242 and #1561 were co-added in the sky coordinates to improve the counting statistics.

The Chandra data are sensitive to the photons in the energy range 0.5-10 keV for OBS #242 and #1561 and 1-10 keV for OBS # 2268 and #2275 because of an imposed lower energy telemetry cutoff (Wang et al. 2002a). The data, corrected for the CTI effect of the CCD chips with the Penn State software (Townsley et al. 2000), provide a spectral resolution of $`E/\delta E30`$. The spatial resolution, a function of the location in the ACIS-I CCD, is in the range of a couple of arcseconds for the X-ray features discussed here. Both the spatial and spectral resolution in this study are largely limited by the limited counting statistics of the data.

## 3 X-ray Properties

### 3.1 G359.89-0.08

Figure 1 shows the count distribution in this field for energies of 4.0$``$9.0 keV. An elongated concentration of X-ray emission is present near R.A., DEC. (J2000) = 17h45m40$`\stackrel{\mathrm{s}}{\mathrm{.}}`$4, -29$`\mathrm{°}`$04$`\mathrm{}`$29$`\mathrm{}`$, or l,b = 359.89, -0.08. Thus, this source will be referred to as G359.89-0.08. Figure 2 shows the 0.5-4.0 keV band count map overlaid with the contours of the smoothed count distribution in the 4.0-9.0 keV band. The elongation of G359.89-0.08 occurs in the NW–SE direction with a length of $``$24$`\mathrm{}`$ and a width of $`8\mathrm{}`$. We also detect a point-like source (CXOU J174539.6-290413; Figures 1 & 2) with a total of 11 counts detected within an 1$`\stackrel{}{\mathrm{.}}`$5 radius; the expected number of the local background counts is $`3`$ and therefore this detection has a signal-to-noise ratio of $`2.5`$. A comparison of the count rates of the source in the two observations (OBS #242 and #1561) shows no significant variability.

The energy distributions of G359.89-0.08 and CXOU J174539.6-290413 are similar, with counts almost entirely in the energy range above 4.0 keV as Figures 1 and 2 illustrate well. There is no significant soft X-ray enhancement ($`<`$4 keV) associated with either G359.89-0.08 or the point-like source. This implies that they are at about the same distance and that the line-of-sight X-ray absorbing gas column density may be quite large ($`N_H>10^{23}`$ cm-2).

We carried out a spectral analysis of G359.89-0.08 by extracting the spectrum of the extended source from the rectangular region illustrated in Figure 1. The large box in Figure 1 represents the region used for determination of the local background. Because of the limited counting statistics, the spectral fits alone cannot be used to distinguish between models. For example, the spectrum of G359.89-0.08 can be fitted by either a thermal plasma (Raymond & Smith 1977) or a simple power law model, both with a strong interstellar medium (ISM) absorption. Figure 3 shows the best-fit power law model to the data of G359.89-0.08. The parameters of the two different model fits are listed in Table 1. The best fit to the absorbing gas column density is 3.7$`\times 10^{23}`$ cm-2, which, for the power law model gives an X-ray (0.2-10 keV) luminosity of Lx $``$ 1.6$`\times `$1034 $`d_8^2`$ erg s-1, where $`d_8`$ is the distance in units of the distance of the GC, 8 kpc. There is some excess near 6.7 keV (Figure 3), however it is most likely due to background noise fluctuations as this excess is not seen in the XMM data of G359.89-0.08 (Sakano et al. 2002).

With only $``$11 total counts from the point-like source, CXOU J174539.6-290413, little can be said about its spectral shape. We thus assume a power law spectrum with a photon index of 2 and the same absorbing gas column density as the best-fit value obtained for G359.89-0.08 (3.7$`\times 10^{23}`$ cm-2). The detected count flux of 1.4$`\times 10^4`$ counts s-1 then gives a 0.2-10 keV X-ray luminosity of 8 $`\times `$1032 $`d_8^2`$ erg s-1, where $`d_8`$ is the distance in units of 8 kpc.

### 3.2 G359.54+0.18

Figure 4 shows the X-ray emission that appears to be associated with the well-known radio NTF G359.54+0.18. This X-ray feature has a strikingly linear morphology extending for nearly 2′, and corresponds exactly with the brightest portion of the northern of the two radio filaments in G359.54+0.18. While the width of the X-ray feature is broaden in the smoothed image because of the limited counting statistics, the boundary of the X-ray emission appears to correspond well to the width of the radio filament. This clearly suggests that these two features are likely to be physically related. Figure 5 shows the average (but unsmoothed) X-ray intensity as a function of distance perpendicular to its long axis (a cross-cut) from the raw counts image. The width of this X-ray filament is resolved to be $`10`$″. The distance of the radio NTF G359.54+0.18 has now been constrained to be within a few hundred parsecs of the GC (Roy 2003); therefore, the linear size of the X-ray emitting region is approximately 10 pc $`\times `$ 0.5 pc.

The spectral shape of G359.54+0.18 is more difficult to characterize with the only $``$70 counts collected in the 1-10 keV range. We find that the spectrum of G359.54+0.18 is consistent with a power law with a photon index equal to 2 and an X-ray-absorbing gas column density of $`n_H10^{23}`$ cm-2, typical for a source in the GC region. The inferred X-ray luminosity of the filament, Lx(0.2-10 keV) is 2.4$`\times 10^{33}`$ $`d_8^2`$ erg s-1. Alternatively, the spectrum can also be characterized by a Raymond-Smith (1977) thermal plasma of a temperature $``$ 2 keV and a similar luminosity as the above power law fit.

## 4 Radio Properties

Both G359.89-0.08 and G359.54+0.18 have prominent and unusual radio counterparts. We discuss the radio properties of these sources in the following.

### 4.1 G359.89-0.08

Previous radio data on G359.89-0.08 were originally obtained by Yusef-Zadeh & Morris (1987) with the Very Large Array (VLA) radio telescope at 20 cm. These observations of this region, in addition to other VLA archive data, were reprocessed and imaged by Lang et al. (1999). For this study we have re-imaged both the Yusef-Zadeh & Morris (1987) and Lang et al. (1999) data to make new estimates of the flux of radio features for comparison with the X-ray (see below).

Figure 6 shows an overlay of the X-ray emission in G359.89-0.08 and the radio continuum emission from the corresponding “radio wisp”, first recognized by Ho et al. (1985) at 2 and 6 cm and was then shown at 20 cm (e.g., Yusef-Zadeh & Morris 1987). Ho et al. (1985) suggested that the wisp was part of a supernova remnant (SNR) shell with a nonthermal spectrum ($`\alpha `$$``$$``$0.4; where S$`{}_{\nu }{}^{}\nu ^\alpha `$). However, this radio spectral index was not well determined (Ho et al. 1985). We have re-calculated the radio spectral index, using the radio data at 2 and 20 cm. We measured the integrated 20 cm flux of the wisp to be 720 mJy. This flux, together with the 2 cm flux of the wisp of $``$447 mJy (Ho et al. 1985), suggests that the index is $`\alpha `$$``$$``$0.2. The radio luminosity ($`10^710^{11}`$ Hz, derived from the 2 cm flux density and using this spectral index of $``$0.2) is 2.9$`\times 10^{33}`$ $`d_8`$ erg s-1.

Interestingly, only part of the X-ray wisp G359.89-0.08 and the radio wisp overlap spatially. The X-ray intensity centroid of G359.89-0.08 shows an offset of $``$10$`\mathrm{}`$ toward the NW from the centroid of the radio wisp. Although this position offset needs to be explained, the radio wisp is likely to be physically associated with G359.89-0.08. In the 8$`{}_{}{}^{}\times `$6 region around the GC, excluding the SgrA complex, only two isolated nonthermal diffuse radio features have been detected (Ho et al. 1985); the chance for a random superposition of the centroid of the X-ray wisp within the boundaries of one of these two nonthermal radio features is $`5\times 10^3`$. Furthermore, the other two elongated X-ray features detected so far in the GCS (G0.13-0.11 (Wang et al. 2002b); G359.54+0.18, this paper) also have radio counterparts, and we thus expect that the spatial and morphological coincidence between G359.89-0.08 and the radio wisp represents a physical association.

Coil & Ho (1999; 2000) have also argued for a possible association between the radio wisp and a molecular “streamer”, which is projected between the so-called 20 km s-1 cloud M-0.13-0.08 and Sgr A. The lower tip of the streamer coincides spatially with the radio wisp and G359.89-0.08 (see Figure 4 of Coil & Ho (2000) and Figure 6 in this paper). The molecular hydrogen column density of the main body of this streamer is about 1.4$`\times `$1024 cm-2. Since the NH3 emission strength at the lower tip is $``$1/5 of the NH3 emission strength of the main body of the streamer (Coil & Ho 1999; 2000), the molecular hydrogen column density along the line of sight to G359.89-0.08 is about 3$`\times `$1023 cm-2, consistent with the difference ($``$2.7$`\times `$1023 cm-2) between the X-ray absorbing column densities to G359.89-0.08 (3.7$`\times 10^{23}`$ cm-2) and to Sgr A ($``$1023 cm-2) (e.g., Baganoff et al. 2001a). Therefore, G359.89-0.08 is most likely located behind this streamer. We assume here that G359.89-0.08 has a distance comparable with that to the GC and scale the luminosities with $`d_8`$, the distance in units of 8 kpc (distance to GC).

### 4.2 G359.54+0.18

In the case of G359.54+0.18, VLA observations of this source were originally made by Yusef-Zadeh, Wardle, & Parastaran (1997) with the VLA at 3.6 and 6 cm. Their observations (Figure 4) show that this radio NTF extends for 8′ (20 pc) and has a very prominent bi-furcated morphology, which is common of most of the GC NTFs. The 90 to 20 cm spectral index of G359.54+0.18 has been calculated to be $`\alpha `$=$``$0.8 (Anantharamaiah et al. 1991). The radio luminosity ($`10^710^{11}`$ Hz, (derived from a 6 cm flux density of 150 mJy from the region where the X-ray emission is arising and using $`\alpha `$=$``$0.8) is 5$`\times 10^{32}`$ $`d_8`$ erg s-1. Similar to the other well-studied NTFs (e.g. Lang et al. 1999), G359.54+0.18 is characterized by strongly linearly polarized emission and a well-ordered magnetic field along its long axis (Yusef-Zadeh et al. 1997). The 6 to 3.6 cm spectral index is slightly steeper (by $`\alpha `$=$``$0.5) along the eastern side of the NTF than that of the center of the NTF and western side, which may indicate a steepening in the energy distribution to the East.

## 5 Nature of the X-ray Emission

### 5.1 Thermal Emission

The spatial and spectral properties of the X-ray and radio emission presented above provide useful constraints on the physical nature of the X-ray emission in G359.89-0.08 and G359.54+0.18. In the case of G359.89-0.08, the thermal hypothesis requires a temperature $``$13.5 keV (Table 1). No diffuse X-ray feature with such a high thermal temperature is known in the Galaxy. If the X-ray emission is really thermal, the closest possibility is that G359.89-0.08 could be a background cluster of galaxies, although the temperature is still considerably higher than the typical cluster temperature (2$`\times 10^7`$–108 K; Fabian 1994). The small sizes and high fluxes of the observed X-ray emission (Table 1) would further imply a very distant rich cluster. Morphologically, such a cluster should appear relatively round, inconsistent with the wisp-like appearance of G359.89-0.08. This distant cluster hypothesis would also be difficult to interpret the high flux and offset morphology of the apparently associated radio emission. We thus conclude that G359.89-0.08 is not a thermal source.

The thermal interpretation of the X-ray emission associated with G359.54+0.18 has the similar difficulties. In particular, the X-ray morphology of G359.54+0.18 is even more narrowly distributed than G359.89-0.08. If the filament represents a cylinder with a diameter of $``$10$`\mathrm{}`$, the volume of the X-ray-emitting region is then $``$ 5$`\times 10^{55}`$ cm3 at the distance of 8 kpc. ¿From the X-ray luminosity, we can further infer the thermal pressure to be $`8\times 10^9`$ dynes cm-2. Because the magnetic field in the GC region is likely to be in the range of 10-4 to 10-3 Gauss (e.g., Ananthanamaiah et al. 1991; Morris & Serabyn 1996), the corresponding magnetic field pressure (4$`\times 10^{10}`$ to 4$`\times 10^8`$ dynes cm-3/2) is probably not high enough to confine the thermal plasma in such a narrow region. Furthermore, the thermal origin of the X-ray-emitting gas provides no explanation for the nonthermal radio emission, which is much more extended linearly. Therefore, a thermal origin of G359.54+0.18 is problematic.

### 5.2 Nonthermal Emission

Nonthermal X-ray emission in these two sources may arise from synchrotron emission or from inverse Compton scattering. The presence of the nonthermal radio emission is a testimony of the presence of relativistic electrons. Furthermore, it is important to note that the luminosity is considerably greater in X-ray than the radio for both G359.89-0.08 and G359.54+0.18 (§3-4).

The intensity of the inverse Compton scattering is proportional to the energy density of a photon field $`U_{ph}`$. In the GC, the energy density is generally dominated by Far-IR photons, $`10^{10}\mathrm{ergs}\mathrm{s}^1`$ (e.g., Odenwald & Fazio 1984), compared with the energy density of the microwave background radiation, $`U_{ph}4\times 10^{13}`$ erg cm-3, or the radio synchrotron radiation contained in the radio NTFs and NTF-like features, $``$10-16 erg cm-3 (e.g. Yusef-Zadeh et al. 1997; Ho et al. 1985). The Far-IR energy density may be even comparable to the magnetic field energy density ($``$4$`\times `$10$`{}_{}{}^{10}B_{4}^{2}`$ erg cm-3, where $`B_4`$ is the magnetic field strength in units of 0.1 mG; Morris and Serabyn 1996).

The intensity ratio of inverse-Compton scattering over synchrotron radiation is approximately $`\frac{\gamma _c^{2p}U_{ph}}{\gamma _s^{2p}U_B}`$, where $`p`$ is the index of the assumed power law particle energy distribution. The electron that scatters a far-IR photon ($`200`$ $`\mu `$m) to X-ray ($`4`$ keV) would typically have a Lorentz factor $`\gamma _c10^2`$, and is about an order of magnitude less energetic than the particles that are responsible for the observed radio synchrotron emission from the NTFs ($`\gamma _s10^3`$). Therefore, in principle, the inverse-Compton scattering can produce an X-ray intensity that rivals the synchrotron radiation, if $`p=2\alpha +1`$ is significantly less 2 and/or there is a local enhancement of the far-IR photon field. But it is difficult for the inverse-Compton scattering mechanism to explain the fact that the X-ray arises only from part of the radio-emitting regions, especially in the case of G359.54+0.18. The two strands in this NTF are too close positionally for only one of them be affected by a local enhancement of the far-IR photon field, for example. Although IC scattering can not be ruled out completely, it appears that synchrotron radiation provides a more natural interpretation of the X-ray emission of both G359.89-0.08 and G359.54+0.18, which is detailed in the following.

## 6 Origins of Relativistic Particles

### 6.1 G359.89-0.08

#### 6.1.1 Supernova Remnant (SNR) Origin

The first possibility for the origin of synchrotron particles in G359.89-0.08 is the nearby SNR (G359.92-0.09) (Ho et al. 1985; Coil & Ho 2000). Evidence for this SNR is present in the morphology of the radio features in this region, including the apparent circular structure consisting of the radio “wisp” and other shell-like radio sources (Ho et al. 1985). It has been proposed that the SNR shock could generate particles that may be energetic ($`10^{14}`$ eV) enough to produce X-ray synchrotron radiation (e.g., Koyama et al. 1995).

However, it is difficult to associate G359.89-0.08 with this SNR G359.92-0.09. Firstly, if the X-ray synchrotron emission arises from a SNR, a tight spatial correlation between the radio and X-ray emission would be expected if they both arise from particles accelerated by the same SNR shock. Indeed, such correlations are observed in all SNR shells that are dominated by nonthermal radio and X-ray emission, such as SN 1006 (Reynolds & Gilmore 1986; Koyama et al. 1995; Willingale 1996) and RCW 86 (Borkowski et al. 2001). The 10-30″ offset between the radio and X-ray emission in G359.89-0.08, is therefore unusual and difficult to explain, although we can not exclude the possibility that the radio and X-ray features are from different parts of the SNR shell and in projection, overlap.

Secondly, the molecular line (NH3) study of the central 15 pc region of the Galaxy also shows evidence for the interaction between an SNR and the surrounding molecular streamers (Coil & Ho 2000). The velocity gradients and velocity displacement of the southern tip of a molecular streamer thought to be interacting with G359.89-0.08 suggests that the SNR is partially in front of the molecular gas and likely to be embedded in a distribution of disturbed molecular material (Coil & Ho 2000). However, the high X-ray-absorbing gas column density along the line of sight to G359.89-0.08 suggests that the X-ray emission must lie behind some enhancement of molecular material ($`\mathrm{\S }`$4) and is not consistent with an X-ray detection of a SNR shell or arc that lies in front of the molecular gas. The X-ray emission in G359.89-0.08 is unlikely to be a detection of the SNR G359.92-0.09.

For these reasons, we conclude that G359.89-0.08 is unlikely part of the SNR shell and that the X-ray synchrotron emission does not arise from shocked-SNR particles.

#### 6.1.2 Pulsar Wind Nebula (PWN)

We find that the X-ray properties of G359.89-0.08 are consistent with what is expected for a PWN. Both the spectrum and the luminosity of G359.89-0.08 are quite typical for a PWN, which usually has a nonthermal X-ray spectrum with photon index 1.1 to 2.4 and 0.2-10.0 keV X-ray luminosities from 4$`\times `$1032 to 2$`\times `$1037 erg s-1 (e.g., Gotthelf & Olbert 2001).

Naturally, we speculate that X-ray source CXCGCS J174539.6-290413 is the putative pulsar that powers the PWN. Indeed, the X-ray characteristics of this source, though weakly constrained, are consistent with being an isolated young pulsar at the similar distance as G359.89-0.08 (e.g., Becker & Trümper 1997). ¿From the X-ray luminosities of both the source and G359.89-0.08, we estimate the spin-down power $`\dot{E}`$ of the pulsar as $``$4$`\times 10^{36}`$ erg/s (Seward-Wang’s 1988; Becker & Trümper 1997)

The wisp morphology of G359.89-0.08 and the location of the source CXCGCS J174539.6-290413 further suggest that they form a ram-pressure confined PWN (e.g., Wang, Li, & Begelman 1993). When a pulsar moves supersonically in a medium, a bow shock is expected to develop ahead of the pulsar. The pulsar wind is thermalized at the reverse shock, which can lead to acceleration of particles just as in a normal PWN. The ram-pressure of the bow shock then sweeps up the shocked pulsar wind material into a trail in the direction opposite to the pulsar motion. The pulsar wind material in this trail is relativistic plasma and can have a bulk motion that is mildly relativistic. Such systems have been observed recently in N157B (Wang et al. 2001), SNR G5.3-1.0 (Kaspi et al. 2001), and SNR W44 (Frail et al. 1996; Petre et al. 2002).

¿From the length of the X-ray feature $``$3 lyr sin$`{}_{}{}^{1}\theta `$ $`d_8`$, where $`\theta `$ is the angle between the flow direction and the line of sight, we estimate the lifetime of the X-ray emitting particles ($`\tau 40`$ yr $`B_4^{1.5}ϵ^{0.5}`$, where $`B_4`$ is the magnetic field strength in units of 10-4 Gauss and $`ϵ`$ is the photon energy in keV). The bulk motion velocity is thus about 0.15 $`c`$ $`B_4^{1.5}`$sin$`{}_{}{}^{1}\theta `$$`d_8`$, in which a photon energy of 4 keV has been used. With the magnetic field in the GC region in the range of 10-4 to 10-3 Gauss (e.g., Anantharamaiah et al. 1991, Morris & Serabyn 1996), the bulk velocity could be a significant fraction of the speed of light.

The above ram-pressure confined PWN interpretation also provides a natural explanation of the radio wisp and its offset from the X-ray wisp G359.89-0.08. The radio synchrotron particles have a much longer lifetime ($`\tau 6\times 10^5`$ yr $`\nu _{GHz}^{0.5}B_4^{1.5}`$), comparable to, or less than, the age of the pulsar. Thus we expect the radio synchrotron emission from the accumulated particles over the history of the PWN and in a region further offset from the X-ray “trail” (G359.89-0.08). If the centroid of the radio emission represents the location where the pulsar was born, the separation from the pulsar $`4`$ light years then gives an estimate of the pulsar age of $`1.3\times 10^4\mathrm{years}(v_p/100\mathrm{km}\mathrm{s}^1`$, where $`v_p`$ is the proper motion of the pulsar. In addition, the high polarization (10-20$`\%`$), center-filled morphology, and relatively flat non-thermal radio spectrum (Ho et al. 1985; $`\mathrm{\S }`$4) are all consistent with the properties of a PWN. The ratio of the X-ray (0.2-10 keV) luminosity to radio luminosity ($`L_x/L_r`$$``$8) is also comparable to PWNe such as 3C58 (e.g., Helfand & Becker 1987) and SNR G54.1+0.3 (Lu et al. 2002). Thus, we conclude that the ram-pressure confined PWN provides a unified explanation for the linear complex formed by the X-ray source CXCGCS J174539.6-290413, the X-ray emission in G359.89-0.08, and the radio counterpart.

We have also tried to study whether there exists any X-ray spectral evolution along G359.89-0.08 with increase distance from the point source CXCGCS J174539.6-290413. Because all the photons softer than 4 keV from G359.89-0.08 have been absorbed by ISM, we calculate the hardness ratios (the 5.5-9.0 keV counts divided by the 4.0-5.5 keV counts) of the two regions illustrated in Figure 1. The hardness ratio of the upper right region is 1.09$`\pm `$0.15 and that of the lower left region is 1.08$`\pm `$0.15, indicating that no spectral evolution along the length has been detected. However, this is not evidence against a PWN scenario. In a PWN, the X-ray spectrum of the closest region (from the pulsar) is usually flatter than the X-ray spectrum of the furthest region with a photon index difference of $``$0.5 (e.g., Lu et al. 2002; Willingale et al. 2001). Such a photon index difference corresponds to a hardness difference of only 0.10, if we assume that the X-ray spectrum of the furthest region is a power law with a photon index of -2.0. Apparently, the quality of the current data is not high enough to permit a spectral evolution study.

### 6.2 G359.54+0.18

There is no sign for any radio SNR emission near the X-ray filament G359.54+0.18. The NTF G359.54+0.18 is clearly not associated with a SNR and exhibits the morphology and physical properties of the NTFs. In addition, the X-ray emission is detected only in the middle of the northern of the two strands in G359.54+0.18. The southern filament is actually brighter in radio (Figure 5, see also Yusef-Zadeh et al. 1997), which is different from the strong correlation between the surface brightnesses of the nonthermal X-ray and radio emission as seen in SNRs.

Can G359.54+0.18 also be a PWN? There is no evidence for a point-like X-ray source that may represent a young energetic pulsar near G359.54+0.18, and which traces the origin of the relativistic particles. Of course, this lack of a point-like X-ray source alone does not exclude the PWN possibility. The source may be too faint to be detected with the existing data, or the X-ray emission may be beamed away from us. The most serious difficulty of the PWN interpretation is the presence of the two radio filaments and the fact that the X-ray emission is only associated with one of them. One possibility is that the pulsar is moving, and thus on its path, it illuminated the southern strand of G359.54+0.18 in the recent past and is now located near the northern strand of the NTF. Therefore the lack of X-ray emission from the southern strand would then be due to the synchrotron cooling of relativistic particles. The presence of into magnetic field flux tubes may be related to the synchrotron cooling instability of the PWN. But this mechanism does not explain why there are only two adjacent tubes. Furthermore, the radio spectral index of this NTF, $`\alpha `$=-0.8$`\pm `$0.1 (Anantharamaiah et al. 1991), is substantially steeper than the typical for PWNe.

Finally, let us examine the particle acceleration via magnetic reconnection. Magnetic reconnection is a source of inductive electric field, which can accelerate electric particles (Blandford 1994). Observational evidence for particle acceleration by magnetic reconnection has been obtained by investigating the hard X-ray emission of solar flares (e.g., Masuda et al. 1994). However, the actual acceleration process is complicated and has not been well understood so far (Blandford 1994). Nevertheless, the co-existence of the two nearly parallel radio filaments makes the magnetic reconnection an attractive interpretation for G359.89-0.08. The orientation of the magnetic field is found to be parallel to the filaments (Yusef-Zadeh et al. 1997), although the direction of the field lines are unknown. If the lines run in opposite directions in the two filaments, the magnetic reconnection might have occurred in a close contact between the two filaments, leading to the acceleration of particles. This may provide a reasonable explanation for the radio emission from the two filaments. But the mechanism still does not explain why the X-ray emission coincides with one of the filaments, not in-between them. Future, deeper X-ray observations are needed to make closer and better comparisons with the existing detailed radio data on this intriguing NTF.

We thank S. Immler and R. Williams for their comments. This work is supported partially by NASA-grant SAO GO-12068X and NASA LTSA grant NAG5-7935. FJL also appreciates support of the Special Funds for Major State Basic Research Projects and the National Natural Science Foundation of China.


text:
# The Wiener Test for Higher OrderElliptic Equations

1. Introduction. Wiener’s criterion for the regularity of a boundary point with respect to the Dirichlet problem for the Laplace equation \[W\] has been extended to various classes of elliptic and parabolic partial differential equations. They include linear divergence and nondivergence equations with discontinuous coefficients, equations with degenerate quadratic form, quasilinear and fully nonlinear equations, as well as equations on Riemannian manifolds, graphs, groups, and metric spaces (see \[LSW\], \[FJK\], \[DMM\], \[LM\], \[KM\], \[MZ\], \[AH\], \[Lab\], \[TW\] to mention only a few). A common feature of these equations is that all of them are of second order, and Wiener type characterizations for higher order equations have been unknown so far. Indeed, the increase of the order results in the loss of the maximum principle, Harnack’s inequality, barrier techniques, and level truncation arguments, which are ingredients in different proofs related to the Wiener test for the second order equations.

In the present work we extend Wiener’s result to elliptic differential operators $`L()`$ of order $`2m`$ in the Euclidean space $`𝐑^n`$ with constant real coefficients

$$L()=(1)^m\underset{|\alpha |=|\beta |=m}{}a_{\alpha \beta }^{\alpha +\beta }.$$

We assume without loss of generality that $`a_{\alpha \beta }=a_{\beta \alpha }`$ and $`(1)^mL(\xi )>0`$ for all nonzero $`\xi 𝐑^n`$. In fact, the results can be extended to equations with variable (for example, Hölder continuous) coefficients in divergence form but we leave aside this generalization to make exposition more lucid.

We use the notation $``$ for the gradient $`(_{x_1},\mathrm{},_{x_n})`$, where $`_{x_k}`$ is the partial derivative with respect to $`x_k`$. By $`\mathrm{\Omega }`$ we denote an open set in $`𝐑^n`$ and by $`B_\rho (y)`$ the ball $`\{x𝐑^n:|xy|<\rho \}`$, where $`y𝐑^n`$. We write $`B_\rho `$ instead of $`B_\rho (O)`$.

Consider the Dirichlet problem

$$L()u=f,fC_0^{\mathrm{}}(\mathrm{\Omega }),u\stackrel{˚}{H}^m(\mathrm{\Omega }),$$
(1)
where we use the standard notation $`C_0^{\mathrm{}}(\mathrm{\Omega })`$ for the space of infinitely differentiable functions in $`𝐑^n`$ with compact support in $`\mathrm{\Omega }`$ as well as $`\stackrel{˚}{H}^m(\mathrm{\Omega })`$ for the completion of $`C_0^{\mathrm{}}(\mathrm{\Omega })`$ in the energy norm.

We call the point $`O\mathrm{\Omega }`$ regular with respect to $`L()`$ if for any $`fC_0^{\mathrm{}}(\mathrm{\Omega })`$ the solution of (1) satisfies

$$\underset{\mathrm{\Omega }xO}{\text{lim}}u(x)=0.$$
(2)
For $`n=2,3,\mathrm{},2m1`$ the regularity is a consequence of the Sobolev imbedding theorem. Therefore, we suppose that $`n2m`$. In the case $`m=1`$ the above definition of regularity is equivalent to that given by Wiener.

The following result coincides with Wiener’s criterion in the case $`n=2`$ and $`m=1`$.

###### Theorem 1

Let $`2m=n`$. Then $`O`$ is regular with respect to $`L()`$ if and only if

$$_0^1C_{2m}(B_\rho \backslash \mathrm{\Omega })\rho ^1𝑑\rho =\mathrm{}.$$
(3)
Here and elsewhere $`C_{2m}`$ is the potential-theoretic Bessel capacity of order $`2m`$ (see \[AHed\]). If $`n=2m`$ and $`O`$ belongs to a continuum contained in the complement of $`\mathrm{\Omega }`$, condition (3) holds.

The case $`n>2m`$ is more delicate because no result of Wiener’s type is valid for all operators $`L()`$ (see \[MN\]). To be more precise, even the vertex of a cone can be irregular with respect to $`L()`$ if the fundamental solution of $`L()`$:

$$F(x)=F(x/|x|)|x|^{2mn},x𝐑^n\backslash O,$$
(4)
changes sign. Examples of operators $`L()`$ with this property were given in \[MN\] and \[D\]. For instance, according to \[MN\] the vertex of a sufficiently thin 8-dimensional cone $`K`$ is irregular with respect to the operator

$$L()u:=10_{x_8}^4u+\mathrm{\Delta }^2u,u\stackrel{˚}{H}^2(𝐑^8\backslash K).$$

In the sequel, Wiener’s type characterization of regularity for $`n>2m`$ is given for a subclass of the operators $`L()`$ called positive with the weight $`F`$. This means that for all real-valued $`uC_0^{\mathrm{}}(𝐑^n\backslash O)`$,

$$_{𝐑^n}L()u(x)u(x)F(x)𝑑xc\underset{k=1}{\overset{m}{}}_{𝐑^n}|_ku(x)|^2|x|^{2kn}𝑑x,$$
(5)
where $`_k`$ is the gradient of order $`k`$, i.e. $`_k=\{^\alpha \}`$ with $`|\alpha |=k`$.

The positivity of the left-hand side in (5) is equivalent to the inequality

$$_{𝐑^n}_{𝐑^n}\frac{L(\xi )+L(\eta )}{L(\xi \eta )}f(\xi )f(\eta )𝑑\xi 𝑑\eta >0$$

for all non-zero $`fC_0^{\mathrm{}}(𝐑^n)`$.

###### Theorem 2

Let $`n>2m`$ and let $`L()`$ be positive with weight $`F`$. Then $`O`$ is regular with respect to $`L()`$ if and only if

$$_0^1C_{2m}(B_\rho \backslash \mathrm{\Omega })\rho ^{2mn1}𝑑\rho =\mathrm{}.$$
(6)
Note that in direct analogy with the case of the Laplacian we could say, in Theorems 1 and 2, that $`O`$ is irregular with respect to $`L()`$ if and only if the set $`𝐑^n\backslash \mathrm{\Omega }`$ is $`2m`$-thin in the sense of linear potential theory \[L\], \[AHed\].

Let, for example, the exterior of $`\mathrm{\Omega }`$ contain the region

$$\{x:0<x_n<1,\left(x_1^2+\mathrm{}+x_{n1}^2\right)^{1/2}<f(x_n)\},$$

where $`f`$ is an increasing function such that $`f(0)=f^{}(0)=0`$. Then the point $`O`$ satisfies (6) if and only if

$$_0^1|\mathrm{log}f(\tau )|^1\tau ^1𝑑\tau =\mathrm{}\mathrm{for}n=2m+1$$

and

$$_0^1f(\tau )\tau ^{2mn}𝑑\tau =\mathrm{}\mathrm{for}n2m+2.$$

Since, obviously, the operator $`L()`$ of the second order is positive with the weight $`F`$, Wiener’s result for $`n>2`$ is contained in Theorem 2.

We note that the pointwise positivity of $`F`$ follows from (5), but the converse is not true. In particular, the $`m`$-harmonic operator with $`2m<n`$ satisfies (5) if and only if $`n=5,6,7`$ for $`m=2`$ and $`n=2m+1`$, $`2m+2`$ for $`m>2`$ (see \[M2\], where the proof of sufficiency of (6) is given for $`(\mathrm{\Delta })^m`$ with $`m`$ and $`n`$ as above, and also \[E\] dealing with the sufficiency for noninteger powers of the Laplacian in the intervals $`(0,1)`$ and $`[n/21,n/2)`$).

We state some auxiliary assertions of independent interest which concern the so called $`L`$-capacitary potential $`U_K`$ of the compact set $`K𝐑^n`$, $`n>2m`$, i.e. the solution of the variational problem

$$\mathrm{inf}\{_{𝐑^n}L()uu𝑑x:uC_0^{\mathrm{}}(𝐑^n),u=1\mathrm{in}\mathrm{vicinity}\mathrm{of}K\}.$$

These assertions are used in the proof of necessity in Theorem 2.

By the $`m`$-harmonic capacity $`\mathrm{cap}_m(K)`$ of a compact set $`K`$ we mean

$$\mathrm{inf}\{\underset{|\alpha |=m}{}\frac{m!}{\alpha !}||^\alpha u||_{L_2(𝐑^n)}^2:uC_0^{\mathrm{}}(\mathrm{\Omega }),u=1\mathrm{in}\mathrm{vicinity}\mathrm{of}K\}.$$
(7)
###### Lemma 1

Let $`\mathrm{\Omega }=𝐑^n`$, $`2m<n`$. For all $`y𝐑^n\backslash K`$

$`U_K(y)=2^1U_K(y)^2`$
$`+{\displaystyle _{𝐑^n}}{\displaystyle \underset{mj1}{}}{\displaystyle \underset{|\mu |=|\nu |=j}{}}^\mu U_K(x)^\nu U_K(x)𝒫_{\mu \nu }()F(xy)dx,`$ (8)
where $`𝒫_{\mu \nu }(\zeta )`$ are homogeneous polynomials of degree $`2(mj)`$, $`𝒫_{\mu \nu }=𝒫_{\nu \mu }`$ and $`𝒫_{\alpha \beta }(\zeta )=a_{\alpha \beta }`$ for $`|\alpha |=|\beta |=m`$.

###### Corollary 1

Let $`\mathrm{\Omega }=𝐑^n`$ and $`2m<n`$. For all $`y𝐑^n\backslash K`$ there holds the estimate

$$|_jU_K(y)|c_j\mathrm{dist}(y,K)^{2mnj}\mathrm{cap}_mK,$$
(9)
where $`j=0,1,2,\mathrm{}`$ and $`c_j`$ does not depend on $`K`$ and $`y`$.

By $``$ we denote the Hardy-Littlewood maximal operator.

###### Corollary 2

Let $`2m<n`$ and let $`0<\theta <1`$. Also let $`K`$ be a compact subset of $`\overline{B_\rho }\backslash B_{\theta \rho }`$. Then the $`L`$-capacitary potential $`U_K`$ satisfies

$$_lU_K(0)c_\theta \rho ^{2mln}\mathrm{cap}_mK,$$
(10)
where $`l=0,1,\mathrm{},m`$ and $`c_\theta `$ does not depend on $`K`$ and $`\rho `$.

Let $`L()`$ be positive with the weight $`F`$. Then identity (1) implies that the $`L`$-capacitary potential of a compact set $`K`$ with positive $`m`$-harmonic capacity satisfies

$$0<U_K(x)<2\mathrm{on}𝐑^n\backslash K.$$
(11)
In general, the bound $`2`$ in (11) cannot be replaced by $`1`$.

###### Proposition 1

If $`L=\mathrm{\Delta }^{2m}`$, then there exists a compact set $`K`$ such that

$$(U_K1)|_{𝐑^n\backslash K}$$

changes sign in any neighbourhood of a point of $`K`$.

We give a lower pointwise estimate for $`U_K`$ stated in terms of capacity (compare with the upper estimate (9)).

###### Proposition 2

Let $`n>2m`$ and let $`L()`$ be positive with the weight $`F`$. If $`K`$ is a compact subset of $`B_d`$ and $`y𝐑^n\backslash K`$, then

$$U_K(y)c(|y|+d)^{2mn}\mathrm{cap}_mK.$$

Sufficiency in Theorem 2 follows from the next assertion which is of interest in itself.

###### Lemma 2

Let $`2m<n`$ and let $`L()`$ be positive with the weight $`F`$. Also let $`u\stackrel{˚}{H}^m(\mathrm{\Omega })`$ satisfy $`L()u=0`$ on $`\mathrm{\Omega }B_{2R}`$. Then, for all $`\rho (0,R)`$,

$`sup\{|u(p)|^2:p\mathrm{\Omega }B_\rho \}+{\displaystyle _{\mathrm{\Omega }B_\rho }}{\displaystyle \underset{k=1}{\overset{m}{}}}{\displaystyle \frac{|_ku(x)|^2}{|x|^{n2k}}}dx`$
$`c_1M_R(u)\mathrm{exp}\left(c_2{\displaystyle _\rho ^R}\mathrm{cap}_m(\overline{B}_\tau \mathrm{\Omega }){\displaystyle \frac{d\tau }{\tau ^{n2m+1}}}\right),`$ (12)
where $`c_1`$ and $`c_2`$ are positive constants, and

$$M_R(u)=R^n_{\mathrm{\Omega }(B_{2R}\backslash B_R)}|u(x)|^2𝑑x.$$

The present work gives answers to some questions posed in \[M2\]. I present several simply formulated unsolved problems.

1. Is it possible to replace the positivity of $`L()`$ with the weight $`F(x)`$ by the positivity of $`F(x)`$ in Theorem 2?

A particular case of this problem is the following one.

2. Does Theorem 2 hold for the operator $`(\mathrm{\Delta })^m`$, where

$$n8,m=2\mathrm{and}n2m+3,m>2\mathrm{?}$$
(13)
The next problem concerns Green’s function $`G_m`$ of the Dirichlet problem for $`(\mathrm{\Delta })^m`$ in an arbitrary domain $`\mathrm{\Omega }`$.

3. Prove or disprove the estimate

$$|G_m(x,y)|\frac{c(m,n)}{|xy|^{n2m}},$$
(14)
where $`c(m,n)`$ is independent of $`\mathrm{\Omega }`$ and $`m`$ and $`n`$ are the same as in (13).

For $`n=5,6,7`$, $`m=2`$ and $`n=2m+1`$, $`2m+2`$, $`m>2`$ estimate (13) was proved in \[M3\]. In the sequel, by $`u`$ we denote a solution in $`\stackrel{˚}{H}^m(\mathrm{\Omega })`$ of the equation

$$(\mathrm{\Delta })^mu=f\mathrm{in}\mathrm{\Omega }.$$
(15)
Clearly, (14) leads to the following estimate of the maximum modulus of $`u`$

$$u_L_{\mathrm{}}c(m,n,\mathrm{mes}_n\mathrm{\Omega })f_{L_p(\mathrm{\Omega })},$$

where $`p>n/2m`$. However, the validity of this estimate for the same $`n`$ and $`m`$ as in (13) is an open problem. Moreover, the following questions arise.

4. Let $`m=2`$, $`n8`$, and let $`\mathrm{\Omega }`$ be an arbitrary bounded domain. Is $`u`$ uniformly bounded in $`\mathrm{\Omega }`$ for any $`fC_0^{\mathrm{}}(\mathrm{\Omega })`$?

5. Let $`m>2`$ and $`n2m+3`$. Also, let $`\mathrm{\Omega }`$ have a conic singularity. Is $`u`$ uniformly bounded in $`\mathrm{\Omega }`$ for any $`fC_0^{\mathrm{}}(\mathrm{\Omega })`$?

For $`m=2`$, the affirmative answer to the last question is given in \[MP\].

I formulate two related open problems.

6. Let $`m=2`$ and $`n=2`$. Is  $`u`$ Lipschitz up to the boundary of an arbitrary bounded domain, for any $`fC_0^{\mathrm{}}(\mathrm{\Omega })`$ ?

7. Let  $`m=2`$ and $`n3`$. Does $`u`$ belong to the class $`C^{1,1}(\mathrm{\Omega })`$ for any $`fC_0^{\mathrm{}}(\mathrm{\Omega })`$ if $`\mathrm{\Omega }`$ is convex?

According to \[KoM\], the last is true in the two-dimensional case.

I conclude with the following variant of the Phragmén-Lindelöf principle (see \[M3\]).

###### Proposition 3

Let either $`n=5,6,7`$, $`m=2`$ or $`n=2m+1`$, $`2m+2`$, $`m>2`$. Further, let $`\eta u\stackrel{˚}{H}^m(\mathrm{\Omega })`$ for all $`\eta C^{\mathrm{}}(𝐑^n)`$, $`\eta =0`$ near $`O`$. If

$$\mathrm{\Delta }^mu=0\mathrm{on}\mathrm{\Omega }B_1,$$

then either $`u\stackrel{˚}{H}^m(\mathrm{\Omega })`$ and

$$\underset{\rho 0}{\mathrm{lim}\mathrm{sup}}\underset{B_\rho \mathrm{\Omega }}{sup}|u(x)|\mathrm{exp}\left(c_\rho ^1\mathrm{cap}_m(\overline{B}_\rho \mathrm{\Omega })\frac{d\rho }{\rho }\right)<\mathrm{}$$

or

$$\underset{\rho 0}{\mathrm{lim}\mathrm{inf}}\rho ^{n2m}M_\rho (u)\mathrm{exp}\left(c_\rho ^1\mathrm{cap}_m(\overline{B}_\rho \mathrm{\Omega })\frac{d\rho }{\rho }\right)>0.$$

It would be interesting to extend this assertion to other values of $`n`$ and $`m`$.