Paper Title (use style: paper title)



CHAPTER 8

SYNTHESIS OF REVERSIBLE CIRCUITS

WITH NO ANCILLA BITS

Maher Hawash, Marek Perkowski and Nouraddin Alhagi

1 Introduction. types of algorithms for reversible circuits synthesis.

There are currently two types of algorithms to synthesize reversible circuits:

(T1) those like MMD [Agrawal04, 3, 4, 7, 9, 10, 11, 14, Maslov03a, Maslov03b, Maslov04, Maslov07, Maslov08, Maslov11, Miller03, Miller03a] that start from a reversible specification,

(T2) those like [6, 12, 13, Mishchenko01, Mishchenko02, Stedman05, Saedi07, Saedi07a, Saedi07b, Wille08, Wille08a, Wille09] that start from non-reversible specification and create ancilla bits.

The second type of methods has been successful for large functions [5, 6, Wille08, Wille08a, Wille09] but solves basically a different problem.

The MMD algorithm [Miller03] (Miller, Maslov and Dueck) is currently the leading reversible logic synthesizer if no ancilla bits are used. Mathematically, the problem is to decompose a large permutation of circuit’s specification to small permutations of reversible gates that are used. This MMD program uses the permutation vector-like reversible function specification as its input an internal data. This data specification which corresponds to a truth table that is explicitly used in the synthesis process and, thus, must be stored and processed in memory. Since it is intrinsically bound by the natural binary order of minterms, and hence does not use search, MMD cannot be enhanced through better search algorithms or iterative/recursive routines. MMD MMD uses no search and it can be not improved by searching or iterating, as its very principle is the natural (binary) ordering of minterms and the synthesis of the function in this order. Since MMD it processes a single order of minterms. H order, and, hence, produces one result. MMD software is reasonably fast and it distinguishes itself among other programs of this type because it achieves (theoretical) 100% convergence regardless the problem size [Miller03]. Practically, however, it can be applied to at most 8 qubit reversible functions and very few reversible functions with more than 8 variables were presented as MMD benchmarks in the literature. It was found both that the complexity of both the synthesis process and the average circuit sizes synthesized by MMD grow very quickly above 8 qubits, herein . We will call them “large circuits”. An approach for large functions was presented in [Alhagi10]. Benchmarks for large functions are given there.

Consequently, in this chapter, we set the benchmark for future research it is difficult to evaluate the reversible minimize quality as there are no data to compare the obtained solutions with (observe that standard non-reversible specifications are used in recent papers [Rice09, Saedi07, Saedi07a, Saedi07b, Wille08, Wille08a, Wille09], and we need reversible functions such as specified by permutations). In any case, at this time MMD program is the current benchmark for the evaluation of programs for reversible circuit synthesis with no ancilla bits. A strong asset of the philosophy used in MMD, in contrast to those used in other programs is that MMD gives a warranty of convergence if the data is small enough for MMD to be able to keep them in memory. Due to the known fact that the quality of MMD may be very low for functions where the exact minimal solution is known, several research groups are constantly attempting to improve on the MMD algorithm.

2 the Algorithm of Agrawal and Jha.

Agrawal and Jha’s algorithm [Agrawal04, 6] uses the number of terms in the Positive Polarity Reed-Muller (PPRM) expansion of synthesized functions as its cost function. As PPRM can be stored by an expression that is shorter than 2n their algorithm could in theory minimize larger functions. On the other hand this algorithm needs has to store not one PPRM equation but many PPRM equations as it represents is a tree-search algorithm. Also, non-factorized PPRMs may be in many cases of similar complexity to truth tables, for instance for function f = a’b’c’d’. Some of the algorithm variants from [Agrawal04, Donald08, 7, 9] have trouble with convergence and there is a trade-off between provable convergence and size of circuits that can be minimized. A challenge thus still exists to create an algorithm that could trade-off quality for time, but with a provable convergence for every function. In this chapter we will present such an algorithm.

3 the MMD Algorithm of Maslov, Miller and Dueck

To make the chapter self-contained we give a brief overview of MMD. More can be found in [4, 14, Maslov03a, Maslov03b, Maslov04,Maslov07, Maslov08, Maslov11, Miller03, Miller03a].

The main idea of all algorithms for reversible circuits synthesis of type T1 is to transform stepbit-by-step bit a reversible function to its identity function.

