2013/09/30 by Guoming Wang, Wang, Guoming
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata
paper · pdf · doi:10.48550/arxiv.1309.7713
openalex publication_date 2013/09/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. Given query access to the adjacency matrix of a graph G with n vertices, we need to determine whether G contains T as a subgraph, or G does not contain T as a minor, under the promise that one of these cases holds. We call this problem the subgraph/not-a-minor problem for T. We show that this problem can be solved by a bounded-error quantum algorithm with O(n) query complexity and O(n) time complexity. The query complexity is optimal, and the time complexity is tight up to polylog factors.