Optimization with Noisy Intermediate-Scale Quantum devices (ONISQ) Proposers Day
March 19, 2019
The Defense Advanced Research Projects Agency (DARPA) Defense Sciences Office (DSO) is sponsoring a Proposers Day to provide information to potential proposers on the objectives of an anticipated Broad Agency Announcement (BAA) for the Optimization with Noisy Intermediate-Scale Quantum devices (ONISQ) program. The Proposers Day will be held on March 19, 2019 from 9:00 AM to 5:00 PM at the Executive Conference Center (4075 Wilson Blvd., Suite 300, Arlington, VA 22203). The event will be webcast for those who would like to participate remotely. Advance registration is required both for attending the Proposers Day in person and for viewing the webcast.
The goals of the ONISQ Proposers Day are to:
(a) introduce the research community (Proposers, Academia, and Government) to the ONISQ program vision and goals;(b) explain the mechanics of a DARPA program and the milestones of this particular effort; and(c) encourage and promote teaming arrangements among potential organizations that have the relevant expertise, facilities, and capabilities for executing a research and development program responsive to the ONISQ program goals.
DARPA anticipates releasing the ONISQ BAA in mid-March. If released, the BAA will be available on the Federal Business Opportunities website at https://www.fbo.gov/ and on http://www.grants.gov/. Following the event, DARPA may post the presented materials as well as a Frequently Asked Questions (FAQ) list to the DARPA/DSO Opportunities webpage. To maximize the pool of innovative proposal concepts, DARPA strongly encourages participation by non‐traditional performers (including small businesses, academic and research institutions, and first‐time Government contractors) in events such as this and any subsequent solicitations.
Program Objective and Description
The principal objective of the ONISQ program is to demonstrate quantitative advantage of Quantum Information Processing (QIP) over the best classical methods for solving combinatorial optimization problems using Noisy Intermediate-Scale Quantum (NISQ) devices. In addition, the program will identify families of problem instances in combinatorial optimization where QIP is likely to have the biggest impact.
Combinatorial optimization problems are NP-complete, and are ubiquitous in a wide range of application areas from industry and science to military. Efficient heuristic algorithms (with no guarantee of optimality) exist for many problem instances, but for many others only exponentially scaling methods exist and such problems can be hard even for modest sizes.
A novel QIP method has recently emerged as a potentially powerful approach for addressing useful combinatorial optimization problems possibly before universal quantum computers (QC) become available. While steady progress has been made in the development of quantum computers over the past couple of decades, most experts agree that fault-tolerant QCs are still decades away. However, in the past couple of years, quantum processors with >50 qubits have been developed in several different platforms (e.g., superconducting, trapped ions, neutral atoms), and processors with >100 physical qubits have been announced. One of the most promising applications of these devices may be in combinatorial optimization using a recent hybrid quantum/classical variational algorithm, Quantum Approximate Optimization Algorithm (QAOA). While little is known still about the QAOA performance due to the difficulty in evaluating it theoretically, what is known so far is very encouraging and provides a strong impetus to implement and evaluate QAOA in hardware, which is the focus of this program.
In ONISQ, we seek to: develop optimal implementations of QAOA in quantum hardware and fully characterize the algorithm performance, benchmark the algorithm against the best classical method(s) for a given problem, and demonstrate a quantum speedup. In order to achieve this goal, it is expected that current hardware will need to be scaled up in the number of physical qubits and circuit depth. An additional objective of the program is to identify families of instances in combinatorial optimization where QIP is likely to have the biggest impact.
