A Finite Presentation of CNOT-Dihedral Operators

被引：11

作者：

Amy, Matthew ^{[1
,2
]}

Chen, Jianxin ^{[3
,4
]}

Ross, Neil J. ^{[3
,4
]}

机构：

[1] Univ Waterloo, Inst Quantum Comp, Waterloo, ON, Canada

[2] Univ Waterloo, David R Cheriton Sch Comp Sci, Waterloo, ON, Canada

[3] Univ Maryland, Inst Adv Comp Studies, College Pk, MD 20742 USA

[4] Univ Maryland, Joint Ctr Quantum Informat & Comp Sci, College Pk, MD 20742 USA

来源：

ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE | 2018年 / 266期

基金：

加拿大自然科学与工程研究理事会;

关键词：

CLIFFORD; ALGORITHM;

D O I：

10.4204/EPTCS.266.5

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give a finite presentation by generators and relations of the unitary operators expressible over the {CNOT,T, X } gate set, also known as CNOT-dihedral operators. To this end, we introduce a notion of normal form for CNOT-dihedral circuits and prove that every CNOT-dihedral operator admits a unique normal form. Moreover, we show that in the presence of certain structural rules only finitely many circuit identities are required to reduce an arbitrary CNOT-dihedral circuit to its normal form. By appropriately restricting our relations, we obtain a finite presentation of unitary operators expressible over the {CNOT; T} gate set as a corollary.

引用

页码：84 / 97

页数：14

共 17 条

[1] Polynomial-Time T-Depth Optimization of Clifford plus T Circuits Via Matroid Partitioning [J].

Amy, Matthew ;

Maslov, Dmitri ;

Mosca, Michele .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2014, 33 (10) :1476-1489

[2] A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits [J].

Amy, Matthew ;

Maslov, Dmitri ;

Mosca, Michele ;

Roetteler, Martin .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2013, 32 (06) :818-830

[3]

[Anonymous], T COUNT OPTIMIZATION

[4]

[Anonymous], UNIFIED FRAMEWORK MA

[5]

[Anonymous], NPJ QUANTUM INFORM

[6] Rewriting modulo symmetric monoidal structure [J].

Bonchi, Filippo ;

Gadducci, Fabio ;

Kissinger, Aleks ;

Sobocinski, Pawel ;

Zanasi, Fabio .

PROCEEDINGS OF THE 31ST ANNUAL ACM-IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2016), 2016, :710-719

[7] Exact synthesis of multiqubit Clifford plus T circuits [J].

Giles, Brett ;

Selinger, Peter .

PHYSICAL REVIEW A, 2013, 87 (03)

[8]

Gosset D, 2014, QUANTUM INF COMPUT, V14, P1261

[9]

Kliuchnikov V, 2013, QUANTUM INF COMPUT, V13, P607

[10] Towards an algebraic theory of Boolean circuits [J].

Lafont, Y .

JOURNAL OF PURE AND APPLIED ALGEBRA, 2003, 184 (2-3) :257-310

← 1 2 →