Quantum Computing

Submitted as part of the requirements for the qualifying exam by Omri Palmon.

You have nothing to do but mention the quantum theory, and people will take voice for the voice of science, and believe anything.

— Bernard Show, Geneva (1938)

1 introduction

In this report we will review three papers that were published in the last two years about quantum computation. Quantum computers are computers that follow the physical laws of quantum physics rather then the laws of classical physics. The idea was first introduced by Fynman [2] which asked two questions, can a classical computer simulate quantum mechanics processes in polynomial time? can a quantum mechanics computer do more then a classical computer? In this report we will review several results that show that quantum computing has some additional power, though exact characterization of this power is not known yet. Maybe the most impressive result is that quantum computer can factor a number to its prime factors in polynomial time. No polynomial solution is known for this problem yet. Furthermore, several cryptography systems assume that factoring of big numbers can not be done in reasonable time. We will also present a problem where a quantum computer using some oracle function can solve in polynomial time a problem which deterministic or probabilistic Turing machines need exponential time to solve this problem. We do not know yet of any such problem which does not involve an external oracle.

Unfortunately building a physical quantum machine is not possible in the known technology. The discovery that quantum computers can have ultimate cryptanalysis power brought a lot of attention (and budgets) to the field. Several groups are trying now to check whether building a quantum machine will be possible technologically.

In this report we will try to give the basic intuition behind the new structure of quantum computing. This is not an easy thing to do, since quantum mechanics itself is very unintuitive. We will try to give the physical equivalents of the basic tools that enable quantum computer to do more then classical ones.

This report was based on [1, 3, 4] . There are two important differences between the material as it is presented here and as it is presented in the original papers. The result in [4] and the easy case of the discrete log problem in [3] were unified to one proof in a more general context. The proof of the factoring algorithm is different from the proof given in [3] and it is much simpler. We also tried to give basic intuition about how the factoring proof relates to the simpler cases.

The organization of the report is as follows, section 2 will describe the formal definition of a quantum Turing machine. Section 3 will explain the differences between a quantum Turing machine and a probabilistic Turing machine, and will give more intuition behind the idea of quantum computing. Section 4 will describe what are the basic operations that a quantum machine can do. Section 5 will describe the first application of quantum computation to find an algebraic invariant of a function, with two applications. In section 6 we will present a probabilistic algorithm for factoring numbers, which still has an exponential subproblem. In section 7 we will show how a quantum Turing machine can solve this subproblem in polynomial time. The appendixes will contain additional issues that are interesting but not essential for understanding the report. Appendix A will give basic knowledge about group theory and Fourier transform on groups. Appendix B will show that classical probabilistic Turing machine can not solve the problem describes in subsection 5.1. Appendix C will give some technical lemma that we will use in the report.

2 What is a Quantum Turing Machine?

In this section we will review the formal definition of quantum Turing machine (QTM). This definition will be contrasted to the definitions of probabilistic Turing machine and nondeterministic Turing machine. Unfortunately, though the formal definitions of quantum computation and probabilistic computation are very similar, the actual models are very different. Therefore we highly recommend the reader not to skip the next section, in which an attempt to give intuitive description of quantum computation is made. Skipping the next chapter might lead to understanding only on the formal level. Such understanding, we think, is as good as not understanding at all.

When reviewing the classical models of computation we will assume the reader is familiar with the models. We will just emphasize the issues in classical computation which are different in quantum computation. Figures 1 and 2 contain the formal descriptions of the various computation models. They are written in a very formal language. We recommend that the reader will use the figures as a formal reference to the text, or to compare between various models.

A deterministic Turing machine (TM) is an automata with a tape. The tape has a read/write head which points to a certain location on the tape. As a function of the automata state, and the current symbol pointed by the tape head, the machine does some deterministic operation. This operation can involve changing the automata state, changing the tape symbol and moving the tape head back or forth. At any given time the TM is in one deterministic state, which is a function of the initial state and the time elapsed. When we query the machine we can ask for the automata state and for the values of the symbols on the tape. Deterministic Turing machines are the basic models for our physical computers.

