arXiv:quant-ph/0511272AbstractReferencesReviewsResources
Quantum Advantage without Entanglement
Dan Kenigsberg, Tal Mor, Gil Ratsaby
Published 2005-11-30Version 1
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.
Comments: 10 pages
Journal: Quantum Information and Computation 6(7), 606--615 (2006)
DOI: 10.1117/12.617175
Keywords: quantum advantage, entanglement, pure-state quantum computation, non-trivial subproblems, quantum phase-oracle
Tags: journal article
Related articles: Most relevant | Search more
arXiv:quant-ph/0207149 (Published 2002-07-26)
Generalizations of entanglement based on coherent states and convex sets
Detailed balance and entanglement
arXiv:quant-ph/0703010 (Published 2007-03-01)
Entanglement in alternating open spin-1/2 chains with XY-Hamiltonian