Unlike classical routing algorithms, quantum routing algorithms make use of entangled states - a type of resources that have a limited lifetime and need to be regenerated after consumption. In a nutshell, quantum routing algorithms have to use these resources efficiently, while optimizing some objectives such as the total waiting time. Current routing algorithms tend to keep a routing request waiting until all of the resources on its path are available. In this paper, we introduce a new way of managing entanglement resources in an opportunistic fashion: a request can move forward along its path as soon as possible (even if some resources on its path are not ready). We show that this opportunistic approach is fundamentally better than conventional approaches. In particular, our results indicate that this new approach achieves a 30-50% improvement in the average total waiting time and average link waiting time compared with several state-of-the-art routing algorithms. As a by-product of this work, we develop a new simulator for quantum routing, which can be used to evaluate various design choices under different scenarios.
翻译:与古老的路线算法不同,量子路由算法利用缠绕状态 — — 这种资源寿命有限,消费后需要再生。 简言之,量子路由算法必须高效使用这些资源,同时优化某些目标,如全部等候时间等。 目前的路线算法往往在等待其道路上所有资源都具备之前,才提出路线要求。 在本文中,我们引入了一种以机会方式管理纠缠资源的新方式:请求可以尽快沿着路径前进(即使其路径上的一些资源尚未准备好 ) 。 我们表明,这种机会主义方法比常规方法要好得多。 特别是,我们的结果显示,这种新方法在平均的总体等待时间和平均等待时间方面实现了30-50%的改进,平均的等待时间比一些最先进的路线算法要长。 作为这项工作的副产品,我们开发了一个新的量子路由模拟器,可以用来评估不同情景下的各种设计选择。