The first extension of the deterministic model is the non-deterministic Turing machine. Such a machine has the same basic structure of automata and tape. The state of a non deterministic machine is a set of possible deterministic states. The basic transition function takes a given automata state and tape symbol to a set of possible deterministic operations. The new non deterministic state is generated by applying on every possible deterministic state all its possible deterministic operations. When we query a non deterministic machine, we first ask if there is a possible state with some query value, and if yes we will apply another query one one of these possible states (for example, we would like to know whether there is a deterministic state with the automata in the accepting state, and if yes to get the tape symbols of that state). Unfortunately a non-deterministic Turing machine can not be built.

Automata states  Q
Tape symbols  Σ
Tape head move  D = {−1, 0, 1}
Local state S = Q × Σ Automata state and current tape symbol
Machine state  M = Q × Σ^{ℕ} × ℕ Automata state, tape contents and head location
Local state of machine state L : M ↦ S  L(q, {σ_{i}}_{i∈ℕ}, j) = (q, σ_{j})
Operation  O = Q × Σ × D new state, write symbol and head move
Operation on State  X : O × M ↦ M
Query  F (M) = F̄  values of q or (σ_{i})

Figure 1: Basic Definitions For Computation Models

It is not known for sure, but widely assumed that non-deterministic machines can not be simulated by deterministic machine.

A second extension to the classical deterministic model the the probabilistic Turing machine (PTM). A PTM has the same basic structure of automata and tape. The state of a PTM is a combination of deterministic states, where the coefficients of all the deterministic states should be non-negative and sum to 1. Each coefficient of a state stands for the probability that the PTM is in that state. The basic transition function takes every automata state and tape symbol to a probability vector of deterministic operations. The new state of a PTM is generated by taking the obvious linear combination of possible outcomes of the deterministic operations (see figure 2 for the formal details). The PTM can be represented as a stochastic matrix that takes every deterministic state to a probability vector of deterministic states. However, not every stochastic matrix represents a PTM. We need this matrix to be “local”, which means that only deterministic operations have positive probability, and those probabilities are determined only by the automata state and current tape symbol. The result of each query on a PTM is a random variable. The probability of a result to be some value is the sum of all the coefficients of the states which can produce this value. Note that these random variables are dependent. It seems that simulating a probabilistic Turing machine by a deterministic Turing machine might involve exponential time, but it is easy to see that the straight forward simulation using some random event generator creates a process with exactly the same distribution without maintaining the exact state.

The definition of QTM is very similar to the definition of PTM. The state is again a combination of deterministic states:

∑_{M∈M} α_{M} |M⟩  α_{M} ∈ ℂ ∑_{M∈M} |α_{M}|^{2} = 1

only that now the coefficients are complex, and the sum of their absolute values squared is 1. In other words the coefficient vector is an l_{2} unit vector. The basic transition function will again take every automata state and tape symbol to a combination of deterministic operations, where the coefficient of the operations are complex. The transition between quantum states will be represented by an infinite matrix which is generated from the combinations of the basic transition function (see figure 2 for the formal details). In order to maintain our basic

Deterministic

Machine State:  M_{D} ∈ M
Basic Transition:  δ_{D} : S ↦ O
Machine Transition: M_{D} ↦ X(δ_{D}(L(M_{D})), M_{D})
Matrix of Transition: Permutation
Query:  F (M_{D})

Non-deterministic

Machine State:  M_{ND} ⊂ M
Basic Transition:  δ_{ND} : S ↦ 2^{O}
Machine Transition: M_{ND} ↦ ⋃_{M∈M_{ND}} {X(O, M)| O ∈ δ_{ND}(L(M))}
Matrix of Transition: -
Query:  F_{1}(M) for some M ∈ M_{ND} such that F_{2}(M) = F̄

Probabilistic

Machine State:  M_{P} = ∑_{M∈M} α_{M} · M α_{M} ≥ 0 ∑_{M∈M} α_{M} = 1
Basic Transition:  δ_{P} : S × O ↦ ℝ δ_{P} (S, O) ≥ 0 ∀s ∈ S ∑_{O∈O} δ_{P} (S, O) = 1
Machine Transition: ∑_{M∈M} α_{M} · M ↦ ∑_{M′∈M} ( ∑_{O,M:X(O,M)=M′} α_{M}δ_{P} (L(M), O)) · M′
Matrix of Transition: Stochastic
Query:  Random Variable: P rob {F_{P} (M_{P}) = F̄} = ∑_{M:F (M)=F̄} α_{M}

