Limiting the Search Space in Optimal Quantum Circuit Mapping
Limiting the Search Space in Optimal Quantum Circuit Mapping
复制标题
限制最佳量子电路映射中的搜索空间
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
R. Wille
中科院分区：
文献类型：
--
作者：
Lukas Burgholzer;Sarah Schneider;R. Wille
在当前可用的量子计算机上执行量子电路需要将它们编译为符合目标体系结构施加的所有限制的表示形式。由于设备物理量子位的连接性有限，编译过程中的一个重要步骤是以所有门都可以在硬件上执行的方式映射电路。为该任务提供最佳解决方案的现有解决方案受到问题指数级复杂性的严重挑战。在本文中，我们表明映射问题的搜索空间可以被极大地限制，同时仍然保持最优性。所提出的策略是通用的、独立于体系结构的，并且可以适应各种映射方法。这些发现得到了理论考虑和实验评估的支持。结果证实，通过限制搜索空间，可以为之前超时的实例确定最佳解决方案，或者可以实现高达三个数量级的加速。
Executing quantum circuits on currently available quantum computers requires compiling them to a representation that conforms to all restrictions imposed by the targeted architecture. Due to the limited connectivity of the devices' physical qubits, an important step in the compilation process is to map the circuit in such a way that all its gates are executable on the hardware. Existing solutions delivering optimal solutions to this task are severely challenged by the exponential complexity of the problem. In this paper, we show that the search space of the mapping problem can be limited drastically while still preserving optimality. The proposed strategies are generic, architecture-independent, and can be adapted to various mapping methodologies. The findings are backed by both, theoretical considerations and experimental evaluations. Results confirm that, by limiting the search space, optimal solutions can be determined for instances that timeouted before or speed-ups of up to three orders of magnitude can be achieved.
时间最优量子位映射
DOI：
10.1145/3445814.3446706
发表时间：
2021
期刊：
Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems
影响因子：
--
作者：
Zhang, Chi;Hayes, Ari B.;Qiu, Longfei;Jin, Yuwei;Chen, Yanhao;Zhang, Eddy Z.
通讯作者：
Zhang, Eddy Z.