  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 for the implementation by 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 (Barrington's theorem) and Physics (simulation of fermionic
Hamiltonians) techniques.
