What are the main algorithms used in quantum computing?

[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

 

[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

 

[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)

 

[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

 

[Baggio]

Thanks - I've been looking at shor's and grover's today which proved to be a bit difficult since we haven't learned 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 :(

 

[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

 

[Baggio]

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

 

[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

 

[Baggio]

ahh thanks for the advice

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

 

[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

 

[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 :-/

 

[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

 

[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 ;)

 

[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

 

[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

 

[Baggio]

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

And the Grover iteration is something along the lines of:

[Oracle] -> [Hadamard gate] -> [Phase shift] -> [Hadamard gate]

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 :(

 

[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 :(

 

[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

 

[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..

 

[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.

 

[Baggio]

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.

That's what i don't understand - what the Hadamard gate does in this case.. I'll take another look at the book

 

[Baggio]

I looked in nielsen & chuang they explain linear algebra but they don't elaborate on how to piece concepts together.. I tried an example with 2 qubits N = 4 on paper

So this superposition would be

(|00> + |01> + |10> + |11>)/2

Apply the oracle:

(|00> + |01> - |10> + |11>)/2

Here let 2 be the correct match, the sign is changed. Now i tried applying a H-transform but how would one do this for two qubits (1 H-gate per qubit)? for othe case |00> would you apply it to the first 0, then the second 0, then do a tensor product of these. Then repeat for the other four kets above then sum?

:(

 

[Baggio]

I've been stuck on this problem for 2 weeks...

I asked my quantum information lecturer... but he's an insecure nervous wreck who just mumbles and I can't tell what he's saying from his russian accent

Anyone have any thoughts or hints?

 

[jvangael]

Exactly.

TO calculate it easily, for each component of the superposition and for every qubit in each component you apply the hadamard transform. Then you get this (rather large) sum. You then just add all the same components together.

Jurgen

 

[blip]

question.

I recently became extremely interested in string theory and the idea of the multiverse with respect to quantum computing. I've read "Mind Machines and the Multiverse," and am in the process of reading "The Fabric of Reality." (which is not quite was I was looking for, but it's interesting nonetheless)

Anyhow, if I want to obtain a better grasp mathematically for these concepts where would I begin, any books?

I have my undergraduate degree in computer science with a firm grasp of modern architecture and software design.
My math background goes up to Calc III, discrete, and linear algebra.

Thanks.

 

[jvangael]

It depends. Are you interested in core Quantum Computing or are you interested in the foundation of physics? The multiverse idea is interesting but has no practical applications in Quantum Computing; it is more a topic in the realm of philosophy and the interpretation of quantum mechanics. If you want to start learning QC there is only one truly amazing book: The Nielsen en Chuang - BIBLE - of quantum computing.

Jurgen

 

[blip]

Cool, thanks for the response.