Toffoli gate implementation using the billiard ball model

Hadi Hosseini; Gerhard W. Dueck

doi:10.1109/ISMVL.2010.40

Toffoli gate implementation using the billiard ball model

Hadi Hosseini, Gerhard W. Dueck

College of Information Sciences and Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Scopus citations

Abstract

In this paper we review the Billiard Ball Model (BBM) introduced by Toffoli and Fredkin. The analysis of a previous approach to design reversible networks based on BBM it shown to ignored physical realities. We prove that some logic function cannot be realized without additional control balls. For example, to realize the logical OR operation, at least three control balls are needed. We show how reversible Toffoli gates can be constructed with this model. Finally, a Toffoli gate module is proposed that can be used in a cascade of gates and thus implement arbitrary reversible functions.

Original language	English (US)
Title of host publication	ISMVL 2010 - 40th IEEE International Symposium on Multiple-Valued Logic
Pages	173-178
Number of pages	6
DOIs	https://doi.org/10.1109/ISMVL.2010.40
State	Published - 2010
Event	40th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2010 - Barcelona, Spain Duration: May 26 2010 → May 28 2010

Publication series

Name	Proceedings of The International Symposium on Multiple-Valued Logic
ISSN (Print)	0195-623X

Conference

Conference	40th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2010
Country/Territory	Spain
City	Barcelona
Period	5/26/10 → 5/28/10

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Access to Document

10.1109/ISMVL.2010.40

Cite this

@inproceedings{6bca63f087194e069eab8726aa9ee187,

title = "Toffoli gate implementation using the billiard ball model",

abstract = "In this paper we review the Billiard Ball Model (BBM) introduced by Toffoli and Fredkin. The analysis of a previous approach to design reversible networks based on BBM it shown to ignored physical realities. We prove that some logic function cannot be realized without additional control balls. For example, to realize the logical OR operation, at least three control balls are needed. We show how reversible Toffoli gates can be constructed with this model. Finally, a Toffoli gate module is proposed that can be used in a cascade of gates and thus implement arbitrary reversible functions.",

author = "Hadi Hosseini and Dueck, {Gerhard W.}",

year = "2010",

doi = "10.1109/ISMVL.2010.40",

language = "English (US)",

isbn = "9780769540245",

series = "Proceedings of The International Symposium on Multiple-Valued Logic",

pages = "173--178",

booktitle = "ISMVL 2010 - 40th IEEE International Symposium on Multiple-Valued Logic",

}

Hosseini, H & Dueck, GW 2010, Toffoli gate implementation using the billiard ball model. in ISMVL 2010 - 40th IEEE International Symposium on Multiple-Valued Logic., 5489120, Proceedings of The International Symposium on Multiple-Valued Logic, pp. 173-178, 40th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2010, Barcelona, Spain, 5/26/10. https://doi.org/10.1109/ISMVL.2010.40

TY - GEN

T1 - Toffoli gate implementation using the billiard ball model

AU - Hosseini, Hadi

AU - Dueck, Gerhard W.

PY - 2010

Y1 - 2010

N2 - In this paper we review the Billiard Ball Model (BBM) introduced by Toffoli and Fredkin. The analysis of a previous approach to design reversible networks based on BBM it shown to ignored physical realities. We prove that some logic function cannot be realized without additional control balls. For example, to realize the logical OR operation, at least three control balls are needed. We show how reversible Toffoli gates can be constructed with this model. Finally, a Toffoli gate module is proposed that can be used in a cascade of gates and thus implement arbitrary reversible functions.

AB - In this paper we review the Billiard Ball Model (BBM) introduced by Toffoli and Fredkin. The analysis of a previous approach to design reversible networks based on BBM it shown to ignored physical realities. We prove that some logic function cannot be realized without additional control balls. For example, to realize the logical OR operation, at least three control balls are needed. We show how reversible Toffoli gates can be constructed with this model. Finally, a Toffoli gate module is proposed that can be used in a cascade of gates and thus implement arbitrary reversible functions.

UR - http://www.scopus.com/inward/record.url?scp=77955322039&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955322039&partnerID=8YFLogxK

U2 - 10.1109/ISMVL.2010.40

DO - 10.1109/ISMVL.2010.40

M3 - Conference contribution

AN - SCOPUS:77955322039

SN - 9780769540245

T3 - Proceedings of The International Symposium on Multiple-Valued Logic

SP - 173

EP - 178

BT - ISMVL 2010 - 40th IEEE International Symposium on Multiple-Valued Logic

T2 - 40th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2010

Y2 - 26 May 2010 through 28 May 2010

ER -

Toffoli gate implementation using the billiard ball model

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this