Reversibility is an important trait for logic systems and an essential aspect of quantum computation. The conversion of traditional Boolean gates such as AND and XOR to the universal Toffoli gate allows for reversibility in classical n-bit to n-bit systems. Using logic pattern recognition and Mathematica’s powerful Boolean functionality, gate counts for reversible circuits can be determined from a given input function.

The Toffoli gate

An essential element in the construction of reversible circuits is the Toffoli gate, invented by Tommaso Toffoli in 1980. This gate takes three bits as input and acts as a controlled-controlled-NOT gate, meaning it flips the third bit if the first two bits are set to 1. Typically, one of both the input and output bits is a garbage bit. In shorthand, the functionality is as follows: {a,b,c} → {a,b,c⊻(a&&b)}. The gate is universal, meaning it can be used independently to represent any circuit. For this reason, this gate will be used extensively in this project.

Function reversibility

Before any reversible gates are implemented, it is essential that the function which they represent is reversible. Such functions are known to be bijective, as they are one-to-one and onto. Accordingly, anything that permutes the domain into the range is a bijective representation of that function. By determining if an input represents a valid permutation, the reversibility of the function can be decided. Note that bits get abstracted to decimal indices numbered from 1 to 2^n where n is the bit length of the function.
(Click arrows next to function names to view code)

Permutation Function


In[]:=
PermutationFunction[{4,3,1,2}]
Out[]=
{0,0}{1,1},{0,1}{1,0},{1,0}{0,0},{1,1}{0,1}
In[]:=
PermutationFunction[{4,3,1,3}]
Out[]=
$Invalid
There are n! reversible functions from n-bit inputs, which leads to a swift combinatorial explosion.
In[]:=
reversibleFunctions[bits_]:=(2^bits)!;​​reversibleFunctions[5]
Out[]=
263130836933693530167218012160000000
As such, it is crucial to find ways to avoid immense computational strain for even 5-bit functions. Initially, we hoped to achieve this by grouping functions by their symmetric properties to perform more generalized initial computations. However, we will soon demonstrate how this was instead achieved using Mathematica’s powerful BooleanConvert function.

Transposition observations

We initially hypothesized that we could attain Toffoli gate counts using the following algorithm: 1. Determine the number of transpositions in any function (p) 2. Determine the number of Toffoli gates to transpose two bits (q) 3. p*q = The number of Toffoli gates needed for that given function
This method was determined to be incorrect as it did not convey the functionality of a real circuit, but nonetheless led to some interesting observations. For example, we gained insight into the spread of transposition counts in functions of different length.

Transposition Counter


In[]:=
transpositionVisual=ListPlot[Table[transpositionCounter/@Range[100],10],​​PlotRange->{{0,100+1},{Min[0],Max[100]}},Frame->True,FrameLabel->{"Function Length","Transpositions"},​​PlotLabel->"Number of Transpositions per Function Length"]
Out[]=
We also developed a system using three Toffoli gates for the planar transposition of two bits. While not relevant to the scope of this project, this was an interesting discovery nonetheless.

New algorithms

Since the initial method for determining minimized Toffoli counts had proven to be trivial, we began developing potential new algorithms. The first was a generalized, “expensive” algorithm that hypothesized that any circuit could be made through iterated usage of a gate that transposes two rows and a gate that shifts every row in a hypothetical “stack”. Here is a visualization of these gates on a four-bit function:

Shift and Transpose


In[]:=
shiftAndTranspose=Grid[{{shift,transpose}},Spacings->3]
Out[]=
Shifted:
Transposed:
However, iterating over such gates would require very lengthy computations and require excessively large amounts of Toffoli gates. Therefore, we devised another algorithm for optimizing this computation in the form of a constructor function that records the order of the input (essential for minimizing the circuit).
This concept was based on the fact that for each n-bit to n-bit function, there are 2^n symmetric groups to work through to create a reversible circuit (“moving up the stack”). We planned to move transposed bits to the bottom of the “stack” to minimize the number of symmetric groups to work through. Accordingly, rows representing the identity across both the input and output would move to the top of the “stack”.

