论文标题
量子子例程组成
Quantum Subroutine Composition
论文作者
论文摘要
算法设计中的一个重要工具是能够从其他作为子例程运行的算法中构建算法。在量子算法的情况下，可以将子例程称为不同输入的叠加，这使事物复杂化。例如，一种称为子例程$ q $ times的经典算法，在其中查询子例程在输入$ i $上的平均可能性是$ p_i $，而在输入$ i $ $ $ t_i $的subroutine成本为$ t_i $，Incurs预期的预期成本$ q \ sum_i p_i p_i p_i e [t_i e [t_i e [t_i] $ from subroutine queroutine queROutine queROutine queries yie querie querie querie querie queries yie querie querie queries。尽管对于经典算法而言，对于量子算法是显而易见的，但要少得多，因为天真，如果我们在输入的叠加上运行量子subroutine，我们需要等待叠加的所有分支才能终止，然后才能应用下一个操作。尽管如此，我们显示一个类似的量子语句（*）：如果$ q_i $是所有查询的平均查询权重，则所有量子子例程查询的成本为$ q \ sum_i q_i q_i e [t_i] $。在这里，对于特定查询的$ i $的查询权重是如果我们要在查询之前衡量输入寄存器中的$ i $的可能性。 我们使用多维量子步行的技术证明了这一结果，该技术最近在Arxiv：2208.13492中引入。我们提出了他们的量子步行边缘组成结果的更通用的版本，该版本可以产生可变的时间量子步行，从而将可变的时间量子搜索概括为例如，以$ \ sqrt {\ sum_ {\ sum_ {\ sum_ {u，v}π_Up_u p_ {顶点$ u $ to vertex $ v $。允许我们在量子步行中构成量子子例程的技术也可以用于在任何量子算法中构成，这就是我们证明（*）的方式。
An important tool in algorithm design is the ability to build algorithms from other algorithms that run as subroutines. In the case of quantum algorithms, a subroutine may be called on a superposition of different inputs, which complicates things. For example, a classical algorithm that calls a subroutine $Q$ times, where the average probability of querying the subroutine on input $i$ is $p_i$, and the cost of the subroutine on input $i$ is $T_i$, incurs expected cost $Q\sum_i p_i E[T_i]$ from all subroutine queries. While this statement is obvious for classical algorithms, for quantum algorithms, it is much less so, since naively, if we run a quantum subroutine on a superposition of inputs, we need to wait for all branches of the superposition to terminate before we can apply the next operation. We nonetheless show an analogous quantum statement (*): If $q_i$ is the average query weight on $i$ over all queries, the cost from all quantum subroutine queries is $Q\sum_i q_i E[T_i]$. Here the query weight on $i$ for a particular query is the probability of measuring $i$ in the input register if we were to measure right before the query. We prove this result using the technique of multidimensional quantum walks, recently introduced in arXiv:2208.13492. We present a more general version of their quantum walk edge composition result, which yields variable-time quantum walks, generalizing variable-time quantum search, by, for example, replacing the update cost with $\sqrt{\sum_{u,v}π_u P_{u,v} E[T_{u,v}^2]}$, where $T_{u,v}$ is the cost to move from vertex $u$ to vertex $v$. The same technique that allows us to compose quantum subroutines in quantum walks can also be used to compose in any quantum algorithm, which is how we prove (*).
