HR001121S0041-Amendment-01.pdf

HR001121S0041

Broad Agency Announcement Quantum-Inspired Classical Computing (QuICC)

Microsystems Technology Office

HR001121S0041

28 September 2021

Amendment 01 As amended November 15, 2021

Summary of Amendment 01: Extends the deadline for Full Proposal Submission.

Table of Contents

PART I: OVERVIEW INFORMATION

PART II: FULL TEXT OF ANNOUNCEMENT

I. Funding Opportunity Description A. Background B. Program Description C. Program Structure D. Technical Areas E. Schedule/Milestones F. Deliverables G. Government Furnished Equipment/Property/Information H. Intellectual Property

II. Award Information A. General Award Information B. Fundamental Research

III. Eligibility Information A. Eligible Applicants

1. Federally Funded Research and Development Centers (FFRDCs) and Government Entities

2. Other Applicants B. Organizational Conflicts of Interest C. Cost Sharing/Matching D. Other Eligibility Criteria

1. Collaborative Efforts IV. Application and Submission Information

A. Address to Request Application Package B. Content and Form of Application Submission

1. Abstract Format

2. Full Proposal Format

3. Proprietary Information

4. Security Information

a. Program Security Information

b. Controlled Unclassified Information (CUI)

i. CUI Proposal Markings

ii. CUI Submission Requirements

c. Unclassified Submissions

5. Disclosure of Information and Compliance with Safeguarding Covered Defense

Information Controls

6. Human Subjects Research (HSR)/Animal Use

7. Approved Cost Accounting System Documentation

8. Section 508 of the Rehabilitation Act (29 U.S.C. § 749d)/FAR 39.2

9. Small Business Subcontracting Plan

10. Intellectual Property

a. For Procurement Contracts

b. For All Non-Procurement Contracts

11. Patents

12. System for Award Management (SAM) and Universal Identifier Requirements

13. Funding Restrictions

C. Submission Information

1. Submission Dates and Times

a. Abstract Due Date

b. Full Proposal Date

c. Frequently Asked Questions (FAQ)

2. Abstract Submission Information

3. Proposal Submission Information

a. For Proposers Requesting Technology Investment Agreements

b. For Proposers Requesting Contracts or Other Transaction Agreements

c. Classified Submission Information

4. Other Submission Requirements

V. Application Review Information A. Evaluation Criteria

1. Overall Scientific and Technical Merit

2. Potential Contribution and Relevance to the DARPA Mission

3. Cost Realism

B. Review and Selection Process

1. Review Process

2. Handling of Source Selection Information

3. Federal Awardee Performance and Integrity Information (FAPIIS)

VI. Award Administration Information A. Selection Notices

1. Abstracts

2. Proposals

B. Administrative and National Policy Requirements

1. Meeting and Travel Requirements

2. Solicitation Provisions and Award Clauses, Terms and Conditions

3. Controlled Unclassified Information (CUI) and Controlled Technical Information

(CTI) on Non-DoD Information Systems

4. Representations and Certifications

C. Reporting D. Electronic Systems

1. Wide Area Work Flow (WAWF)

2. i-Edison

3. Vault

4. DARPA Embedded Entrepreneurship Initiative (EEI)

VII. Agency Contacts VIII. Other Information

A. Proposers Day B. Protesting

ATTACHMENT 1: Cost Volume Proposer Checklist ATTACHMENT 2: Proposal Summary Slide Template ATTACHMENT 3: QuICC Controlled Unclassified Information (CUI) Guide

PART I: OVERVIEW INFORMATION

Federal Agency Name: Defense Advanced Research Projects Agency (DARPA), Microsystems Technology Office (MTO)

Funding Opportunity Title: Quantum-Inspired Classical Computing (QuICC) Announcement Type: Initial Announcement Funding Opportunity Number: HR001121S0041 Catalog of Federal Domestic Assistance Numbers (CFDA): Not applicable Dates: (All times listed herein are Eastern Time) o Posting Date: September 28, 2021 o Proposers Day: October 1, 2021 o Abstract Due Date: October 25, 2021 o FAQ Submission Deadline: December 21, 2021 o Proposal Due Date: January 12, 2022 o Estimated period of performance start: May 2022

Concise description of the funding opportunity: 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.

Anticipated Funding Available for Award: Approximately $58M of total funding is anticipated for awards made against this BAA, with a distribution of o $17M for Technical Area 1 (TA1) o $41M for Technical Area 2 (TA2)

Anticipated individual awards: Multiple awards are anticipated.

Anticipated funding type: 6.2 Types of instruments that may be awarded: Procurement contract or other transaction.

Agency contact:

o Dr. Bryan Jacobs, Program Manager BAA Coordinator: HR001121S0041@darpa.mil

