Quantum Algorithms via Linear Algebra(rjlipton.wordpress.com)
rjlipton.wordpress.com
Quantum Algorithms via Linear Algebra
http://rjlipton.wordpress.com/2014/12/06/quantum-algorithms-via-linear-algebra-2/
2 comments
There are three main types of problems on which quantum computers outperform classical computers
1. Searching an unsorted list. (boring)
2. Factorizing numbers - generally the hidden subgroup problem. This one is interesting because it breaks certain classical cryptographic schemes. (just shift to different crypto schemes)
3. The one that is really interesting is the ability to simulate certain quantum systems efficiently. (it doesn't look from the contents that these guys are discussing these algorithms). The ability to simulate quantum systems efficiently has promising applications in biological systems, chemistry and condensed matter physics. These applications have the potential to create structural changes in human civilizations on the scale that the classical computer revolution had.
For example, drug design today proceeds by a lot of trial and error and experimentation. This is because of our inability to simulate cellular processes by using classical computers. Quantum computers might be able to make some of these simulations feasible, both in terms of time and economics. It is only currently a 'might' because on the one hand we have had continuous improvements in quantum simulation algorithms, we have also realized that certain problems cannot even be solved feasibly by even quantum computers. Future progress in the field of quantum algorithms will tell us which side of the fence we land on.
1. Searching an unsorted list. (boring)
2. Factorizing numbers - generally the hidden subgroup problem. This one is interesting because it breaks certain classical cryptographic schemes. (just shift to different crypto schemes)
3. The one that is really interesting is the ability to simulate certain quantum systems efficiently. (it doesn't look from the contents that these guys are discussing these algorithms). The ability to simulate quantum systems efficiently has promising applications in biological systems, chemistry and condensed matter physics. These applications have the potential to create structural changes in human civilizations on the scale that the classical computer revolution had.
For example, drug design today proceeds by a lot of trial and error and experimentation. This is because of our inability to simulate cellular processes by using classical computers. Quantum computers might be able to make some of these simulations feasible, both in terms of time and economics. It is only currently a 'might' because on the one hand we have had continuous improvements in quantum simulation algorithms, we have also realized that certain problems cannot even be solved feasibly by even quantum computers. Future progress in the field of quantum algorithms will tell us which side of the fence we land on.
"... The one that is really interesting is the ability to simulate certain quantum systems efficiently. ... applications have the potential to create structural changes in human civilizations on the scale that the classical computer revolution had. ..."
@abdullahkhalids, thx for answering a simple Q. Excellent summary & can see why there's a lot of interest in this area.
@abdullahkhalids, thx for answering a simple Q. Excellent summary & can see why there's a lot of interest in this area.
Any NP problem.
No. There is no reason to think that BQP = NP.
There is a very good reason to think that: the press always gets this wrong. So unless you either have some real knowledge in the field or you've come across Scott Aaronson's writings, you may be excused for believing that quantum computers "try all possibilities in parallel".
But there's good reason to think that NP problems might benefit from quantum computers.
(Still, Factorization is in NP, but that's not the whole story)
http://en.wikipedia.org/wiki/BQP
(Still, Factorization is in NP, but that's not the whole story)
http://en.wikipedia.org/wiki/BQP
Some light reading for my next long flight.
good to read, for the linear algebra alone.
"... what has really been driving the surge are quantum algorithms, which by our expectant understanding of Nature promise to accomplish tasks beyond the feasibility of our abundant classical computers ...."
anyone got an idea of what problems (aside from passwd cracking)?