Comment by mtgx | Hacker News Reader

Comment by mtgx | Hacker News Reader

NSA with classic computers - analyzing what has already happened.

NSA with quantum computers - pre-crime analysis

CIA is already working on this with Recorded Future, and NYPD created a system with the help of Microsoft to create statistics to see where most crime is "likely" to happen and when.

I think we'll see a lot of very powerful technologies (quantum computers, mosquito-drones that can poison you in your sleep, etc) that can be so easily abused by governments, because they won't resist using them to get rid of people they don't like, especially if these technologies step on legal gray areas, but even if they don't (not like "mass spying of citizens" is anywhere close to gray area), or if they think they can keep their usage secret.

This is why it's going to be extremely important that the people get very outraged at such abuses as soon as even small ones happen using these technologies in the next few decades, to find balance in the law and government, before it's too late (these things will be moving fast).

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.

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.

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

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.

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.

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

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

Reply on news.ycombinator.com