EFFICIENT CLIFFORD plus T APPROXIMATION OF SINGLE-QUBIT OPERATORS

被引:0
作者
Selinger, Peter [1 ]
机构
[1] Dalhousie Univ, Dept Math & Stat, Halifax, NS B3H 4R2, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
circuit synthesis; Clifford plus T; efficient approximation of unitary operators; ALGORITHMS; GATES;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We give an efficient randomized algorithm for approximating an arbitrary element of SU(2) by a product of Clifford+T operators, up to any given error threshold epsilon > 0. Under a mild hypothesis on the distribution of primes, the algorithm's expected runtime is polynomial in log(1/epsilon). If the operator to be approximated is a z-rotation, the resulting gate sequence has T-count K+4 log(2)(1/epsilon), where K is approximately equal to 10. We also prove a worst-case lower bound of K+4log(2)(1/epsilon), where K = -9, so that our algorithm is within an additive constant of optimal for certain z-rotations. For an arbitrary member of SU(2), we achieve approximations with T-count K + 12 log(2)(1/epsilon). By contrast, the Solovay-Kitaev algorithm achieves T-count O(log(c)(1/epsilon)), where c is approximately 3.97.
引用
收藏
页码:159 / 180
页数:22
相关论文
共 16 条
[1]   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
[2]  
[Anonymous], 2013, ARXIV13126584
[3]  
[Anonymous], 2002, AM MATH SOC, DOI DOI 10.1090/GSM/047
[4]  
Cohen H., 2000, GRADUATE TEXTS MATH, V193
[5]  
Dawson CM, 2006, QUANTUM INFORM COMPU, V6, P81
[6]   Distillation of nonstabilizer states for universal quantum computation [J].
Duclos-Cianci, Guillaume ;
Svore, Krysta M. .
PHYSICAL REVIEW A, 2013, 88 (04)
[7]  
Fowler AG, 2011, QUANTUM INF COMPUT, V11, P867
[8]   Quantum computations: algorithms and error correction [J].
Kitaev, AY .
RUSSIAN MATHEMATICAL SURVEYS, 1997, 52 (06) :1191-1249
[9]  
Kliuchnikov V., 2013, ARXIV13104150
[10]  
Kliuchnikov V, 2013, QUANTUM INF COMPUT, V13, P607