论文标题
布尔矩阵产品最大见证人的量子和近似算法
Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
论文作者
论文摘要
发现两个布尔矩阵（简称MW）的布尔产品的最大见证人的最大见证人的问题具有许多重要应用，尤其是全对最低的共同祖先（LCA）问题，在有向的无环图（DAGS）中。自2006年以来，在N \ times n布尔矩阵的MW问题上最著名的上限时间限制了。为了获得此问题的更快算法，我们研究了MW的量子算法和MW的近似算法（在标准计算机模型中）。我们的一些量子算法是输入或输出敏感的。我们针对MW问题的最快量子算法，因此对于相关问题，时间\ tilde {o}（n^{2 +λ/2}）= \ tilde {o} {o}（n^{2.434}），其中λssatifeλsatsifeλsatsifeλssatifecousefous n \ times n^λ$矩阵乘以n^λ\ times n矩阵的乘法指数。接下来，我们考虑MW问题的轻松版本（在标准模型中），要求报告矩阵产品的每个非零条目的有限等级的见证人（最高见证人的等级1）。首先，通过调整已知算法的最大见证人，我们获得了一种放松问题的算法，该算法报告了产品矩阵的每个非零入口，最多是\ ell fime \ ell fime \ tilde {o}（O}（O}（（n/\ ell）n^（n/\ ell）n^n^（1，\ log_n \ log_n \ ell，1）}）。然后，通过将轻松的问题减少到所谓的K-witness问题，我们提供了一种算法，该算法为产品矩阵C的每个非零条目c [i，j]报告级别的见证人（\ lceil w_c（i，j）/j/k \ rceil），其中w_c（i，j）是c [i，j）的数量。该算法在\ tilde {o}（n^ωk^{0.4653} +n^2k）时间中运行，其中ω=ω（1,1,1）。
The problem of finding maximum (or minimum) witnesses of the Boolean product of two Boolean matrices (MW for short) has a number of important applications, in particular the all-pairs lowest common ancestor (LCA) problem in directed acyclic graphs (dags). The best known upper time-bound on the MW problem for n\times n Boolean matrices of the form O(n^{2.575}) has not been substantially improved since 2006. In order to obtain faster algorithms for this problem, we study quantum algorithms for MW and approximation algorithms for MW (in the standard computational model). Some of our quantum algorithms are input or output sensitive. Our fastest quantum algorithm for the MW problem, and consequently for the related problems, runs in time \tilde{O}(n^{2+λ/2})=\tilde{O}(n^{2.434}), where λsatisfies the equation ω(1, λ, 1) = 1 + 1.5 \, λand ω(1, λ, 1) is the exponent of the multiplication of an n \times n^λ$ matrix by an n^λ \times n matrix. Next, we consider a relaxed version of the MW problem (in the standard model) asking for reporting a witness of bounded rank (the maximum witness has rank 1) for each non-zero entry of the matrix product. First, by adapting the fastest known algorithm for maximum witnesses, we obtain an algorithm for the relaxed problem that reports for each non-zero entry of the product matrix a witness of rank at most \ell in time \tilde{O}((n/\ell)n^{ω(1,\log_n \ell,1)}). Then, by reducing the relaxed problem to the so called k-witness problem, we provide an algorithm that reports for each non-zero entry C[i,j] of the product matrix C a witness of rank O(\lceil W_C(i,j)/k\rceil ), where W_C(i,j) is the number of witnesses for C[i,j], with high probability. The algorithm runs in \tilde{O}(n^ωk^{0.4653} +n^2k) time, where ω=ω(1,1,1).
