We consider exact quantum circuit synthesis, quantum gate efficiency, and the spectral gap conjecture from the perspective of computable analysis. Circuit synthesis, in both its exact and its approximate variant, is fundamental to the circuit model of quantum computing. As an engineering problem, however, the practical and theoretical aspects of quantum circuit synthesis are far from being fully understood. Particularly, this concerns explicit methods for gate-agnostic circuit synthesis and questions of gate efficiency. More than 20 years ago, Harrow et al. published their famous spectral gap theorem - given a suitable family of quantum gates, it is possible to approximate any unitary transformation by means of a quantum circuit whose length is proportional to the required accuracy's logarithm. Moreover, Harrow et al. suspected that all universal gate families allow for this type of approximation, a hypothesis that became known as the spectral gap conjecture and remains unproven until today. Being an entirely classical task, quantum circuit synthesis must be considered in the context of digital computing - that is, in the context of Turing computability and computable analysis. Using the relevant mathematical framework, we establish no-go results concerning exact quantum circuit synthesis and quantum big-O analysis. Our findings relate to the theory of approximate t-designs, which has recently received notable attention through the literature. Moreover, as follows from our findings, the existence of an algorithm that computes leading big-O coefficients would prove the spectral gap conjecture true within the computable special unitary group.