Quantum

Machine State:  M_{Q} = ∑_{M∈M} α_{M} |M⟩ α_{M} ∈ ℂ ∑_{M∈M} |α_{M}|^{2} = 1
Basic Transition:  δ_{Q} : S × O ↦ ℂ δ_{Q}δ_{Q}^{T} = I
Machine Transition: ∑_{M∈M} α_{M} |M⟩ ↦ ∑_{M′∈M} ( ∑_{O,M:X(O,M)=M′} α_{M}δ_{Q}(L(M), O)) |M′⟩
Matrix of Transition: Unitarian
Query:  Random Variable: P rob {F_{Q}(M_{Q}) = F̄} = ∑_{M:F (M)=F̄} |α_{M}|^{2}

State change after measurement with result F̄

∑_{M∈M} α_{M} |M⟩ ↦ \frac{1}{\sqrt{∑_{M:F (M)=F̄} |α_{M}|^{2}}} ∑_{M:F (M)=F̄} α_{M} |M⟩

Figure 2: Description of Various Computation Models condition of the quantum state we will require that this matrix will be unitarian. This also implies that the vectors of the basic transition function are orthonormal vectors. But unlike the PTM model, an orthonormal basic vectors do not ensure that the big matrix is unitarian. The results of a query of QTM is a random variable. The probability of the output to be of some value is the sum of the absolute value squared of all the coefficients of the deterministic states that produce this value. If we have some query function F on deterministic states, then the output of the same query function on a quantum machine is random variable with distribution

P rob {F_{Q} ( ∑_{M∈M} α_{M} |M⟩) = F̄} = ∑_{M:F (M)=F̄} |α_{M}|^{2} .

Unlike the PTM case, a measurement actually changes the machine state. The new state now is a combination of all the states that are consistent with the output of the measurement, scales such that the l_{2} norm condition will still hold, i.e. if the output of F is F̄ then the change is

∑_{M∈M} α_{M} |M⟩ ↦ \frac{1}{\sqrt{∑_{M:F (M)=F̄} |α_{M}|^{2}}} ∑_{M:F (M)=F̄} α_{M} |M⟩ .

A more detailed combination of this phenomena, and the differences between QTM and PTM will be discussed in the next section.

3 A Quantum Turing Machine is NOT a Probabilistic Turing Machine

At first sight a QTM might look just like a PTM, with the technical difference that probabilities are now complex numbers rather then positive real numbers. The difference is a non-trivial and a very important one. It is interesting that the same confusion exists when one tries to explain quantum mechanics in intuitive terms. We will first describe some phenomena will enable us to understand better quantum mechanic (or maybe, just realize to what extent we do not understand quantum mechanics...).

Assume that we have some source of light as in figure 3. The light goes through two very small and very close holes, and then hits a white wall. If there would be only one hole, we would just see some white spot on the wall. But the two holes cause interference. For some points on the wall the light waves from the two holes will cancel each other, in some points they will add and double the amount of light. An important point is that the sum of the patterns that each hole creates separately is not the pattern created by both of them together.

On the beginning of the century the theories about waves and particles being the same thing started to emerge. One of the important experiments that conformed these theories was repeating the same experiment with electrons rather then light. The result was quite surprising, electrons behaved just like waves — they interfered. When a source of electrons was placed instead of the source of light, the electrons never hit the wall on some places, and hit the wall with twice the intensity on others.

Figure 3: Wave Interference

The same experiment was repeated, but in a slightly different setting. Only one electron was shot through the two holes at the time, and the place where the single electron hit the wall was marked. The experiment was repeated a lot of times, but each time there was only one electron in the system. The very surprising and unintuitive result is these interference patterns appear also in single electrons. The single electrons will never hit the locations in which the “electron waves” from the two holes will cancel each other, and hit the wall in twice the frequency in places where the waves sum together. Our basic intuition tells us that the single electron should “choose” one hole, go through it and then hit the wall. But this intuition leads to the conclusion that the pattern generated from the passing through two holes is some combination of the two patterns caused by going through one hole.

