Background Knowledge for the Quantum Circuit Knitting Paper — A Guide for EE Engineers

This document provides the quantum computing background needed to read the paper
"A Hardware-Aware Gate Cutting Framework for Practical Quantum Circuit Knitting" (ICCAD 2024).
It is written for readers with an Electrical Engineering (EE) background who have not
formally studied quantum mechanics. All concepts are explained using analogies from
signal processing, digital circuits, linear algebra, and PCB layout & routing.

I. Qubits: From Booleans to Vectors

1.1 Classical Bits vs. Qubits

1.2 Vector Representation of Quantum States

A qubit's state is a 2-dimensional column vector (analogous to a phasor in AC circuit analysis, carrying both magnitude and phase):

where $c_0$ and $c_1$ are complex numbers (probability amplitudes) satisfying the normalization condition $|c_0|^{2 + |c_1|}2 = 1$.

• $|c_0|^2$ is the probability of measuring 0.
• $|c_1|^2$ is the probability of measuring 1.

EE Analogy: Imagine a signal on a transmission line that is not simply high or low, but simultaneously carries two frequency components (a "0 component" and a "1 component"), each with its own amplitude and phase.

1.3 Superposition

When both $c_0$ and $c_1$ are nonzero, the qubit is in a superposition — it is both 0 and 1 at the same time.

Example: $|\psi\rangle = \frac{1}{\sqrt{2}} |0\rangle + \frac{1}{\sqrt{2}} |1\rangle = \begin{bmatrix} 0.707 \ 0.707 \end{bmatrix}$

The probability of measuring 0 or 1 is each 50%.

Physical implementation: On a superconducting quantum chip, applying a microwave pulse with exactly half the duration needed for a full flip ($\pi/2$ pulse) pushes $|0\rangle$ into this superposition state.

1.4 Measurement and Collapse

Once a qubit is measured, its superposition collapses irreversibly into a definite 0 or 1.

This is fundamentally different from classical circuits:

• In classical circuits, you can probe a voltage with an oscilloscope at any time without affecting the signal.
• For qubits, "looking" at it irreversibly destroys the superposition information.

This property is the fundamental reason why qubits cannot be refreshed like SDRAM.

1.5 Multi-Qubit Systems and Dimensional Explosion

When there are 2 qubits A and B, their joint state space is the tensor product (Kronecker product) of their individual spaces:

• 2 qubits → 4-dimensional vector ($2^2 = 4$)
• $n$ qubits → $2^n$-dimensional vector

Key insight: This is the source of quantum computing's exponential power — $n$ qubits can simultaneously represent a superposition of $2^n$ states.
It is also why classically simulating quantum computation is so hard: simulating 50 qubits requires storing and operating on a $2^{{50}$ ($\approx 10}{15}$) dimensional vector.

II. Quantum Gates: Matrix Transformations

2.1 Core Concept

In classical circuits, logic gates are Boolean functions (AND, OR, NOT).
In quantum circuits, all quantum gates are mathematically just matrices. Executing a quantum gate is performing a matrix multiplication on the state vector:

where $U$ is a unitary matrix satisfying $U^\dagger U = I$. Unitarity guarantees reversibility and probability conservation.

2.2 Common Single-Qubit Gates ($2 \times 2$ Matrices)

2.3 CNOT Gate (Controlled-NOT) — The Source of Entanglement

The CNOT gate is the most important 2-qubit gate in quantum computing, represented by a $4 \times 4$ matrix.

Logic rule: If the control qubit A = 1, flip the target qubit B; if A = 0, B stays unchanged.

EE logic perspective: It is equivalent to a classical XOR gate: $B_{\text{out}} = A \oplus B_{\text{in}}$.

Block matrix perspective:

• Upper-left $I$ (identity matrix): When A = 0, pass through (do nothing).
• Lower-right $X$ (NOT matrix): When A = 1, flip B.

Physical implementation (superconducting chips):

On IBM's superconducting quantum chips, the CNOT gate is implemented via Cross-Resonance (CR) microwave pulses:

1. Qubits A and B are two LC oscillator circuits operating at different resonant frequencies.
2. They are weakly coupled through a microwave transmission line (coupling cavity).
3. A microwave pulse at B's resonant frequency is applied to qubit A.
4. Due to the coupling, whether B flips depends on A's current state.

Mathematical proof of entanglement:

Suppose A is in the superposition $\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$, and B is initialized to $|0\rangle$.
The joint initial state is:

After multiplying by the CNOT matrix:

