Symmetry

Symmetry Groups for the Decomposition of Reversible Computers, Quantum Computers, and Computers in between

Alexis De Vos, Stijn De Baerdemacker

Published Jun 7, 2011• 16 citations

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 2w − 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 2w − 1 control gates.

DOI: 10.3390/sym3020305

Related papers

Creating subgroups of U(2w) for quantum-minus computers

Alexis De Vos, Michiel Boes

Classical reversible computers on w bits are isomorphic to the (finite) symmetric group S 2 w ; quantum computers on w qubits are isomorphic to the (Lie) unitary group U(2 w ). We investigate and classify groups X which represent computers intermediate between classical reversible computers and quantum computers. Such intermediate groups X may exist in three flavours: finite groups of order larger than (2 w )!, infinite but discrete groups, and Lie groups of dimension smaller than (2 w ). For our purpose, we start from 1-qubit transformations, represented by 2 × 2 unitary matrices. We call this group the creator. Its members are called gates and act on one qubit. Controlled gates are quantum circuits acting on w qubits, such that the 1-qubit transformation (applied to a particular qubit) depends on the state of the w − 1 other qubits. The controlled gates generate the group X of 2 w × 2 w matrices, called the creation. We discuss all creators of order up to 8. Additionally a creator of order 16 and one of order 192 are discussed.

Journal of Physics Conference SeriesMar 1, 20111 citation

Reversible computation, quantum computation and computer architectures in between

Alexis De Vos, Michiel Boes, Stijn De Baerdemacker

Thanks to the cosine-sine decomposition of unitary matrices, an arbitrary quantum circuit, acting on w qubits, can be decomposed into 2^w-1 elementary quantum gates, called controlled V gates. Thanks to the Birkhoff decomposition of doubly stochastic matrices, an arbitrary (classical) reversible circuit, acting on w bits, can be decomposed into 2w-1 elementary gates, called controlled NOT gates. The question arises under which conditions these two synthesis methods are applicable for intermediate cases, i.e. computers based on some group, which simultaneously is a subgroup of the unitary group U(2^w) and a supergroup of the symmetric group S_{2^w}. It turns out that many groups either belong to a class that might have a cosine-sine-like decomposition but no Birkhoff-like decomposition and a second class that might have both decompositions. For an arbitrary group, in order to find out to which class it belongs, it suffices to evaluate a function Phi(m), deduced either from its order (in case of a finite group) or from its dimension (in case of a Lie group). Here m=2^w is the degree of the group.

Reversible ComputationJan 1, 20101 citation

Matrix Calculus for Classical and Quantum Circuits

Alexis De Vos, Stijn De Baerdemacker

Quantum computation on w qubits is represented by the infinite unitary group U(2 w ); classical reversible computation on w bits is represented by the finite symmetric group S 2 w . In order to establish the relationship between classical reversible computing and quantum computing, we introduce two Lie subgroups XU( n ) and ZU( n ) of the unitary group U( n ). The former consists of all unitary n × n matrices with all line sums equal to 1; the latter consists of all unitary diagonal n × n matrices with first entry equal to 1. Such a group structure also reveals the relationship between matrix calculus and diagrammatic zx-calculus of quantum circuits.

ACM Journal on Emerging Technologies in Computing SystemsNov 18, 20147 citations

Reversible logic

Alexis De Vos

Reversible logic circuits are beneficial to both classical and quantum computer design. Present-day logic building-blocks (like OR gates and NAND gates) are logically irreversible and therefore cannot be used for designing reversible computers. Thus reversible computation needs an appropriate design methodology. In contrast to conventional digital logic circuits, reversible logic circuits (of a same logic width w) form a mathematical group. The reversible circuits of width w form a group isomorphic to the symmetric group S_{2^w}. Its Young subgroups allow systematic and efficient synthesis of an arbitrary reversible circuit. We can choose either a left coset, a right coset, or a double coset approach. The optimal design is reminiscent of the so-called banyan networks of telecommunication. As an illustration, three experimental prototypes (in c-MOS chip technology) of reversible computing devices are presented. Special care has been taken to avoid as much as possible the appearance of garbage bits. The examples illustrate how, in a near future, reversible computers will outperform conventional computers, in terms of power dissipation and heat generation.

Jan 1, 20090 citations

On two subgroups of U(n), useful for quantum computing

Alexis De Vos, Stijn De Baerdemacker

As two basic building blocks for any quantum circuit, we consider the 1-qubit PHASOR circuit ϕ( θ ) and the 1-qubit NEGATOR circuit N ( θ ). Both are roots of the IDENTITY circuit. Indeed: both ϕ(0) and N (0) equal the 2 × 2 unit matrix. Additionally, the NEGATOR is a root of the classical NOT gate. Quantum circuits (acting on w qubits) consisting of controlled PHASORs are represented by matrices from ZU(2 w ); quantum circuits consisting of controlled NEGATORs are represented by matrices from XU(2 w ). Here, ZU( n ) and XU( n ) are subgroups of the unitary group U( n ): the group XU( n ) consists of all n × n unitary matrices with all 2 n line sums (i.e. all n row sums and all n column sums) equal to 1 and the group ZU( n ) consists of all n × n unitary diagonal matrices with first entry equal to 1. Any U( n ) matrix can be decomposed into four parts: U = exp( iα ) Z 1 XZ 2 , where both Z 1 and Z 2 are ZU( n ) matrices and X is an XU( n ) matrix. We give an algorithm to find the decomposition. For n = 2 w it leads to a four-block synthesis of an arbitrary quantum computer.

Journal of Physics Conference SeriesApr 13, 20159 citations

The synthesis of a quantum circuit

Alexis De Vos, Stijn De Baerdemacker

As two basic building blocks for any quantum circuit, we consider the 1-qubit NEGATOR(θ) circuit and the 1-qubit PHASOR(θ) circuit, extensions of the NOT gate and PHASE gate, respectively: NEGATOR(π) = NOT and PHASOR(π) = PHASE.Quantum circuits (acting on w qubits) consisting of controlled NEGATORs are represented by matrices from XU(2 w ); quantum circuits (acting on w qubits) consisting of controlled PHASORs are represented by matrices from ZU(2 w ).Here, XU(n) and ZU(n) are subgroups of the unitary group U(n): the group XU(n) consists of all n × n unitary matrices with all line sums equal to 1 and the group ZU(n) consists of all n × n unitary diagonal matrices with first entry equal to 1.We conjecture that any U(n) matrix can be decomposed into four parts: U = e iα Z1XZ2, where both Z1 and Z2 are ZU(n) matrices and X is an XU(n) matrix.For n = 2 w , this leads to a decomposition of a quantum computer into simpler blocks.

Cambridge University Press eBooksJan 1, 20144 citations