Quantum Algorithms via Linear Algebra

http://rjlipton.wordpress.com/2014/12/06/quantum-algorithms-via-linear-algebra-2/

by signa11 • 12 years ago

44 8 12 years ago

rjlipton.wordpress.com

mlubin• 12 years ago

Some light reading for my next long flight.

bootload2• 12 years ago

"... One thing important to us is that the book should look and feel like a linear algebra text. ..."

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

DSingularity• 12 years ago

Any NP problem.

cperciva• 12 years ago

No. There is no reason to think that BQP = NP.

abdullahkhalids• 12 years ago

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.

bootload2• 12 years ago

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

Quantum Algorithms via Linear Algebra

Related Stories