army/NSA are interested in QC

[Eugen Leitl]

(good luck)

http://www.networkworld.com/community/node/34597

NSA and Army on quest for quantum physics jackpot

By Layer 8 on Tue, 10/28/2008 - 1:35pm.

Sounds like a dangerous combination.  The US Army Research Office and the
National Security Agency (NSA) are together looking for some answers to their
quantum physics questions.

Specifically the scary couple is soliciting proposals to achieve three broad
goals:

-develop new quantum computing algorithms for hard computational problems;

-characterize the efficiency of candidate quantum algorithms;

-develop insights into the power of quantum computation and consider issues
of quantum complexity and computability.

    The announcement went on to say proposals for research should devise
specific quantum algorithms to solve mathematically and computationally hard
problems from such diverse fields as algebra, number theory, geometry,
analysis, optimization, graph theory, differential equations, combinatorics,
topology, logic, and simulation.

    The Army said quantum algorithms that are developed should focus on
constructive solutions 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 or problems exactly were.

    Other specifics of that the NSA and Army are looking for are as follows:

    "To characterize the efficiency of candidate quantum algorithms, metrics
must be developed to quantify the performance of quantum algorithms relative
to their classical analogs. The problems to which they are being applied must
have well-defined inputs, and well-defined outputs, along with a well-defined
statement of what exactly is being computed. A full accounting of all
computational resources must be made including such things as numbers of
qubits, numbers of quantum gates, amount of memory being used, amounts of
classical pre-computation and post-computation, probability of success, and
number of times the algorithm must be run.

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

     The agencies went on to say they expect to award in March 2009 multiple,
one to three year awards of less than $200K per year.

  Quantum physics has long been an area of enormous government interest. In
March, the Defense Advanced Research Projects Agency said it was looking for
innovative research proposals in the intriguing area of quantum entanglement
--  a developing component of quantum physics that looks at the behavior
between atoms and  photons that could ultimately play a key role in
developing security, unbelievably fast networks and even teleportation.
DARPA's program, called Quantum Entanglement Science and Technology (QuEST)
has the lofty goal of developing revolutionary advances in the fundamental
understanding of quantum information science, DARPA said.

DARPA last month put out a research request it calls Mathematical Challenges,
that has the mighty goal of "dramatically revolutionizing mathematics and
thereby strengthening DoD's scientific and technological capabilities." The
challenges are in fact 23 questions that if answered, would offer a high
potential for major mathematical breakthroughs, DARPA said.

And just this month researchers at the US National Institute of Standards and
Technology (NIST) have demonstrated a technique that could make quantum
cryptography significantly cheaper to implement, moving it nearer to possible
commercial acceptance.  The technique is aimed at cutting the cost of
equipment needed for quantum key distribution (QKD), designed to distribute
cryptographic keys using a secure system based on the principles of quantum
mechanics.