DARPA/MTO

ATTN: HR001121S0041

675 North Randolph Street Arlington, VA 22203-2114 mailto:name@darpa.mil

PART II: FULL TEXT OF ANNOUNCEMENT

I. Funding Opportunity Description

The Defense Advanced Research Projects Agency (DARPA) often selects its research efforts through the Broad Agency Announcement (BAA) process. This BAA is being issued, and any resultant selection will be made, using the procedures under Federal Acquisition Regulation (FAR) 6.102(d)(2) and 35.016 and 2 C.F.R. § 200.203. Any negotiations and/or awards will use procedures under FAR 15.4, Contract Pricing. Proposals received as a result of this BAA shall be evaluated in accordance with evaluation criteria specified herein through a scientific review process.

DARPA BAAs are posted on the SAM website, under the Contract Opportunities link, at https:// sam.gov/. The following information is for those wishing to respond to the BAA.

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. Proposed research should investigate innovative approaches that enable revolutionary advances in science, devices, or systems. Specifically excluded is research that primarily results in evolutionary improvements to the existing state of practice. The QuICC program will focus exclusively on classical, hybrid (mixed-signal) solver systems; technologies such as all-digital solvers or quantum computing are not within the scope of this program.

A. Background

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.

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 conventional1 and quantum2 computers by over a factor of 10,000 - but have only been demonstrated using small (<100 bit), boutique problems (e.g., MAX-CUT)3 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.

B. Program Description

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 obtain 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 application-scale benchmarking techniques.

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

1 Y. Haribara, et al. (2016) In: Lecture Notes in Physics, vol. 911, Springer, Tokyo; arXiv:1501.07030 [quant-ph] 2 K. Sankar, et al. (2021), arXiv:2105.03528 [quant-ph] 3 R. Hamerly et al., Sci. Adv. 5, eaau0823 (2019) 4 Algorithms using only digital logic run on conventional hardware, e.g., CPUs, GPUs, or FPGAs; see also footnote 21 and 22

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. There are several rudimentary, proof-of-concept demonstrations of solvers5 or components,6 but scaling solver capabilities toward larger scale, more complex applications have met the following limitations:

Analog hardware limitations. These are related to the topology of the dynamical systems (i.e., the type of interactions and the connectivity graph between the dynamical systems) and how finely the interactions need to be controlled. Current systems only implement pairwise (quadratic) interactions, which means higher-order terms (cubic and above) in the original problem cannot be directly mapped to the analog hardware. The structure, or degree of connectivity between dynamical systems, also limits the class of problems that can be efficiently mapped to the analog hardware. Finally, the precision required to set the interaction strengths (or coupling values) between dynamical systems should increase to match the system size, otherwise these solvers are essentially finding solutions to the wrong problem. All of these analog hardware issues currently limit the size and complexity of problems that can be solved directly on the analog subsystems.

Digital resource limitations and serialized problem decomposition. Mission-relevant problems are typically too big to fit on existing analog hardware. Consequently, larger problems are currently solved using decomposition techniques that run subproblems of the original problem on the analog hardware sequentially, i.e., in series. The entire sequence is then repeated until the desired solution quality is achieved. Excessive repetition of this serial process currently limits the overall computational efficiency of QI solvers.

These limitations lead to the following technical challenges to scaling up solver capabilities to mission-relevant problem classes and sizes. Performers in this program should be prepared to address the technical challenges (TCs), which include:

5 C. C. McGeoch, Theor. Comput. Sci., 816, pp. 169-183 (2020) 6 See footnote 1

TC1: Scaling Analog Hardware Advantages to Mission Relevant Problems.

Existing QI solver techniques demonstrate that performance gains diminish exponentially as the problem complexity and number of interacting dynamical systems increase. The problem is further exacerbated by the use of pair-wise only interactions and by limited connectivity, both of which inflate the number of dynamical systems that must be used to encode the original problem in the analog hardware. For example, the number of dynamical system elements typically grows as O(N2) for problem embedding,7 where N characterizes problem size. The resulting implementation features a number of dynamical system elements that typically exceeds the number of problem variables by two orders of magnitude. Also, because the required analog control precision needs to increase with the number of dynamical systems, this inefficiency currently forces the corresponding circuit resources to grow according to a high-order power law in the problem size.

Overcoming this TC and achieving the program goals will necessitate the development of techniques wherein the dynamical system requirements grow linearly (or sub-quadratically) with the number of problem variables – for all problem classes up to 1,000 variable problems – with a corresponding improvement in computational efficiency.

TC2: Limiting the Growth of Digital Computations with Problem Size

