量子科技中心_量科网

由CNOT门和Rz门构成的量子电路是众多量子算法的基本构建模块，因此优化此类量子电路的合成至关重要。该研究团队从理论角度出发，通过研究图形奇偶网络合成问题来解决这一难题。针对图G的图形奇偶网络是由纯CNOT门构成的量子电路，其中G的每条边都在电路中得以体现，且导线最终状态与原始输入相匹配。研究目标是为采用伊辛模型表述的组合优化问题设计门数量最少的图形奇偶网络。 研究证明：对于具有n个顶点和m条边的连通图，其图形奇偶网络至少需要m + n − 1个门。当图中最短环长度不小于5时，该下界可提升至m + Ω(m) = m + Ω(n^1.5)。该团队提出一种简单的随机化算法作为补充，能以m + O(n^1.5√(log n))的期望门数合成图形奇偶网络。 此外，研究人员开始探索允许使用精确m + n − 1个门构建图形奇偶网络的连通图，推测所有此类图都属于新定义的图类，并针对该图类提出了线性时间的最小图形奇偶网络合成算法。然而，该图类在诱导子图操作下不具备封闭性，且团队证明其识别问题是NP完全问题，同时给出了基于树宽参数的固定参数可解算法作为补充。