text:
# Efficient Quantum Algorithms for Shifted Quadratic Character Problems

## 1 Introduction

All known problems that have a polynomial time quantum algorithms but have no known polynomial time classical algorithm are some variant of the Hidden Subgroup Problem. The problem is: given a function on a group $`G`$ that is constant and distinct on cosets of some unknown subgroup, find a set of generators of the subgroup. An example of a problem that can be viewed in this framework is Shor’s algorithm for factoring. In this case the problem reduces to finding the period of a function, which amounts to finding the hidden subgroup of a cyclic group. The variant in this case is that the group size is unknown. Much of the research in quantum algorithms has focused on first reducing the problem to a variant of the Hidden Subgroup Problem (hsp), and then extending the machinery to handle the particular variant. Some examples of this include .

In this paper we introduce the Shifted Legendre Symbol Problem (slsp), which does not appear to be an instance of the Hidden Subgroup Problem. As such, the quantum algorithm for the slsp deviates from the structure of the algorithms that solve the hsp. The quantum component of the previous algorithms has two basic steps. The first is to set up an equal superposition over group elements by computing the Fourier transform, after which some function evaluation is executed, such as $`|x|x,f(x)`$ or $`|x(1)^{f(x)}|x`$. The second step is to Fourier sample the state , i.e. to compute the Fourier transform and measure. The algorithm in this article starts with the state setup as before, but Fourier sampling is not sufficient, because after the second step the resulting distribution is uniform no matter what instance of the problem is given. This is very different from the hsp algorithm, where the distribution induced by Fourier sampling is enough to solve the problem. There is also another difference. In general, a Fourier transform is defined in terms of a group, and as a result previous algorithms relied solely on properties of groups, such as what their irreducible representations are. One variant of the slsp we solve is its extension to general finite fields. In contrast to previous algorithms, our algorithm uses a transform that depends on the fact that there is an underlying field, which supports both addition and multiplication.

The Shifted Legendre Symbol Problem is defined as follows. Given a function $`f`$ and an odd prime $`p`$ such that $`f(x)=\left(\frac{x+s}{p}\right)`$, find $`s`$. Here $`\left(\frac{x}{p}\right)`$ is the Legendre Symbol, which is $`1`$ if $`x`$ is a square mod $`p`$, $`1`$ if it is not, and $`0`$ if $`p|x`$. We also introduce a few variants of this problem. The first variation is the Shifted Jacobi Symbol Problem. The setup is the same as the original problem, except that instead of a prime $`p`$, an odd square free $`n=p_1\mathrm{}p_k`$ is used and the function is $`f_s(x)=\left(\frac{x+s}{n}\right)`$, where $`\left(\frac{x}{n}\right)`$ is the Jacobi symbol. The second variant also keeps $`n`$ unknown. To still be able to define the function a new domain of size $`M`$ is used where $`M`$ is an arbitrary integer much larger than $`n`$ and the shifted Jacobi symbol is repeated out to $`M`$. The quantum algorithm uses a property of the Jacobi symbol to first find the period $`n`$ of the function, and then uses the algorithm for the Shifted Jacobi Symbol Problem. The last variant is a generalization of the slsp to general fields. Here the function is a shifted version of the quadratic character $`\chi `$ over the finite field: $`\chi (x)`$ is $`1`$ if $`x`$ is a square in $`𝔽_q`$, $`1`$ if it is not a square, and $`\chi (0)=0`$. The algorithm in this case is more complicated and involves properties not existing in purely group theoretic problems. In particular the trace of field elements is used in the transform.

The classical complexities of the problems are unknown. When the field size is known, the problem has polynomial query complexity, but it is unknown if they have polynomial time algorithms. In any case, we hope that the general structure of our algorithm will lead to new quantum algorithms.

Related Work. Finding an efficient quantum algorithm for the Shifted Legendre Symbol Problem was originally posed as an open question in van Dam .

Many papers have studied the properties of Legendre and Jacobi sequences, as referenced in . In cryptography, Damgård  has suggested using shifted Legendre and Jacobi sequences as pseudo-random bits in the following sense. The seed to the generators are two unknown values $`s`$ and $`p`$. Consider the sequence $`\left(\frac{s}{p}\right),\left(\frac{s+1}{p}\right),\mathrm{},\left(\frac{s+t1}{p}\right)`$, where $`t`$ is a polynomial in $`\mathrm{log}p`$. If it is hard to predict the next bits $`\left(\frac{s+t}{p}\right),\left(\frac{s+t+1}{p}\right),\mathrm{}`$ from this sequence, then we consider the Legendre sequence ‘unpredictable’. Damgård showed that if Legendre sequences are unpredictable in a very weak sense, then Jacobi sequences (defined similarly) are unpredictable in a very strong sense. Whether or not Legendre sequences are indeed unpredictable is still an open question.

The slsp with unknown $`p`$ is at least as hard as the problem posed by Damgård in the sense that solving the slsp yields the value $`s`$, with which the next bits can be computed. However, it is also potentially easier to solve because an slsp algorithm is allowed to query the string adaptively.

Current problems that have exponential separations between their quantum and classical complexity can be viewed as variants of the Hidden Subgroup Problem. The algorithm to solve these problems first creates a state that is uniform over a coset of a subgroup and then computes the Fourier transform and measures. The recursive Fourier sampling problem  is not directly an instance, but uses the same exact properties in reverse. That is, in the Hidden Subgroup Problem algorithm the Fourier transform takes a state that is uniform over a coset to a perp subgroup state where the coset is encoded in the phases of the basis vectors. The reverse operation is to start with the phases, and to compute the Fourier transform to find the coset. One level of the recursive Fourier sampling problem does this with the subgroup restricted to trivial: the map is $`_{x_2^n}(1)^{xs}|x|s`$, where $`s`$ is the coset. This problem is perhaps the closest in structure to ours, but as mentioned, the new algorithms presented here do not rely only on this property of cosets being taken to perp subgroups with phases.

## 2 Preliminaries

In this section we first define the problems we solve and then we provide other background necessary for the rest of the paper.

For a prime $`p`$, the Legendre Symbol $`\left(\frac{x}{p}\right)`$ is defined to be $`1`$ if $`x`$ is a quadratic residue, $`1`$ if $`x`$ is a quadratic non-residue modulo $`p`$, and $`0`$ if $`p|x`$. The Legendre symbol can be extended in several ways. Here we will do so by defining it for for rings $`_n`$ and finite fields $`𝔽_q`$. For an integer $`n=p_1\mathrm{}p_k`$ the Jacobi Symbol $`\left(\frac{x}{n}\right)`$ is defined by $`\left(\frac{x}{n}\right)=\left(\frac{x}{p_1}\right)\mathrm{}\left(\frac{x}{p_k}\right)`$, where the respective $`\left(\frac{x}{p_i}\right)`$ are Legendre Symbols and the product is over all the prime factors $`p_i`$ of $`n`$, with repetitions. For a finite field $`𝔽_q`$ and $`x𝔽_q`$, the quadratic character $`\chi (x)`$ is $`1`$ if $`x`$ is a quadratic residue, $`1`$ is $`x`$ is a quadratic non-residue, and $`0`$ if $`x=0`$.

We can now define the problems solved in this paper. The first problem is the basic example which the others build on.

###### Definition 1 (Shifted Legendre Symbol Problem)

Given an odd prime $`p`$ and a function $`f_s:𝔽_p\{1,0,1\}`$ such that $`f_s(x)=\left(\frac{x+s}{p}\right)`$ for some $`s𝔽_p`$, find $`s`$.

The first variant extends the definition to rings.

###### Definition 2 (Shifted Jacobi Symbol Problem)

Given a square free odd integer $`n`$ and a function $`f_s:_n\{1,0,1\}`$ such that $`f_s(x)=\left(\frac{x+s}{n}\right)`$. Find the unknown shift factor $`s_n`$.

If the integer $`n`$ is not square free, the Shifted Jacobi Problem does not have a unique answer anymore. Consider for example the equality, $`\left(\frac{x+p}{p^2}\right)=\left(\frac{x+p}{p}\right)\left(\frac{x+p}{p}\right)=\left(\frac{x}{p}\right)\left(\frac{x}{p}\right)=\left(\frac{x}{p^2}\right)`$, for all $`x_{p^2}`$. Instead we could define the task to find one of the values $`s^{}`$ such that $`f_s(x)=\left(\frac{x+s^{}}{n}\right)`$. This problem is again efficiently solvable on a quantum computer.

The goal of the second variant is to also keep $`n`$ unknown in the Shifted Jacobi Symbol Problem. Notice that the slsp with $`p`$ unknown is a special case of this problem.

###### Definition 3 (Shifted Jacobi Symbol Problem, unknown $`n`$)

Given an integer $`M`$ and a function $`f_s:_M\{1,0,1\}`$ such that $`f_s(x)=\left(\frac{x+s}{n}\right)`$ for some integer odd square free $`n`$, with $`n^2<M`$, find $`s`$ and $`n`$.

The last variant is a generalization to all possible finite fields.

###### Definition 4 (Shifted Quadratic Character Problem)

Given $`q=p^r`$, a power of an odd prime $`p`$, and a function $`f:𝔽_q\{1,0,1\}`$ such that $`f(x)=\chi (x+s)`$ for some $`s𝔽_q`$, find $`s`$. Here $`\chi `$ is the quadratic character of $`𝔽_q`$.

We will now give some background on finite fields, the representation we use, and the time it takes to do basic computations.

