Quantum Algorithms for the Minimum Steiner Tree problem with application to Binary Near-Perfect Phylogenies

2025/10/10 by Meng, Lingfa, Novo, David Salvador, Werner, Albert H. +1
#68Q12 (Secondary) #81P68 (Primary) #F.2.2 #FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2510.09911

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.

Citations

• Local Search for Weighted Tree Augmentation and Steiner Tree
• Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
• Fourier meets Möbius: fast subset convolution
• Toward Defining the Course of Evolution: Minimum Change for a Specific Tree Topology

Related

• Quantum Speedup for the Minimum Steiner Tree Problem
• Inference of maximum parsimony phylogenetic trees with model-based classical and quantum methods
• Additive Approximation for Near-Perfect Phylogeny Construction
• Quantum Algorithms for Evaluating MIN-MAX Trees
• Noisy Tree Data Structures and Quantum Applications