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

arXiv:1502.00819

From reversible computation to quantum computation by Lagrange interpolation

Alexis De Vos, Stijn De Baerdemacker

Published Feb 3, 2015• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1502.00819

Related papers

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

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

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, 2009•0 citations

From group theory to reversible computers

Alexis De Vos, Yvan Van Rentergem

Reversible logic circuits of certain logic width form a group, isomorphic to a symmetric group. Its Young Subgroups allow systematic synthesis of an arbitrary reversible circuit. We can choose either a left coset, right coset, or double coset approach. The tools are beneficial to both classical and quantum computers.

International journal of unconventional computing•Jan 1, 2006•11 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

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 Series•Mar 1, 2011•1 citation
Classical reversible circuits, acting on wwwbits, 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 lengthppp, 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 pppmatrices of the cycle, we step from a finite cyclic group of orderppp 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.
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.
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.
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.
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.