Quantum Error Correction (QEC) is essential for future quantum computers due to its ability to exponentially suppress physical errors. The surface code is a leading error-correcting code candidate because of its local topological structure, experimentally achievable thresholds, and support for universal gate operations with magic states. However, its physical overhead scales quadratically with number of correctable errors. Conversely, quantum low-density parity-check (qLDPC) codes offer superior scaling but lack, on their own, a clear path to universal logical computation. Therefore, it is becoming increasingly evident that there are significant advantages to designing architectures using multiple codes. Heterogeneous architectures provide a clear path to universal logical computation as well as the ability to access different resource trade offs.

The Hidden Weighted Bit function plays an important role in the study of classical models of computation. A common belief is that this function is exponentially hard to implement using reversible ancilla-free circuits, even though introducing a small number of ancillae allows a very efficient implementation. In this paper, we refute the exponential hardness conjecture by developing a polynomial-size reversible ancilla-free circuit computing the Hidden Weighted Bit function. Our circuit has size O(n^6.42), where n is the number of input bits. We also show that the Hidden Weighted Bit function can be computed by a quantum ancilla-free circuit of size O(n^2). The technical tools employed come from a combination of Theoretical Computer Science (Barringtons theorem) and Physics (simulation of fermionic Hamiltonians) techniques.