论文标题
图形属性可以具有指数量子加速吗？
Can graph properties have exponential quantum speedup?
论文作者
论文摘要
量子计算机有时可以呈指数优于经典计算机，但仅用于足够结构的问题。众所周知，完全置换对称性的查询问题最多可以具有多项式量子速度（即使对于部分功能），但目前尚不清楚必须放松该条件以实现指数加速。特别是，自然要询问（部分）图形属性是否可能进行指数加速，其中输入描述了图，并且输出只能取决于其同构类别。我们表明，这个问题的答案在很大程度上取决于输入模型。在邻接矩阵模型中，我们证明了任何Graph属性的界限随机查询复杂性$ r $ r $ $ \ MATHCAL {p} $具有$ r（\ Mathcal {p}）= O（q（q（\ Mathcal {p}）^{6}）$ Q $ $ q $是$ q $ bounded-eved-erdecteDeDeDeDeDEded-ernum Quemppty。这对邻接矩阵模型中的蒙塔纳罗和de狼有负面问题。更一般而言，我们证明$ r（\ Mathcal {p}）= o（q（\ mathcal {p}）^{3l}）$对于任何$ l $ - 均匀的hypergraph property $ \ mathcal {p} $ in Aidjacency Matrix模型中。相比之下，在有界度图的邻接列表模型中，我们表现出一个有望的问题，显示了随机查询复杂性和量子查询复杂性之间的指数分离。
Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity $R$ of any graph property $\mathcal{P}$ has $R(\mathcal{P}) = O(Q(\mathcal{P})^{6})$, where $Q$ is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove $R(\mathcal{P}) = O(Q(\mathcal{P})^{3l})$ for any $l$-uniform hypergraph property $\mathcal{P}$ in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.
