M.Sc Thesis

M.Sc StudentRatsaby Gil
SubjectQuantum Advantage, even without Entanglement
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Tal Mor
Full Thesis textFull thesis text - English Version


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.