4 ms·

Quantum computing could be used for solving systems of linear equations more efficiently for example, having applications in image/video processing, weather pre

Quantum computing could be used for solving systems of linear equations more efficiently for example, having applications in image/video processing, weather predictions and all kinds of analysis - solving such equations with classic computers is done in something like O(n^3) or O(Cn^2) with a huge C, but quantum computers could reduce this to O(log n) or something like that. This is really cool, because doing simulations of complex systems, like weather modelling, involves a huge number number of equations and variables (think billions, or even trillions). It isn't far fetched to think of evolved quantum algorithms for making better predictions than we currently do. On the other hand, some people kind of have the impression that with quantum computers suddenly NP won't be an issue anymore. Which is simply not true. Most problems we have will simply go unsolved and quantum computers will introduce problems of their own.

gizmo686 13y ago
>quantum computers could reduce this to O(log n) I doubt it. It would take O(n) just to copy that data into your quantum computer.
- bad_user 13y ago
  Well yes, that's one problem with quantum computing. Writing data to those qubits and reading the computed results is getting you back to square one.
- drkevorkian 13y ago
  He might be referring to this: http://arxiv.org/pdf/0811.3171v3.pdf http://arxiv.org/pdf/0811.3171v3.pdf So, if the question you want to ask is "what is some property of the solution of the (sparse) set of linear equations" rather than wanting to know the (inherently O(n)) solution itself, you can get exponential speedup.
atondwal 13y ago
> solving such equations with classic computers is done in something like O(n^3) or O(Cn^2) with a huge C, but quantum computers could reduce this to O(log n) or something like that. If you're referring to the algorithm I think you're referring to, you only get the speedup if your linear system is Hermitian and has O(polylog(n)) nonzero entries, which doesn't really help us if we care about things like weather modelling.
- damarquis 13y ago
  I believe it has even been proved that for most computational problems quantum computers cannot give an exponential speedup.

gizmo686 13y ago

>quantum computers could reduce this to O(log n) I doubt it. It would take O(n) just to copy that data into your quantum computer.

bad_user 13y ago
Well yes, that's one problem with quantum computing. Writing data to those qubits and reading the computed results is getting you back to square one.
drkevorkian 13y ago
He might be referring to this: http://arxiv.org/pdf/0811.3171v3.pdf http://arxiv.org/pdf/0811.3171v3.pdf So, if the question you want to ask is "what is some property of the solution of the (sparse) set of linear equations" rather than wanting to know the (inherently O(n)) solution itself, you can get exponential speedup.

atondwal 13y ago

> solving such equations with classic computers is done in something like O(n^3) or O(Cn^2) with a huge C, but quantum computers could reduce this to O(log n) or something like that. If you're referring to the algorithm I think you're referring to, you only get the speedup if your linear system is Hermitian and has O(polylog(n)) nonzero entries, which doesn't really help us if we care about things like weather modelling.

damarquis 13y ago
I believe it has even been proved that for most computational problems quantum computers cannot give an exponential speedup.