Span program is a linear-algebraic model of computation which can be used todesign quantum algorithms. For any Boolean function there exists a span programthat leads to a quantum algorithm with optimal quantum query complexity. Ingeneral, finding such span programs is not an easy task. In this work, given aquery access to the adjacency matrix of a simple graph $G$ with $n$ vertices,we provide two new span-program-based quantum algorithms: an algorithm fortesting if the graph is bipartite that uses $O(n\sqrt{n})$ quantum queries; analgorithm for testing if the graph is connected that uses $O(n\sqrt{n})$quantum queries.
展开▼
机译：跨度程序是计算的线性代数模型，可用于设计量子算法。对于任何布尔函数，都存在一个span程序，该程序会导致量子算法具有最佳的量子查询复杂度。通常，要找到这样的跨度程序并非易事。在这项工作中，假设查询访问具有$ n $个顶点的简单图形$ G $的邻接矩阵，我们提供了两种基于跨度程序的量子算法：一种用于检验图形是否为二分图的算法，该算法使用$ O（n \ sqrt {n}）$量子查询；用于测试使用$ O（n \ sqrt {n}）$ quantum查询的图形是否已连接的算法。
展开▼
