text:
# Quantum Computation and Lattice Problems

## 1 Introduction

Quantum computation is a computation model based on quantum physics. Assuming that the laws of nature as we know them are true, this might allow us to build computers that are able to perform tasks that classical computers cannot perform in any reasonable time. One task which quantum algorithms are known to perform much better than classical algorithm is that of factoring large integers. The importance of this problem stems from its ubiquitous use in cryptographic applications. While there are no known polynomial time classical algorithms for this problem, a groundbreaking result of Shor from 1994  showed a polynomial time quantum algorithm for factoring integers. In the same paper, Shor showed an algorithm for finding the discrete log. However, despite enormous effort, we have only a few other problems for which quantum algorithms provide an exponential speedup (e.g., ). Other notable quantum algorithms such as Deutsch and Jozsa’s algorithm  and Simon’s algorithm  operate in the black box model. Grover’s algorithm  provides a square root speedup over classical algorithms.

The current search for new quantum algorithms concentrates on problems which are not known to be $`NP`$-hard. These include the graph isomorphism problem and lattice problems. In this paper we are interested in lattice problems or specifically, the unique shortest vector problem (SVP). A lattice is a set of all integral linear combinations of a set of $`n`$ linearly independent vectors in $`^n`$. This set of $`n`$ vectors is known as a basis of the lattice. In the SVP we are interested in finding the shortest nonzero vector in a lattice. In the $`f(n)`$-unique-SVP we are given the additional promise that the shortest vector is shorter by a factor of at least $`f(n)`$ from all other non parallel vectors. This problem also has important applications in cryptography. Namely, Ajtai and Dwork’s cryptosystem  and the recent cryptosystem by Regev  are based on the hardness of this lattice problem.

A central problem in quantum computation is the hidden subgroup problem (HSP). Here, we are given a black box that computes a function on elements of a group $`G`$. The function is known to be constant and distinct on left cosets of a subgroup $`HG`$ and our goal is to find $`H`$. Interestingly, almost all known quantum algorithms which run super-polynomially faster than classical algorithms solve special cases of the HSP on Abelian groups. Also, it is known that solving the HSP on the symmetric group leads to a solution to graph isomorphism . This motivated research into possible extensions of the HSP to noncommutative groups (see, e.g., ). However, prior to this paper the HSP on groups other than the symmetric group and Abelian groups had no known applications.

In this paper we will be interested in the HSP on the dihedral group. The dihedral group of order $`2N`$, denoted $`D_N`$, is the group of symmetries of an $`N`$-sided regular polygon. It is isomorphic to the abstract group generated by the element $`\rho `$ of order $`n`$ and the element $`\tau `$ of order 2 subject to the relation $`\rho \tau =\tau \rho ^1`$. Although the dihedral group has a much simpler structure than the symmetric group, no efficient solution to the HSP on the dihedral group is known. Ettinger and Høyer  showed that one can obtain sufficient statistical information about the hidden subgroup with only a polynomial number of queries. However, there is no efficient algorithm that solves the HSP using this information. Currently, the best known algorithm is due to Kuperberg  and runs in subexponential time $`2^{O(\sqrt{\mathrm{log}N})}`$.

The following is the main theorem of this paper. The dihedral coset problem is described in the following paragraph.

###### Theorem 1.1

If there exists a solution to the dihedral coset problem with failure parameter $`𝖿`$ then there exists a quantum algorithm that solves the $`\mathrm{\Theta }(n^{\frac{1}{2}+2𝖿})`$-unique-SVP.

The input to the dihedral coset problem (DCP) is a tensor product of a polynomial number of registers. Each register is in the state $`|0,x+|1,(x+d)\mathrm{mod}N`$ for some arbitrary $`x\{0,\mathrm{},N1\}`$ and $`d`$ is the same for all registers. These can also be thought of as cosets of the subgroup $`\{(0,0),(1,d)\}`$ in $`D_N`$. Our goal is to find the value $`d`$. In addition, we say that the DCP has a failure parameter $`𝖿`$ if each of the registers with probability at most $`\frac{1}{(\mathrm{log}N)^𝖿}`$ is in the state $`|b,x`$ for arbitrary $`b,x`$ instead of a coset state. We note that any algorithm that solves the dihedral HSP by sampling cosets also solves the DCP for some failure parameter $`𝖿`$. The reason is that since the algorithm samples only a polynomial number of cosets, we can take $`𝖿`$ to be large enough such that with high probability all the registers are coset states. This is summarized in the following corollary.

###### Corollary 1.2

If there exists a solution to the dihedral HSP that samples cosets (e.g., any solution using the ‘standard method’) then there exists a quantum algorithm that solves $`poly(n)`$-unique-SVP.

The following is the second main theorem of this paper. In the subset sum problem we are given two integers $`t,N`$ and a set of numbers. We are asked to find a subset of the numbers that sums to $`t`$ modulo $`N`$. A legal input is an input for which such a subset exists (a formal definition appears in Section 4) and we are interested in algorithms that solve a non-negligible part of the inputs:

###### Theorem 1.3

If there exists an algorithm $`S`$ that solves $`\frac{1}{poly(\mathrm{log}N)}`$ of the legal subset sum inputs with parameter $`N`$ then there exists a solution to the DCP with failure parameter $`𝖿=1`$.

As shown in , the dihedral HSP can be reduced to the case where the subgroup is of the form $`\{(0,0),(1,d)\}`$. Then, by sampling cosets we obtain states of the form $`|0,x+|1,(x+d)\mathrm{mod}N`$ with no error. Hence,

###### Corollary 1.4

If there exists an algorithm $`S`$ that solves $`\frac{1}{poly(\mathrm{log}N)}`$ of the legal subset sum inputs with parameter $`N`$ then there exists a solution to the dihedral HSP.

Finally, the following is an immediate corollary of the two previous theorems:

###### Corollary 1.5

If there exists an algorithm that solves $`\frac{1}{poly(\mathrm{log}N)}`$ of the legal subset sum inputs with parameter $`N`$ then there exists a quantum algorithm for the $`\mathrm{\Theta }(n^{2.5})`$-unique-SVP.

This result is known as a worst case to average case quantum reduction. Such reductions are already known in the classical case . The exponent $`2.5`$ in our reduction is better than the one in . However, the reduction in , which appeared after the original publication of the current paper, further improves the exponent to $`1.5`$ and hence subsumes our reduction. In addition, unlike the classical reductions, our subset sum problems have a density of one, i.e., the size of the input set is very close to $`\mathrm{log}N`$. Therefore, some cryptographic applications such as the one by Impagliazzo and Naor  cannot be used.

### Intuitive overview

Before proceeding to the main part of the paper, we describe our methods in a somewhat intuitive way. First, let us describe the methods used in solving the unique-SVP. Recall that our solution is based on a solution to the DCP. We begin by showing how such a solution can be used to solve a slightly different problem which we call the two point problem. Instead of a superposition of two numbers with a fixed difference, our input consists of registers in a superposition of two $`n`$-dimensional vectors with a fixed difference. Then, the idea is to create an input to the two point problem in the following way. Start by creating a superposition of many lattice points and collapse the state to just two lattice points whose difference is the shortest vector. Repeating this procedure creates an input to the two point problem whose solution is the shortest vector.

Collapsing the state is performed by partitioning the space into cubes. Assume the partition has the property that in each cube there are exactly two lattice points whose difference is the shortest vector. Then, we compute the cube in which each point is located and measure the result. The state collapses to a superposition of just the two points inside the cube we measured. The important thing is to make sure that exactly two points are located in each cube. First, in order to make sure that the cubes are not aligned with the lattice, we randomly translate them. The length of the cubes is proportional to the length of the shortest vector. Although the exact length of the shortest vector is unknown, we can try several estimates until we find the right value. Since the lattice has a unique shortest vector, all other nonparallel vectors are considerably longer and do not fit inside a cube. Therefore we know that the difference between any two points inside the same cube is a multiple of the shortest vector. Still, this is not good enough since instead of two points inside each box we are likely to have more points aligned along the shortest vector. Hence, we space out the lattice: instead of creating a superposition of all the lattice points we create a superposition of a subset of the points. The set of points created by this technique has the property that along the direction of the shortest vector there are pairs of points whose difference is the shortest vector and the distance between two such pairs is much larger than the shortest vector. As before, this can be done without knowing the shortest vector by trying several possibilities.

The second part of the paper describes a solution to the DCP with failure parameter 1 which uses a solution to the average case subset sum problem. Recall that we are given registers of the form $`|0,x+|1,(x+d)\mathrm{mod}N`$ where $`x\{0,\mathrm{},N1\}`$ is arbitrary and we wish to find $`d\{0,\mathrm{},N1\}`$. Consider one such register. We begin by applying the Fourier transform to the second part of the register (the one holding $`x`$ and $`x+d`$) and then measuring it. If $`a`$ is the value we measured, the state collapses to a combination of the basis states $`|0`$ and $`|1`$ such that their phase difference is $`2\pi \frac{ad}{N}`$. If we were lucky enough to measure $`a=1`$, then the phase difference is $`2\pi \frac{d}{N}`$ and by measuring this phase difference we can obtain an estimation on $`d`$. This, however, happens with exponentially small probability. Since the phase is modulo $`2\pi `$, extracting the value $`d`$ is much harder when $`a`$ is larger. Instead, we perform the same process on $`r`$ registers and let $`a_1,\mathrm{},a_r`$ be the values we measure. The resulting tensor state includes a combination of all $`2^r`$ different $`0,1`$ sequences. The phase of each sequence can be described as follows. By ignoring a fixed phase, we can assume that the phase of the sequence $`00\mathrm{}0`$ is $`0`$. Then, the phase of the sequence $`100\mathrm{}0`$ is $`2\pi \frac{a_1d}{N}`$ and in general, the phase of the sequence $`\alpha _1\alpha _2\mathrm{}\alpha _r`$ is $`2\pi \frac{d}{N}`$ multiplied by the sum of the values $`a_i`$ for which $`\alpha _i=1`$. This indicates that we should try to measure the phase difference of two sequences whose sums differ by $`1`$. However, although we can estimate the phase difference of one qubit, estimating the phase difference of two arbitrary sequences is not possible.

We proceed by choosing $`r`$ to be very close to $`\mathrm{log}N`$. This creates a situation in which for almost every $`t\{0,\mathrm{},N1\}`$ there is a subset whose sum modulo $`N`$ is $`t`$ and in addition, there are not too many subsets that sum to the same $`t`$ modulo $`N`$. Assume for simplicity that every $`t`$ has exactly one subset that sums to $`t`$ modulo $`N`$. We calculate for each sequence the value $`\frac{t}{2}`$ where $`t`$ is its sum. After measuring the result, say $`s`$, we know that the state is a superposition of two sequences: one that sums to $`2s`$ and one that sums to $`2s+1`$. Notice that since $`a_1,\mathrm{},a_r`$ are uniformly chosen between $`\{0,\mathrm{},N1\}`$ we can use them as an input to the subset sum algorithm. The key observation here is that the subset sum algorithm provides the reverse mapping, i.e., from a value $`t`$ to a subset that sums to $`t`$. So, from $`s`$ we can find the sequence $`\alpha _1`$ that sums to $`2s`$ and the sequence $`\alpha _2`$ that sums to $`2s+1`$. Since we know that the state is a superposition of $`|\alpha _1`$ and $`|\alpha _2`$ we can use a unitary transformation that transforms $`|\alpha _1`$ to $`|0`$ and $`|\alpha _2`$ to $`|1`$. Now, since the two states differ in one qubit, we can easily measure the phase difference and obtain an estimate on $`d`$. This almost completes the description of the DCP algorithm. The estimate on $`d`$ is only polynomially accurate but in order to find $`d`$ we need exponential accuracy. Hence, we repeat the same process with pairs whose difference is higher. So, instead of choosing pairs of difference $`1`$ we choose pairs of difference $`2`$ to get an estimate on $`2d`$, then $`4`$ to get an estimate on $`4d`$ and so on111This description is very similar to the method of exponentially accurate phase estimation used in Kitaev’s algorithm . Actually, our case is slightly more difficult because we cannot measure all the multiples $`2^i`$. Nevertheless, we can measure enough multiples of the phase to guarantee exponential accuracy..

### Outline

The next section contains some notations that are used in this paper. The two main sections of this paper are independent. In Section 3 we prove Theorem 1.1 and Section 4 contains the proof of Theorem 1.3.

## 2 Preliminaries

We denote the imaginary unit by $`ı`$ and use the notation $`e(x)=e^{2\pi ıx}`$. Occasionally, we omit the normalization of quantum states. We use the term $`n`$-ball to refer to the $`n`$-dimensional solid body and the term sphere to refer to its surface. We denote the set $`\{1,\mathrm{},n\}`$ by $`[n]`$. All logarithms are of base 2 unless otherwise specified. We use $`\delta _{ij}`$ to denote the Kronecker delta, i.e., 1 if $`i=j`$ and 0 otherwise. A sequence $`\overline{\alpha }\{0,1\}^r`$ is identified with the set $`\{i|\alpha _i=1\}`$. Several constants appear in our proofs. To make it easier to follow, we denote constants with a subscript that is somewhat related to their meaning. Specifically, in Section 3, $`c_{\mathrm{𝖼𝗎𝖻}}`$ is related to the cubes that partition the space, $`c_{\mathrm{𝖻𝖺𝗅}}`$ is related to the radius of the balls, and $`c_{\mathrm{𝗎𝗇𝗊}}`$ appears in the guarantee of the unique shortest vector. Also, in Section 4 we use $`c_𝗋`$ in the definition of the parameter $`r`$, $`c_𝗌`$ in our assumptions on the subset sum subroutine and $`c_𝗆`$ when we prove the existence of matchings.

