A complete set of transformation rules for reversible circuits

• URL: http://arxiv.org/abs/2508.17273v1
• Date: Sun, 24 Aug 2025 09:45:14 GMT
• Title: A complete set of transformation rules for reversible circuits
• Abstract summary: We propose the first complete set of transformation rules for reversible circuits.<n>We show that every reversible function is computed by a unique reversible circuit in the canonical form.
• Score: 4.640835690336652
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reversible logic synthesis is a crucial component in quantum electronic design automation. While rule-based methodologies have gained prominence in reversible circuit optimization, the completeness of the transformation rule systems is a longstanding problem in this domain. In this work, we propose the first complete set of transformation rules for reversible circuits, comprising five fundamental rules: any two equivalent reversible circuits can be transformed into each other using the rules. To prove the completeness, a canonical circuit representation for reversible functions is introduced, and we show that every reversible function is computed by a unique reversible circuit in the canonical form, and any reversible circuit can be transformed into its canonical form by applying the rules.

Related papers

• Polycontrolled PROPs for Qudit Circuits: A Uniform Complete Equational Theory For Arbitrary Finite Dimension [0.0]
  We present a finite schematic axiomatisation of quantum circuits over d-level systems (qudits)<n>For each d we define a PROP equipped with a family of control functors, treating control as a primitive categorical constructor.
  arXiv  Detail & Related papers  (2026-02-10T15:16:46Z)
• An order-theoretic circuit syntax and characterisation of the concept lattice [0.0]
  We take an order-theoretic approach to circuit (string diagram) syntax, treating a circuit as a partial order with additional input-output structure.<n>We define morphisms between circuits and prove a factorisation theorem showing that these can, in the finite case, be regarded as formalising a notion of syntactical circuit rewrites.
  arXiv  Detail & Related papers  (2025-07-07T19:18:37Z)
• Generalized Linear Mode Connectivity for Transformers [87.32299363530996]
  A striking phenomenon is linear mode connectivity (LMC), where independently trained models can be connected by low- or zero-loss paths.<n>Prior work has predominantly focused on neuron re-ordering through permutations, but such approaches are limited in scope.<n>We introduce a unified framework that captures four symmetry classes: permutations, semi-permutations, transformations, and general invertible maps.<n>This generalization enables, for the first time, the discovery of low- and zero-barrier linear paths between independently trained Vision Transformers and GPT-2 models.
  arXiv  Detail & Related papers  (2025-06-28T01:46:36Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Normalizing Resistor Networks [0.0]
  This paper describes a rewriting system for resistor circuits over any positive division rig. We show how these transformations can be organized into a confluent and terminating rewriting system on the category of resistor circuits.
  arXiv  Detail & Related papers  (2023-03-20T01:23:18Z)
• Efficient estimation of trainability for variational quantum circuits [43.028111013960206]
  We find an efficient method to compute the cost function and its variance for a wide class of variational quantum circuits. This method can be used to certify trainability for variational quantum circuits and explore design strategies that can overcome the barren plateau problem.
  arXiv  Detail & Related papers  (2023-02-09T14:05:18Z)
• A Complete Equational Theory for Quantum Circuits [58.720142291102135]
  We introduce the first complete equational theory for quantum circuits. Two circuits represent the same unitary map if and only if they can be transformed one into the other using the equations.
  arXiv  Detail & Related papers  (2022-06-21T17:56:31Z)
• LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits [58.720142291102135]
  We introduce the LOv-calculus, a graphical language for reasoning about linear optical quantum circuits. Two LOv-circuits represent the same quantum process if and only if one can be transformed into the other with the rules of the LOv-calculus.
  arXiv  Detail & Related papers  (2022-04-25T16:59:26Z)
• Quantum simulation of $\phi^4$ theories in qudit systems [53.122045119395594]
  We discuss the implementation of quantum algorithms for lattice $Phi4$ theory on circuit quantum electrodynamics (cQED) system. The main advantage of qudit systems is that its multi-level characteristic allows the field interaction to be implemented only with diagonal single-qudit gates.
  arXiv  Detail & Related papers  (2021-08-30T16:30:33Z)
• Hardware-Encoding Grid States in a Non-Reciprocal Superconducting Circuit [62.997667081978825]
  We present a circuit design composed of a non-reciprocal device and Josephson junctions whose ground space is doubly degenerate and the ground states are approximate codewords of the Gottesman-Kitaev-Preskill (GKP) code. We find that the circuit is naturally protected against the common noise channels in superconducting circuits, such as charge and flux noise, implying that it can be used for passive quantum error correction.
  arXiv  Detail & Related papers  (2020-02-18T16:45:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.