Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017.Cataloged from PDF version of thesis.Includes bibliographical references (pages 177-184).The field of quantum computing investigates the extent to which one can design a quantum system that outperforms all known classical hardware at a certain task. But, to what extent can a human being, capable only (perhaps) of classical computation and of observing classical bit-string messages, verify that a quantum device in their possession is performing the task that they wish? This is a fundamental question about the nature of quantum mechanics, and the extent to which humans can harness it in a trustworthy manner. It is also a natural and important consideration when quantum devices may be used to perform sensitive cryptographic tasks which have no known efficient classical witness of correctness (Quantum Key Distribution, and Randomness Expansion are two examples of such tasks). It is remarkable that any quantum behavior at all can be tested by a verifier under such a constraint, without trusting any other quantum mechanical device in the process! But, intriguingly, when there are two or more quantum provers available in an interactive proof, there exist protocols to verify many interesting and useful quantum tasks in this setting. This thesis investigates multi-prover interactive proofs for verifying quantum behavior, and focuses on the stringent testing scenario in which the verifier in the interactive proof is completely classical as described above. It resolves the question of the maximum attainable expansion rate of a randomness expansion protocol by providing an adaptive randomness expansion protocol that achieves an arbitrary, or infinite rate of randomness expansion [29]. Secondly it presents a new rigidity result for the parallel repeated magic square game [24], which provides some improvements on previous rigidity results that play a pivotal role in existing interactive proofs for entangled provers, QKD, and randomness expansion results. This new rigidity result may be useful for improving such interactive proofs in the future. The second half of this thesis investigates the problem of bounding the role of quantum entanglement in non-local processes. This is important for understanding the upper limit on the power of multi-prover interactive proof systems with entangled provers. In particular it establishes that, assuming the Strong Kirchberg Conjecture, one can provide a doubly exponential upper bound on the class MIP* [25] (for comparison, the best known unconditional upper bound on MIP* is that its languages are recursively enumerable!). Finally this thesis presents a result which characterizes the type of entanglement that is useful in entanglement assisted quantum communication complexity by showing that any communication protocol using arbitrary shared entanglement can be simulated by a protocol using only EPR pairs for shared entanglement. Therefore all quantum communication protocols can be approximately simulated by a protocol using only the maximally entangled state as a shared resource.by Matthew Ryan Coudron.Ph. D.