News for hackers. Stuff that matters.
Re:What could the NSA do with a quantum computer? by jgrahamc on Friday June 28, 2013 @01:31PM (#5959205)
It's a pity that this article doesn't mention Shor's Algorithm (http://en.wikipedia.org/wiki/Shor%27s_algorithm). Shor's algorithm would make integer factorization O((log n)^3).

But we have a way to go: "Also in 2012, the factorization of 21 was achieved, setting the record for the largest number factored with a quantum computer."

Re:What could the NSA do with a quantum computer? by mtp0101 on Friday June 28, 2013 @03:22PM (#5959860)
The article actually does mention Shor's, just not explicitly. The author introduces integer factorization as "a kind of reverse multiplication" (lol). He then explains that quantum computers can factor numbers efficiently and that this has implications for computer security.
Re:What could the NSA do with a quantum computer? by uptown on Friday June 28, 2013 @02:41PM (#5959647)
Whenever somebody brings up what technology the NSA might have, now or in the future, I think back to Apple's eventual response to "antenna-gate". The speculation was that their antenna testing consisted of makings some phone calls, and seeing if things worked. Then Apple released these photos:

http://www.apple.com/lae/antenna/

I'd love to know what the NSA's version of this would be. Given their mission, and the financials resources available to them - it's difficult for me to imagine that they don't have technology at-their-disposal that blows most people's minds in terms of power and capabilities.

Re:What could the NSA do with a quantum computer? by mturmon on Friday June 28, 2013 @03:31PM (#5959898)
Another point of reference is the Keyhole satellites (e.g., http://en.wikipedia.org/wiki/National_Reconnaissance_Office#...), which turned out to be larger than most people imagined.
Re:What could the NSA do with a quantum computer? by Zarathust on Friday June 28, 2013 @01:35PM (#5959248)
"A report leaked to the Guardian suggests that the NSA can get three billion pieces of information a month from computer records alone.".

3 billion records doesn't seem to be that much. I mean, even with a desktop computer, having a month to compute something meaningful out of that doesn't seem far fetched. I really don't think they need sci-fi computers for all of that. 3B/month * 12months * 5 years = 180 billion records. That's a lot but large tech companies seem to deal with those kinds of numbers all year long.

Re:What could the NSA do with a quantum computer? by jstalin on Friday June 28, 2013 @01:57PM (#5959396)
For those of us who are not mathematicians, what would quantum computing practically mean? Compare current math capabilities of computers and quantum computing in layman's terms, please.
Re:What could the NSA do with a quantum computer? by _j5l3 on Friday June 28, 2013 @02:12PM (#5959495)
Quantum computers are not just super-fast versions of normal computers. They allow the running of some algorithms that normal computers can't physically run. One particularly important algorithm is Shor's algorithm.

Shor's algorithm allows quick factorization of primes. RSA encryption, the main way that things are encrypted today, relies on the assumption that factoring large primes is computationally infeasible. So quantum computers would allow the NSA to read RSA-encrypted data.

Re:What could the NSA do with a quantum computer? by weinzierl on Friday June 28, 2013 @02:26PM (#5959568)
From a computer science standpoint this incorrect. Regarding computability, quantum computers have exactly the same power as traditional computers.
Re:What could the NSA do with a quantum computer? by gizmo686 on Friday June 28, 2013 @02:31PM (#5959591)
Regarding computability yes. Regarding time complexity, it is unproven.

What we do know is that there is a known algorithm to factor number in polynomial time on quantum computers and there is not a known algorithm to do so on classical computers. Assuming that factoring numbers is actually a hard problem on classical computers (unproven, but generally accepted), then quantum computers are more powerful than classical ones.

Re:What could the NSA do with a quantum computer? by bo1024 on Friday June 28, 2013 @02:36PM (#5959623)
I'm not sure what you're referring to; everything in the parent post is correct. You are right that quantum and classical computers have the same "power" in terms of problems that can be solved, but it is also true that quantum computers may be able to computer certain functions faster than classical computers (using faster algorithms that don't run on classical computers).
Re:What could the NSA do with a quantum computer? by weinzierl on Friday June 28, 2013 @02:52PM (#5959698)
I'm referring to "They allow the running of some algorithms that normal computers can't physically run."

I understood this as, it's impossible to run some algorithms on a traditional computer. You can run Shor's algorithm on a Turing machine, albeit requiring a simulation of qbits. You can run it in javascript and in your browser if you like.

Re:What could the NSA do with a quantum computer? by mtp0101 on Friday June 28, 2013 @03:29PM (#5959887)
True, you can simulate the qbits, so the more precise statement would be they can execute some algorithms in a way that classical computers cannot and this gives them superior efficiency in some situations.
Re:What could the NSA do with a quantum computer? by _j5l3 on Friday June 28, 2013 @05:25PM (#5960429)
You're right. I should have specified that they can run certain algorithms with a runtime complexity impossible on a classical computer.
Re:What could the NSA do with a quantum computer? by sp332 on Friday June 28, 2013 @02:45PM (#5959659)
If you take into account the probability of breaking a given 4,096-bit RSA cipher before the heat death of the universe, it is correct. However this is an implementation detail, and a hardware problem to boot :p
Re:What could the NSA do with a quantum computer? by Tloewald on Friday June 28, 2013 @03:51PM (#5960008)
Rather mathematical response to a question requesting an answer for non mathematicians ;-)

Since Moore's Law is giving us one more bit of decryption per unit time every 1.5 years, 4096 * 1.5 years is probably going to precede the heat death of the universe handily. But 6000-or-so years of Moore's Law does tax credulity.

Re:What could the NSA do with a quantum computer? by weavejester on Friday June 28, 2013 @03:11PM (#5959815)
It's worth pointing out that other public-key encryption algorithms don't have the same vulnerability to quantum computers. It's also unlikely (but unproven) that quantum computers can solve NP-complete problems.
Re:What could the NSA do with a quantum computer? by jstalin on Friday June 28, 2013 @03:21PM (#5959855)
Such as AES and PGP?
Re:What could the NSA do with a quantum computer? by weavejester on Friday June 28, 2013 @04:26PM (#5960174)
AES is a symmetric encryption algorithm, which is to say it only has one key for both encryption and decryptions.

PGP is a piece of software, and not an algorithm. I believe it uses RSA and AES by default, but I could be wrong :)

AFAIK RSA, DSA, Diffie-Hellman, and ECC are all known to be vulnerable to Shor's Algorithm (which, granted, do make up a lot of the crypto in common use), but there are lesser-used algorithms like McEliece and NTRU that are not vulnerable.

That said, quantum computers are still very far from breaking modern cryptography. We're playing around with a handful of qubits, but to break something like a 4096 bit RSA key would take trillions of quantum gates.

Re:What could the NSA do with a quantum computer? by damarquis on Friday June 28, 2013 @04:11PM (#5960096)
AES yes, PGP no. Anything based on the difficulty of discrete logs is done for. There are 2 types that remain secure, schemes based on the difficulty of solving problems in lattices and problems in coding theory. Lattice based cryptography is particularly interesting since all known fully homomorphic encryption schemes use it. If this remains the case, and if FHE matures faster than quantum computers (and it actually has been as far as I can tell) that everyone will switch to lattice based cryptography making quantum computers a little less useful and interesting.
Re:What could the NSA do with a quantum computer? by mtp0101 on Friday June 28, 2013 @03:27PM (#5959878)
AES uses a symmetric key so it is not a public key system
Re:What could the NSA do with a quantum computer? by sp332 on Friday June 28, 2013 @02:19PM (#5959532)
Um, In certain conditions, atoms and subatomic particles can be in two places at once, or spin clockwise and anticlockwise at the same time. That means you can use a single atom to represent two binary digits. No, that's not how that works...

A qubit represents a single bit, in its two possible states: 1 and 0. Alone, the qubit could hold the probabilities that the bit will be a 0 or a 1 when you observe it. But for a quantum computer to be cool, you have to include entanglement!

When 2 qubits are entangled, they represent the probabilities of each of the 4 possibilities: 00, 01, 10, 11. If you only had the probability of each bit separately, say 10%/90% and 40%/60%, then the state would just be the multiplication of the two values: 4% for 00, 6% for 01, 36% for 10, 54% for 11. And if the first bit's probability changes, the second bit doesn't change. A simple multiplication will give you the new answer.

But entanglement means the probabilities are dependent on the values of other bits :) So say: if the first is a 0, the second has a 90% chance of also being a 0. And if the first is 1, the second only has a 50% chance of being a 0 or a 1. So if the first has a 20% chance of being a 0, that gives us 18% for 00, 2% for 01, 40% for 10 and 40% for 11. The values of the bits are linked to each other. It's not limited to a simple linear percentage; it can get more complicated by running the bits through various gates. So if the first bit's probability changes, you have to recalculate the new probabilities of B given A. That's when it would take exponential time using a classical computer, but it's all done instantaneously via entanglement.

Re:What could the NSA do with a quantum computer? by xanmas on Friday June 28, 2013 @02:40PM (#5959641)
I think they were trying to explain super-dense coding [1].

[1] http://en.wikipedia.org/wiki/Superdense_coding

Re:What could the NSA do with a quantum computer? by sp332 on Friday June 28, 2013 @02:43PM (#5959655)
Maybe. But even that requires 2 qubits.
Re:What could the NSA do with a quantum computer? by jzelinskie on Friday June 28, 2013 @01:23PM (#5959155)
Isn't this article pretty much fear mongering? There's no way the NSA has a reasonably powerful quantum computer and the proper algorithms to do anything. However, the question still remains once these devices are feasible and popular: how can they use it to process the data they've already collected?
Re:What could the NSA do with a quantum computer? by tptacek on Friday June 28, 2013 @01:50PM (#5959344)
To anyone who really understands the NSA's reputation, it seems like a uniquely silly kind of fear-mongering.

The traditional rap against the NSA is that they've had productive breaks on all our conventional crypto constructions for decades (a more refined, modern bit of innuendo about NSA is that they have a cookbook of surprising implementation faults; side channels, for instance, that we haven't thought of yet --- here it's worth remembering that very few people in the world truly understand x64 and ARM microarchitecture, and Venn diagram overlap of those people and cryptographers is microscopic).

Crypto implementors have worked under the assumption that most crypto is suspect, given that they're outspent 100:1 by NSA, for decades.

"Revelations" about quantum computing at NSA as applied to cryptography would change basically nothing about how the smart money would bet on NSA capabilities.

Re:What could the NSA do with a quantum computer? by ryandvm on Friday June 28, 2013 @01:33PM (#5959220)
I don't know about that. If a quantum computer is possible, you can rest assured that the U.S. defense complex has procured themselves one with their unfathomable budget.
Re:What could the NSA do with a quantum computer? by jzelinskie on Friday June 28, 2013 @01:49PM (#5959338)
Quantum computers are very well possible; whether they are feasible to data mine our large amounts of data is the actual question. You don't think the corporate entities in the tech industry would be just as invested? This is an area of research far too large to be concealed within the government. I wonder what the NSA program would look like if it wasn't for the surge in "big data" tooling after Google's MapReduce/GFS/BigTable papers.
Re:What could the NSA do with a quantum computer? by Xcelerate on Friday June 28, 2013 @01:32PM (#5959207)
If the NSA wanted to do something really interesting with a quantum computer, they would invest in scientific research instead.

Quantum computing allows specific types of quantum simulations to be performed in polynomial time instead of exponential time. The most powerful classical computers cannot get around what is known as the fermion sign problem.

I think super-accurate simulations would be very exciting; imagine a world where experiments are conducted using computers, but give the same exact results as their "real-life" counterparts.

Re:What could the NSA do with a quantum computer? by mturmon on Friday June 28, 2013 @03:43PM (#5959963)
"they would invest in scientific research instead"

They already are, and have been for many years now. Here's one example from a couple of years ago (https://www.fbo.gov/index?s=opportunity&mode=form&tab=core&i...) but there have been much larger-scale investments too.

Because of its coding and codebreaking relevance, this stuff is squarely within their charter. They are all over it.

Re:What could the NSA do with a quantum computer? by nissimk on Friday June 28, 2013 @01:07PM (#5959068)
What's the deal with this Dwave device?? Is it the real thing?

According to wikipedia there is a "history of controversy." [1] Can anyone here provide more details?

http://en.wikipedia.org/wiki/D-Wave_Systems#History_of_contr...

Re:What could the NSA do with a quantum computer? by Zweihander on Friday June 28, 2013 @01:30PM (#5959193)
From a recent HN post: http://www.wired.com/wiredenterprise/2013/06/d-wave-quantum-...

It looks like it's the real thing in terms of being able to do a lot of useful quantum calculations that can't be done as easily with classical computers. It's not the full deal in terms of being able to do everything a 'true' quantum computer should be able to do - sounds like it might be able to help the NSA out with their data problem though.

Re:What could the NSA do with a quantum computer? by izend on Friday June 28, 2013 @01:31PM (#5959206)
The Dwave device is definitely real, it is a specific type of quantum computer which is called adiabatic quantum computer and can be used to efficiently solve optimization problems [1].

Some people believe the Dwave device shouldn't be labeled as a "Quantum Computer" because the general community typically uses the Quantum Computer label for a device which could compute NP-Complete problems in linear time instead of exponential time, the Dwave device cannot do this.

[1] https://en.wikipedia.org/wiki/Optimization_problem

Re:What could the NSA do with a quantum computer? by arjunnarayan on Friday June 28, 2013 @01:53PM (#5959369)
Quantum computing is not known to allow you to compute NP hard problems in linear (or polynomial) time. Specifically, the relationship between BQP and NP is open, but widely believed to be not equal (just as the general community's priors are biased towards P \neq NP). Here's a hint as to why: http://en.wikipedia.org/wiki/Grover%27s_algorithm#Optimality

If you are interested in what exactly the D-Wave computer is doing, http://www.scottaaronson.com/blog/?p=1400 is a good source.

Re:What could the NSA do with a quantum computer? by gizmo686 on Friday June 28, 2013 @01:55PM (#5959385)
Quantum computers cannot solve NP-Complete problems in sub exponential time (we think). If we could measure the quantom state then they would be able to. However there is an exponentially small chance that when we make the measurement we will see the currect answer instead of no result (or simmiliar). Effectively, we need to repeat the computation an exponential amount of times to arrive at the answer.

There is a genneral algorithm that could solve many (all?) NP-Complete problems in the square root of the time it takes classical algorithms, but that is still exponential.

Re:What could the NSA do with a quantum computer? by lucb1e on Friday June 28, 2013 @03:40PM (#5959946)
This might sound conspiracy-theory-like, but I think we should assume they have technology a few years ahead of what we know. It might be best to assume they do actually have a working quantum computer, perhaps not breaking all existing crypto yet, but certainly something powerful.
Re:What could the NSA do with a quantum computer? by mtgx on Friday June 28, 2013 @12:47PM (#5958940)
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).

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.