Hidden weighted bit function hwbN
has N inputs and N outputs. Its output equals
its input shifted left on the number of positions equal to the number
of
ones
in the input pattern. Thus, hwbN
function is reversible. Hidden weighted bit function is known to have an
exponential
size BDD for any variable ordering. This type functions were first
proposed as reversible benchmarks
by Patel and Markov.
It is known that hwbN
functions may be implemented with polynomial quantum/reversible cost
assuming a logarithmic number of garbage bits is available. It remains an open
question if a polynomial cost reversible/quantum implementation exists
if addition of garbage bits is not allowed.