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
Z-module with a symmetric
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 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-
∣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/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.
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.