论文标题
网络可靠性的量子算法
A Quantum Algorithm for Network Reliability
论文作者
论文摘要
建立对组件故障有弹性的网络至关重要。我们获得电力和电信或物联网的访问权限，所有这些都可以在强大的网络提供的不间断服务上取决于。计算网络可靠性$ r $是$ \ sharp $ p-complete且棘手，可以准确计算中和大型网络。在这里，我们提出了计算$ r $的量子算法的明确，电路级实现。我们的算法需要$ o（ev/ε）$门操作和$ o（e）$ qubits，其中$ v $和$ e $是图表中的节点和边缘的数量，而$ε$是可靠性估算中的不确定性。在当前已知的最佳经典方法上，这构成了重要的多项式加速。我们进一步提供量子门计数，这与耐受耐受性和容忍度的政权相关，足以计算$ r $。
Building a network that is resilient to a component failure is vital. Our access to electricity and telecommunications or the internet of things all hinge on an uninterrupted service provided by a robust network. Calculating the network reliability $R$ is $\sharp$P-complete and intractable to calculate exactly for medium and large networks. Here, we present an explicit, circuit-level implementation of a quantum algorithm that computes $R$. Our algorithm requires $O(EV/ε)$ gate operations and $O(E)$ qubits, where $V$ and $E$ are the number of nodes and edges in the graph and $ε$ is the uncertainty in the reliability estimation. This constitutes a significant polynomial speedup over the best classical approaches currently known. We further provide quantum gate counts, relevant for both pre-fault-tolerant and fault-tolerant regimes, sufficient to compute $R$.
