  Research on quantum computing has recently gained significant momentum since
first physical devices became available. Many quantum algorithms make use of
so-called oracles that implement Boolean functions and are queried with highly
superposed input states in order to evaluate the implemented Boolean function
for many different input patterns in parallel. To simplify or enable a
realization of these oracles in quantum logic in the first place, the Boolean
reversible functions to be realized usually need to be broken down into several
non-reversible sub-functions. However, since quantum logic is inherently
reversible, these sub-functions have to be realized in a reversible fashion by
adding further qubits in order to make the output patterns distinguishable (a
process that is also known as embedding). This usually results in a significant
increase of the qubits required in total. In this work, we show how this
overhead can be significantly reduced by utilizing coding. More precisely, we
prove that one additional qubit is always enough to embed any non-reversible
function into a reversible one by using a variable-length encoding of the
output patterns. Moreover, we characterize those functions that do not require
an additional qubit at all. The made observations show that coding often allows
one to undercut the usually considered minimum of additional qubits in
sub-functions of oracles by far.