The following is the formal definition of the DCP:

###### Definition 2.1

The input to the DCP with failure parameter $`𝖿`$ consists of $`poly(\mathrm{log}N)`$ registers. Each register is with probability at least $`1\frac{1}{(\mathrm{log}N)^𝖿}`$ in the state $`\frac{1}{\sqrt{2}}(|0,x+|1,(x+d)\mathrm{mod}N)`$ on $`1+\mathrm{log}N`$ qubits where $`x\{0,\mathrm{},N1\}`$ is arbitrary and $`d`$ is fixed. Otherwise, with probability at most $`\frac{1}{(\mathrm{log}N)^𝖿}`$, its state is $`|b,x`$ where $`b\{0,1\}`$ and $`x\{0,\mathrm{},N1\}`$ are arbitrary. We call such a register a ‘bad’ register. We say that an algorithm solves the DCP if it outputs $`d`$ with probability $`poly(\frac{1}{\mathrm{log}N})`$ and time $`poly(\mathrm{log}N)`$.

## 3 A Quantum Algorithm for unique-SVP

In this section we prove Theorem 1.1. We begin by showing a simple reduction from the two point problem to the DCP in Section 3.1. We then prove a weaker version of Theorem 1.1 with $`\mathrm{\Theta }(n^{1+2𝖿})`$ instead of $`\mathrm{\Theta }(n^{\frac{1}{2}+2𝖿})`$ in Section 3.2. We complete the proof of Theorem 1.1 in Section 3.3. Throughout this section, we use a failure parameter $`𝖿>0`$ in order to make our results more general. The reader might find it easier to take $`𝖿=1`$.

### 3.1 The Two Point Problem

###### Definition 3.1

The input to the two point problem with failure parameter $`𝖿`$ consists of $`poly(n\mathrm{log}M)`$ registers. Each register is with probability at least $`1\frac{1}{(n\mathrm{log}(2M))^𝖿}`$ in the state $`\frac{1}{\sqrt{2}}(|0,\overline{a}+|1,\overline{a}^{})`$ on $`1+n\mathrm{log}M`$ qubits where $`\overline{a},\overline{a}^{}\{0,\mathrm{},M1\}^n`$ are arbitrary such that $`\overline{a}^{}\overline{a}`$ is fixed. Otherwise, with probability at most $`\frac{1}{(n\mathrm{log}(2M))^𝖿}`$, its state is $`|b,\overline{a}`$ where $`b\{0,1\}`$ and $`\overline{a}\{0,\mathrm{},M1\}^n`$ are arbitrary. We say that an algorithm solves the two point problem if it outputs $`\overline{a}^{}\overline{a}`$ with probability $`poly(\frac{1}{n\mathrm{log}M})`$ and time $`poly(n\mathrm{log}M)`$.

###### Lemma 3.2

If there exists an algorithm that solves the DCP with failure parameter $`f`$ then there is an algorithm that solves the two point problem with failure parameter $`f`$.

* Consider the following mapping from $`\{0,\mathrm{},M1\}^n`$ to $`\{0,\mathrm{},(2M)^n1\}`$:

$$f(a_1,\mathrm{},a_n)=a_1+a_22M+\mathrm{}+a_n(2M)^{n1}.$$

Given an input to the two point problem, we create an input to the DCP by using the above mapping on the last $`n\mathrm{log}M`$ qubits of each register. Hence, each register is with probability at least $`1\frac{1}{(n(\mathrm{log}2M))^𝖿}`$ in state

$$\frac{1}{\sqrt{2}}(|0,f(\overline{a})+|1,f(\overline{a}^{})).$$

The difference $`f(\overline{a}^{})f(\overline{a})`$ is $`(a_1^{}a_1)+(a_2^{}a_2)2M+\mathrm{}+(a_n^{}a_n)(2M)^{n1}`$ and is therefore fixed. Otherwise, with probability at most $`\frac{1}{(n(\mathrm{log}2M))^𝖿}`$ the register is in the state $`|b,f(\overline{a})`$ for arbitrary $`b,\overline{a}`$. This is a valid input to the DCP with $`N=(2M)^n`$ since the probability of a bad register is at most $`\frac{1}{(n\mathrm{log}(2M))^𝖿}=\frac{1}{(\mathrm{log}N)^𝖿}`$.

Using the DCP algorithm with the above input we obtain the difference $`b_1+b_22M+\mathrm{}+b_n(2M)^{n1}`$ where $`b_i=a_i^{}a_i`$. In order to extract the $`b_i`$’s we add $`M+M2M+M(2M)^2+\mathrm{}+M(2M)^{n1}`$. Extracting $`b_i`$ from $`(b_1+M)+(b_2+M)2M+\mathrm{}+(b_n+M)(2M)^{n1}`$ is possible since each $`b_i+M`$ is an integer in the range $`1`$ to $`2M1`$. The solution to the two point problem is the vector $`(b_1,\mathrm{},b_n)`$.

### 3.2 A Weaker Algorithm

We recall several facts about an LLL-reduced basis. Such a basis can be found for any lattice by using a polynomial time algorithm . Given a basis $`\overline{b}_1,\mathrm{},\overline{b}_n`$, let $`\overline{b}_1^{},\mathrm{},\overline{b}_n^{}`$ be its Gram-Schmidt orthogonalization. That is, $`\overline{b}_i^{}`$ is the component of $`\overline{b}_i`$ orthogonal to the subspace spanned by $`\overline{b}_1,\mathrm{},\overline{b}_{i1}`$. An LLL reduced basis $`\overline{b}_1,\mathrm{},\overline{b}_n`$ satisfies that $`\overline{b}_i^{}\sqrt{2}\overline{b}_{i+1}^{}`$ and that for $`i>j`$, $`|\overline{b}_i,\overline{b}_j^{}|\frac{1}{2}\overline{b}_j^{}^2`$. In addition, recall that $`\mathrm{min}_i\overline{b}_i^{}`$ is a lower bound on the length of the shortest vector. Since $`\overline{b}_1^{}=\overline{b}_1`$ and $`\overline{b}_1^{}2^{(i1)/2}\overline{b}_i^{}`$ we get that the vector $`\overline{b}_1`$ is at most $`2^{(n1)/2}`$ times longer than the shortest vector. Consider the representation of the LLL basis in the orthonormal basis $`\frac{\overline{b}_1^{}}{\overline{b}_1^{}},\mathrm{},\frac{\overline{b}_n^{}}{\overline{b}_n^{}}`$. The vector $`\overline{b}_i`$ can be written as $`(b_{i1},b_{i2},\mathrm{},b_{ii},0,\mathrm{},0)`$. Notice that $`b_{ii}=\overline{b}_i^{}`$ and that $`|b_{ij}|\frac{1}{2}\overline{b}_j^{}`$ for every $`i>j`$. In the following, $`\overline{u}`$ denotes the shortest vector.

###### Lemma 3.3

Consider the representation of the shortest vector $`\overline{u}`$ in the LLL-reduced lattice basis $`\overline{u}=_{i=1}^nu_i\overline{b}_i`$. Then, $`|u_i|2^{2n}`$ for $`i[n]`$.

* Changing to the orthonormal basis, $`\overline{u}=_{i=1}^nu_i\overline{b}_i=_{i=1}^n(_{j=i}^nu_jb_{j,i})\frac{\overline{b}_i^{}}{\overline{b}_i^{}}`$. In addition, we know that $`\overline{b}_i^{}2^{(i1)/2}\overline{b}_1^{}2^n\overline{u}`$. Hence, $`|_{j=i}^nu_jb_{j,i}|2^n\overline{b}_i^{}`$ for every $`i[n]`$. By taking $`i=n`$ we get that $`|u_n|`$ is at most $`2^n`$. We continue inductively and show that $`|u_k|2^{2nk}`$. Assume that the claim holds for $`u_{k+1},\mathrm{},u_n`$. Then, $`|_{j=k+1}^nu_jb_{j,k}|\frac{1}{2}|_{j=k+1}^nu_j|\overline{b}_k^{}\frac{1}{2}(_{j=k+1}^n2^{2nj})\overline{b}_k^{}\frac{1}{2}2^{2nk}\overline{b}_k^{}`$. By the triangle inequality, $`|u_kb_{k,k}||_{j=k+1}^nu_jb_{j,k}|+|_{j=k}^nu_jb_{j,k}|(\frac{1}{2}2^{2nk}+2^n)\overline{b}_k^{}2^{2nk}\overline{b}_k^{}`$ and the proof is completed.

Let $`p>n^{2+2𝖿}`$ be any fixed prime. The following is the main lemma of this section:

###### Lemma 3.4

For any $`𝖿>0`$ let $`\overline{u}=_{i=1}^nu_i\overline{b}_i`$ be the shortest lattice vector in a $`(c_{\mathrm{𝗎𝗇𝗊}}n^{1+2𝖿})`$-unique lattice where $`c_{\mathrm{𝗎𝗇𝗊}}>0`$ is a constant. If there exists a solution to the two point problem with failure parameter $`𝖿`$ then there exists a quantum algorithm that given this lattice and three integers $`l,m,i_0`$ returns $`(u_1,\mathrm{},u_{i_01},\frac{u_{i_0}m}{p},u_{i_0+1},\mathrm{},u_n)`$ with probability $`1/poly(n)`$ if the following conditions hold: $`\overline{u}l2\overline{u}`$, $`u_{i_0}m(\mathrm{mod}p)`$ and $`1mp1`$.

We first show how this lemma implies Theorem 1.1 with $`\mathrm{\Theta }(n^{1+2𝖿})`$ by describing the SVP algorithm. According to Lemma 3.2 and the assumption of the theorem, there exists a solution to the two point problem with failure parameter $`𝖿`$. Hence, Lemma 3.4 implies that there exists an algorithm that given the right values of $`l,m,i_0`$ outputs $`(u_1,\mathrm{},u_{i_01},\frac{u_{i_0}m}{p},u_{i_0+1},\mathrm{},u_n)`$. The value $`l`$ is an estimate of the length of the shortest vector $`\overline{u}`$. Because the LLL algorithm gives a $`2^{(n1)/2}`$-approximation to the length of the shortest vector, one of $`(n1)/2`$ different values of $`l`$ is as required. In addition, since $`\overline{u}`$ is the shortest vector, $`\overline{u}/p`$ cannot be a lattice vector and therefore there exists an $`i_0`$ such that $`u_{i_0}0(\mathrm{mod}p)`$. Hence, there are only $`O(pn^2)`$ possible values for $`l,m`$ and $`i_0`$. With each of these values the SVP algorithm calls the algorithm of Lemma 3.4 a polynomial number of times. With high probability in one of these calls the algorithm returns the vector $`(u_1,\mathrm{},u_{i_01},\frac{u_{i_0}m}{p},u_{i_0+1},\mathrm{},u_n)`$ from which $`\overline{u}`$ can be extracted. The results of the other calls can be easily discarded because they are either longer lattice vectors or non-lattice vectors.

* (of Lemma 3.4) We start by applying the LLL algorithm to the unique lattice in order to create a reduced basis. Denote the resulting basis by $`\overline{b}_1,\mathrm{},\overline{b}_n`$. Let $`\overline{e}_1,\mathrm{},\overline{e}_n`$ be the standard orthonormal basis of $`^n`$.

Let $`w_1,\mathrm{},w_n`$ be $`n`$ real values in $`[0,1)`$ and let $`M=2^{4n}`$. Assume without loss of generality that $`i_0=1`$. The function $`f`$ is defined as $`f(t,\overline{a})=(a_1p+tm)\overline{b}_1+_{i=2}^na_i\overline{b}_i`$ where $`t\{0,1\}`$ and $`\overline{a}=(a_1,\mathrm{},a_n)𝒜=\{0,\mathrm{},M1\}^n`$. It maps the elements of $`\{0,1\}\times 𝒜`$ to lattice points. In addition, consider a lattice vector $`\overline{v}`$ represented in the orthonormal basis $`\overline{v}=_{i=1}^nv_i\overline{e}_i`$. The function $`g`$ maps $`\overline{v}`$ to the vector $`(v_1/(c_{\mathrm{𝖼𝗎𝖻}}n^{\frac{1}{2}+2𝖿}l)w_1,\mathrm{},v_n/(c_{\mathrm{𝖼𝗎𝖻}}n^{\frac{1}{2}+2𝖿}l)w_n)`$ in $`^n`$ where the constant $`c_{\mathrm{𝖼𝗎𝖻}}>0`$ will be specified later.

In the following, we describe a routine that creates one register in the input to the two point problem that hides the difference $`(u_1,\mathrm{},u_{i_01},\frac{u_{i_0}m}{p},u_{i_0+1},\mathrm{},u_n)`$. We call the routine $`poly(n\mathrm{log}M)=poly(n)`$ times in order to create a complete input to the two point problem. We then call the two point algorithm and output its result. This completes the proof of the lemma since with probability $`1/poly(n\mathrm{log}M)=1/poly(n)`$ our output is correct.

The routine starts by choosing $`w_1,\mathrm{},w_n`$ uniformly from $`[0,1)`$. We create the state

$$\frac{1}{\sqrt{2M^n}}\underset{t\{0,1\},\overline{a}𝒜}{}|t,\overline{a}.$$

Then, we compute the function $`F=gf`$ and measure the result, say $`r_1,\mathrm{},r_n`$. The state collapses to (normalization omitted)

$$\underset{\begin{array}{c}t\{0,1\}\overline{a}𝒜\\ F(t,\overline{a})=(r_1,\mathrm{},r_n)\end{array}}{}|t,\overline{a}|r_1,\mathrm{},r_n.$$

This completes the description of the routine. Its correctness is shown in the next two claims.

###### Claim 3.5

