Circuit Composition and Quantum Simulation

7. Composing Operators, and the Direct Comparison to Quantum Circuit Simulation

NAND completeness

Chaining a single gate — NAND — is provably enough to reach every boolean function, including the “junk” functions from Shannon’s counting argument that have no single-gate shortcut. They’re not unreachable, they just need more gates chained together:

#define NAND(a,b) (!((a)&&(b)))
bool NOT(bool a)       { return NAND(a,a); }
bool AND(bool a,bool b){ return NOT(NAND(a,b)); }
bool OR(bool a,bool b) { return NAND(NOT(a),NOT(b)); }

The relevant question shifts from “does a formula exist” (answered by functional completeness: yes, always) to “how few gates does this specific function need” — which is exactly circuit minimization, the real field (Karnaugh maps by hand, Quine–McCluskey or ESPRESSO as automated tools) that finds the shortest gate chain for a target function.

Bitslicing: the actual parallel speedup

Chaining k gates to evaluate one row costs O(k) instructions — no free lunch. Applying the same chain to a full machine word instead of one bit evaluates as many rows as there are bits in the word, in the same instruction count:

uint64_t out = ~(a & b) ^ c;  // one 3-gate chain, 64 answers computed at once

This is a real, named technique (bitslicing), used in cryptographic implementations (bitsliced AES/DES) for exactly this reason.

The direct comparison to quantum circuit simulation

Every piece built in this conversation turned out to have a named counterpart in real quantum-simulation research:

Table as one vector [a,b,c,d]      →  State vector (2^n amplitudes)
Top/bottom cofactor split          →  Decision-diagram (QMDD) node split
Redundancy / compressibility       →  Entanglement / how well a state compresses
                                        into a small decision diagram or MPS
Closed-form evaluator, no stored   →  Stabilizer formalism (Gottesman-Knill
table (the "Doom hack" move)            theorem): Clifford-only circuits (H, S,
                                        CNOT) never need the full 2^n vector at
                                        all — stored in O(n²) bits,
                                        updated in polynomial time
NAND completeness                  →  Universal gate sets (e.g. H, T, CNOT):
                                        any quantum operation is reachable
Circuit minimization               →  Solovay–Kitaev theorem: bounds how
                                        few gates approximate a target unitary
                                        to a given precision
Bitslicing (one chain, many lanes) →  SIMD/GPU-parallel amplitude updates

The one correction that mattered here: two different “walls”

Two different exponential difficulties appeared across the conversation and it was important not to conflate them:

• 2^n (a single table’s or a single quantum state’s own size) is the real, recurring bottleneck that classical quantum simulators fight for one specific circuit. Decision diagrams, tensor networks, and the stabilizer trick are all built to dodge this.
• 2^(2^n) (the space of every possible function/circuit) is the space you’d have to search if you were trying to find or compile a good circuit from scratch, out of every conceivable one — this is what Solovay–Kitaev and gate synthesis research address, not the cost of running an already-chosen circuit.

The honest limit: what none of this covers

None of the structures built here — grids, halves, redundancy scores, closed forms, NAND chains — had a continuous parameter (a dial-able θ). That’s exactly the piece Gottesman–Knill/stabilizer methods don’t cover either: the moment a real circuit uses a non-Clifford gate (an arbitrary rotation), the polynomial-time trick stops applying and the full 2^n cost returns. Whether a circuit is “how much Clifford vs. not” is the single number that predicts whether a real simulator can cheat through it.

Related Research: The quantum circuit composition and stabilizer formalism work here connects directly to Algebraic Balance: A Unified Mathematical Framework for Physical Systems which explores quantum computing applications and mathematical frameworks for physical systems, including stabilizer formalism and universal gate sets.