News for hackers. Stuff that matters.
Re:What could the NSA do with a quantum computer? by tptacek on Friday June 28, 2013 @01:46PM (#5959322)
I've read this comment 3 times right now and, respectfully --- I mean this in a dry, analytical sense --- I can't understand the claim here.

Can you be specific as to how quantum algorithms are going to allow NSA to do "pre-crime analysis"? Could you talk a little bit more about the applicability of quantum algorithms to big data statistics problems?

You were very quick to comment on this thread, so I'm asking expecting that you have some interesting thoughts about quantum computing.

Re:What could the NSA do with a quantum computer? by bad_user on Friday June 28, 2013 @02:16PM (#5959520)
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.

Re:What could the NSA do with a quantum computer? by atondwal on Friday June 28, 2013 @03:18PM (#5959847)
> 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.

Re:What could the NSA do with a quantum computer? by damarquis on Friday June 28, 2013 @03:59PM (#5960042)
I believe it has even been proved that for most computational problems quantum computers cannot give an exponential speedup.
Re:What could the NSA do with a quantum computer? by gizmo686 on Friday June 28, 2013 @02:33PM (#5959609)
>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.

Re:What could the NSA do with a quantum computer? by drkevorkian on Friday June 28, 2013 @04:57PM (#5960308)
He might be referring to this: 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.

Re:What could the NSA do with a quantum computer? by bad_user on Friday June 28, 2013 @02:45PM (#5959662)
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.