For current QI solver approaches, the required digital computing resources currently grow exponentially with problem complexity and size, quickly overwhelming any advantage of the analog platform. This poor scaling is principally driven by the mismatch between: a) the structure of the optimization problem, and b) the topology of the analog systems. Optimization problems that are most efficiently expressed in terms of higher-order interactions require extensive (i.e.

exponentially7 growing) digital resources to be mapped to the analog platforms.

Significant O(1,000x) improvements in the total computing efficiency can only be achieved if the digital resources grow more slowly than in conventional cSoA solvers, which scale at least cubically with problem size. This implies that the digital computing resources needs to be limited to roughly 0.1% of their equivalent for conventional approaches at mission scale to achieve the program goals.

TC3: Realizing Predictive Benchmarks at Prototype System Scales

It is vital that an approach’s mission-scale performance be accurately predictable by its performance at intermediate scales. The problem is that early-phase platforms do not have enough dynamical systems to directly run full application-scale benchmark problems. State-of-the-art performance claims are widely8 based on problem classes (e.g., MAX-CUT) that are trivial to map into available systems, thereby obfuscating both scaling challenges described in TC1 and TC2.

7 D. Venturelli, et al., Phys. Rev. X 5, 031040 (2015) 8 Z. Wang, et al., Phys. Rev. A 88, 063853 (2013); Y. Yamamoto, et al., Appl. Phys. Lett. 117, 160501 (2020); J.

Chou, et al., Scientific Reports, 9:14786 (2019); T. Wang and J. Roychowdhury, arXiv:1903.07163 [cs.ET]; S.

Dutton, et al., Nat. Electron. 4, 502-512 (2021)

To overcome this challenge and achieve the program goals will necessitate the development of predictive benchmarks that can be used to quantitatively extrapolate performance gains to platforms with 10x more dynamical systems.

The QuICC program will pursue advanced hybrid solver technologies to overcome or obviate these technical challenges. Proposers will be challenged to demonstrate their understanding of these technical challenges and clearly articulate their technical approaches to scale up the solver capabilities to mission-relevant scales. The end of program goal is to demonstrate prototype 1,000 variable-class solver systems with 50x improvement in computational efficiency over conventional state-of-the-art and will also show the feasibility of attaining (through post-program engineering improvements) a 500x improvement for mission-scale problems.

Details of the program structure are in the following section. DARPA encourages integrated, interdisciplinary teams with expertise in both algorithms and analog hardware technologies in order to achieve all QuICC program goals.

C. Program Structure

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

The program comprises two technical areas (TAs): TA1 – Solver Co-design and Mission Relevant Benchmarking and TA2 – Analog Hardware Prototyping. The timeline and structure of individual technical areas are depicted in Figure 1. It is expected that fewer performers will be funded (options exercised) to participate in Phase 2 and Phase 3 of the program. Phase 2 and 3 options may be exercised, at the Government’s sole discretion, based on technical progress measured against the metrics and milestones defined in the BAA and on funding availability.

Proposers must respond to all program areas, submitting a full proposal to address both technical areas. Both technical areas should be costed separately, with separate Statement of Work (SoW) tasks. Proposers may propose more than one core technology approach for TA2, as described in the following section.

Figure 1. Program Phase Structure and Technical Areas

D. Technical Areas

This QuICC program BAA is soliciting comprehensive research proposals for efforts in two technical areas:

Technical Area 1 (TA1): Solver Co-design and Mission Relevant Benchmarking

Technical Area 1 encompasses the efforts to develop full solver stacks (excepting the physical analog hardware; see TA2) to address the development of solver algorithms and system hardware performance models and estimates. TA1 will also address advanced research concepts to generate benchmarks that are predictive of larger-scale system performance, for all program-specified problem classes, when run on reduced-scale hardware.

Co-design Framework Proposed approaches should include the development of a full solver stack (excepting the analog hardware; see TA2) for the algorithms of the program-specified problem classes, and should also include the development of predictive benchmarking techniques. For example, a full QI solver stack could comprise:

Mapping problems to computational models Pre-processing with problem decomposition capabilities Embedding problem variables in analog hardware Interfacing with analog hardware, sampling, and readout Post-processing

Proposers should note that the foregoing example contains what might comprise a full solver stack for some historical or even recent QI solvers, but proposers should not conclude that QuICC seeks to limit itself to any historical or recent QI solver concept. Rather, QuICC strongly encourages proposers to propose those QI solver concepts that have the best likelihood of meeting the QuICC milestones. The definition of QI solver has intentionally been made very broad here to give proposers the freedom to formulate concepts that have exceptional potential.

