Current efforts towards scaling quantum computer focus on increasing the qubit count or reducing noise. We propose an alternative strategy: qutrits. In prior work, qutrits conferred only a lg(3) constant factor advantage via binary to ternary compression. We introduce a new technique that maintains binary input and output, but uses intermediate qutrit states that replace ancillas. We show that this technique leads to asymptotically better circuit depths. Our circuit constructions have polylog depth, compared to linear depth for qubit-only circuits. We explore the tradeoff of operating higher-error qutrits by performing simulation under realistic noise models. Our simulations suggest that our techniques would significantly improve circuit fidelity by orders of magnitude, even for current device errors and sizes. Our circuit constructions are applicable to a broad range of quantum algorithms.