← Back to papers
Quantum Algorithms for the Minimum Steiner Tree problem with application to Binary Near-Perfect Phylogenies
Lingfa Meng, David Salvador Novo, Albert H. Werner, Samir Bhatt·October 10, 2025
Quantum Physics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We present a quantum algorithm in bioinformatics for solving the Binary Near-Perfect Phylogeny Problem (BNPP) with a complexity bound of $O(8.926^q + 8^q nm2)$, where n is the number of input taxa and m is the sequence length for each taxon with each character in the sequence being a binary bit using the QRAM model. We give another polynomial space exact algorithm for the Minimum Steiner Tree (MST) problem with complexity $O^*(e^{(1+g(k,l))k})$ in the circuit model.