The proposal should include a description of the initial hardware performance model to help illustrate the proposer’s approach to the analog hardware simulator. To enable efficient IV&V on the program deliverables and tight coordination between the two TAs, proposed solver frameworks should incorporate an analog hardware simulation capability that accepts machine-readable hardware performance models (potentially from other performers or the Government team) for the purposes of performance projection analysis and verification. In the interests of full solver integration, the proposed TA1 framework should be compatible with TA2 analog hardware through standardized control and readout interface protocols. Program performers will be expected to establish (collaboratively, with Government team mediation) open, nonproprietary, standardized machine-readable formats for hardware performance models, and also the open, nonproprietary control and readout interface protocols.

Proposals should provide a concise discussion of the technical approach and rationale to achieve the TA1 milestones. Proposals must address how the proposed approach overcomes or obviates the technical challenges that limit digital computing resource growth. Consideration should be given to all of the SoA technical limitations: topology, control precision, and serial problem decomposition.

Proposals should also include estimates for the computational requirements of proposed simulations and benchmarking for Government Team planning purposes.

Within TA1, progress towards the computational efficiency goal will be measured by projected gains in computational efficiency, at specified problem sizes, relative to cSoA solvers for program-specified benchmarks. TA1 metrics include: system computational efficiency and digital computational efficiency. System computational efficiency is the computational efficiency of the solver platform, taking into account the total energy-to-solution associated with the entire platform. Digital computational efficiency is the computational efficiency (characterized by the energy-to-solution) of only the digital logic. Digital computational efficiency, when compared to cSoA, is always compared to the total energy-to-solution of the cSoA system.

Predictive Benchmarking The proposed approach to develop predictive benchmarks should produce benchmark instances for all phase-specific problem classes, according to the schedule found in Table 1. As the size of the analog hardware increases from phase to phase, the benchmarks will serve to predict the performance of the solver system for the next phase, using current phase hardware sizes.

Progress toward the benchmarking goal will be measured by benchmark gain. Benchmark gain is the factor by which the required hardware size can be reduced while still providing faithful performance predictions (i.e., energy to solution) for the target hardware scale. For example, a benchmark that can provide performance predictions for a 1,000-variable problem – while running on hardware that can accommodate only 200 problem variables – has a benchmark gain of 5. In order to guarantee a useful performance prediction, the solution to the benchmark should have a quality of 99% or greater relative to the best of the known solutions, at >90% confidence level. Confidence levels are to be estimated through simulation and analysis.

TA1 Objectives with Key Milestones by Phase The objectives of TA1 for each phase are listed below. In order to reach the TA1 objectives, the program structure is designed to enable tight coordination between phases within TA1, and also integration with TA2.

Phase 1 (Base) – Solver co-design framework development and proof-of-concept predictive benchmarking: TA1 will focus on development of a co-design analysis framework that can estimate all analog hardware (TC1) and ancillary digital computing (TC2) resource costs through full system simulation.

o Phase 1 Problem Classes: The performance estimates will be performed on Government provided instances of the Boolean Satisfiability (SAT) problem, and on performer provided instances of a Performer Proposed Problem (PPP).

o Current System Performance Estimates: the solver framework will use Phase 1 validated hardware performance models from TA2 (at the 50-problem variable hardware size) to establish baseline system performance estimates through simulations for the Phase 1 problem classes at problem sizes of 50 problem variables.

o Projected System Performance Estimates: the solver framework will use projected hardware performance models from TA2 (at the 200-problem variable hardware size) to estimate performance for Phase 2 through simulation. The result will be a projected digital computational efficiency for Phase 1 problem classes at the Phase 2 problem size of 200 problem variables. The associated milestone is an improvement in digital computational efficiency of at least ten-fold (10x) over cSoA solvers, on average, running the same problem instances.

o Predictive Benchmarking: TA1 will also focus on development and validation of predictive benchmarking techniques targeting the Phase 2 – TA2 demonstration scales (200 problem variables) using 50 problem variable hardware.

Phase 2 (Option) – Algorithm optimization: TA1 will increase the accuracy of the framework estimates by implementing and optimizing all algorithms needed by the Phase 2 problem classes and incorporating larger (and integrated) hardware performance models coming from compatible TA2 hardware.

o Phase 2 Problem Classes: The performance estimates will be performed through simulation on Government provided instances of the Boolean Satisfiability (SAT) and Maximum Likelihood Estimation (MLE) problems, and on performer provided instances of a Performer Proposed Problem (PPP).

o Projected System Performance Estimates: the solver framework will use projected hardware performance models from TA2 (at the 1,000-problem variable hardware size) to estimate performance for Phase 3 through simulation. The result will be a projected digital computational efficiency for Phase 2 problem classes at the Phase 3 problem size of 1,000 problem variables. The associated milestone is an improvement in digital computational efficiency of at least one hundred-fold (100x) over cSoA solvers, on average, running the same problem instances.

