Quantum Enhanced Optimization (QEO)

IARPA has interest in quantum annealing systems which outperform classical methods in solution of hard combinatorial optimization problems. Classical methods for solving large, practical problems are often inefficient, e.g., scale poorly (exponentially) with problem size, become trapped in sub-optimal solutions, and produce correlated solutions when sampling from multiple, degenerate minima. A means of enhanced solution of hard combinatorial optimization problems is of interest to provide cost-effective efficiencies and reduced risk in enterprise operations.

Evidence [1-8] supporting the potential of quantum enhancement of quantum annealing compels development of appropriately designed architectures and annealing parameters which make optimal use of quantum effects. Enhancement outcomes of interest include speed-up  in time-to-solution (TTS), improvement in scaling complexity, and higher quality solutions (e.g., lower values for the cost function, and or more useful statistical diversity of nearly degenerate solutions).

Quantum enhancement can be viewed as a result of constructive interference of collective qubit state transitions toward favorable outcomes during the evolution of a quantum annealer. Noise processes can obscure constructive interference of quantum effects, eliminating enhancement. Super-classical annealing performance is anticipated to rely on high fidelity systems that protect and optimize quantum effects promoting enhancement.

A means to enhancement beyond the reach of classical methods is of particular interest. This may be achieved most effectively by an improvement in scaling complexity. A polynomial improvement  in scaling complexity for a new quantum annealing machine may be sufficient to place its performance safely out of reach from plausible advancements in known classical methods. With this definitive advantage, the added cost of specialized annealing hardware may be justified.

The goal of the QEO Program (hereinafter, the “program goal”) is a basis of design for application-scale quantum annealers providing a 104 speed-up with polynomial improvement in scaling complexity over classical methods.

The QEO program is divided into two phases.  Phase 1 will run for a period of 36 months and encompasses a 12-month Base Period and two 12-month Option Periods, followed by Phase 2 for a period of 24 months encompassing two 12 month Option Periods. Both phases are solicited under this BAA.

Proposals are sought to develop theoretical and experimental capability to progressively design, fabricate, analyze, and optimize quantum annealing Test Beds, and from all activity to develop a progressive basis of design for application-scale quantum annealers meeting the program goal. Through Test Bed experiments QEO performers will corroborate innovative concepts for annealer design and operation, and predictive models of enhancement. From all activity, successful QEO performers will demonstrate how enhancement is optimally promoted, and estimate the elements of the basis of design required for application-scale, application-specific machines meeting the program goal.

QEO performers must explore a range of highly advanced quantum annealing capabilities and identify preferred combinations and implementation to meet the program goal. Capabilities of interest include:
  • Physical-Spin-Qubits with high, tunable coherence and function;
  • Advanced quantum fluctuations (e.g., multi-spin);
  • Broader classes of spin connectivity and physical architectures to access a broader, harder, problem space (e.g., simultaneous long-range and multi-spin interactions, higher intrinsic connectivity);
  • Real-time measurements during the annealing protocol to elucidate quantum enhancement phenomena and optimize both design and dynamic operation for performance;
  • Advanced annealing protocols (e.g., spatially-varying fields and couplings, adaptive control methods based on feedback, active qubit cooling);
  • Quantum error mitigation: error suppression, as well as engineered dissipation and cooling;
  • Greater precision, stability, and speed of calibration and control signals using state-of-art electronics;
  • Smart integration that optimizes the separate quantum (coherent Ising spins and couplings) and classical (control and readout) elements of the annealing system

Contracting Office Address

Office of the Director of National Intelligence
Intelligence Advanced Research Projects Activity
Washington, DC 20511

Primary Point of Contact

Karl F. Roenigk
Program Manager