14 September 2005 Quantum advantage without entanglement
Author Affiliations +
Abstract
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, Dan Kenigsberg, Tal Mor, Tal Mor, Gil Ratsaby, 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
PROCEEDINGS
9 PAGES


SHARE
RELATED CONTENT

Using fewer qubits to correct errors in the three stage...
Proceedings of SPIE (October 07 2018)
Quantum teleportation and survey technology
Proceedings of SPIE (October 21 2010)
Sharing quantum secrets
Proceedings of SPIE (February 02 2004)
Quantum noise and probabilistic teleportation
Proceedings of SPIE (May 15 2003)
Quantum information theory for model abstraction techniques
Proceedings of SPIE (September 18 2001)
Graph state secret sharing in higher-dimensional systems
Proceedings of SPIE (August 30 2010)

Back to Top