o Predictive Benchmarking: TA1 will also adapt the predictive benchmark capabilities established in Phase 1 to predict performance at intermediate scales

(1,000 problem variables) using TA2 hardware demonstration scales (200 problem variables).

Phase 3 (Option) – Mission-scale performance prediction: TA1 will focus on further reduction of ancillary digital computing resource requirements, and on optimization of performance for mission-scale benchmark problems.

o Phase 3 Problem Classes: The performance estimates will be performed through simulation on Government provided instances of the Boolean Satisfiability (SAT) and Maximum Likelihood Estimation (MLE), Maximum Fault Minimum Cardinality (MFMC) and Mixed Integer Linear Programming (MILP) problems, and on performer provided instances of a Performer Proposed Problem (PPP).

o Projected System Performance Estimates: the solver framework will use projected hardware performance models from TA2 (at the ≥ 10,000 problem variable hardware size) to estimate performance through simulation for mission-relevant scales. The result will be a projected digital computational efficiency for Phase 3 problem classes at mission-relevant problem sizes of at least 10,000 problem variables. The associated milestone is an improvement in digital computational efficiency of at least one thousand-fold (1000x) over cSoA solvers, on average, running the same problem instances.

o Feasibility Analysis: The framework estimate must provide feasibility analysis of an improvement in computational efficiency of at least five-hundred-fold (500x) over cSoA solvers for the Phase 3 problem classes at mission-relevant scales (≥10,000 problem variables).

o Predictive Benchmarking: TA1 will further advance predictive benchmark capabilities to predict performance at mission scales (≥10,000 problem variables) using the program hardware size target (1,000 problem variables).

Specific deliverables for TA1:

Solver framework including an analog hardware simulator that accepts hardware performance models in the program-standardized format, along with the runtime environment specifications, and including the capability to interface with TA2 analog hardware deliverables through the open, nonproprietary control and readout protocol;

Web-based access to the solver framework for the Government team, to enable solver framework and platform validation; Web interface must support program-developed open standards for problem instance specifications, solver control parameters, and solutions.

Solver performance projection and feasibility analysis for benchmark problems;

At least one proposed problem class, in addition to the four given problem classes;

Demonstration of predictive benchmark techniques with smaller-scale hardware, and problem instances in each problem class; and Benchmarking results on projected analog hardware performance.

See also Section I.F “Deliverables” for detailed deliverable requirements and schedule.

Technical Area 2 (TA2): Analog Hardware Prototyping

Technical Area 2 seeks to develop new dynamical system (analog) hardware and associated component models for performance estimation and will demonstrate solver performance. The proposed dynamical systems are expected to overcome or obviate existing analog hardware limitations and scale analog hardware advantages to mission-relevant problem classes and sizes, as well as reduce digital overhead related to analog hardware.

In TA2, proposers shall provide a concise discussion of the technical approach and rationale to:

a) overcome or obviate prior analog hardware limitations; and b) achieve the TA2 milestones for computational efficiency relative to conventional state-of-the-art solvers for solutions to selected benchmarks that have the same (or better) quality of solution as conventional solver solutions.

Proposals must include at least one core technology (for example, semiconductor-based, superconductor-based, magnetic, optical, etc.) for TA2. Proposals may include more than one core technology approach to TA2. Different core technologies should be proposed as separate TA2 approaches, with clearly delineated SoW tasks that are costed separately. Multiple TA2 approaches should be designated in the SoW and cost proposal as TA2(a), TA2(b), TA2(c), etc.

Proposers are discouraged from submitting variations of a core technology as separate TA2 approaches, e.g., different types of semiconductor-based circuits. Instead, proposers should incorporate trade-off studies and potential design variations to mitigate technical risks into one TA2 approach for each core technology proposed.

Proposed analog dynamical system hardware should interface with the TA1 solver framework through a control and readout interface protocol. Program performers will be expected to establish (collaboratively , with Government team mediation) open, nonproprietary control and readout interface protocols.

Similar to TA1, within TA2 progress towards the computational efficiency goal will be measured by projected gains in computational efficiency, at specified problem sizes, relative to cSoA solvers for program-specified benchmarks. TA2 metrics include the system computational efficiency defined in TA1 above, and the analog computational efficiency. Analog computational efficiency is the computational efficiency (characterized by the energy-to-solution) of only the analog hardware. Analog computational efficiency, when compared to cSoA, is always compared to the total energy-to-solution of the cSoA system.

TA2 Objectives with Key Milestones by Phase The objectives of TA2 for each phase are listed below. In order to reach the TA2 objectives, the program structure is designed to enable tight coordination between phases within TA2, and also integration with TA1.

Phase 1 (Base) – Prototype hardware and performance model development: TA2 will focus on developing new hardware components and the providing validated component performance models in an open, non-proprietary, standardized hardware performance model format.

