Development of Quantum Algorithms

The U.S. Army Research Office (ARO) together with the National Security Agency
(NSA) is soliciting proposals to develop new quantum computing algorithms for hard
computational problems, develop insights into the power of quantum computation, and consider
issues of quantum complexity and computability.
Proposals for research in quantum algorithms should primarily be to devise novel
quantum algorithms for solving 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. 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. Complexity analysis such as upper and lower bounds on algorithms, including
developing new methodologies for deriving such bounds, is encouraged. Noisy intermediate
scale quantum (NISQ) computation produces approximate solutions. The error in these solutions
depends upon the noise. Complexity analysis of quantum algorithms for such approximate
solutions produced by NISQ machines is of interest.
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. Although quantum
algorithm proposals may consider general architectural constraints (e.g. nearest neighbor only
gates) for implementing algorithms, they should otherwise concentrate on developing the
algorithm. Quantum algorithm proposals may consider computational models other than the
circuit model (e.g. the adiabatic model).
To characterize the efficiency of candidate quantum algorithms, metrics must be
developed to quantify the performance of quantum algorithms relative to their classical
analogues. 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; typical units include
numbers of qubits, numbers of quantum gates, runtime of the algorithm, amount of memory
being used, amounts of classical pre-computation and post-computation, and probability of
success. Worst-case analyses of the algorithms are preferable to average case analyses, but if
average case analysis is to be used in an efficiency measure, the distribution of all cases must be
made explicit as well as the placement of average cases within this distribution. In addition, proposals that study the algorithmic limitations of fully functional quantum computers will be considered as long as similar performance metrics are specified and quantified.