Lower bounds on the non-Clifford resources for quantum computations
Lower bounds on the non-Clifford resources for quantum computations
复制标题
DOI：
10.1088/2058-9565/ab8963
复制
发表时间：
2020-07-01
影响因子：
6.7
通讯作者：
Kliuchnikov, Vadym
中科院分区：
文献类型：
--
作者：
Beverland, Michael;Campbell, Earl;Kliuchnikov, Vadym
将稳定器操作视为免费的，我们在资源状态的数量（也称为魔术状态）上建立了下限，需要执行各种量子计算任务。我们的边界适用于使用任意数量的稳定器Ancillas的测量值适用于自适应计算。我们考虑（1）资源状态转换，（2）单量单位合成，（3）计算子例程，包括量子加法器和多重控制的Z门。为了证明我们的资源转换范围，我们介绍了两个新单调，稳定剂无效和二元单调，并利用已经知道的稳定剂范围。我们考虑借用资源状态的转换，称为催化剂，并在算法结束时返回它们。我们表明，催化是许多转化所必需的，并引入了新的催化转化，其中一些是最佳的。通过找到用于固定后稳定器计算的规范形式，我们表明，将单量单位统一到钻石 - 标准精度E内部至少需要1/7。 log（2）（1/e） - 平均4/3T态。这是使用倒下后的混合技术以及所使用的辅助数量可以取决于e的第一个下限，适用于合成协议。为了达到乘法因素，我们最佳地降低了实施无处不在的模块化加法器和乘以控制的t态所需的t或ccz状态数量。当Pauli测量结果的概率为1/2时，我们的某些边界在一个小的附加常数内就变得紧密。
Treating stabilizer operations as free, we establish lower bounds on the number of resource states, also known as magic states, needed to perform various quantum computing tasks. Our bounds apply to adaptive computations using measurements with an arbitrary number of stabilizer ancillas. We consider (1) resource state conversion, (2) single-qubit unitary synthesis, and (3) computational subroutines including the quantum adder and the multiply-controlled Z gate. To prove our resource conversion bounds we introduce two new monotones, the stabilizer nullity and the dyadic monotone, and make use of the already-known stabilizer extent. We consider conversions that borrow resource states, known as catalyst states, and return them at the end of the algorithm. We show that catalysis is necessary for many conversions and introduce new catalytic conversions, some of which are optimal. By finding a canonical form for post-selected stabilizer computations, we show that approximating a single-qubit unitary to within diamond-norm precision e requires at least 1/7 . log(2)(1/e) - 4/3T-states on average. This is the first lower bound that applies to synthesis protocols using fall-back, mixing techniques, and where the number of ancillas used can depend on e. Up to multiplicative factors, we optimally lower bound the number of T or CCZ states needed to implement the ubiquitous modular adder and multiply-controlled-Z operations. When the probability of Pauli measurement outcomes is 1/2, some of our bounds become tight to within a small additive constant.