A NASA Perspective on Quantum Computing, with Emphasis on Recent Results in Distributed Computing

The NASA Quantum Artificial Intelligence Laboratory (QuAIL) performs research to assess the potential impact of quantum computers on challenging computational problems relevant to NASA missions of the future, with particular emphasis on discrete optimization. The talk will begin with a brief overview of the QuAIL team and some general remarks on the status of and prospects for quantum computing. The talk will then transition to a discussion of distributed quantum computing, with an emphasis on recent results in the quantum CONGEST-CLIQUE Model (qCCM). I’ll introduce both the classical and quantum CONGEST-CLIQUE Models of distributed computation, and then outline two quantum algorithms that succeed with high probability; one yields an approximately optimal Steiner Tree, and the other an exact directed minimum spanning tree, each using asymptotically fewer rounds of communication than any known algorithms in the classical CONGEST-CLIQUE model. We achieve these results by combining classical algorithms with fast quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms, as well as related prior classical and quantum algorithms, revealing the importance of “small” factors and highlighting that advances are needed to render both practical. The talk will conclude with some open questions.