Example 8.2.1. Fig. 8.1 explains illustrates the basic flow of MMD algorithm. The first column are lists all input minterms of the function in the order of natural number numerical order(linear) ordering: 0, 1, 2, 3, etc. The second column in Fig. 8.1 are lists values of the output vectors that correspond to the input vectors from the first column. For instance, we see thatthat the input minterm a’ b’ c’ = 000 is mapped to the output minterm A’ B’ C’ = 000 and . Similarly minterm input 001 is mapped to minterm the output minterm 100. The minterm that maps to itself , like 000 ( 000 is called the sSelf-mapping minterms are minterms with matching input and output values (e.g., minterm 000 above). As we see in Table from Fig. 2.1 minterm 111 is also a self-mapping minterm. The synthesis process applies successive gates to the output column (ABC), bit-by-bit, to generate the corresponding minterm of the input column (abc). The next columns represent the results of applying successive gates to the output minterms. The synthesis process is thus executed from outputs to inputs. Recall that Toffoli (Feynman) gates are used that are self-inverse gates (M-1 = M), so they process information the same way from inputs to outputs and from outputs to inputs. The MMD algorithm shown here is thus the “backward searching” or “output to input searching” algorithm. Since the first minterm is self-mapping, MMD skips to the second minterm applying a controlled- Feynman gate to bit c, shaded, conditional on bit a being set, underscored. After applying the application of each gate, the column of output column minterms (of intermediate functions) should become more and more similar to the first column – the column of input vectors. The question is “what does it mean to be more similar?” It is an advantage of general search methods that various measures of complexity or coincidence or similarity have been used [9, 10, 11, Mishchenko02]. This may lead to better and faster solutions but it is hard or impossible to prove convergence. The MMD algorithm has however a very simple and working solution to this problem. They just wantIt requires that the intermediate columns be remain exactly the same as the input column in some subset of rows from the top. The completed rowsrows, we call them the “completed rows” are from start from row 0, then next row 1, row 2 etc. up to the minterm under construction (the completed rows are shaded in Fig. 2.1). When some subset of rows from top is are completed, they cannot are not allowed to changebe changed (shown in shaded areas in Fig. 8.1) which is guaranteed by the selection of proper control bits.

|abc |ABC |1 |2 |

| | |Gates |Q-Cost |Time(ms) |Gates |Q-Cost |Time(ms) |

|4 |hwb4 |24 |120 |0.577 |19 |91 |339 |

|5 |hwb5 |62 |498 |0.033 |53 |389 |392 |

|6 |hwb6 |164 |1,800 |0.075 |140 |1,276 |613 |

|7 |hwb7 |382 |5,614 |0.247 |353 |4,961 |1503 |

|8 |hwb8 |883 |17,927 |1.312 |837 |15,873 |987 |

|9 |hwb9 |2050 |52,318 |4.171 |1993 |48,817 |4,170 |

|10 |urf3 |3426 |119,986 |12.595 |3334 |110,910 |58,306 |

|11 |urf4 |10527 |456,139 |75.780 |10336 |403,184 |384,589 |

Figure 8.5. Comparison of numbers of gates and quantum costs of MMD and MP algorithms for reversible functions with various numbers of bits. This is “large circuits” variant with k=5000. No ancilla bits.

8.5. 4. Algorithm MP

After many failed attempts at creating better minimizers based on other search strategies [Alhagi, 13, Mishchenko02, Stedman05], we decided to improve MMD. The main weakness of MMD is that it is limited to functions of the size that their truth table (exponential size) can fit into the in memory. This limits practically MMD's approach to about 13 variables. Because of its design principle, even with big speed penalty MMD just cannot minimize larger functions. Thus an improved algorithm has to use an entirely different representation. When it was decided to use an internal representation other than a truth table or a spectrum with 2n minterms, the problem was “what is the best representation that would still guarantee convergence?”. Kerntopf used a new type of decision diagrams but he did not prove the convergence and, as a result, his method only worked only for 3 variables. In unpublished research we used ESOPs and FPRMs rather than PPRM but we were not able to find a heuristic that would work better than the variants from [Agrawal04, Donald08, 7, 9]. Other cascade types have been also proposed in the newer versions of composition-based search approaches [11, Mishchenko01, Mishchenko02, Alhagi] but there were troubles with either the size of solutions or convergence. Here we present a search method that is both convergent, and allows for synthesis of large functions, and produces near minimal solutions. This algorithm includes variants which are various generalizations of MMD.

8.5.1. Ideas.

The Eearlier attempts at improving MMD algorithm resulted in very good/minimal solutions for some circuits or non-converging/incorrect circuits for others [Alhagi10, 10, 11, Mishchenko02, Stedman05]. Thus the order of selecting outputs to be covered by gates was found experimentally to be more important than the gate heuristics to choose gates. For more larger number of variables, a variant of our algorithm was created based on the following principles below:

[pic](1) Rather than maintaining a set of tables mapping inputs to outputs, the algorithm creates these columns implicitly, simulating minterms one-by-one. It does not create columns of minterms as in section 2 but creates these columns implicitely, simulating the minterms one-by-one. The simulator uses the equations from the specification together with the part of the already constructed reversible circuit. To demonstrate the concept, The best way to explain this idea is to imagine two circuits similar to like one from Fig. 8.2 composed cascaded back to back and simulated from inputs at each stage of minterm transformation. The first circuit, is described by equations, represents the function under synthesis, and the second circuit is the outcome of synthesis. is the circuit that is created (in reverse order of gates). When the synthesis is process completeds, we have two equivalent circuits, one mirror of the another exist, where . The the first circuit is specified by equations, and the second by reversible gates (in reverse order of gates). When we simulate this composed circuit, for every input minterm, the same minterm is obtained at the outputs of the concatenated circuits, and hence,, thus the concatenated circuits together are a reversible identity. Since Thus one of them is the circuits mirror of one another one, . Tthe solution is then the represented by the reverse of the second circuit from of the concatenationconcatenated whole.

Table 2. Comparison of numbers of gates and quantum costs of MMD and MP algorithms for reversible functions with various numbers of qubits. This is “large circuits” variant with k=10. No ancilla bits.

(2) The A number k of randomly selected MMDSN orders are generated for mintermsrepresenting the function under synthesis. The best solution with optimal cost is selected out of all these solutions. with the possibility of Earlier backtracking is possible if the temporary cost exceeds the minimum cost found determined earlier in the process.

(3) When possible, template matching method from MMD is used on the result for post-processing to further improve the quantum cost.

8.5.2. Results of MP for Four Variables.

For functions of four variables, we created a set of randomly generated four-bit reversible functions, AHP1-AHP50, and synthesized them using the original MMD, MMDS and our MP orders. For MMDS and MP, we tested the AHP functions against all possible permutations and calculated the minimum possible gate count as shown in Table 8.1. It is evident that our selective order consistently produce superior results compared to the single MMD order for a negligible time penalty. Notice , however, that although the MMDSN order did not generate the optimal gate count generated by MMDS, the time advantage of MP is huge at 4 bits, and would be astronomical at greater number of bits. Even at higher number of bits, MMDSN order consistently produces better results than MMD within tolerable time. For example, at 11 bits, MP accrued a saving of 191 gates taking about six minutes to synthesize 5000 MMDSN sequences selected at random, and maintaining the solution with the best gate count. Although the current implementation of the MP algorithm does not utilize parallel processing, the algorithm is prime for parallelization through threading, multiprocessing or within a cloud infrastructure. Such capability would allow for synthesizing a selecting a larger iteration variant (k) and thus produce even larger circuits. The reader should note that in this study, neither MMD or MP used local optimization techniques, e.g. template matching, which would ideally reduce the number of gates even further. Although MP would run even slower with template matching, its inclination to parallelization would easily minimize such an impact. new benchmarks NA1 – NA50, we created a variant of algorithm that generates all MMDS orders and finds the best order, i.e. the reversible circuit with the minimum cost. The results for functions of four variables are shown in Table 1 (we created our own benchmarks since there are very few 4-variable benchmarks in literature). This table demonstrates that algorithm MP is better than MMD in terms of total quantum costs. It is slower, though. In few cases that MMD was better than MP in Table 1 were because the MMD used template matching local optimization and MP was not using any local optimization after the search. However, for small functions we can always use the original MMD after MP algorithm to use template matching and achieve better results. Observe that MMD runs just once and has no search. Thus running MP with all or at least many orders and next using MMD-based template matching creates algorithm that is always better than MMD but running slower. It would be an easy way “to win” with MMD. An additional However, additional advantage of MP approach is that we can have a trade-off – the longer we run the new combined algorithm the better is potentially our result. This property is missing in both MMD and Agrawal/Jha approaches.

8.5.3. Results of the MP for more than four Variables.

Table 8.2 shows the results with k = 105000 produced with a single threaded application on a Windows 7 operating system running on a Intel® Core™2 Duo 2.93 GHz processor. The application allows the user to k to any value to get the trade-off between synthesis time and quantum cost improvement. As of this writing, we were not able to compare MP with original MMD on larger functions since MMD does not accept functions of 30 variables as it is not able to store a vector with 230 rows in memory.

As we see in Table 8.2, the improvement here is best for functions with less than 7 variables, which means that k should be increased. To understand the limitation of our approach for very large functions we created 10 randomly generated reversible functions of 30 variables [Alhagi10], which were input as separate equations for each bit (this variant of MP is not format compatible with MMD and other programs). Such large benchmarks do not exist in literature. For instance, function Chal30, shuffled 1,073,741,824 times (230 times), number of gates generated 430,296 (calculated by program MP, not RCV, circuit was so large that quantum cost software did not work). We run 20 orderings, it took 1 hour and 9 minutes to run. Results for other benchmarks from this set are similar. The results of MP are available on .

8.5.4. Conclusions ON MP.

We presented a new algorithm MP to synthesize reversible circuits in the spirit of MMD. As the algorithm is a generalization of MMD, it can never create solutions worse than those by MMD. But it can create results of smaller cost and can find solutions to problems that are too large for MMD to handle. Our algorithm does not require to store the large truth table or other exponential representation as it calculates the values in the run from the logic equations. Although MP still needs an exponential number of simulations, it does not need to store exponential data. Also we use many orders of minterm creation which leads to more efficient circuits. However, we pay the price of a slower synthesis process. The results have been also extended to synthesis of incompletely specified functions and ancilla bits [Alhagi10] and state machines [Kumar07, Kumar08]. As the reversible logic is still a research rather than industrial topic, speed of obtaining the solution seems to be less important than exploring larger circuits and being able to evaluate their quality. The trade-off that exists in MP between the time and cost of solution helps in this research.

8.6. Recent research on reversible circuits with no ancilla qubits

to be added.

References

1] [Agrawal04] A. Agrawal, and N.K. Jha, Synthesis of reversible logic, Proc. DATE, Paris, France, Febr. 2004, pp. 1530-1591

