Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Physics Conference Series

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

Alexis De Vos, Michiel Boes

Published Mar 1, 2011• 1 citation
Publisher

Abstract

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.

DOI
10.1088/1742-6596/284/1/012021

Related papers

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

Alexis De Vos, Stijn De Baerdemacker

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.

Symmetry•Jun 7, 2011•16 citations

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 Computation•Jan 1, 2010•1 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 Systems•Nov 18, 2014•7 citations

From reversible computation to quantum computation by Lagrange interpolation

Alexis De Vos, Stijn De Baerdemacker

Classical reversible circuits, acting on $w$~bits, are represented by permutation matrices of size $2^w \times 2^w$. Those matrices form the group P($2^w$), isomorphic to the symmetric group {\bf S}$_{2^w}$. The permutation group P($n$), isomorphic to {\bf S}$_n$, contains cycles with length~$p$, ranging from~1 to $L(n)$, where $L(n)$ is the so-called Landau function. By Lagrange interpolation between the $p$~matrices of the cycle, we step from a finite cyclic group of order~$p$ to a 1-dimensional Lie group, subgroup of the unitary group U($n$). As U($2^w$) is the group of all possible quantum circuits, acting on $w$~qubits, such interpolation is a natural way to step from classical computation to quantum computation.

arXiv:1502.00819•Feb 3, 2015•2 citations

Almost-classical quantum computers

Michiel Boes, Alexis De Vos, Jan De Beule

By means of a subgroup of the 2 X 2 unitary matrices, i.e. a subgroup Q of U(2), acting on a single qubit, we create a group X, acting on w qubits. If Q equals the group of order 2 consisting of the follower and the inverter, we recover S_{2^w}, i.e. the permutation matrices describing a classical reversible computer acting on w bits. If Q is another group of two 2 X 2 matrices, then a new kind of computing appears.

•Jan 1, 2010•1 citation

The Roots of the NOT Gate

Alexis De Vos, Stijn De Baerdemacker

The quantum gates called 'k th root of NOT' and 'controlled k th root of NOT' can be applied to synthesize circuits, both classical reversible circuits and quantum circuits. Such circuits, acting on w qubits, fill a (2w-1)2-dimensional subspace of the (2w)2-dimensional space U(2w) of the 2w× 2wunitary matrices and thus describe computers situated between classical reversible computers and full quantum computers.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2012•5 citations
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.
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.
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.
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.
Classical reversible circuits, acting on www~bits, are represented by permutation matrices of size 2w×2w2^w \times 2^w2w×2w. Those matrices form the group P(2w2^w2w), isomorphic to the symmetric group {\bf S}2w_{2^w}2w​. The permutation group P(nnn), isomorphic to {\bf S}n_nn​, contains cycles with length~ppp, ranging from~1 to L(n)L(n)L(n), where L(n)L(n)L(n) is the so-called Landau function. By Lagrange interpolation between the ppp~matrices of the cycle, we step from a finite cyclic group of order~ppp to a 1-dimensional Lie group, subgroup of the unitary group U(nnn). As U(2w2^w2w) is the group of all possible quantum circuits, acting on www~qubits, such interpolation is a natural way to step from classical computation to quantum computation.