In a way that contradicts our basic intuition about reality, each electron goes through both holes and interferes with itself. The electron did not choose only one state with some probability. It is not the case that one thing happened and we can’t measure it. The electron is indeed going through the two holes together.

As the electron in the experiment described above, a QTM is not just at some state with some probability. It is really in all the different states together with some coefficients. Furthermore, a QTM can also interfere. Take for example a QTM with two states c_{1}, c_{2}, which at any given time performs the following transformation

α_{1} |c_{1}⟩ + α_{2} |c_{2}⟩ ⟶ \frac{1}{\sqrt{2}}(α_{1} + α_{2}) |c_{1}⟩ + \frac{1}{\sqrt{2}}(α_{1} − α_{2}) |c_{2}⟩ .

It is easy to check that the above transformation is indeed unitarian. If the machine is at time 0 in state c_{1}, and then it is measured at time 1 then we will get either c_{1} or c_{2} with probabilities (\frac{1}{2}, \frac{1}{2}). Exactly the same distribution will hold if we will start at time 0 from state c_{2}. But if we start at time 0 from the state \frac{1}{\sqrt{2}} |c_{1}⟩ + \frac{1}{\sqrt{2}} |c_{2}⟩ then measuring the state at time 1 will give the result c_{1} with probability 1. This an interference of the QTM. If we will measure the machine after staring from a combination of states, we wont get a combination of the measurement results after starting from each state separately. Note that though the actual quantum state satisfies the basic intuition about combination, the results of the measurements do not.

If we will take a close look on the situation we will see an even more strange behavior. When a machine starting at time 0 at state \frac{1}{\sqrt{2}} |c_{1}⟩ + \frac{1}{\sqrt{2}} |c_{2}⟩ is measured at time 1 it will always give c_{1} as a result. But if we will measure the machine at time 0, the result at time 0 will be either c_{1} or c_{2}, and the machine will change to either 0 |c_{1}⟩ + 1 |c_{2}⟩ or 1 |c_{1}⟩ + 0 |c_{2}⟩, and hence measuring at time 1 will now give c_{1} or c_{2} with probabilities (\frac{1}{2}, \frac{1}{2}). It is important to note that the act of measuring at time 0 changed the output at time 1. This is a very important difference between the PTM model and the QTM model. In the PTM model the results of measurements are dependent random variable, and hence the value of measurement at time 0 can change the distribution of the result at time 1. But just measuring at time 0, without telling the result wont change the output of the measurement at time 1. In the QTM model, measuring at time 0 changes the result of the measurement at time 1, even if the output of the measurement at time 0 is not known. This can be view as an example of Hiezenberg’s uncertainty principal, we can not measure the QTM without actually changing it.

This interference phenomena will be our basic computation tool in giving quantum computers more power then classical ones. In some sense we will cause all the non-solution of the problem to disappear and only the solutions will remain.

4 What can a QTM Do?

In this section we will describe what useful basic operations QTM can do. The first obvious question is whether a QTM can do deterministic processing. Returning to the definitions of a QTM, we can observe that a QTM will perform a deterministic operation if the column of the matrix associated with with the current state is a unit vectors. Since the definition of the QTM required this matrix to be unitarian, the matrix of a deterministic computation must be a permutation matrix. This means that a QTM can do a deterministic process if and only if it is reversible. This does not mean that the QTM can not compute a non one to one functions. It only means that whenever we calculate a function which is not one to one we should also maintain some information that will enable us to return to the original state. For example keeping a record of the parameters of the function will be enough since we can always erase the result.

Clearly we expect a QTM to do more interesting things then deterministic computation. The basic algorithm that gives QTM addition power is the Fourier transform on groups. Appendix A gives some mathematical background about the Fourier transform on finite Abelian groups. We will assume that the QTM can do the following on the group elements:

• The QTM can represent a group element in polynomial number of bits.

• The QTM can compute the isomorphism G ≅ ℤ_{p_{1}^{α_{1}}} ⊕ ⋯ ⊕ ℤ_{p_{k}^{α_{k}}} in polynomial time.

Note that the last thing implies that the QTM can perform the group operation, represent elements in the dual group Ĝ and compute ĥ(g) for ĥ ∈ Ĝ, g ∈ G.