Consider the finite field $`𝔽_q`$ with $`q`$ the $`r`$th power of the prime $`p`$. In this article the elements $`x𝔽_q`$ are represented as polynomials in $`𝔽_p[X]`$ modulo an irreducible polynomial in $`𝔽_p[X]`$ of degree $`r`$. The $`𝔽_p`$ coefficients of such a polynomial are denoted by $`x_j`$, that is $`x=_{j=0}^{r1}x_jX^j`$. When we write $`|x`$ we mean $`|x_0,x_1,\mathrm{},x_{r1}`$. With this representation the bit-complexity of adding or subtracting two elements of $`𝔽_q`$ is $`O(\mathrm{log}q)`$. Multiplication and division require $`O((\mathrm{log}q)^2)`$ bit operations for this ‘model’ for $`𝔽_q`$. (See, for example, Chapter 6 in  for details on this.)

For a finite field $`𝔽_{p^r}`$ the *trace* of an element $`x`$ is defined by

$`\mathrm{Tr}(x)`$ $`=`$ $`{\displaystyle \underset{j=0}{\overset{r1}{}}}x^{p^j}.`$
By the equality $`(\mathrm{Tr}(x))^p=\mathrm{Tr}(x)`$ we see that the trace maps the elements of the finite field to its base field $`𝔽_p`$. Because $`\mathrm{Tr}(x)`$ is a polynomial of degree $`p^{r1}`$ (less than $`p^r`$), it is a non-constant function. We also have, using $`(x+y)^p=x^p+y^p`$,

$`\mathrm{Tr}(ax+by)`$ $`=`$ $`a\mathrm{Tr}(x)+b\mathrm{Tr}(y)`$
for all $`a,b𝔽_p`$ and $`x,y𝔽_q`$. It follows that the trace of $`x=_{j=0}^{r1}x_jX^j`$ equals the summation $`_{j=0}^{r1}x_j\mathrm{Tr}(X^j)`$ over the base field $`𝔽_p`$. With this property it can be shown that the calculation of $`\mathrm{Tr}(x)`$ requires $`O((\mathrm{log}q)^2)`$ bit operations .

The main operation used in quantum algorithms is the Fourier transform. Here we will need to compute the Fourier transform over $`_p`$ for a large prime $`p`$, which is defined by

$`|x`$ $``$ $`{\displaystyle \frac{1}{\sqrt{p}}}{\displaystyle \underset{y=0}{\overset{p1}{}}}\mathrm{e}^{2\pi \mathrm{i}(xy)/p}|y.`$
It is unknown how to efficiently compute this transformation exactly. Approximations have been given in . From  we have: there is a quantum algorithm which $`ϵ`$-approximates the quantum Fourier transform over $`_p`$ for an arbitrary $`n`$-bit $`p`$ and any $`ϵ`$ and which runs in time $`O\left(n\mathrm{log}\frac{n}{ϵ}+\mathrm{log}^2\frac{1}{ϵ}\right)`$. We will denote the $`p`$th root of unity $`\mathrm{e}^{2\pi \mathrm{i}/p}`$ by $`\omega _p`$.

We will also need a result about Fourier sampling (computing the Fourier transform and measuring) repeated superpositions . Suppose we want to compare the distribution induced by Fourier sampling a state $`|\varphi `$ with the distribution induced by Fourier sampling the state $`|\stackrel{~}{\varphi }`$ which is $`|\varphi `$ repeated many times. It turns out this is possible but we need to define special distributions to do it. The problem is that $`|\stackrel{~}{\varphi }`$ has a larger support, so we need a way to shrink the domain so the two can be compared. The way to do it is to use continued fractions on the result of the sample. We will now formalize this.

For simplicity we will suppress a detail or two to make this more readable. Let $`|\varphi =_{x=0}^{n1}\varphi _x|x`$ be an arbitrary superposition, and let $`\widehat{𝒟}_{|\varphi }`$ the distribution induced by Fourier sampling $`|\varphi `$. Let the superposition $`|\stackrel{~}{\varphi }=c_{x=0}^{M1}\varphi _{xmodn}|x`$ be $`|\varphi `$ repeated until some arbitrary integer $`M`$, not necessarily a multiple of $`n`$, where $`c`$ is the proper normalization constant. Let $`\widehat{𝒟}_{|\stackrel{~}{\varphi }}`$ be the distribution induced by Fourier sampling $`|\stackrel{~}{\varphi }`$. Notice that $`\widehat{𝒟}_{|\varphi }`$ is a distribution on $`\{0,\mathrm{},n1\}`$ and $`\widehat{𝒟}_{|\stackrel{~}{\varphi }}`$ is a distribution on $`\{0,\mathrm{},M1\}`$.

We can now define the two distributions we will compare. Let $`\widehat{𝒟}_{|\varphi }^{\text{RF}}`$ be the distribution induced on the reduced fractions of $`\widehat{𝒟}_{|\varphi }`$, that is, if $`x`$ is a sample from $`\widehat{𝒟}_{|\varphi }`$, we will return the fraction $`x/n`$ in lowest terms. In particular, define $`\widehat{𝒟}_{|\varphi }^{\text{RF}}(j,k)=\widehat{𝒟}_{|\varphi }(jm)`$ if $`mk=n`$. Let $`\widehat{𝒟}_{|\stackrel{~}{\varphi }}^{\text{CF}}`$ be the distribution induced on fractions from first sampling $`\widehat{𝒟}_{|\stackrel{~}{\varphi }}`$ and then running continued fractions on the result and $`M`$. If $`M=\mathrm{\Omega }(\frac{n}{ϵ^2})`$ and $`M=\mathrm{\Omega }(\frac{M}{ϵ})`$, then $`|\widehat{𝒟}_{|\varphi }^{\text{RF}}\widehat{𝒟}_{|\stackrel{~}{\varphi }}^{\text{CF}}|_1`$ is upper bounded by about $`n/\sqrt{M}`$.

This basically says that to understand the distribution induced by Fourier sampling a repeated state, only the distribution induced by Fourier sampling non-repeated state has to be understood. However, it is not the exact distribution of the unrepeated state, since we look at the distribution over reduced fractions. We will use this to solve the unknown $`n`$ case of the Jacobi problem.

## 3 An Algorithm for Prime Size Fields

In this section we give algorithms solving the Shifted Legendre Symbol Problem and variants when working over a finite field of prime size. The main ideas are contained in the algorithm for the Shifted Legendre Symbol Problem, and we can apply the same algorithm to solve the same problem when $`p`$ is unknown, and also to solve the Shifted Jacobi Symbol Problem.

The idea for the algorithm follows from a few known facts. Assume we start the algorithm in the standard way, i.e. by putting the function value in the phase to get $`|f_s=_{i_p}\left(\frac{i+s}{p}\right)|i`$. Assume the functions $`f_i`$ are orthogonal (they are close to orthogonal). Define the matrix $`C`$ where the $`i^{th}`$ row is $`|f_i`$. Our quantum state $`|f_s`$ is one of the rows, so $`C|f_s=|s`$. The issue now is how to efficiently implement $`C`$. $`C`$ is a circulant matrix, i.e. $`c_{i,j}=c_{i+1,j+1}`$. The Fourier transform diagonalizes a circulant matrix: $`C=F_p(F_p^1CF_p)F_p^1=F_pDF_p^1`$, where $`D`$ is diagonal, so we can implement $`C`$ if we can implement $`D`$. It turns out that the vector on the diagonal of $`D`$ is the vector $`F_p|f_0`$, but $`|f_0`$ is an eigenvector of the Fourier transform, so up to a global phase which we can ignore, we are done. To summarize: to implement $`C`$, we compute the Fourier transform, compute $`f_0`$ into the phases (this is just the Legendre Symbol), and then compute the Fourier transform again (it is not important whether we use $`F_p`$ or $`F_p^1`$). We will now present this algorithm step-by-step.

###### Algorithm 1 (Shifted Legendre Symbol Problem)

Input: An odd prime $`p`$ and a function $`f_s`$ such that $`f_s(x)=\left(\frac{x+s}{p}\right)`$ for all $`x_p`$.
Output: $`s`$.

1. Compute the Fourier transform over $`_p`$ of $`|0`$ and compute $`f_s`$ into the phases, approximating:

$$\frac{1}{\sqrt{p1}}\underset{x𝔽_p}{}\left(\frac{x+s}{p}\right)|x$$
2. Compute the Fourier transform over $`_p`$:

$$\frac{1}{\sqrt{p1}}\underset{y𝔽_p}{}\omega _p^{ys}\left(\frac{y}{p}\right)|y$$
3. Compute $`f_0`$ into the phases, approximating:

$$\frac{1}{\sqrt{p}}\underset{y𝔽_p}{}\omega _p^{ys}|y$$
4. Compute the inverse Fourier transform over $`_p`$; this gives the answer $`|s`$.

###### Theorem 1

Algorithm 1 solves the Shifted Legendre Symbol Problem in two queries and polynomial time with probability exponentially close to one.

Proof: The first step is a standard setup used in quantum algorithms. The only difference is that $`f_s`$ evaluates to zero in one position. In this case, just treat it as a one. After this the state is exponentially close to the state shown. Recall that the Legendre Symbol $`\left(\frac{x}{p}\right)`$ is zero when $`p|x`$, so one amplitude is zero.

The result of applying the Fourier transform is (where we replace $`x`$ with $`xs`$)

