Back to the ELIS department. Back to the ELIS Research Groups .

**NEWS FLASH: BRAND NEW BOOK**

In August 2018, publisher Morgan & Claypool published a brand new book:

"Synthesis of quantum circuits versus synthesis of classical reversible circuits"

by Alexis De Vos, Stijn De Baerdemacker, and Yvan Van Rentergem:

**NEWS FLASH: RC 2020 CONFERENCE**

After the successful
international workshops/conferences on reversible computation, i.e.

RC2009,
on 22 March 2009, in York,

RC2010,
on 2-3 July 2010, in Bremen,

RC2011,
on 4-5 July 2011, in Gent

RC2012,
on 2-3 July 2012, in København,

RC2013,
on 4-5 July 2013, in Victoria,

RC2014,
on 10-11 July 2014, in Kyoto,

RC2015,
on 16-17 July 2015, in Grenoble,

RC2016,
on 7-8 July 2016, in Bologna,

RC2017,
on 6-7 July 2017, in Kolkata,

RC2018,
on 12-14 September 2018, in Leicester, and

RC2019,
on 24-25 June 2019, in Lausanne,

the twelfth event, i.e. RC2020,
will take place in Oslo, on 9-10 July 2020.

Reversible computers are computers that can calculate both forwards and backwards:

They are based on reversible logic operations. For an introduction: see the two text books above. One can also read an early book on the subject: Addison Wesley (1996) published `Feynman lectures on computation', containing an excellent tutorial introduction to the subject.

At the Universiteit Gent we design, fabricate and test basic building blocks for such computers. They are based on the theoretical work by the Fredkin--Toffoli group of Massachusetts Institute of Technology. The design and fabrication happens in close collaboration with the Invomec division of Imec v.z.w. in Leuven.

We use standard c-MOS technology, but full-custom design. The processing of the chips happens within the Europractice consortium. Here is a reversible logic gate with three logic inputs and three logic outputs, seen through an optical microscope:

A scanning electron microscope gives more depth and perspective :

The circuit consists of 24 transistors (twelve n-MOS and twelve p-MOS), arranged on the edges of two hexagons. Particular is the fact that the circuit works without help of any power suppies (no V_dd nor V_ss nor ground busbars). All energy provided to the output pins, comes from the input pins.

More complex circuits, containing e.g. six such building blocks, have been realised successfully. Here is one of them: because it contains exactly 144 transistors, we call it our `gross' circuit:

The following four-bit ripple adder makes use of sixteen building blocks and thus contains 384 transistors :

Many different 4-bit reversible adders have been designed. The second ripple adder uses Feynman's three building blocks: the NOT, the CONTROLLED NOT, and the CONTROLLED CONTROLLED NOT. It needs only 192 transistors, but performs equally well. The carry-look-ahead adder needs more transistors (i.e. 320), but is faster. It uses a generalization of the Feynman gates, i.e. the so-called control gates. Here it is:

In a control gate, one bit is inverted, on condition that some boolean function of some other bits equals one. Besides such controlled NOT gates, a.k.a. Toffoli gates, we also use controlled SWAP gates, a.k.a. Fredkin gates.

Here is an ambitious project: this chip contains 2,504 transistors. It reversibly multiplies an arbitrary 8-bit number with the number sqrt(2)/2.

It contains four adders and four subtracters. The adders (and subtracters) are of the ingeneous reversible type called the Cuccaro addition circuit (2005). Here is one of the four 8-bit Cuccaro adders (140 micrometer * 230 micrometer):

