You are here

Quantum Algorithms for Military Cargo Transport

Description:

OUSD (R&E) CRITICAL TECHNOLOGY AREA(S): Quantum Science; Sustainment & Logistics; Advanced Computing and Software

 

The technology within this topic is restricted under the International Traffic in Arms Regulation (ITAR), 22 CFR Parts 120-130, which controls the export and import of defense-related material and services, including export of sensitive technical data, or the Export Administration Regulation (EAR), 15 CFR Parts 730-774, which controls dual use items. Offerors must disclose any proposed use of foreign nationals (FNs), their country(ies) of origin, the type of visa or work permit possessed, and the statement of work (SOW) tasks intended for accomplishment by the FN(s) in accordance with the Announcement. Offerors are advised foreign nationals proposed to perform on this topic may be restricted due to the technical data under US Export Control Laws.

 

OBJECTIVE: The objective of this topic is to develop and document quantum algorithms and quantum computer specifications for solving military cargo transport, as scaled from regional through full global coverage, on increasing forecast durations, while accommodating disruptions consistent with wartime operations.

 

DESCRIPTION: Military cargo transport and commercial package delivery are problems with similar structure and complexity. An example solution for the transport problem is a set of assignments within a particular forecast timeframe, such that each assignment associates payload, support materials (e.g., fuel), and aircrew with an aircraft, which is in turn assigned a particular route and destination. As the solution timeframe lengthens, so too increases the number of assignments associated with any specific aircraft. Any disruptions to the assignments, whether due to natural or man-made influences, incur a significant computational burden potentially accompanied by an operational halt.

 

Candidate transport assignments are generated from a combinatorial explosion of factors and quantities, and each candidate assignment must be validated for consistency and compatibility with constraints such as aircraft maintenance schedules, aircrew weekly hours, fuel availability, refueling duration, route availability, expected load/unload duration, and available hangar and/or ramp space. Any candidate solution requires its constituent assignments to be further checked against one another to prevent redundancy and mutual exclusivity. Full solution optimization via classical computing appears to be intractable (possibly NP-complete), requiring far more processing time than practical real-world operations allow.

 

Commercially available transport planning systems sacrifice optimality in favor of actionable solutions on relevant decision timelines. These systems – which reduce but do not escape the underlying computationally intensive resource allocation – achieve their goals by carefully restructuring the problem for example with additional constraints (e.g., shorter forecast duration, reduced geographic coverage) or through efficient heuristics (e.g., data-driven predictive assignment models).

 

Processing power is a continual critical enabler for practical planning systems. Quantum computing shows promise for resource allocation problems and with the right quantum algorithm(s) could even make optimal solutions achievable on operationally relevant timelines. However, the nature of the cargo transport planning problem may be such that some or all sub-problems are best solved with classical computing techniques. Critical investigations within this activity include 1) the military cargo transport problem and how its overall complexity is influenced by the scale of key factors (e.g., number of aircraft, time horizon, number of sites), 2) which elements of the overall military cargo transport problem and what quantum algorithm(s) are most likely to exhibit quantum advantage, 3) what real-world measurements and user inputs must be accommodated by a quantum algorithm for military cargo transport, 4) at what scale quantum advantage is likely to be achieved for military cargo transport as a whole and/or for key sub-problems within a hybrid quantum-classical solution, and 5) how the choice of quantum computing architecture influences the quantum system specifications required to execute the quantum algorithm(s) solving military cargo transport.

 

PHASE I: Awardee(s) will analyze the military transport resource allocation problem, identifying and documenting key factors and scalability impacts influencing complexity. Awardee(s) will develop quantum algorithms or a hybrid set of classical and quantum algorithms providing optimal solutions -- or improved approximations to the optimal solution -- to military cargo transport at all scales and timelines of military interest; developed algorithms must provide computational advantage over the currently fielded state of the art. Awardee(s) will recommend specifications for one or more quantum computing architectures capable of executing the developed quantum algorithms for military cargo transport at operationally relevant scales.

 

PHASE II: Awardee(s) will prototype or develop approaches to prototype the recommended quantum or hybrid quantum-classical system. Awardee(s) will develop practical approaches to assess system utility and assess quantum advantage at multiple operationally relevant problem scales. Awardee(s) will execute the developed assessments as state of the art permits.

 

PHASE III DUAL USE APPLICATIONS: Awardee(s) can expect to develop a strategy for transitioning the technology, with appropriate consideration for critical technology thresholds and scale at which quantum advantage applies.

 

REFERENCES:

  1. * 1. *S. Yarkoni et al. “Solving the shipment rerouting problem with quantum optimization techniques,” International Conference on Computational Logistics 2021, pp 502-517. https://doi.org/10.1007/978-3-030-87672-2_33;
  2. * 2. *A. M. Dalzell et al, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv, 2023. https://arxiv.org/abs/2310.03011;
  3. * 3. *DARPA, “Quantifying utility of quantum computers”, 2021. https://www.darpa.mil/news-events/2021-04-02;

 

KEYWORDS: quantum algorithms; quantum computing; logistics; military transport

US Flag An Official Website of the United States Government