o Phase 1 Problem Classes: The performance estimates will be performed on Government provided instances of the Boolean Satisfiability (SAT) problem, and on performer provided instances of a Performer Proposed Problem (PPP).

o Fabricated Hardware: The prototype analog dynamical systems should be capable of embedding problems with at least fifty (50) problem variables.

o Dynamical System Scaling Exponent: The proposed implementations should enable the number of required dynamical system elements to scale linearly with problem size, up to the specified size of fifty (50) problem variables. The associated milestone is that the scaling exponent is less than 1.5 for all Phase 1 problem classes.

o Hardware Performance Models: TA2 performers should provide validated component performance models for TA1 to estimate the system computational efficiency improvement over cSoA solvers for the Phase 1 problem classes at problem sizes of fifty (50) problem variables.

o Projected Hardware Performance Models: TA2 performers should provide projected component performance models (at the 200-problem variable hardware size) to TA1 for digital computational efficiency estimation. These models should also lead to an analog computational efficiency improvement over cSoA solvers for Phase 1 problem classes at the Phase 2 problem size (200 problem variables). The associated milestone is an improvement in analog computational efficiency of at least ten-fold (10x) over cSoA solvers, on average, running the same problem instances.

Phase 2 (Option) – Hardware integration and scaling: TA2 will focus on demonstrating integrated hardware subsystems and providing the corresponding hardware performance models. The proposed analog dynamical systems should be fully integrated with control while the minimum number of embedded problem variables will increase to at least two hundred (>200).

o Phase 2 Problem Classes: Same as in Phase 1, but expanded to include:

Instances of the Maximum Likelihood Estimation (MLE) problem.

o Fabricated Hardware: Same as in Phase 1, but with:

200 problem variables instead of 50.

o Dynamical System Scaling Exponent: Same as in Phase 1, but with:

200 problem variables instead of 50, and Phase 2 problem classes instead of Phase 1 problem classes.

o Hardware Performance Models: Same as in Phase 1, but with:

200 problem variables instead of 50, and Phase 2 problem classes instead of Phase 1 problem classes.

o Projected Hardware Performance Models: Same as in Phase 1, but with:

1,000 problem variables instead of 200, Phase 2 problem classes instead of Phase 1 problem classes, and 100x improvement instead of 10x.

o Estimated System Computational Efficiency: TA2 performers should estimate system computational efficiency improvements over cSoA solvers for selected problems (SAT and PPP) for problem sizes of 1,000 problem variables using predictive benchmarks. The associated milestone is an improvement in system computational efficiency of at least fifty-fold (50x) over cSoA solvers, on average, running the same problem instances.

o Demonstration of System Computational Efficiency: TA2 performers should conduct a full system demonstration for the Phase 2 problem classes at problem sizes of 200 problem variables. The associated milestone is an improvement in system computational efficiency of at least ten-fold (10x) over cSoA solvers, on average, running the same problem instances.

Phase 3 (Option) – Prototype-scale demonstration and mission-scale estimation:

TA2 will focus on demonstrating system performance on program-specified application problem classes, along with the predictive benchmarks coming from TA1.

o Phase 3 Problem Classes: Same as in Phase 2, but expanded to include:

Instances of the Maximum Fault Minimum Cardinality (MFMC) and

Mixed Integer Linear Programming (MILP) problems o Fabricated Hardware: Same as in Phase 1, but with:

1,000 problem variables instead of 50.

o Dynamical System Scaling Exponent: Same as in Phase 1, but with:

1,000 problem variables instead of 50, and Phase 3 problem classes instead of Phase 1 problem classes.

o Hardware Performance Models: Same as in Phase 1, but with:

1,000 problem variables instead of 50, and Phase 3 problem classes instead of Phase 1 problem classes.

o Projected Hardware Performance Models: Same as in Phase 1, but with:

≥10,000 problem variables instead of 200, Phase 3 problem classes instead of Phase 1 problem classes, and 1,000x improvement instead of 10x.

o Estimated System Computational Efficiency: Same as in Phase 2, but with:

10,000 problem variables instead of 1,000, and 500x improvement instead of 50x.

o Demonstration of System Computational Efficiency: Same as in Phase 2, but with:

1,000 problem variables instead of 200, Phase 3 problem classes instead of Phase 2 problem classes, and 50x improvement instead of 10x.

Specific Deliverables for TA2:

Demonstration of analog dynamical system hardware with the open, non-proprietary control and readout interface;

Web-based access to the analog dynamical system hardware and integrated solver (as applicable) for the Government team, to enable benchmarking and validation; Web interface must support program-developed open standards for problem instance specifications, solver control parameters, and solutions;