To make the Fourier transform computable in polynomial time we will assume that for each subgroup ℤ_{p^{α}} in the decomposition p^{α} is polynomial. An equivalent assumption is that the order of each element in G is polynomial.

The Fourier transform is the transformation

|x⟩ ⟼ ∑_{y∈G} \frac{1}{|G|^{1/2}} ŷ(x) |y⟩ .

Though this is an exponential matrix, we will show how it can be decomposed to polynomial number of small matrices, each can be done in polynomial time by a QTM.

The QTM will work with the representation

x ∈ G ↦ (x_{1}, …, x_{k}) ∈ ℤ_{p_{1}^{α_{1}}} ⊕ ⋯ ⊕ ℤ_{p_{k}^{α_{k}}} .

In this representation the Fourier transform is

|x⟩ ⟼ ∑_{y∈G} \frac{1}{|G|^{1/2}} [∏_{j=1}^{k} exp (2πi\frac{x_{j}y_{j}}{p_{j}^{α_{j}}} )] |y⟩ .

Define for every j

T_{j} : |(x_{1}, …, x_{k})⟩ ↦ ∑_{y_{j}∈ℤ_{p{α_{j} \atop j}}} \frac{1}{(p_{j}^{α_{j}})^{1/2}} exp (2πi\frac{x_{j}y_{j}}{p_{j}^{α_{j}}} ) |(x_{1}, …, x_{j−1}, y_{j}, x_{j+1}, …, x_{k})⟩ .

Since p_{j}^{α_{j}} is polynomial, each T_{j} can be computed in polynomial time. It is easy to verify that T_{1} · T_{2} ⋯ T_{k}[|x⟩] is the Fourier transform of |x⟩. Since k is bounded by log |G| it is polynomial, and hence the whole process is polynomial.

5 Finding an Algebraic Invariant of a Function

Assume that we have some finite Abelian group G and a function f : G → I for some index set I. Assume that H ⊂ G is a subgroup of G and that f is H invariant, i.e. for every h ∈ H and g ∈ G we have f(gh) = f(g). We will assume that we know nothing about f. The only way to obtain information about it is to ask some oracle for the value of f on some elements of g. We would like to find H, the f invariant subgroup of G. We will show that this can be done in polynomial time by a QTM, subject to the assumption that the order of each group element is polynomial. We will also assume that the QTM can represent and manipulate the group elements as described in the previous section. Appendix B will show that there is an instance of this problem which is hard in classical computation models. Figure 4 will describe the quantum algorithm.

When trying to find the invariant subgroup H, the QTM will actually find a character that is identically 1 on the group H. A function f which is H invariant can be seen as a function on G/H. We will denote the elements of G/H as ḡ and the reduced function f̄: G/H ↦ I.

Init Measure state Apply Fourier transform Compute f

∑_{x∈G} \frac{1}{|G|^{1/2}} |x⟩

∑_{x∈G} \frac{1}{|G|^{1/2}} |x, f(x)⟩

∑_{x,y∈G} \frac{1}{|G|}ŷ(x) |y, f(x)⟩

|y, z⟩ with probability

∑_{x:f(x)=z} \frac{1}{|G|^{2}} ŷ(x)

Figure 4: Algebraic Invariant Finding Algorithm We will start from an initial state where each member of G has the same phase

∑_{x∈G} \frac{1}{|G|^{1/2}} |x⟩ .

Then we compute f(x), writing it after x to make the computation reversible

∑_{x∈G} \frac{1}{|G|^{1/2}} |x, f(x)⟩ .

The next step is to compute Fourier transform on x as explained in section 4

∑_{x,y∈G} \frac{1}{|G|}ŷ(x) |y, f(x)⟩ .

When we measure the machine the probability to get some result (y, z) is

| ∑_{x:f(x)=z} \frac{1}{|G|}ŷ(x)|^{2} = | ∑_{x̄:f̄(x̄)=z} \frac{1}{|G|} ∑_{h∈H} ŷ(xh)|^{2}

= \frac{1}{|G|^{2}} | ∑_{x̄:f̄(x̄)=z} ŷ(x̄) ∑_{h∈H} ŷ(h)|^{2}