2] [Alhagi10] N.Alhagi, A Synthesis Method to Synthesize Reversible Functions using Arbitrary Gates and Relational Specification, Ph.D. Thesis, PSU, 2010.

3] [Donald08] J. Donald and N.K. Jha, Reversible Logic Synthesis with Fredkin and Peres Gates, ACM Journal on Emerging Technologies in Computing Systems, Vol. 4, No. 1, Article 2, March 2008.

4] [Dueck03] G. W. Dueck and D. Maslov, "Reversible Function Synthesis with Minimum Garbage Outputs," 6th International Symposium on Representations and Methodology of Future Computing Technologies (RM), Trier, Germany, March 2003, pp. 154-161.

5] [Große06] D. Große, X. Chen, and R. Drechsler, Exact Toffoli network synthesis of reversible logic using boolean satisfiability, Proc. IEEE Dallas/CAS Workshop, pp. 51–54, 2006.

6] [Große09] D. Große, R. Wille, G.W. Dueck, and R. Drechsler. Exact multiple control toffoli network synthesis with SAT techniques. IEEE Trans. on CAD, 28(5):703–715, 2009.

7] [Gupta06] P. Gupta, A. Agrawal, and N. Jha. An algorithm for synthesis of reversible logic circuits. IEEE Trans. on CAD, 25(11):pp. 2317–2330, 2006.