$`{\displaystyle \frac{1}{\sqrt{p1}}}{\displaystyle \underset{x=0}{\overset{p1}{}}}\left({\displaystyle \frac{x+s}{p}}\right)|x`$ $``$ $`{\displaystyle \frac{1}{\sqrt{p1}}}{\displaystyle \underset{y=0}{\overset{p1}{}}}{\displaystyle \frac{1}{\sqrt{p}}}{\displaystyle \underset{x=0}{\overset{p1}{}}}\left({\displaystyle \frac{x}{p}}\right)\omega _p^{y(xs)}|y.`$
Factoring out the $`\omega _p^{ys}`$ term, using the change of variable $`z=xy`$, and using the facts that $`\left(\frac{zy^1}{p}\right)=\left(\frac{z}{p}\right)\left(\frac{y^1}{p}\right)`$ and $`\left(\frac{y^1}{p}\right)=\left(\frac{y}{p}\right)`$ we have

$$\frac{1}{\sqrt{p1}}\frac{1}{\sqrt{p}}\left[\underset{z=0}{\overset{p1}{}}\left(\frac{z}{p}\right)\omega _p^z\right]\underset{y=1}{\overset{p1}{}}\left(\frac{y}{p}\right)\omega _p^{ys}|y$$

So we are left to evaluate $`_{z=0}^{p1}\left(\frac{z}{p}\right)\omega _p^z`$, which is the Gauß sum , and is $`\sqrt{p}`$ if $`p1mod4`$ and is $`\mathrm{i}\sqrt{p}`$ if $`p3mod4`$. Hence, up to a global constant which we can ignore, the state follows.  $`\mathrm{}`$

###### Corollary 1

Algorithm 1 can be used to solve the Shifted Jacobi Symbol Problem.

Proof: We start with the uniform superposition of $`_n`$ and calculate the function value $`f_s`$ for each element:

$`{\displaystyle \frac{1}{\sqrt{n}}}{\displaystyle \underset{x_n}{}}|x,0`$ $``$ $`{\displaystyle \frac{1}{\sqrt{n}}}{\displaystyle \underset{x_n}{}}|x,\left(\frac{x+s}{n}\right).`$
Next, we measure if the rightmost value is non-zero. If this is the case, which happens with probability $`\varphi (n)/n`$ (where $`\varphi `$ is Euler’s phi function obeying $`\varphi (n)=|_n^{}|`$), the state has collapsed to the superposition:

$$\frac{1}{\sqrt{\varphi (n)}}\underset{x_n^{}}{}|x,\left(\frac{x+s}{n}\right).$$

Otherwise, we simply try again the same procedure. (The success probability $`\varphi (n)/n`$ is lower bounded by $`\mathrm{\Omega }(1/\mathrm{log}(\mathrm{log}n))`$, see , hence we can expect to be successful after $`O(\mathrm{log}(\mathrm{log}n))`$ trials.)

We continue with the reduced state by changing the phase of $`|x`$ to $`\left(\frac{x+s}{n}\right)`$ and uncomputing the function value again, giving

$$\frac{1}{\sqrt{\varphi (n)}}\underset{x_n}{}\left(\frac{x+s}{n}\right)|x.$$

Let $`n=p_1p_2\mathrm{}p_k`$ be the prime decomposition of $`n`$ such that $`_n=_{p_1}\times \mathrm{}\times _{p_k}`$. Using Shor’s algorithm, we can determine these factors efficiently. Because $`\left(\frac{x+s}{n}\right)=\left(\frac{x+s_1}{p_1}\right)\left(\frac{x+s_2}{p_2}\right)\mathrm{}\left(\frac{x+s_k}{p_k}\right)`$, we can just consider each $`p_j`$ component separately (with $`s_1smodp_1`$, $`s_2smodp_2`$, et cetera). Hence, by performing the ‘inverse Chinese remainder’ map $`|x|xmodp_1,\mathrm{},xmodp_k`$, we obtain the state

$`{\displaystyle \underset{x_1_{p_1}}{}}\mathrm{}{\displaystyle \underset{x_k_{p_k}}{}}\left({\displaystyle \frac{x_1+s_1}{p_1}}\right)\mathrm{}\left({\displaystyle \frac{x_k+s_k}{p_k}}\right)|x_1,\mathrm{},x_k`$ $`=`$ $`{\displaystyle \underset{j=1}{\overset{k}{}}}{\displaystyle \underset{x_j_{p_j}}{}}\left({\displaystyle \frac{x_j+s_j}{p_j}}\right)|x_j.`$
But now we use Algorithm 1 on each factor to get $`|s_1,\mathrm{},s_k`$, after which the Chinese remainder theorem gives us the answer $`s`$.  $`\mathrm{}`$

We now give an algorithm for the above problem when also $`n`$ is unknown. In addition to using known techniques, the algorithm depends on the fact that sampling the Fourier transform of the shifted Legendre Symbol results in the uniform distribution on $`_n^{}`$.

###### Algorithm 2 (Shifted Jacobi Symbol Problem, unknown $`n`$)

Input: An integer $`M`$ and a function $`f_s:\{0,\mathrm{},M1\}\{1,0,1\}`$ such that $`f_s(x)=\left(\frac{x+s}{n}\right)`$ for some integer $`n`$, with $`n^2<M`$
Output: $`n`$ and $`s`$.

1. Create the following state as in Corollary 1:

$$c\underset{x=0}{\overset{M1}{}}\left(\frac{x+s}{n}\right)|x$$
2. Compute the Fourier transform over $`_M`$.
3. Measure, with outcome $`i`$, and use continued fractions on $`i`$ and $`M`$, returning $`j/n`$.
4. Run Algorithm 1 using $`f_s`$ and $`n`$.

###### Theorem 2

Algorithm 1 solves the Shifted Jacobi Symbol Problem with unknown $`n`$ in quantum polynomial time with high probability.

Proof: Let $`|\psi _s=\frac{1}{\sqrt{\varphi (n)}}_{x=0}^{n1}\left(\frac{x+s}{n}\right)|x`$ be the state after the setup in Corollary 1 and let $`|\stackrel{~}{\psi }_s=c_{x=0}^{M1}\left(\frac{x+s}{n}\right)|x`$ be the repeated version in Algorithm 2, where $`c`$ is the normalizing constant. We can relate the distributions induced by Fourier sampling $`|\varphi _s`$ and $`|\stackrel{~}{\varphi }_s`$ using the discussion in Section 2. If $`M=n`$ then Lemma 1 implies that $`i`$ is uniformly distributed over $`_n^{}`$ and we would be done since the denominator returned by continued fractions is $`n`$ in this case. However this will still be the case even if $`Mn`$. If $`M`$ is a multiple of $`n`$ and if the Fourier transform of $`|\psi _s`$ is $`_{x=0}^{n1}\alpha _x|x`$, then the Fourier transform of $`|\stackrel{~}{\psi }_s`$ is $`_{x=0}^{n1}\alpha _x|M/nx`$, so we get what we want. If $`M`$ is not a multiple but is large enough, the distributions as discussed in Section 2 are $`ϵ`$-close.  $`\mathrm{}`$

###### Lemma 1

Let $`n`$ be an odd square free integer. If we apply the quantum Fourier transform over $`_n`$ to the superposition of the states $`\left(\frac{x+s}{n}\right)|x`$ for all $`x_n`$, we establish the evolution

$`{\displaystyle \frac{1}{\sqrt{\varphi (n)}}}{\displaystyle \underset{x_n}{}}\left({\displaystyle \frac{x+s}{n}}\right)|x`$ $``$ $`{\displaystyle \frac{\mathrm{i}^{(n1)^2/4}}{\sqrt{\varphi (n)}}}{\displaystyle \underset{y_n}{}}\omega _n^{sy}\left({\displaystyle \frac{y}{n}}\right)|y.`$
Proof: First, we note that we can rewrite the output as