= \frac{1}{|G|^{2}} |[ ∑_{x̄:f̄(x̄)=z} ŷ(x̄)] · [ ∑_{h∈H} ŷ(h)]|^{2} .

Since ŷ is also a character on H, ∑_{h∈H} ŷ(h) is either 0 or ŷ is identically 1 on H (as explained in the appendix A). Hence sampling the QTM to get the state |y, z⟩ will always give y such that ŷ is identically 1 on H. Furthermore, if f̄ is one to one, then all these characters are chosen with equal probability.

5.1 Application - Invariance Under XOR-mask

Assume G = ℤ_{2}^{n}, sequences of n bits with the bitwise xor operation. We are given some oracle that computes f : G ↦ 2^{n}. We know that there are two possibilities for the definition of f, either f(x) = f(y) implies x = y (one to one function), or f(x) = (y) implies x = y or x = sy for some fixed bit string s. How can we decide of which type f is, and find s if f is of the second type?

The group H is {0^{n}, s}. Finding a character that is 1 on H is finding an n-bit string y such that 0 = ∑ y_{i}s_{i} (mod 2). Choosing at random O(n) such strings will enable us to find the s by solving a system of linear equations (over the field ℤ_{2}). If the system of equations will have only the string of zeros as solution then f is one to one. Appendix B will show that this problem is exponential in classical computation models.

5.2 Application - Discrete log

Given a prime p and two numbers x, g ∈ ℤ_{p}, we would like to find r such that g^{r} = x

(mod p). We will solve the problem for the case where p − 1 is a smooth number, i.e. if the prime number factorization of p − 1 is p_{1}^{α_{1}} ⋯ p_{k}^{α_{k}} then for each j, p_{j}^{α_{j}} is polynomial.

We will work with the group G = ℤ_{p−1} × ℤ_{p−1}. The function f will be defined as

f(a, b) = g^{a}x^{−b} = g^{a−rb} (mod p) .

The invariant group H is

H = {(x, y)|x − ry = 0 (mod p − 1)} .

Since p is prime f is one to one on G/H. The smoothness of p−1 assures us that we can find the decomposition of ℤ_{p−1} and compute the Fourier transform in polynomial time. Using the algorithm we will obtain a character which is 1 on H. Such character will be represented by (c, d) ∈ G, where

(c, d)^{}(a, b) = exp(2πi\frac{ca + db}{p − 1}) .

The fact that (c, d)^{}is identically 1 on H is equivalent to d = −rc (mod p − 1). If c and p − 1 are relatively prime then we can find using Euclid’s algorithm k, l such that

ck + l(p − 1) = 1

and hence

−kd = rck = −r(−l(p − 1) + 1) = r (mod p − 1) .

It is now remains to estimate the probability that for random (c, d) that satisfy d = −rc

(mod p − 1), c and p − 1 will be relatively prime. Since c sets d this is the same probability that random c will be relative prime to p − 1. The number of numbers c which are relatively prime to p − 1 is Euler’s function ϕ(p − 1) which is known to satisfy ϕ(n)/n ≥ 1/ log n.

6 Factoring

Given a natural number n, we know that there is a unique decomposition of n as a multiple of prime numbers. Unfortunately finding this decomposition is a very hard problem. The best algorithm known to us runs in O(e^{\sqrt{L}}) time, where L is the number of digits in the number n. It is not known whether this problem can be solved in polynomial time or not. The assumption that this is a hard to compute problem is the foundation of many modern cryptography systems. We will present an algorithm for factoring which polynomial except one exponential component. In the next section we will show how this component can be solved in polynomial time using quantum computing.

Clearly it is enough to find algorithm that factors n to a multiple of two number n = ab, repeating such process log n times will be enough for a complete factorization. The algorithm is described in figure 5.

Done No Done orYes No No  Yes Yes gcd(x^{r/2} + 1, n) ≠ 1 (mod n) r even? gcd(x, n) = 1 ? Find random x < n gcd(x^{r/2} − 1, n) ≠ 1 (mod n) Find r s.t. x^{r} = 1 (mod n) x^{r/2} ≠ −1 (mod n)?

Figure 5: Factoring Algorithm

Assume that we reached the last step, then we have x, r such that x^{r} = 1 (mod n), r is even and x^{r/2} ≠ −1 (mod n). Hence

