Quantum Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees

Phillip Kerger; David E Bernal Neira; Eleanor Rieffel

NASA NTRS · 20230002008

Quantum Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees

Phillip Kerger·David E Bernal Neira·Eleanor Rieffel

Abstract

We present two algorithms in the Quantum CONGEST- CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact directed minimum spanning tree, each of which uses O ̃(n1/4) rounds of communication and O ̃(n9/4) messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, 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 classical algorithms, revealing that advances are needed to render both practical.

Explore related subjects

quantum computing distributed algorithms CONGEST-CLIQUE Steiner Tree

Keep this discovery

Explore connections, maps & timelines

BibTeX RIS

Phillip Kerger, David E Bernal Neira, Eleanor Rieffel. Quantum Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees. https://ntrs.nasa.gov/citations/20230002008

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related reports

DOE OSTI2025

Design and Optimization of a Hybrid Design for Quantum Transduction

This study presents the mechanical design and analysis of a quantum electro-optical transducer engineered to operate at millikelvin temperatures within a dilution refrigerator. The transducer enables bidirectional microwave-optical frequency conversion through a hybrid architecture that integrates a superconducting radiofrequency (SRF) cavity with an electro-optic optical cavity. Among several design options investigated, the configuration offering the best thermal and mechanical performance was selected, yielding a robust solution with reduced sensitivity to fabrication tolerances, improved heat dissipation, as well as alignment precision. The design ensures uniform temperature distribution, enabling higher laser pump powers and, thus, increased conversion efficiency, while maintaining mechanical stresses safely below the material yield strength. Electromagnetic simulations further validate the design, demonstrating enhanced coupling between the optical and microwave modes, as well as a broader tuning range achieved with smaller tuner displacements.

quantum computing↗

DOE OSTI2025

Quantum Computing and Simulations for Energy-Related Applications

Quantum Information Science (QIS) is an emerging field that has the potential to cause revolutionary advances in many areas of science and engineering, and nations around the world are vying for dominance in the field. To support DOE urgent task to make sure the U.S. wins the quantum race, in Spring of 2019 NETL started to establish and maintain QIS competency by focusing on energy-related applications. After more than five years’ hard-working, NETL QUEST (quantum for energy systems & technologies) team has made great progress on quantum sensing and quantum computing for energy applications. Significant outcomes have been achieved. To report our research progress and to propose new research directions, in this presentation at the American Physical Society (APS) annual meeting, I'm highlighting the progress of QUEST team on quantum computing for energy-related applications.

quantum computing↗

NASA NTRS2023

Improved Fermion Hamiltonians for Quantum Simulation

The Symanzik improvement program has been quite successful in classical simulations of quantum chromodynamics allowing calculations to be performed at coarser lattice spacings and with reduced computational resource costs. It is expected that improved Hamiltonians will be essential to simulate lattice field theories using quantum computers. In this work I will discuss the formulation of an ASQTAD and HISQ Hamiltonian amenable for quantum simulations. I will also show preliminary results that demonstrate significant tree-level contributions are removed in the spectrum of the 1 flavor Schwinger model.

quantum computing↗