Chenjian Li与Ji Guan证明CNOT精确综合的vanilla形式为NP困难

Chenjian Li与Ji Guan在论文摘要中证明，在无可用辅助量子比特、全连接且从固定标签量子比特恒等变换出发的vanilla CNOT精确综合问题为NP困难，其有界判定形式为NP完全。研究通过网格图Hamiltonian路径的归约和复制记录量子比特构造，将中间路径访问编码到最终输出，并报告该困难性在单位三角目标、近线性门预算以及零相位多项式综合中仍然存在；完整证明细节未在材料中提供。