you are in... Main\news
July 8, 2021: moving to a new home.
The Reversible Logic Synthesis Benchmarks
Page is moving to a new host, https://github.com/.
It is envisioned that the Page will be
revised soon, as it is due for a major overhaul. For example, the costs of the multiply
controlled gates used in the project are no more accurate, as better
constructions have been reported since the costs were introduced on this
project. This calls for a recalculation
of (almost) all quantum costs reported.
Secondly, not all circuits reported accurately reflect the best
known. Specifically, better
implementations of RD (input weight) and HWB (Hidden Weighted Bit) circuits are
known in the literature but not yet reflected on this page. Thirdly, the understanding that the
reversible circuits are of value as parts of quantum computations has
crystallized, and quantum computations impose certain restrictions. These restrictions call for clarification and
revision of the specification of some functions.
January 8, 2018: new circuits added.
Xiaoxiao Wang from Xi'an Shiyou
University, China, emailed three new improved circuit implementations (hwb5, mod5adder, nth_prime6).
Also added are two new functions and circuits for GF field multiplier of
binary sizes 131 and 163, corresponding, as of today, to unsolved
Certicom challenges of Levels I and II.
March 3, 2017: new circuits added.
Mustapha Yusuf Abubakar
from Universiti Teknologi
PETRONAS Malaysia emailed two new implementations (hwb5,
nth_prime5).
February 9, 2017: new circuit added.
Martin Roetteler
from Microsoft Research--Redmond emailed an optimized implementation of the permenent3x3 benchmark function.
August 31, 2015: new circuits added.
Dmitry Zakablukov
of Bauman Moscow State Technical University contributed circuits for the
permanent benchmark function family.
August 18/19, 2015: new circuits added.
Several more circuits by Dmitry Zakablukov of Bauman Moscow State Technical University have
been added. This includes circuits for
hwb7 through hwb12, and nth_prime with 7 through 11
inputs.
August 10, 2015: several new circuits added.
Several new circuits by Dmitry Zakablukov of Bauman Moscow State Technical University have
been added.
September 2, 2011: two new circuits added.
New smaller circuits for benchmark functions hwb5 and nth_prime5_inc have been added. These circuits were provided by Marek Szyprowski and Pawel Kerntopf from Warsaw University of Technology, Warsaw, Poland.
Circuit pictograms were generated with the use of a test version of the QCViewer, a software package being developed by the Quantum Circuits group at the Institute for Quantum Computing, University of Waterloo. Qualitative improvement comes from the use of vector graphics.
January 28, February 8, and February 16, 2011: fourteen new circuits added.
New smaller circuits for benchmark functions 4_49, 4b15g_1, 4b15g_2, 4b15g_3, 4b15g_4, 4b15g_5, hwb4, and nth_prime4_inc have been added. These circuits were provided by Marek Szyprowski and Pawel Kerntopf from Warsaw University of Technology, Warsaw, Poland.
January 11, 2011: maximal size optimal 4-bit circuits added.
This update includes the addition of all (up to equivalence with respect to the input/output relabeling and inversion) 4-bit functions requiring the maximal possible number of NOT, CNOT, Toffoli, and Toffoli-4 gates in their optimal implementation, 4b15g_1, 4b15g_2, 4b15g_3, 4b15g_4, and 4b15g_5.
July 8, 2010: costs of circuits with Fredkin gates corrected.
This revision corrects calculation of quantum costs in the circuits with Fredkin gates. Thanks to Jeevan Jyoti Mani Tripathi and Mehdi Saeedi for pointing out this error, and assisting in correcting it.
July 2, 2010: GF multiplier circuits added.
This revision includes the addition of GF field multiplier circuits for a variety of parameters. A few larger circuits were added on July 6, 2010.
June 28, 2010: a number of circuits added; announcing RCViewer+.
This update includes the addition of a number if circuits for hwb and nth_primeK_inc benchmark functions. These circuits have been provided by Mehdi Saeedi; the synthesis algorithm used is discussed in this paper.
A new version of the RCViewer, the RCViewer+ is now available. The new RCViewer+ corrects an error in RCViewer's calculation of the quantum cost of circuits with Fredkin gates. Moreover, in comparison to the RCViewer, it has new features, including:
- support of multiple control Toffoli and Fredkin gates with both positive and negative controls;
- ability to display Hadamard, controlled-V, and controlled-V+ gates (a particular type of the square root of CNOT);
- ability to displayed levelled/parallelized circuit.
The group who wrote RCViewer+ intends to further improve this circuit viewer/analyzer in the near future. Suggestions are welcome.
April 21, 2010: a few optimal 4-bit circuits added.
This minor update includes the addition of a few 4-bit circuits with a provably minimal number of gates. Consequently, every 4-bit circuit with a minimal number of gates posted on this web page is now proved optimal.
Secondly, thanks to Jeevan Jyoti Mani Tripathi from Gorakhpur University, India, for pointing out an error in the way RCViewer calculates quantum cost of the circuits involving SWAP/Fredkin gates. This error has not been fixed yet.
October 29, 2009 - November 17, 2009: more functions and circuits added.
This update includes the following major changes:
1. Addition of the polynomial size circuits for hwb type functions with up to 1000 inputs, and a few larger (hwb12, hwb13, hwb14) function specifications.
2. Introduction of the new nth_prime and permanent benchmark functions.
This addresses two issues, raised verbally by the community: to include large circuits (1.), and to have complex/hard function specifications (2.). With the next revision, I am hoping to add practical circuits, i.e., those constituting a part of or of interest in quantum algorithms.
February 20, 2008: more circuits added.
8-bit adder circuit has been added. Thanks to Y. Takahashi from NTT Communications Science Laboratory, Japan.
October 3, 2007: more circuits added.
Added includes improved designs for 2of5 and mod5 functions, thanks to A. Younes from the Department of Mathematics and Computer Science at Alexandria University, Egypt.
November 15, 2005: more circuits added.
We added some new circuits for most of the benchmark functions available through this web page. The new designs often provide significant improvement over the best available previously. These new circuits were synthesized by an automated synthesis procedure discussed in this paper (work in preparation).
November 9, 2005: one more function added.
Vishal Gupta from the Department of Computer Science & Engineering at Indian Institute of Technology (IIT), Madras, India suggested a function and its reversible design. Click here for more details.
February 20, 2005: more circuits added.
We added circuits for the hwb benchmark functions with parameters 8, 9, 10, and 11 synthesized by a method being currently developed. The other set of circuits added this time is for the Gray code type functions.
January 7, 2005: updated quantum cost calculation.
The update is based on the new results for the quantum cost calculation of the large Toffoli gates. Updated are the table with quantum cost calculation (the old table is still available here) together with the quantum costs of the affected circuits. For those circuits whose quantum cost changed (which includes some/all implementations of cycle10_2, cycle17_3, ham15, hwb7, mod1024adder, mod1048576adder, rd53), the old quantum cost is now shown in small font in brackets as "(old: xxx)". Eventually, the old quantum costs and the old quantum cost calculation table will be deleted, leaving the new cost calculation only.
Finally, the RCViewer circuit viewer was updated as to accommodate the new quantum cost calculation. The new software, version 1.14, is available in .exe and .zip formats. In comparison with the previous versions, this version also features ability to change controls of the gates in a viewed circuit by clicking them.