On the controlled-NOT complexity of controlled-NOT–phase circuits

Amy, Matthew, Azimzadeh, Parsiad, Mosca, Michele · 2018 · Quantum Science and Technology

| 编号 NA098 | 主题 线路综合与等价验证 | DOI 10.1088/2058-9565/aad8ca |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

2018 · Quantum Science and Technology We study the problem of CNOT-optimal quantum circuit synthesis over gate sets consisting of CNOT and Z-basis rotations of arbitrary angles. We show that the circuit-polynomial correspondence relates such circuits to Fourier expansions of pseudo-Boolean functions, and that for certain classes of functions this expansion uniquely determines the minimum CNOT cost of an implementation. As a corollary we prove that CNOT minimization over CNOT and phase gates is at least as hard as synthesizing a CNOT-optimal circuit computing a set of parities of its inputs. We then show that this problem is NP-complete for two restricted cases where all CNOT gates are required to have the same target, and where the circuit inputs are encoded in a larger state space. The latter case has applications to CNOT optimization over more general Clifford+T circuits. We further present an efficient heuristic algorithm for synthesizing circuits over CNOT and Z-basis rotations with small CNOT cost. Our experiments show a 23% reduction of CNOT gates on average across a suite of Clifford+T benchmark circuits, with a maximum reduction of 43%.

全文共 21 页；文本提取件位于 .extracted/papers/NA098.txt（不随站点发布）。

本站词条在引用该文献时，会以 wikilink（sources/NA098）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。