| Summary: | <p>This thesis studies computational advantages that could be achieved by
using quantum resources in two different contexts.</p>
<p>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].</p>
<p>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.</p>
|
|---|