Paper
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, Tal Mor, and Gil Ratsaby "Quantum advantage without entanglement", Proc. SPIE 5893, Quantum Communications and Quantum Imaging III, 58930N (14 September 2005); https://doi.org/10.1117/12.617175
Lens.org Logo
CITATIONS
Cited by 1 scholarly publication.
Advertisement
Advertisement
RIGHTS & PERMISSIONS
Get copyright permission  Get copyright permission on Copyright Marketplace
KEYWORDS
Quantum communications

Quantum computing

Evolutionary algorithms

Quantum efficiency

Quantum information

Quantum physics

Computer science

RELATED CONTENT

Discrimination of entangled quantum states
Proceedings of SPIE (December 16 2022)
Using fewer qubits to correct errors in the three stage...
Proceedings of SPIE (October 08 2018)
Quantum teleportation and survey technology
Proceedings of SPIE (October 22 2010)
Is quantum parallelism real?
Proceedings of SPIE (April 03 2008)
Graph state secret sharing in higher-dimensional systems
Proceedings of SPIE (August 30 2010)

Back to Top