News for hackers. Stuff that matters.
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.