text:
# Quantum Algorithm Uncertainty Principles

## 0. Introduction

Feynman and Bennet (see ) previously asked if Heisenberg’s uncertainty principle puts a limitation on quantum computers. Feynman’s answer was negative. Given that the quantum Fourier transform is at the core of Shor’s type of quantum algorithms, it is natural to ask if the finite Fourier transform uncertainty principle puts limitations on quantum algorithms and quantum computers. In this paper, we will show that the discrete time Fourier transform uncertainty principle is an aid for Shor’s type of quantum algorithms.

It is well known that the uncertainty principle is a property of Fourier analysis. Basically, the uncertainty principle says that a nonzero function $`f`$ and its Fourier transform $`\widehat{f}`$ can not be both highly localized or concentrated. In applications, the most famous uncertainty principle is Heisenberg’s uncertainty principle. There are also less well known finite Fourier transform uncertainty principles that are used in signals analysis (see  and ). We will use ideas from the latter uncertainty principles to derive lower bounds for the probability of measuring an element in some set $`T`$ in a certain class of quantum algorithms.

We will consider quantum algorithms of the following type. Start with two registers both set to $`0`$. Apply the quantum Fourier transform (over $`p`$) to the first register. Compute from the first register the function $`g\left(j\right)`$ and store its value in the second register:

$$|0|0\frac{1}{\sqrt{p}}\underset{j=0}{\overset{p1}{}}|j|0\frac{1}{\sqrt{p}}\underset{j=0}{\overset{p1}{}}|j|g\left(j\right).$$
$`0.1`$
We then measure the second register and see the value $`b`$. Next, zero-pad the $`p`$ dimensional quantum state up to a $`q`$ dimensional quantum state for $`qp`$ and then apply the quantum Fourier transform (over $`q`$) to the first register. Using the notation

$$B=\left\{c_p\right|g\left(c\right)=b\},$$
$`0.2`$
in mathematical notation, the process is

$`{\displaystyle \frac{1}{\sqrt{p}}}{\displaystyle \underset{j=0}{\overset{p1}{}}}|j|g\left(j\right){\displaystyle \frac{1}{\sqrt{|B|}}}{\displaystyle \underset{cB}{}}|c|b`$ $`0.3`$
$`{\displaystyle \frac{1}{\sqrt{|B|}}}{\displaystyle \frac{1}{\sqrt{q}}}{\displaystyle \underset{k=0}{\overset{q1}{}}}\left\{{\displaystyle \underset{cB}{}}\mathrm{exp}\left({\displaystyle \frac{2i\pi ck}{q}}\right)\right\}|k|b`$
$`{\displaystyle \frac{1}{\sqrt{|B|}}}{\displaystyle \frac{1}{\sqrt{q}}}{\displaystyle \underset{k=0}{\overset{q1}{}}}\left\{{\displaystyle \underset{cB}{}}\mathrm{exp}\left({\displaystyle \frac{2i\pi ck}{q}}\right)\right\}|k,`$
where we have dropped the second register in the last expression in 0.3 since it no longer concerns us. Finally, we measure the first register and we would like to know the probability of measuring an element in some set $`T`$ in this last measurement. Let us denote this probability by $`prob(T,p,q)`$. In particular,

$$prob(T,p,q)=\frac{1}{q|B|}\underset{cT}{}\left|\underset{cB}{}\mathrm{exp}\left(\frac{2i\pi ck}{q}\right)\right|^2$$
$`0.4`$
In general, the expression in 0.4 is hard to compute in closed form. Techniques have been developed to derive lower bounds for 0.4 and the correctness of Shor’s factoring and discrete log algorithm can be derived this way (see ). We now rewrite 0.4 in terms of the time-limiting and band-limiting operators. Let $`f=|0`$, then $`f_j\mathrm{exp}\left(\frac{2i\pi jc}{q}\right)`$ is $`0`$ if $`j0`$ and it is $`1`$ if $`j=0`$. Using this, 0.3 can be written as

$$\frac{1}{\sqrt{|B|}}\frac{1}{\sqrt{q}}\underset{k=0}{\overset{q1}{}}\left\{\underset{cB}{}\left(\underset{j=0}{\overset{q1}{}}f_j\mathrm{exp}\left(\frac{2i\pi jc}{q}\right)\right)\mathrm{exp}\left(\frac{2i\pi ck}{q}\right)\right\}|k.$$
$`0.5`$
The expression in 0.5 is $`\sqrt{\frac{q}{|B|}}R_B^qf`$ where $`R_B^qf`$ is the band-limiting operator from finite Fourier transform analysis. In signals analysis language, the band-limiting operator Fourier transforms $`f`$ into the frequency domain, zeros out the transformed signal outside of some band $`B`$ and then attempts to reconstruct the original signal $`f`$ with an inverse Fourier transform as given in 0.5. Also from signals analysis, for any signal $`f`$, the time-limiting operator $`P_T^qf`$ zeros out f outside of the set $`T`$. With the time and band-limiting operators, 0.4 can be written as

$$prob(T,p,q)=\frac{q}{|B|}P_T^qR_B^qf_2^2.$$
$`0.6`$
The goal of this paper is to derive lower bounds for 0.6. This is important since if the lower bound is of the form

$$prob(T,p,q)>\frac{1}{poly\left(\text{input size}\right)},$$
$`0.7`$
then by repeating the experiment a polynomial number of times, we can measure something in $`T`$ with high probability. We also know that the quantum Fourier transform can be implemented with a polynomial number of gates (see ). Hence, given 0.7, we can use a polynomial number of quantum gates to measure something in $`T`$ with high probability. It turns out that there is a finite Fourier transform uncertainty principle associated with the right-hand-side of 0.6. It is given by

$$\left(1ϵ\eta \right)f_2P_T^qR_B^qf_2P_T^qR_B^qf_2,$$
$`0.8`$
where $`ϵ`$ and $`\eta `$ depends on $`f`$. At first glance, the uncertainty principle might be useful for quantum computing since it provides a lower bound for 0.6. Unfortunately, 0.8 is useless for quantum computing because for $`f=|0`$, $`ϵ+\eta 1`$. Nonetheless, the proof of the uncertainty principle in 0.8 was enlightening. It paved the way to deriving some general lower bounds for 0.6 and these lower bounds can be used to derive Shor’s factoring and discrete log algorithm. We will call these lower bounds quantum algorithm uncertainty principles or QAUP for short.

It is well known that factoring a positive integer $`N`$ can be reduced to finding the period $`r`$ of the function $`x^amodN`$ for some $`xmodN`$. Shor (see  and ) showed us how to do this. Hallgren and Hales () abstracted the essentials from Shor’s algorithm and derived quantum Fourier sampling theorems (QFST) to deal with the type of problems similar to the one in the last paragraph. Basically, when applied to quantum algorithms, QFST relate $`prob(T,p,p)`$ to $`prob(T^{^{}},p,q)`$ via equations of the type

$$prob(T^{^{}},p,q)\frac{1}{poly\left(\text{input size}\right)}prob(T,p,p).$$
$`0.9`$
Here, $`q=poly\left(\text{input size}\right)p`$ and $`T^{^{}}`$ is nicely related to $`T`$ (for the factoring problem, $`T^{^{}}=\left\{\frac{qj}{p}\right|jT\}`$ ). Thus, if

$$prob(T,p,p)>\frac{1}{poly\left(\text{input size}\right)},$$
$`0.10`$
then

$$prob(T^{^{}},p,q)>\frac{1}{poly\left(\text{input size}\right)}.$$
$`0.11`$
This tells us that we can apply the quantum Fourier transform over some smooth $`q>p`$ and we are in business to measure something in $`T^{^{}}`$.

The proof of the uncertainty principle that we are interested in compares $`f`$ to $`P_T^qR_B^qf`$. The theorems derived in  compares $`prob(T^{^{}},p,q)`$ to $`prob(T,p,p)`$. It turns out that the proof of the uncertainity principle can be modified to compare $`prob(T^{^{}},p,q)`$ to $`prob(T,p,p)`$ also. Let us write

$$prob(T,p,p)=\underset{kT}{}prob(k,p,p).$$
$`0.12`$
The type of lower bounds that we will derive is of the form

$$prob(T^{^{}},p,q)\frac{p}{q}\underset{kT}{}\left(\sqrt{prob(k,p,p)}small(k,\mathrm{})\right)^2,$$
$`0.13`$
for $`q>p`$. Here, $`small(k,\mathrm{})`$ is some small number that depends on all the variables involved, $`T`$ and $`T^{^{}}`$ do not have to be nicely related to each other as long as for all values of $`k`$, the expression that gets squared in 0.13 is positive.

After deriving quantum algorithm uncertainty principles, we will apply them to the factoring and discrete log problems. For factoring, $`\sqrt{prob(k,p,p)}=\frac{1}{\sqrt{r}}`$ for all $`k`$ and $`|T|=\mathrm{\Phi }\left(r\right)`$, where $`\mathrm{\Phi }\left(r\right)`$ is the Euler phi function. After some computation, $`\sqrt{prob(k,p,p)}=\frac{1}{\sqrt{r}}`$ factors out of the right-hand-side of 0.13 leaving

$`prob(T^{^{}},p,q){\displaystyle \frac{p}{q}}\left(1small\right)^2{\displaystyle \underset{cT}{}}{\displaystyle \frac{1}{r}}={\displaystyle \frac{p}{q}}\left(1small\right)^2{\displaystyle \frac{\mathrm{\Phi }\left(r\right)}{r}}>`$ $`0.14`$
$`{\displaystyle \frac{p}{q}}\left(1small\right)^2{\displaystyle \frac{1}{\mathrm{log}\mathrm{log}r}}>{\displaystyle \frac{p}{q}}\left(1small\right)^2{\displaystyle \frac{1}{poly\left(\mathrm{log}r\right)}}.`$
This tells us that it is OK to transform over some smooth $`q>p=rt`$. As in Shor’s algorithm (see ), after measuring something in $`T^{^{}}`$, $`r`$ can be recovered by using continued fractions. The discrete log problem is similar.

It is natural to ask if quantum algorithm uncertainty principles have any physical significance other than as a tool for proving theorems. This is not an easy question to answer since we currently do not have the concepts of time and frequency domain in quantum computing. One might venture to ask if the power of quantum computing is somehow related to the uncertainty principle (Heisenberg or QAUP). If it were, it would certainly be a triumph for the uncertainty principle. We will leave these questions open for future research. We will end our introduction with a quote from . “The uncertainty principle is widely known for its philosophical applications: in quantum mechanics, of course, it shows that a particle’s position and momentum can not be determined simultaneously…; in signal processing it establishes limits on the extent to which the instantaneous frequency of a signal can be measured… However, it also has technical applications, for example in the theory of partial differential equations…” \- D. Donoho and P. Stark

## 1. Finite Fourier Transform Uncertainty Principles

We start by giving a review of the finite Fourier transform uncertainty principles. The notations in this section are taken from  and they are slightly different from standard quantum computing notations. Let $`f:_q`$, then the Fourier transform of $`f`$ is the function given by

$$\widehat{f}\left(y\right)=\underset{x=0}{\overset{q1}{}}f\left(x\right)\mathrm{exp}\left(\frac{2\pi ixy}{q}\right).$$
$`1.1`$
The inverse Fourier transform of $`\widehat{f}`$ is the function given by

$$f\left(x\right)=\frac{1}{q}\underset{y=0}{\overset{q1}{}}\widehat{f}\left(y\right)\mathrm{exp}\left(\frac{2\pi ixy}{q}\right).$$
$`1.2`$
Notice that the above discrete Fourier transform is not the same transform as the quantum Fourier transform given in equation 3.1, they differ by a minus sign in the phase of the transform and an overall normalization constant. We will use a hat to denote the discrete Fourier transform and $`\text{FT}_p`$ to denote the quantum Fourier transform over $`p`$.

In vector or quantum computing notation, $`f`$ is a vector given by

$$f=\underset{j=0}{\overset{q1}{}}f_j|j$$
$`1.3`$
where $`f_j=f\left(j\right)`$. The Fourier and inverse Fourier transform are given by

$$\widehat{f}=\underset{j=0}{\overset{q1}{}}\left\{\underset{l=0}{\overset{q1}{}}f_l\mathrm{exp}\left(\frac{2\pi ilj}{q}\right)\right\}|j,$$
$`1.4`$
and

$$f=\frac{1}{q}\underset{j=0}{\overset{q1}{}}\left\{\underset{l=0}{\overset{q1}{}}\widehat{f}_l\mathrm{exp}\left(\frac{2\pi ilj}{q}\right)\right\}|j,$$
$`1.5`$
respectively.

###### Definition 1.1

The support of $`f`$ is defined to be

$$\text{supp}f=\left\{x_q\right|f\left(x\right)0\}.$$
$`1.6`$
###### Theorem 1.1 \bfUncertainty Principle - version 1

Suppose $`f:_q`$ and $`f`$ is not the zero function, then $`|\text{supp }f||\text{supp }\widehat{f}|q`$.

###### Demonstration Proof

See  and references within. ∎

###### Definition 1.2

Let $`T_q`$, define $`\delta _T:_q\{0,1\}`$ by

$$\delta _T\left(x\right)=\{\begin{array}{cc}1,\hfill & \text{if }xT\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}$$
$`1.7`$
###### Definition 1.3 Time and Band-limiting Operators

Let $`f:_q`$ and $`B,T_q`$, the time-limiting and band-limiting operators are defined by

$$\left[P_T^qf\right]\left(x\right)=f\left(x\right)\delta _T\left(x\right),$$
$`1.8`$
and

