Synthesis of the Optimal 4-bit Reversible Circuits

Details Synthesis of the Optimal 4-bit Reversible Circuits Synthesis of the Optimal 4-bit Reversible Circuits

2010-03-09

arxiv.org/abs/1003.1914v1

Physics

Quantum Physics

Scientific paper

Optimal synthesis of reversible functions is a non-trivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a huge search space (16!~2^44 functions). The output of such a search alone, counting only the space required to list Toffoli gates for every function, would require over 100 terabytes of storage. In this paper, we present an algorithm that synthesizes an optimal circuit for any 4-bit reversible specification. We employ several techniques to make the problem tractable. We report results from several experiments, including synthesis of random 4-bit permutations, optimal synthesis of all 4-bit linear reversible circuits, synthesis of existing benchmark functions, and distribution of optimal circuits. Our results have important implications for the design and optimization of quantum circuits, testing circuit synthesis heuristics, and performing experiments in the area of quantum information processing.

Affiliated with

Also associated with

No associations

Rating

Synthesis of the Optimal 4-bit Reversible Circuits does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Synthesis of the Optimal 4-bit Reversible Circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Synthesis of the Optimal 4-bit Reversible Circuits will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-455378