Quantum computation and combinatorial structures

Publication Type:
Issue Date:
Full metadata record
This thesis explores the relationship between quantum computation and combinatorial structures, with the goal of improving our understanding of the complexity of quantum computation. We begin by studying the case when the complexity of combinatorial structures can be used to provide evidence for the hardness of classically simulating quantum computations. To this end, we show that the complexity of evaluating multiplicative-error approximations of Jones polynomials can be used to bound the classical complexity of simulating random quantum computations. We then proceed by studying the contrary case, that is, when do the combinatorial structures allow for an efficient classical simulation of quantum computations? We establish an efficient deterministic approximation algorithm for the Ising model partition function with complex parameters when the interactions and external fields are absolutely bounded close to zero. This provides an efficient classical algorithm for simulating a class of quantum computations with bounded interactions between the qubits. In the second part of this thesis, we present some independent results on the efficient preparation of Fock states with a high number of photons from a resource of single photons. These Fock states are a fundamental resource in many quantum information protocols.
Please use this identifier to cite or link to this item: