Span-program-based quantum algorithm for tree detection

Understand

Span program is a linear-algebraic model of computation originally proposed for studying the complexity theory.

• Recently, it has become a useful tool for designing quantum algorithms.
• In this paper, we present a time-efficient span-program-based quantum algorithm for the following problem.
• Let $T$ be an arbitrary tree.