A quantum circuit must be preprocessed before implementing on NISQ devices due to the connectivity constraint. Quantum circuit mapping (QCM) transforms the circuit into an equivalent one that is compliant with the NISQ device's architecture constraint by adding SWAP gates. The QCM problem asks the minimal number of auxiliary SWAP gates, and is NP-complete. The complexity of QCM with fixed parameters is studied in the paper. We give an exact algorithm for QCM, and show that the algorithm runs in polynomial time if the NISQ device's architecture is fixed. If the number of qubits of the quantum circuit is fixed, we show that the QCM problem is NL-complete by a reduction from the undirected shortest path problem. Moreover, the fixed-parameter complexity of QCM is W[1]-hard when parameterized by the number of qubits of the quantum circuit. We prove the result by a reduction from the clique problem. If taking the depth of the quantum circuits and the coupling graphs as parameters, we show that the QCM problem is still NP-complete over shallow quantum circuits, and planar, bipartite and degree bounded coupling graphs.
翻译:由于连通性限制,在安装 NISQ 设备之前必须预处理量子电路。 量子电路映射( QCM) 通过添加 SWAP 门, 将电路转换成与 NISQ 设备结构限制相符的等效电路。 QCM 问题要求最小的辅助 SWAP 门数, 并且是NP 完整的。 文件中研究了 QCM 与固定参数的复杂程度。 我们给出了 QCM 精确的算法, 并显示如果 NISQ 设备的结构固定下来, 算法在多音时间运行。 如果量电路的量子数已经固定, 我们显示QCM 问题通过减少未定向的最短路径问题而完成了 NL 问题。 此外, QCM 的固定参数复杂性是 W[ 1]- 硬度, 由量子电路路的数参数参数来测量。 我们证明, 如果将量子电路深度和组合图作为参数, 我们显示QCM 平面平面的平面和平面平面图问题仍然是平面的平面的平流。