量子科技中心_量科网

Beverland等人的前期工作[2]表明，要实现n量子比特托佛利门的精确克里福德+T电路，至少需要n个T门。本研究表明，通过引入可忽略的1/多项式(n)误差（该误差在多数实际应用中可忽略不计），便能以指数级减少T门数量。具体而言，通过随机选取的克里福德+T电路，仅需最多O(log(1/ε))个T门，即可在钻石距离度量下以ε误差实现n量子比特托佛利门。研究人员同时给出了匹配的Ω(log(1/ε))下限证明其最优性，并指出任何实现恒定误差的纯酉电路必须使用Ω(n)个T门。该工作还扩展采样技术以实现其他布尔函数，并基于非自适应奇偶决策树复杂度及其随机化变体，阐述了布尔函数T门数量的上下界。