Ghent University Academic Bibliography

Advanced

Symmetry groups for the decomposition of reversible computers, quantum computers, and computers in between

Alexis De Vos UGent and Stijn De Baerdemacker UGent (2011) SYMMETRY-BASEL. 3(2). p.305-324
abstract
Whereas quantum computing circuits follow the symmetries of the unitary Lie group, classical reversible computation circuits follow the symmetries of a finite group, i.e. the symmetric group. We confront the decomposition of an arbitrary classical reversible circuit with w bits and the decomposition of an arbitrary quantum circuit with w qubits. Both decompositions use the control gate as building block, i.e. a circuit transforming only one (qu)bit, the transformation being controlled by the other w-1 (qu)bits. We explain why the former circuit can be decomposed into 2w-1 control gates, whereas the latter circuit needs 2^w-1 control gates. We investigate whether computer circuits, not based on the full unitary group but instead on a subgroup of the unitary group, may be decomposable either into 2w-1 or into 2^w-1 control gates.
Please use this url to cite or link to this publication:
author
organization
year
type
journalArticle (original)
publication status
published
subject
keyword
reversible computing, group theory, quantum computing
journal title
SYMMETRY-BASEL
Symmetry-Basel
volume
3
issue
2
issue title
Symmetry in theoretical computer science
pages
305 - 324
Web of Science type
Article
Web of Science id
000208832200011
ISSN
2073-8994
DOI
10.3390/sym3020305
language
English
UGent publication?
yes
classification
A1
copyright statement
I have retained and own the full copyright for this publication
id
1258500
handle
http://hdl.handle.net/1854/LU-1258500
date created
2011-06-09 10:25:40
date last changed
2014-11-27 13:07:31
@article{1258500,
  abstract     = {Whereas quantum computing circuits follow the symmetries of the unitary Lie group, classical reversible computation circuits follow the symmetries of a finite group, i.e. the symmetric group. We confront the decomposition of an arbitrary classical reversible circuit with w bits and the decomposition of an arbitrary quantum circuit with w qubits. Both decompositions use the control gate as building block, i.e. a circuit transforming only one (qu)bit, the transformation being controlled by the other w-1 (qu)bits. We explain why the former circuit can be decomposed into 2w-1 control gates, whereas the latter circuit needs 2\^{ }w-1 control gates. We investigate whether computer circuits, not based on the full unitary group but instead on a subgroup of the unitary group, may be decomposable either into 2w-1 or into 2\^{ }w-1 control gates.},
  author       = {De Vos, Alexis and De Baerdemacker, Stijn},
  issn         = {2073-8994},
  journal      = {SYMMETRY-BASEL},
  keyword      = {reversible computing,group theory,quantum computing},
  language     = {eng},
  number       = {2},
  pages        = {305--324},
  title        = {Symmetry groups for the decomposition of reversible computers, quantum computers, and computers in between},
  url          = {http://dx.doi.org/10.3390/sym3020305},
  volume       = {3},
  year         = {2011},
}

Chicago
De Vos, Alexis, and Stijn De Baerdemacker. 2011. “Symmetry Groups for the Decomposition of Reversible Computers, Quantum Computers, and Computers in Between.” Symmetry-basel 3 (2): 305–324.
APA
De Vos, Alexis, & De Baerdemacker, S. (2011). Symmetry groups for the decomposition of reversible computers, quantum computers, and computers in between. SYMMETRY-BASEL, 3(2), 305–324.
Vancouver
1.
De Vos A, De Baerdemacker S. Symmetry groups for the decomposition of reversible computers, quantum computers, and computers in between. SYMMETRY-BASEL. 2011;3(2):305–24.
MLA
De Vos, Alexis, and Stijn De Baerdemacker. “Symmetry Groups for the Decomposition of Reversible Computers, Quantum Computers, and Computers in Between.” SYMMETRY-BASEL 3.2 (2011): 305–324. Print.