NASA Logo, National Aeronautics and Space Administration

+NASA Home

+Ames Home

Quantum Artificial Intelligence Laboratory Team Receives Algorithms Journal 2020 Best Paper Award
Intelligent Systems Division Banner

Quantum Artificial Intelligence Laboratory Team Receives Algorithms Journal 2020 Best Paper Award

The Multidisciplinary Digital Publishing Institute (MDPI) Algorithms Journal awarded Dr. Stuart Hadfield, Dr. Zhihui Wang, Mr. Bryan O'Gorman, Dr. Eleanor G. Rieffel, Dr. Davide Venturelli, and Dr. Rupak Biswas the Algorithms 2020 Best Paper Award on April 30, 2021. Their manuscript is entitled, "From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz,” Algorithms 12 (2), 34 (2019).

The Quantum Alternating Optimizing Ansatz (QAOA) was inspired by the simple structure of the Quantum Approximate Optimization Algorithm by Farhi et al., 2014, which is a gate model quantum optimization approximate optimization algorithm. QAOA makes use of phase separation operators that are cost-function dependent and mixing operators, alternating application of operators from each family p times. The work of Hadfield et al. supports more general mixing operators than the original structure proposed by Farhi et al., providing significant improvements in implementability and generality. These more general mixing operators also support incorporation of hard constraints instead of the more traditional approach of incorporating a penalty term in the phase separation operator commonly used in quantum annealing. This approach ensures the algorithm explores only the feasible sub-space that, while usually still exponentially large, is exponentially smaller than the full search space, resulting in a more efficient heuristic.

BACKGROUND: Presently, there are only a few applications where quantum computing provably outperforms classical, non-quantum computation, which is not surprising at this stage of quantum computing. Computationally challenging real-world problems are frequently tackled with heuristic algorithms that are empirically tested on benchmark problems. Similarly, empirical testing of quantum heuristic algorithms on quantum hardware in the coming years will significantly increase the applications for which quantum computing is known to outperform classical approaches. The QAOA is now one of the leading candidates for quantum optimization heuristics.

Algorithms is a peer-reviewed, open access journal that provides an advanced forum for studies related to algorithms and their applications. Algorithms is published monthly online by MDPI.

NASA PROGRAM FUNDING: NASA Advanced Exploration Systems program; Bryan O’Gorman was supported by a NASA Space Technology Research Fellowship; Dr. Zhihui Wang and Dr. Davide Venturelli were supported by NASA Academic Mission Services (NNA16BD14C); and Stuart Hadfield was supported by NASA contract NNX12AK33A.

TEAM: Dr. Stuart Hadfield, Dr. Zhihui Wang, Mr. Bryan O'Gorman, Dr. Eleanor G. Rieffel, Dr. Davide Venturelli, and Dr. Rupak Biswas

POINT OF CONTACT: Eleanor Rieffel, eleanor.rieffel@nasa.gov

First Gov logo
NASA Logo - nasa.gov