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