NSA and Army On Quest For Quantum Physics Jackpot

coondoggie sends this excerpt from NetworkWorld: "The US Army Research Office and the National Security Agency (NSA) are together looking for some answers to their quantum physics questions. ... The Army said quantum algorithms that are developed should focus on constructive solutions [PDF] for specific tasks, and on general methodologies for expressing and analyzing algorithms tailored to specific problems — though they didn't say what those specific tasks were ... 'Investigators should presuppose the existence of a fully functional quantum computer and consider what algorithmic tasks are particularly well suited to such a machine. A necessary component of this research will be to compare the efficiency of the quantum algorithm to the best existing classical algorithm for the same problem.'"

What's the point..

[LingNoi]

That's probably what they're trying to figure out with this.

Why should we fund this? I mean look at the depression we're all in, they're obviously trying to make budget cuts and aren't sure if they should drop quantum computing.

Re:So...

[Anonymous Coward]

It's just as possible that they don't have one but are working on one. Their goal may be to have a supply of algorithms already available by the time they complete their development of a quantum computer.

Another possibility, which was mentioned by someone else above, is that they may be trying to decide whether they should try to build a quantum computer.

Re:What's the point..

[MrMista_B]

Also likely, from this 'Investigators should presuppose the existence of a fully functional quantum computer' is that they /already have/ a fully functional quantum computer, and are just trying to figure out what to do with the darned thing.

Re:wait..

[FrangoAssado]

Can't a quantum computer [...] break any encryption instantly by only actually arriving at the destination assigned?

No. Quantum computers can theoretically solve some problems faster than classical computers. Among these (and perhaps most famously) is factoring -- see Shor's Algorithm [wikipedia.org]. Fast factorization breaks RSA encryption, which is what everyone uses.

It is not known whether quantum computers can in general solve problems exponentially faster than classical ones. Further, it is not known for most important problems how to take advantage of quantum computers to achieve dramatic speedups (or even if it's possible). It seems that NSA and the Army want to know more about this.

I'm more interested in its promise for simulation

[Anonymous Coward]

I think cracking codes is one of the least meaningful purposes quantum computers will have. Simulation of quantum systems, for basic research as well as for engineering, will make a much bigger impact. Yet people always seem to focus on the promise it holds for code-cracking. I think most people just don't appreciate how important quantum mechanics has been in creating the technologies that are all around us in the modern world. Being able to more 'naturally' simulate these systems that rely on quantum phenomena could potentially open up whole new fields of study.

Re:It's about time

[darkstar949]

If I remember my theory correctly, then any of the NP-Complete problems would most likely be solvable in polynomial time using quantum computers. A couple of the problems have more obvious military uses than others; for example, the knapsack problem would allow for the optimization of logistics and it looks like there is already a quantum algorithm of knapsack problem. [sciencelinks.jp]