Combinatorial Problems Arising from Quantum Computing

This thesis studies certain combinatorial problems that arise in the study of quantum computation. More precisely, we establish oracle results that exemplify ways in which the behavior of quantum polynomial time ($\mathsf{BQP}$) can be remarkably decoupled from that of classical complexity classes like $\mathsf{NP}$ and $\mathsf{BPP}$. We also study a problem related to a conjecture which would imply quantum supremacy results: bounding the cardinality of the range of the permanent.