  Quantum circuits with symmetry-respecting gates have attracted broad interest
in quantum information science. While recent work has developed a theory for
circuits with Abelian symmetries, revealing important distinctions between
Abelian and non-Abelian cases, a comprehensive framework for non-Abelian
symmetries has been lacking. In this work, we develop novel techniques and a
powerful framework that is particularly useful for understanding circuits with
non-Abelian symmetries. Using this framework we settle an open question on
quantum circuits with SU(d) symmetry. We show that 3-qudit SU(d)-invariant
gates are semi-universal, i.e., generate all SU(d)-invariant unitaries, up to
certain constraints on the relative phases between sectors with inequivalent
representation of symmetry. Furthermore, we prove that these gates achieve full
universality when supplemented with 3 ancilla qudits. Interestingly, we find
that studying circuits with 3-qudit gates is also useful for a better
understanding of circuits with 2-qudit gates. In particular, we establish that
even though 2-qudit SU(d)-invariant gates are not themselves semi-universal,
they become universal with at most 11 ancilla qudits. Additionally, we
investigate the statistical properties of circuits composed of random
SU(d)-invariant gates. Our findings reveal that while circuits with 2-qudit
gates do not form a 2-design for the Haar measure over SU(d)-invariant
unitaries, circuits with 3-qudit gates generate a t-design, with t that is
quadratic in the number of qudits.
