Share Email Print
cover

Proceedings Paper

Quantum advantage without entanglement
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper 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.

Paper Details

Date Published: 15 September 2005
PDF: 9 pages
Proc. SPIE 5893, Quantum Communications and Quantum Imaging III, 58930N (15 September 2005); doi: 10.1117/12.617175
Show Author Affiliations
Dan Kenigsberg, Technion (Israel)
Tal Mor, Technion (Israel)
Gil Ratsaby, Technion (Israel)


Published in SPIE Proceedings Vol. 5893:
Quantum Communications and Quantum Imaging III
Ronald E. Meyers; Yanhua Shih, Editor(s)

© SPIE. Terms of Use
Back to Top