Studies in classical simulation vs quantum advantage for algorithms and communication

Thesis

This thesis studies computational advantages that could be achieved by using quantum resources in two different contexts.

The first part studies Permutational Quantum Computing, a quantum computational model developed to study computation by spin recoupling. It was a conjecture, stated by Jordan in [Quantum Inf. Comput., 10, 470–497 (2010)], that the model solves problems that have no efficient classical algorithms by approximating its transition amplitudes to polynomial precision. Here we give a classical algorithm that disproves this conjecture and also prove that the computational complexity class PQP, defined to capture the computational power of the model in this regime, is entirely classical. The simulation algorithms are derived by utilizing the computational tractability framework of van den Nest [Quantum Inf. Comput., 9–10, 784–812 (2011)]. We look for other sources of quantum advantage in the computational model and rule out the possibility that it encodes answers to computationally hard problems in patterns of small number of significantly large output probabilities. This analysis extends the results of Schwarz and van den Nest [arXiv:1310.6749].

The second part of the thesis studies advantages achievable in the context of communication complexity. We take inspiration in the proof of the Pusey-Barrett-Rudolph theorem and devise a simple communication task based on the concept of quantum state antidistinguishability. We show that there is an exponential separation between one-way exact classical and quantum communication complexities for the task, but also that the separation for this particular task disappears if we allow for interaction or require only a bounded error solution. We conclude by stating and numerically justifying a conjecture about quantum state antidistinguishability that could have some implications for quantum foundations.

Authors: Havlicek, V

• DOI: 10.5287/ora-nznx9xxo4
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Keywords: Quantum Algorithms; Quantum Computation
• Subjects: Quantum Computation