$`\left[R_B^qf\right]\left(x\right)`$ $`={\displaystyle \frac{1}{q}}{\displaystyle \underset{cB}{}}\widehat{f}\left(c\right)\mathrm{exp}\left({\displaystyle \frac{2\pi ixc}{q}}\right)`$ $`1.9`$
$`={\displaystyle \frac{1}{q}}{\displaystyle \underset{cB}{}}\left\{{\displaystyle \underset{j=0}{\overset{q1}{}}}f\left(j\right)\mathrm{exp}\left({\displaystyle \frac{2\pi ijc}{q}}\right)\right\}\mathrm{exp}\left({\displaystyle \frac{2\pi ixc}{q}}\right),`$
respectively.

The time-limiting operator zeros out $`f`$ outside of $`T`$ and the band-limiting operator attempts to reconstruct $`f`$ from $`\widehat{f}`$ by using only information within the set (band) $`B`$. In vector notation, the band-limiting operator is given by

$$R_B^qf=\frac{1}{q}\underset{k=0}{\overset{q1}{}}\left\{\underset{cB}{}\left\{\underset{j=0}{\overset{q1}{}}f_j\mathrm{exp}\left(\frac{2\pi ijc}{q}\right)\right\}\mathrm{exp}\left(\frac{2\pi ikc}{q}\right)\right\}|k.$$
$`1.10`$
From here on, we will assume that $`T\mathrm{}`$ and $`B\mathrm{}`$ since the empty set is not very interesting to us.

The 2-norm of $`f:_q`$ is defined by

$$f_2=\sqrt{f,f}=\sqrt{\underset{x=0}{\overset{q1}{}}|f\left(x\right)|^2}.$$
$`1.11`$
It follows from Parseval’s equality that $`f,f=\frac{1}{q}\widehat{f},\widehat{f}`$ and 1.11 implies that $`f_2=\frac{1}{\sqrt{q}}\widehat{f}_2`$. Let $`F=\{f:_q\}`$ and $`Q`$ be a linear operator $`Q:FF`$. The operator norm of $`Q`$ is defined by

$$Q=\underset{f0}{sup}\left\{\frac{Qf_2}{f_2}\right\}.$$
$`1.12`$
###### Lemma 1.1

Let $`T,B_q`$, then $`R_B^q=1,P_T^q=1`$, and

$$P_T^qR_B^q=R_B^qP_T^q1.$$
$`1.13`$
###### Demonstration Proof

See . ∎

###### Theorem 1.2 \bfUncertainty Principle - version 2

$$\frac{\sqrt{|T||B|}}{q}P_T^qR_B^q\sqrt{\frac{|T||B|}{q}}.$$
$`1.14`$
###### Demonstration Proof

See  . ∎

###### Definition 1.4

We say that $`f:_q`$ is $`ϵ`$-concentrated on $`T_q`$ if

$$f\delta _Tf_2=fP_T^qf_2ϵf_2,$$
$`1.15`$
and we say that $`f`$ is $`\eta `$-band-limited to $`B`$ if there is a function $`f_B:_q`$ such that $`\text{supp}(\widehat{f}_B)B`$ and

$$ff_B_2=\frac{1}{\sqrt{q}}\widehat{f}\widehat{f}_B_2\eta f_2.$$
$`1.16`$
We now present the last finite Fourier transform uncertainty principle. This uncertainty principle is the one that we are interested in for applications to quantum algorithms. We will give a proof of this version of the uncertainty principle since it compares $`f`$ to $`P_T^qR_B^qf`$ as mentioned earlier. We will modify this theorem to compare $`prob(T^{^{}},p,q)`$ to $`prob(T,p,p)`$.

###### Theorem 1.3 \bfUncertainty Principle - version 3

Suppose $`f:_q`$ is nonzero and it is $`ϵ`$-concentrated on $`T`$ as well as $`\eta `$-band-limited on $`B`$, then

$$\left(1ϵ\eta \right)f_2P_T^qR_B^qf_2,$$
$`1.17`$
and

$$1ϵ\eta P_T^qR_B^q\sqrt{\frac{|T||B|}{q}}.$$
$`1.18`$
###### Demonstration Proof (From )

We have

$`f_2P_T^qR_B^qf_2`$ $`fP_T^qR_B^qf_2`$ $`1.19`$
$`fP_T^qf_2+P_T^qfP_T^qR_B^qf_2`$
$`ϵf_2+P_T^qfR_B^qf_2`$
$`ϵf_2+fR_B^qf_2,`$
where we have used $`P_T^q=1`$ from lemma 1.1. Since $`f`$ is $`\eta `$-band-limited on $`B`$, it follows that

$`fR_B^qf_2`$ $`={\displaystyle \frac{1}{\sqrt{q}}}\widehat{f}P_B^q\widehat{f}_2`$ $`1.20`$
$`{\displaystyle \frac{1}{\sqrt{q}}}\widehat{f}f_B_2\eta f_2.`$
This gives

$$f_2P_T^qR_B^qf_2ϵf_2+\eta f_2,$$
$`1.21`$
and $`\left(1ϵ\eta \right)f_2P_T^qR_B^qf_2`$ follows. Finally, $`\left(1ϵ\eta \right)P_T^qR_B^q`$ follows from $`P_T^qR_B^qf_2\left(P_T^qR_B^q\right)f_2`$, and $`P_T^qR_B^q\sqrt{{\displaystyle \frac{|T||B|}{q}}}`$ is from uncertainty principle-version 2. ∎

## 2. Uncertainty in Quantum Algorithms

We now show how uncertainty principle - version 3 can be applied to quantum algorithms. We will consider quantum algorithms of the following form. Prepare $`|0|0`$. Apply the quantum Fourier transform (eqn. 3.1) to the prepared state

$$|0|0\frac{1}{\sqrt{p}}\underset{j=0}{\overset{p1}{}}|j|0.$$
$`2.1`$
Next, compute

$$\frac{1}{\sqrt{p}}\underset{j=0}{\overset{p1}{}}|j|0\frac{1}{\sqrt{p}}\underset{j=0}{\overset{p1}{}}|j|g\left(j\right)$$
$`2.2`$
and then measure the second register obtaining $`b=g\left(c\right)`$. This will put the quantum computer into the state

$$\frac{1}{\sqrt{|B|}}\underset{cB}{}|c,$$
$`2.3`$
where $`B=\left\{c\right|c_p,b=g\left(c\right)\}`$ and the second register is suppressed. We then zero-pad the quantum state from a $`p`$-dimensional state to a $`q`$-dimensional state for some $`qp`$ and apply the quantum Fourier transform over $`_q`$ to the first register. The quantum computer will be in the state

$$\frac{1}{\sqrt{|B|}}\frac{1}{\sqrt{q}}\underset{k=0}{\overset{q1}{}}\left\{\underset{cB}{}\mathrm{exp}\frac{2i\pi ck}{q}\right\}|k.$$
$`2.4`$
Finally, we measure the first register and the probability of measuring an element in some set $`T_q`$ is of great interest. In particular, we would like this probability to be at least $`\frac{1}{poly\left(\text{input size}\right)}`$ so that the experiment can be repeated a polynomial number of times in hope of measuring something in $`T`$ with high probability.

It turns out that the probability of measuring something in $`T`$ can be written in terms of the time-limiting and band-limiting operators from section 1. Let $`f=|0`$, then 2.4 can be written as

$$\frac{1}{\sqrt{|B|}}\frac{1}{\sqrt{q}}\underset{k=0}{\overset{q1}{}}\left\{\underset{cB}{}\left(\underset{j=0}{\overset{q1}{}}f_j\mathrm{exp}\left(\frac{2i\pi jc}{q}\right)\right)\mathrm{exp}\frac{2i\pi ck}{q}\right\}|k=\frac{\sqrt{q}}{\sqrt{|B|}}R_B^qf,$$
$`2.5`$
where the equality comes from 1.10. The probability of measuring something in the set $`T`$ is just

$$\frac{q}{|B|}P_T^qR_B^qf_2^2.$$
$`2.6`$
At first glance, the uncertainty principle - version 3 might provide a useful lower bound for the probability of measuring something in $`T`$. It turns out that version 3 is totally useless for this purpose. If $`0T`$, $`f`$ is 1-concentrated on $`T`$ ($`ϵ`$ is at least 1) and the uncertainty inequality is rendered useless. If $`0T`$, then $`ϵ=0`$ and we take $`\eta =\sqrt{\frac{q|B|}{q}}`$ (it is at least that big). The probability of measuring $`0`$ in the first register is $`\frac{|B|}{q}`$, and the uncertainty principle tells us that the probability of measuring something in $`T\left\{0\right\}`$ is greater than

$$\frac{q}{|B|}\left(1\sqrt{\frac{q|B|}{q}}\right)^2\frac{|B|}{q}.$$
$`2.7`$
The expression in 2.7 is negative!

Nonetheless, the proof of theorem 1.3 is a good model for deriving useful lower bounds. In light of theorem 1.3, and the work of , it turns out that it is fruitful to derive uncertainty principles which relate $`P_T^{^{}}^qR_B^qf_2`$ to $`P_T^pR_B^pf_2`$ for $`q>p`$. We will do just that.

## 3. Motivations: Factoring, The Easy Case

In this section, we will review an easy case of Shor’s factoring algorithm. Factoring an odd integer $`N`$ can be reduced to finding the order (even) of a random integer $`xmodN`$, i.e. finding $`r`$ such that $`x^r1modN`$ where $`r`$ is divisible by 2. Suppose $`N`$ has $`k`$ distinct prime factors, i.e. $`N=p_1^{e_1}\mathrm{}p_k^{e_k}`$, then algorithm is as follows:

Step 1. Choose a random $`xmodN`$. Use the polynomial time Euclidean algorithm to compute gcd$`(x,N)`$. If gcd$`(x,N)1`$, a factor of N is found so assume gcd$`(x,N)=1`$.

Step 2. Find the smallest $`r`$ such that $`x^r1modN`$. This is the ”hard” part of the algorithm.

Step 3. If $`r`$ is odd, go back to step 1. The probability that $`r`$ is odd is $`\left(\frac{1}{2}\right)^k`$.

Step 4. Since $`r`$ is even, $`\left(x^{\frac{r}{2}}1\right)\left(x^{\frac{r}{2}}+1\right)=x^r10modN`$. If $`\left(x^{\frac{r}{2}}+1\right)0modN`$, go back to step 1. The probability that $`\left(x^{\frac{r}{2}}+1\right)0modN`$ is less than $`\left(\frac{1}{2}\right)^{k1}`$.

Step 5. Since $`\left(x^{\frac{r}{2}}+1\right)0modN`$, $`\left(x^{\frac{r}{2}}1\right)`$ and $`N`$ must have a nontrivial common factor. Use the polynomial time Euclidean algorithm to find gcd$`(x^{\frac{r}{2}}1,N)`$. Notice that gcd$`(x^{\frac{r}{2}}1,N)N`$ otherwise $`x^{\frac{r}{2}}1modN`$ contradicting step 2 where $`r`$ is the smallest such number with this property.

The hard part of the above algorithm is in step 2, but Shor  and  showed us how to do that step with a polynomial number of quantum gates. His algorithm relies heavily on the quantum Fourier transform. The quantum Fourier transform is a unitary operator that takes the state $`|a=_{j=0}^{p1}a_j|j`$ to

$$\text{FT}_p|a=\frac{1}{\sqrt{p}}\underset{c=0}{\overset{p1}{}}\left[\underset{j=0}{\overset{p1}{}}a_j\mathrm{exp}\left(2\pi ijc/p\right)\right]|c,$$
$`3.1`$
where $`p=2^l`$ ($`p`$ can be a smooth integer). The quantum Fourier transform can be implemented with a polynomial number of quantum gates, see . We will review Shor’s algorithm for a simple (rather unrealistic) case.

We start with $`|0|0`$ and take the Fourier transform of the first register

$$|0|0\frac{1}{\sqrt{p}}\underset{c=0}{\overset{p1}{}}|c|0.$$
$`3.2`$
Next, we perform the operation

$$\frac{1}{\sqrt{p}}\underset{c=0}{\overset{p1}{}}|c|0\frac{1}{\sqrt{p}}\underset{c=0}{\overset{p1}{}}|c|x^cmodN.$$
$`3.3`$
Here is where we make our unreasonable assumption. Assume that the period $`r`$ exactly divides $`p`$ and write $`p=rt`$. Now we measure the second register and see $`b=x^amodN`$, where a is the smallest positive integer that satisfies the equation. Notice that we have no knowledge of $`a`$. This puts our quantum computer into the state

$$\frac{1}{\sqrt{A+1}}\underset{j=0}{\overset{A}{}}|jr+a|b$$
$`3.4`$
where $`A`$ is the largest integer for which $`Ar+a<p`$. Since $`p=rt`$, $`A=\frac{p}{r}1`$. The above state can be rewritten as

$$\sqrt{\frac{r}{p}}\underset{j=0}{\overset{{\displaystyle \frac{p}{r}}1}{}}|jr+a,$$
$`3.5`$
where the state $`|b`$ has been dropped for notation convenience. Next, apply the quantum Fourier transform:

