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

A study on CNOT−based quantum circuits using rewriting systems

Issei Sakashita

Published Oct 31, 2013• 0 citations
Publisher
DOI
10.15017/1398533

Related papers

A Pattern Matching Based Framework for Quantum Circuit Rewriting

Hui Jiang, Dian-Kang Li, Yuxin Deng +1 more

Journal of Computer Science and Technology•Nov 1, 2024•2 citations

Quantum Gates from Wolfram Model Multiway Rewriting Systems

Furkan Semih Dündar, Xerxes D. Arsiwalla, Hatem Elshatlawy

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.20587•Dec 24, 2025•1 citation

Transformation rules for CNOT-based quantum circuits and their applications

Kazuo Iwama, Shigeru Yamashita

New Generation Computing•Dec 1, 2003•6 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.

quant-pharXiv:2610.09749•Oct 8, 2026•0 citations

From Quantum Circuits to Quantum Computational Logics

María Luisa Dalla Chiara, Roberto Giuntini, Roberto Leporini +1 more

Trends in logic•Jan 1, 2018•0 citations

Lin-search: Scaling Exact Synthesis of CNOT Circuits via Hybrid Iterative Deepening Search

Chenjian Li, Xiangzhen Zhou, Ji Guan +3 more

Exact synthesis of CNOT circuits is a core primitive in quantum compilers, but existing SAT-based and database-based methods suffer from encoding overhead, memory bottlenecks, and poor scalability. We propose Lin-search, a framework for exact CNOT synthesis based on iterative deepening search. Lin-search explores circuits in non-decreasing gate count while pruning partial solutions using variable-mismatch constraints, matrix-based lower bounds, and canonicalization under local circuit equivalences. In random benchmarks, Lin-search finds optimal circuits with up to 15 qubits and 15 CNOT gates in 600 seconds on a laptop, achieving up to speedup 100×–1000× and scalability of +3 qubits over a SAT-based baseline incorporated in Qiskit. When integrated as a rewriting kernel in a Clifford+T optimization flow, Lin-search further reduces CNOT count by 16% compared to the original circuits on average and decreases timeout counts by 30% compared to the SAT-based method, demonstrating its effectiveness as a practical exact synthesis engine for quantum compilers.

ACM/IEEE Design Automation Conference (DAC)•Jul 26, 2026•1 citation
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 NNN-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 Z\mathbb{Z}Z-module with a symmetric Z\mathbb{Z}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 SSS-matrix for multiway systems of Leibnizian strings. The elements of this SSS-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 SSS-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π/8π/8, and Hadamard gates. Hence, using multiway systems one can represent quantum circuits for qubits.
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]][[7,1,3]][[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−3p = 10^{-3}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 ppp spanning two orders of magnitude. We also apply the method to Steane-based dynamic syndrome extraction constructed from Goto's verified logical-∣0⟩\lvert 0 \rangle∣0⟩ 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/103p/103p/10 the selected circuit lowers the logical error rate by approximately 15% for both logical basis states, and by approximately 10% at p/10p/10p/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.
Exact synthesis of CNOT circuits is a core primitive in quantum compilers, but existing SAT-based and database-based methods suffer from encoding overhead, memory bottlenecks, and poor scalability. We propose Lin-search, a framework for exact CNOT synthesis based on iterative deepening search. Lin-search explores circuits in non-decreasing gate count while pruning partial solutions using variable-mismatch constraints, matrix-based lower bounds, and canonicalization under local circuit equivalences. In random benchmarks, Lin-search finds optimal circuits with up to 15 qubits and 15 CNOT gates in 600 seconds on a laptop, achieving up to speedup 100×–1000× and scalability of +3 qubits over a SAT-based baseline incorporated in Qiskit. When integrated as a rewriting kernel in a Clifford+T optimization flow, Lin-search further reduces CNOT count by 16% compared to the original circuits on average and decreases timeout counts by 30% compared to the SAT-based method, demonstrating its effectiveness as a practical exact synthesis engine for quantum compilers.