For every $`\overline{r}^n`$, there is at most one element of the form $`(0,\overline{a})`$ and at most one element of the form $`(1,\overline{a}^{})`$ that get mapped to $`\overline{r}`$ by $`F`$. Moreover, if both $`(0,\overline{a})`$ and $`(1,\overline{a}^{})`$ get mapped to $`\overline{r}`$ then $`\overline{a}^{}\overline{a}`$ is the vector $`(\frac{u_1m}{p},u_2,\mathrm{},u_m)`$.

+ Consider two different lattice points in the image of $`f`$, $`\overline{v}=f(t,\overline{a})`$ and $`\overline{v}^{}=f(t^{},\overline{a}^{})`$, that get mapped to $`\overline{r}`$ by $`g`$. Let $`\overline{v}=_{i=1}^nv_i\overline{e}_i`$ and $`\overline{v}^{}=_{i=1}^nv_i^{}\overline{e}_i`$ be their representation in the orthonormal basis. If $`\overline{v}^{}\overline{v}`$ is not a multiple of the shortest vector, then $`\overline{v}^{}\overline{v}>c_{\mathrm{𝗎𝗇𝗊}}n^{1+2𝖿}\overline{u}\frac{1}{2}c_{\mathrm{𝗎𝗇𝗊}}n^{1+2𝖿}l`$. Therefore, there exists a coordinate $`i[n]`$ such that $`|v_i^{}v_i|\frac{1}{2}c_{\mathrm{𝗎𝗇𝗊}}n^{\frac{1}{2}+2𝖿}l`$ and for $`c_{\mathrm{𝗎𝗇𝗊}}>2c_{\mathrm{𝖼𝗎𝖻}}`$ this implies $`g(\overline{v})g(\overline{v}^{})`$ no matter how $`w_1,\mathrm{},w_n`$ are chosen. Hence, $`\overline{v}^{}\overline{v}=k\overline{u}`$ for some integer $`k0`$. By considering the first coordinate of $`\overline{v}^{}\overline{v}`$ in the lattice basis we get that $`(a_1^{}p+t^{}m)(a_1p+tm)km(\mathrm{mod}p)`$. This implies that $`kt^{}t(\mathrm{mod}p)`$. If $`t=t^{}`$ then $`k0(\mathrm{mod}p)`$ which implies that $`|k|p`$. Thus, $`\overline{v}^{}\overline{v}p\overline{u}>c_{\mathrm{𝖼𝗎𝖻}}n^{1+2𝖿}l`$ and again, $`g(\overline{v})g(\overline{v}^{})`$. This proves the first part of the claim. For the second part, let $`t=0`$ and $`t^{}=1`$. Then, $`k1(\mathrm{mod}p)`$. As before, this can only happen when $`k=1`$ and hence the second part of the claim holds.

Hence, it is enough to show that the probability that this register is bad is low enough. The probability of measuring $`|r_1,\mathrm{},r_n`$ equals $`\frac{1}{2M^n}|\{(t,\overline{a})|F(t,\overline{a})=(r_1,\mathrm{},r_n)\}|`$. Notice that this probability is the same as the probability that $`F(t,\overline{a})=(r_1,\mathrm{},r_n)`$ for randomly chosen $`t`$ and $`\overline{a}`$. Hence, we consider a randomly chosen $`t`$ and $`\overline{a}`$. If $`t=0`$, let $`\overline{a}^{}=(a_1+\frac{u_1m}{p},a_2+u_2,\mathrm{},a_n+u_n)`$ and if $`t=1`$ let $`\overline{a}^{}=(a_1\frac{u_1m}{p},a_2u_2,\mathrm{},a_nu_n)`$.

###### Claim 3.6

With probability at least $`1\frac{1}{(n\mathrm{log}(2M))^𝖿}`$, for randomly chosen $`t`$ and $`\overline{a}`$, $`\overline{a}^{}`$ is in $`𝒜`$ and $`F(1t,\overline{a}^{})=F(t,\overline{a})`$.

+ We assume that $`t=0`$, the proof for $`t=1`$ is similar. According to Lemma 3.3, $`|u_i|<2^{2n}`$. Hence, unless there exists an $`i`$ for which $`a_i<2^{2n}`$ or $`a_i>M2^{2n}`$, $`\overline{a}^{}`$ is guaranteed to be in $`𝒜`$. This happens with probability at most $`n2^{2n+1}/M`$ because $`\overline{a}`$ is a random element of $`𝒜`$.

    Notice that $`f(1,\overline{a}^{})f(0,\overline{a})=\overline{u}`$. Since $`w_1,\mathrm{},w_n`$ are randomly chosen, the probability that $`F(1t,\overline{a}^{})`$ and $`F(t,\overline{a})`$ differ on the $`i`$’th coordinate is at most

    $$\frac{|\overline{u},\overline{e}_i|}{c_{\mathrm{𝖼𝗎𝖻}}n^{\frac{1}{2}+2𝖿}l}\frac{|\overline{u},\overline{e}_i|}{c_{\mathrm{𝖼𝗎𝖻}}n^{\frac{1}{2}+2𝖿}\overline{u}}.$$

    By the union bound, the probability that $`F(1t,\overline{a}^{})F(t,\overline{a})`$ is at most

    $$\frac{_i|\overline{u},\overline{e}_i|}{c_{\mathrm{𝖼𝗎𝖻}}n^{\frac{1}{2}+2𝖿}\overline{u}}\frac{1}{c_{\mathrm{𝖼𝗎𝖻}}n^{2𝖿}}$$

    where we used the fact that the $`l_1`$ norm of a vector is at most $`\sqrt{n}`$ times its $`l_2`$ norm.

    The sum of the two error probabilities $`n\frac{2^{2n+1}}{M}+\frac{1}{c_{\mathrm{𝖼𝗎𝖻}}n^{2𝖿}}`$ is at most $`\frac{1}{(n\mathrm{log}(2M))^𝖿}`$ for $`c_{\mathrm{𝖼𝗎𝖻}}`$ large enough.

This concludes the proof of Lemma 3.4.

### 3.3 An Improved Algorithm

In this section we complete the proof of Theorem 1.1. The algorithm we describe has many similarities with the one in the previous section. The main difference is that it is based on $`n`$-dimensional balls instead of cubes. The idea is to construct a ball of the right radius around lattice points and to show that if two lattice points are close then the two balls have a large intersection while for any two far lattice points the balls do not intersect. For technical reasons, we will assume in this section that the lattice is a subset of $`^n`$. Any lattice with rational points can be scaled so that it is a subset of $`^n`$. We begin with some technical claims:

###### Claim 3.7

For any $`R>0`$, let $`B_n`$ be the ball of radius $`R`$ centered around the origin in $`^n`$ and let $`B_n^{}=B_n+\overline{d}`$ for some vector $`\overline{d}`$ be a shifted ball. Then, the relative $`n`$-dimensional volume of their intersection is at least $`1O(\sqrt{n}\overline{d}/R)`$, i.e.,

$$\frac{\mathrm{vol}(B_nB_n^{})}{\mathrm{vol}(B_n)}1O(\sqrt{n}\overline{d}/R).$$

* Consider a point $`\overline{x}^n`$ such that $`\overline{x},\overline{d}/\overline{d}\overline{d}/2`$, i.e., a point which is closer to the center of $`B_n^{}`$ than to the center of $`B_n`$. Notice that $`\overline{x}B_n`$ implies $`\overline{x}B_n^{}`$. In other words, the cap $`C_n`$ of $`B_n`$ given by all such points $`\overline{x}`$ is contained in $`B_nB_n^{}`$. By using a symmetric argument for points $`\overline{x}^n`$ such that $`\overline{x},\overline{d}/\overline{d}<\overline{d}/2`$ we get,

$$\mathrm{vol}(B_nB_n^{})=2\mathrm{vol}(C_n).$$

We can lower bound the volume of $`C_n`$ by half the volume of $`B_n`$ minus the volume of an $`n`$-dimensional cylinder of radius $`R`$ and height $`\overline{d}/2`$:

$$\mathrm{vol}(C_n)\frac{1}{2}\mathrm{vol}(B_n)\frac{\overline{d}}{2}\mathrm{vol}(B_{n1})$$

where $`B_{n1}`$ is the $`n1`$-ball of radius $`R`$. We complete the proof by using the estimate $`\mathrm{vol}(B_{n1})/\mathrm{vol}(B_n)=O(\sqrt{n}/R)`$,

$$\mathrm{vol}(C_n)/\mathrm{vol}(B_n)\frac{1}{2}O(\sqrt{n}\overline{d}/R).$$

In the algorithm we will actually represent the balls using points of a fine grid. Therefore, we would like to say that the above claim still holds if we consider the number of grid points inside $`B_n`$, $`B_n^{}`$ and $`B_nB_n^{}`$ instead of their volumes. The following claim is more than enough for our needs:

###### Claim 3.8 (Special case of Proposition 8.7 in )

Let $`L`$ be an integer and consider the scaled integer grid $`\frac{1}{L}^n`$. Then, for any convex body $`Q`$ that contains a ball of radius $`r\frac{1}{L}n^{1.5}`$,

$$\left|\frac{|\frac{1}{L}^nQ|}{L^n\mathrm{vol}(Q)}1\right|<\frac{2n^{1.5}}{rL}.$$

###### Corollary 3.9

Let $`L=2^n`$ and consider the scaled integer grid $`\frac{1}{L}^n`$. For any $`R1`$, let $`B_n`$ be the ball of radius $`R`$ centered around the origin in $`^n`$ and let $`B_n^{}=B_n+\overline{d}`$ for some vector $`\overline{d}`$ such that $`R/poly(n)\overline{d}R`$. Then, the relative number of grid points in their intersection is at least $`1O(\sqrt{n}\overline{d}/R)`$, i.e.,

$$\frac{|\frac{1}{L}^nB_nB_n^{}|}{|\frac{1}{L}^nB_n|}1O(\sqrt{n}\overline{d}/R).$$

* We first note that $`B_n`$, $`B_n^{}`$ and $`B_nB_n^{}`$ all contain the ball of radius $`R/21/2`$ centered around $`\overline{d}/2`$. Using Claim 3.8 we obtain that the number of grid points in these bodies approximates their volume up to a multiplicative error of $`\frac{2n^{1.5}}{L/2}=2^{\mathrm{\Omega }(n)}`$. We complete the proof by using Claim 3.7.

Let $`D(,)`$ denote the trace distance between two quantum states . It is known that the trace distance represents the maximum probability of distinguishing between the two states using quantum measurements. We need the following simple bound on the trace distance:

###### Claim 3.10

For all $`k>0`$ and density matrices $`\sigma _1,\mathrm{},\sigma _k,\sigma _1^{},\mathrm{},\sigma _k^{}`$,

$$D(\sigma _1\mathrm{}\sigma _k,\sigma _1^{}\mathrm{}\sigma _k^{})\underset{i=1}{\overset{k}{}}D(\sigma _i,\sigma _i^{})$$

* Using the triangle inequality,

$`D(\sigma _1\mathrm{}\sigma _k,\sigma _1^{}\mathrm{}\sigma _k^{})`$ $``$ $`D(\sigma _1\mathrm{}\sigma _k,\sigma _1^{}\sigma _2\mathrm{}\sigma _k)+`$
$`D(\sigma _1^{}\sigma _2\mathrm{}\sigma _k,\sigma _1^{}\sigma _2^{}\sigma _3\mathrm{}\sigma _k)+\mathrm{}`$
$`D(\sigma _1^{}\mathrm{}\sigma _{k1}^{}\sigma _k,\sigma _1^{}\mathrm{}\sigma _k^{})`$
$`=`$ $`D(\sigma _1,\sigma _1^{})+D(\sigma _2,\sigma _2^{})+\mathrm{}+D(\sigma _k,\sigma _k^{}).`$

In addition, we will need the following lemma:

###### Lemma 3.11

For any $`1R2^{poly(n)}`$, let

$$|\eta =\frac{1}{\sqrt{|\frac{1}{L}^nB_n|}}\underset{\overline{x}\frac{1}{L}^nB_n}{}|\overline{x}$$

be the uniform superposition on grid points inside a ball of radius $`R`$ around the origin where $`L=2^n`$. Then, for any $`c>0`$, a state $`|\stackrel{~}{\eta }`$ whose trace distance from $`|\eta `$ is at most $`1/n^c`$ can be efficiently computed.

* In order to bound the trace distance, we will use the fact that for any two pure states $`|\psi _1,|\psi _2`$,

$$D(|\psi _1,|\psi _2)=\sqrt{1|\psi _1|\psi _2|^2}|\psi _1|\psi _2_2.$$
(1)
The first equality appears in  and the inequality follows by a simple calculation.

Consider the (continuous) uniform probability distribution $`q`$ over $`B_n`$. Then one can define its discretization $`q^{}`$ to the grid $`\frac{1}{L}^n`$ as

$$q^{}(\overline{x})=_{\overline{x}+[0,1/L]^n}q(\overline{y})𝑑\overline{y}$$

for $`\overline{x}\frac{1}{L}^n`$. In other words, $`q^{}(\overline{x})`$ is proportional to the volume of the intersection of $`B_n`$ with the cube $`\overline{x}+[0,1/L]^n`$. Notice that for points $`\overline{x}`$ such that $`\overline{x}+[0,1/L]^n`$ is completely contained in $`B_n`$, $`q^{}(\overline{x})=1/(L^n\mathrm{vol}(B_n))`$. We claim that the state

$$|\eta ^{}=\underset{\overline{x}\frac{1}{L}^n}{}\sqrt{q^{}(\overline{x})}|\overline{x}$$

is exponentially close to $`|\eta `$. Intuitively, this holds since the two differs only on points which are very close to the boundary of the ball, namely, of distance $`\sqrt{n}/L`$ from the boundary. The number of such points is negligible compared to the number of points in the interior of the ball. More formally, define