8] [Hu06] J. Hu G-S Ma, G. Feng, Efficient Algorithm for Positive-polarity Reed-muller Expansions of reversible circuits, Proc. 18th Intern. Conf. on Microelectronics (ICM) 2006, pp. 63-66.

9] [Donald08] J. Donald and N. K. Jha, ``Reversible logic synthesis with Fredkin and Peres gates," ACM Journal of Emerging Technologies in Computing Systems, Vol.4, issue 1, Mar. 2008.

10] [Kerntopf04] P. Kerntopf, A new heuristic algorithm for reversible logic synthesis, Proc. DAC, pp. 834-837, June 2004.

11] [Khlopotine02] A. Khlopotine, M. Perkowski, and P. Kerntopf, Reversible logic synthesis by gate composition, Proc. IWLS 2002, pp. 261 – 266.

12] [Kumar07] M. Kumar, B. Year, N. Metzger, Y. Wang, and M. Perkowski, Realization of Incompletely Specified Functions in Minimized Reversible Circuits, Proc. RM 2007.

13] [Kumar08] M. Kumar, Realization of Incompletely Specified Reversible Functions MS. Thesis. PSU. 2008.

14] [Maslov03] D. Maslov and G. Dueck, Improved quantum cost for k-bit Toffoli gates, IEE Electron. Lett., vol. 39, no. 25, pp. 1790–1791, Dec. 2003.

