Abstract:
to represent the evolutionary relationships between entities such as species, languages, cancer
cells, and viruses. To reconstruct and analyze phylogenetic networks, the problem of deciding
whether or not a given rooted phylogenetic network embeds a given rooted phylogenetic tree
is of recurring interest. This problem, formally know as Tree Containment, is NP-complete in
general and polynomial-time solvable for certain classes of phylogenetic networks. In this paper,
we connect ideas from quantum computing and phylogenetics to present an efficient Quadratic
Unconstrained Binary Optimization formulation for Tree Containment in the general setting. For
an instance (N, T ) of Tree Containment, where N is a phylogenetic network with nN vertices
and T is a phylogenetic tree with nT vertices, the number of logical qubits that are required for
our formulation is O(nNnT ).