$`{\displaystyle \frac{1}{\sqrt{n\varphi (n)}}}{\displaystyle \underset{y_n}{}}{\displaystyle \underset{x_n}{}}\left({\displaystyle \frac{x+s}{n}}\right)\omega _n^{xy}|y`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{n\varphi (n)}}}{\displaystyle \underset{y_n}{}}\omega _n^{sy}\left[{\displaystyle \underset{x_n^{}}{}}\left({\displaystyle \frac{x}{n}}\right)\omega _n^{xy}\right]|y,`$
by substituting $`x`$ with $`x+s`$ in the summation and using the fact that $`\left(\frac{x}{n}\right)=0`$ for all $`x_n^{}`$.

The amplitudes between the square brackets depend on $`y`$ in the following way. First, we consider the case when $`y`$ is co-prime to $`n`$, that is: $`y_n^{}`$, and there exists also an inverse $`y^1_n^{}`$. We then see that

$`{\displaystyle \underset{x_n^{}}{}}\left({\displaystyle \frac{x}{n}}\right)\omega _n^{xy}`$ $`=`$ $`\left({\displaystyle \frac{y^1}{n}}\right){\displaystyle \underset{z_n^{}}{}}\left({\displaystyle \frac{z}{n}}\right)\omega _n^z,`$
where we used the substitution $`xzy^1`$ and the multiplicativity of the Jacobi symbol.

Next, we look at the case where $`n`$ and $`y`$ have a common, non-trivial, factor $`f`$. We say that $`n=mf`$ and $`y=rf`$, and we know that $`f`$ and $`m`$ are co-prime (because $`n`$ is square free). The Chinese remainder theorem tells us that there is a bijection between the elements $`x_n`$ and the coordinates $`(xmodm,xmodf)_m\times _f`$, which also establishes a one-to-one mapping between $`_n^{}`$ and $`_m^{}\times _f^{}`$. This allows us to rewrite the expression as follows.

$`{\displaystyle \underset{x_n^{}}{}}\left({\displaystyle \frac{x}{n}}\right)\omega _n^{xy}`$ $`=`$ $`{\displaystyle \underset{x_{mf}^{}}{}}\left({\displaystyle \frac{x}{mf}}\right)\omega _{mf}^{xrf}`$
$`=`$ $`{\displaystyle \underset{x_{mf}^{}}{}}\left({\displaystyle \frac{xmodm}{m}}\right)\left({\displaystyle \frac{xmodf}{f}}\right)\omega _m^{xr}`$
$`=`$ $`{\displaystyle \underset{x_1_m^{}}{}}\left({\displaystyle \frac{x_1}{m}}\right)\omega _m^{x_1r}{\displaystyle \underset{x_2_f^{}}{}}\left({\displaystyle \frac{x_2}{f}}\right).`$
Because $`f`$ is odd and square free $`_{x_f^{}}\left(\frac{x}{f}\right)=0`$, and hence the above term equals zero. This concludes the proof of the lemma.  $`\mathrm{}`$

## 4 An Algorithm for General Finite Fields

Here we will solve the general case of the Shifted Legendre Symbol Problem for any finite field $`𝔽_q`$. From now on $`q=p^r`$, with $`p`$ an odd prime and the degree $`r`$ an integer. See Section 2 for details about finite fields. The idea used for the SLSP algorithm cannot be used directly here, since the matrix is no longer circulant. To get around that problem, we use the following map:

###### Lemma 2 (Trace-Fourier Transform over $`𝔽_q`$)

The unitary mapping

$`|x`$ $``$ $`{\displaystyle \frac{1}{\sqrt{q}}}{\displaystyle \underset{y𝔽_q}{}}\omega _p^{\mathrm{Tr}(xy)}|y`$
is computable in polynomial time.

Proof: Assume that the mapping

$`|x`$ $``$ $`{\displaystyle \underset{j=0}{\overset{r1}{}}}|\mathrm{Tr}(xX^j).`$
can be computed in polynomial time. First apply this map, and then compute the Fourier transform over $`_p^r`$. This gives us the final state

$`{\displaystyle \underset{j=0}{\overset{r1}{}}}{\displaystyle \frac{1}{\sqrt{p}}}{\displaystyle \underset{y_j𝔽_p}{}}\omega _p^{\mathrm{Tr}(xX^j)y_j}|y_j`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{q}}}{\displaystyle \underset{y𝔽_q}{}}\omega _p^{\mathrm{Tr}(xy)}|y.`$
We will now show that the map

$`|x`$ $``$ $`|\mathrm{Tr}(x),\mathrm{Tr}(xX),\mathrm{},\mathrm{Tr}(xX^{r1})`$
is reversible. Let $`T(x)=[\mathrm{Tr}(x),\mathrm{Tr}(xX),\mathrm{},\mathrm{Tr}(xX^{r1})]`$. $`T`$ is a linear functional since $`\mathrm{Tr}`$ is, so if $`T(a)=T(b)`$ then $`T(ab)`$ is the zero vector. We will show that $`T(x)`$ is not the zero vector except for $`x=0`$. Suppose $`T(x)`$ is the zero vector. Since $`\mathrm{Tr}`$ is not the zero map, choose $`a𝔽_q`$ such that $`\mathrm{Tr}(a)0`$. Choose $`z_0,\mathrm{},z_{r1}`$ such that $`_jz_jxX^j=a`$. Then $`\mathrm{Tr}(a)=\mathrm{Tr}(_jz_jxX^j)=_jz_j\mathrm{Tr}(xX^j)=0`$, since $`\mathrm{Tr}(xX^j)=0`$ for all $`j`$. But this is a contraction by the choice of $`a`$. So $`T`$ is one-to-one.

We will now show that the map is computable in polynomial time. It is enough if $`x`$ can be computed from $`\mathrm{Tr}(x),\mathrm{Tr}(xX),\mathrm{},\mathrm{Tr}(xX^{r1})`$. But the equations $`\mathrm{Tr}(x)=_{j=0}^{r1}x_j\mathrm{Tr}(X^j)`$, $`\mathrm{Tr}(xX)=_{j=0}^{r1}x_j\mathrm{Tr}(X^{j+1})`$, …, $`\mathrm{Tr}(xX^{r1})=_{j=0}^{r1}x_j\mathrm{Tr}(X^{j+r1})`$ are $`r`$ linear equations in $`r`$ unknowns, and the values $`\mathrm{Tr}(x),\mathrm{Tr}(xX),\mathrm{},\mathrm{Tr}(xX^{r1})`$ and $`\mathrm{Tr}(X^j)`$ for all $`j`$ are known, so the coefficients $`x_j`$ of $`x`$ can be solved for using linear algebra.  $`\mathrm{}`$

(We recently learned that, independently, de Beaudrap *et al.*   have used a transform closely related to the above for the construction of a different quantum algorithm.)

###### Theorem 3

Algorithm 3 (see below) solves the Shifted Quadratic Character Problem over any finite field with two queries and in polynomial time with probability exponentially close to one.

The presentation of the algorithm below differs from the SLSP algorithm in that it does not use approximations. Approximations work here also, but here we show how the problem can be solved exactly if the base field is of fixed size (so that the Fourier transform is not approximate). Also notice that the Trace-Fourier transform is not a unique solution to this problem, any linear functional will work in place of $`\mathrm{Tr}`$.

###### Algorithm 3

Input: A power of a prime $`q=p^r`$ and a function $`f_s`$ such that $`f_s(x)=\chi (x+s)`$.
Output: $`s`$.

1. Use the Fourier transform over $`_{q+1}`$ on $`|0`$, and two queries to $`f_s`$ to create (with probability $`q/(q+1)`$) the state

$$\frac{1}{\sqrt{q}}\underset{x𝔽_q}{}\chi (x+s)|x+\frac{1}{\sqrt{q}}|\delta .$$

With probability $`1/(q+1)`$ this step gives $`s`$ directly.
2. Compute the Trace-Fourier transform of Lemma 2 over $`𝔽_q`$. In the proof it will be shown that the output of this transform equals

$`{\displaystyle \frac{1}{q}}\left[{\displaystyle \underset{z𝔽_q}{}}\chi (z)\omega _p^{\mathrm{Tr}(z)}\right]\left({\displaystyle \underset{y𝔽_q}{}}\chi (y)\omega _p^{\mathrm{Tr}(sy)}|y\right)+{\displaystyle \frac{1}{\sqrt{q}}}|\delta .`$ (1)
The term between the square brackets is known the *quadratic Gauß sum* $`G(𝔽_q)`$, with $`G(𝔽_q)=(1)^{r1}\mathrm{i}^{r(p1)^2/4}\sqrt{q}`$ (see Theorem 11.5.4 in ). With this knowledge we can perform the next step.
3. Uncompute the phases $`\chi (y)`$ for $`y0`$, and change the dummy vector to $`(1)^{r1}\mathrm{i}^{r(p1)^2/4}|0`$. By dropping the general phase $`G(𝔽_q)/\sqrt{q}`$, we can now write

$$\frac{1}{\sqrt{q}}\underset{y𝔽_q}{}\omega _p^{\mathrm{Tr}(sy)}|y$$

for the state.
4. Finally, compute the inverse Trace-Fourier transform over $`𝔽_q`$. This gives us the requested shift parameter as $`|s`$.

Proof: For the first step we create, with one call to $`f_s`$ the superposition

$$\frac{1}{\sqrt{q+1}}\underset{x𝔽_q}{}|x,f_s(x)+\frac{1}{\sqrt{q+1}}|\delta ,1,$$

where $`\delta `$ denotes a ‘dummy state’. Next, we measure if the rightmost bit is zero. If this is the case (probability $`1/(q+1)`$), the state has collapsed to $`|s,0`$, which tells us the value $`s`$ immediately. Otherwise, we are left with the superposition of the entries $`x`$ with $`f_s(x)=\pm 1`$ and the dummy state. This enables us to create the proper phases $`f_s(x)=\chi (x+s)`$ and uncompute (with a second $`f_s`$ query) the rightmost bit, which we will ignore from now on.

At step 2, we perform the Trace-Fourier transform to the state, yielding

$$\frac{1}{q}\underset{x𝔽_q}{}\underset{y𝔽_q}{}\chi (x+s)\omega _p^{\mathrm{Tr}(xy)}|y+\frac{1}{\sqrt{q}}|\delta .$$

We rewrite this expression as follows: replace $`x`$ with $`z=xy+sy`$, and use the multiplicativity of $`\chi `$ and the linearity of the trace in $`\chi (zy^1)\omega _p^{\mathrm{Tr}(zsy)}=\chi (z)\omega _p^{\mathrm{Tr}(z)}\chi (y)\omega _p^{\mathrm{Tr}(sy)}`$. This proves the validity of Equation 1.  $`\mathrm{}`$

## 5 Conclusion and Open Problems

We have shown the existence of efficient quantum algorithms for several versions of the ‘Shifted Quadratic Character Problem’. The classical complexity of these problems remains open. In the light of Shor’s result, we would also like to know whether the problems become classically tractable if we assume that factoring is easy.

## 6 Acknowledgements

WvD was supported by the Institute for Logic, Language and Computation in Amsterdam, the EU fifth framework project QAIP IST-1999-11234, and the TALENT grant S 62-552 of the Netherlands Organization for Scientific Research (NWO).

## Appendix A From Legendre Symbols to Gauß Sums

### A.1 Legendre Symbol, Jacobi Symbol, and Quadratic Character

