Department of Defense (DOD) must solve many complex optimization problems to enable mission capabilities – from determining the most efficient way to distribute supplies to minimizing warfighters’ exposure to hostile forces. Solving these intricate scenarios is difficult, largely owing to the limitations of existing computing resources. Today, many optimization problems are solved on conventional computers running both heuristic and approximate algorithms, extracting the best solutions allowed by the limited time and energy that is available.
Many Department of Defense (DoD) mission capabilities are limited by the available computing resources required to solve hard optimization problems within tactically relevant timescales subject to field constraints (e.g., power). Quantum computing is widely promoted as a potential solution for this class of problems; however, there is no direct evidence indicating that this technology will ever be relevant for size, weight, and power (SWaP) constrained environments.
There are two major approaches to quantum computing systems – annealing and the gate model. Gate model systems actually require longer coherence times, more qubit control, etc. than annealing. The annealing model is especially useful for solving problems can be expressed as an energy landscape, and the solution to the problem is the lowest point in that landscape such as minimizing error in a voice recognition system, controlling risk in a financial portfolio, or reducing energy loss in an electrical grid. In comparison, a universal quantum computer is one that, in theory, can perform any computation exponentially faster than a classical computer.
In a hybrid quantum computer, the quantum device will act as a quantum co-processor that works with a classical device, which will include circuits for control and pre- and post-processing. “A hybrid quantum computer exploits the best of both worlds as it seeks to have the best parts of a quantum device and a classical supercomputer work together.” Moreover, the algorithms that run on a hybrid quantum computer are more robust towards decoherence, and therefore reduce the need for quantum error correction.
DARPA launched the Quantum-Inspired Classical Computing (QuICC), a $58 million program in Oct 2021 with the aim to develop hybrid systems for the Department of Defense to overcome optimization problems that could affect mission capabilities. It seeks to integrate analog hardware with digital logic processes to create QI solvers for dynamic system emulation.
Detailed benchmarking and analysis of quantum computing has inspired the development of promising new algorithmic and hardware techniques that avoid the hardest technical challenges facing quantum computing while delivering significant advantages over prior (digital computing) techniques. Of particular interest are Quantum-Inspired (QI) solvers. QI solvers are hybrid: they are classical, mixed-signal systems consisting of analog hardware and digital logic. The analog hardware typically emulates interacting dynamical systems (e.g., magnetic spins). The digital logic processes the results from the analog hardware to obtain the solution to the optimization problem.
Prototype QI solvers are projected to outperform both conventional and quantum computers by over a factor of 10,000 – but have only been demonstrated using small (<100 bit), boutique problems (e.g., MAX-CUT) that are specifically tailored to existing architectures and do not predict performance for large-scale, mission-relevant problems. In driving to larger scales and more relevant problem classes, current implementations face analog hardware challenges due to restrictive connectivity between dynamical systems, and also due to limited control precision. Alternatively, when problem decomposition is used to solve larger problems on smaller analog hardware, digital resource requirements suffer excessive growth from the large number of repetitions needed for convergence.
To date, prototype QI solvers have been demonstrated using small, “boutique” problems tailored to existing architectures. To tackle larger scale, more DOD-relevant problem classes, the QuICC program must address multiple technical obstacles. These include analog hardware challenges that restrict connectivity between dynamic systems, as well as the prohibitive growth in digital resources with problem size, that prevent the expansion of existing quantum-inspired classical solvers from expanding covering large DOD-relevant cases.
To overcome the challenges, the QuICC program seeks innovative solutions with algorithmic and analog hardware co-design, and application-scale benchmarking techniques. Researchers will work across two technical areas to achieve the target objectives. The first area focuses on developing solver algorithms and creating a framework for assessing the potential performance of QI solvers. The second aims to develop QI dynamical system hardware as well as validated models of their performance.
Progress on QuICC will be measured against a set of key metrics, including computational efficiency, which is characterized by the energy expended to obtain a high-quality solution to a given problem. QuICC prototype systems will target a 50X reduction in energy for intermediate problem sizes, and show the feasibility of a 500X reduction for mission-scale problem sizes. A broad agency announcement posted on SAM.gov stated that the agency expects to award $17 million for the first technical area of the project and $41 million for the second area. Proposals are due Dec. 8th.
The Microsystems Technology Office at DARPA seeks innovative proposals for the research and development of quantum-inspired (QI) solver systems that solve hard optimization problems at mission-relevant sizes within tactically-relevant timescales. QI solvers are hybrid: they are classical, mixed-signal systems consisting of analog hardware and digital logic. The analog hardware typically emulates interacting dynamical systems, and the digital logic processes the
analog results to obtain high quality solutions to the optimization problem. QuICC seeks to develop QI solvers and benchmark potential mission-scale performance.
The program objective is to deliver prototype systems that demonstrate at least 50X improvement in computational efficiency for intermediate problem sizes and to show the feasibility of attaining at least 500X improvement in computational efficiency for mission-scale problem sizes.
QuICC seeks to develop QI solvers and benchmark potential mission-scale performance. A key metric will be the computational efficiency, which is characterized by the energy expended to btain a high-quality solution to a given problem, i.e., a desired solution would be of the same (or better) quality as the best of the known solutions obtained from conventional state-of-the-art (cSoA4) solvers. Smaller energy-to-solution means greater computational efficiency. 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 cSoA solvers. To overcome or obviate the scaling challenges, the QuICC program seeks innovative solutions with algorithmic and analog hardware co-design, alongside applicationscale benchmarking techniques.
The optimization problems targeted by the QuICC program are nondeterministic polynomialtime (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. Furthermore, the selected problem classes cover a range of mission-relevant applications that are known to have different types of overhead costs when mapped to existing QI solvers. These benchmark problem classes include: Boolean Satisfiability (SAT), Maximum Likelihood Estimation (MLE), Maximum-Fault Minimum-Cardinality (MFMC) sampling, and Mixed-Integer Linear Programming (MILP). At least one additional problem class (referred to as “performer proposed problem” or PPP) is expected to be introduced by the proposer.
The specific program goals, which apply to all benchmark problem classes listed above, are:
- A prototype solver system demonstrating at least 50x improvement in computational efficiency over all known (cSoA) methods for benchmark problems of size 1,000-3,000 problem variables.
- Benchmarking results and analysis showing feasibility of attaining (through post-program engineering refinements) at least 500x improvement in computational efficiency over cSoA, for benchmark problems of size 10,000-30,000 problem variables in fieldable systems.
The QI solvers to be developed are mixed-signal systems consisting of two subsystems:
- Analog hardware incorporating dynamical systems that facilitate identification of good solutions to the problem;
- Digital logic performing computations to convert problems into computational models, interface with the analog subsystem, and process results from analog subsystem to obtain the solution to the optimization problem.
The QuICC program seeks to advance capabilities of the QI solver systems in problem sizes and types of problem classes toward mission-relevant applications while improving computational efficiency.
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). The program milestones are designed to progressively advance the scaling of QI solver technology toward mission-relevant problems and sizes, while addressing the underlying co-risks of excessive auxiliary digital computations (TC2) and unrealizable analog hardware requirements (TC1).