(x^{r/2} + 1)(x^{r/2} − 1) = 0 (mod n)

which implies that for some integer j,

[x^{r/2} + 1 (mod n)] · [x^{r/2} − 1 (mod n)] = jn .

The assumptions that x^{r/2} ≠ −1 (mod n) and that r is the order of x (i.e. x^{r/2} ≠ 1

(mod n)) imply that both numbers are not 0 or n. Hence at least one of them is not relatively prime to n. We need to estimate the expected number of times we will loop until finding x that satisfies all the conditions. Number theory assures us that we will get to the last step with probability 1−1/2^{k−1}, where k is the number of of different prime factors. The decomposition of n which is a power of a prime can be done with strait forward methods.

To find the order of x we will define f(a) = x^{a} (mod n), finding the order x is exactly finding the cycle of f. We will see how a QTM can find the cycle of f : Z ↦ I in polynomial time, assuming f itself can be computed in polynomial time, and that f is one to one except its cycle.

7 Finding the Cycle of a Function

Assume that we have a function f : ℤ ↦ I, where f is cyclic, i.e. there exist some u ∈ Z such that f(a) = f(r + a). We will also assume that except the r cycle f is a one to one, i.e. f(a) = f(b) iff r|(b − a). We will have some bound n on the cycle. Assume that f can be computed in polynomial time. We would like to find an algorithm that finds the cycle r in polynomial time (polynomial in log n).

Finding the cycle is finding some algebraic invariant of f because f(a) = f(a + u) for all u ∈ rℤ (where rℤ is the group of numbers which are multiples of r). This suggests that a QTM might be useful in finding such r using the same technique as in section 5. Unfortunately the group ℤ is infinite, and hence direct application of the algorithm is impossible. We will solve the problem by working in ℤ_{q} for some q which will be big enough to have a lot of cycles of the function, but small enough to keep the algorithm polynomial.

We will find q > 32n^{4} which is smooth, the proof of existence and algorithm for finding such q is given in appendix C. We will follow the same algorithm described in figure 4. Starting from the uniform superposition:

∑_{a=0}^{q−1} \frac{1}{q^{1/2}} |a⟩ .

Then computing f(a) for all a

∑_{a=0}^{q−1} \frac{1}{q^{1/2}} |a, f(a)⟩ .

Using the Fourier transform to map a to c gives us

∑_{a,c=0}^{q−1} \frac{1}{q} exp(2πiac/q) |c, f(a)⟩ .

Now we will measure the machine. The for some c and k < r, the probability for |c, f(k)⟩ is

| ∑_{a:f(a)=f(k)} \frac{1}{q} exp(2πica/q)|^{2} = |\begin{matrix}⌊ & \frac{q−k−1}{r} & ⌋ \\ & ∑ \\ & b=0 \end{matrix} \frac{1}{q} exp(2πic(br + k)/q)|^{2}

= |\begin{matrix}⌊ & \frac{q−k−1}{r} & ⌋ \\ & ∑ \\ & b=0 \end{matrix} \frac{1}{q} exp(2πicbr/q)|^{2}

= |\frac{1}{q} \frac{1 − exp(2πic ⌊\frac{q−k−1}{r}⌋ r/q)}{1 − exp(2πicr/q)}|^{2}
≤ \frac{1}{q^{2}} \frac{4}{(\{cr\}_{q}/q)^{2}}
≤ \frac{4}{\{cr\}_{q}^{2}} .

Where {cr}_{q} is the number which is congruent to cr modulo q and is in the range −q/2, …, q/2. This hints that we have high probability to obtain c such that rc is close to a multiple of q. Estimating the probability of getting c such that the distance of rc from a multiple of q is more then x gives

P rob \{|\{cr\}_{q}| ≥ x\} = ∑_{c≤q,k≤r:|\{cr\}_{q}|≥x} P rob \{|c, f(k)⟩\} ≤ rq \frac{4}{x^{2}} .

Assume that |{cr}_{q}| ≤ x, then there is an integer d such that

|rc − qd| ≤ x

which implies

|\frac{c}{q} − \frac{d}{r}| ≤ \frac{x}{rq} .

