Reversible Logic Synthesis Benchmarks Page

you are in... Main\hwbN functions

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.