$`\sqrt{{\displaystyle \frac{r}{p}}}{\displaystyle \underset{j=0}{\overset{{\displaystyle \frac{p}{r}}1}{}}}|jr+a`$ $`{\displaystyle \frac{1}{\sqrt{p}}}{\displaystyle \underset{c=0}{\overset{p1}{}}}\sqrt{{\displaystyle \frac{r}{p}}}{\displaystyle \underset{j=0}{\overset{{\displaystyle \frac{p}{r}}1}{}}}\mathrm{exp}\left(2\pi i(jr+a)c/p\right)|c`$ $`3.6`$
$`={\displaystyle \frac{\sqrt{r}}{p}}{\displaystyle \underset{c=0}{\overset{p1}{}}}\mathrm{exp}\left(2\pi iac/p\right){\displaystyle \underset{j=0}{\overset{{\displaystyle \frac{p}{r}}1}{}}}\mathrm{exp}\left(2\pi ijrc/p\right)|c,`$
Observing that

$$\underset{j=0}{\overset{{\displaystyle \frac{p}{r}}1}{}}\mathrm{exp}\left(2\pi ijrc/p\right)=\{\begin{array}{cc}\frac{p}{r},\hfill & \text{if }c\text{ is a multiple of }\frac{p}{r}\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array},$$
$`3.7`$
eqn. 3.6 is just

$$\frac{1}{\sqrt{r}}\underset{j=0}{\overset{r1}{}}\mathrm{exp}\left(2\pi iaj/r\right)|jp/r=\frac{1}{\sqrt{r}}\underset{j=0}{\overset{r1}{}}\mathrm{exp}\left(2\pi iaj/r\right)|jt.$$
$`3.8`$
Finally, with probability $`\frac{1}{r}`$, we measure the first register and see $`k={\displaystyle \frac{jp}{r}}=jt`$ where $`0jr1`$. Notice that the probability of measuring $`|k|b`$ for any particular $`k`$ and $`b`$ is $`1/r^2`$. This gives us $`{\displaystyle \frac{k}{p}}={\displaystyle \frac{j}{r}}`$ where $`k`$ and $`p`$ are known. If $`j`$ and $`r`$ are relatively prime, we can determine $`r`$. The number of $`j`$’s that are relatively prime to $`r`$ is $`\mathbb{\Phi }\left(r\right)`$. Since there are $`r`$ number of different $`k`$’s and $`b`$’s, the total probability of observing $`|k=jt|b`$ such that $`j`$ is relatively prime to $`r`$ is

$$r^2\frac{\mathbb{\Phi }\left(r\right)}{r}\frac{1}{r^2}=\frac{\mathbb{\Phi }\left(r\right)}{r}>\frac{k}{\mathrm{log}\mathrm{log}r}\frac{k}{\mathrm{log}n}.$$
$`3.9`$
This tells us that for the simple case, with high probability, we can find $`r`$ with a polynomial (with respect to $`n=\mathrm{log}r`$) number of quantum gates. In other words, let

$$T=\left\{k=jt\right|\mathrm{gcd}(j,r)=1,0jr1\}.$$
$`3.10`$
Then we can measure something in $`T`$ with probability at least the inverse of a polynomial in the size of the input.

The above algorithm is not very useful in general. The reason for this is that we assumed $`p=rt`$ and we do not know $`r`$ ($`r`$ is what we seek). We performed two quantum Fourier transforms over $`p`$. In generalizing this easy case to the general case, we must address these two Fourier transforms.

## 4. Quantum Algorithm Uncertainty Principles (QAUP) - version 1

We now derive quantum algorithm uncertainty principles that relate $`P_T^{^{}}^qR_B^qf_2`$ to $`P_T^pR_B^pf_2`$ for $`q>p`$.

###### Proposition 4.1

For all $`x`$, $`|\mathrm{exp}\left(ix\right)1||x|`$.

###### Demonstration Proof

The inequality is certainly true when $`2|x|`$, so we will assume $`2>|x|`$. The expression $`|\mathrm{exp}\left(ix\right)1|`$ is the length of the vector $`(\mathrm{cos}x,\mathrm{sin}x)(1,0)`$ in $`^2`$. The smallest arc-length of the piece of the unit circle that starts at $`(0,1)`$ and ends at $`(\mathrm{cos}x,\mathrm{sin}x)`$ is $`1|x|`$. Since the shortest distance between two points in $`R^2`$ is a straight line, $`|\mathrm{exp}\left(ix\right)1||x|`$ follows.

###### Lemma 4.1

Let $`q>p`$, $`f=|0`$, $`T_p`$, and

$$T^{^{}}=\left\{k^{^{}}_q\right|k^{^{}}=\frac{qk}{p}+ϵ_k,kT,\text{ no restrictions on }ϵ_k\}.$$
$`4.1`$
Let $`\overline{B}`$ be a set and $`B=a+\overline{B}=\left\{a+b\right|b\overline{B}\}`$. Suppose that for all $`kT`$,

$$0\frac{2\pi |ϵ_k|}{q^2}\underset{c\overline{B}}{}|c|\frac{2\pi \delta _{k,\overline{B}}}{q^2}\frac{p}{q}P_k^pR_B^pf_2,$$
$`4.2`$
where $`\delta _{k,\overline{B}}`$ depends on $`k`$ and $`_{c\overline{B}}|c|`$. Then for all $`k^{^{}}T`$,

$`0{\displaystyle \frac{p}{q}}P_k^pR_B^pf_2{\displaystyle \frac{2\pi \delta _{k,\overline{B}}}{q^2}}`$ $`4.3`$
$`{\displaystyle \frac{p}{q}}P_k^pR_B^pf_2{\displaystyle \frac{2\pi |ϵ_k|}{q^2}}{\displaystyle \underset{c\overline{B}}{}}|c|`$
$`P_k^{^{}}^qR_B^qf_2.`$
###### Demonstration Proof

The left most two inequalities in 4.3 comes from 4.2. Notice that the relationship between $`B`$, $`\overline{B}`$, 0.4, and 2.6 imply that

$`P_k^pR_B^pf_2={\displaystyle \frac{1}{p}}\left|{\displaystyle \underset{cB}{}}\mathrm{exp}\left({\displaystyle \frac{2i\pi ck}{p}}\right)\right|={\displaystyle \frac{1}{p}}\left|{\displaystyle \underset{\overline{c}\overline{B}}{}}\mathrm{exp}\left({\displaystyle \frac{2i\pi \overline{c}k}{p}}\right)\right|,`$ $`4.4`$
$`P_k^{^{}}^qR_B^qf_2={\displaystyle \frac{1}{q}}\left|{\displaystyle \underset{cB}{}}\mathrm{exp}\left({\displaystyle \frac{2i\pi ck^{^{}}}{q}}\right)\right|={\displaystyle \frac{1}{q}}\left|{\displaystyle \underset{\overline{c}\overline{B}}{}}\mathrm{exp}\left({\displaystyle \frac{2i\pi \overline{c}k^{^{}}}{q}}\right)\right|,`$
$`prob(k,p,p)={\displaystyle \frac{p}{|B|}}P_k^pR_B^pf_2^2={\displaystyle \frac{1}{p|B|}}\left|{\displaystyle \underset{\overline{c}\overline{B}}{}}\mathrm{exp}\left({\displaystyle \frac{2i\pi \overline{c}k}{p}}\right)\right|^2,`$
$`prob(k^{^{}},p,q)={\displaystyle \frac{q}{|B|}}P_k^{^{}}^qR_B^qf_2^2={\displaystyle \frac{1}{q|B|}}\left|{\displaystyle \underset{\overline{c}\overline{B}}{}}\mathrm{exp}\left({\displaystyle \frac{2i\pi \overline{c}k^{^{}}}{q}}\right)\right|^2,`$
which imply

$`{\displaystyle \frac{p}{q}}P_k^pR_B^pf_2P_k^{^{}}^qR_B^qf_2\left|{\displaystyle \frac{1}{q}}{\displaystyle \underset{\overline{c}\overline{B}}{}}\mathrm{exp}\left({\displaystyle \frac{2i\pi \overline{c}k}{p}}\right){\displaystyle \frac{1}{q}}{\displaystyle \underset{\overline{c}\overline{B}}{}}\mathrm{exp}\left({\displaystyle \frac{2i\pi \overline{c}k^{^{}}}{q}}\right)\right|.`$ $`4.5`$
The expression on the right can be rewritten as

$`{\displaystyle \frac{1}{q}}\left|{\displaystyle \underset{\overline{c}\overline{B}}{}}\mathrm{exp}\left({\displaystyle \frac{2i\pi \overline{c}k}{p}}\right)\left(\mathrm{exp}\left({\displaystyle \frac{2i\pi \overline{c}ϵ_k}{q}}\right)1\right)\right|.`$ $`4.6`$
Using

$$|\mathrm{exp}\left(ix\right)1|<|x|,$$
$`4.7`$
4.6 can be bounded from above by

$`{\displaystyle \frac{1}{q}}{\displaystyle \underset{\overline{c}\overline{B}}{}}\left|\left(\mathrm{exp}\left({\displaystyle \frac{2i\pi \overline{c}ϵ_k}{q}}\right)1\right)\right|{\displaystyle \frac{1}{q}}{\displaystyle \underset{\overline{c}\overline{B}}{}}\left|{\displaystyle \frac{2i\pi \overline{c}ϵ_k}{q}}\right|=`$ $`4.8`$
$`{\displaystyle \frac{2\pi |ϵ_k|}{q^2}}{\displaystyle \underset{\overline{c}\overline{B}}{}}|\overline{c}|{\displaystyle \frac{2\pi \delta _{k,\overline{B}}}{q^2}}.`$
Finally, 4.5, 4.6 and 4.8 imply 4.3 ∎

###### Theorem 4.1 QAUP - version 1

Under the conditions of lemma 4.1,

$$0\frac{p}{q}\left\{\frac{\sqrt{p}}{\sqrt{|B|}}\right||P_k^pR_B^pf||_2\frac{2\pi \delta _{k,\overline{B}}}{q\sqrt{|B|p}}\}^2\frac{q}{|B|}P_k^{^{}}^qR_B^qf_2^2.$$
$`4.9`$
###### Demonstration Proof

Since 4.3 is greater than zero, we can square all terms in 4.3 and keep the inequalities and obtain

$`0`$ $`{\displaystyle \frac{q}{|B|}}\left\{{\displaystyle \frac{\sqrt{p|B|}}{q}}\left({\displaystyle \frac{\sqrt{p}}{\sqrt{|B|}}}P_k^pR_B^pf\right){\displaystyle \frac{2\pi \delta _{k,\overline{B}}}{q^2}}\right\}^2`$ $`4.10`$
$`{\displaystyle \frac{q}{|B|}}P_k^{^{}}^qR_B^qf^2.`$
The middle term in 4.10 is

$$\frac{p}{q}\left\{\frac{\sqrt{p}}{\sqrt{|B|}}\right||P_k^pR_B^pf||_2\frac{2\pi \delta _{k,\overline{B}}}{q\sqrt{|B|p}}\}^2.\mathit{}$$
$`4.11`$
###### Corollary 4.1 QAUP - version 1.a

Under the conditions of lemma 4.1, let

$$T^{^{}}=\left\{k^{^{}}_q\right|k^{^{}}=\frac{qk}{p},kT\},$$
$`4.12`$
or

$$T^{^{}}=\{k^{^{}}_q|k^{^{}}=\frac{qk}{p},kT\},$$
$`4.13`$
or

$$T^{^{}}=\left\{k^{^{}}_q\right|k^{^{}}=\frac{qk}{p},kT\}.$$
$`4.14`$
Suppose,

$$\underset{\overline{c}\overline{B}}{}|\overline{c}|\delta _{\overline{B}},$$
$`4.15`$
then

$$0\frac{p}{q}\left\{\frac{\sqrt{p}}{\sqrt{|B|}}\right||P_k^pR_B^pf||_2\frac{2\pi \delta _{\overline{B}}}{q\sqrt{|B|p}}\}^2\frac{q}{|B|}P_k^{^{}}^qR_B^qf_2^2.$$
$`4.16`$
###### Demonstration Proof

This is an application of $`|ϵ_k|<1`$ in 4.2 to 4.9. ∎

###### Remark Remark 4.1

Summing over all $`k^{^{}}T`$ and $`kT`$ in 4.16, 4.9 or 4.3 gives inequalities of the form 0.13.

## 5. Application to Factoring, QAUP - version 1

We will now show how corollary 4.1 can be applied to factoring. Recall that for easy factoring, $`prob(k,p,p)=\frac{1}{r}`$ for any $`k`$ in 3.10.

Let $`T`$ be as given in 3.10 and $`T^{^{}}`$ be as given in 4.12. From section 3, we have $`B=\{a,a+r,\mathrm{},a+\left(t1\right)r\}`$ which implies $`|B|=t`$ and $`\overline{B}=\{0,r,2r,\mathrm{},\left(t1\right)r\}`$. Let us take $`p=rt2r^2`$ (i.e. $`t2r`$), $`q=sp=2^l>p`$ for some $`s`$ such that

$$0<1\frac{\pi }{s}.$$
$`5.1`$
The sum $`_{\overline{c}\overline{B}}\overline{c}`$ can be evaluated in closed form, but it is more convenient to bound it from above by an integral and obtain

$$\underset{\overline{c}\overline{B}}{}\overline{c}<r\frac{t^2}{2}=\delta _B.$$
$`5.2`$
With 5.2, 4.4, and our choice of $`p`$ and $`q`$,

$$\frac{2\pi \delta _B}{q^2}=\frac{2\pi }{s^2r^2t^2}\frac{rt^2}{2}=\frac{\pi }{s^2r},$$
$`5.3`$
and