In this appendix, $`p`$ is a prime, $`q`$ is the prime power $`p^r`$ with degree $`r`$, and $`n`$ is a (typically non-prime) positive integer. We denote the field of size $`p`$ by $`_p`$, instead of the perhaps more accurate $`/(p)`$. Similarly, the ring induced by $`modn`$ addition and multiplication is $`_n`$. The finite field of size $`q`$ is described by $`𝔽_q`$, and hence $`𝔽_p=_p`$, but $`𝔽_{p^2}_{p^2}`$. The respective multiplicative subgroups are indicated by the $``$ superscript: $`_p^{}`$, $`_n^{}`$ and $`𝔽_q^{}`$.

The *Legendre symbol* indicates if a non-zero element is a square modulo $`p`$ or not:

$`\left({\displaystyle \frac{x}{p}}\right)`$ $`=`$ $`\{\begin{array}{cc}\hfill 0& \text{if }x=0modp\hfill \\ \hfill +1& \text{if there exists a }y0\text{ such that }y^2=xmodp\hfill \\ \hfill 1& \text{if for all }y\text{}y^2xmodp\text{.}\hfill \end{array}`$
Let $`n=p_1p_2\mathrm{}p_k`$ be the prime factor decomposition of $`n`$. The *Jacobi symbol* generalizes the Legendre symbol for all rings $`_n`$ in the following way:

$`\left({\displaystyle \frac{x}{n}}\right)`$ $`=`$ $`\left({\displaystyle \frac{x}{p_1}}\right)\left({\displaystyle \frac{x}{p_2}}\right)\mathrm{}\left({\displaystyle \frac{x}{p_k}}\right).`$
Clearly, $`\left(\frac{x}{n}\right)=0`$ for all $`x`$ not co-prime to $`n`$. Note that $`\left(\frac{x}{n}\right)=+1`$ does not always imply that there is a $`y`$ with $`y^2=xmodn`$. Take, for example, $`\left(\frac{2}{9}\right)=1`$.

For finite fields $`𝔽_q`$, the Legendre symbol becomes the *quadratic character* $`\chi `$, which is defined

$`\chi (x)`$ $`=`$ $`\{\begin{array}{cc}\hfill 0& \text{if }x=0\hfill \\ \hfill +1& \text{if there exists a }y0\text{ such that }y^2=x\hfill \\ \hfill 1& \text{if for all }y\text{}y^2x\text{.}\hfill \end{array}`$
for all $`x𝔽_q`$.

### A.2 Basic Properties

The Legendre symbol, Jacobi symbol and quadratic character are all three *multiplicative characters* because they obey $`(xy/p)=(x/p)(y/p)`$, $`(xy/n)=(x/n)(y/n)`$, and $`\chi (xy)=\chi (x)\chi (y)`$, respectively. This implies a series of results.

Let $`g`$ be a generator of $`_p^{}`$. Because the multiplicative subgroup has $`p1`$ elements, we know that $`g^i=g^jmodp`$ if and only if $`i=jmodp1`$. Hence, the quadratic equation $`(g^j)^2=g^{2j}=g^imodp`$ is correct if and only if $`2j=imodp1`$.

For an odd prime $`p`$, there can only exists a $`j`$ with $`(g^j)^2=g^imodp`$ when $`i`$ is even, as $`p1`$ is even. Obviously, if $`i`$ is even, then $`g^j`$ with $`j=\frac{i}{2}`$ gives also a solution. In short: $`(g^i/p)=(1)^i`$. This proves that $`\frac{p1}{2}`$ of the elements $`x`$ of $`_p^{}`$ are a quadratic residue with $`(x/p)=+1`$, while the other $`\frac{p1}{2}`$ are non-squares.

If $`p`$ is even, then for all $`i`$ either $`i`$ or $`(i+p1)`$ will be even. Hence, either $`j=\frac{i}{2}`$ or $`j=\frac{i+p1}{2}`$ gives a proper solution to the equality $`(g^j)^2=g^imodp`$. This proves that all elements $`x_p^{}`$ are quadratic residues with $`(x/p)=+1`$. This rather redundant proof for the only existing case $`p=2`$ is justified by the following lemma.

###### Lemma 3

For any finite field $`𝔽_{p^r}`$, we have for the summation of its quadratic character values

$`{\displaystyle \underset{x𝔽_{p^r}}{}}\chi (x)`$ $`=`$ $`\{\begin{array}{cc}\hfill 0& \text{if }p\text{ is odd}\hfill \\ \hfill p^r1& \text{if }p\text{ is even.}\hfill \end{array}`$
Proof: Every multiplicative group $`𝔽_{p^r}^{}`$ has a generator $`g`$ with period $`p^r1`$. Use this in combination with the proof method of the preceding paragraphs.  $`\mathrm{}`$

We will reach a similar result for the summation of the Jacobi symbol values over $`_n`$, when $`n`$ is odd and squarefree. Let again $`n=p_1\mathrm{}p_k`$ be the prime decomposition. The Chinese remainder theorem tells us that the mapping $`x_n(xmodp_1,\mathrm{},xmodp_k)_{p_1}\times \mathrm{}\times _{p_k}`$ is a bijection. (All $`p_i`$ terms are different, because we assumed $`n`$ to be square free.) This enables us to prove the following lemma.

###### Lemma 4

Let $`n`$ be an odd, square free integer. The summation of all the Jacobi values of $`_n`$ obeys

$`{\displaystyle \underset{x_n}{}}\left({\displaystyle \frac{x}{n}}\right)`$ $`=`$ $`0.`$
Proof: Let $`n=p_1\mathrm{}p_k`$ be the decomposition of $`n`$ into its prime factors. The definition of the Jacobi symbol in combination with Chinese remainder theorem yields the equality

$`{\displaystyle \underset{x_n}{}}\left({\displaystyle \frac{x}{n}}\right)`$ $`=`$ $`{\displaystyle \underset{x_n}{}}\left({\displaystyle \frac{x}{p_1}}\right)\mathrm{}\left({\displaystyle \frac{x}{p_k}}\right)`$
$`=`$ $`{\displaystyle \underset{x_1_{p_1}}{}}\mathrm{}{\displaystyle \underset{x_k_{p_k}}{}}\left({\displaystyle \frac{x_1}{p_1}}\right)\mathrm{}\left({\displaystyle \frac{x_k}{p_k}}\right)`$
$`=`$ $`\left({\displaystyle \underset{x_1_{p_1}}{}}\left({\displaystyle \frac{x_1}{p_1}}\right)\right)\mathrm{}\left({\displaystyle \underset{x_k_{p_k}}{}}\left({\displaystyle \frac{x_k}{p_k}}\right)\right).`$
By the previous lemma we know that each $`_{x_p}(x/p)`$ is zero, hence the above product is zero as well.  $`\mathrm{}`$

### A.3 Gauß Sums

Let $`\omega _p`$ denote the complex root $`\mathrm{e}^{2\pi i/p}`$. The *trace* of an element $`x𝔽_{p^r}`$ is defined by $`\mathrm{Tr}(x)=_{j=0}^{r1}x^{p^j}`$. It can be shown that for every $`x𝔽_{p^r}`$, its trace is an element of the base-field: $`\mathrm{Tr}(x)𝔽_p`$. When we write $`\omega _p^{\mathrm{Tr}(x)}`$ we interpret the value $`\mathrm{Tr}(x)`$ as an element of the set $`\{0,1,\mathrm{},p1\}`$.

###### Definition 5

For the field $`_p`$, the ring $`_n`$ and the finite field $`𝔽_{p^r}`$ we define the *quadratic Gauß sum* $`G`$ by

$`G(_p)`$ $`=`$ $`{\displaystyle \underset{x_p}{}}\left({\displaystyle \frac{x}{p}}\right)\omega _p^x,`$
$`G(_n)`$ $`=`$ $`{\displaystyle \underset{x_n}{}}\left({\displaystyle \frac{x}{n}}\right)\omega _n^x,`$
$`G(𝔽_{p^r})`$ $`=`$ $`{\displaystyle \underset{x𝔽_{p^r}}{}}\chi (x)\omega _p^{\mathrm{Tr}(x)}.`$
It is not immediately clear that this definition does not give contradicting values for the identical cases $`G(_p)`$ and $`G(𝔽_p)`$. However, the next result shows that this conflict does not occur. We will not give the proofs of the following lemma as that goes far beyond the scope of this article. Instead, the curious reader is referred to the book by Berndt *et al.*

###### Lemma 5

Let $`p`$ be an odd prime and $`n`$ an odd square free integer. The following equalities hold for the different quadratic Gauß sums:

$`G(_p)`$ $`=`$ $`\{\begin{array}{cc}\hfill \sqrt{p}& \text{if }p=1mod4\hfill \\ \hfill \mathrm{i}\sqrt{p}& \text{if }p=3mod4\hfill \end{array}`$
$`G(_n)`$ $`=`$ $`\{\begin{array}{cc}\hfill \sqrt{n}& \text{if }n=1mod4\hfill \\ \hfill \mathrm{i}\sqrt{n}& \text{if }n=3mod4\hfill \end{array}`$
$`G(𝔽_{p^r})`$ $`=`$ $`\{\begin{array}{cc}\hfill \sqrt{p^r}& \text{if }p=1mod4\text{ and }r\text{ is even}\hfill \\ \hfill \sqrt{p^r}& \text{if }p=1mod4\text{ and }r\text{ is odd}\hfill \\ \hfill \sqrt{p^r}& \text{if }p=3mod4\text{ and }r=0mod4\hfill \\ \hfill \mathrm{i}\sqrt{p^r}& \text{if }p=3mod4\text{ and }r=1mod4\hfill \\ \hfill \sqrt{p^r}& \text{if }p=3mod4\text{ and }r=2mod4\hfill \\ \hfill \mathrm{i}\sqrt{p^r}& \text{if }p=3mod4\text{ and }r=3mod4\hfill \end{array}`$
Note that indeed $`G(_p)=G(𝔽_p)`$.