$$|\eta ^{\prime \prime }=\sqrt{\frac{L^n\mathrm{vol}(B_n)}{|\frac{1}{L}^nB_n|}}|\eta ^{}.$$

Using Equation 1,

$$D(|\eta ,|\eta ^{})|\eta ^{}|\eta _2|\eta ^{}|\eta ^{\prime \prime }_2+|\eta ^{\prime \prime }|\eta _2.$$

The first term is at most $`2^{\mathrm{\Omega }(n)}`$ according to Claim 3.8. For the second term, notice that the amplitudes of $`|\eta ^{\prime \prime }`$ and $`|\eta `$ are the same except possibly on points $`\overline{x}`$ of distance $`\sqrt{n}/L`$ from the boundary. Using Claim 3.8 again we get that the fraction of such points is closely approximated by one minus the ratio of volumes of the ball of radius $`R\sqrt{n}/L`$ and the ball of radius $`R`$. This ratio of volumes is $`(1\sqrt{n}/(RL))^n(1\sqrt{n}/L)^n1n^{1.5}/L=12^{\mathrm{\Omega }(n)}`$.

In the following we show how to approximate the state $`|\eta ^{}`$. This idea is essentially due to Grover and Rudolph . Let $`m`$ be large enough so that $`B_n`$ is contained in the cube $`[2^m,2^m]^n`$. Using our assumption on $`R`$, $`m<n^{c_1}`$ for some $`c_11`$. We represent $`\overline{x}`$ using $`K=n(m+1+\mathrm{log}L)<2n^{1+c_1}`$ qubits, i.e., a block of $`m+1+\mathrm{log}L`$ qubits for each dimension. Hence, we can write $`|\eta ^{}`$ as

$$|\eta ^{}=\underset{x_1,\mathrm{},x_K\{0,1\}}{}\sqrt{q^{}(x_1,\mathrm{},x_K)}|x_1,\mathrm{},x_K.$$

We now show an equivalent way of writing $`|\eta ^{}`$. Let us extend the definition of $`q^{}`$ in the following way: for any $`kK`$ and any $`x_1,\mathrm{},x_k\{0,1\}`$ define $`q^{}(x_1,\mathrm{},x_k)`$ as the sum of $`q^{}(x_1,\mathrm{},x_k,x_{k+1},\mathrm{},x_K)`$ over all sequences $`x_{k+1},\mathrm{},x_K\{0,1\}`$. Notice that $`q^{}(x_1,\mathrm{},x_k)`$ corresponds to the volume of the intersection of $`B_n`$ with a certain cuboid (also known as a rectangular parallelepiped). For example, $`q^{}(0)=q^{}(1)=\frac{1}{2}`$ since they represent the intersection of $`B_n`$ with two halves of the cube $`[2^m,2^m]^n`$. Using the definition $`s(x_1)=q^{}(x_1)`$ and for $`k>1`$, $`s(x_1,\mathrm{},x_k)=q^{}(x_1,\mathrm{},x_k)/q^{}(x_1,\mathrm{},x_{k1})`$ we see that

$$|\eta ^{}=\underset{x_1\{0,1\}}{}\sqrt{s(x_1)}\underset{x_2\{0,1\}}{}\sqrt{s(x_1,x_2)}\mathrm{}\underset{x_K\{0,1\}}{}\sqrt{s(x_1,\mathrm{},x_K)}|x_1,\mathrm{},x_K.$$

The algorithm starts with all $`K`$ qubits in the state $`|0`$ and sets one qubit at a time. The first qubit is rotated to the state $`\frac{1}{\sqrt{2}}(|0+|1)`$. Assume we are now in the $`k`$’th step after setting the state of qubits $`1,\mathrm{},k1`$. We use the fact that there exists a classical algorithm for approximating the volume of a convex body up to any $`1/poly(n)`$ error (see  and references therein). The body should be provided by a “well-guaranteed weak membership oracle”, i.e., a sphere containing the body, a sphere contained in the body, both of non-zero radius and an oracle that given a point decides if it is inside the body or not. It is easy to construct such two spheres and an oracle for a body given by the intersection of a ball with a cuboid. Hence, we can compute two values $`\stackrel{~}{s}(x_1,\mathrm{},x_{k1},0)`$ and $`\stackrel{~}{s}(x_1,\mathrm{},x_{k1},1)`$ such that

$$\stackrel{~}{s}(x_1,\mathrm{},x_{k1},0)+\stackrel{~}{s}(x_1,\mathrm{},x_{k1},1)=1$$

and

$$\left|\frac{\stackrel{~}{s}(x_1,\mathrm{},x_{k1},i)}{s(x_1,\mathrm{},x_{k1},i)}1\right|<n^{c_2}$$

for $`i=0,1`$ and some constant $`c_2`$ which will be chosen later. Then, we rotate the $`i`$’th qubit to the state $`\sqrt{\stackrel{~}{s}(x_1,\mathrm{},x_{k1},0)}|0+\sqrt{\stackrel{~}{s}(x_1,\mathrm{},x_{k1},1)}|1`$. This completes the description of the procedure.

Notice that the amplitude of each basis state $`|x_1,\mathrm{},x_K`$ in the resulting state $`|\stackrel{~}{\eta }`$ is given by

$$\underset{k=1}{\overset{K}{}}\sqrt{\stackrel{~}{s}(x_1,\mathrm{},x_k)}(1n^{c_2})^K\underset{k=1}{\overset{K}{}}\sqrt{s(x_1,\mathrm{},x_k)}.$$

Hence the inner product $`\stackrel{~}{\eta }|\eta ^{}`$ is at least

$`(1n^{c_2})^K{\displaystyle \underset{x_1,\mathrm{},x_K\{0,1\}}{}}{\displaystyle \underset{k=1}{\overset{K}{}}}s(x_1,\mathrm{},x_k)`$ $`=`$ $`(1n^{c_2})^K{\displaystyle \underset{x_1,\mathrm{},x_K\{0,1\}}{}}q^{}(x_1,\mathrm{},x_K)`$
$`=`$ $`(1n^{c_2})^K1Kn^{c_2}12n^{1+c_1c_2}.`$
Using Equation 1,

$$D(|\eta ^{},|\stackrel{~}{\eta })=\sqrt{1|\stackrel{~}{\eta }|\eta ^{}|^2}<n^c$$

for a large enough $`c_2`$.

Let $`p>n^{2+2𝖿}`$ be any fixed prime. The following is the main lemma of this section. It essentially replaces Lemma 3.4 and hence implies Theorem 1.1.

###### Lemma 3.12

For any $`𝖿>0`$ let $`\overline{u}=_{i=1}^nu_i\overline{b}_i`$ be the shortest lattice vector in a $`(c_{\mathrm{𝗎𝗇𝗊}}n^{\frac{1}{2}+2𝖿})`$-unique lattice where $`c_{\mathrm{𝗎𝗇𝗊}}>0`$ is a constant. If there exists a solution to the two point problem with failure parameter $`𝖿`$ then there exists a quantum algorithm that given this lattice and three integers $`l,m,i_0`$ returns $`(u_1,\mathrm{},u_{i_01},\frac{u_{i_0}m}{p},u_{i_0+1},\mathrm{},u_n)`$ with probability $`1/poly(n)`$ if the following conditions hold: $`\overline{u}l2\overline{u}`$, $`u_{i_0}m(\mathrm{mod}p)`$ and $`1mp1`$.

* As before, let $`\overline{b}_1,\mathrm{},\overline{b}_n`$ be an LLL reduced basis, let $`M=2^{4n}`$ and assume that $`i_0=1`$. We also define $`f(t,\overline{a})`$ as before. Assume that the number of registers needed by the two point algorithm is at most $`n^{c_1}`$ for some constant $`c_1>0`$.

The algorithm starts by calling the routine of Claim 3.11 $`n^{c_1}`$ times with accuracy parameter $`n^{c_2}`$ and $`R=c_{\mathrm{𝖻𝖺𝗅}}n^{\frac{1}{2}+2𝖿}l`$ for some constants $`c_2,c_{\mathrm{𝖻𝖺𝗅}}>0`$. The state we obtain is

$$|\stackrel{~}{\eta }_1\mathrm{}|\stackrel{~}{\eta }_{n^{c_1}}$$
(2)
where each $`|\stackrel{~}{\eta }_i`$ has a trace distance of at most $`n^{c_2}`$ from $`|\eta `$. According to Claim 3.10, the above tensor product has a trace distance of at most $`n^{c_1c_2}`$ from $`|\eta ^{n^{c_1}}`$. In the following we show that the algorithm succeeds with probability at least $`n^{c_3}`$ for some $`c_3>0`$ given the state $`|\eta ^{n^{c_1}}`$. This would complete the proof since given the state in Equation 2, the algorithm succeeds with probability at least $`n^{c_3}n^{c_1c_2}>\frac{1}{2}n^{c_3}`$ for large enough $`c_2`$.

We describe a routine that given the state $`|\eta `$ creates one register in the input to the two point problem. In order to produce a complete input to the two point problem, the algorithm calls this routine $`n^{c_1}`$ times, each time with a new $`|\eta `$ register. It then calls the two point algorithm and outputs the result. As required, the success probability is $`1/poly(n\mathrm{log}M)=n^{c_3}`$ for some $`c_3>0`$.

Given $`|\eta `$, the routine creates the state

$$\frac{1}{\sqrt{2M^n}}\underset{t\{0,1\},\overline{a}𝒜}{}|t,\overline{a}|\eta ,$$

or equivalently,

$$\underset{t\{0,1\},\overline{a}𝒜,\overline{x}\frac{1}{L}^nB_n}{}|t,\overline{a},\overline{x}$$

where $`B_n`$ is the ball of radius $`R`$ around the origin and $`L=2^n`$. We add the value $`f(t,\overline{a})`$ to the last register,

$$\underset{t\{0,1\},\overline{a}𝒜,\overline{x}\frac{1}{L}^nB_n}{}|t,\overline{a},f(t,\overline{a})+\overline{x}.$$

Finally, we measure the last register and if $`\overline{x}^{}`$ denotes the result, the state collapses to

$$\underset{t\{0,1\},\overline{a}𝒜|\overline{x}^{}f(t,\overline{a})+\frac{1}{L}^nB_n}{}|t,\overline{a},\overline{x}^{}.$$

###### Claim 3.13

For every $`\overline{x}^{}`$, there is at most one element of the form $`(0,\overline{a})`$ and at most one element of the form $`(1,\overline{a}^{})`$ such that $`\overline{x}^{}f(t,\overline{a})+\frac{1}{L}^nB_n`$. Moreover, if there are two such elements $`(0,\overline{a})`$ and $`(1,\overline{a}^{})`$ then $`\overline{a}^{}\overline{a}`$ is the vector $`(\frac{u_1m}{p},u_2,\mathrm{},u_m)`$.

+ Consider two different lattice points in the image of $`f`$, $`\overline{v}=f(t,\overline{a})`$ and $`\overline{v}^{}=f(t^{},\overline{a}^{})`$, such that $`\overline{x}^{}`$ is both in $`\overline{v}+\frac{1}{L}^nB_n`$ and $`\overline{v}^{}+\frac{1}{L}^nB_n`$. This implies that $`\overline{v}\overline{v}^{}c_{\mathrm{𝖻𝖺𝗅}}n^{\frac{1}{2}+2𝖿}l2c_{\mathrm{𝖻𝖺𝗅}}n^{\frac{1}{2}+2𝖿}\overline{u}`$. For $`c_{\mathrm{𝗎𝗇𝗊}}>2c_{\mathrm{𝖻𝖺𝗅}}`$ this means that $`\overline{v}^{}\overline{v}=k\overline{u}`$ for some integer $`k0`$. As before, by considering the first coordinate of $`\overline{v}^{}\overline{v}`$ in the lattice basis we get that $`(a_1^{}p+t^{}m)(a_1p+tm)km(\mathrm{mod}p)`$. Hence, $`kt^{}t(\mathrm{mod}p)`$. If $`t=t^{}`$ then $`k0(\mathrm{mod}p)`$ and therefore $`|k|p`$ which contradicts the above upper bound on the distance between $`\overline{v}`$ and $`\overline{v}^{}`$. This proves the first part of the claim. For the second part, let $`t=0`$ and $`t^{}=1`$. Then, $`k1(\mathrm{mod}p)`$. As before, this can only happen when $`k=1`$ and hence the second part of the claim holds.

Notice that the probability of measuring $`\overline{x}^{}`$ is the same as that obtained by first choosing random $`t`$ and $`\overline{a}`$ and then choosing a random point in $`f(t,\overline{a})+\frac{1}{L}^nB_n`$. Let us define for any $`t`$ and $`\overline{a}`$ the vector $`\overline{a}^{}`$ as before.

###### Claim 3.14

With probability at least $`1\frac{1}{(n\mathrm{log}(2M))^𝖿}`$, for randomly chosen $`t`$ and $`\overline{a}`$ and a random point $`\overline{x}^{}`$ in $`f(t,\overline{a})+\frac{1}{L}^nB_n`$, $`\overline{a}^{}`$ is in $`𝒜`$ and $`\overline{x}^{}`$ is also in $`f(1t,\overline{a}^{})+\frac{1}{L}^nB_n`$.