$$\frac{p}{q}P_k^pR_B^pf_2=\frac{p}{q}\sqrt{\frac{|B|}{p}}\sqrt{prob(k,p,p)}=\frac{1}{s}\sqrt{\frac{t}{rt}}\frac{1}{\sqrt{r}}=\frac{1}{sr}.$$
$`5.4`$
The expressions in 5.1, 5.3 and 5.4 imply that 4.2 is satisfied.

We now proceed to evaluate 4.16 giving

$$\frac{1}{s}\left\{\frac{1}{\sqrt{r}}\frac{2\pi }{srt\sqrt{t}\sqrt{rt}}\frac{rt^2}{2}\right\}^2=\frac{1}{sr}\left(1\frac{\pi }{s}\right)^2<prob(k^{^{}},p,q).$$
$`5.5`$
Finally, we arrive at the desired result. From 4.16 and 5.5, we have

$$prob(T^{^{}},p,q)=\underset{k^{^{}}T^{^{}}}{}\frac{q}{|B|}P_k^{^{}}^qR_B^qf_2^2>\underset{kT}{}\frac{1}{sr}\left(1\frac{\pi }{s}\right)^2=\left(1\frac{\pi }{s}\right)^2\frac{\mathrm{\Phi }\left(r\right)}{r},$$
$`5.6`$
and if $`s`$ is reasonable, we obtain

$$prob(T^{^{}},p,q)>\frac{1}{poly\left(\mathrm{log}r\right)}.$$
$`5.7`$
To complete this half of generalizing the two quantum Fourier tranforms over $`p`$, suppose we measure $`k^{^{}}=\frac{qk}{p}`$. Then

$$\left|k^{^{}}\frac{qk}{p}\right|<1$$
$`5.8`$
implies

$$\left|\frac{k^{^{}}}{q}\frac{jt}{rt}\right|=\left|\frac{k^{^{}}}{q}\frac{j}{r}\right|<\frac{1}{q}<\frac{1}{2sr^2}<\frac{1}{2r^2}$$
$`5.9`$
and we can use continued fraction to find $`r`$ since gcd$`(j,r)=1`$.

### 5a

We now deal with the second quantum Fourier transform over $`p`$. The technique used here is from . This generalization can be extracted to a more general uncertainty principle but we will not do it here because the notation is quite cumbersome.

We assume we have an $`r^{^{}}`$ such that $`2r<r^{^{}}<4r`$. This can be achieved by repeating the experiment and taking $`r^{^{}}=2+1,4+1,8+1,\mathrm{}`$ Doing this will require the experiment to be repeated at most on the order of $`\mathrm{log}N`$ number of times, which is polynomial. Let $`p^{^{}}=2^l`$ be such that

$$4r^2<\left(r^{^{}}\right)^2<p^{^{}}<2\left(r^{^{}}\right)^2<32r^2,$$
$`5.10`$
and $`p`$ be such that

$$4r^2p=rtp^{^{}}<r\left(t+1\right)<33r^2.$$
$`5.11`$
The choice of $`p`$ will allow continued fraction expansion to recover $`r`$ and the choice of $`p^{^{}}`$ will allow the quantum Fourier transform to be applied over a smooth number. Let

$`B=\left\{j\right|b=x^jmodN,0jp^{^{}}1\},`$ $`5.12`$
$`a=\mathrm{min}\left\{cB\right\}.`$
Since $`p=rtp^{^{}}<r\left(t+1\right)`$, either

$$B=\{a,a+r,\mathrm{},a+\left(t1\right)r\},$$
$`5.13`$
or

$$B=\{a,a+r,\mathrm{},a+tr\}.$$
$`5.14`$
Instead of applying the quantum Fourier transform over $`p`$ as in 3.2, we apply it over $`p^{^{}}`$ and the algorithm becomes

$$\sqrt{\frac{1}{|B|}}\underset{jB}{}|j\frac{1}{\sqrt{q|B|}}\underset{c=0}{\overset{q1}{}}\underset{jB}{}\mathrm{exp}\left(2\pi ijc/q\right)|c.$$
$`5.15`$
With 5.15, the probability of measuring $`k^{^{}}`$ is either

$$prob(k^{^{}},p^{^{}},q)=\frac{1}{qt}\left|\underset{j=0}{\overset{t1}{}}\mathrm{exp}\left(2\pi ijrk^{^{}}/q\right)\right|^2,$$
$`5.16`$
or

$$prob(k^{^{}},p^{^{}},q)=\frac{1}{q\left(t+1\right)}\left|\underset{j=0}{\overset{t}{}}\mathrm{exp}\left(2\pi ijrk^{^{}}/q\right)\right|^2,$$
$`5.17`$
depending on whether $`B`$ is of the form 5.13 or 5.14, respectively. If we get 5.16, then nothing has changed by appling the quantum Fourier transform over $`p^{^{}}`$ and the result will be the same as that of 5.6, i.e.

$$prob(k^{^{}},p^{^{}},q)=prob(k^{^{}},p,q)>\left(1\frac{\pi }{s}\right)^2\frac{\mathrm{\Phi }\left(r\right)}{r}.$$
$`5.18`$
We now consider the case of 5.17. For notation convenience, let

$`a={\displaystyle \underset{j=0}{\overset{t1}{}}}\mathrm{exp}\left(2\pi ijrk^{^{}}/q\right),`$ $`5.19`$
$`b=\mathrm{exp}\left(2\pi itrk^{^{}}/q\right).`$
Notice that

$$\frac{1}{\sqrt{sr}}\left(1\frac{\pi }{s}\right)<\sqrt{prob(k^{^{}},p,q)}=\frac{1}{\sqrt{qt}}|a|=\sqrt{\frac{r}{qp}}|a|.$$
$`5.20`$
We will choose $`s`$ so that

$$0<1\frac{1}{2\left(1{\displaystyle \frac{\pi }{s}}\right)}<1\frac{1}{2t\left(1{\displaystyle \frac{\pi }{s}}\right)}$$
$`5.21`$
is satisfied as well as 5.1. With our notations we have

$`|a+b|=|a|\left|1+{\displaystyle \frac{b}{a}}\right||a|\left|1{\displaystyle \frac{|b|}{|a|}}\right|=|a|\left|1{\displaystyle \frac{1}{|a|}}\right|=`$ $`5.22`$
$`|a|\left|1\sqrt{{\displaystyle \frac{r}{qp}}}{\displaystyle \frac{1}{\sqrt{prob(k^{^{}},p,q)}}}\right|.`$
The expressions in 5.20 and 5.21 tell us that

$`1\sqrt{{\displaystyle \frac{r}{qp}}}{\displaystyle \frac{1}{\sqrt{prob(k^{^{}},p,q)}}}>1\sqrt{{\displaystyle \frac{r}{qp}}}{\displaystyle \frac{\sqrt{s}\sqrt{r}}{\left(1{\displaystyle \frac{\pi }{s}}\right)}}>`$ $`5.23`$
$`1\left({\displaystyle \frac{\sqrt{s}r}{\sqrt{s}rt}}\right){\displaystyle \frac{1}{\left(1{\displaystyle \frac{\pi }{s}}\right)}}=1{\displaystyle \frac{1}{2t}}{\displaystyle \frac{1}{\left(1{\displaystyle \frac{\pi }{s}}\right)}}>0,`$
and this implies that

$$|a+b||a|\left(1\frac{s}{2t\left(s\pi \right)}\right).$$
$`5.24`$
For the expression in 5.17, we have

$`prob(k^{^{}},p^{^{}},q)={\displaystyle \frac{1}{q\left(t+1\right)}}|a+b|{\displaystyle \frac{t}{qt\left(t+1\right)}}|a|^2\left(1{\displaystyle \frac{s}{2t\left(s\pi \right)}}\right)^2=`$ $`5.25`$
$`{\displaystyle \frac{t}{\left(t+1\right)}}prob(k^{^{}},p,q)\left(1{\displaystyle \frac{s}{2t\left(s\pi \right)}}\right)^2>`$
$`{\displaystyle \frac{t}{\left(t+1\right)}}{\displaystyle \frac{1}{sr}}\left(1{\displaystyle \frac{\pi }{s}}\right)^2\left(1{\displaystyle \frac{s}{2t\left(s\pi \right)}}\right)^2.`$
(Notice that 5.25 is an opportunity for QAUP, but we will not pursue it here.) Since $`4r^2p=rt<32r^2`$, we have $`4rt<32r`$. Using this to bound 5.25, we obtain

$$prob(k^{^{}},p^{^{}},q)>\frac{4}{33rs}\left(1\frac{\pi }{s}\right)^2\left(1\frac{s}{2t\left(s\pi \right)}\right)^2.$$
$`5.26`$
Finally, summing over all $`k^{^{}}T^{^{}}`$ (for either 5.16 or 5.17) yields

$`prob(T^{^{}},p^{^{}},q)>{\displaystyle \underset{k^{^{}}T^{^{}}}{}}{\displaystyle \frac{4}{33rs}}\left(1{\displaystyle \frac{\pi }{s}}\right)^2\left(1{\displaystyle \frac{s}{2t\left(s\pi \right)}}\right)^2=`$ $`5.27`$
$`{\displaystyle \frac{4\mathrm{\Phi }\left(r\right)}{33rs}}\left(1{\displaystyle \frac{\pi }{s}}\right)^2\left(1{\displaystyle \frac{s}{2t\left(s\pi \right)}}\right)^2>{\displaystyle \frac{1}{poly\left(\mathrm{log}r\right)}}.`$
To recover $`r`$, we proceed as in 5.8 and 5.9.

## 6. Motivation: Discrete Log, The Easy Case

Mimicking section 3 of factoring, we study the easy case of the discrete log problem. Given $`x,g`$ and $`p`$, the discrete log problem is to find the least $`r`$ such that $`g^rxmodp`$.

The quantum algorithm is as follows. Prepare the superposition

$$\frac{1}{p1}\underset{a=0}{\overset{p2}{}}\underset{b=0}{\overset{p2}{}}|a,b,0.$$
$`6.1`$
Compute in the third register $`g^ax^b`$

$$\frac{1}{p1}\underset{a=0}{\overset{p2}{}}\underset{b=0}{\overset{p2}{}}|a,b,g^ax^b.$$
$`6.2`$
Measure the third register $`y=g^k=g^ax^b=g^{arb}`$. The number of pairs $`(a,b)`$ such that $`arbkmod\left(p1\right)`$ is $`p1`$ since there are $`p1`$ different values of $`b`$ to choose from and that exhausts all the solution pairs. Let

$$B=\left\{(a,b)_{p1}\times _{p1}\right|arbkmod\left(p1\right)\},$$
$`6.3`$
then the state of the machine will be

$$\frac{1}{\sqrt{p1}}\underset{(a,b)B}{}|a,b,$$
$`6.4`$
where the third register is suppressed. Now apply the quantum Fourier transform over $`_p`$ on the first two registers and obtain

$$\frac{1}{\left(p1\right)^{\frac{3}{2}}}\underset{c=0}{\overset{p2}{}}\underset{d=0}{\overset{p2}{}}\underset{(a,b)B}{}\mathrm{exp}\left[2\pi i\left(ac+bd\right)/\left(p1\right)\right]|c,d.$$
$`6.5`$
Finally, measure the first and second register and obtain $`|c,d`$ with probability

$$\left|\frac{1}{\left(p1\right)^{\frac{3}{2}}}\underset{a,b,arbk}{}\mathrm{exp}\left[2\pi i\left(ac+bd\right)/\left(p1\right)\right]\right|^2.$$
$`6.6`$
Substituting $`ak+rbmod\left(p1\right)`$ gives

$$\left|\frac{1}{\left(p1\right)^{\frac{3}{2}}}\underset{b=0}{\overset{p2}{}}\mathrm{exp}\left[2\pi i\left(kc+b\left(d+rc\right)\right)/\left(p1\right)\right]\right|^2.$$
$`6.7`$
Notice that the sum is