15] [Maslov03a] D. Maslov and G. W. Dueck, Garbage in reversible design of multiple output functions, in Proc. 6th Int. Symp. Representations and Methodology of Future Computing Technologies, Mar. 2003, pp. 162–170.

16] [Maslov03b] D. Maslov, Reversible Logic Synthesis, PhD dissertation, 2003.

17] [Maslov04] D. Maslov and G.W. Dueck, Reversible cascades with minimal garbage, IEEE Transactions on CAD, 23(11): pp. 497-1509, November 2004.

18] [Maslov07] D. Maslov, G.W. Dueck, and D.M. Miller, Techniques for the Synthesis of Reversible Toffoli Networks, ACM Transactions on Design Automation of Electronic Systems, Vol. 12, No. 4, Article 42, Sept. 2007.

19] [Maslov08] D. Maslov, G.W. Dueck, D. M. Miller, and C. Negrevergne, Quantum Circuit Simplification and Level Compaction, IEEE Trans. on CAD, Vol. 27, No. 3, March 2008, pp 436-444.

20] [Maslov11] D. Maslov, Web Page:

21] [Miller03] D. M. Miller and G.W. Dueck, Spectral Techniques for Reversible Logic Synthesis, Proc. RM 2003, pp. 56-62.

22] [Miller03a] D. M. Miller, D. Maslov and G. W. Dueck, A Transformation Based Algorithm for Reversible Logic Synthesis, Proc. DAC, Anaheim, pp. 318–323, June 2003.

23] [Mishchenko01] A. Mishchenko and M. Perkowski, Fast Heuristic Minimization of Exclusive Sum-of-Products, Proc. Reed-Muller Workshop, 2001, Starkville, Mississippi, pp. 242-250.

24] [Mishchenko02] A. Mishchenko and M. Perkowski, “Logic Synthesis of Reversible Wave Cascades”, Proc. IEEE/ACM IWLS, June 4-7, 2002, pp. 197 – 202.

25] [Mohamadi08] M. Mohamadi, and M. Eshghi, Heuristic methods to use don’t cares in automated design of reversible and quantum logic circuits. Quantum Inf. Process. J. 7(4), pp. 175–192, 2008.

26] [Stedman05] Ch. Stedman, B. Yen and M. Perkowski, Synthesis of Reversible Circuits with Small Ancilla Bits for Large Irreversible Incompletely Specified Multi-Output Boolean Functions, Proc. 14th International Workshop on Post-Binary ULSI Systems, May 18, 2005, Calgary, Canada.

27] [Rice09] J. E. Rice K. B. Fazel, M.A. Thornton, and K. B. Kent Toffoli Gate Cascade Generation Using ESOP Minimization and QMDD-based Swapping. Proc. RM, May 23-24, 2009, pp. 63-72.

28] [Saedi07] M. Saeedi, M. Sedighi, M. S. Zamani, A Novel Synthesis Algorithm for Reversible Circuits, Proc. ICCAD, San Jose, California, pp. 65-68. 2007.

29] [Saedi07a] M. Saeedi, M. Sedighi, M. Saheb Zamani, A New Methodology for Quantum Circuit Synthesis: CNOT-Based Circuits as an Example,” Proc. IWLS, 2007. Paradise Point Resort and Spa, San Diego, CA, USA, May 30-June 1.

30] [Saedi07b] M. Saeedi, M. S. Zamani, M. Sedighi, On the Behavior of Substitution-Based Reversible Circuit Synthesis Algorithms: Investigation and Improvement,” Proc. ISVLSI, 9-11 March 2007, pp. 428-436.

31] [Wille08] R. Wille, D. Große, L. Teuber, G. W. Dueck, and R. Drechsler. RevLib: An online resource for reversible functions and reversible circuits. Proc. 38th ISMVL, pp. 220–225. Dallas, TX, USA, 2008. .

32] [Wille08a] R. Wille, R. Drechsler, BDD-based Synthesis of Reversible Logic for Large Functions. Proc. DAC, pp. 270-275. San Francisco, California

33] [Wille09] R. Wille, M. Saeedi, R. Drechsler, Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost. IWLS 2009.

|Function |MMDSN |MMD |MMDS |

