Quantum advantage without entanglement
Quantum advantage without entanglement
复制标题
DOI：
10.1117/12.617175
复制
发表时间：
2005-08
期刊：
影响因子：
--
通讯作者：
D. Kenigsberg;T. Mor;Gil Ratsaby
中科院分区：
文献类型：
--
作者：
D. Kenigsberg;T. Mor;Gil Ratsaby
研究了无纠缠纯态量子计算相对于经典计算的优势。对于Deutsch-Jozsa算法，我们给出了可以在没有纠缠的情况下求解的最大子问题，并表明该算法仍然比经典算法具有优势。我们进一步表明，这个子问题是更大的意义，通过证明它包含所有的布尔函数的量子相位预言是非纠缠。对于西蒙和格罗弗的算法，我们提供了简单的证明，没有非平凡的子问题可以解决这些算法没有纠缠。
We study the advantage of pure-state quantum computation without entanglement over classical computation. For the Deutsch-Jozsa algorithm we present the maximal subproblem that can be solved without entanglement, and show that the algorithm still has an advantage over the classical ones. We further show that this subproblem is of greater significance, by proving that it contains all the Boolean functions whose quantum phase-oracle is non-entangling. For Simon's and Grover's algorithms we provide simple proofs that no non-trivial subproblems can be solved by these algorithms without entanglement.