|M.Sc Student||Ratsaby Gil|
|Subject||Quantum Advantage, even without Entanglement|
|Department||Department of Computer Science||Supervisor||Professor Tal Mor|
|Full Thesis text|
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.