量子科技中心_量科网

在该工作中，该研究团队将最近提出的图组合框架推广到非布尔设置。该框架中的量子算法由超图表示，其中每个超边与多个顶点相邻。量子算法的输入和输出由一组边界顶点表示，而超边则像开关一样，将输入顶点连接到算法计算的输出。 除了推广图组合框架外，该团队新提出的框架统一了量子分治框架、决策树框架和统一量子行走搜索框架。对于决策树，该团队还在非布尔情况下基于改进的加权方案构建了量子算法。对于量子行走搜索，该团队展示了其技术如何自然地实现子程序成本的分摊。 先前的研究展示了如何通过分摊量子行走的成本来加速“检测”标记顶点的过程。在该工作中，该团队将这些结果扩展到“查找”此类标记顶点的设置，尽管是在某些受限设置中。 在此过程中，该团队通过对不可约、可逆马尔可夫过程进行新颖分析，通过线性代数方法将其有效电阻与随机行走算子相连接。这显著简化了量子行走搜索算法的实现，实现了对约翰逊图上量子行走的分摊加速，避免了量子快速前向的需要，并从查询复杂度陈述中移除了对数因子。