Utilizing Boolean functionality

Amid the efforts to develop these algorithms, a much simpler way for determining Toffoli counts in a given circuit presented itself. This came from using Mathematica’s functions BooleanFunction and BooleanConvert, which could find minimized traditional Boolean expressions for n-bit functions in algebraic normal form (ANF). This is essential because Toffoli gates can represent AND and XOR using a single gate, and ANF form expressions are denoted exclusively using AND, XOR, and NOT. Note that NOT is reversible and therefore does not require a Toffoli equivalent (although NOT can be expressed using Toffoli, hence Toffoli’s universality).
In[]:=
toffoli := {a, b, c ⊻ (a && b)};​​Column[{Last[toffoli]/.b->True,Last[toffoli]/.c->False,Last[toffoli]/.{a->True,b->True}}]
Out[]=
a⊻c
a&&b
!c
To utilize BooleanFunction or BooleanConvert, input functions must first be encoded from their binary form. Below is an example of an encoded 3-bit function:
In[]:=
threeBitCodes[permutation_]:=FromDigits[#,2]&/@Transpose[​​Tuples[{1,0},3][[permutation]]​​];​​codes=threeBitCodes[RandomSample[Range[8]]]
Out[]=
{150,92,209}
These codes can then be converted to standard Boolean expressions:
In[]:=
Grid[{BooleanConvert[BooleanFunction[#,3][a,b,c],"ANF"]&/@codes},Spacings->2]
Out[]=
a⊻b⊻c
a⊻b⊻(a&&b)⊻(a&&c)
!(b⊻c⊻(a&&b)⊻(b&&c))
Note that this is also a relatively quick method of computation due to the optimized nature of Mathematica’s documented functions, as seen by the timings below on the 40,320 3-bit reversible functions.

All Codes


In[]:=
allCodeTiming
Out[]=
6.×
-6
10
In[]:=
allFuncTiming
Out[]=
2.×
-6
10

Toffoli gate counting & pattern matching

The first task is to count Toffoli patterns in the functions for a given bit length. Once those are determined, the remaining AND and XOR gates can be counted as each taking a single Toffoli gate for construction. NOT gates get counted separately since they are relevant to constructing reversible circuits but do not require Toffoli equivalents.
To do this, we utilize a counting function which uses Mathematica’s FixedPoint function to act in a recursive manner. This function takes a Boolean expression as input, before performing round after round of minimization by recognizing Toffoli patterns (of the generic form c ⊻ (a && b)). After each round of this reduction, the minimized patterns are replaced by an indicator with an index before the counting function is called again. This function can now recognize indicators from the previous minimization as a part of the Toffoli pattern, and the reduction process continues until no patterns remain. At this point, any outstanding AND or XOR gates are added to the overall Toffoli count, which has been incremented with each pattern reduction throughout the process.

Counting Functions

In[]:=
newCountingFunction[ind_][exprIN_]:=Module[​​{expr=exprIN,first,plus,args,countTof=0,count},​​​​first=First[SortBy[Union[Cases[expr,​​XOR[a_,AND[b_,c_]],{0,Infinity}]​​],Depth],True];​​​​If[!TrueQ[first],​​count=Count[expr,first,{0,Infinity}];​​args={first[[1]],first[[2,1]],first[[2,2]]};​​plus=Total[If[Or[AtomQ[#],MatchQ[#,z[_]]],0,​​Count[#,_XOR|_AND,{0,Infinity}]​​]&/@args];​​​​(* Sowing count *)​​countTof=(1+plus)*count;​​Sow[countTof];ind++;​​Fold[ReplacePart[#1,#2->z[ind]]&,expr,​​Position[expr,first]],​​expr]​​]
We use these functions to determine the Toffoli gate counts in a minimized system, which can be compared with non-minimized gate counts for the same system. The following function displays the codes, Toffoli gate counts, NOT counts, and non-minimized gate counts for each bit transition. Note that a permutation of 2^n values (n being the function’s bit count) is also shown, representing a decimal representation for the order of the 2^n binary values of each column.

Visualizations

To more effectively display the functions and their gate counts, the following visuals include array plots to represent the binary transpositions of input/output values.
The codes and their corresponding functions refer to transpositions between each row of the array plots, and circuits to preform these operations can be minimized by the Toffoli gate counts listed. The fact that these Toffoli counts are often smaller than the non-minimized counts demonstrates the importance of avoiding an algorithm which merely replaces each XOR and AND gate with its Toffoli counterpart. Moreover, such an algorithm would be less efficient in a practical sense due to an increased count of garbage bits needed in the system. These are major motivating factors in making our algorithm reduce original functions by using Toffoli patterns.

Gate count comparisons

While the minimization capabilities of this algorithm are evident immediately, it is useful to see the impact of its use over every function of a given bit length. Over any given function, this impact can be negligible or quite large.
To better understand the magnitude of these differences over every function of a given bit length, we will analyze the spread of these values.
Minimizing the patterns can prove quite effective across the spread of every function of a certain bit length. The difference between the average number of gates used is 4.02857. In a practical setting, this leads to much simpler circuits with far fewer garbage bits than if a Toffoli gate had merely replaced every AND and OR operation.
Unfortunately, acquiring this statistical data over every function for a given bit length proves to be quite challenging, due to the aforementioned combinatorial explosion of n-bit functions’ permutations. For example, a 5-bit function would have (2^5)! permutations to represent possibilities for a reversible system. It is unfeasible to work through these 263,130,836,933,693,530,167,218,012,160,000,000 permutations and gain statistical observations on their minimization due to time and memory constraints. However, determining gate counts of individual functions of such length can still be calculated quickly using the algorithms described in this project.
For some final observations, we can see that the maximum amount of gates reduced is nine. Included is the first example of a 9 gate reduction. This notable minimization occurs 48 times, whereas zero reductions occur 1344 times.

Example circuits

To illustrate the impact of reducing gate counts using Toffoli patterns, we include visualizations of partial circuit synthesis using the different methods on the function b⊻c⊻(a&&b). This further demonstrates the importance of gate minimization in simplifying circuits and minimizing use of garbage bits.

Concluding remarks

The results of this project give insight into methods for minimizing gate counts in reversible functions and reducing Boolean functions using the Toffoli gate. However, there are ample opportunities for continued investigation, especially for efficient automated synthesis of these circuits. This includes the minimization of garbage bits required for Toffoli-based circuits and redevelopment for quantum circuit applications. Additionally, finding ways to systematically group functions of n bits is essential for avoiding problematic combinatorial explosions. While this project has allowed for individual inputs with higher bit counts to be analyzed, it would be beneficial to also gain statistical conclusions from all functions with more than three bits.

Acknowledgement

I am extremely grateful for Bradley Klee’s assistance and support as my mentor in the development of this project. His patience and insight into the effective implementation of code and the project’s direction was incredibly valuable. Additionally, I thank Johannes Martin, Russell Martinez, Zsombor Meder, and Bowen Ping for their collaboration and encouragement as a part of my group. I would finally like to thank Stephen Wolfram and the entire Summer School staff for this wonderful learning opportunity and their assistance in project selection.

Keywords

◼
  • Toffoli gate
    • ◼
  • Logic systems
    • ◼
  • ANF Boolean functions

    • References

    ◼
  • De Vos , A.; Van, Y. (2005, May 1). Reversible computing: Proceedings of the 2nd Conference on Computing Frontiers. ACM Conferences. https://dl.acm.org/doi/10.1145/1062261.1062270
    • ◼
  • Dueck, G. W.; Maslov, D. (1997). Reversible function synthesis with minimum garbage outputs. https://www.cs.unb.ca/~gdueck/reversible/synthesis.pdf

    • CITE THIS NOTEBOOK

    Exploring minimized reversible circuits for n-bit functions​
    by Benjamin Peter​
    Wolfram Community, STAFF PICKS, July 12, 2023
    ​https://community.wolfram.com/groups/-/m/t/2958640