Validated hardware performance models for performance estimates in open, non-proprietary, standardized format;

Analog dynamical system performance projections; and

Solver system performance estimation using predictive benchmark instances from TA1.

See also Section I.F “Deliverables” for detailed deliverable requirements and schedule.

Integration and Problem Classes for All Technical Areas:

Program Metrics and Milestones The list of program metrics and milestones is presented in Table 1.

Integration In order to reach the program objectives and to facilitate test and evaluation (T&E) of deliverables, the program structure is designed to enable tight integration between TA1 and TA2.

Proposed solver frameworks in TA1 should accept – and dynamical system hardware performance models in TA2 should conform to – hardware performance models in an open, non-proprietary, standardized format that will be established by program performers (collaboratively, with Government team mediation). Similarly, proposed analog dynamical system hardware in TA2 and solver frameworks in TA1 should conform to an open, nonproprietary control and readout interface protocol, established by program performers (collaboratively, with Government team mediation). The proposed solver frameworks should integrate with analog dynamical system hardware, and should provide remote access to the Government team through a web-based, open interface to enable solver framework and analog hardware platform validation.

Problem Classes The program seeks to advance the capabilities of QI solvers for hard optimization problems beyond MAX-CUT. The classes of optimization problems include:9

Boolean Satisfiability (SAT) for cryptanalysis of members of the message-digest algorithm family, such as MD4 or reduced-round MD5,10 or for cryptanalysis of members of the secure hash algorithm family, such as reduced-round SHA-1;11 or for solving k- SAT with k≥3 in conjunctive normal form (CNF) or similar format;12

Maximum Likelihood Estimation (MLE) for multiple-input and multiple output (MIMO) computations,13 e.g., decoding, channel estimates, and precoding;

Maximum-Fault Minimum-Cardinality (MFMC) sampling for circuit testing;14 and Mixed-Integer Linear Programing (MILP) for logistics, e.g., vehicle routing problems

(VRP)15 or sample benchmark instances from CVRPLIB16 X-set.17

9 Examples in each problem class are provided for cost estimation purposes; they are expected to be refined throughout the program by the Government team.

10 I. Otpuschennikov, et al., "Encoding Cryptographic Functions to SAT Using Transalg System", Proc. ECAI’16,

pp. 1594-1595, (2016); arXiv:1607.00888 [cs.AI] 11 V. Skladanivskyy, "Minimalistic Round-reduced SHA-1 Pre-image Attack", Proc. SAT Race 2019, p. 51 12 For example, output of CNFgen <https://massimolauria.net/cnfgen/>, or Cgen <https://github.com/vsklad/cgen> 13 N. Ide, et al. 2020 International Symposium on Information Theory and Its Applications; arXiv:2007.08689 [cs.IT] 14 A. Feldman, et al., In Proc. AAAI’08, vol. 2, pp. 919-924 (2008); A. Feldman, et al., J. Artif. Intell. Res., vol. 38, pp.371-413 (2010) 15 E. Ucho, et al., Eur. J. Oper. Res., vol. 257, pp. 845-858 (2016); S. Feld, et al., Front. ICT 6:13 (2019) 16 CVRPLIB (Capacitated Vehicle Routing Problem Library): http://vrp.atd-lab.inf.puc-rio.br/ 17 X-set is the collection of the benchmark instances from E. Ucho, et al., Eur. J. Oper. Res., vol. 257, pp. 845-858 (2016) https://massimolauria.net/cnfgen/ https://github.com/vsklad/cgen

During the program, performers are expected to provide at least one (1) additional problem class and associated milestones for each program phase. These Performer Proposed Problem (PPP) specifications should include: a) descriptions of related DoD mission(s), b) the mission impact of increased computational efficiency; and c) the associated energy-to-solution for conventional state-of-the-art solvers18 for each program phase’s specific problem size. Additional problem classes may be introduced by program performers as the program progresses.

With the exception of estimates of system computational efficiency in TA2, performers in both TAs should demonstrate the following problem classes for respective solver systems and subsystems to meet the individual phase goals:

Phase 1: SAT, and, additionally, either a PPP or one of the three other program problem classes

Phase 2: SAT, MLE, and, additionally, either a PPP or one of the two other program problem classes

Phase 3: All four program problem classes defined above, and any PPP.

For estimates of system computational efficiency in Phases 2 and 3, performers should demonstrate solving problems in SAT, and, additionally, either the PPP or one of the three other program problem classes.

Table 1. Metrics and Milestones TA Metrics and Milestones TC Phase 1 Phase 2 Phase 3

All Problem classes19 SAT, PPP SAT, MLE, PPP All, PPP TA1 Benchmark gain20 3 5x 5x 10x

TA1

Projected digital computational efficiency improvement over cSoA (@ problem size)

