# Quantum Computing Algorithms

1. Oct 14, 2004

### Baggio

I've been asked to take part in a project invloving reasearch into Q.C I've basically got to investigate algorithms and i was wondering which are the main algorithms that have been devloped? So far I have Shor's factoring, Grover's searching and Discrete Logarithm algorithms.. Are there any others that are important you think?

Thanks

2. Oct 14, 2004

### jvangael

Quantum Algorithms

Well,

Shor and Discrete Logarithm all fit in a larger framework based on the hidden subgroup problem. There is a polytime quantum algorithm for the hidden subgroup problem and shor, discrete-log, order findin all derive from it.

Grover also derives more or less from what is called amplitude aplification algorithms. Basically amplitude amplification allows to speedup a lot more algorithms.

You could also look into quantum random walks which give a speedup oer classical walks. (Researchers such as Andris Ambainis did work on this.)

There are also the "Promise" problems which could be interesting: Deutch-Jozsa - Bernstein Vazirani, although some people do not consider them actual algorithms.

Hope this helps.

Jurgen

3. Oct 14, 2004

### slyboy

There are also a couple of newer algorithms, also based on the quantum Fourier transform. Hallgren's algorithm for Pell's equation (http://www.arxiv.org/abs/quant-ph/0302134) and various algorithms by van Dam, Hallgren and collaborators on problems that do not fit into the hidden subgroup class of problems
http://www.arxiv.org/abs/quant-ph/0011067
http://www.arxiv.org/abs/quant-ph/0207131
http://www.arxiv.org/abs/quant-ph/0211140

At present it is not clear exactly what class of problems can be efficiently solved on a quantum computer, but not on a classical computer. Although we suspect that things like factoring are hard on a classical computer, proving it would require solving the P=NP problem in complexity theory, which is generally thought to be incredibly difficult (the Clay institute will give you a million dollars if you can manage to do it).

In other areas of quantum computing and communications, the benefit of quantum over classical can be definitively proved. For example, in quantum communication complexity, Ran Raz proved that there were problems with an exponential separation in communication cost for quantum protocols over classical ones.

R. Raz, Proc. 31 ACM Symp. on Theory of Computing, pp.358-367, (1999)

4. Oct 14, 2004

### meteor

Not as famous as Shor's algorithm, but Kitaev algorithm is also a quantum algorithm for factoring numbers

In August appeared this paper where Azuma presents a quantum algorithm for examining oracles
http://arxiv.org/abs/quant-ph/0408013

Last edited: Oct 14, 2004
5. Oct 14, 2004

### Baggio

Thanks - I've been looking at shor's and grover's today which proved to be a bit difficult since we haven't learnt the math so i've bsaically been trying to teach my self going along. I think i'm going to go with shor's, grover's and may be the dicrete logarithm one that's IF i can find some decent information on it :(

6. Oct 15, 2004

### Baggio

I'm using a book to try and understand Shor's algorithm and it constantly says so and so is computed in poly(log 2)time which is fair enough but how can we determine mathematically that it is in fact computed in poly(log N) time (N - number to be factorised)

Also where does the quantum fourier transform come into it? According to the books I read number theory and Euclid's theorem is used to find the factors.. So what use is the QFT.. you've already found the factors..??

I'm missing an important link here

Last edited: Oct 15, 2004
7. Oct 16, 2004

### Baggio

can someone tell me the sort of math i need to read up on in order to understand Shor's algorithm?

8. Oct 16, 2004

### jvangael

First of all, you need a (very small) notion on number theory. The first part of the algorithm applies some basic number theory to conclude that finding a prime divisor is equivalent to finding the order of a certain element in a finite field. The last part of the algorithm uses a little basic number theory to derive the order by applying the continued fractions algorithm.

For quantum mechanics, you would need a thourough grasp of linear algebra. The algorithm itself applies a quantum fourier transform. A book like Nielsen & Chuang explains the transform well enough to understand Shor factorisation and Discrete Logarithm.

I would suggest to first start studying Grover's algorithm to test your knowledge of quantum mechanics. If you understand it well, you can move on to Shor's algorithm which is a little more complicated.

Jurgen

9. Oct 16, 2004

### Baggio

Yes number theory I was looking at that today.. In my book it says that if r is even that

$a^r = 1 mod(N)$ Can be written as

$a^r -1 = 0 mod(N)$

How would i go about proving this? I'm not satisfied with just accepting it as given

Thanks

10. Oct 16, 2004

### jvangael

Ok, you are forgetting a lot of important details but because you are talking about Shor factorisation this is what you would like to know I think:

if gcd(a, N) = 1, then a is an element of the group $Z_N^*$. This group has order $\phi(N)$ where $\phi$ is the euler totient function. Therefore by the implications of Lagrange's theorem $a^{(\phi(N))} \equiv 1 mod(N)$.

In the case of factoring an integer using Shor's algorithm, N and a have been tested in polynomial time for gcd = 1 using Euclids algorithm at the start of the algorithm.

$a^r \equiv 1 mod(N)$ therefore $a^r -1 \equiv 0 mod(N)$ is just standard modulo arithmetic.

Again, I would suggest studying the Grover algorithm first which is much easier to grasp. Especially as a first introduction to quantum computing.

Jurgen

Last edited: Oct 16, 2004
11. Oct 16, 2004

### Baggio

hmm you're right

Groups, order. euler totient fn, lagranges thereom.. Never covered this stuff (I'm a 3rd year undergraduate..

That was the point at which I got stuck now i know why..

Fact is eventually I've got to cover shor's algorithm for this project as it is important :-/

12. Oct 16, 2004

### jvangael

Hmm,

Ok, if you really have to cover Shor's algorithm i'd suggest to go to your local library, get Nielsen & Chuang's book. It has the basic number and group theory you need. It has a sufficient treatment on fourier transforms, just enough to understand Shor's algorithm.

Jurgen

13. Oct 17, 2004

### Baggio

What's the name of the book? (Make life a lot easier)

EDIT: Never mind

Hehe I just put in a request for a copy at my university library - I think it's the same copy one of my group project members have... oh well ;)

Last edited: Oct 17, 2004
14. Oct 24, 2004

### Baggio

Just finished learning about Deutsch's Algorithm and now i've started looking at grover's but now i'm stuck...

I can't see how the unitary transform

$U_{\omega}: |x> \rightarrow (-1)^{f_{\omega}(x)}|x>$

can be written as

$U_{\omega} = 1 - 2|\omega><\omega|$

And then they write the unitary phase transform as

$U_{\ s} = 2|\ s><\ s| - I$

Thanks

15. Oct 24, 2004

### jvangael

Well,

Basically what

$U_{\omega}: |x> \rightarrow (-1)^{f_{\omega}(x)}|x>$

says is that you retain the phase for all vectors including the $$|\omega>$$ vector. Moreover, $$|\omega>$$ vector's phase gets flipped. Now going from 1 to -1 is the same as extracting 2 from it's phase. So the operator

$U_{\omega} = 1 - 2|\omega><\omega|$

says to leave every vector alone (the identity) and for every vector which projects on $$|\omega>$$ you subtract two from the phase. Now because in Grover's algorithm all the "solutions" are represented by orthogonal vectors, there will only be one vector ($$|\omega>$$ itself) which when projected on the $$|\omega><\omega|$$ subspace will not be projected to 0.

I think this gives you an idea. You might want to try to figure the next one out yourself first.

Jurgen

16. Oct 25, 2004

### Baggio

According to the literature the oracle takes |x> -> -|x> if f(x) = 1

And the Grover iteration is something along the lines of:

Which can be seen in this pdf page 120..

So what is the point in introducing another phase shift into the algorithm..

I think this is evading me because of my lack of understanding as to what the first H-gate in the iteration is doing :(

17. Oct 26, 2004

### Baggio

I'm at a loss here.. I just can't understand why another tranform is needed since the oracle already changes the sign from + to -

I've been spending the last 2 days on this :(

18. Oct 27, 2004

### jvangael

Let me give you an intuitive feel for why the second transform is needed. The oracle creates a phase flip. Take the first phase flip in the algorithm: this buys you nothing because if you'd measure, the probability outcomes don't depend on the sign of the component. Now what you want to do is transform the phase difference in an amplitude difference. This is what the inversion about average (the second transform) does. It brings the amplitude of the fipped component back to positive by flipping the amplitude about the average. The amplitude of all other components gets a little smaller. After one such step, the result is that the component you are looking for has a little higher probability of being detected than the others. Just repeast the procedure and you will end up with high probability with a solution to your search.

Jurgen

19. Oct 27, 2004

### Baggio

Ok thanks I get that :D

But what do the H gates before and after the phase inversion do? From my basic understanding I thought the H-gate simply put the register in a superposition like $N -> 1/\sqrt{N}\sum |x>$ so passing this though the oracle will flip the sign of the matching state.. Then another H-gate is applied and i don't know what this does..

From what i read somewhere HH= I so applying HH|0> -> |0> but with the phase changed on one of the states i don't know what the effect would be..

20. Oct 27, 2004

### jvangael

I can't go through all the details but try figuring out for yourself what a Hadamard gate does to all the basis states. Than sum up what you need for the state after an oracly query and apply basic linear algebra. I believe Nielsen & Chuang has a really good overview of the Linear Algebra required to understand the transformation.