A study on CNOT−based quantum circuits using rewriting systems

We show how representations of finite-dimensional quantum operators can be constructed using nondeterministic rewriting systems. In particular, we investigate Wolfram model multiway rewriting systems based on string substitutions. Multiway systems were proposed by S. Wolfram as generic model systems for multicomputational processes, emphasizing their significance as a foundation for modeling complexity, nondeterminism, and branching structures of measurement outcomes. Here, we investigate a specific class of multiway systems based on cyclic character strings with a neighborhood constraint - the latter called Leibnizian strings. We show that such strings exhibit a Fermi-Dirac distribution for expectation values of occupation numbers of character neighborhoods. A Leibnizian string serves as an abstraction of a $N$ -fermion system. A multiway system of these strings encodes causal relations between rewriting events in a nondeterministic manner. The collection of character strings realizes a $\mathbb{Z}$ -module with a symmetric $\mathbb{Z}$ -bilinear form. For discrete spaces, this generalizes the notion of an inner product over a vector field. This admits a discrete analogue of the path integral and a $S$ -matrix for multiway systems of Leibnizian strings. The elements of this $S$ -matrix yield transition amplitudes between states of the multiway system based on an action defined over a sequence of Leibnizian strings. We then show that these $S$ -matrices give explicit representations of quantum gates for qubits and qudits, and also circuits composed of such gates. We find that, as formal models of nondeterministic computation, rewriting systems of Leibnizian strings with causal structure encode representations of the CNOT, $π/8$ , and Hadamard gates. Hence, using multiway systems one can represent quantum circuits for qubits.We show how representations of finite-dimensional quantum operators can be constructed using nondeterministic rewriting systems. In particular, we investigate Wolfram model multiway rewriting systems based on string substitutions. Multiway systems were proposed by S. Wolfram as generic model systems for multicomputational processes, emphasizing their significance as a foundation for modeling complexity, nondeterminism, and branching structures of measurement outcomes. Here, we investigate a specific class of multiway systems based on cyclic character strings with a neighborhood constraint - the latter called Leibnizian strings. We show that such strings exhibit a Fermi-Dirac distribution for expectation values of occupation numbers of character neighborhoods. A Leibnizian string serves as an abstraction of a $N$-fermion system. A multiway system of these strings encodes causal relations between rewriting events in a nondeterministic manner. The collection of character strings realizes a $\mathbb{Z}$-module with a symmetric $\mathbb{Z}$-bilinear form. For discrete spaces, this generalizes the notion of an inner product over a vector field. This admits a discrete analogue of the path integral and a $S$-matrix for multiway systems of Leibnizian strings. The elements of this $S$-matrix yield transition amplitudes between states of the multiway system based on an action defined over a sequence of Leibnizian strings. We then show that these $S$-matrices give explicit representations of quantum gates for qubits and qudits, and also circuits composed of such gates. We find that, as formal models of nondeterministic computation, rewriting systems of Leibnizian strings with causal structure encode representations of the CNOT, $π/8$, and Hadamard gates. Hence, using multiway systems one can represent quantum circuits for qubits.

quant-pharXiv:2512.20587Dec 24, 20250 citations

Automated reduction of fault-tolerant circuits

Hyeongjun Jeon, Jeonghoon Lee, Taehyun Kim

We present an automated method for reducing fault-tolerant circuits through fault-equivalent rewrites. Starting from a known fault-tolerant circuit, the search applies non-reducing enabling rules to expose Bell-pair reductions, each of which removes an ancilla preparation and a CNOT gate. Because every search transition preserves fault equivalence, the resulting circuits inherit the fault-tolerance properties of the input circuit. Candidate circuits are evaluated using circuit-level Monte Carlo simulation. For Shor-style syndrome extraction with the $[[7,1,3]]$ code, our method reduces one syndrome-measurement round from 30 to 18 ancilla preparations and from 54 to 42 CNOT gates. At a physical two-qubit error rate of $p = 10^{-3}$ , the optimized circuit lowers the logical error rate by approximately 21% for both logical basis states. The reduction ranges from 13% to 23% over a range of $p$ spanning two orders of magnitude. We also apply the method to Steane-based dynamic syndrome extraction constructed from Goto's verified logical- $\lvert 0 \rangle$ preparation, in which the verification qubit serves as a flag. The search selects a circuit using four ancillas and 14 CNOT gates, matching the resource counts of the previous design but with an improved CNOT depth. Under depolarizing idle noise at $3p/10$ the selected circuit lowers the logical error rate by approximately 15% for both logical basis states, and by approximately 10% at $p/10$ . These results demonstrate that automated fault-equivalent rewriting can identify circuits with lower resource costs or improved logical performance without separately verifying the fault tolerance of every candidate.We present an automated method for reducing fault-tolerant circuits through fault-equivalent rewrites. Starting from a known fault-tolerant circuit, the search applies non-reducing enabling rules to expose Bell-pair reductions, each of which removes an ancilla preparation and a CNOT gate. Because every search transition preserves fault equivalence, the resulting circuits inherit the fault-tolerance properties of the input circuit. Candidate circuits are evaluated using circuit-level Monte Carlo simulation. For Shor-style syndrome extraction with the $[[7,1,3]]$ code, our method reduces one syndrome-measurement round from 30 to 18 ancilla preparations and from 54 to 42 CNOT gates. At a physical two-qubit error rate of $p = 10^{-3}$, the optimized circuit lowers the logical error rate by approximately 21% for both logical basis states. The reduction ranges from 13% to 23% over a range of $p$ spanning two orders of magnitude. We also apply the method to Steane-based dynamic syndrome extraction constructed from Goto's verified logical-$\lvert 0 \rangle$ preparation, in which the verification qubit serves as a flag. The search selects a circuit using four ancillas and 14 CNOT gates, matching the resource counts of the previous design but with an improved CNOT depth. Under depolarizing idle noise at $3p/10$ the selected circuit lowers the logical error rate by approximately 15% for both logical basis states, and by approximately 10% at $p/10$. These results demonstrate that automated fault-equivalent rewriting can identify circuits with lower resource costs or improved logical performance without separately verifying the fault tolerance of every candidate.