format: text

text:
# Anomalous dynamic response in the two-dimensional lattice Coulomb gas model: Effects of pinning

## I Introduction

Two-dimensional (2D) vortex physics is strongly reflected in the properties of systems related to 2D superfluids like Josephson junction arrays,  superconducting films, and 4He films,  as well as high-$`T_c`$ superconductors.  The vortices are, e.g., responsible for the well-known Kosterlitz-Thouless (KT) transition  and there is a fairly good understanding of the thermodynamic properties related to 2D vortex physics. However, the dynamical aspects, which can be probed by the complex impedance and the flux noise measurements in superconductors,  and by the torsional oscillator period shift in 4He-films,  are much less well understood. The first attempt to describe the dynamic vortex response phenomenologically was given by Ambegaokar-Halperin-Nelson-Siggia (AHNS) in Ref. . However, it was later discovered that the Minnhagen phenomenology (MP) in Ref.  based on essentially the same ingredients as AHNS, described experiments and simulations better.  A particularly interesting aspect in the MP is that it reflects an anomaly in the 2D vortex response,  which, for example, in a superconductor takes the form of a logarithmic divergence of the complex conductivity: $`\sigma (\omega )\mathrm{ln}\omega `$ for small frequency $`\omega `$. There still remain open questions on what ingredients can cause this anomaly and give rise to the anomalous response form.

There has been a number of attempts to obtain the MP form with other phenomenological approaches as well as somewhat formally more rigorous ones.  One possibility is that it is an intrinsic property of the 2D vortex system which is linked to the long range logarithmic interaction, as presumed by the original motivation for the MP response form.  Another possibility is that it is caused by the coupling between the perpendicular currents described by the vortices and the longitudinal currents (often referred to as the spin-wave part).  In the present paper we suggest that there is yet another possibility; the MP type response can also arise from pinning influencing the vortex system.

The approach to this problem, which we subscribe to here, is to systematically investigate various models by aid of simulations. Vortices can be described as 2D Coulomb gas particles, in the sense that a vortex with vorticity $`\pm 1`$ corresponds to a Coulomb gas particle with charge $`\pm 1`$ (See, e.g., Ref.  for details on the mapping between the two models). Since the dynamics of the vortices can to a good approximation be described by the Langevin dynamics,  we can view the 2D Coulomb gas model with Langevin dynamics as the dynamic model for the “pure” 2D vortex response which includes neither any coupling to a spin-wave part nor any pinning. For a superconducting film in the absence of an external perpendicular magnetic field (which corresponds to the absence of a net rotation in case of superfluid 4He film), the numbers of vortices and antivortices (with vorticities 1 and $`1`$, respectively) are always equal, and the system is described by the charge neutral two components 2D Coulomb gas model,  on which the AHNS, as well as the MP, are based. Although it was clearly shown from simulation of this neutral 2D Coulomb gas model that the low-temperature phase is well described by the MP response form with the logarithmic divergence of the conductivity,  there still remains the possibility that the coupling to the spin-wave part or pinning could also influence and perhaps lead to the anomalous response in certain cases.

In Ref.  it has been found in experiments that the 2D triangular Josephson array in a perpendicular magnetic field is also well described by the MP response form, which has again been confirmed in simulations of the related frustrated 2D $`XY`$ model with relaxation dynamics.  Since in these cases pinning could with large probability be excluded as the cause of the effect, the observed anomalous behavior can in these cases be attributed to either the logarithmic vortex interaction, or to the interplay between the vortex and the spin-wave interactions, or to a combination of both.  From the analysis of the experimental results in Ref.  for thin MoGe superconducting film in a perpendicular magnetic field, it has also been pointed out that the data show MP behavior.  Since in Ref.  it was argued that for this sample the vortex pinning due to disorder was important, this raises the question of how pinning influences the dynamic behavior. Could the MP response form also arise from an interplay between the vortex system and pinning? In the present work we conclude, from simulations of the lattice Coulomb gas model, that the vortex system, in the absence of couplings to the spin-wave part but in the presence of pinning, indeed in certain parameter regions gives rise to MP features reflecting an anomalous diffusion.

The paper is organized as follows: In Sec. II we describe the Coulomb gas model and the correlation functions we study in simulations. Section III gives a brief description of the features of the MP response form and make comparisons with the standard Drude response form. The results from the simulations are given in Sec. IV, and in Sec. V we try to give some perspective from comparisons with other results.

## II The Lattice Coulomb Gas Model

In this work, we use the 2D Coulomb gas model on an $`L\times L`$ triangular lattice, whose Hamiltonian in the absence of disorder is written as

$$H=\frac{1}{2}\underset{ij}{}(n_if)V_{ij}(n_jf),$$
(1)
where $`n_i`$ is the integer charge on the $`i`$th site and the frustration $`f`$ controls the total number of charges $`N_c_in_i=fN`$ ($`NL^2`$). The interaction $`V_{ij}`$ between charges at positions $`𝐫_i`$ and $`𝐫_j`$ for a triangular lattice is given by

$$V_{ij}=\frac{1}{N}\underset{𝐤0}{}\frac{3\pi e^{i𝐤(𝐫_i𝐫_j)}}{62\mathrm{cos}𝐤𝐚_12\mathrm{cos}𝐤𝐚_22\mathrm{cos}𝐤𝐚_3},$$
(2)
where $`𝐚_1𝐚`$, $`𝐚_2𝐛`$, and $`𝐚_3𝐚𝐛`$ with two primitive translational vectors $`𝐚`$ and $`𝐛`$ for 2D triangular lattice. (We choose $`𝐚=\widehat{𝐱}`$ and $`𝐛=\widehat{𝐱}/2+\sqrt{3}\widehat{𝐲}/2`$ with lattice spacing set to unity.)

We also study the effects of quenched disorder and consider the Hamiltonian

$$H=\frac{1}{2}\underset{ij}{}(n_if)V_{ij}(n_jf)\underset{i}{}U_in_i,$$
(3)
where the pinning potential $`U_i`$ at $`i`$ has value $`U^p(>0)`$ if the disorder is located at $`i`$ and $`U_i=0`$ otherwise. The randomly distributed disorder realization is parameterized by the pinning strength $`U^p`$ and the ratio $`r_p`$ between the number of pinning sites $`N_p`$ and the total number of charges $`N_c`$: $`r_pN_p/N_c`$. This corresponds to point disorder since we can express it as $`U(𝐫)=_{j=1}^{N_p}U^p\delta (𝐫𝐫_j)`$ in continuum limit, where $`𝐫_j`$ denotes the positions of disordered sites.

We use Monte Carlo (MC) dynamics which can be implemented as follows: Allow two different MC tries where one is the charge hopping to one of its nearest neighbors, i.e., $`(1,0)(0,1)`$, and the other is the generation of a charge-anticharge dipole on one bond, i.e., $`(0,0)(1,1)`$. As was already observed in Ref. , for parameters used in this work the acceptance ratio for generation of charge dipole is found to be extremely small even at temperatures much higher than the critical temperatures (referring to the depinning and melting of the solid phase). We are here studying a temperature region where no charge dipoles are in practice created. Consequently, we only include the charge hopping in our MC try. This means that the model we are studying only contain charges of one sign. Our algorithm is thus: At each step, we first pick up one charge at random and try to move it to one of its six nearest neighboring sites which is also randomly chosen. This MC try is accepted or not according to the standard Metropolis algorithm. One can make the MC simulation more efficient by using a nonlocal update (e.g., the randomly chosen charge can be allowed to hop to a distant site). On the other hand, as far as the dynamic behavior is concerned, the local update rule like the one used in the present work is believed to better imitate the relaxational dynamics of the corresponding continuum model (which corresponds to the Coulomb gas model with Langevin dynamics).

For the characterizations of the thermodynamic properties, we measure (i) the dielectric constant $`1/ϵ(0)`$, which corresponds to the helicity modulus in the vortex systems and detects the superconducting to normal transition, (ii) the orientational order parameter $`\varphi _6`$, which probes the melting of the solid-like structure, and (iii) the specific heat $`C_v`$ (see Ref. ):

$`{\displaystyle \frac{1}{ϵ(0)}}`$ $``$ $`\underset{𝐤0}{lim}\left[1{\displaystyle \frac{2\pi }{TNk^2}}n_𝐤n_𝐤\right],`$ (4)
$`\varphi _6`$ $`=`$ $`{\displaystyle \frac{1}{N_c^2}}{\displaystyle \underset{ij}{}}e^{i6(\theta _i\theta _j)},`$ (5)
$`C_v`$ $`=`$ $`{\displaystyle \frac{H^2H^2}{T^2N}},`$ (6)
where $`\mathrm{}`$ is the thermal average, $`n_𝐤_in_ie^{i𝐤𝐫_i}`$ is the Fourier transformation of the charge distribution, $`\theta _i`$ is the angle between a reference direction, say $`x`$, and the line connecting the $`i`$th particle and its closest neighbor. Since the smallest wavevector is limited by the system size, we choose $`𝐤=𝐀/L`$, $`𝐁/L`$, and $`(𝐀+𝐁)/L`$ with reciprocal lattice vectors $`𝐀4\pi \widehat{𝐲}/\sqrt{3}`$ and $`𝐁2\pi (\widehat{𝐱}\widehat{𝐲}/\sqrt{3})`$, and take the average over these three smallest $`𝐤`$’s (with magnitude $`k=\sqrt{16\pi ^2/3N}`$) to obtain the static dielectric function $`1/ϵ(0)`$ in Eq. (4).

