NSA and Army On Quest For Quantum Physics Jackpot 110
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.'"
Re:So... (Score:3, Informative)
Two problems:
1.) They wouldn't tell us. They wouldn't even tell us this subtly.
2.) They would have no lack of work for their shiny new toy, and the algorithm exists already. See Shor's algorithm [wikipedia.org].
Re:It's about time (Score:2, Informative)
You don't remember your theory correctly. Most QM researchers believe that NP complete problems -cannot- be solved in polynomial time, using a QM computer. I think that particular paper is now considered dubious, to put it mildly.
The real open problem that might be accessible to a QM computer is graph isomorphism.