These reversible c-MOS techniques, we call reversible MOS or `r-MOS'. They are particularly suited for so-called adiabatic switching. Here is an experimental oscilloscope picture, showing an adiabatic input signal A_0 and a resulting output signal C_4 of an adder circuit.

Unfortunately signal C_4 does not follow signal A_0 well in the range +/- 1 volt. This is caused by the threshold voltages of the transistors (about 0.8 volts here). Nevertheless, adiabatic adressing can save one order of magnitude in the power dissipation.

For more information on reversible computing techniques:

- At the Københavns Universitet, there is prof. Robert Glueck with his reversible programming languages.
- At the Universität Bremen, there is dr. Robert Wille with emphesis on the full design flow of reversible logic (i.e. synthesis, optimization, verification, and debugging).

Research staff involved in Gent consists of:

Former research staff involved consists of:

- dr. ir. Bart Desoete (1 Sep 1997 - 28 Feb 2002), now engineer at the factory QinetiQ, designing space ships,
- prof. dr. ir. Filip Beunis (1 Oct 2002 - 31 Dec 2002), now professor on liquid crystals at the Universiteit Gent,
- dr. ir. Yvan Van Rentergem (1 Jan 2004 - 31 March 2008), now modelling engineer at Arcelor-Mittal steel factory, and
- dr. ir. Stéphane Burignat (16 Nov 2009 - 15 Aug 2013).

The project has been sponsored by the special research fund Bijzonder Onderzoeksfonds under the following grants:

- " Adiabatische aansturing van reversibele computerchips " (1 Jan 1998 - 31 Dec 1999)
- " Reversibele digitale schakelingen met ultra-lage warmte-dissipatie " (1 Jan 2000 - 31 Dec 2001)
- " Optimaal ontwerp van reversibele digitale schakelingen " (1 Jan 2004 - 31 Dec 2007),

- " Realistische evaluatie van zeer laag energieverbruik reversibele geintegreerde circuits " (1 Jan 2012 - 31 Dec 2012),

- " MicroPower " (1 Jan 2009 - 31 Dec 2013),

- the COST Action IC 1405
" Reversible computation - extending horizons of computing " (30 Apr 2015 - 29 Apr 2019),

a research network of 21 European countries.

Dr. Burignat (Gent) and Dr. Thomsen (København)
are measuring the cascade of a do and an undo chip,
thus illustrating the reversibility of the circuit.

MAIN REFERENCES :

Reference # 1 : a beautiful circuit

B. Desoete and A. De Vos published a paper entitled
`` A reversible carry-look-ahead adder using control gates '', in
Integration, the V.L.S.I. Journal,
volume 33 (2002) pp. 89-104.

Reference # 2 : a beautiful theorem from group theory

A. De Vos and L. Storme published a paper entitled
`` r-Universal reversible logic gates '', in
Journal of Physics A: Mathematical and General,
volume 37 (2004) pp. 5815 - 5824.

Reference # 3 : an (almost) optimal synthesis method

A. De Vos and Y. Van Rentergem published an almost optimal synthesis method
for an arbitrary reversible circuit, based on dual Young subgroups and the Birkhoff theorem
on doubly stochastic matrices :
`` Young subgroups for reversible computers '', in the journal
Advances in Mathematics of Communications,
volume 2 (2008), pp. 183 - 200.

Reference # 4 : a survey on chip performance

S. Burignat and A. De Vos published
`` A review on the performance of reversible ripple-adders '', in the
International Journal of Electronics and Telecommunications,
volume 58 (2012), pp. 205 - 212.

Reference # 5 : a first step towards quantum computing

A. De Vos, J. De Beule and L. Storme published a paper on the quantum gate known as
the square root of NOT:
`` Computing with the square root of NOT '', in the
Serdica Journal of Computing,
volume 3 (2009), pp. 359 - 370.

Reference # 6 : a large step into the quantum world

A. De Vos and S. De Baerdemacker have published a paper on the quantum gate known as
the NEGATOR:
`` The NEGATOR as a basic building block in quantum circuits '', in the journal
Open Systems and Information Dynamics,
volume 20 (2013), p. 1350004.

Reference # 7 : a challenging conjecture

In January 2014, A. De Vos and S. De Baerdemacker have put forward a conjecture about unitary matrices:
`` Scaling a unitary matrix '', in the
arXiv,
published in the journal
Open Systems and Information Dynamics,
volume 21 (2014), p. 1450013.
In August 2014, the conjecture was proved by Idel and Wolf, in the
arXiv.

Reference # 8 : a quantum synthesis method

A. De Vos and S. De Baerdemacker have published a
paper,
on quantum computers:
`` Block-ZXZ synthesis of an arbitrary quantum circuit '', in the journal
Physical Review A,
volume 94 (2016), p. 052317.

Reference # 9 : a mathematical theorem

S. De Baerdemacker, A. De Vos, L. Chen, and L. Yu have published
a first paper,
a second paper, and
a third paper,
on a unitary version of Birkhoff's theorem, in the journal
Linear Algebra and its Applications,
volume 493 (2016), pp. 455 - 468,
volume 514 (2017), pp. 151 - 164, and
volume 578 (2019), pp. 27 - 52.

**AND PLEASE READ THIS ONE :**

In its March-April 2006 issue (pp. 107-111), the journal American Scientist

has published a review paper entitled `Reverse engineering',

with a photograph of one of our circuits !

**AND PLEASE READ THE TEXTBOOKS :**

Wiley-VCH, Springer Verlag, and Morgan & Claypool have published

the following textbooks on reversible computing:

`Reversible computing' (251 pages),

`Towards a design flow for reversible logic' (184 pages), and

`Synthesis of quantum circuits versus synthesis of classical reversible circuits' (125 pages):

**AND, FINALLY, PLEASE VIEW THE MOVIE :**

Since February 2014, an 8-minutes movie about
the bilateral research project MicroPower (see below) is available in three versions (each 552 MegaBytes):

a version without subtitles (partly in English and partly in Dutch),

a version with English subtitles, and

a version with Danish subtitles.

The movie was produced in a collaboration between
Københavns Universitet, the Universiteit Gent, and the company fisheye.

This page

http://www.elis.UGent.be/~aldevos/projects/computer.html

is maintained by
Alexis De Vos.

Last maintenance on 08 July 2019.