The dynamic behaviors are described by the dynamic dielectric function $`1/ϵ(\omega )`$ (see Refs.  and  for details):

$`{\displaystyle \frac{1}{ϵ(\omega )}}{\displaystyle \frac{1}{ϵ(0)}}=i\omega {\displaystyle _0^{\mathrm{}}}𝑑te^{i\omega t}G(t),`$ (7)
$`G(t)\underset{k0}{lim}{\displaystyle \frac{2\pi }{Nk^2T}}n_𝐤(t)n_𝐤(0),`$ (8)
where $`n_𝐤(t)n_𝐤(0)`$ is the charge correlation function, and $`1/ϵ(0)`$ is the static dielectric constant given above. Just as for $`1/ϵ(0)`$ in Eq. (4), $`G(t)`$ is obtained as the average over the three smallest wavevectors. We measure time $`t`$ in units of the MC step so that one time unit corresponds to $`N_c`$ MC tries to move the randomly chosen particle to one of its nearest neighbors.

## III Dynamic Response

The dynamic response function we focus on is the complex dielectric function $`1/ϵ(\omega )`$ given by Eq. (7). The anomalous vortex diffusion is reflected in the fact $`G(t)1/t`$ for large $`t`$ From this one directly infers that to leading order in small $`\omega `$ (Ref. )

$`\mathrm{Re}\left({\displaystyle \frac{1}{ϵ(\omega )}}{\displaystyle \frac{1}{ϵ(0)}}\right)={\displaystyle \frac{1}{\stackrel{~}{ϵ}}}\omega ,`$ (9)
$`\mathrm{Im}\left({\displaystyle \frac{1}{ϵ(\omega )}}{\displaystyle \frac{1}{ϵ(0)}}\right)=\mathrm{Im}\left({\displaystyle \frac{1}{ϵ(\omega )}}\right)={\displaystyle \frac{2}{\stackrel{~}{ϵ}\pi }}\omega \mathrm{ln}\omega ,`$ (10)
where $`1/\stackrel{~}{ϵ}`$ is a constant and the first equality in Eq. (10) follows because $`1/ϵ(0)`$ is always a real quantity. The complex conductivity for a superconductor $`\sigma (\omega )`$ corresponds to $`1/i\omega ϵ(\omega )`$ which means that $`\mathrm{Re}\sigma (\omega )\mathrm{ln}\omega `$ for small $`\omega `$ This logarithmic divergence is another characteristics of the anomalous vortex diffusion.

The MP form is given by

$`\mathrm{Re}\left({\displaystyle \frac{1}{ϵ(\omega )}}{\displaystyle \frac{1}{ϵ(0)}}\right)={\displaystyle \frac{1}{\stackrel{~}{ϵ}}}{\displaystyle \frac{\omega }{\omega +\omega _0}},`$ (11)
$`\mathrm{Im}\left({\displaystyle \frac{1}{ϵ(\omega )}}\right)={\displaystyle \frac{2}{\stackrel{~}{ϵ}\pi }}{\displaystyle \frac{\omega \omega _0\mathrm{ln}\omega /\omega _0}{\omega ^2\omega _0^2}},`$ (12)
and the corresponding explicit form of $`G(t)`$, which we denote by $`G_{\mathrm{MP}}`$, hence incorporates the features associated with $`G(t)1/t`$ The MP form is associated with a single characteristic frequency $`\omega _0`$. In the 2D neutral Coulomb gas all vortices are bound in vortex-antivortex pairs in the low-temperature phase.  This implies an infinite correlation length which for a superconductor means a vanishing resistance $`R`$ Since the logarithmic divergence of the conductivity means that $`R=0`$, a possible scenario is that the MP response form describes the response of the vortex-antivortex bound pairs and hence should apply to the low-temperature phase. It has been verified, from simulations of the 2D neutral Coulomb gas with Langevin dynamics, that the MP form indeed gives a very good description in this case.  Above the KT transition there are both free vortices and bound vortex-antivortex pairs present and hence there is a finite correlation length. This means that $`G(t)`$ has an exponential decay of the form $`e^{t/\tau }`$, where $`\tau `$ is a relaxation time and $`R1/\tau `$. Thus a finite resistance is associated with an exponential decay of $`G(t)`$. If there were only free vortices then $`G(t)`$ would be dominated by the exponential factor and the response should to good approximation be described by the standard Drude form $`G_\mathrm{D}e^{t/\tau }`$, i.e.,

$`\mathrm{Re}\left({\displaystyle \frac{1}{ϵ(\omega )}}\right)={\displaystyle \frac{1}{\stackrel{~}{ϵ}}}{\displaystyle \frac{\omega ^2}{\omega ^2+\tau ^2}},`$ (13)
$`\mathrm{Im}\left({\displaystyle \frac{1}{ϵ(\omega )}}\right)={\displaystyle \frac{1}{\stackrel{~}{ϵ}}}{\displaystyle \frac{\omega \tau ^1}{\omega ^2+\tau ^2}}.`$ (14)
More generally, when free vortices are present the response form $`G_{\mathrm{MPD}}=G_{\mathrm{MP}}(t)G_\mathrm{D}(t)`$ has from simulations been shown to give a good parameterization of the data.

One difference between the MP response and the Drude response, which is easy to gauge in experiments and simulations, is the peak ratio: The peak ratio (PR) is defined as the ratio between the real and imaginary part of the complex dielectric function at the frequency where $`|\mathrm{Im}[1/ϵ(\omega )]|`$ has its maximum, i.e., at the dissipation peak (see Fig. 6). For the standard Drude response this ratio is 1 whereas it is $`2/\pi 0.64`$ for the MP response. In general when the resistance is finite the peak ratio should be between these two values, $`2/\pi \mathrm{PR}1`$.

Our strategy is to calculate $`G(t)`$ as described above and then to gauge the response by studying the peak ratio, $`G(t)`$ for large $`t`$, and to what extent the response is parameterized by the MP form.

## IV Simulation Results

### A Lattice Coulomb gas without disorder

In this section, we first present the results of the MC simulations of the lattice Coulomb gas model given by the Hamiltonian in Eq. (1) for the case without random pinning sites, i.e., $`U_i=0`$ in Eq. (3). It is known that the system can undergo two phase transitions in this case:  One is the depinning of the solid at $`T_c`$, corresponding to the superconducting to normal transition, and the other is the solid to liquid transition at $`T_m`$ ($`T_cT_m`$). These two transitions can be identified by aid of the quantities $`1/ϵ(0)`$ and $`\varphi _6`$, respectively. Since the continuum system corresponds to an infinitesimally small lattice spacing and the frustration $`f`$ is proportional to the area of the elementary plaquette, the continuum limit of the lattice Coulomb gas is given by $`f0`$, but with the number of particles $`N_c`$ still finite: $`N_c=Nf`$=const. The observation in Ref.  that $`T_c`$ becomes smaller as $`f`$ is decreased indicates that $`T_c0`$ in the continuum system so that the system only has one transition at a nonzero temperature $`T_m`$.

We start by presenting some static results for $`f=1/16`$ on a $`64\times 64`$ triangular grid. In the simulations, we start from high enough temperatures and anneal the system by decreasing the temperature slowly, to avoid being captured by metastable states at low temperatures. However, the local MC scheme used in this work (a particle is only allowed to hop to its nearest neighbor sites) makes it difficult to achieve equilibration near and below the transition. Thus very many MC updates are required in this region (our longest runs consists of $`2\times 10^6`$ MC steps). As $`T`$ is decreased $`1/ϵ(0)`$ abruptly changes to unity near $`T0.01`$ (see Fig. 1). This abrupt change is associated with the normal (high $`T`$) to superconducting (low $`T`$) transition in the vortex system since $`1/ϵ(0)`$ corresponds to the superfluid density.  In the Coulomb gas model it corresponds to a transition where the Coulomb gas systems becomes pinned to the underlying grid. The six-fold orientational order parameter $`\varphi _6`$ has the value unity for a perfect triangular Abrikosov vortex lattice. Consequently the abrupt drop of $`\varphi _6`$ seen in Fig. 1 indicates that the vortex solid melts into a vortex liquid near $`T0.01`$. The specific heat $`C_v`$ also shows a sharp maximum near this temperature $`T0.01`$. Consequently the data in Fig. 1 for the lattice Coulomb gas model with $`f=1/16`$ are consistent with a single phase transition corresponding to a transition where the superconductor becomes normal and the Abrikosov vortex structure melts, i.e., $`T_cT_m0.01`$

We next turn to the dynamic results for $`f=1/16`$. These are shown in Fig. 2: The characteristic frequency $`\omega _0`$ in Fig. 2(a), determined from the peak position of $`|\mathrm{Im}[1/ϵ(\omega )]|`$, shows a dip-like feature near $`T=0.01`$, reflecting a critical slowing down close to the phase transition (compare the static results in Fig. 1). In general, a system composed of particles is expected to be well described by a Drude approximation at sufficiently high temperatures because the interaction between the particles becomes negligible in comparison with the strong thermal fluctuations. The dynamic response function in such a temperature regime should be well described by the Drude response form Eqs. (9) and (10) and should consequently be well characterized by the peak ratio (PR) equal to one. As is shown in Fig. 1(b), the dynamic dielectric function indeed approaches the Drude PR value one at higher temperatures. However, the PR crosses over to a value close to PR=0.64 which characterizes the anomalous behavior (see the previous section) as we approach $`T0.01`$ from above.