If x is small enough such that x/rq ≤ 1/2n^{2} then d/r is the unique continued fraction approximation to c/q, and the value of d/r can be easily obtained. The choice of q > 32n^{4} makes sure that we will be able to calculate the value of d/r with probability 1/2, since we can take x = rq/2n^{2}.

Unfortunately we might calculate the value of d/r and obtain some d′/r′ = d/r. In that case we know that r is a multiple of r′ and we will repeat the algorithm with f′(a) = f(r′a), repeating the algorithm at most log r ≤ log n time.

A Group Theory Background

Let G be a finite Abelian group. Then it is a well known fact from group theory that

G ≅ ℤ_{p_{1}^{α_{1}}} ⊕ ⋯ ⊕ ℤ_{p_{k}^{α_{k}}}

for distinct primes p_{1}, …, p_{k}, where ℤ_{n} is the group of numbers from 0 to n − 1 with the addition modulus n.

A character χ on G is a homeomorphism from G to the unit circle of ℂ which takes the group operation to the multiplication in ℂ, i.e.

χ : G ↦ ℂ
∀x ∈ G |χ(x)| = 1
∀x, y ∈ G χ(xy) = χ(x)χ(y) .

The characters on G form a group, with the point-wise multiplication,

(χ_{1} · χ_{2})(x) = χ_{1}(x)χ_{2}(x) .

The group of all characters is called the dual group of G and is denoted as Ĝ. For G ≅ ℤ_{n} it is easy to check that the dual group Ĝ is also isomorphic to ℤ_{n} and the isomorphism is defined as

k̂(j) = exp (2πi\frac{kj}{n} ) .

Using the fact about the decomposition of every group we get that G ≅ Ĝ for very finite Abelian group, and that if the decomposition of G is defined by some

x ↦ (x_{1}, …, x_{k}) x_{j} ∈ ℤ_{p_{j}^{α^{j}}}

then the isomorphism y ∈ G ↦ ŷ ∈ Ĝ is defined by

ŷ(x) = ∏_{j=1}^{k} exp (2πi\frac{x_{j}y_{j}}{p_{j}^{α^{j}}} ) .

Another useful fact is that for a character χ on G either ∑_{x∈G} χ(x) is 0, or χ(x) = 1 for all x ∈ G. This is true since for every y the mapping x ↦ yx is a one to one mapping on G, hence

∑_{x∈G} χ(x) = ∑_{x∈G} χ(yx) = χ(y) ∑_{x∈G} χ(x)

and hence either the sum is 0 or χ(y) is 1.

B Hardness of the XOR-mask problem in classical computational models.

Suppose that we will wont to solve the xor mask problem using a deterministic computer. It is easy to see that worst case time analysis will result in exponential number of calls to the oracle. This is because after k call to the oracle to compute the function on different bit strings, we will exclude only k(k − 1)/2 possible values of s. Since there are 2^{n} possible values of s we will need exponential number of of oracle calls.

This is also true for the probabilistic model. Assume that the oracle first flips a fair coin to decide if the function will be one to one or not. Depending on the result the oracle will either choose a random one to one function (with equal probability to all possible functions), or find a random s and random function which is s invariant (again with equal probability for all such s and possible function). Easy computation shows that after polynomial number of function evaluation the probability for the answer to be true is \frac{1}{2} +ϵ where 1/ϵ is exponential.

C Smooth Numbers

A smooth number is a number q with prime number factorization q = p_{1}^{α_{1}} ⋯ p_{k}^{α_{k}} such that p_{j}^{α_{j}} is polynomial in log q. For a given n we will show here an algorithm to find a smooth number between n and 2n.

1. Multiply the prime numbers 2 · 3 · 5 … until the result p is bigger then n.

2. If the result is less then 2n we are done.

3. Otherwise, find a prime number in the range p/n and p/2n (Tchebychef) and divide n by that number.

References

[1] E. Bernstein and U. Vazirani. Quantum complexity theory. In Proc. 25th ACM Symposium on Theory of Computing (STOC), pages 11–20, 1993.

[2] R. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21:467–488, 1982.

[3] Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In IEEE Symposium on Foundations of Computer Science (FOCS), 1994.

[4] Simon. On the power of quantum computation. In IEEE Symposium on Foundations of Computer Science (FOCS), 1994.