+ According to Lemma 3.3, $`|u_i|<2^{2n}`$. Hence, unless there exists an $`i`$ for which $`a_i<2^{2n}`$ or $`a_i>M2^{2n}`$, $`\overline{a}^{}`$ is guaranteed to be in $`𝒜`$. This happens with probability at most $`n2^{2n+1}/M`$ because $`\overline{a}`$ is a random element of $`𝒜`$.

    Fix $`\overline{a},\overline{a}^{}𝒜`$. We would like to show that if $`\overline{x}^{}`$ is chosen uniformly from $`f(t,\overline{a})+\frac{1}{L}^nB_n`$ then with high probability it is also in $`f(1t,\overline{a}^{})+\frac{1}{L}^nB_n`$. By translating both sets by $`f(t,\overline{a})`$ we get the equivalent statement that if $`\overline{x}^{}`$ is chosen uniformly from $`\frac{1}{L}^nB_n`$ then with high probability it is also in $`(f(1t,\overline{a}^{})f(t,\overline{a}))+\frac{1}{L}^nB_n`$. Since we assumed that our lattice is a subset of $`^n`$, $`f(1t,\overline{a}^{})f(t,\overline{a})^n`$ and the latter set equals $`\frac{1}{L}^n(f(1t,\overline{a}^{})f(t,\overline{a})+B_n)`$. Using Corollary 3.9 and the fact that $`f(1t,\overline{a}^{})f(t,\overline{a})=\overline{u}l`$, we get that the required probability is at least

    $$1O(\sqrt{n}l/R)=1O(\sqrt{n}l/(c_{\mathrm{𝖻𝖺𝗅}}n^{\frac{1}{2}+2𝖿}l))=1O(1/(c_{\mathrm{𝖻𝖺𝗅}}n^{2𝖿})).$$

    The sum of the two error probabilities $`n\frac{2^{2n+1}}{M}+O(1/(c_{\mathrm{𝖻𝖺𝗅}}n^{2𝖿}))`$ is at most $`\frac{1}{(n\mathrm{log}(2M))^𝖿}`$ for $`c_{\mathrm{𝖻𝖺𝗅}}`$ large enough.

This concludes the proof of Lemma 3.12.

## 4 The Dihedral Coset Problem

We begin this section with a description of the average case subset sum problem. We describe our assumptions on the subroutine that solves it and prove some properties of such a subroutine. In the second subsection we present an algorithm that solves the DCP with calls to an average case subset sum subroutine.

### 4.1 Subset Sum

The subset sum problem is defined as follows. An input is a sequence of numbers $`A=(a_1,\mathrm{},a_r)`$ and two numbers $`t,N`$. The output is a subset $`B[r]`$ such that $`_{iB}a_it(\mathrm{mod}N)`$. Let a legal input be an input for which there exists a subset $`B`$ with $`_{iB}a_it(\mathrm{mod}N)`$. For a constant $`c_𝗋>0`$, we fix $`r`$ to be $`\mathrm{log}N+c_𝗋`$ since we will only be interested in such instances. First we show that there are many legal inputs:

###### Lemma 4.1

For randomly chosen $`a_1,\mathrm{},a_r,t`$ in $`\{0,\mathrm{},N1\}`$, the probability that there is no $`B[r]`$ such that $`_{iB}a_it(\mathrm{mod}N)`$ is at most $`\frac{1}{2}`$.

* Fix a value of $`t`$. Define a random variable $`X_{\overline{b}}`$ for every $`\overline{b}\{0,1\}^r,\overline{b}0^r`$ as $`1`$ if $`_ib_ia_it(\mathrm{mod}N)`$ and $`0`$ otherwise. Since for every $`\overline{b}`$ the sum $`_ib_ia_i`$ has any value modulo $`N`$ with the same probability, the expectation of $`X_{\overline{b}}`$ is $`\frac{1}{N}`$ and its variance is $`\frac{1}{N}\frac{1}{N^2}<\frac{1}{N}`$. Hence,

$$E[\underset{\overline{b}}{}X_{\overline{b}}]=\underset{\overline{b}}{}E[X_{\overline{b}}]=\frac{2^r1}{N}$$

Given two different sequences $`\overline{b},\overline{b}^{}\{0,1\}^r`$ we show that $`X_{\overline{b}}`$ and $`X_{\overline{b}^{}}`$ are independent. Let $`i`$ be such that $`b_ib_i^{}`$ and assume without loss of generality that $`b_i=1,b_i^{}=0`$ and $`i=1`$. Then,

$`Pr_{a_1,\mathrm{},a_r}[X_{\overline{b}}=1X_{\overline{b}^{}}=1]`$ $`=`$ $`E_{a_2,\mathrm{},a_r}[Pr_{a_1}[X_{\overline{b}}=1X_{\overline{b}^{}}=1]]`$
$`=`$ $`E_{a_2,\mathrm{},a_r}[1/N\delta _{X_{\overline{b}^{}},1}]`$
$`=`$ $`Pr_{a_1,\mathrm{},a_r}[X_{\overline{b}}=1]Pr_{a_1,\mathrm{},a_r}[X_{\overline{b}^{}}=1]`$
where the second equality holds because $`X_{\overline{b}^{}}`$ does not depend on $`a_1`$ and $`X_{\overline{b}}`$ is 1 with probability $`1/N`$ for any $`a_2,\mathrm{},a_r`$. A similar argument holds for other values of $`X_{\overline{b}}`$ and $`X_{\overline{b}^{}}`$. Therefore, the random variables are pairwise independent and by the Chebyshev bound,

$$Pr[\underset{\overline{b}}{}X_{\overline{b}}<\frac{1}{2}\frac{2^r1}{N}]4\frac{N}{2^r1}\frac{8}{2^{c_𝗋}}.$$

In particular, the probability of $`_{\overline{b}}X_{\overline{b}}=0`$, that is, the probability that there is no $`B`$ such that $`_{iB}a_it(\mathrm{mod}N)`$ is at most $`\frac{8}{2^{c_𝗋}}=\frac{1}{2}`$ for $`c_𝗋=4`$.

We assume that we are given a subroutine that answers a $`\frac{1}{\mathrm{log}^{c_𝗌}N}`$ fraction of the legal subset sum inputs with parameter $`N`$ where $`c_𝗌>0`$ is any constant. As can be seen from the previous lemma, this implies that the subroutine answers a non-negligible fraction of all inputs (and not just the legal inputs). In addition, we assume that the subroutine is deterministic. We denote by $`S(A,t)`$ the result of the subroutine $`S`$ on the input $`A=(a_1,\mathrm{},a_r),t`$ and we omit $`N`$. This result can either be a set or an error. Let $`S(A)`$ denote the set of $`t`$’s for which the subroutine returns a set and not an error, i.e., $`S(A)=\{t|S(A,t)error\}`$.

###### Corollary 4.2

For randomly chosen $`a_1,\mathrm{},a_r`$ in $`\{0,\mathrm{},N1\}`$, $`Pr_A[|S(A)|\frac{N}{4\mathrm{log}^{c_𝗌}N}]=\mathrm{\Omega }(\frac{1}{\mathrm{log}^{c_𝗌}N})`$ where $`A=(a_1,\mathrm{},a_r)`$.

* Since $`S(A,t)error`$ only when $`(A,t)`$ is a legal input,

$`Pr_{A,t}[S(A,t)error]`$ $`=`$ $`Pr_{A,t}[S(A,t)error(A,t)\text{is legal}]`$
$`=`$ $`Pr_{A,t}[S(A,t)error|(A,t)\text{is legal}]Pr_{A,t}[(A,t)\text{is legal}]{\displaystyle \frac{1}{2\mathrm{log}^{c_𝗌}N}}.`$
In addition,

$`Pr_{A,t}[S(A,t)error]`$ $`=`$ $`E_A[{\displaystyle \frac{|S(A)|}{N}}]`$
$``$ $`Pr_A[|S(A)|{\displaystyle \frac{N}{4\mathrm{log}^{c_𝗌}N}}]+Pr_A[|S(A)|<{\displaystyle \frac{N}{4\mathrm{log}^{c_𝗌}N}}]{\displaystyle \frac{1}{4\mathrm{log}^{c_𝗌}N}}`$
$``$ $`Pr_A[|S(A)|{\displaystyle \frac{N}{4\mathrm{log}^{c_𝗌}N}}]+{\displaystyle \frac{1}{4\mathrm{log}^{c_𝗌}N}}.`$
By combining the two inequalities we obtain the corollary.

###### Lemma 4.3

Let $`T\{0,\mathrm{},N1\}`$ be a set such that $`|T|>\frac{N}{s}`$ for a certain $`s`$. Then, for any $`q<\frac{N}{8s}`$ there exists $`q^{}\{q,2q,\mathrm{},sq\}`$ such that the number of pairs $`t,t+q^{}`$ that are both in $`T`$ is $`\mathrm{\Omega }(\frac{N}{s^3})`$.

* Define the partition of $`T`$ into sets $`T_0,\mathrm{},T_{q1}`$ as

$$T_k=\{i|iT,ik(\mathrm{mod}q)\}.$$

At least $`\frac{q}{2s}`$ of the sets are of size at least $`\frac{N}{2sq}`$ since their union is $`T`$ and $`\frac{q}{2s}\frac{N}{q}+\frac{N}{2s}<|T|`$. Let $`T_i`$ be such a set and for $`tT_i`$ consider the values $`t+q,t+2q,\mathrm{},t+4sq`$. Therefore, the number of $`tT_i`$ such that none of these values is in $`T_i`$ is less than $`\frac{N}{4sq}`$ because $`|\{i|0i<N,ik(\mathrm{mod}q)\}|=\frac{N}{q}`$. Therefore, more than $`|T_i|\frac{N}{4sq}\frac{N}{4sq}`$ of the elements $`tT_i`$ are such that one of $`t+q,t+2q,\mathrm{},t+4sq`$ is also in $`T_i`$. Summing over all sets $`T_i`$ such that $`|T_i|\frac{N}{2sq}`$, there are at least $`\frac{N}{4sq}\frac{q}{2s}=\frac{N}{8s^2}`$ elements $`tT`$ for which one of $`t+q,t+2q,\mathrm{},t+4sq`$ is also in $`T`$. Thus, there exists a $`q^{}\{q,2q,\mathrm{},4sq\}`$ such that the number of $`tT`$ for which $`t+q^{}T`$ is at least $`\frac{N}{32s^3}`$.

###### Definition 4.4

A partial function $`f:\{0,\mathrm{},N1\}\{0,\mathrm{},N1\}`$ is called a matching if for all $`i`$ such that $`f(i)`$ is defined, $`f(i)i`$ and $`f(f(i))=i`$. A matching is a $`q`$-matching if for all $`i`$ such that $`f(i)`$ is defined, $`|f(i)i|=q`$. We define an equal partition of the domain of a matching $`f`$ by $`A_1(f)=\{i|f(i)definedf(i)>i\}`$ and $`A_2(f)=\{i|f(i)definedf(i)<i\}`$. The intersection of a matching $`f`$ and a set $`T\{0,\mathrm{},N1\}`$ is the set $`\{i|iTf(i)T\}`$.

For any $`q`$ we define the following $`q`$-matchings:

$$f_q^1(t)=\{\begin{array}{cc}t+q\hfill & t\mathrm{mod}2q<q,t+q<N,\hfill \\ tq\hfill & t\mathrm{mod}2qq,tq0,\hfill \\ undefined\hfill & \text{otherwise}.\hfill \end{array}f_q^2(t)=\{\begin{array}{cc}tq\hfill & t\mathrm{mod}2q<q,tq0,\hfill \\ t+q\hfill & t\mathrm{mod}2qq,t+q<N,\hfill \\ undefined\hfill & \text{otherwise}.\hfill \end{array}$$

###### Lemma 4.5

There exists a constant $`c_𝗆`$ such that for any integer $`q<\frac{N}{\mathrm{log}^{c_𝗆}N}`$ there exists a matching $`f`$ among the $`2\mathrm{log}^{c_𝗆}N`$ matchings $`f_q^1,f_{2q}^1,\mathrm{},f_{\mathrm{log}^{c_𝗆}Nq}^1,f_q^2,f_{2q}^2,\mathrm{},f_{\mathrm{log}^{c_𝗆}Nq}^2`$ such that with probability at least $`\frac{1}{\mathrm{log}^{c_𝗆}N}`$ on the choice of $`A`$, the intersection of $`f`$ and $`S(A)`$ is $`\frac{N}{\mathrm{log}^{c_𝗆}N}`$. We call such an $`f`$ a good matching.

* According to Corollary 4.2, $`\frac{1}{4\mathrm{log}^{c_𝗌}N}`$ of the possible values of $`A`$ satisfy $`|S(A)|>\frac{N}{4\mathrm{log}^{c_𝗌}N}`$. For such $`A`$, Lemma 4.3 with $`s=4\mathrm{log}^{c_𝗌}N`$ implies that there exists a value $`q^{}\{q,2q,\mathrm{},4\mathrm{log}^{c_𝗌}Nq\}`$ such that the number of pairs $`t,t+q^{}`$ that are both in $`S(A)`$ is $`\mathrm{\Omega }(\frac{N}{\mathrm{log}^{3c_𝗌}N})`$. Therefore, for such $`A`$ and $`q^{}`$, the size of the intersection of one of the matchings $`f_q^{}^1,f_q^{}^2`$ and $`S(A)`$ is $`\mathrm{\Omega }(\frac{N}{\mathrm{log}^{3c_𝗌}N})`$. This implies that one of the $`8\mathrm{log}^{c_𝗌}N`$ matchings considered must have an intersection of size $`\mathrm{\Omega }(\frac{N}{\mathrm{log}^{3c_𝗌}N})`$ with at least $`\frac{1}{32\mathrm{log}^{2c_𝗌}N}`$ of the possible values of $`A`$. We conclude the proof by choosing $`c_𝗆>3c_𝗌`$.

### 4.2 The Quantum Algorithm

We begin with the following simple claim:

###### Claim 4.6

For any two basis states $`|a`$ and $`|b`$, $`ab`$, there exists a routine such that given the state $`|a+e(\varphi )|b`$ outputs the state $`|0+e(\varphi )|1`$.

* Consider the function $`f`$ defined as $`f(a)=0,f(0)=a,f(b)=1,f(1)=b`$ and $`f(i)=i`$ otherwise. It is reversible and can therefore be implemented as a quantum routine.

We now describe the main routine in the DCP algorithm.

###### Lemma 4.7

There exist routines $`R_1,R_2`$ such that given a $`q`$-matching $`f`$ and an input for the DCP with failure parameter $`1`$, they either output a bit or they fail. Conditioned on non-failure, the probability of the bit being 1 is $`\frac{1}{2}\frac{1}{2}\mathrm{cos}(2\pi q\frac{d}{N})`$ for $`R_1`$ and $`\frac{1}{2}+\frac{1}{2}\mathrm{sin}(2\pi q\frac{d}{N})`$ for $`R_2`$. Moreover, if $`f`$ is a good matching, the success probability is $`\mathrm{\Omega }(\frac{1}{\mathrm{log}^{c_𝗆}N})`$.

* The routines begin by performing a Fourier transform on the last $`\mathrm{log}N`$ qubits of each input register. Consider one register. Assuming it is a good register, the resulting state is

$`{\displaystyle \frac{1}{\sqrt{2N}}}{\displaystyle \underset{i=0}{\overset{N1}{}}}e(ix/N)|0,i+{\displaystyle \frac{1}{\sqrt{2N}}}{\displaystyle \underset{i=0}{\overset{N1}{}}}e(i(x+d)/N)|1,i=`$
$`{\displaystyle \frac{1}{\sqrt{2N}}}{\displaystyle \underset{i=0}{\overset{N1}{}}}e(ix/N)(|0+e(id/N)|1)|i.`$
We measure the last $`\mathrm{log}N`$ qubits and let $`a\{0,\mathrm{},N1\}`$ be the result. The state collapses to

$$\frac{1}{\sqrt{2}}e(ax/N)(|0+e(ad/N)|1)|a.$$

If it is a bad register, it is in the state $`|b,x`$ where both $`b`$ and $`x`$ are arbitrary. After the Fourier transform the state is $`\frac{1}{\sqrt{N}}_{i=0}^{N1}e(ix/N)|b,i`$ and after measuring $`a`$ in the last $`\mathrm{log}N`$ qubits, the state is $`e(ax/N)|b,a`$. Notice that in both cases any value $`a`$ in $`\{0,\mathrm{},N1\}`$ has an equal probability of being measured.

We choose the number of input registers to be $`r`$. Let $`A=(a_1,\mathrm{},a_r)`$ be the sequence of values measured in the above process. Notice that this sequence is uniform and hence can be used as an input to the average case subset sum algorithm. In the following, we assume that $`s`$ of the $`r`$ registers are bad. Later we will claim that with good probability, none of the registers is bad. Yet, we have to show that even if one of the registers is bad, the routine does not return erroneous results. Without loss of generality, assume that the first $`s`$ registers are bad. The resulting state is:

$$\underset{i=1}{\overset{s}{}}[e(a_ix_i/N)|b_i,a_i]\underset{i=s+1}{\overset{r}{}}[\frac{1}{\sqrt{2}}e(a_ix_i/N)(|0+e(a_id/N)|1)|a_i].$$

Or, by omitting the multiplication by the fixed phase and the $`r\mathrm{log}N`$ fixed qubits,

$$\underset{i=1}{\overset{s}{}}[|b_i]\underset{i=s+1}{\overset{r}{}}[\frac{1}{\sqrt{2}}(|0+e(a_id/N)|1)].$$

Denote these $`r`$ qubits by $`\overline{\alpha }=(\alpha _1,\mathrm{},\alpha _r)`$.

We add $`r+1`$ new qubits, $`\overline{\beta }=(\beta _1,\mathrm{},\beta _r)`$ and $`\gamma `$. Let $`t_{\overline{\alpha }}`$ denote the sum $`_{i=1}^r\alpha _ia_i`$. Next, we perform the following operations:

$`\text{if }S(A,t_{\overline{\alpha }})\overline{\alpha }S(A,f(t_{\overline{\alpha }}))=error\text{ }\text{then }exit\text{if }t_{\overline{\alpha }}A_1(f)\text{ }\text{then }\{\begin{array}{cc}\overline{\beta }\overline{\alpha }\hfill & \\ \gamma 1\hfill & \end{array}\text{ }\text{else if }t_{\overline{\alpha }}A_2(f)\text{ }\text{then }\{\begin{array}{cc}\overline{\beta }S(A,f(t_{\overline{\alpha }}))\hfill & \\ \gamma 1\hfill & \end{array}\text{ }\text{else }exit`$

In order to describe the state after the above procedure, we define the following subsets of $`\{0,1\}^r`$:

$$M=\{\overline{\alpha }\{0,1\}^r|\alpha _1=b_1,\mathrm{},\alpha _s=b_s\}$$

$$L=\{\overline{\alpha }M|t_{\overline{\alpha }}A_1(f)S(A,t_{\overline{\alpha }})=\overline{\alpha }S(A,f(t_{\overline{\alpha }}))error\}$$

$$R=\{\overline{\alpha }M|t_{\overline{\alpha }}A_2(f)S(A,t_{\overline{\alpha }})=\overline{\alpha }S(A,f(t_{\overline{\alpha }}))error\}$$

Using the order $`|\overline{\alpha },\overline{\beta },\gamma `$, the resulting state is:

$`{\displaystyle \frac{1}{\sqrt{2^{rs}}}}({\displaystyle \underset{\overline{\alpha }MLR}{}}e(\overline{\alpha },\overline{a}{\displaystyle \frac{d}{N}})|\overline{\alpha },\overline{0},0+`$
$`{\displaystyle \underset{\overline{\alpha }L}{}}e(\overline{\alpha },\overline{a}{\displaystyle \frac{d}{N}})|\overline{\alpha },\overline{\alpha },1+{\displaystyle \underset{\overline{\alpha }R}{}}e(\overline{\alpha },\overline{a}{\displaystyle \frac{d}{N}})|\overline{\alpha },S(A,f(t_{\overline{\alpha }})),1)`$
$`=`$ $`{\displaystyle \frac{1}{\sqrt{2^{rs}}}}({\displaystyle \underset{\overline{\alpha }MLR}{}}e(\overline{\alpha },\overline{a}{\displaystyle \frac{d}{N}})|\overline{\alpha },\overline{0},0+`$
$`{\displaystyle \underset{\overline{\alpha }L}{}}(e(\overline{\alpha },\overline{a}{\displaystyle \frac{d}{N}})|\overline{\alpha },\overline{\alpha },1+e(S(A,f(t_{\overline{\alpha }})),\overline{a}{\displaystyle \frac{d}{N}})|S(A,f(t_{\overline{\alpha }})),\overline{\alpha },1))`$
$`=`$ $`{\displaystyle \frac{1}{\sqrt{2^{rs}}}}({\displaystyle \underset{\overline{\alpha }MLR}{}}e(\overline{\alpha },\overline{a}{\displaystyle \frac{d}{N}})|\overline{\alpha },\overline{0},0+`$
$`{\displaystyle \underset{\overline{\alpha }L}{}}e(\overline{\alpha },\overline{a}{\displaystyle \frac{d}{N}})(|\overline{\alpha }+e(q{\displaystyle \frac{d}{N}})|S(A,f(t_{\overline{\alpha }})))|\overline{\alpha },1)`$
Now we measure $`\overline{\beta }`$ and $`\gamma `$. If $`\gamma =0`$, the routine failed. Otherwise, the state of $`\overline{\alpha }`$ is (omitting the fixed $`\overline{\beta }`$ and $`\gamma `$):

$$\frac{1}{\sqrt{2}}(|\overline{\beta }+e(q\frac{d}{N})|S(A,f(t_{\overline{\beta }}))).$$

Notice that since $`\overline{\beta }`$ is known and $`S(A,f(t_{\overline{\beta }}))`$ can be easily found by calling $`S`$, we can transform this state to the state

$$\frac{1}{\sqrt{2}}(|0+e(q\frac{d}{N})|1)$$

by using Claim 4.6. By omitting some qubits, we can assume that this is a state on one qubit. By using the Hadamard transform the state becomes

$$\frac{1}{2}((1+e(q\frac{d}{N}))|0+(1e(q\frac{d}{N}))|1).$$

We measure the qubit and the probability of measuring $`1`$ is

$$\frac{1}{4}|1e(q\frac{d}{N})|^2=\frac{1}{4}(22\mathrm{cos}(2\pi q\frac{d}{N}))=\frac{1}{2}\frac{1}{2}\mathrm{cos}(2\pi q\frac{d}{N}).$$

This completes the description of $`R_1`$. The routine $`R_2`$ applies the transform

$$\left(\begin{array}{cc}1& 0\\ 0& ı\end{array}\right)$$

before the Hadamard transform and thus the state becomes

$$\frac{1}{2}((1+e(1/4+q\frac{d}{N}))|0+(1e(1/4+q\frac{d}{N}))|1)$$

and the probability of measuring $`1`$ becomes $`\frac{1}{2}\frac{1}{2}\mathrm{cos}(\pi /2+2\pi q\frac{d}{N})=\frac{1}{2}+\frac{1}{2}\mathrm{sin}(2\pi q\frac{d}{N})`$.

From the previous description, it is clear that the probability of measuring 1 conditioned on a non-failure is correct. Thus, it remains to prove that when $`f`$ is a good matching the failure probability is low. The success probability equals the probability of measuring $`\gamma =1`$ which is $`|LR|/2^{rs}`$. Assume that none of the $`r`$ registers is bad. Then, $`|LR|/2^{rs}=|LR|/2^r`$ and $`LR`$ becomes $`\{\overline{\alpha }\{0,1\}^r|t_{\overline{\alpha }}A_1(f)A_2(f)S(A,t_{\overline{\alpha }})=\overline{\alpha }S(A,f(t_{\overline{\alpha }}))error\}`$. Notice that the size of this set equals $`|\{t|tS(A)f(t)S(A)\}|`$ which, according to the definition of a good matching, is at least $`\frac{N}{\mathrm{log}^{c_𝗆}N}`$. Therefore the probability of success conditioned on all of the registers being good is $`|LR|/2^r=\frac{1}{2^{c_𝗋}\mathrm{log}^{c_𝗆}N}=\mathrm{\Omega }(\frac{1}{\mathrm{log}^{c_𝗆}N})`$. This concludes the proof since with probability at least $`(1\frac{1}{\mathrm{log}N})^r=(1\frac{1}{\mathrm{log}N})^{\mathrm{log}N+c_𝗋}=\mathrm{\Omega }(1)`$ none of the registers is bad.

###### Claim 4.8

Given an approximation $`x`$ of $`\mathrm{sin}\varphi `$ and an approximation $`y`$ of $`\mathrm{cos}\varphi `$ with additive error $`ϵ`$, we can find $`\varphi \mathrm{mod}2\pi `$ up to an additive error of $`O(ϵ)`$.

* Assume $`y0`$ and let $`z=\frac{x}{1+y}`$. A simple calculation shows that $`z`$ is an estimate of $`\frac{\mathrm{sin}\varphi }{1+\mathrm{cos}\varphi }`$ up to an additive error of at most $`4ϵ`$. The estimate on $`\varphi `$ is $`2\mathrm{arctan}z`$. Since the absolute value of the differential of $`\mathrm{arctan}`$ is at most $`1`$, this is an estimate of $`2\mathrm{arctan}(\frac{\mathrm{sin}\varphi }{1+\mathrm{cos}\varphi })=\varphi `$ with an additive error of at most $`8ϵ`$. When $`y<0`$ we compute an estimate of $`2\text{arccot}(\frac{\mathrm{sin}\varphi }{1\mathrm{cos}\varphi })=\varphi `$.

###### Lemma 4.9

There exists a routine $`R_3`$ such that with probability exponentially close to $`1`$, given any $`q<\frac{N}{\mathrm{log}^{c_𝗆}N}`$ finds a value $`q^{}\{q,\mathrm{},\mathrm{log}^{c_𝗆}Nq\}`$ and an estimate $`x`$ such that $`x[q^{}d\frac{N}{\mathrm{log}^{c_𝗆+1}N},q^{}d+\frac{N}{\mathrm{log}^{c_𝗆+1}N}](\mathrm{mod}N)`$.

* Assume we are given a $`q^{}`$-matching $`f`$. We call routines $`R_1`$ and $`R_2`$ $`\mathrm{log}^{3c_𝗆+4}N`$ times. If the number of successful calls to one of the routines is less than $`\mathrm{log}^{2c_𝗆+3}N`$, we fail. Otherwise, let $`x[0,1]`$ be the average of the successful calls to $`R_1`$ and $`y[0,1]`$ be the average of the successful calls to $`R_2`$. According to the Chernoff bound,

$$Pr[|x(\frac{1}{2}\frac{1}{2}\mathrm{cos}(2\pi q^{}\frac{d}{N}))|>\frac{1}{c_𝖾\mathrm{log}^{c_𝗆+1}N}]<2e^{2\mathrm{log}^{2c_𝗆+3}N/(c_{𝖾}^{}{}_{}{}^{2}\mathrm{log}^{2c_𝗆+2}N)}$$

which is exponentially low in $`\mathrm{log}N`$ for any constant $`c_𝖾>0`$. A similar bound holds for $`y`$. Hence, we can assume that $`x^{}=12x`$ and $`y^{}=2y1`$ are approximations of $`\mathrm{cos}(2\pi q^{}\frac{d}{N})`$ and of $`\mathrm{sin}(2\pi q^{}\frac{d}{N})`$ respectively up to an additive error of $`\frac{2}{c_𝖾\mathrm{log}^{c_𝗆+1}N}`$. According to Claim 4.8, this translates to an estimate of $`q^{}\frac{d}{N}\mathrm{mod}1`$ with an additive error of $`\frac{1}{\mathrm{log}^{c_𝗆+1}N}`$ for $`c_𝖾`$ large enough.

By repeating the above procedure with all the matchings that appear in Lemma 4.5, we are guaranteed to find a good matching. According to Lemma 4.7, a call to routine $`R_1`$ or to routine $`R_2`$ with a good matching succeeds with probability at least $`c_𝗀\frac{1}{\mathrm{log}^{c_𝗆}N}`$ for a certain $`c_𝗀>0`$. The probability that none of $`\mathrm{log}^{c_𝗆+1}N`$ calls to the subroutine succeeds is $`(1c_𝗀\frac{1}{\mathrm{log}^{c_𝗆}N})^{\mathrm{log}^{c_𝗆+1}N}`$ which is exponentially small. Thus, for one of the matchings, with probability exponentially close to $`1`$ we have $`\mathrm{log}^{2c_𝗆+3}N`$ successful calls to routines $`R_1`$ and $`R_2`$ and routine $`R_3`$ is successful.

We conclude the proof of Theorem 1.3 with a description of the algorithm for finding $`d`$. We begin by using routine $`R_3`$ with the value $`1`$ to obtain an estimate $`x_1`$ and a value $`\widehat{q}\mathrm{log}^{c_𝗆}N`$ such that $`x_1[d^{}\frac{N}{\mathrm{log}^{c_𝗆+1}N},d^{}+\frac{N}{\mathrm{log}^{c_𝗆+1}N}](\mathrm{mod}N)`$ where $`d^{}`$ denotes $`(d\widehat{q}\mathrm{mod}N)`$. In the following we find $`d^{}`$ exactly by calling $`R_3`$ with multiples of $`\widehat{q}`$. The algorithm works in stages. In stage $`i`$ we have an estimate $`x_i`$ and a value $`q_i`$. The invariant we maintain is $`x_i[q_id^{}\frac{N}{\mathrm{log}^{c_𝗆+1}N},q_id^{}+\frac{N}{\mathrm{log}^{c_𝗆+1}N}](\mathrm{mod}q_iN)`$ . We begin with $`x_1`$ as above and $`q_1=1`$. Assume that the invariant holds in stage $`i`$. We use routine $`R_3`$ with the value $`2q_i\widehat{q}`$ to obtain an estimate $`x`$ with a value $`q^{}\{2q_i\widehat{q},4q_i\widehat{q},\mathrm{}2\mathrm{log}^{c_𝗆}Nq_i\widehat{q}\}`$ such that $`x[q_{i+1}d^{}\frac{N}{\mathrm{log}^{c_𝗆+1}N},q_{i+1}d^{}+\frac{N}{\mathrm{log}^{c_𝗆+1}N}](\mathrm{mod}N)`$ where $`q_{i+1}=q^{}/\widehat{q}`$. Notice that our previous estimate $`x_i`$ satisfies $`\frac{q_{i+1}}{q_i}x_i[q_{i+1}d^{}\frac{2N}{\mathrm{log}N},q_{i+1}d^{}+\frac{2N}{\mathrm{log}N}](\mathrm{mod}q_{i+1}N)`$. Since this range is much smaller than $`N`$, we can combine the estimate $`x`$ on $`(q_{i+1}d^{}\mathrm{mod}N)`$ and the estimate $`\frac{q_{i+1}}{q_i}x_i`$ on $`(q_{i+1}d^{}\mathrm{mod}q_{i+1}N)`$ to obtain $`x_{i+1}`$ such that $`x_{i+1}[q_{i+1}d^{}\frac{N}{\mathrm{log}^{c_𝗆+1}N},q_{i+1}d^{}+\frac{N}{\mathrm{log}^{c_𝗆+1}N}](\mathrm{mod}q_{i+1}N)`$. The last stage is when $`q_i\frac{4N}{\mathrm{log}^{c_𝗆+1}N}`$. Then, $`d^{}`$ can be found by rounding $`\frac{x_i}{q_i}`$ to the nearest integer. Given $`d^{}`$ there are at most $`\widehat{q}\mathrm{log}^{c_𝗆}N`$ possible values for $`q`$. Since this is only a polynomial number of options we can output one randomly.

## 5 Acknowledgements

I would like to thank Dorit Aharonov, Noga Alon, Andris Ambainis, Irit Dinur, Sean Hallgren, Alexei Kitaev, Hartmut Klauck, Ashwin Nayak, Cliff Smyth and Avi Wigderson for many helpful discussions and comments.


format: text

text:
# Peculiar roles of spins in the thermal conductivity of pure and doped La2CuO4: Comparison with CuGeO3

## Abstract

In-plane and out-of-plane thermal conductivities ($`\kappa _{ab}`$ and $`\kappa _c`$) are measured on single crystals of pure, 1%-hole-doped, and 1%-Zn-doped La2CuO4. The roles of magnons and the spin stripes in the heat transport in these samples are discussed. Comparison with the heat transport in CuGeO3, which shows similar $`\kappa (T)`$ behavior as that of La2CuO4, gives us a lesson of how the heat transport can probe the difference in the spin ground state.

, , ,

thanks: Corresponding author. E-mail: ando@criepi.denken.or.jp

Thermal conductivity is a basic transport property that usually bears information on charge carriers and phonons, as well as their scattering processes. In materials where spins are playing a major role, the behavior of the thermal conductivity is largely governed by the spins, because the spin excitations can carry heat current themselves and also scatter electrons and phonons. Although the heat transport due to spin excitations in magnetic materials has been known for a long time , recent studies of the heat transport in strongly-correlated low-dimensional cuprate systems (such as high-$`T_\mathrm{c}`$ cuprates , spin-Peierls material CuGeO3 , etc.) have found the spin-related heat transport to be useful for extracting information on the peculiar spin systems in these compounds. In this paper, we present some new data on the thermal conductivity $`\kappa `$ of lightly Sr- or Zn-doped La2CuO4 (LCO), where we find unusual difference between Sr and Zn doping. Comparison of the data of lightly-doped LCO with those of CuGeO3 demonstrates how the behavior of $`\kappa (T)`$ reflects the difference in the spin ground states.

The single crystals of LCO, La2-xSrxCuO4 (LSCO), and La2Cu1-yZnyO4 (LCZO) are grown by the traveling-solvent floating-zone technique . The thermal conductivity is measured with a steady-state technique below 150 K, and with a modified steady-state technique, which minimizes the radiation loss, above 150 K. Details of the CuGeO3 experiments are described in Refs.  and .

Figure 1 shows $`\kappa _{ab}(T)`$ and $`\kappa _c(T)`$ for LCO, LSCO ($`x`$=0.01), and LCZO ($`y`$=0.01); here, we concentrate on comparing the effect of hole doping and Zn doping of the same amount, 1%. The LCO sample has the Néel temperature $`T_\mathrm{N}`$ of 307 K. It has been discussed  for LCO that the high-temperature peak in $`\kappa _{ab}(T)`$ is due to magnons, while the low-temperature peak is due to phonons. In our doped samples, $`T_\mathrm{N}`$ is still relatively high for both LSCO with $`x`$=0.01 ($`T_\mathrm{N}`$=242 K) and LCZO with $`y`$=0.01 ($`T_\mathrm{N}`$=295 K); nevertheless, the high-temperature peak already disappears in LSCO, while it clearly remains in LCZO. This observation supports the picture that magnons cause the high-temprature peak and suggests that Sr doping is more detrimental to the magnon heat transport than Zn doping. On the other hand, the low-temperature phonon peak in $`\kappa _{ab}(T)`$ is more strongly suppressed in LCZO than in LSCO; this is not what is expected from simple defect scattering, because the atomic mass difference between Cu and Zn is much smaller than that between La and Sr. Most likely, the enhanced damping of the phonon peak in LCZO is due to the magnon scattering of phonons.

When one looks at the $`\kappa _c(T)`$ behaviors in Fig. 1(b), one notices that the difference between Sr- and Zn-doping is more pronounced in this direction, and the trend is opposite to that in $`\kappa _{ab}(T)`$; namely, along the $`c`$-axis the Sr doping causes much stronger damping of the phonon peak. Although the exact mechanism of this strong damping is to be scrutinized by future research, we tentatively ascribe this effect to the spin stripes observed by neutrons  in this lightly Sr-doped region: Since there is a strong spin-lattice coupling in LSCO , formation of the spin stripes is expected to induce local lattice distortions; such lattice distortions do not scatter phonons if they are periodic (in fact, we do not see strong scattering of phonons in the in-plane direction, for which the stripes are well ordered), but the stripes are known to be very disordered along the $`c`$-axis . Thus, we have a good reason to expect that the anomalous damping of the phonon peak in $`\kappa _c`$(T) with only 1% of hole doping is due to the existence of peculiar spin texturing and strong spin-lattice coupling.

Comparison of the data in Fig. 1(a) to the $`\kappa (T)`$ behavior of CuGeO3  measured along the spin chain direction (Fig. 2) is quite illuminating. The 0-T data in Fig. 2 look quite similar to the $`\kappa _{ab}(T)`$ data of LCO, which is natural because in both systems the high-temperature peak is caused by the heat conduction due to spin excitations and the low-temperature peak is due to phonons. The spin heat transport (high-temperature peak) is quickly suppressed upon doping Mg to CuGeO3 , as is the case with doped LCO. The difference between the two systems becomes evident when one compares the magnetic-field dependences. In CuGeO3, as is shown in Fig. 2, application of magnetic field along the chain direction causes a damping of the phonon peak, and the 14-T field, which closes the spin gap of the spin-Peierls state, completely suppresses the phonon peak; we discussed  that this is because more and more spin excitations (which scatter phonons) are allowed as the spin gap is suppressed with the magnetic field. On the other hand, for LCO, we observed that the $`\kappa (T)`$ behavior is essentially unchanged with magnetic field; this is understandable, because the characteristic magnetic energy in LCO is given by the exchange interaction $`J`$, which is order of 2000 K. Therefore, the behavior of the thermal conductivity clearly reflects the different nature of the spin ground state in the two systems.

The experiments on CuGeO3 were done in collaboration with A. Kapitulnik, I. Tanaka, R. S. Feigelson, I. Tsukada, T. Masuda, and K. Uchinokura.


text:
# Viscoelasticity in normal 3He as a consequence of the Landau theory of normal Fermi liquids

## Abstract

We show that a viscoelastic dispersion relation for shear waves in normal 3He at low temperatures follows directly from the Landau theory of normal Fermi liquids. This theoretical result is in accord with the experimental observations of propagating high frequency shear waves that identify normal 3He as a viscoelastic substance.

A viscoelastic substance has high frequency properties that are characteristic of a solid an at low frequency the properties of a viscous fluid. The best known example is Silly Putty©. At very low temperatures, 3He in its normal state also has these properties Rudnick (1980). Somewhat surprisingly it was only recognized to be a viscoelastic substance several years after the development of the Landau theory of normal Fermi systems Landau (1957). 3He is also a remarkable viscoelastic liquid. Ordinary liquids exhibit viscoelasticity that is far from simple. Both shear and bulk moduli relax, and a spectrum of relaxation times is commonly observed Herzfeld and Litovitz (1959). A viscoelastic substance in which only the shear modulus relaxes, with a single relaxation time, is called an ideal viscoelastic substance. Based on experiments with longitudinal sound, 3He appears to be an ideal viscoelastic substance, and is, furthermore, the *only known example* of such a substance. It has been shown on theoretical grounds Bedell and Pethick (1982) that this is true to a “reasonable first approximation.” However, it is also found in in Bedell and Pethick (1982) that ideal viscoelastic behavior is “only a crude first approximation for *transverse* sound,” and that the ideal “viscoelastic model does not give quantitatively reliable results.” Special importance is attached to the fact that the transverse sound velocity is less than or equal to the Fermi velocity, and it is inferred that this interferes with the validity of the viscoelastic interpretation of transverse zero sound.

The purpose of this note is to show that Fermi liquid theory can be used to derive the general viscoelastic equations for transverse zero sound exactly, independently of the relative magnitudes of the transverse sound velocity and the Fermi velocity. Thus, while 3He may not be an ideal viscoelastic substance for transverse sound, nevertheless it is a viscoelastic substance.

What we are able to do is show that the Landau theory leads to a dispersion relation for transverse zero sound that is *exactly* as given by a viscoelastic model. This dispersion relation is

$$\left(\frac{\omega }{q}\right)^2=\frac{\mu _{}(q,\omega )}{\rho }$$
(1)
where $`\omega `$ and $`q`$ are the frequency and wave vector of the transverse mode, $`\rho `$ is the mass density and $`\mu _{}(q,\omega )`$ is the transverse modulus, i. e.

$$\mathrm{\Pi }_{xz}=\mu _{}\left(\frac{u_x}{z}+\frac{u_z}{x}\right)$$
(2)
where $`\mathrm{\Pi }_{xz}`$ is an off-diagonal element of the stress tensor and $`(u_x/z+u_z/x)`$ is the corresponding elemetnt of the strain tensor. The dependence on $`q`$ of $`\mu _{}`$ arises from its non-locality in real space.

In the remainder of this note, we obtain from the Landau theory of normal Fermi liquids a general expression for $`\mu _{}(q,\omega )`$. We then derive a closed-form dispersion relation for propagating transverse modes, valid for all frequencies and relaxation times. Finally, we show that this dispersion relation can be cast in the form (1). This establishes the viscoelastic model of transverse zero sound propagation as a rigorous outcome of Landau theory. We note at the outset that two assumptions are made in obtaining our result. The first is that all Landau parameters $`F_l`$ with $`l3`$ are zero. The second is that all distortions of the Fermi surface decay locally via collisions with a single relaxation time, with the exception of a dilation and a translation, which do not decay via collisions because of particle and momentum conservation.

Small deviations from equilibrium of the quasiparticle distribution function, $`n_\stackrel{}{p}(\stackrel{}{x},t)`$ will be denoted by $`\delta n_\stackrel{}{p}(\stackrel{}{x},t)`$, where $`\stackrel{}{p}`$ is the quasiparticle momentum not . We assume that the mode has a space and time dependence of the form $`e^{i(qz\omega t)}`$. The linearized Landau kinetic equation is, then, in the absence of external forcing Bedell and Pethick (1982),

$$\left(i\omega +iqv_F\mathrm{cos}\theta \right)n_\stackrel{}{p}+\frac{n_\stackrel{}{p}^0}{ϵ_F}\mathrm{cos}\theta \underset{\stackrel{}{p}^{}}{}f_{\stackrel{}{p}\stackrel{}{p}^{}}^s\delta n_\stackrel{}{p}^{}=I\left[n_\stackrel{}{p}\right]$$
(3)
The quantity $`f_{\stackrel{}{p}\stackrel{}{p}^{}}^s`$ is the spin-symmetric quasiparticle interaction energy, $`I[n_\stackrel{}{p}]`$ is the collision contribution to the kinetic equation and $`n_\stackrel{}{p}^0`$ is the equilibrium distribution. We are interested in transverse modes, so we write

$`\delta n_\stackrel{}{p}`$ $`=`$ $`{\displaystyle \frac{n_\stackrel{}{p}^0}{ϵ_\stackrel{}{p}}}\nu _\stackrel{}{p}`$ (4)
$`=`$ $`{\displaystyle \frac{N(0)}{p_F^2}}\delta (pp_F)\nu _\stackrel{}{p}`$
where $`p_F`$ is the Fermi momentum,

$$\nu _\stackrel{}{p}=B\mathrm{sin}\theta \mathrm{cos}\varphi +D\mathrm{sin}\theta \mathrm{cos}\theta \mathrm{cos}\varphi +\overline{\nu }_\stackrel{}{p}$$
(5)
and $`\overline{\nu }_\stackrel{}{p}`$ consists of the contributions of all higher order, appropriately transverse, spherical harmonics to $`\nu _\stackrel{}{p}`$. Inserting (4) and (5) into (3), and adopting a single-relaxation-time model for $`I[n_\stackrel{}{p}]`$ we obtain

$`\left[i\omega +iqv_F\mathrm{cos}\theta \left(1+{\displaystyle \frac{F_1}{3}}\right)\right]B\mathrm{sin}\theta \mathrm{cos}\varphi `$
$`+\left[i\omega +iqv_F\mathrm{cos}\theta \left(1+{\displaystyle \frac{F_2}{5}}\right)+{\displaystyle \frac{1}{\tau }}\right]D\mathrm{sin}\theta \mathrm{cos}\theta \mathrm{cos}\varphi `$
$`+\left[i\omega +iqv_F\mathrm{cos}\theta +{\displaystyle \frac{1}{\tau }}\right]\overline{\nu }_\stackrel{}{p}`$ $`=`$ $`0`$
We are assuming that $`F_l=0`$ when $`l3`$. The $`F_l`$’s are Landau parameters defined in the standard way.

The modulus $`\mu _{}`$ can now be obtained from (3) using

$`\mathrm{\Pi }_{xz}`$ $`=`$ $`{\displaystyle \underset{\stackrel{}{p}}{}}p_x(v_\stackrel{}{p})_z\delta \overline{n}_\stackrel{}{p}`$ (7)
$`=`$ $`p_Fv_FN(0)D\left(1+{\displaystyle \frac{F_2}{5}}\right){\displaystyle \mathrm{sin}^3\theta \mathrm{cos}^2\theta \mathrm{cos}^2\varphi d\theta d\varphi }`$
$`=`$ $`p_Fv_FN(0)D\left(1+{\displaystyle \frac{F_2}{5}}\right)I_1`$
where the last equality should be taken as a definition of $`I_1`$. In (7), we used

$$\delta \overline{n}_\stackrel{}{p}=\delta n_\stackrel{}{p}\frac{n_\stackrel{}{p}^0}{ϵ_\stackrel{}{p}}\underset{\stackrel{}{p}^{}}{}f_{\stackrel{}{p}\stackrel{}{p}^{}}^s\delta n_\stackrel{}{p}^{}$$
(8)
The strain tensor, $`\stackrel{}{u}_{xz}`$ is calculated using the connection between current density and strain Bedell and Pethick (1982). One obtains

$`{\displaystyle \frac{u_x}{z}}`$ $`=`$ $`{\displaystyle \frac{qN(0)}{\omega n}}v_FB\left(1+{\displaystyle \frac{F_1}{3}}\right){\displaystyle \mathrm{sin}^3\theta \mathrm{cos}^2\varphi d\theta d\varphi }`$ (9)
$`=`$ $`{\displaystyle \frac{qN(0)}{\omega n}}v_FB\left(1+{\displaystyle \frac{F_1}{3}}\right)I_2`$
The last equality above defines $`I_2`$. Thus,

$`\mu _{}`$ $`=`$ $`{\displaystyle \frac{\mathrm{\Pi }_{xz}}{u_x/z}}`$ (10)
$`=`$ $`{\displaystyle \frac{\omega np_F}{q}}{\displaystyle \frac{D}{B}}{\displaystyle \frac{1+\frac{F_2}{5}}{1+\frac{F_1}{3}}}{\displaystyle \frac{I_1}{I_2}}`$
The quantity $`n`$ in (9) and (10) is the particle number density.

The ratio $`D/B`$ in (10) is obtained by noting that $`\overline{\nu }_\stackrel{}{p}`$, which, according to (LABEL:eq:6) is given by

$`\overline{\nu }_\stackrel{}{p}`$
$`=`$ $`{\displaystyle \frac{\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_1}{3}\right)}{\omega qv_F\mathrm{cos}\theta +\frac{i}{\tau }}}B\mathrm{sin}\theta \mathrm{cos}\varphi `$
$`{\displaystyle \frac{\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_2}{5}\right)+\frac{i}{\tau }}{\omega qv_F\mathrm{cos}\theta +\frac{i}{\tau }}}D\mathrm{cos}\theta \mathrm{sin}\theta \mathrm{cos}\varphi `$
is orthogonal to the spherical harmonic $`Y_2^1\mathrm{cos}\theta \mathrm{sin}\theta \mathrm{cos}\varphi `$. Thus,

$$\frac{D}{B}=\frac{\frac{\left(\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_1}{3}\right)\right)\mathrm{cos}\theta \mathrm{sin}^3\theta \mathrm{cos}^2\varphi }{\omega qv_F\mathrm{cos}\theta +\frac{i}{\tau }}𝑑\theta 𝑑\varphi }{\frac{\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_2}{5}\right)+\frac{i}{\tau }}{\omega qv_F\mathrm{cos}\theta +\frac{i}{\tau }}\mathrm{cos}^2\theta \mathrm{sin}^3\theta \mathrm{cos}^2\varphi d\theta d\varphi }$$
(12)
The modulus described by (10) with $`D/B`$ given by (12) interpolates between a low frequency limit proportional to $`\omega \tau /i`$ and a finite high frequency limit that is real and positive if $`\omega >qv_F`$ and complex otherwise. It is thus a viscoelastic modulus.

