14 September 2005 Quantum advantage without entanglement
Author Affiliations +
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.
© (2005) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Dan Kenigsberg, Tal Mor, Gil Ratsaby, "Quantum advantage without entanglement", Proc. SPIE 5893, Quantum Communications and Quantum Imaging III, 58930N (14 September 2005); doi: 10.1117/12.617175; https://doi.org/10.1117/12.617175


Quantum teleportation and survey technology
Proceedings of SPIE (October 22 2010)
Applications of quantum message sealing
Proceedings of SPIE (May 25 2005)
Graph state secret sharing in higher-dimensional systems
Proceedings of SPIE (August 30 2010)
Quantizing knots, groups and graphs
Proceedings of SPIE (June 03 2011)

Back to Top