The question is then what causes this crossover behavior. Is it associated with the depinning transition at $`T_c`$ or with the melting transition at $`T_m`$? In order to address this question one needs a temperature separation between the two transitions. In Ref. , it was shown that as $`f`$ is decreased, the two transitions present become well separated. With this in mind we, as a next step, repeat the simulations for a much smaller value of $`f`$.

Figure 3 shows the static results $`1/ϵ(0)`$, $`\varphi _6`$, and $`C_v`$ for the system with $`f=1/64`$ on a $`96\times 96`$ lattice. As seen from the figure, the superconducting to normal transition is now at $`T_c0.0035`$ and is well separated from the vortex solid melting transition at $`T_m0.007`$, as was found in Ref. . As also seen in Fig 3, the existence of two transitions are also reflected by two peaks in $`C_v`$: one near $`T_c`$ and another broader one near $`T_m`$. The intermediate phase existing between $`T_c`$ and $`T_m`$ is characterized by a vanishing $`1/ϵ(0)`$ together with a nonzero $`\varphi _6`$ and is interpreted as a floating solid phase:  The vortex solid structure is depinned from the underlying discrete grid and floats around, which leads to dissipation of energy.

Next we analyze the dynamic response function for $`f=1/64`$ is terms of the characteristic frequency $`\omega _0`$ and the peak ratio PR. In Fig. 4, it is shown that $`\omega _0`$ displays a dip-like structure, reflecting a critical slowing down near $`T_c`$ rather than at $`T_m`$ Similarly, the correspondence of the crossover behavior for $`f=1/16`$ in PR from Drude to anomalous response form shown in Fig. 2(b), is in Fig. 4(b) found to be near $`T_c`$ and not near $`T_m`$ From this we conclude that the crossover behavior in the dynamic response is associated with $`T_c`$ and hence with the pinning of the Coulomb gas to the underlying lattice. Thus for the pure one component lattice Coulomb gas with MC dynamics we infer that there is a crossover behavior from a normal Drude like response to an anomalous response. An essential ingredient for the appearance of the anomalous response is associated with the pinning between the vortex system and the underlying lattice.

### B Lattice Coulomb gas with disorder

In the previous section we inferred that the pinning, caused by the underlying lattice, leads to a crossover from a Drude to an anomalous dynamic response. In the present section we study the role of pinning further by introducing extrinsic vortex pinning caused by disorder into the model. The general idea is that the anomaly in the dynamics is caused by a sluggish motion of the vortex system and that pinning hindering the vortex motion can cause such a behavior. To this end we introduce point impurities into the lattice Coulomb gas model as described by the Hamiltonian in Eq. (3). For a superconductor this corresponds to magnetic point impurities. In this section, we perform MC dynamic simulations for 10 different disorder realizations in order to get disorder averaged quantities.

In Fig. 5 the PR for the system with $`f=1/64`$ and $`L=96`$ at $`T=0.01`$ is displayed as a function of the pinning strength $`U^p`$ (the number of pinning sites $`N_p`$ is fixed to 14, which approximately corresponds to 10% of the total number of vortices $`N_c`$, i.e., $`N_p0.1N_c`$). As seen in Fig. 5 the dynamic response for the pure case ($`U^p=0`$) has PR close to one at this higher $`T`$ \[compare Fig. 4(b)\]. This means that the pinning to the underlying lattice at this $`T`$ is too weak to influence the behavior so that the vortices should obey a Drude response. However, if we introduce disorder then Fig. 5 shows a decreasing PR with increasing pinning strength again suggesting a crossover towards an anomalous dynamic response \[compare Fig. 4(b)\]. This is consistent with the idea that when the pinning strength becomes stronger, the motion of the vortices becomes more sluggish, resulting in a decrease of the PR and a crossover to an anomalous response.

This scenario implies that if we introduce enough pinning then the crossover to the anomalous response should become complete. To achieve this we investigate a stronger pinning case where $`N_p=N_c`$ and the pinning strength $`U^p=0.1`$. Figure 6 shows the obtained dielectric function $`1/ϵ(\omega )`$ for this case \[see Eqs. (7) and (8)\] at $`T=0.02`$ which is much higher than $`T_c`$ as well as $`T_m`$ for the pure case ($`T_c0.0035`$ and $`T_m0.007`$, respectively). As illustrated in Fig. 6, the PR is indeed close to the anomalous value PR$`=2/\pi `$ in this case. In the MP phenomenology the anomalous dynamics is linked to a $`1/t`$ decay of the correlation function $`G(t)`$ \[compare Eqs. (8)-(12)\]. The time-correlation function $`G(t)`$ (corresponding to $`1/ϵ(\omega )`$ in Fig. 6) is shown in Fig. 7 and indeed has a $`1/t`$-tail as is manifested by the horizontal plateau of $`tG(t)`$ for larger $`t`$. This suggests that there exists a link between a $`1/t`$-tail in $`G(t)`$ and the PR$`=2/\pi `$. Such a link is incorporated into the MP response form Eqs. (11) and (12). The inset in Fig. 7 shows what happens for the same case at the higher $`T=0.03`$. In this case $`G(t)`$ suggests the presence of an exponential decay. This is very similar to previous simulations where $`G_{\mathrm{MPD}}G_{\mathrm{MP}}(t)G_\mathrm{D}(t)`$ has been shown to give a good parameterization \[see Sec. III below Eq. (14) and Refs. , , and \]. Figure 8(a) shows that a reasonable fit of $`1/ϵ(\omega )`$ to the MP form is obtained in the anomalous case $`T=0.02`$. This suggests that the basic link between the $`G(t)1/t`$ and the PR=$`2/\pi `$ is reasonably well captured by the MP form. Figure 8(b) shows a fit to the exponentially decaying case at $`T=0.03`$ using the parameterization $`G_{\mathrm{MPD}}G_{\mathrm{MP}}(t)G_\mathrm{D}(t)`$. Again a reasonable fit is obtained with PR$`0.9`$. This suggests that, although it is close to the Drude form, there is a small crossover towards the anomalous response (see Fig. 5).

In this section we have thus shown that for the one component lattice Coulomb gas, at a $`T`$ so high that the pinning to the underlying lattice plays no role, it is still possible to obtain a crossover to the anomalous response by introducing pinning through randomly distributed pinning sites.

## V Comparison and Discussions

We have found from simulations that the 2D one component lattice Coulomb gas with Monte Carlo dynamics under certain circumstances displays an anomalous dynamic response. An essential ingredient for the appearance of this anomalous response is found to be pinning; either pinning due to the underlying lattice or external pinning induced by disorder. The anomalous response vanishes gradually as the pinning effects become weaker and from this we conclude that there is no anomaly in the absence of pinning.

We gauge the degree of anomaly in the response by the behavior of the correlation function $`G(t)`$ for large $`t`$, the peak ratio, and to what extent the response can be parameterized by the MP form. We find that the full anomaly is characterized by $`G(t)1/t`$ for large $`t`$, a peak ratio consistent with $`2/\pi `$ and note that these two features are also incorporated into the phenomenological MP form. For the one component lattice Coulomb gas this means that an anomalous response in the absence of externally introduced pinning only appears very close to the depinning of the vortex system from the underlying lattice structure. From this we further infer that the pure continuum one component Coulomb gas has no anomalous response and that in this case external pinning is required to change the response from normal to anomalous.

It is interesting to compare this with the 2D neutral (two components) continuum Coulomb gas with Langevin dynamics which is the generic model for the vortex physics of a 2D superconductor(superfluid) in the absence of an external perpendicular magnetic field (net rotation).  This model undergoes a KT transition and below this transition the dynamic response has from simulations been shown to be anomalous characterized by $`G(t)1/t`$ for large $`t`$, a peak ratio consistent with $`2/\pi `$, and to be well described by the MP form.  Since the same response form is found for the one component Coulomb gas in the presence of external pinning, as for the 2D neutral (two component) Coulomb gas below the KT transition, one might speculate about a common physical feature. We here suggest that the common physical feature is pinning; in the one case externally introduced and in the other intrinsic in the sense that negative vortices act as (moving) pinning centers for positive ones (and vice versa). In both cases the pinning mechanism suppresses the free vortex diffusion. When this suppression is complete the response becomes anomalous as for the one component Coulomb gas with enough external pinning and for the neutral Coulomb gas below the KT-transition where all positive and negative vortices are bound together in pairs.

Thus our conclusion based on simulations is that the 2D one component continuum Coulomb gas cannot have an anomalous response by itself. This is in contrast to the theoretical considerations in Ref. , based on a Mori approximation scheme, which suggest that the one component model in certain parameter regions could have an anomalous response. We have not been able to find any support for this suggestion in our simulations.

The MP form  was originally motivated for the 2D neutral (two components) Coulomb gas as an extension of the AHNS phenomenology  and was assumed to describe the response of bound vortex pairs. Other recent improvements of the AHNS phenomenology also gives a peak ratio close to $`2/\pi `$ However, the MP form is to our knowledge the only form that incorporates both the large $`t`$ behavior $`G(t)1/t`$ and the peak ratio $`2/\pi `$, both of which seems to be characteristics of the anomalous response. In the one component Coulomb gas case with external pinning there is at present really no motivation for the MP form; it is just a simple form which simultaneously incorporates two features which seem to be characteristics of the anomalous response.

Our basic conclusion is that the anomalous response form can indeed arise from an interplay between pinning and a vortex system associated with an external perpendicular magnetic field. In this context one may note that a $`2/\pi `$ peak ratio was found for the experimental data in Ref.  This was a MoGe superconducting film in a perpendicular magnetic field where pinning was expected to be important.  We suggest that this might be an experimental example of our present findings from simulations.

### Acknowledgment

This work was supported by the Swedish Natural Research Council through contract No. FU 04040-332.