Now A and B are bound together: measuring A as 0 guarantees B is also 0; measuring A as 1 guarantees B is also 1. This 4D vector cannot be factored back into two independent 2D vectors — this is entanglement.

2.4 CZ Gate (Controlled-Z) — The Primary Target of "Cutting" in the Paper

Logic rule: Apply a phase flip (multiply by −1) if and only if both A and B are 1.

EE analogy: An AND-gated phase inverter. Only when both inputs are high does the output signal's phase flip by 180°.

The CZ gate is equivalent in importance to the CNOT gate for generating entanglement. The paper chooses to "cut" CZ gates during circuit partitioning.

2.5 SWAP Gate — The Most Expensive "Wire"

Function: Exchange the states of two qubits.

EE analogy: An on-chip data router or jumper wire. Because physical qubits are fixed in place and can only interact with adjacent neighbors, non-adjacent qubits must relay data through a chain of SWAP gates.

Underlying implementation: 3 alternating-direction CNOT gates in cascade

A SWAP gate cannot be directly executed on hardware. It must be decomposed into 3 CNOT gates:

where $\text{CNOT}{A \to B}$ means A controls B, and $\text{CNOT}{B \to A}$ means B controls A (reversed pulse direction).

This is exactly the classical XOR Swap algorithm (swapping two variables without a temporary):

a = a XOR b   // 1st CNOT: A drives B
b = a XOR b   // 2nd CNOT: B drives A (reversed)
a = a XOR b   // 3rd CNOT: A drives B

Role of entanglement in this process:

1. 1st CNOT: A and B become entangled (signals mixed).
2. 2nd CNOT (reversed): Exploiting XOR's self-cancellation property ($a \oplus a = 0$), A's original component is cancelled out. A becomes a clean copy of B's initial value.
3. 3rd CNOT: Using the now-clean A to interfere with B one last time, B's residual mixed component is precisely cancelled.

Final result: Entanglement completely vanishes (the "solder joint" is removed), and A and B have cleanly swapped their data.

Matrix verification: The CNOT matrix satisfies $\text{CNOT}^2 = I$ (it is its own inverse), which enables the three alternating cascades to form perfect destructive interference.