Equation (LABEL:eq:11) also provides us with the dispersion relation for a propagating transverse mode. Notice that $`\overline{\nu }_\stackrel{}{p}`$ is also orthogonal to $`Y_1^1\mathrm{sin}\theta \mathrm{cos}\varphi `$. We then obtain the following requirement for a nontrivial solution to the undriven kinetic equation:

$`{\displaystyle \frac{\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_1}{3}\right)}{\omega qv_F\mathrm{cos}\theta +\frac{i}{\tau }}\mathrm{sin}^3\theta \mathrm{cos}^2\varphi d\theta d\varphi }`$ (13)
$`=`$ $`{\displaystyle \frac{\frac{\left(\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_1}{3}\right)\right)\mathrm{cos}\theta \mathrm{sin}^3\theta \mathrm{cos}^2\varphi d\theta d\varphi }{qv_F\mathrm{cos}\theta +\frac{i}{\tau }}\frac{\left(\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_2}{5}\right)+\frac{i}{\tau }\right)\mathrm{cos}\theta \mathrm{sin}^3\theta \mathrm{cos}^2\varphi d\theta d\varphi }{\omega qv_F\mathrm{cos}\theta +\frac{i}{\tau }}}{\frac{\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_2}{5}\right)+\frac{i}{\tau }}{qv_F\mathrm{cos}\theta +\frac{i}{\tau }}\mathrm{cos}^2\theta \mathrm{sin}^3\theta \mathrm{cos}^2\varphi d\theta d\varphi }}`$
This is a closed-form dispersion relation for undriven transverse modes in a normal Fermi liquid. Its solution interpolates between an overdamped low frequency mode and a propagating high frequency shear wave.

