Quantum-Inspired Classical Computing (QuICC)   4

Background
The DARPA Microsystems Technology Office (MTO) is soliciting innovative proposals for the research and development of quantum-inspired solvers for hard optimization problems and for the demonstration of feasibility in achieving at least two orders of magnitude improvements in computational efficiency over all existing techniques.

Work Details
The program objectives are to deliver prototype systems demonstrating at least 50X improvement in computational efficiency for intermediate problem sizes and to show the feasibility of attaining (through post-program engineering refinements) at least 500X improvement in computational efficiency for mission-scale problem sizes when compared to the computational efficiency of conventional state-of-the-art solvers. The optimization problems targeted by the QuICC program are nondeterministic polynomial-time (NP)-hard and have computational resource costs that scale at least cubically with the number of variables for the best-known heuristic and approximate algorithms when run on conventional computers. The specific program goals apply to benchmark problem classes such as Boolean Satisfiability (SAT), Maximum Likelihood Estimation (MLE), Maximum-Fault Minimum-Cardinality (MFMC) sampling, and Mixed-Integer Linear Programming (MILP).

Period of Performance
The QuICC program is a 60-month, three-phase effort with a 24-month Phase 1 (base), 18-month Phase 2 (option), and 18-month Phase 3 (option).