标题： 寻找轨迹覆盖：图态的近似最优分解作为线性融合网络 显示英文标题

标题： Finding trail covers: near-optimal decompositions of graph states as linear fusion networks

摘要： 量子编译需要开发新的算法，以优化在物理硬件上实现量子计算的成本。 通常这会引发在经典计算中渐近困难的问题，而启发式方法和对已知问题的归约在实践中非常有用。 在本文中，我们研究了三个图论问题，这些可以看作是欧拉路径和哈密顿路径问题的推广。 这些问题是光子测量基础量子计算实现中的产物，在这种实现中，图态是通过融合有限长度的线性资源态构建的。 由于融合操作成功的概率小于1，我们希望最小化构建特定图态所需的融合次数，这相当于找到图的最小路径或轨迹覆盖。 我们证明了这些覆盖问题在大多数情况下是NP难的，并给出了用于在图中寻找轨迹覆盖的启发式算法，包括对旅行商问题的归约。 我们提出了新的图态重写策略，以减少构建给定图所需的融合次数。 最后，我们将这些算法应用于光子融合网络的编译，并提供了一系列基准测试，展示了我们的算法在常见纠错码和QASMBench集中的电路上的性能。 显示英文摘要

摘要： Quantum compilation requires the development of new algorithms that optimise the cost of implementing quantum computations on physical hardware. Often this gives rise to problems which are asymptotically hard to solve classically, and for which heuristics and reductions to known problems are of great practical use. In this paper, we study three graph-theoretic problems which can be seen as generalisations of the Eulerian and Hamiltonian path problems. These arise in photonic implementations of measurement-based quantum computing, where graph states are constructed by fusing bounded-length linear resource states. Since the fusion operation succeeds with probability smaller than one, we wish to minimise the number of fusions required to build a particular graph state and this corresponds to finding a minimal path or trail cover of the graph. We show that these covering problems are NP-hard in most cases and give heuristic algorithms for finding trail covers in graphs including a reduction to the travelling salesman problem. We propose new rewrite strategies for graph states that reduce the number of fusions required to build a given graph. Finally, we apply these algorithms to the compilation of photonic fusion networks and provide a series of benchmarks showing the performance of our algorithms on common error-correcting codes and circuits from the QASMBench set.