The U.

S.

Army Research Office (ARO) together with the National Security Agency(NSA) is soliciting proposals to develop new quantum computing algorithms for hardcomputational problems, develop insights into the power of quantum computation, and considerissues of quantum complexity and computability.Proposals

credit:

for research in quantum algorithms should primarily be to devise novelquantum algorithms for solving mathematically and computationally hard problems fromsuch diverse fields as algebra, number theory, geometry, analysis, optimization, graphtheory, differential equations, combinatorics, topology, logic, and simulation.

Quantumalgorithms that are developed should focus on constructive solutions for specific tasksand on general methodologies for expressing and analyzing algorithms tailored tospecific problems.

Complexity analysis such as upper and lower bounds on algorithms, includingdeveloping new methodologies for deriving such bounds, is encouraged.

Noisy intermediatescale quantum (NISQ) computation produces approximate solutions.

The error in these solutionsdepends upon the noise.

Complexity analysis of quantum algorithms for such approximatesolutions produced by NISQ machines is of interest.Investigators should presuppose the existence of a fully functional quantum computer andconsider what algorithmic tasks are particularly well suited to such a machine.

Anecessary component of this research will be to compare the efficiency of the quantumalgorithm to the best existing classical algorithm for the same problem.

Although quantumalgorithm proposals may consider general architectural constraints (e.g.

nearest neighbor onlygates) for implementing algorithms, they should otherwise concentrate on developing thealgorithm.

Quantum algorithm proposals may consider computational models other than thecircuit model (e.g.

the adiabatic model).To characterize the efficiency of candidate quantum algorithms, metrics must bedeveloped to quantify the performance of quantum algorithms relative to their classicalanalogues.

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

A full accounting of all computational resources must be made; typical units includenumbers of qubits, numbers of quantum gates, runtime of the algorithm, amount of memorybeing used, amounts of classical pre-computation and post-computation, and probability ofsuccess.

Worst-case analyses of the algorithms are preferable to average case analyses, but ifaverage case analysis is to be used in an efficiency measure, the distribution of all cases must bemade 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.