Technical Report MSC-2006-28

Title: Quantum Advantage Even Without Entanglement
Authors: Ratsaby Gil
Supervisors: Tal Mor
Abstract: Two main motivations inspired this work. The first was to explore the role of entanglement in quantum computation, and more specifically whether significant quantum advantage over classical computation can exist without entanglement. The second was to explore the existence of new problems for which there is a quantum advantage, and the role of entanglement in them. We focused mainly on the case of exact pure-state quantum computing with oracles and promises, and obtained the following results: for the Deutsch-Jozsa problem we find the maximal sub-problem that can be solved without entanglement, and show that the Deutsch-Jozsa algorithm still has a non-negligible advantage over the best classical algorithm. We show that this sub-problem is of greater significance, by proving that it contains all the Boolean functions whose quantum phase-oracle is non-entangling. This approach is then generalized: we show that a Deutsch-Jozsa-like promise problem exists for any Boolean function, and find those that have an entanglement-free sub-problem. We then present a method for constructing a large amount of new promise problems for which there is a quantum advantage, and investigate entanglement-free sub-problems.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2006
To the main CS technical reports page

Computer science department, Technion