arXiv Analytics

Sign in

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)
Categories: quant-ph, cs.CC
Related articles: Most relevant | Search more
arXiv:quant-ph/0207149 (Published 2002-07-26)
Generalizations of entanglement based on coherent states and convex sets
arXiv:1407.0520 [quant-ph] (Published 2014-07-02, updated 2015-03-27)
Detailed balance and entanglement
arXiv:quant-ph/0703010 (Published 2007-03-01)
Entanglement in alternating open spin-1/2 chains with XY-Hamiltonian