10x @ 200 100x @ 1,000 1,000x @ 10,000

TA1 Hardware performance model size 1,2 50 200 1,000

TA1 Technology demo All Co-design framework full stack

Co-design framework full stack

Feasibility analysis of >500x computational efficiency improvement TA2 Fabricated analog hardware size 1 50 200 1,000 TA2 Scaling exponent (@ up to problem size) 1 < 1.5 @ 50 < 1.5 @ 200 < 1.5 @ 1,000

TA2

Estimated system computational efficiency improvement over cSoA (@ problem size) using predictive benchmarks

1,2

- 50x @1,000 500x @10,000

TA2

Projected analog computational efficiency improvement over cSoA (@ problem size)

10x @ 200 100x @ 1,000 1000x @ 10,000

TA2

Demonstrated system computational efficiency improvement over cSoA (@ problem size)

1,2

- 10x @ 200 50x @ 1,000

18 Methodology used to determine cSoA energies for PPPs must be clearly defined and supported by references.

19 Except the estimate of system computational efficiency in TA2, which requires only SAT and one additional problem class.

Notes for Table 1:

cSoA means conventional state-of-the-art digital solvers that run on, for example, StarExec21-equivalent systems.22

“Computational efficiency improvement over cSoA” means computational efficiency compared to cSoA. The QI solution quality is measured by the best value of the objective function found relative to the best of the known cSoA solutions for a given problem. For the determination of computational efficiency, QI solutions should be of the same or better quality as cSoA solutions, except in Phase 1, when solution quality is permitted to be 90% of cSoA solutions.

Digital computational efficiency is characterized by the energy consumed by the digital subsystem. Improvement means less energy. When compared to cSoA, it is compared to the total energy consumed by the cSoA.

Analog computational efficiency is characterized by the energy consumed by the analog subsystem. Improvement means less energy. When compared to cSoA, it is compared to the total energy consumed by the cSoA.

Projected computational efficiency means the computational efficiency obtained by simulation and analysis with projected hardware performance models.

Analog hardware size, and hardware performance model size, are defined as the problem size (number of problem variables) that can be embedded in the hardware, for all problem classes addressed in a given program phase.

The problem size (number of problem variables) for individual problem classes are defined as the following:23 o SAT: Problem size is defined as the number of distinct Boolean variables (i.e., without counting both a variable and its negation).

o MLE-MIMO:

For pre-coding and decoding, problem size is defined as the number of users multiplied by the number of bits in the modulation scheme (constellation), For channel estimation, problem size is defined as the number of antennas multiplied by the number of users, multiplied by the number of bits for target resolution.

o MFMC for circuit testing: Problem size is defined as the number of gates in the circuit.

(This is in contrast to the conventional scheme:24 as the number of observables (inputs and outputs), plus the number of gates and internal wires) o MILP for logistics: Problem size is defined as the number of customers multiplied by the number of scenario attributes (or constraints) for vehicle routing problems (VRP), or as the number of integer variables specific to given types of problems.

Scaling exponents are defined as the logarithm of the number of analog dynamical system elements (used for embedding problem variables) divided by the logarithm of the number of problem variables. Scaling exponents are calculated for problem sizes up to the phase specific target (i.e., 50 problem variables in Phase 1, 200 in Phase 2, 1,000 in Phase 3).

20 At least 90% confidence level 21 StarExec infrastructure specification can be found at https://www.starexec.org/starexec/public/machine-specs.txt 22 Examples of conventional computing systems are provided for cost estimation purposes; they are expected to be refined throughout the program by the Government team.

23 The definitions of problem sizes and problem variables are provided for cost estimation purposes; they are expected to be refined throughout the program by the Government team.

24 A. Feldman, et al., J. Artif. Intell. Res., vol. 38, pp.371-413 (2010)

E. Schedule/Milestones

The QuICC program is a 60-month, three-phase program with the period of performance expected to start in May 2022. A mandatory program kickoff meeting at each phase will be held to present the technical approach, to discuss technical and programmatic items of concern and to interact with the government team and other program performers. The end of each phase is a major event in the program and end-of-phase review meetings will be scheduled approximately six weeks before the end of each phase. These meetings will be used to communicate technical progress toward the milestones achieved over the entire phase. Technical progress toward the milestones of the program is a major deciding factor for continuation into subsequent phases and will be monitored through monthly teleconference calls, quarterly technical reviews, occasional site visits, and annual program reviews by the DARPA program manager and other members of the government team.

The three phases of the program are structured to retire the major risks in achieving the program goals. Proposals must clearly explain how the proposed approaches overcome or obviate the risks in each phase of the program.

Phase 1, Prototype Development – Small-Scale Problems (24 months)

Phase 1 will address the underlying…