Performance cost (the paper's core optimization target):

If 10 SWAP gates are chained to route data across a chip, that requires 30 CNOT gates — the signal will be completely drowned in microwave noise.

III. Physical Constraints of Quantum Hardware

3.1 Topology

In classical PCB or ASIC design, EDA tools can route metal traces across multiple layers to connect any two pins.

Quantum chips cannot do this. Physical qubits (superconducting LC resonators) can only couple through fixed microwave transmission lines. The chip's connectivity forms a fixed topology graph.

For example, IBM's Eagle processor (127 qubits) uses the "Heavy-Hex" topology: each qubit is directly connected to only 2 or 3 neighbors.

EE analogy: This is similar to an FPGA's interconnect fabric. Logical netlists must go through Place & Route to be mapped onto physical routing tracks.

3.2 Qubit Routing

When a logical circuit requires two non-adjacent physical qubits to perform a 2-qubit gate, the quantum compiler must insert SWAP gates to "transport" the data to an adjacent position.

Routing example: Physical layout A — B — C — D, and we need A to interact with D:

1. SWAP(A, B): A's data moves to position B (3 CNOTs).
2. SWAP(B, C): Data continues moving to position C (3 CNOTs).
3. Now C and D are adjacent — execute the target operation.

Total overhead: 6 extra CNOT gates inserted.

3.3 Fidelity and Circuit Depth

• Fidelity: How closely the quantum computation result matches the theoretically correct answer. EE analogy: Signal-to-Noise Ratio (SNR).
• Circuit depth: The longest chain of gates from input to output. EE analogy: Critical Path Length.
• Iron law: The deeper the circuit (more gates traversed), the greater the accumulated noise, and the lower the fidelity.

3.4 Why Can't Qubits Be "Refreshed"?

Because qubits cannot be refreshed, all computation must complete before the quantum state "decays" (decoherence). Therefore, minimizing circuit depth (using fewer SWAP gates) is the top priority in the NISQ era.

IV. Quantum Circuit Knitting

4.1 Basic Idea

When a quantum circuit requires more qubits than a physical chip can hold, the large circuit is cut into multiple subcircuits that fit on the small chip. These subcircuits are run independently, and finally a classical computer (CPU/GPU) stitches the results back together.

EE analogy: Partitioning an oversized PCB netlist and mapping it onto multiple physically isolated small FPGA development boards.

4.2 Gate Cutting — The Approach Used in This Paper

When the algorithm decides to cut a 2-qubit gate (e.g., CZ gate) that spans two subcircuits:

1. Remove the 2-qubit gate.
2. Insert specific single-qubit gates and mid-circuit measurement operations at both cut endpoints.
3. Generate multiple different subcircuit configurations and run them separately.
4. The classical computer aggregates results from all configurations using a mathematical formula.

4.3 Quasiprobability Decomposition

This is the mathematical foundation of gate cutting.
Core principle: A $4 \times 4$ two-qubit gate matrix can be decomposed into a sum of 4 independent tensor products of single-qubit operations.

For the CZ gate, its matrix decomposes into the following 4-term linear combination (corresponding to Figure 4 in the paper):

where:

• $I$: Identity matrix (do nothing).
• $Z$: Pauli-Z gate (180° phase flip).
• $c_i$: Weight coefficients (some positive, some negative — hence "quasiprobability").
• $\otimes$: Tensor product (Kronecker product), indicating that two single-qubit operations act independently on their respective qubits.

None of these terms require any physical connection — the A-side and B-side operations are completely independent.

4.4 Post-selection

When executing certain decomposition terms, a mid-circuit measurement of the qubit is required.
Only when the measurement outcome matches the value required by the formula ($+1$ or $-1$) is that run's data kept.
Mismatched results are discarded.

EE analogy: This is a mid-circuit IF-condition filter. It wastes a large amount of sampling data and is the direct cause of exponential growth in sampling overhead.

4.5 Classical Postprocessing

After collecting results from all configurations, the classical computer (GPU) multiplies each result by its corresponding coefficient and sums them up according to the quasiprobability decomposition formula. Mathematically, this is equivalent to Tensor Network Contraction — essentially large-scale Kronecker product operations on matrices.

The paper uses the NVIDIA cuTensorNet library for GPU-accelerated execution of this step.

V. Cost Analysis: Two "Exponential Bills"

After cutting a circuit, the system faces two fundamentally different costs:

5.1 Quantum Side: Sampling Overhead — $\mathcal{O}(\gamma^{2n})$

Why this happens:

1. Quasiprobability decomposition introduces negative coefficients.
2. Negative coefficients cause quadratic accumulation of signal variance (analogous to noise power addition in EE).
3. Post-selection discards a large fraction of non-conforming data.
4. To suppress variance and maintain SNR, the only option is to increase the number of samples (shots).

Examples:

5.2 Classical Side: Postprocessing Overhead — $\mathcal{O}(4^n)$

Why this happens: Each cut of a 2-qubit gate produces 4 replacement configurations. With $n$ cuts, all combinations total $4^n$.

Examples:

Key takeaway: Without mathematical approximations, the number of cuts $n$ typically cannot exceed 5 to 10. This means every single cut is precious — it must be placed at the most advantageous position.

VI. Hardware-Aware Cutting: The Paper's Core Innovation

6.1 The Problem with Previous Methods

Traditional cutting algorithms (e.g., CutQC) focus solely on minimizing the number of cuts $n$, completely ignoring the target chip's physical topology. The consequence:

1. The resulting subcircuits are logically clean but physically mismatched.
2. The quantum compiler is forced to insert massive numbers of SWAP gates within each subcircuit for routing.
3. Circuit depth skyrockets, and fidelity collapses.

6.2 This Paper's Solution

Introduce hardware topology information upfront during the cutting stage, jointly optimizing both "number of cuts" and "number of SWAP gates."

Core tool — Graph Edit Distance (GED):

• Model the subcircuit's qubit interaction relationships as a logical interaction graph.
• Model the target chip's physical wiring as a hardware topology graph.
• Compute the graph edit distance between the two: the smaller the GED, the better the subcircuit matches the hardware, and the fewer SWAP gates will be needed.

Cost function:

By tuning the parameter $\alpha$, the algorithm automatically finds the optimal trade-off between cut count and routing overhead.

6.3 Experimental Results

VII. Summary: The Paper in One Sentence

Because circuit cutting is constrained by the exponential costs of $4^{n$ and $9}n$,
we are destined to make only a very small number of cuts.
Since every cut is so precious, we must not cut blindly.
This paper develops a hardware-aware algorithm that compares against the physical
chip's wiring diagram (GED) before cutting, ensuring that the resulting subcircuits
fit the hardware topology as closely as possible — thereby drastically reducing SWAP gates,
lowering circuit depth, and preserving the fragile fidelity.