论文标题
用固定参数的量子电路映射的复杂性
The Complexity of Quantum Circuit Mapping with Fixed Parameters
论文作者
论文摘要
由于连接性约束，必须在在NISQ设备上实施之前对量子电路进行预处理。量子电路映射（QCM）将电路转换为相同的电路，该电路通过添加交换门符合NISQ设备的体系结构约束。 QCM问题询问辅助交换门的数量最少，并且是NP完整的。在纸张中研究了QCM与固定参数的复杂性。我们给出了QCM的精确算法，并证明如果固定了NISQ设备的体系结构，则该算法在多项式时间内运行。如果量子电路的量子数量是固定的，我们表明QCM问题是通过从无方向的最短路径问题降低来完成的。此外，当通过量子电路的量子数进行参数时，QCM的固定参数复杂性为W [1]。我们通过减少集团问题来证明结果。如果将量子电路的深度和耦合图作为参数，我们表明QCM问题在浅量子电路上仍然是NP完整的，而平面，双分和程度界面耦合图。
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.