$$\{\begin{array}{cc}0,\hfill & \text{if }d+rc0mod\left(p1\right)\hfill \\ \left(p1\right)\mathrm{exp}2\pi ikc/\left(p1\right),\hfill & \text{if }drc.\hfill \end{array}$$
$`6.8`$
Hence, with probability $`1/\left(p1\right)`$ we will measure $`cmod\left(p1\right)`$ and $`drc`$. If $`c`$ and $`p1`$ are relatively prime, we can find $`r`$. Thus, we are interested in the set

$$T=\left\{(c,d)_{p1}\times _{p1}\right|drcmod\left(p1\right),gcd(c,p1)=1\},$$
$`6.9`$
and the probability of measuring something in $`T`$ is

$$\frac{\mathrm{\Phi }\left(p1\right)}{p1}>\frac{1}{\mathrm{log}\mathrm{log}p}.$$
$`6.10`$
## 7. QAUP - version 2, Multi-Dimensional

Motivated by the discrete log problem, we will derive multi-dimensional quantum algorithm uncertainty principles. The quantum algorithms that we are interested in are of the following form. Start with $`n+1`$ registers all set to $`0`$: $`|0,0,\mathrm{},0|0`$. For each of the first $`n`$ registers, apply the quantum Fourier transform over $`_{p_j1}`$ and obtain

$$\underset{j=1}{\overset{n}{}}\frac{1}{\sqrt{p_j1}}\underset{a_1,\mathrm{},a_n}{}|a_1,\mathrm{},a_n|0.$$
$`7.1`$
Next, compute

$$\underset{j=1}{\overset{n}{}}\frac{1}{\sqrt{p_j1}}\underset{a_k,\mathrm{},a_k}{}|a_k,\mathrm{},a_k|f(a_k,\mathrm{},a_k),$$
$`7.2`$
and then measure the $`n+1`$ register. The computer will go into the state

$$\frac{1}{\sqrt{|B|}}\underset{|a_1,\mathrm{},a_nB}{}|a_1,\mathrm{},a_n,$$
$`7.3`$
where the $`n+1`$ register is suppressed. Next, zero-pad $`p_j1`$ up to $`q_j`$ for $`q_jp_j1`$ and then apply the quantum Fourier transform again and obtain

$`{\displaystyle \frac{1}{\sqrt{|B|}}}\left({\displaystyle \underset{j=1}{\overset{n}{}}}{\displaystyle \frac{1}{\sqrt{q_j}}}\right)`$ $`{\displaystyle \underset{b_1,\mathrm{},b_n}{}}\{`$ $`7.4`$
$`{\displaystyle \underset{(a_1,\mathrm{},a_n)B}{}}{\displaystyle \underset{l=1}{\overset{n}{}}}\mathrm{exp}\left({\displaystyle \frac{2\pi ia_lb_l}{q_l}}\right)\}|b_1,\mathrm{},b_n.`$
Finally, measure the rest of the registers and we would like to have some sense of the probability of measuring something in a particular set $`T`$.

Let $`f=_{j=1}^n|0`$, then the probability of measuring something in $`T`$ is given by

$$\frac{1}{|B|}P_T^qR_B^qf_2^2\underset{j=1}{\overset{n}{}}q_j,$$
$`7.5`$
where $`P_T^q`$ and $`R_B^q`$ are the multidimensional time and band-limiting operators respectively. Notice that for any $`kT`$, the probability of measuring $`k`$ is given by

$$\frac{1}{|B|}\left(\underset{j=1}{\overset{n}{}}\frac{1}{q_j}\right)\left|\underset{(a_1,\mathrm{},a_m)B}{}\underset{l=1}{\overset{n}{}}\mathrm{exp}\left(\frac{2\pi ia_lk_l}{q_l}\right)\right|^2.$$
$`7.6`$
###### Lemma 7.1

Let $`q_jp_j1,1jn`$, $`T_{p_11}\mathrm{}_{p_n1}`$,

$$T^{^{}}=\{k^{^{}}=(k_1^{^{}},\mathrm{},k_n^{^{}})_{j=1}^n_{q_j}|k_j^{^{}}=\frac{\left(q_j\right)k_j}{\left(p_j1\right)}+ϵ_j,(k_1,\mathrm{},k_n)T\},$$
$`7.7`$
$`\overline{p}={\displaystyle \underset{j=1}{\overset{n}{}}}\left(p_j1\right),`$
$`\overline{q}={\displaystyle \underset{j=1}{\overset{n}{}}}q_j,`$
and $`k^{^{}}T^{^{}}`$ which corresponds to $`kT`$. Suppose

$$0\frac{2\pi }{\overline{q}}\underset{|a_1,\mathrm{},a_nB}{}\left|\underset{l=1}{\overset{n}{}}\frac{a_lϵ_l}{q_l}\right|\frac{2\pi \delta _{k,B}}{\overline{q}}\frac{\overline{p}}{\overline{q}}P_k^pR_B^pf_2,$$
$`7.8`$
then

$`0`$ $`{\displaystyle \frac{\overline{p}}{\overline{q}}}P_k^pR_B^pf_2{\displaystyle \frac{2\pi \delta _{k,B}}{\overline{q}}}P_k^{^{}}^qR_B^qf_2.`$ $`7.9`$
###### Demonstration Proof

The proof is similar to that of lemma 4.1.

$`{\displaystyle \frac{\overline{p}}{\overline{q}}}P_k^pR_B^pf_2P_k^{^{}}^qR_B^qf_2`$ $`7.10`$
$`{\displaystyle \frac{1}{\overline{q}}}\left|{\displaystyle \underset{|a_1,\mathrm{},a_nB}{}}{\displaystyle \underset{l=1}{\overset{n}{}}}\mathrm{exp}\left({\displaystyle \frac{2\pi ia_lk_l}{p_l1}}\right){\displaystyle \underset{l=1}{\overset{n}{}}}\mathrm{exp}\left({\displaystyle \frac{2\pi ia_lk_l^{^{}}}{q_l}}\right)\right|.`$
The right-hand-side of inequality 7.10 can be written as

$`{\displaystyle \frac{1}{\overline{q}}}\left|{\displaystyle \underset{|a_1,\mathrm{},a_nB}{}}\left[{\displaystyle \underset{l=1}{\overset{n}{}}}\mathrm{exp}\left({\displaystyle \frac{2\pi ia_lk_l}{p_l1}}\right)\right]\left[{\displaystyle \underset{l=1}{\overset{n}{}}}\mathrm{exp}\left({\displaystyle \frac{2\pi ia_lϵ_l}{q_l}}\right)1\right]\right|.`$ $`7.11`$
Using

$$|\mathrm{exp}\left(ix\right)1||x|,$$
$`7.12`$
7.11 is bounded from above by

$`{\displaystyle \frac{1}{\overline{q}}}{\displaystyle \underset{|a_1,\mathrm{},a_nB}{}}\left|\left[{\displaystyle \underset{l=1}{\overset{n}{}}}\mathrm{exp}\left({\displaystyle \frac{2\pi ia_lϵ_l}{q_l}}\right)1\right]\right|`$ $`7.13`$
$`{\displaystyle \frac{2\pi }{\overline{q}}}{\displaystyle \underset{|a_1,\mathrm{},a_nB}{}}\left|{\displaystyle \underset{l=1}{\overset{n}{}}}{\displaystyle \frac{a_lϵ_l}{q_l}}\right|{\displaystyle \frac{2\pi \delta _{k,B,}}{\overline{q}}}.`$
The expressions in 7.10, 7.11, and 7.13 imply

$`{\displaystyle \frac{\overline{p}}{\overline{q}}}P_k^pR_B^pf_2{\displaystyle \frac{2\pi \delta _{k,B}}{\overline{q}}}P_k^{^{}}^qR_B^qf_2.\mathit{}`$ $`7.14`$
###### Theorem 7.1 QAUP - version 2

Under the conditions of lemma 7.1,

$`0`$ $`{\displaystyle \frac{\overline{p}}{\overline{q}}}\left({\displaystyle \frac{\sqrt{\overline{p}}}{\sqrt{|B|}}}P_k^pR_B^pf_2{\displaystyle \frac{2\pi \delta _{k,B}}{\sqrt{|B|\overline{p}}}}\right)^2{\displaystyle \frac{\overline{q}}{|B|}}P_k^{^{}}^qR_B^qf_2^2.`$ $`7.15`$
###### Demonstration Proof

Similar to theorem 4.1. ∎

## 8. Application to Discrete Log, QAUP-version 2.

We will apply QAUP-version 2 to the discrete log algorithm. Instead of applying the quantum Fourier transforms over $`p`$ as given in 6.5, we will apply it over $`q=2^l`$. This is natural since the dimension of the Hilbert space in qubit quantum computing is a power of two. We take $`n=2`$, $`p_11=p_21=p1`$, $`|B|=p1`$ and

$$\frac{\sqrt{\overline{p}}}{\sqrt{|B|}}P_k^pR_B^pf_2=\frac{1}{\sqrt{p1}},$$
$`8.1`$
where 8.1 comes from 6.7 and 6.8. Let

$$q_1=q_2=q=2^l=s\left(p1\right)>\left(p1\right),$$
$`8.2`$
where $`s`$ satisfies

$$0<1\frac{3\pi }{s},$$
$`8.3`$
and let

$$T^{^{}}=\left\{(\frac{\left(q\right)k_1}{p1},\frac{\left(q\right)k_2}{p1})\right|(k_1,k_2)T\},$$
$`8.4`$
where $`T`$ is given by 6.9. With this choice of $`T`$ and $`T^{^{}}`$, we have $`|ϵ_1|,|ϵ_2|<1`$. To satisfy 7.9, we have

$$\underset{|a_0,a_1B}{}\left|\underset{l=0}{\overset{1}{}}\frac{a_lϵ_l}{q_l}\right|=\frac{1}{q}\underset{a,b,arbk}{}|aϵ_1+bϵ_2|\frac{1}{q}\underset{a,b,arbk}{}a+b.$$
$`8.5`$
Since $`a\left(k+rb\right)mod\left(p1\right)`$, $`a`$ satisfies $`a<p1`$ and we can use it to bound the last sum as follows

$`{\displaystyle \underset{a,b,arbk}{}}a+b<{\displaystyle \underset{b=0}{\overset{p2}{}}}p1+b=\left(p1\right)^2+{\displaystyle \underset{b=0}{\overset{p2}{}}}b<`$ $`8.6`$
$`\left(p1\right)^2+{\displaystyle \frac{\left(p1\right)^2}{2}}={\displaystyle \frac{3\left(p1\right)^2}{2}}={\displaystyle \frac{3\overline{p}}{2}}.`$
This gives

$$\frac{2\pi \delta _{k,B}}{\overline{q}}=\frac{3\pi \overline{p}}{q\overline{q}}=\frac{3\pi }{s^3\left(p1\right)}.$$
$`8.7`$
Further,

$`{\displaystyle \frac{\overline{p}}{\overline{q}}}P_k^pR_B^pf_2={\displaystyle \frac{1}{s^2}}{\displaystyle \frac{\sqrt{p1}}{p1}}{\displaystyle \frac{p1}{\sqrt{p1}}}P_k^pR_B^pf_2=`$ $`8.8`$
$`{\displaystyle \frac{1}{s^2}}{\displaystyle \frac{\sqrt{p1}}{p1}}{\displaystyle \frac{1}{\sqrt{p1}}}={\displaystyle \frac{1}{s^2\left(p1\right)}}.`$
The expressions in 8.3, 8.7 and 8.8 imply that 7.8 is satisfied.

We now proceed to evaluate 7.15. We have

$`{\displaystyle \frac{1}{s^2}}\left({\displaystyle \frac{1}{\sqrt{p1}}}{\displaystyle \frac{2\pi }{\sqrt{\left(p1\right)^3}}}{\displaystyle \frac{3\left(p1\right)^2}{2s\left(p1\right)}}\right)^2=`$ $`8.9`$
$`{\displaystyle \frac{1}{s^2\left(p1\right)}}\left(1{\displaystyle \frac{3\pi }{s}}\right)^2<{\displaystyle \frac{\overline{q}}{|B|}}||P_k^{^{}}^qR_B^qf||_2^2.`$
Finally, summing over all $`k^{^{}}T^{^{}}`$ yields

$$\underset{k^{^{}}T^{^{}}}{}\frac{\overline{q}}{|B|}P_k^{^{}}^qR_B^qf_2^2>\frac{\mathrm{\Phi }\left(p1\right)}{s^2\left(p1\right)}\left(1\frac{3\pi }{s}\right)^2,$$
$`8.10`$
and this tells us that if $`s`$ is reasonable, then the probability of measuring an element in $`T^{^{}}`$ is at least the inverse of a polynomial in $`\mathrm{log}p`$.

To finish the algorithm, we need to recover $`r`$. Since we know $`q`$ and $`p1`$, we can check if our measurement on the first and second register is of the form

$$(c^{^{}},d^{^{}})=(\frac{qc}{p1},\frac{qd}{p1}),$$
$`8.11`$
for some $`(c,d)`$ (not necessarily in $`T`$). We can actually find $`c`$ and $`d`$ if it is of this form. If $`(c,d)T`$, we can recover $`r`$ and the probability of this happening is at least inverse polynomial.


format: text

text:
# TRINLAT-02/01 Supersymmetry on the lattice

## 1 INTRODUCTION

Supersymmetry or fermion-boson symmetry is one of the most fascinating topics in field theory. Even if has not yet been observed in Nature, thousands of papers have been written on this subject. Its validity in particle physics follows from the common belief in unification through the feasibility of incorporating quantum gravity. From a theoretical point of view, non-perturbative studies of supersymmetric (SUSY) gauge theories turn out to have remarkably rich properties which are of great physical interest, as have been shown in . For this reason, much effort has been dedicated to formulating a lattice version of SUSY theories (for a recent review of SUSY Yang-Mills (SYM) theories, using Wilson fermions, see ). The lattice formulation has been succesful to extract non-perturbative dynamics in field theory, specially in QCD, and may be able to provide additional information and confirm the existing analytical calculations. Whether superymmetry is or not an exact symmetry is a question that must be settle by going beyond perturbation theory.

### 1.1 SYM theory in the continuum

In the continuum, the action for the $`N=1`$ SYM theory with an $`SU(N_c)`$ gauge group is

$$=\frac{1}{4}F_{\mu \nu }^a(x)F_{\mu \nu }^a(x)+\frac{1}{2}\overline{\lambda }^a(x)\gamma _\mu 𝒟_\mu \lambda (x)^a,$$
(1)
where $`\lambda ^a`$ is a 4-component Majorana spinor and satisfies the Majorana condition $`\overline{\lambda }^a=\lambda _{}^{a}{}_{}{}^{T}C`$. The gluon fields are represented by $`A_\mu =igA_\mu ^aT^a`$ and $`F_{\mu \nu }=igF_{\mu \nu }^aT^a`$. $`𝒟_\mu \lambda ^a=_\mu \lambda ^a+gf_{abc}A_\mu ^b\lambda ^c`$ is the covariant derivative in the adjoint representation. The continuum SUSY transformations read

$`\delta A_\mu (x)=2g\overline{\lambda }(x)\gamma _\mu \epsilon ,`$ (2)
$`\delta \lambda (x)={\displaystyle \frac{i}{g}}\sigma _{\rho \tau }F_{\rho \tau }(x)\epsilon ,\delta \overline{\lambda }(x)={\displaystyle \frac{i}{g}}\overline{\epsilon }\sigma _{\rho \tau }F_{\rho \tau }(x),`$
where $`\sigma _{\rho \tau }=\frac{i}{2}[\gamma _\rho ,\gamma _\tau ]`$, $`\lambda =\lambda ^aT^a`$ and $`\epsilon `$ is a global Grassmann parameter with Majorana properties. These transformations relate fermions and bosons, leave the action invariant and commute with the gauge transformations so that the resulting Noether current $`S_\mu (x)`$ is gauge invariant. For $`N=1`$ SYM theory the supercurrent is given by

$$S_\mu (x)=F_{\rho \tau }^a(x)\sigma _{\rho \tau }\gamma _\mu \lambda ^a(x).$$
(3)
Classically, the Noether current is conserved, $`_\mu S_\mu (x)=0`$, provided the fields satisfy the equations of motion. Furthermore one finds that it fullfills a spin $`3/2`$ constraint: $`\gamma _\mu S_\mu (x)=0`$.

### 1.2 Superfields

Supersymmetry in Eq. (1) can be better understood in the language of superfields . In the Wess-Zumino gauge, the action for the $`N=1`$ SYM theory is

$$S_{SYM}=\text{Re}\left\{d^4xd^2\theta \text{Tr}[W^\alpha W_\alpha ]\right\}.$$
(4)
$`W(x,\theta ,\overline{\theta })_\alpha =\frac{1}{8}(\overline{D}\overline{D})e^{2V}D_\alpha e^{2V}`$ is the spinorial field strength superfield which depends on the four coordinates $`x`$ and the anticommuting Weyl spinor variables $`\theta _\alpha `$, $`\overline{\theta }_{\dot{\alpha }}`$ $`(\alpha ,\dot{\alpha }=1,2)`$. $`\overline{D}_{\dot{\alpha }}`$ and $`D_\alpha `$ are the superspace derivatives while $`V=V(x,\theta ,\overline{\theta })`$ is the vector superfield which takes the form

$`V`$ $`=`$ $`\theta \sigma ^\mu \overline{\theta }A_\mu (x)+i(\theta \theta )\overline{\theta }\overline{\psi }_w(x)`$ (5)
$`i(\overline{\theta }\overline{\theta })\theta \psi _w(x)+{\displaystyle \frac{1}{2}}(\theta \theta )(\overline{\theta }\overline{\theta })D(x).`$
The particle content can be identified as one bosonic vector field $`A_\mu =igA_\mu ^aT^a`$, its SUSY partner, a complex Weyl spinor field $`\psi _w=T^a\psi _w^a`$, and an auxiliary scalar field $`D`$. The action can be expressed in terms of these components as

$`S_{SYM}={\displaystyle }d^4x\{{\displaystyle \frac{i}{4}}F_{\mu \nu }^aF^{\mu \nu a}+{\displaystyle \frac{1}{2}}i\psi _w^a\sigma ^\mu (𝒟_\mu \overline{\psi }_w)^a`$
$`{\displaystyle \frac{1}{2}}i(𝒟_\mu \overline{\psi }_w)^a\overline{\sigma }^\mu \psi _w^a+{\displaystyle \frac{1}{2}}D^2\}.`$ (6)
In the on-shell case, the auxiliary scalar field $`D`$ is eliminated by the equation of motion $`D=0`$. Introducing one massless Majorana fermion, the gluino, in the adjoint representation $`\lambda =((\psi _w)_\alpha ,(\overline{\psi }_w)^{\dot{\alpha }})`$, and going to the Euclidean space, we recover Eq. (1).

### 1.3 SUSY Ward Identities (WIs)

The existence of a renormalized SUSY Ward-type identity

$$_\mu S_\mu ^R(x)=2m_R\chi _R(x),$$
(7)
is generally assumed. It is obtained by performing a variation of the functional integral with respect to a local, smooth transformation, $`\epsilon =\epsilon (x)`$, and then putting the sources to zero. $`S_\mu ^R`$ is the renormalized supercurrent and $`\chi _R=Z_\chi \chi `$, with $`\chi \frac{1}{2}F_{\mu \nu }^a\sigma _{\mu \nu }\lambda ^a`$. $`m_R`$ is the renormalized gluino mass. For $`m_R=0`$ we have supersymmetry while a non-vanishing value of $`m_R`$ breaks supersymmetry softly.

### 1.4 Non-perturbative effects of the SYM dynamics

Because of asymptotic freedom and the corresponding infrared instability, it is reasonable to guess that, as in conventional QCD, there are many non-perturbative phenomena that occur in this theory. For the $`N=1`$ SYM theory we may expect confinement and spontaneous chiral symmetry breaking. The discrete chiral symmetry is expected to be broken by a non-zero gluino condensate while the confinement is realized by colorless bound states described by the effective action belonging to chiral supermultiplets.

It is generally assumed that supersymmetry is not anomalous (Eq. (7) holds) and only the mass term is responsible for a soft breaking. However, in  the question of whether non-perturbative effects may cause a supersymmetry anomaly has been raised. Only a study of the continuum limit of the lattice SUSY WIs can shed light on this question.

### 1.5 Chiral symmetry breaking

Introducing a non-zero gluino mass term in Eq. (1), $`_{mass}=m_{\stackrel{~}{g}}\overline{\lambda }^a\lambda ^a`$, breaks supersymmetry softly (which implies that the non-renormalization theorem and cancellation of divergencies are preserved ). In the massless case, the global chiral symmetry is $`U(1)_\lambda `$:

$$\lambda e^{i\phi \gamma _5}\lambda ,\overline{\lambda }\overline{\lambda }e^{i\phi \gamma _5},$$
(8)
which is anomalous. This implies that the divergence of the axial current, $`J_\mu ^5=\overline{\lambda }\gamma _5\lambda `$, is

$$_\mu J_\mu ^5=\frac{N_cg^2}{32\pi ^2}\epsilon ^{\mu \nu \rho \sigma }F_{\mu \nu }^aF_{\rho \sigma }^a.$$
(9)
The anomaly leaves a $`Z_{2N_c}`$ subgroup of $`U(1)_\lambda `$ unbroken. Eq. (8) is equivalent to $`m_{\stackrel{~}{g}}m_{\stackrel{~}{g}}e^{2i\phi \gamma _5}`$ and $`\mathrm{\Theta }_{SYM}\mathrm{\Theta }_{SYM}2N_c\phi `$.

In the SUSY case, $`m_{\stackrel{~}{g}}=0`$, the $`U(1)_\lambda `$ symmetry is unbroken if $`\phi \frac{k\pi }{N_c}`$ for $`(k=0,1,\mathrm{},2N_c1)`$. $`Z_{2N_c}`$ is expected to be spontaneously broken to $`Z_2`$ by a value of $`<\overline{\lambda }\lambda >0`$ . The consequence of this spontaneous chiral symmetry breaking is the existence of a first order phase transition at $`m_{\stackrel{~}{g}}=0`$. That means the existence of $`N_c`$ degenerate ground states with different orientations of the gluino condensate $`(k=0,\mathrm{},N_c1)`$,

$$<\overline{\lambda }\lambda >=c\mathrm{\Lambda }^3e^{\frac{2\pi ik}{N_c}},$$
(10)
where $`\mathrm{\Lambda }`$ is the dynamical scale of the theory which can be calculated on the lattice, for example, while $`c`$ is a numerical constant which depends on the renormalization scheme used to compute $`\mathrm{\Lambda }`$. Eq. (10) shows the dependence on the gauge group. For $`SU(2)`$ two degenerate ground states with opposite sign of the gluino condensate, $`<\overline{\lambda }\lambda ><0`$ and $`<\overline{\lambda }\lambda >>0`$ appear, while for $`SU(3)`$ there are three degenerate vacua at $`k=k_c`$ (in  a fourth state with $`<\lambda \lambda >=0`$ is claimed). A first numerical study of SYM theory with a gauge group $`SU(3)`$ is in .

### 1.6 Magnitude of the gluino condensate

The calculation of the gluino condensate for the $`N=1`$ SYM theory is a puzzle. Two approachs in the literature have been used which give different results for $`c`$. One is based on weak-coupling instanton (WCI) calculations  and gives $`c=1`$. In the second, calculations based on strong-coupling instanton (SCI) give $`c=2/((N_c1)!(3N_c1))^{1/N_c}`$ . For a review on SCI see . Several suggestions have been put forward to resolve the puzzle, see for example . Ref.  cast serious doubts on the SCI calculation by showing that the cluster decomposition is not valid. It is also shown that the addition of the so-called Kovner-Shifman (KS) chiral symmetric vacuum state  can not straightforwardly resolve the disagreement between the SCI and WCI results . The KS vacuum can indeed potentially resolve the mismatch at the 1-instanton sector $`(k=1)`$ but it fails to do so for the topological sectors with $`k>1`$ . Using an instanton liquid picture gives qualitatively similar results and evidence for the gluino condensate .

### 1.7 Light hadron spectrum

For the $`N=1`$ SYM theory a low energy effective action has been proposed by Veneziano and Yankielowicz (VY) . The action contains all degrees of freedom, gauge invariant and colorless, composite fields: $`F_{\mu \nu }^aF_{\mu \nu }^a`$, $`F_{\mu \nu }^a\stackrel{~}{F}_{\mu \nu }^a`$, $`\overline{\lambda }^a\lambda ^a`$, in analogy to QCD, while $`\chi =\sigma _{\mu \nu }F_{\mu \nu }^a\lambda ^a`$ is a new type of composite operator formed by a gluino $`\lambda `$ and a gauge field $`F`$, both in the adjoint representation. These fields can be combined to form the chiral supermultiplet, containing the expression for the anomalies as component fields

$$S(x,\theta )=\varphi (x)+\sqrt{2}\theta \chi (x)+\theta \theta F(x).$$
(11)
$`\varphi =\frac{\beta (g)}{2g}(\psi _w)^\alpha (\psi _w)_\alpha `$, is proportional to the gluino bilinear (here $`\psi _w`$ denotes a 2-component Weyl spinor), while the other components, which we do not report here (see ), contain combinations of gluino-gluino field and gluino-gluon fields. The VY action has the form

$$_{eff}=\frac{1}{\alpha }(S^{}S)^{1/3}|_D+\gamma [(S\text{log}\frac{S}{\mu ^3}S)|_F+h.c.].$$

Expanding the effective VY action around its minimum, it is found that the low energy spectrum forms a supermultiplet, consisting of a scalar meson $`\overline{\lambda }^a\lambda ^a`$ (the $`af_0`$), a pseudoscalar meson $`\overline{\lambda }^a\gamma _5\lambda ^a`$ (the $`a\eta `$), (the $`a`$ denoting the adjoint representation), and a spin-$`1/2`$ gluino-glueball particle, the $`\chi `$. Glueballs are absent in this formulation.

In the SUSY point these masses are degenerate. The introduction of a $`m_{\stackrel{~}{g}}0`$ breaks supersymmetry softly and leads to a splitting of the multiplet. How the spectrum is influenced by the soft SUSY breaking has been studied in :

$`M_{a\eta }`$ $`=`$ $`N_c\alpha \mathrm{\Lambda }+{\displaystyle \frac{40\pi ^2|m_{\stackrel{~}{g}}|}{3N_c}}+\mathrm{},`$
$`M_{a\chi }`$ $`=`$ $`N_c\alpha \mathrm{\Lambda }+{\displaystyle \frac{48\pi ^2|m_{\stackrel{~}{g}}|}{3N_c}}+\mathrm{},`$
$`M_{af_0}`$ $`=`$ $`N_c\alpha \mathrm{\Lambda }+{\displaystyle \frac{56\pi ^2|m_{\stackrel{~}{g}}|}{3N_c}}+\mathrm{}.`$ (12)
Unfortunately, the range of applicability of the linear mass formulae is not known because of the unknown magnitude of the constants and of the higher order terms in Eq. (12).

Introducing an extra term in the effective VY action, Farrar et al. (FGS) solved the question of including glueballs in the low energy spectrum . For unbroken supersymmetry we expect to see two chiral multiplets (not one), at the bottom of the SYM spectrum. The lighter one contains a $`0^+\text{glueball}F_{\mu \nu }F_{\mu \nu }`$, a $`0^{}\text{glueball}\epsilon ^{\mu \nu \rho \sigma }F_{\mu \nu }F_{\rho \sigma }`$ and a gluino-glueball ground state, while the heavier supermultiplet is the VY one. Moreover, in the FGS picture, a non-zero mixing between the $`af_0`$ and $`0^+`$ glueball is possible. Of course, other generalizations beside the FGS picture are conceivable.

## 2 LATTICE FORMULATION OF $`N=1`$ SYM

The question of whether it is possible to formulate successfully SUSY theories on the lattice has been addressed in the past by several authors  (the reader is refered to  for a sucessful contruction of a lattice $`2d`$ Wess-Zumino model, and some discussion concerning Ref. ). It can be seen that a lattice regularized version of a gauge theory is not SUSY since the Poincaré invariance (a sector of the superalgebra) is lost, thus $`\{Q_\alpha ,\overline{Q}_\beta \}=2\sigma _{\alpha \beta }^\mu P_\mu `$. Poincaré invariance is achieved automatically without fine tuning in the continuum limit because operators that violate Poincaré invariance are all irrelevant. Moreover, if the SUSY theory contains scalar fields one can have scalar mass terms that break supersymmetry. Since these operators are relevant, fine tuning is necessary in order to cancel their contributions.

Another problem is the question of how to balance bosonic and fermionic modes, the numbers of which are constrained by the supersymmetry: the naive lattice fermion formulation results in the doubling problem , and produces a wrong number of fermions. The problem can be treated as in QCD by using different fermion formulations. Let us briefly summarize those which have applications in SUSY theories.

### 2.1 Wilson fermions

In the Wilson formulation for the $`N=1`$ SYM theory it is proposed to give up manifest supersymmetry on the lattice and restore it in the continuum limit . Supersymmetry is broken by the lattice, by the Wilson term and is softly broken by the presence of the gluino mass. Supersymmetry is recovered in the continuum limit by tuning the bare parameters $`g`$ and the gluino mass $`m_{\stackrel{~}{g}}`$ to the SUSY point. The chiral and SUSY limit can be recovered simultaneously at $`m_{\stackrel{~}{g}}=0`$.

In the Wilson formulation, the Curci and Veneziano (CV) effective action, suitable for Monte Carlo simulations, reads

$$S_{CV}=\beta \underset{pl}{}\left(1\frac{1}{N_c}\text{Re}\text{Tr}U_{\mu \nu }\right)\frac{1}{2}\text{log}\text{det}Q[U].$$

For the gauge group $`SU(N_c)`$, the bare coupling is given by $`\beta 2N_c/g^2`$. The fermion matrix for the gluino $`Q`$ is defined by

$`Q_{yb,xa}[U]\delta _{xy}\delta _{ab}k{\displaystyle \underset{\mu =1}{\overset{4}{}}}[`$
$`\delta _{y,x+\widehat{\mu }}(1+\gamma _\mu )V_{ba,x\mu }+\delta _{y+\widehat{\mu },x}(1\gamma _\mu )V_{ba,x\mu }^T].`$
$`k`$ is the hopping parameter defined as $`k=1/(2(4+m_0a))`$, where $`m_0`$ is the bare mass, and the matrix for the gauge field link in the adjoint representation is

$$V_{ab,x\mu }V_{ab,x\mu }[U]\frac{1}{2}\text{Tr}(U_{x\mu }^{}T_aU_{x\mu }T_b).$$
(14)
The fermion matrix for the gluino in Eq. (2.1) is not hermitian but it satisfies $`Q^{}=\gamma _5Q\gamma _5`$. That allows for the definition of the hermitian fermion matrix $`\stackrel{~}{Q}\gamma _5Q`$. The path integral over the Majorana fermions gives the Pfaffian,

$$[d\lambda ]e^{\frac{1}{2}\overline{\lambda }Q\lambda }=[d\lambda ]e^{\frac{1}{2}\lambda ^TCQ\lambda }=Pf(M),$$

where $`MCQ`$ is an antisymmetric matrix.

It is easy to see that $`Pf(M)=\pm \sqrt{detQ}`$. In the effective CV action the absolute value of the Pfaffian is taken into account (this may cause the sign problem). The omitted sign can be included by reweighting the expectation values according to the formula,

$$<𝒪>=\frac{<𝒪\text{sign}Pf(M)>_{CV}}{<\text{sign}Pf(M)>_{CV}}.$$
(15)
The spectral flow is a method which checks the value of the sign of the Pfaffian. The experience of the DESY-Münster collaboration shows that bellow the critical line $`k_c(\beta )`$, corresponding to zero gluino mass $`(m_{\stackrel{~}{g}}=0)`$, negative Pfaffians practically never appear .

The factor $`1/2`$ in front of $`\text{log}\text{det}Q[U]`$ shows that Majorana fermions imply a flavor number $`N_f=1/2`$. This can be achieved by the hybrid molecular dynamics (HMD) algorithm  which is applicable to any number of flavors. The HMD has been checked for the CV action in $`N=1`$ $`SU(2)`$ SYM at small lattices $`4^3\times 8`$ . Another method for simulation with non-even numbers of flavors is based on the multi-bosonic algorithm proposed by Lüscher . A two-step variant using a noisy correction step , has been developed by Montvay in  called the two-step multibosonic (TSMB) algorithm. In the two-step variant, to represent the fermion determinant one uses a first polynomial $`𝒫_{n_1}^{(1)}(x)`$ for a crude approximation realizing a fine correction by another polynomial $`𝒫_{n_2}^{(2)}(x)`$ that satisfies, $`\underset{n_2\mathrm{}}{lim}𝒫_{n_1}^{(1)}(x)𝒫_{n_2}^{(2)}(x)=x^{N_f/2}`$, for $`x[\epsilon ,\lambda ]`$. The fermion determinant is approximated as

$$\text{det}(Q^{}Q)^{N_f}\frac{1}{\text{det}P_{n_1}^{(1)}(Q^{}Q)\text{det}P_{n_2}^{(2)}(Q^{}Q)}.$$

Unquenched results using TSMB have been reported by the DESY-Münster-Roma collaboration (the first large scale numerical simulation of $`N=1`$ SYM theory). For $`SU(2)`$ see , while for $`SU(3)`$ see . Interesting quenched results (which was pioneering work) are in .

In order to check the expected pattern of spontaneous chiral symmetry breaking, let us first write the expression for the renormalized gluino condensate, obtained by additive and multiplicative renormalizations: $`<\overline{\lambda }\lambda >_{R(\mu )}=Z(a\mu )[<\overline{\lambda }\lambda >b_0(a\mu )]`$. In a numerical simulation, a first order phase transition (or cross-over) should show up (on small or modere lattices) as a jump in the expectation value of the gluino condensate at $`k=k_c`$. By tuning the hopping parameter $`k`$ to $`k_c`$, for a fixed $`\beta `$ value, one expects to see a two peak structure in the distribution of the gluino condensate. By increasing the volume the tunneling between the two ground states becomes less and less probable and at some point practically impossible. Outside the phase transition region, the observed distribution can be fitted by a single Gaussian but in the transition region a good fit can only be obtained with two Gaussians. The DESY-Münster collaboration performed the first lattice investigation of the gluino condensate. Results for $`SU(2)`$ are reported in Fig. 1 and show that a first order phase transition occurs at $`k_c=(0.1955\pm 0.0005)`$ for $`\beta =2.3`$. The lattice size used is $`6^3\times 12`$ . For $`SU(3)`$, preliminary results are in . Here the pattern is more complicated, $`Z_6Z_2`$. The probability distribution for the gluino condensate was measured for $`k=0.1950`$ and $`\beta =5.6`$ on a rather small lattice $`4^3\times 8`$, with encouraging results. Of course, a more accurate study by going to larger lattices will clarify the nature of the transition.

SUSY restoration can be also verified by a direct inspection of the low energy mass spectrum : this is expected to reproduce the SUSY multiplets predicted in . An accurate analysis of the spectrum is, however, a non-trivial task from the computational point of view and an independent method for checking SUSY restoration would be welcome. Moreover, the mixing between the states has been measured. Numerical simulations show that this mixing is practically zero . At this conference, new results for the low lying spectrum of $`N=1`$ SYM, for $`12^3\times 24`$ and $`k=0.1955`$ and for $`16^3\times 32`$ and $`k=0.194`$, are reported by Peetz .

A study with a large number of colors $`N_c`$ and strong coupling, by considering the hopping parameter expansion as a sum over lattice paths (random walks), is . The surprising result is that the quenched approximation is exact at this order (and it is also consistent with the quenched results of Donini et al. in ). Formulae for the propagators and masses of 2- and 3-gluino states are also presented. The 2-gluino masses do coincide with the results for the meson spectrum in ordinary lattice QCD at strong coupling . A preliminary study of a 3-gluino states is reported also in . This particle does not appear in  even if it contains the same quantum numbers. A numerical analysis of this issue would clarify whether it contributes or not in the mass spectrum. At this conference, a study of the strong coupling expansion for $`N=1`$ SYM theory using the Hamiltonian formalism is also presented . It is shown that the theory is effectively described by an $`SO(4)`$ antiferromagnet.

### 2.2 Domain wall fermions

A very nice innovation is the domain wall fermions (DWF) approach. A new lattice fermion regulator, which improves the lattice formulation for fermions because the zero gluino mass is achieved without fine tuning. Application of DWF in SUSY theories has been explored in  and also suggested in , with a different approach as . First Monte Carlo simulations for $`N=1`$ $`SU(2)`$ SYM with DWF, using the lines of Refs.  are in . DWF were introduced in  and were further developed in . For a recent review on DWF for SUSY gauge theories see .

There are two unwelcome difficulties in using Wilson fermions as mentioned in the previous section. The first one is the need for fine tuning. The second one is related with the sign of the Pfaffian. DWF are defined by extending the space-time to five dimensions. Also a non-zero five dimensional mass or domain wall height $`m_0`$, which controls the number of flavors, is present. $`L_s`$ is the size of the fifth dimension and free boundary conditions for the fermions are implemented. As a result the two chiral components of the Dirac fermion are separated with one chirality bound exponentially on one wall and the other on the opposite wall. For any value of $`a`$ the two chiralities mix only by an amount that decreases exponentially as $`L_s\mathrm{}`$. For $`L_s=\mathrm{}`$, chiral symmetry is expected to be exact even at finite lattice spacing. So, there is no need for fine tuning . DWF offer for the first time the oportunity to separate the continuum limit, $`a0`$, from the chiral limit, $`L_s\mathrm{}`$.

DWF introduce two extra parameters: $`L_s`$ and $`m_0`$. These two parameters together with the four dimensional mass $`m_f`$ control the effective fermion mass $`m_{eff}`$. In the free theory one finds

$$m_{eff}=m_0(2m_0)[m_f+(1m_0)^{L_s}],$$
(16)
with $`0<m_0<2`$. The value of $`m_0=1`$ is optimal because finite $`L_s`$ effects do not contribute to $`m_{eff}`$. In the interactive theory, one would not expect such optimal value, due to the fact that $`m_0`$ will fluctuate. Then the goal would be to have $`L_s`$ large enough to have the second term of Eq. (16) small, in order to simulate at reasonably small masses and extrapolate to the chiral limit, $`m_f0`$ and $`L_s\mathrm{}`$ .

The effective action, which is not reported here (more details in ) contains $`L_s`$ heavy species. When $`L_s`$ is increased they may introduce bulk effects which must be substracted. This can be done by introducing Pauli-Villars type fields . The fermionic path integral gives the Pfaffian

$$[d\lambda ]e^{S_F}=Pf(M_F)=\sqrt{det(D_F)}$$
(17)
which is positive for $`m_f>0`$. This is a second advantage of the DWF approach.

Numerical simulations with DWF for $`N=1`$ $`SU(2)`$ SYM are reported in , using the (HMDR) of . They concern only the study of the gluino condensate, for rather small volumes, $`4^4`$ and $`8^4`$. The results for $`m_f=0`$ are shown in Fig. 2. As can be seen, $`<\overline{\lambda }\lambda >(L_s\mathrm{})`$ has a non-zero VEV which remains different from zero, even for rather small volumes. These results (and also those in ) support the non-zero value for the gluino condensate.

Also the DWF has difficulties in its implementation. Beside the two extra parameters, it may happen that the two chiralities do not decouple, even for $`L_s\mathrm{}`$. In this case the chiral symmetry can not be restored. This may need large values of $`L_s`$ and for this reason much expensive cost in the simulations. From the computational point of view, SYM is harder to simulate than QCD, using DWF, while with Wilson fermions, SYM is easier to simulate than QCD.

### 2.3 SUSY WIs on the lattice

Another independent way to study the SUSY limit is by means of the SUSY WIs. On the lattice they contains explicit SUSY breaking terms and the SUSY limit is defined to be the point in parameter space where these breaking terms vanish and the SUSY WIs take their continuum form. These issues have been investigated numerically by the DESY-Münster-Roma collaboration, using Wilson fermions . Previoulsy in .

In the continuum, the SUSY WIs are given by Eq. (7) where $`S_\mu ^R(x)Z_SS_\mu (x)+Z_TT_\mu (x)`$ and $`Z_S`$ and $`Z_T`$ are multiplicative renormalization factors. $`T_\mu (x)=F_{\mu \nu }^a(x)\gamma _\mu \lambda ^a(x)`$ is a mixing current with dimension $`7/2`$ as $`S_\mu (x)`$ .

In the Wilson formulation, supersymmetry is not realized on the lattice. One might still define some lattice SUSY transformations (which reduce to the continuum ones (1.1) in the limit $`a0`$). One choice is

$`\delta U_\mu (x)`$ $`=`$ $`agU_\mu (x)\overline{\epsilon }(x)\gamma _\mu \lambda (x)`$
$`ag\overline{\epsilon }(x+a\widehat{\mu })\gamma _\mu \lambda (x+a\widehat{\mu })U_\mu (x),`$
$`\delta \lambda (x)`$ $`=`$ $`{\displaystyle \frac{i}{g}}\sigma _{\rho \tau }𝒢_{\rho \tau }(x)\epsilon (x).`$ (18)
In the case of a gauge invariant operator insertion $`𝒪(y)`$, we find for the bare SUSY WIs

$`<𝒪(y)_\mu S_\mu (x)>2m_0<𝒪(y)\chi (x)>+<{\displaystyle \frac{\delta 𝒪(y)}{\delta \overline{\epsilon }(x)}}|_{\epsilon =0}>`$
$`=<𝒪(y)X_S(x)>.`$ (19)
Comparing with Eq. (7), beside the presence of a non-zero bare mass term in the action which breaks supersymmetry soflty, the rest of the SUSY breaking results in the presence of the $`X_S`$ term, that appear since the action is not fully SUSY. In order to renormalize the SUSY WIs a possible operator mixing has to be taken into account. In the case of gauge invariant operator insertion, $`X_S`$ mixes with the following operators of equal or lower dimension , $`_\mu S_\mu `$, $`_\mu T_\mu `$ and $`\chi `$. The SUSY WIs can be written as

$`<𝒪(y)_\mu S_\mu (x)>+Z_TZ_S^1<𝒪(y)_\mu T_\mu (x)>`$
$`=m_RZ_S^1<𝒪(y)\chi (x)>.`$ (20)
Here the gauge invariant operator $`𝒪(y)`$ at point $`y`$ is assumed to be sufficiently far away from $`x`$ in such a way that contact terms are avoided. This is the on-shell regime. $`m_R=m_0a^1Z_\chi `$ and $`_\mu `$ is the lattice derivative. In numerical simulations, Eq. (20) can be computed at fixed $`\beta `$ and $`k`$. Thus, by choosing two elements of the $`4\times 4`$ matrices, a system of two equations can be solved for $`Z_TZ_S^1`$ and $`m_RZ_S^1`$. One must clearly ensure that these two equations are non-trivial and independent. To do this, a proper definition of the supercurrent operator and the operator insertion $`𝒪`$ is necessary. In Ref. , two different definitions for the supercurrent operator are considered in Eq. (20): the local definition (3), and more involved, the point-split definition, reported also in , which differs from the local one in order $`𝒪(a)`$.

The dependence of $`Z_TZ_S^1`$ and $`m_RZ_S^1`$ on $`k`$, are shown in Fig. 3 and Fig. 4, respectively, with two different operator insertion, $`\chi (x)`$ and $`T_0(x)`$, for a lattice size $`12^3\times 24`$. Fitting results are considered only for the insertion $`\chi (x)`$. In Fig. 3, $`Z_TZ_S^1=0.039(7)`$, for the point-split current and $`Z_TZ_S^1=0.185(7)`$, for the local current . Also, the combination of $`Z_TZ_S^1`$ shows no dependence on $`k`$. In fact, the latter is an $`O(a)`$ effect. An estimate of $`Z_TZ_S^1`$ at the 1-loop order, using the point split current and $`\beta =2.3`$ is $`Z_TZ_S^1Z_T|_{1loop}=0.074`$ . Preliminary studies for $`Z_TZ_S^1`$, using the local current definition, are reported in . Turning to Fig. 4, the expectation is that $`m_RZ_S^1`$ vanishes linearly when $`kk_c`$. Also, a determination of $`k_c`$ by performing an extrapolation to zero gluino mass is obtained. The results is $`k_c=0.19750(38)`$ for the point split current and $`k_c=0.19647(27)`$ for the local one. These values can be compared with the previous determination from the first order phase transition, $`k_c=(0.1955\pm 0.0005)`$ , see also Fig. 1.

A study of the continuum limit of the lattice SUSY WIs, using Wilson fermions, at the 1-loop order is . It is interesting to see whether an analytic calculation of the $`Z_S`$ and $`Z_T`$ renormalization factors is in agreement with the numerical ones. Compared with numerical simulations , a lattice perturbative calculation of the SUSY WIs is more complicated. In order to do perturbation theory, we have to fix the gauge, which implies that new terms appear in the SUSY WIs: the gauge fixing term, the Faddeev-Popov term and a term coming from the gauge variation of the involved operators . This is also discussed in . Taking into account all these contributions we have ,

$`<𝒪_\mu S_\mu (x)>2m_0<𝒪\chi (x)>+<{\displaystyle \frac{\delta 𝒪}{\delta \overline{\epsilon }(x)}}|_{\epsilon =0}>`$
$`<{\displaystyle \frac{𝒪\delta S_{GF}}{\delta \overline{\epsilon }(x)}}|_{\epsilon =0}><{\displaystyle \frac{𝒪\delta S_{FP}}{\delta \overline{\epsilon }(x)}}|_{\epsilon =0}>=<𝒪X_S(x)>.`$
In  the operator insertion studied (at the 1-loop order) is $`𝒪:=A_\alpha ^a(y)\overline{\lambda }^b(z)`$, which is a non-gauge invariant operator (a similar choice of operators as in the numerical case, for example $`\chi `$, would lead to a 2-loop calculation). In this case, $`X_S(x)`$ mixes with operators of equal or lower dimension , as for the on-shell case, plus $`_iZ_iA_i`$, where the additional operators $`A_i`$ correspond to mixing with non-gauge invariant operators. In , an on-shell 1-loop perturbative calculation (using an exact expression for $`X_S`$), gives $`Z_TZ_S^1Z_T|_{1loop}=0.074`$, using a point-split definition for the supercurrent, while preliminary studies using the local supercurrent, in the off-shell regime , give also results of the same order for $`Z_T`$ .

### 2.4 Ginsparg-Wilson (GW) fermions

The GW relation  is defined to be

$$\gamma _5D+D\gamma _5=aD\gamma _5D,$$
(21)
where $`\gamma _5D`$ is an hermitian lattice Dirac operator. An explicit solution to the GW algebra, free of doubling species is reported in . It exhibits highlight chiralities properties  and locality . Either DWF (already discussed) or operators obtained from a renormalization group (RG) blocking of the continuum one, the fixed-point (FP) operator , satisfy the GW relation.

Theoretical applications of GW algebra to lattice supersymmetry are reported in  for the Wess-Zumino model . In , it is suggested that a lattice version of a perturbatively finite theory preserves supersymmetry to all orders in perturbation theory, in the sense that the SUSY breaking terms induced by the failure of the Leibniz rule become irrelevant in the continuum limit. Differences between implementing GW fermions and Wilson fermions are also analyzed. In  a conflict between lattice chiral symmetry and the Majorana condition for a Yukawa-type coupling is pointed out. If one adopts GW operators, a precise analysis of supersymmetry and its breaking require a consistent formulation of Majorana fermions.

In Ref.  a new formulation of SYM on the lattice with an exact fermionic symmetry is presented. First, it is considering the model in a fundamental lattice which is called the one-cell model and it is derived the preSUSY transformations. Then, it is extended to the entire lattice. The lattice action has a peculiar form: a $`2a`$ translational invariance, not the usual $`a`$ ones, and it is called Ichimatsu lattice (similar to a chessboard). At this conference, first non-perturbative results on an Ichimatsu lattice gauge theory is presented , while in  the study of the phase transition is reported. Although this is an interesting formulation, one has to note that, because of the staggered fermion action, there is no exact balance between fermionic and bosonic degrees of freedom.

## 3 EXACT SUPERSYMMETRY ON THE LATTICE

Improving lattice supersymmetry seems to be a difficult task for gauge theories. In fact, most SUSY theories, as for example $`N=2`$ or $`N=4`$ SYM, contain scalar bosons which typically produce SUSY violating relevant operators, which has to be fined tune away. For $`N=1`$, as we have seen, only a fine tuning is needed in order to eliminate the mass term. Unfortunately, because there is no discrete version of supersymmetry which can be implemented to forbid scalar masses and unwanted relevant operators, it is desiderable to construct lattice structures which directly display at least a subset of exact supersymmetry in order to decrease the number of fine tuning to do. In Ref.  a similar approach is used, for the $`2d`$ Wess-Zumino model with extended $`N=2`$ supersymmetry on the lattice. The model is then discretized in a way that preserves exactly a subset of the continuum SUSY transformations. This is enough to guarantee that the full symmetry is restored without fine tuning in the continuum limit. Also numerical results using the HMC algorithm are presented , and show the equality between fermions and boson masses and also the verification of the WIs to high precition.

Another nice example of exact lattice supersymmetry is , where a perfect SUSY action for the $`2d`$ and $`4d`$ Wess-Zumino model, free case, is presented. The perfect action is achieved in terms of block variable RG transformation, which maps a system from a fine lattice to a coarser lattice in a specific way, that keeps the partition function and all expectation values invariant. It is preserved invariance under a continuous SUSY type of field transformations in a local perfect lattice action, which contains also a remnant chiral symmetry. This perfect formulation also cures the problem related with the Leibniz rule on the lattice . In the perfect lattice formulation it is obtained the consistently blocked continuum translation operator. Therefore the algebra with the field variations closes. Ref.  uses a similar approach.

At this conference a talk by Kaplan , based on a recent remarkable paper  has been presented. It is a new method for implementing supersymmetry on a spatial lattice for a variety of SYM theories in $`3+1`$ dimensions, including $`N=4`$, in a way that eliminates or reduces the problem of fine tuning. The formalism is presented in the Minskowski space but a generalization to Euclidean space is under way. The motivation is based on a recent work on deconstruction of SUSY theories . The spatial lattice is created by “orbifolding”. Starting from a “mother theory”, being a SUSY quantum mechanics (QM) system with extended supersymmetry, a gauge group $`U(kN^d)`$, and a global $`R`$ symmetry group $`G_R`$, the spatial lattice is constructed by orbifolding out a $`Z_N^d`$ factor from $`G_R\times U(kN^d)`$, which will result in a $`U(k)`$ gauge symmetry, living on a $`d`$-dimensional spatial lattice. This is called the “daughter theory”. Taking then the continuum limit of this “daughter theory”, in some point in the classical moduli space of vacua, produces a higher dimensional quantum field theory with the original extended supersymmetry restored (previoulsy broken by the orbifolding procedure), together with Poincaré invariance. The important point is that the lattice generated by orbifolding can retain some of the exact supersymmetries which facilitates the recovery of the remaining ones in the continuum limit. This method also protects the renormalizability of the theory. In , a SUSY QM model with extended supersymmetry in $`0+1`$ dimensions is considered, and then the types of lattices that can be obtained via orbifolding are shown.

### 3.1 Other related topics

At this conference, a nice example of a Hamiltonian lattice version for the $`2d`$ Wess-Zumino model is presented by Campostrini . Previous results in . Developing numerical simulations techniques using the Hamiltonian approach  turns out to be very advantageous (but contains also some disadvantages). Powerful many-body techniques are available: the Green Function Monte Carlo (GFMC) algorithm . Since $`H`$ is conserved, it is possible to preserve exactly a $`1d`$ SUSY subalgebra of the continuum $`N=1`$ SUSY algebra. This is an advantage in comparison with the standard lattice formulation and is it enough to guarantee the most important properties of SUSY-like paring of positive energy states . Moreover, fermions are implemented directly, and need not be integrated out. A disadvantage is that fermions may lead to sign problems, but at least in $`1+1`$ dimensions, it can be by-passed. In , simulations using GFMC are performed. The algorithm is very efficient in computing the ground state energy $`E_0`$ (because it can distinguish between 0 and $`10^5`$), and therefore can be used to study the pattern of supersymmetry breaking, which corresponds to $`E_0>0`$, while unbroken supersymmetry corresponds to $`E_0=0`$. Focusing on $`V(\varphi )=\lambda \varphi ^2+\lambda _0`$, predictions for the strong coupling and the weak coupling regime are quite different and it is interesting to study both numerically and analytically and the crossover from the strong to the weak coupling .

At this conference a related and very interesting method, namely, SUSY Discretized Light-Cone Quantization (SDLCQ) has been reported by Trittmann . SDLCQ is a discrete, Hamiltonian and manifestly SUSY approach to solving a quantum field theory. Some results (including a review) for the $`N=1`$ SUSY Chern Simons theory, in $`2d`$ and $`3d`$, including correlators and bound states are in . The theory is discretized by imposing periodic boundary conditions on the boson and fermion field in terms of discrete momentum modes, $`k=nP/K`$, where $`K`$ is a positive integer that determines the resolution (typically of order 10 in the numerical calculations). The continuum limit is reached for $`K\mathrm{}`$. The low energy spectrum mass is determined using the fit $`M^2=M_{\mathrm{}}^2+b(1/K)`$ and approximate BPS states which have non-zero masses are found. In , a numerical test of the Maldacena conjecture within the $`1015\%`$ is found. A schematic comparison of SDLCQ and lattice gauge theory is also presented.

Ref.  casts a Hamiltonian study of SYM QM, which faces the problem of the introduction of a cut-off that violates supersymmetry and the restoration of supersymmetry when it is taken away. It has been applyed to the Wess-Zumino QM and for the SYM QM, in $`2d`$ and $`4d`$. There are no sign problems. Also, the complete spectrum, Witten index and identification of SUSY multiplets has been determined .

## 4 CONCLUSIONS

A big effort has been made in order to describe supersymmetry on the lattice. Traditional Wilson fermions have been used in realistic computations with nice results. Improved chiral fermions results are starting too. New exciting ideas  are now waiting for numerical applications. It has also been shown that most properties of $`N=1`$ SYM are analogous to non-SUSY YM and QCD and can be tested on the lattice in order to understand a possible transition from SYM to YM. For this reason, placing real-world QCD in a wider variety of theories may help us to better understand it. Acknowledgments. It is a pleasure to thank M. Beccaria, M. Campostrini, F. Farchioni, T. Galla, C. Gebert, R. Kirchner, M. Lüscher, I. Montvay, G. Münster, J. Negele, R. Peetz and A. Vladikas. Also, W. Bietenholz, M. Golterman, D. B. Kaplan, C. Pena, S. Pinsky, H. So, U. Trittmann and J. Wosiek, for discussions and private communication. M. Peardon and S. Ryan for the nice and stimulating atmosphere at Trinity College. This work was partially funded by the Enterprise-Ireland grant SC/2001/307.