# GatesQ-CostTime (ms)# GatesQ-CostTime (ms)# GatesQ-CostTime (ms)AHP-0181028.393201441.0741555 178,097 AHP-1016686.991292090.0221442 182,428 AHP-100221508.040251490.0181898 205,910 AHP-102211097.653281920.01919103 362,359 AHP-10419997.408281920.0201773 392,670 AHP-106211297.567241160.0161777 438,121 AHP-108201088.078211290.0151777 464,066 AHP-100016807.497191110.0141454 468,883 AHP-1002211137.513312230.0141878 526,966 AHP-1004201367.056231670.0291579 539,691 AHP-100617937.495241720.03017109 575,764 AHP-100819956.682312150.0241890 593,118 AHP-101018746.953302300.0281785 621,180 AHP-1012231317.146281680.0311870 626,634 AHP-1014231398.069271790.0311975 639,966 AHP-1016181266.748231670.0301579 646,605 AHP-1018171056.939251970.0301563 408,780 AHP-1020181067.317251931.8031696 284,467 AHP-1022191117.697241560.1531454 268,481 AHP-1024221386.622302180.1481676 253,849 AHP-102614667.252171130.1541466 229,625 AHP-102814867.343201480.1571381 222,084 AHP-1030211377.776271670.1241680 211,866 AHP-1032201086.726271870.1061793 214,853 AHP-1034191237.132221380.1021571 220,812 AHP-1036191077.257261860.0931781 206,786 AHP-1038181067.927181060.0831365 210,267 AHP-104016966.478221740.0781139 217,464 AHP-1042221467.263251730.0801999 204,661 AHP-1044191077.325231590.0961692 196,889 AHP-1046191077.739231470.0921571 210,829 AHP-104818946.484201200.0961789 201,351 AHP-1050231237.325342300.0831983 219,222 AHP-1052181107.557261660.0801684 241,366 AHP-105417817.226241640.0471676 215,861 AHP-105617937.757281960.8131567 228,621 AHP-1058181186.991231550.0151555 200,601 AHP-1060191518.110211610.0191583 252,009 AHP-1062191077.268312470.0201676 236,668 AHP-1064231317.357291890.0172084 237,049 AHP-1066181227.055312350.0171575 240,952 AHP-1068221348.60621970.0171999 272,891 AHP-1070181067.707221580.0181680 386,639 AHP-1072201127.611231590.0191672 313,911 AHP-1074221268.236261940.01718106 263,204 AHP-1076211218.644281840.0201874 264,143 AHP-1078211057.690302220.0211878 277,411 AHP-1080211457.879211090.0161793 289,429 AHP-1082211338.109292330.0161692 230,252 AHP-1084231198.797311870.01420104 263,490 AHP-1086201167.367271950.0141785 232,918 

-----------------------

| |Functio|MMD |MP |

| |n | | |

| | | | |

|# | | | |

|bit| | | |

|s | | | |

| | |Gates |Q-Cost |Time(ms|Gates |Q-Cost |Time(ms)|

| | | | |) | | | |

|4 |hwb4 |24 |154 |0.577 |19 | |339 |

|5 |hwb5 |62 |914 |0.033 |53 | |392 |

|6 |hwb6 |164 |4036 |0.075 |140 | |613 |

|7 |hwb7 |382 |13893 |0.247 |353 | |1503 |

|8 |hwb8 |883 |58605 |1.312 |837 | |987 |

|9 |hwb9 |2050 |,-AC`ae|4.171 |1993 | |4,170 |

| | | |uvwxy…½| | | | |

| | | |¾ | | | | |

| | | |, - | | | | |

| | | |úòæÝÖËÂ| | | | |

| | | |¹®ª£•„z| | | | |

| | | |si^S^G^| | | | |

| | | |?^hÊg-C| | | | |

| | | |JaJhtYç| | | | |

| | | |hwi5?CJ| | | | |

| | | |aJhtYçh| | | | |

| | | |tYçCJaJ| | | | |

| | | |htYçhwi| | | | |

| | | |CJaJh,$| | | | |

| | | |ÂhtYç5?| | | | |

| | | |CJ | | | | |

| | | |h,$Â5?C| | | | |

| | | |JhtYçhÙ| | | | |

| | | |“5?CJ | | | | |

| | | |188997 | | | | |

|10 |urf3 |3426 |538588 |12.595 |3334 | |58,306 |

|11 |urf4 |10527 |1412439|75.780 |10336 | |384,589 |

Table 2. Comparison of numbers of gates and quantum costs of MMD and MP algorithms for reversible functions with various numbers of bits. This is “large circuits” variant with k=5000. No ancilla bits.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download