quant-pharXiv:2610.09749Oct 8, 20260 citations

Transformation rules for CNOT-based quantum circuits and their applications

Kazuo Iwama, Shigeru Yamashita

New Generation ComputingDec 1, 20035 citations

Bases for quantum circuits

Alexei Kitaev, Alexander Khanievich Shen', M. Vyalyi

Graduate studies in mathematicsMay 31, 20020 citations

Toffoli Gate Rewrite Rules for Quantum Circuit Optimisation

Linh Bui

Quantum circuit optimisation is essential for reducing the resource requirements of quantum algorithms, particularly on current noisy and resource-constrained quantum hardware. Since several well-defined quantum circuit optimisation problems are classified as NP-hard, heuristic approaches, such as rewrite rules, are widely adopted. This thesis implements a set of Toffoli gate rewrite rules with an appropriate dependency-check algorithm within Pandora and evaluates their effectiveness on NRSCM and VBE adder circuits ranging from 16 to 2048 bits. The benchmarking results show that the effectiveness of the optimiser using the implemented rewrite rules strongly depends on input circuit structures and the selection of rules. In particular, a 50% reduction in the CNOT gate count was achieved for VBE circuits with an appropriate combination of rules, while NRSCM circuits did not exhibit any meaningful reduction. These results show the potential of the implemented method in reducing gate counts of certain types of quantum circuits with trade-offs in other gate counts. Future work could investigate and improve the current rewrite rule set to increase its effectiveness and enable a broader range of applicable circuits.Quantum circuit optimisation is essential for reducing the resource requirements of quantum algorithms, particularly on current noisy and resource-constrained quantum hardware. Since several well-defined quantum circuit optimisation problems are classified as NP-hard, heuristic approaches, such as rewrite rules, are widely adopted. This thesis implements a set of Toffoli gate rewrite rules with an appropriate dependency-check algorithm within Pandora and evaluates their effectiveness on NRSCM and VBE adder circuits ranging from 16 to 2048 bits. The benchmarking results show that the effectiveness of the optimiser using the implemented rewrite rules strongly depends on input circuit structures and the selection of rules. In particular, a 50% reduction in the CNOT gate count was achieved for VBE circuits with an appropriate combination of rules, while NRSCM circuits did not exhibit any meaningful reduction. These results show the potential of the implemented method in reducing gate counts of certain types of quantum circuits with trade-offs in other gate counts. Future work could investigate and improve the current rewrite rule set to increase its effectiveness and enable a broader range of applicable circuits.

Sep 4, 20260 citations

N

-fermion system. A multiway system of these strings encodes causal relations between rewriting events in a nondeterministic manner. The collection of character strings realizes a

\mathbb{Z}

-module with a symmetric

\mathbb{Z}

-bilinear form. For discrete spaces, this generalizes the notion of an inner product over a vector field. This admits a discrete analogue of the path integral and a

S

-matrix for multiway systems of Leibnizian strings. The elements of this

S

-matrix yield transition amplitudes between states of the multiway system based on an action defined over a sequence of Leibnizian strings. We then show that these

S

-matrices give explicit representations of quantum gates for qubits and qudits, and also circuits composed of such gates. We find that, as formal models of nondeterministic computation, rewriting systems of Leibnizian strings with causal structure encode representations of the CNOT,

π/8

, and Hadamard gates. Hence, using multiway systems one can represent quantum circuits for qubits.

[[7,1,3]]

code, our method reduces one syndrome-measurement round from 30 to 18 ancilla preparations and from 54 to 42 CNOT gates. At a physical two-qubit error rate of

p = 10^{-3}

, the optimized circuit lowers the logical error rate by approximately 21% for both logical basis states. The reduction ranges from 13% to 23% over a range of

p

spanning two orders of magnitude. We also apply the method to Steane-based dynamic syndrome extraction constructed from Goto's verified logical-

\lvert 0 \rangle

preparation, in which the verification qubit serves as a flag. The search selects a circuit using four ancillas and 14 CNOT gates, matching the resource counts of the previous design but with an improved CNOT depth. Under depolarizing idle noise at

3p/10

the selected circuit lowers the logical error rate by approximately 15% for both logical basis states, and by approximately 10% at

p/10

. These results demonstrate that automated fault-equivalent rewriting can identify circuits with lower resource costs or improved logical performance without separately verifying the fault tolerance of every candidate.