...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Complexity Classification of Conjugated Clifford Circuits
【24h】

Complexity Classification of Conjugated Clifford Circuits

机译：共轭Clifford回路的复杂度分类

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Clifford circuits - i.e. circuits composed of only CNOT, Hadamard, and pi/4 phase gates - play a central role in the study of quantum computation. However, their computational power is limited: a well-known result of Gottesman and Knill states that Clifford circuits are efficiently classically simulable. We show that in contrast, "conjugated Clifford circuits" (CCCs) - where one additionally conjugates every qubit by the same one-qubit gate U - can perform hard sampling tasks. In particular, we fully classify the computational power of CCCs by showing that essentially any non-Clifford conjugating unitary U can give rise to sampling tasks which cannot be efficiently classically simulated to constant multiplicative error, unless the polynomial hierarchy collapses. Furthermore, by standard techniques, this hardness result can be extended to allow for the more realistic model of constant additive error, under a plausible complexity-theoretic conjecture. This work can be seen as progress towards classifying the computational power of all restricted quantum gate sets.
机译：Clifford电路-即仅由CNOT，Hadamard和pi / 4相门组成的电路-在量子计算的研究中起着核心作用。但是，它们的计算能力是有限的：Gottesman和Knill的众所周知的结果表明，Clifford电路可以有效地经典模拟。相比之下，我们表明，“共轭Clifford电路”（CCC）-可以通过相同的一个1比特的门U对每个qubit进行附加的共轭-可以执行硬采样任务。尤其是，我们通过证明基本上所有非Clifford共轭unit单元U都可以引起采样任务，除非多项式层次结构崩溃，否则它不能有效地经典地模拟为恒定的乘法误差，从而对CCC的计算能力进行了完全分类。此外，在合理的复杂性理论猜想下，通过标准技术，可以扩展该硬度结果，以实现恒定的加性误差的更现实的模型。这项工作可以看作是对所有受限量子门集的计算能力进行分类的进步。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号