A few further manipulations suffice to reduce this dispersion relation to the desired form (1). First, for the left hand side we have

$`{\displaystyle \left(\frac{1}{\omega qv_F\mathrm{cos}\theta +\frac{i}{\tau }}\frac{1}{\omega +\frac{i}{\tau }}\right)\left(\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_1}{3}\right)\right)}`$ (14)
$`\mathrm{sin}^3\theta \mathrm{cos}^2\varphi d\theta d\varphi `$
$`+{\displaystyle \frac{\omega }{\omega +\frac{i}{\tau }}}{\displaystyle \mathrm{sin}^3\theta \mathrm{cos}^2\varphi d\varphi d\theta }`$
$`=`$ $`{\displaystyle \frac{qv_F}{\omega +\frac{i}{\tau }}}{\displaystyle \frac{\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_1}{3}\right)}{\omega qv_F\mathrm{cos}\theta +\frac{i}{\tau }}\mathrm{cos}\theta \mathrm{sin}^3\theta \mathrm{cos}^2\varphi d\theta d\varphi }`$
$`+{\displaystyle \frac{\omega }{\omega +\frac{i}{\tau }}}I_2`$
Inserting this into (13) we obtain, after some manipulations,

$`\omega I_2`$ $`=`$ $`\{{\displaystyle }{\displaystyle \frac{\left(\omega +\frac{i}{\tau }\right)\mathrm{cos}\theta \mathrm{sin}^3\theta \mathrm{cos}^2\varphi \left(\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_2}{5}\right)+\frac{i}{\tau }\right)d\theta d\varphi }{\omega qv_F\mathrm{cos}\theta +\frac{i}{\tau }}}`$ (15)
$`qv_F{\displaystyle }{\displaystyle \frac{\mathrm{cos}^2\theta \mathrm{sin}^3\theta \mathrm{cos}^2\varphi \left(\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_2}{5}\right)+\frac{i}{\tau }\right)d\theta d\varphi }{\omega qv_F\mathrm{cos}\theta +\frac{i}{\tau }}}\}`$
$`\times \left\{{\displaystyle \frac{\frac{\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_1}{3}\right)}{\omega qv_F\mathrm{cos}\theta +\frac{i}{\tau }}\mathrm{cos}\theta \mathrm{sin}^3\theta \mathrm{cos}^2\varphi d\theta d\varphi }{\frac{\omega qv_F\mathrm{cos}\theta \left(1+\frac{F_2}{5}\right)+\frac{i}{\tau }}{\omega qv_F\mathrm{cos}\theta +\frac{i}{\tau }}\mathrm{cos}^2\theta \mathrm{sin}^3\theta \mathrm{cos}^2\varphi d\theta d\varphi }}\right\}`$
A few straightforward steps and reference to (9) and (12) yields

$$\omega =qv_F\left(1+\frac{F_2}{5}\right)\frac{I_1}{I_2}\frac{D}{B}$$
(16)
Thus,

$$\left(\frac{\omega }{q}\right)^2=\frac{\omega v_F}{q}\left(1+\frac{F_2}{5}\right)\frac{I_1}{I_2}\frac{D}{B}$$
(17)
Using (10):

$$\left(\frac{\omega }{q}\right)^2=\frac{1}{n}\frac{v_F}{p_F}\left(1+\frac{F_2}{5}\right)\mu _{}(q,\omega )$$
(18)
Finally, since $`1+F_1/3=m^{}/m`$ and $`v_F=p_F/m^{}`$, we have

$`\left({\displaystyle \frac{\omega }{q}}\right)^2`$ $`=`$ $`{\displaystyle \frac{1}{mn}}\mu _{}`$ (19)
$`=`$ $`{\displaystyle \frac{1}{\rho }}\mu _{}`$
and the viscoelastic dispersion relation is recovered.

The above result establishes the viscoelastic model for transverse zero sound propagation in normal 3He as an exact consequence, within the assumptions noted above, of the Landau theory of normal Fermi liquids. However, we would like to point out that a propagating shear mode in liquid 3He is, in and of itself, evidence that the substance is viscoelastic. Such a mode occurs in solids and not in liquids. The criticisms base on the Landau theory of normal Fermi liquids have been of the modeling of transverse zero sound as an *ideal* viscoelastic phenomenon. Because the Fermi velocity is greater than the velocity of transverse zero sound we do not expect the spatially local modulus with a single relaxation time that characerizes an ideal viscoelastic substance to apply here. As pointed out earlier, *no* viscoelastic substance has been found to be ideal with the single exception of 3He as a medium for longitudinal mode propagation. That the dispersion relation for transverse modes in 3He does not fit the ideal viscoelastic model is therefore not surprising. In our opinion, viscoelasticity provides an intuitively useful and quantitatively valuable model for zero sound propagation in normal 3He. Furthermore, as we have just seen, it follows directly from Landau theory.