...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Power of Uninitialized Qubits in Shallow Quantum Circuits
【24h】

Power of Uninitialized Qubits in Shallow Quantum Circuits

机译：浅量子电路中未初始化量子位的功率

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

摘要

We study the computational power of shallow quantum circuits with O(log n) initialized and n^{O(1)} uninitialized ancillary qubits, where n is the input length and the initial state of the uninitialized ancillary qubits is arbitrary. First, we show that such a circuit can compute any symmetric function on n bits that is classically computable in polynomial time. Then, we regard such a circuit as an oracle and show that a polynomial-time classical algorithm with the oracle can estimate the elements of any unitary matrix corresponding to a constant-depth quantum circuit on n qubits. Since it seems unlikely that these tasks can be done with only O(log n) initialized ancillary qubits, our results give evidences that adding uninitialized ancillary qubits increases the computational power of shallow quantum circuits with only O(log n) initialized ancillary qubits. Lastly, to understand the limitations of uninitialized ancillary qubits, we focus on near-logarithmic-depth quantum circuits with them and show the impossibility of computing the parity function on n bits.
机译：我们研究了具有O（log n）初始化和n ^ {O（1）}未初始化辅助量子位的浅量子电路的计算能力，其中n是输入长度，并且未初始化辅助量子位的初始状态是任意的。首先，我们证明了这样的电路可以在n位上计算经典可在多项式时间内计算的任何对称函数。然后，我们将这种电路视为一个预言机，并证明具有预言机的多项式时间经典算法可以在n个量子位上估计与恒定深度量子电路相对应的任何unit矩阵的元素。由于仅用O（log n）初始化的辅助量子位似乎不可能完成这些任务，因此我们的结果提供了证据，即仅使用O（log n）初始化的辅助量子位添加未初始化的辅助量子位会增加浅量子电路的计算能力。最后，为了了解未初始化的辅助量子位的局限性，我们将重点放在具有它们的近对数深度量子电路上，并表明不可能在n位上计算奇偶校验函数。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号