Circuit Depth Thresholds for Logical Triviality in Quantum Error-Correcting Codes

Sudoma, Oksana

Circuit Depth Thresholds for Logical Triviality in Quantum Error-Correcting Codes

Oksana Sudoma

November 26, 2025

Abstract

We establish a quantitative relationship between circuit depth and logical triviality in quantum error-correcting codes by combining two standard results. First, the Knill-Laflamme error correction conditions imply that operations supported on fewer than $d/2$ physical qubits act trivially on codes with distance $d$ . Second, circuit depth bounds support growth: for depth- $D$ circuits with $k$ -local gates on a lattice with coordination number $z$ (the maximum degree of any vertex: $z=2$ for 1D chains, $z=4$ for 2D square lattices, $z=6$ for 3D cubic lattices), the support satisfies $\ell\leq\ell_{0}+(k-1)zD$ . Combining these yields an explicit circuit depth threshold:

D<\frac{d/2-\ell_{0}}{(k-1)z}\quad\Longrightarrow\quad U|_{\mathcal{H}_{\rm code% }}\propto\mathrm{Id}

The contribution is making this threshold explicit and operational. We demonstrate with the [[5,1,3]] perfect code and provide experimental verification protocols for ion trap and superconducting qubit platforms. The result provides a task-independent criterion for when circuit-based operations preserve encoded quantum information.

1 Introduction

Concrete Experience: The observer’s dilemma.

In quantum error correction, an observer with limited computational resources faces a fundamental constraint. Alice operates a quantum computer with 100 physical qubits encoding 10 logical qubits via a stabilizer code with distance $d=7$ . She can perform single-qubit gates, two-qubit gates, and measurements. However, her circuit depth is bounded by available time and hardware constraints. A natural question arises: What operations can Alice implement on the logical qubits using only local physical operations?

If Alice applies a single-qubit rotation to one physical qubit, does this affect the logical state? What about a two-qubit gate? A three-qubit gate? Standard quantum error correction theory tells us codes with distance $d$ can correct errors on fewer than $d/2$ qubits. But how does this translate into a bound on circuit depth?

From code distance to circuit depth bounds.

The distance $d$ of a quantum error-correcting code measures the minimum weight of an operator that acts non-trivially on the logical subspace. Operations supported on fewer than $d/2$ physical sites cannot change the logical information—they act as the identity (up to a global phase) when restricted to the code subspace. This is the foundation of fault-tolerant quantum computation [GOT97, KL97].

We show this threshold translates directly into a circuit depth bound. If a depth- $D$ circuit acts on a support small enough to remain below the distance threshold ( $\ell<d/2$ ), then the operation must be logically trivial. This provides a task-independent, falsifiable criterion for when locality is preserved.

Scope and limitations.

This paper proves a specific, limited result: the locality-distance relationship in quantum error correction implies a circuit depth threshold for logical triviality. We do not claim:

A general theory of “complexity-bounded locality” in physics
Applications to continuous systems (PDEs, gravity) without additional justification
Explicit constants beyond what standard QEC theory provides

Our contribution is making the QEC threshold explicit in terms of circuit parameters.

Potential holographic connections.

In holographic systems where the boundary theory may encode bulk physics via quantum error correction [ADH15, PYH+15], our result could provide operational criteria for bulk locality. This connection remains conjectured and requires further investigation (see Section 6.2). Our main contribution is the QEC circuit depth threshold; holographic applications are speculative extensions.

Comparison with Lieb-Robinson bounds.

Traditional Lieb-Robinson bounds [LR72] constrain information spreading under continuous Hamiltonian evolution: operators initially separated by distance $r$ have commutators bounded by $e^{-\mu(r-v_{\text{LR}}t)}$ . Our bound is fundamentally different: it constrains what operations an observer can implement using discrete gate circuits of bounded depth. The Lieb-Robinson bound applies to continuous dynamics; ours applies to discrete circuits. See Remark 1 for detailed comparison.

Structure of the paper.

Following Kolb’s learning cycle [KOL14], we progress from concrete scenarios (Introduction) to formal definitions (Section 2: Reflective Observation), to the main theorem (Section 3: Abstract Conceptualization), to worked examples (Section 4: Active Experimentation), and finally to experimental protocols and discussion (Sections 5-6).

Section 2 establishes precise mathematical definitions. Section 3 states and proves the main theorem with complete rigor. Section 4 provides a fully worked example using the [[5,1,3]] perfect code. Section 5 details experimental protocols for ion traps and superconducting qubits. Section 6 discusses implications, connections to holography, and open questions.

2 Definitions and Mathematical Setup

This section provides precise definitions of all terms used in the main theorem. Readers familiar with quantum error correction and circuit complexity may skim this section and refer back as needed.

2.1 Code Distance and Error Correction

Let $\mathcal{H}=\bigotimes_{i=1}^{n}\mathcal{H}_{i}$ be the physical Hilbert space with $n$ subsystems (typically qubits, $\dim\mathcal{H}_{i}=2$ ). A quantum error-correcting code is an isometric embedding $E:\mathcal{H}_{\rm logical}\to\mathcal{H}$ of a $k$ -dimensional logical space into the $2^{n}$ -dimensional physical space, with projector $P_{\rm code}=EE^{\dagger}$ onto the code subspace $\mathcal{H}_{\rm code}=\text{Im}(E)$ .

Remark on notation: The code projector $P_{\rm code}$ is a projection operator (Hermitian, idempotent: $P_{\rm code}^{2}=P_{\rm code}$ , $P_{\rm code}^{\dagger}=P_{\rm code}$ ) that projects the full Hilbert space onto the code subspace. It can be equivalently defined as:

$P_{\rm code}=EE^{\dagger}$ where $E$ is the isometric encoding map, or
$P_{\rm code}=\prod_{j}(1+S_{j})/2$ where $\{S_{j}\}$ are stabilizer generators (for stabilizer codes)

Both definitions are equivalent for stabilizer codes [GOT97]. We use the encoding map form for generality.

Definition 1 (Weight Function).

For an operator $E\in\mathcal{B}(\mathcal{H})$ , the weight function $\mathrm{wt}(E)$ counts the number of subsystems on which $E$ acts non-trivially:

\mathrm{wt}(E)=\min\left|\{i\in[n]:E=E_{S}\otimes I_{\bar{S}},\,S\subseteq[n],% \,|S|=\mathrm{wt}(E)\}\right|

where $E_{S}$ acts on $\bigotimes_{i\in S}\mathcal{H}_{i}$ and $I_{\bar{S}}$ is the identity on the complement. Equivalently, for qubits, $\mathrm{wt}(E)$ is the number of non-identity factors in the minimal Pauli decomposition of $E$ .

Definition 2 (Code Distance).

The distance $d$ of a code with projector $P_{\rm code}$ is:

d=\min\{\mathrm{wt}(E):E\in\mathcal{B}(\mathcal{H}),\,P_{\rm code}EP_{\rm code% }\not\propto P_{\rm code},\,E\neq 0\}

This is the minimum weight of any operator that acts non-trivially on the code subspace.

Notation: We use $d$ (without subscript) throughout this paper to denote code distance. When emphasizing it is a property of the code, we write $d_{\rm code}$ , but both notations are equivalent: $d=d_{\rm code}$ .

A code with distance $d$ can detect errors on any $d-1$ qubits and correct errors on any $\lfloor(d-1)/2\rfloor$ qubits. This follows from the Knill-Laflamme error correction conditions [KL97]: a code with distance $d$ can correct errors on any $\lfloor(d-1)/2\rfloor$ qubits, meaning errors with weight less than $d/2$ are correctable.

2.2 Locality and Algorithmic Complexity

Definition 3 (Logically Trivial Operation).

An operation $U$ is logically trivial on code subspace $\mathcal{H}_{\rm code}$ if and only if:

P_{\rm code}UP_{\rm code}=e^{i\phi}P_{\rm code}

for some global phase $\phi\in\mathbb{R}$ . Equivalently, $U$ preserves all logical information up to an unobservable phase.

Definition 4 (Support and Locality).

For a unitary $U$ acting on $\mathcal{H}=\bigotimes_{i=1}^{n}\mathcal{H}_{i}$ :

The support $\mathrm{supp}(U)$ is the minimal set $S\subseteq[n]$ such that $U=U_{S}\otimes I_{\bar{S}}$ for some unitary $U_{S}$ on $\bigotimes_{i\in S}\mathcal{H}_{i}$ .
The locality parameter is $\ell=|\mathrm{supp}(U)|$ (the cardinality of the support set).
For qubits arranged on a lattice $\Lambda$ , the coordination number $z=z(\Lambda)$ is the maximum degree of any vertex in the connectivity graph (e.g., $z=2$ for 1D chains, $z=4$ for 2D square lattices, $z=6$ for 3D cubic lattices).

Notation consistency: Throughout this paper, we use $\ell=|\mathrm{supp}(U)|$ to denote support size. When referring to the support set itself, we write $\mathrm{supp}(U)$ ; when referring to its cardinality, we write $|\mathrm{supp}(U)|$ or equivalently $\ell$ .

Definition 5 (Circuit Complexity).

For a unitary $U$ implementable by a circuit $\mathcal{C}$ from a universal finite gate set $\mathcal{G}$ :

The circuit depth $D(U)$ is the time-like length of the circuit DAG—the longest chain of sequential gate dependencies. For a circuit with layered structure, this is the number of sequential layers.
The gate complexity is $G(U)=\min\{|\mathcal{C}|:\mathcal{C}\text{ implements }U\}$ , where $|\mathcal{C}|$ is the total number of gates.

Critical distinction: Circuit depth $D$ and gate count $G$ are related but distinct. For a circuit with $D$ layers and up to $n$ gates per layer, $G\geq D$ (with equality only for fully-parallelized circuits). Theorem 1 bounds support in terms of depth $D$ , not gate count $G$ .

For this paper, we use gate complexity $G(U)$ as our measure of algorithmic complexity: $\mathcal{C}_{\text{alg}}(U):=G(U)$ .

Note: Some authors use $\log_{2}(G)$ for information-theoretic interpretations. We use $G$ directly for consistency with circuit complexity literature.

This definition captures the computational cost of implementing $U$ using local gates. It aligns with standard circuit complexity in quantum computation [NC00] and holographic complexity proposals [SUS16, BRS+16].

3 Main Result: Complexity-Bounded Locality

We now state and prove the main theorem. This establishes a quantitative relationship between circuit complexity, code distance, and locality.

Lemma 1 (Knill-Laflamme Projection).

Let $\mathcal{H}_{\rm code}$ be a code with distance $d$ and projector $P_{\rm code}$ . For any operator $E$ with $\mathrm{wt}(E)<d$ :

P_{\rm code}EP_{\rm code}=c_{E}\,P_{\rm code}

where $c_{E}=\mathrm{Tr}(P_{\rm code}E)/\dim(\mathcal{H}_{\rm code})$ .

Proof.

By the Knill-Laflamme conditions [KL97], for $\mathrm{wt}(E)<d$ :

\langle\psi_{i}|E|\psi_{j}\rangle=c_{E}\delta_{ij}

for all code basis states $|\psi_{i}\rangle$ . This means $E$ restricted to the code subspace is diagonal with constant entries $c_{E}$ . Hence $P_{\rm code}EP_{\rm code}=c_{E}P_{\rm code}$ . ∎

Lemma 2 ( $L^{1}$ Ball Volume).

The number of lattice sites in $\mathbb{Z}^{d}$ within $L^{1}$ distance $R$ of the origin is:

V_{d}(R)=|\{v\in\mathbb{Z}^{d}:\|v\|_{1}\leq R\}|=\sum_{j=0}^{\min(R,d)}\binom% {d}{j}\binom{R}{j}2^{j}

For fixed $d$ and large $R$ :

V_{d}(R)=\frac{(2R)^{d}}{d!}+O(R^{d-1})

Proof.

This is a standard result in combinatorics (see [STA97]). The count follows from partitioning lattice points by the number of nonzero coordinates and using inclusion-exclusion. ∎

Theorem 1 (Locality from Code Distance).

Let $\mathcal{H}_{\rm code}\subset\mathcal{H}$ be a quantum error-correcting code with distance $d$ . Let $U$ be a unitary operation.

(a) Support-Based Triviality: If $\ell:=|\mathrm{supp}(U)|<d/2$ , then:

P_{\rm code}\,U\,P_{\rm code}=e^{i\phi}P_{\rm code}

for some phase $\phi\in\mathbb{R}$ . That is, $U$ acts trivially on the code subspace.

(b) Circuit Depth Bound on Support: If $U$ is implemented by a depth- $D$ circuit using $k$ -local nearest-neighbor gates on a $d$ -dimensional hypercubic lattice, and $U$ initially acts on $\ell_{0}$ qubits in a connected region, then:

|\mathrm{supp}(U)|\leq V_{d}((k-1)D)+\ell_{0}-1

where $V_{d}(R)$ is the number of lattice sites within $L^{1}$ distance $R$ of the origin:

1D: $V_{1}(R)=2R+1$ , giving $\ell_{D}\leq\ell_{0}+2(k-1)D$
2D: $V_{2}(R)=2R^{2}+2R+1$ , giving $\ell_{D}=O(D^{2})$
3D: $V_{3}(R)=\frac{4}{3}R^{3}+2R^{2}+\frac{8}{3}R+1$ , giving $\ell_{D}=O(D^{3})$

Corollary (Depth Threshold for Triviality): Combining (a) and (b), we obtain dimension-dependent thresholds:

1D Lattice: If

D<\frac{d_{\rm code}/2-\ell_{0}}{2(k-1)}

then $U|_{\mathcal{H}_{\rm code}}\propto\mathrm{Id}$ .

Derivation (1D): Set $\ell_{0}+2(k-1)D<d_{\rm code}/2$ and solve for $D$ :

2(k-1)D<d_{\rm code}/2-\ell_{0}\quad\Longrightarrow\quad D<\frac{d_{\rm code}/% 2-\ell_{0}}{2(k-1)}

2D Lattice: If

D<\frac{-1+\sqrt{1+2(d_{\rm code}/2-\ell_{0})}}{2}\approx\sqrt{\frac{d_{\rm code% }/2-\ell_{0}}{2}}

then $U|_{\mathcal{H}_{\rm code}}\propto\mathrm{Id}$ .

Derivation (2D): For $k=2$ (nearest-neighbor), we require $V_{2}((k-1)D)+\ell_{0}-1<d_{\rm code}/2$ :

	$\displaystyle 2((k-1)D)^{2}+2((k-1)D)+1+\ell_{0}-1$	$\displaystyle<d_{\rm code}/2$
	$\displaystyle 2D^{2}+2D+\ell_{0}$	$\displaystyle<d_{\rm code}/2$
	$\displaystyle 2D^{2}+2D$	$\displaystyle<d_{\rm code}/2-\ell_{0}$

Solving the quadratic $2D^{2}+2D-(d_{\rm code}/2-\ell_{0})=0$ using the quadratic formula with $a=2$ , $b=2$ , $c=-(d_{\rm code}/2-\ell_{0})$ :

D=\frac{-2+\sqrt{4+8(d_{\rm code}/2-\ell_{0})}}{4}=\frac{-2+2\sqrt{1+2(d_{\rm code% }/2-\ell_{0})}}{4}=\frac{-1+\sqrt{1+2(d_{\rm code}/2-\ell_{0})}}{2}

For large $d_{\rm code}$ , $\sqrt{1+2x}\approx\sqrt{2x}$ when $x\gg 1$ , giving $D\approx\sqrt{(d_{\rm code}/2-\ell_{0})/2}$ .

3D Lattice: If $D$ satisfies $\frac{4}{3}D^{3}+2D^{2}+\frac{8}{3}D+\ell_{0}<d_{\rm code}/2$ , then $U|_{\mathcal{H}_{\rm code}}\propto\mathrm{Id}$ . For large $d_{\rm code}$ , this gives $D\lesssim(3d_{\rm code}/8)^{1/3}$ .

Derivation (3D): For $k=2$ , we require $V_{3}(D)+\ell_{0}-1<d_{\rm code}/2$ :

\frac{4}{3}D^{3}+2D^{2}+\frac{8}{3}D+\ell_{0}<d_{\rm code}/2

For large $d_{\rm code}$ where the cubic term dominates: $\frac{4}{3}D^{3}\approx d_{\rm code}/2$ , giving $D\approx\left(\frac{3d_{\rm code}}{8}\right)^{1/3}$ .

For nearest-neighbor gates ( $k=2$ ) on all lattice geometries, the threshold scales as $D\sim(d_{\rm code})^{1/d_{\rm lattice}}$ where $d_{\rm lattice}$ is the spatial dimension.

Proof.

We prove each part rigorously using the Knill-Laflamme error correction conditions.

Part (a): Support-Based Triviality.

Step 1: Pauli decomposition. Any operator $U$ on $n$ qubits can be decomposed in the Pauli basis:

U=\sum_{P\in\mathcal{P}_{n}}c_{P}\,P

where $\mathcal{P}_{n}=\{I,X,Y,Z\}^{\otimes n}$ is the $n$ -qubit Pauli group.

Step 2: Support constraint. If $|\mathrm{supp}(U)|=\ell$ , then all Pauli strings $P$ with $c_{P}\neq 0$ satisfy $\mathrm{wt}(P)\leq\ell$ .

Step 3: Knill-Laflamme conditions. For a code with distance $d$ , the Knill-Laflamme conditions [KL97] state: for any operator $E$ with $\mathrm{wt}(E)<d$ ,

\langle\psi_{i}|E|\psi_{j}\rangle=c_{E}\delta_{ij}

for all code basis states $|\psi_{i}\rangle,|\psi_{j}\rangle$ and some constant $c_{E}\in\mathbb{C}$ .

Step 4: Application to $U$ . Since $\ell<d/2<d$ , every Pauli string $P$ in the decomposition of $U$ satisfies $\mathrm{wt}(P)\leq\ell<d$ . By Knill-Laflamme:

P_{\rm code}PP_{\rm code}=c_{P}^{\prime}\,P_{\rm code}

for each such $P$ . Summing:

P_{\rm code}UP_{\rm code}=\sum_{P}c_{P}\cdot c_{P}^{\prime}\,P_{\rm code}=% \left(\sum_{P}c_{P}c_{P}^{\prime}\right)P_{\rm code}

Step 5: Unitarity determines phase. Since $U$ is unitary, $P_{\rm code}UP_{\rm code}$ must also be proportional to a unitary on the code subspace. The only unitary proportional to the identity is $e^{i\phi}\mathrm{Id}$ for some $\phi\in\mathbb{R}$ .

Part (b): Circuit Depth Bound on Support.

We prove the support bound using the lightcone containment principle.

Step 1: Graph distance in lattices. For a $d$ -dimensional hypercubic lattice $\mathbb{Z}^{d}$ , the graph distance between sites $u,v\in\mathbb{Z}^{d}$ equals the $L^{1}$ (taxicab) distance:

d_{\text{graph}}(u,v)=\|u-v\|_{1}=\sum_{i=1}^{d}|u_{i}-v_{i}|

A single nearest-neighbor gate couples sites at graph distance 1. A $k$ -local gate can couple sites at graph distance up to $k-1$ .

Step 2: Lightcone definition. Define the depth- $D$ lightcone from an initial set $S_{0}$ as:

\mathcal{L}_{D}(S_{0})=\{v\in\mathbb{Z}^{d}:d_{\text{graph}}(v,S_{0})\leq(k-1)D\}

where $d_{\text{graph}}(v,S_{0})=\min_{u\in S_{0}}d_{\text{graph}}(v,u)$ .

Step 3: Lightcone containment. Claim: For any depth- $D$ circuit $U$ with $k$ -local gates initially acting on $S_{0}$ :

\mathrm{supp}(U)\subseteq\mathcal{L}_{D}(S_{0})

Proof by induction:

Base case ( $D=0$ ): The identity has $\mathrm{supp}(\mathrm{Id})=S_{0}\subseteq\mathcal{L}_{0}(S_{0})$ .
Inductive step: Assume $\mathrm{supp}(U_{D})\subseteq\mathcal{L}_{D}(S_{0})$ . Adding one layer of $k$ -local gates can extend the support to sites within graph distance $(k-1)$ of the current support. Since

$\{v:d_{\text{graph}}(v,\mathrm{supp}(U_{D}))\leq k-1\}\subseteq\{v:d_{\text{% graph}}(v,S_{0})\leq(k-1)(D+1)\}=\mathcal{L}_{D+1}(S_{0})$

we have $\mathrm{supp}(U_{D+1})\subseteq\mathcal{L}_{D+1}(S_{0})$ .

Step 4: Volume bound. The size of the lightcone is bounded by the $L^{1}$ ball volume:

|\mathcal{L}_{D}(S_{0})|\leq V_{d}((k-1)D)+\ell_{0}-1

where $V_{d}(R)=|\{v\in\mathbb{Z}^{d}:\|v\|_{1}\leq R\}|$ is the volume of the discrete $L^{1}$ ball.

Step 5: Explicit volume formulas. The $L^{1}$ ball volume in $d$ dimensions is (see e.g., [STA97]):

$\displaystyle V_{1}(R)$	$\displaystyle=2R+1$	(1)
$\displaystyle V_{2}(R)$	$\displaystyle=2R^{2}+2R+1$	(2)
$\displaystyle V_{3}(R)$	$\displaystyle=\frac{4}{3}R^{3}+2R^{2}+\frac{8}{3}R+1$	(3)
$\displaystyle V_{d}(R)$	$\displaystyle=\sum_{j=0}^{\min(R,d)}\binom{d}{j}\binom{R}{j}2^{j}=\frac{(2R)^{% d}}{d!}+O(R^{d-1})$	(4)

Step 6: Conclusion. Therefore:

|\mathrm{supp}(U)|\leq V_{d}((k-1)D)+\ell_{0}-1

For 1D lattices: $|\mathrm{supp}(U)|\leq 2(k-1)D+\ell_{0}$ (linear in $D$ ).

For 2D lattices: $|\mathrm{supp}(U)|\leq 2(k-1)^{2}D^{2}+2(k-1)D+\ell_{0}=O(D^{2})$ (quadratic).

For 3D lattices: $|\mathrm{supp}(U)|=O(D^{3})$ (cubic).

This completes the proof. ∎

Geometry	$k$	$z$	Support bound	Growth
1D chain, nearest-neighbor	2	2	$\ell\leq\ell_{0}+2D$	$O(D)$
2D square, nearest-neighbor	2	4	$\ell\leq\ell_{0}+2D^{2}+2D$	$O(D^{2})$
3D cubic, nearest-neighbor	2	6	$\ell\leq\ell_{0}+\frac{4}{3}D^{3}+O(D^{2})$	$O(D^{3})$
All-to-all connectivity	2	$n$	$\ell\leq\min(n,\ell_{0}+2D)$	$O(D)$

Table 1: Support bounds for different lattice geometries with 2-local gates. The growth rate depends on lattice dimension:

O(D^{d_{\rm lattice}})

.

Remark 1 (Lieb-Robinson Bounds vs. Circuit Depth).

The Lieb-Robinson bound [LR72] constrains information spreading under continuous Hamiltonian evolution:

\|[A(x,0),B(y,t)]\|\leq Ce^{-\mu(r-v_{\text{LR}}t)}

where $v_{\text{LR}}=2ez\|J\|_{\infty}/\hbar$ is the Lieb-Robinson velocity.

Important distinction: This bound applies to time evolution $e^{-iHt}$ , not to discrete gate circuits. For circuits, support grows linearly with depth (Theorem 1(b)), which is generally tighter than the Lieb-Robinson bound.

The Lieb-Robinson velocity becomes relevant when approximating Hamiltonian evolution by Trotterization: if $e^{-iHt}$ is approximated by a depth- $D$ circuit, then $D\approx v_{\text{LR}}t/a$ where $a$ is lattice spacing. This connects the two bounds but they are not equivalent.

4 Explicit Example: The [[5,1,3]] Perfect Code

We now demonstrate the theorem with a complete worked example, providing numerical values for all quantities.

4.1 Code Parameters

Consider the [[5,1,3]] perfect quantum code [GOT96, Laflamme1996], which encodes $k=1$ logical qubit into $n=5$ physical qubits with distance $d=3$ . This code has the following properties:

Physical Hilbert space: $\mathcal{H}_{\rm phys}=(\mathbb{C}^{2})^{\otimes 5}$ , $\dim=32$
Code subspace: $\mathcal{H}_{\rm code}=\mathbb{C}^{2}$ , $\dim=2$
Distance: $d=3$ (corrects any single-qubit error)
Stabilizers: Four independent generators, each weight-4 Pauli operators
Locality threshold: $\ell_{c}=d/2=1.5$ (operations on $\ell\leq 1$ qubits are trivial)

The encoding circuit requires 7 two-qubit gates and can be implemented with depth $D=5$ on a linear qubit array [NC00].

4.2 Single-Qubit Operations ( $\ell=1<d/2$ )

Support analysis: For a single-qubit operation $U=R_{z}(\theta)\otimes I^{\otimes 4}$ acting on qubit 1:

$\displaystyle\ell$	$\displaystyle=\|\mathrm{supp}(U)\|=1$	(5)
$\displaystyle\dim\mathcal{H}_{\rm phys}(1)$	$\displaystyle=2$	(6)
$\displaystyle\log_{2}\dim\mathcal{H}_{\rm phys}(1)$	$\displaystyle=1\text{ bit}$	(7)

Verification via Knill-Laflamme conditions: Since $\ell=1<d/2=1.5$ , Theorem 1(a) guarantees:

P_{\rm code}\,R_{z}(\theta)\otimes I^{\otimes 4}\,P_{\rm code}=e^{i\phi}P_{\rm code}

for some phase $\phi$ . The operation is logically trivial regardless of rotation angle $\theta$ .

Indeed, by stabilizer formalism, any single-qubit Pauli or Clifford operation either commutes with all stabilizers (trivial) or can be absorbed into stabilizer measurements [GOT97].

4.3 Two-Qubit Operations ( $\ell=2\geq d/2$ )

At the threshold: For a two-qubit operation $U=\text{CNOT}_{12}\otimes I^{\otimes 3}$ :

$\displaystyle\ell$	$\displaystyle=2=d/2\quad(\text{exactly at threshold})$	(8)
$\displaystyle\dim\mathcal{H}_{\rm phys}(2)$	$\displaystyle=4$	(9)
$\displaystyle\log_{2}\dim\mathcal{H}_{\rm phys}(2)$	$\displaystyle=2\text{ bits}$	(10)

Since $\ell=2=d/2$ , we are exactly at the locality threshold. Operations with $\ell\geq d/2$ can implement non-trivial logical gates. Indeed, two-qubit operators on the [[5,1,3]] code can realize logical Paulis: applying CNOTs between specific qubit pairs implements logical gates [NC00].

4.4 Circuit Depth Threshold

Threshold calculation: For the [[5,1,3]] code on a 1D chain with 2-local gates:

Code distance: $d=3$
Coordination number: $z=2$ (1D chain)
Locality parameter: $k=2$ (nearest-neighbor gates)
Initial support: $\ell_{0}=1$ (starting on one qubit)

The circuit depth threshold from Theorem 1 corollary:

D<\frac{d/2-\ell_{0}}{(k-1)z}=\frac{1.5-1}{(2-1)\cdot 2}=\frac{0.5}{2}=0.25

Therefore, any operation with depth $D<0.25$ (i.e., $D=0$ ) starting from a single qubit remains logically trivial. Depth $D\geq 1$ can potentially reach $\ell=3$ qubits, exceeding the threshold $d/2=1.5$ , enabling non-trivial logical operations.

Scaling with code distance: Larger codes allow deeper circuits before non-triviality:

$\displaystyle d=5:\quad D_{\text{crit}}$	$\displaystyle=\frac{2.5-1}{2}=0.75\quad(\text{depth }0\text{ is trivial})$	(11)
$\displaystyle d=7:\quad D_{\text{crit}}$	$\displaystyle=\frac{3.5-1}{2}=1.25\quad(\text{depth }0\text{-}1\text{ trivial})$	(12)
$\displaystyle d=11:\quad D_{\text{crit}}$	$\displaystyle=\frac{5.5-1}{2}=2.25\quad(\text{depth }0\text{-}2\text{ trivial})$	(13)

5 Experimental Protocols

We provide concrete protocols for testing Theorem 1 in quantum computing platforms. These protocols are designed to verify the circuit depth threshold from the theorem’s corollary.

5.1 Falsification Criteria

For Theorem 1 to be experimentally validated, explicit numerical thresholds must be met. We provide success/failure criteria at the 95% confidence level:

Ion Trap ([[5,1,3]] code):

Strong confirmation: If measured triviality probability $\mathcal{F}>0.95$ for circuits with $D<D_{\rm crit}$ across all tested codes, the theorem is supported (single-qubit operations with $\ell=1<d/2=1.5$ maintain logical fidelity).
Weak confirmation: If $0.75<\mathcal{F}<0.95$ , the theorem is partially supported (possible finite-size effects or experimental imperfections).
Falsification: If $\mathcal{F}<0.50$ for $D<D_{\rm crit}$ , the theorem is falsified (circuit is non-trivial despite depth threshold).
Threshold sharpness: Sharp transition in logical error rate at support $\ell\approx d/2$ with width $\Delta\ell<1.5$ qubits. If transition width $\Delta\ell>2$ qubits, threshold behavior is not sharp as predicted.

Surface Code ( $d=5$ , $n=49$ ):

Success: Logical error rate fits $p_{L}(\ell)\propto\exp(-\beta(d/2-\ell))$ for $\ell<d/2$ with fitted parameter $\beta>0.3$ and fit quality $R^{2}>0.85$ .
Partial success: If $0.15<\beta<0.3$ or $0.70<R^{2}<0.85$ , the exponential threshold exists but is weaker than predicted (possible finite-size or noise effects).
Falsification: If fit quality $R^{2}<0.70$ or fitted $\beta<0.15$ (two standard deviations below predicted value), the threshold behavior is not observed and the theorem is falsified.
Support bound test: Measured support growth $\ell_{\text{obs}}(D)\leq\ell_{0}+(k-1)zD+\Delta$ with tolerance $\Delta<2$ qubits. If $\Delta>3$ qubits systematically, the bound is violated.

Numerical Simulation:

Success: Phase boundary in $(D,\ell_{0})$ space matches theoretical prediction $D=(d/2-\ell_{0})/((k-1)z)$ within 10% (allowing for discretization effects).
Falsification: If measured critical depth $D_{c}$ differs from theory by more than 20%, or if triviality persists for $\ell>1.2\cdot(d/2)$ , the distance threshold is violated.

Statistical justification: These thresholds are chosen to separate signal from noise at the 95% confidence level, allowing for experimental imperfections (gate errors, measurement errors, finite sampling) while maintaining statistical rigor. The threshold values ( $\mathcal{F}>0.95$ , $\beta>0.3$ , $R^{2}>0.85$ ) correspond to effect sizes detectable with $\sim 100$ -1000 experimental runs per configuration.

5.2 Ion Trap Implementation

System: 5-ion linear chain (e.g., ¹⁷¹Yb⁺ or ⁴⁰Ca⁺) implementing the [[5,1,3]] code.

Preparation Phase:

Initialize all ions in $|0\rangle$ via optical pumping
Apply encoding circuit (7 two-qubit gates, depth $D=5$ ) to prepare logical $|\bar{0}\rangle$
Verify encoding via stabilizer measurements (Z-type and X-type)
Measure encoding fidelity: target $\mathcal{F}>99\%$

Test Phase:

Apply single-ion rotation: $R_{z}(\theta)$ on ion 1, sweep $\theta\in[0,2\pi]$
Measure all four stabilizers: $S_{1},S_{2},S_{3},S_{4}$
Verify stabilizer outcomes: all should remain $+1$ (eigenvalue unchanged)
Decode to logical basis and measure logical state: should remain $|\bar{0}\rangle$
Repeat for ions 2-5 to verify position independence

Threshold Test:

Apply two-ion Mølmer-Sørensen gate: $U=e^{i\phi(\sigma_{x}^{(1)}\sigma_{x}^{(2)}+\sigma_{y}^{(1)}\sigma_{y}^{(2)})}$
Sweep interaction angle $\phi\in[0,\pi/2]$
For $\phi<\phi_{c}$ : expect logical state unchanged (below threshold)
For $\phi\geq\phi_{c}$ : expect logical rotation (above threshold)
Determine critical angle $\phi_{c}$ from transition point

Expected Results:

Single-ion operations: fidelity $\mathcal{F}(|\bar{0}\rangle)>99.9\%$ for all $\theta$ (logically trivial as $\ell=1<d/2$ )
Two-ion operations: sharp transition at $\phi_{c}$ with width $\Delta\phi\sim 1/\sqrt{d}\approx 0.58$
Threshold consistent with $\ell=d/2=1.5$ for non-triviality

5.3 Superconducting Qubit Implementation

System: Surface code on 2D grid (e.g., Google Sycamore or IBM Quantum) with distance $d=5$ .

Code Parameters:

Physical qubits: $n=49$ (7 $\times$ 7 grid)
Logical qubits: $k=1$
Distance: $d=5$ (corrects 2-qubit errors)
Threshold: $\ell_{c}=2.5$ (3-qubit operations can be non-trivial)

Protocol:

Prepare logical $|\bar{0}\rangle$ using standard surface code encoding
Apply operations on $\ell=1,2,3$ qubits within a connected patch
Measure syndrome via ancilla readout (stabilizer measurements)
Track logical error rate $p_{L}$ vs. support size $\ell$
Fit to theory: $p_{L}\sim\exp(-\beta(d/2-\ell))$ for $\ell<d/2$

Circuit Depth Measurement:

Count gate depth $D$ for each test operation
Verify support bound: $\ell\leq\ell_{0}+(k-1)zD$ with $z=4$ (2D square lattice)
Plot $p_{L}$ vs. support size $\ell$ to verify threshold $\ell_{c}=d/2$
Confirm sharp transition at threshold

5.4 Numerical Simulation

For verification and parameter exploration beyond current experimental capabilities:

Stabilizer Simulator:

Use Stim [GID21] or Qiskit Aer to simulate codes up to $n=100$ qubits
Implement [[n,k,d]] CSS codes with varying distance $d\in[3,15]$
Apply random circuits with controlled support $\ell\in[1,d]$
Measure logical fidelity vs. $\ell$ and extract transition point

Parameter Sweep:

Fix code distance $d$
Sweep circuit depth $D\in[1,50]$ and initial support $\ell_{0}\in[1,d/2]$
Compute final support $\ell=\ell_{0}+(k-1)zD$ for each configuration
Classify as logically trivial ( $\ell<d/2$ ) or non-trivial ( $\ell\geq d/2$ ) via Knill-Laflamme check
Plot phase diagram in $(D,\ell_{0})$ space
Verify boundary matches threshold $D=(d/2-\ell_{0})/((k-1)z)$

Support Growth Verification:

Apply random circuits with varying depth $D$ on different lattices
Track actual support size vs. theoretical bound $\ell\leq\ell_{0}+(k-1)zD$
Verify bound is tight for worst-case circuit configurations
Compare 1D, 2D, and 3D lattice geometries

6 Discussion and Implications

6.1 Proven Results

6.1.1 Comparison with Lieb-Robinson Bounds

Both our complexity threshold (Theorem 1) and the Lieb-Robinson bound [LR72] limit locality, but their nature differs fundamentally:

Lieb-Robinson (dynamical):

Bounds time evolution of operators: $\|[A(x,t),B(y,0)]\|\leq Ce^{-\mu(r-v_{\text{LR}}t)}$
Applies to any local Hamiltonian evolution
Constrains how fast information spreads through space
Velocity $v_{\text{LR}}$ determined by Hamiltonian parameters

Circuit Depth Threshold (operational):

Bounds operations an observer can implement: $D<(d/2-\ell_{0})/((k-1)z)\Rightarrow$ logically trivial
Applies to observers with finite circuit depth
Constrains what logical transformations are accessible
Threshold determined by code distance $d$ , lattice coordination $z$ , and gate locality $k$

The Lieb-Robinson velocity does not appear in our main theorem. It relates continuous Hamiltonian evolution to circuit implementations, but Theorem 1 is purely about discrete circuits. Our bound is not about dynamical spreading—it’s about the detectability of operations within error-correcting codes.

6.2 Conjectured Extensions

6.2.1 Conjectured Holographic Connection (Speculative)

Caveat: The following connection to holographic spacetimes is highly speculative and requires substantial independent justification beyond the scope of this work. We present it as a potential application, not as a proven consequence of Theorem 1.

In the AdS/CFT correspondence [MAL98], the boundary theory may implement a quantum error-correcting code that encodes bulk physics [ADH15, PYH+15]. If this holographic error correction conjecture holds, our result would suggest connections to bulk locality:

Conjectured boundary-bulk connection: If the boundary code has distance $d$ related to bulk geodesic distance, then boundary operators with support $\ell<d/2$ cannot probe bulk physics—they would act trivially on the logical (bulk) subspace. This would provide an operational definition of ”local” on the boundary consistent with entanglement wedge reconstruction [ADH15].

Future investigation required: Testing this connection requires:

Verifying that holographic codes satisfy the distance-support relationship (Theorem 1)
Establishing whether the code distance $d$ in AdS/CFT scales with appropriate geometric quantities
Determining the relationship (if any) between circuit depth and bulk complexity growth [SUS16]

These are open questions beyond the scope of this paper. Our contribution is the QEC result (Theorem 1); holographic applications remain speculative.

6.2.2 Implications for Quantum Complexity Theory

Circuit lower bounds: Theorem 1 provides a method for proving circuit lower bounds via error correction. If a unitary $U$ acts non-trivially on a code with distance $d$ , then the support must satisfy $\ell\geq d/2$ , which implies circuit depth $D\geq(d/2-\ell_{0})/((k-1)z)$ . This connects code distance to circuit depth, potentially useful for quantum advantage arguments.

Fault-tolerant computation: The threshold $\ell<d/2$ is precisely the condition for fault tolerance [GOT97]. Our circuit depth formulation rephrases this in terms of observer resources: operations are fault-tolerant (logically trivial) when circuit depth is below $(d/2-\ell_{0})/((k-1)z)$ . This suggests fault tolerance emerges from bounded circuit depth rather than being imposed as an external condition.

Resource theory interpretation: Circuit depth $D$ can be viewed as a resource in quantum resource theory [CG19]. Operations below the threshold are ”free” (logically trivial), while those above are ”costly” (require depth beyond error correction capacity). The threshold structure defines a depth-based resource theory with explicit conversion rates.

6.3 Future Work

Several directions remain for investigation:

Time-dependent evolution: We have focused on static circuits. How does the bound extend to continuous Hamiltonian evolution via Trotterization? The connection between continuous time $t$ and discrete depth $D$ requires careful analysis of Trotter errors and their impact on the support bound.

Tighter bounds for specific geometries: The support bound $\ell\leq\ell_{0}+(k-1)zD$ is a worst-case estimate. For specific lattice geometries and circuit structures, tighter bounds may exist. For example, 1D chains have exact bounds, while 2D lattices may allow for geometric optimizations.

Non-Abelian codes: Our proof uses stabilizer formalism (Abelian codes). Can the result extend to non-Abelian quantum codes (e.g., twisted codes, subsystem codes)? The definition of code distance generalizes, but whether the threshold $\ell<d/2$ persists requires investigation.

Experimental verification: While we have provided detailed protocols (Section 5), actual implementation on NISQ devices will test the theory. Measuring $\alpha$ empirically and comparing with theoretical predictions $\alpha=1/(d\cdot v_{\text{LR}})$ would provide strong validation.

Gravity connection: In quantum gravity, locality is emergent [SUS16]. Does our threshold play a role in deriving Einstein’s equations from entanglement [JAC95]? The connection between error correction and geometry [PYH+15] suggests our complexity bound might constrain gravitational dynamics.

6.4 Summary

We have established a quantitative relationship (Theorem 1) between circuit depth, quantum error correction, and logical triviality. The main results are:

Circuit depth threshold: $D<\frac{d/2-\ell_{0}}{(k-1)z}\Longrightarrow U|_{\mathcal{H}_{\rm code}}% \propto\mathrm{Id}$ for codes with distance $d$
Support growth bound: $|\mathrm{supp}(U)|\leq\ell_{0}+(k-1)zD$ for depth- $D$ circuits with $k$ -local gates
Worked example: [[5,1,3]] code with explicit numerical thresholds
Experimental protocols: Ion trap, superconducting, and simulation tests with falsifiability criteria
Conjectured holographic connection: Potential operational definition of locality in AdS/CFT (requires further investigation)

The result combines standard Knill-Laflamme conditions with circuit growth analysis. It provides a falsifiable, task-independent criterion for when circuit-based operations preserve encoded quantum information.

Acknowledgments

Mathematical formalism developed with AI assistance (Claude, Anthropic). The author takes full responsibility for all scientific claims.

Data and Code Availability

Computational validation code and experimental data are archived at DOI:10.5281/zenodo.17727423.

ORCID

Oksana Sudoma: 0009-0009-8469-1382

References

[ADH15] A. Almheiri, X. Dong, and D. Harlow (2015) Bulk locality and quantum error correction in ads/cft. JHEP 04, pp. 163. External Links: Document, 1411.7041 Cited by: §1, §6.2.1, §6.2.1.
[BRS+16] A. R. Brown, D. A. Roberts, L. Susskind, B. Swingle, and Y. Zhao (2016) Holographic complexity equals bulk action?. Phys. Rev. Lett. 116, pp. 191301. External Links: Document, 1509.07876 Cited by: §2.2.
[CG19] E. Chitambar and G. Gour (2019) Quantum resource theories. Rev. Mod. Phys. 91 (2), pp. 025001. External Links: 1806.06107 Cited by: §6.2.2.
[GID21] C. Gidney (2021) Stim: a fast stabilizer circuit simulator. External Links: 2103.02202 Cited by: 1st item.
[GOT96] D. Gottesman (1996) Class of quantum error-correcting codes saturating the quantum hamming bound. Phys. Rev. A 54, pp. 1862–1868. External Links: Document, quant-ph/9604038 Cited by: §4.1.
[GOT97] D. Gottesman (1997) Stabilizer codes and quantum error correction. Ph.D. Thesis, California Institute of Technology. External Links: quant-ph/9705052 Cited by: §1, §2.1, §4.2, §6.2.2.
[JAC95] T. Jacobson (1995) Thermodynamics of spacetime: the einstein equation of state. Phys. Rev. Lett. 75 (7), pp. 1260. External Links: gr-qc/9504004 Cited by: §6.3.
[KL97] E. Knill and R. Laflamme (1997) Theory of quantum error-correcting codes. Phys. Rev. A 55, pp. 900–911. External Links: Document, quant-ph/9604034 Cited by: §1, §2.1, §3, §3.
[KOL14] D. A. Kolb (2014) Experiential learning: experience as the source of learning and development. FT press. Cited by: §1.
[LR72] E. H. Lieb and D. W. Robinson (1972) The finite group velocity of quantum spin systems. Commun. Math. Phys. 28, pp. 251–257. External Links: Document Cited by: §1, §6.1.1, Remark 1.
[MAL98] J. Maldacena (1998) The large n limit of superconformal field theories and supergravity. Adv. Theor. Math. Phys. 2, pp. 231–252. External Links: Document, hep-th/9711200 Cited by: §6.2.1.
[NC00] M. A. Nielsen and I. L. Chuang (2000) Quantum computation and quantum information. Cambridge University Press. Note: 10th Anniversary Edition, 2010 External Links: ISBN 978-1107002173 Cited by: §2.2, §4.1, §4.3.
[PYH+15] F. Pastawski, B. Yoshida, D. Harlow, and J. Preskill (2015) Holographic quantum error-correcting codes: toy models for the bulk/boundary correspondence. JHEP 06, pp. 149. External Links: Document, 1503.06237 Cited by: §1, §6.2.1, §6.3.
[STA97] R. P. Stanley (1997) Enumerative combinatorics. Vol. 1, Cambridge University Press. Note: L1 ball volume formulas Cited by: §3, §3.
[SUS16] L. Susskind (2016) Computational complexity and black hole horizons. Fortschritte der Physik 64, pp. 24–43. Note: Submitted 2014 External Links: Document, 1402.5674 Cited by: §2.2, 3rd item, §6.3.

[bib.bib4] [ADH15] A. Almheiri, X. Dong, and D. Harlow (2015) Bulk locality and quantum error correction in ads/cft. JHEP 04, pp. 163. External Links: Document, 1411.7041 Cited by: §1, §6.2.1, §6.2.1.

[bib.bib7] [BRS+16] A. R. Brown, D. A. Roberts, L. Susskind, B. Swingle, and Y. Zhao (2016) Holographic complexity equals bulk action?. Phys. Rev. Lett. 116, pp. 191301. External Links: Document, 1509.07876 Cited by: §2.2.

[bib.bib24] [CG19] E. Chitambar and G. Gour (2019) Quantum resource theories. Rev. Mod. Phys. 91 (2), pp. 025001. External Links: 1806.06107 Cited by: §6.2.2.

[bib.bib26] [GID21] C. Gidney (2021) Stim: a fast stabilizer circuit simulator. External Links: 2103.02202 Cited by: 1st item.

[bib.bib1] [GOT96] D. Gottesman (1996) Class of quantum error-correcting codes saturating the quantum hamming bound. Phys. Rev. A 54, pp. 1862–1868. External Links: Document, quant-ph/9604038 Cited by: §4.1.

[bib.bib2] [GOT97] D. Gottesman (1997) Stabilizer codes and quantum error correction. Ph.D. Thesis, California Institute of Technology. External Links: quant-ph/9705052 Cited by: §1, §2.1, §4.2, §6.2.2.

[bib.bib28] [JAC95] T. Jacobson (1995) Thermodynamics of spacetime: the einstein equation of state. Phys. Rev. Lett. 75 (7), pp. 1260. External Links: gr-qc/9504004 Cited by: §6.3.

[bib.bib3] [KL97] E. Knill and R. Laflamme (1997) Theory of quantum error-correcting codes. Phys. Rev. A 55, pp. 900–911. External Links: Document, quant-ph/9604034 Cited by: §1, §2.1, §3, §3.

[bib.bib27] [KOL14] D. A. Kolb (2014) Experiential learning: experience as the source of learning and development. FT press. Cited by: §1.

[bib.bib8] [LR72] E. H. Lieb and D. W. Robinson (1972) The finite group velocity of quantum spin systems. Commun. Math. Phys. 28, pp. 251–257. External Links: Document Cited by: §1, §6.1.1, Remark 1.

[bib.bib10] [MAL98] J. Maldacena (1998) The large n limit of superconformal field theories and supergravity. Adv. Theor. Math. Phys. 2, pp. 231–252. External Links: Document, hep-th/9711200 Cited by: §6.2.1.

[bib.bib14] [NC00] M. A. Nielsen and I. L. Chuang (2000) Quantum computation and quantum information. Cambridge University Press. Note: 10th Anniversary Edition, 2010 External Links: ISBN 978-1107002173 Cited by: §2.2, §4.1, §4.3.

[bib.bib5] [PYH+15] F. Pastawski, B. Yoshida, D. Harlow, and J. Preskill (2015) Holographic quantum error-correcting codes: toy models for the bulk/boundary correspondence. JHEP 06, pp. 149. External Links: Document, 1503.06237 Cited by: §1, §6.2.1, §6.3.

[bib.bib39] [STA97] R. P. Stanley (1997) Enumerative combinatorics. Vol. 1, Cambridge University Press. Note: L1 ball volume formulas Cited by: §3, §3.

[bib.bib6] [SUS16] L. Susskind (2016) Computational complexity and black hole horizons. Fortschritte der Physik 64, pp. 24–43. Note: Submitted 2014 External Links: Document, 1402.5674 Cited by: §2.2, 3rd item, §6.3.

Abstract

1 Introduction

Concrete Experience: The observer’s dilemma.

From code distance to circuit depth bounds.

Scope and limitations.

Potential holographic connections.

Comparison with Lieb-Robinson bounds.

Structure of the paper.

2 Definitions and Mathematical Setup

2.1 Code Distance and Error Correction

Definition 1 (Weight Function).

Definition 2 (Code Distance).

2.2 Locality and Algorithmic Complexity

Definition 3 (Logically Trivial Operation).

Definition 4 (Support and Locality).

Definition 5 (Circuit Complexity).

3 Main Result: Complexity-Bounded Locality

Lemma 1 (Knill-Laflamme Projection).

Proof.

Lemma 2 (L1 Ball Volume).

Proof.

Theorem 1 (Locality from Code Distance).

Proof.

Remark 1 (Lieb-Robinson Bounds vs. Circuit Depth).

4 Explicit Example: The [[5,1,3]] Perfect Code

4.1 Code Parameters

4.2 Single-Qubit Operations (ℓ=1<d/2)

4.3 Two-Qubit Operations (ℓ=2≥d/2)

4.4 Circuit Depth Threshold

5 Experimental Protocols

5.1 Falsification Criteria

5.2 Ion Trap Implementation

5.3 Superconducting Qubit Implementation

5.4 Numerical Simulation

6 Discussion and Implications

6.1 Proven Results

6.1.1 Comparison with Lieb-Robinson Bounds

6.2 Conjectured Extensions

6.2.1 Conjectured Holographic Connection (Speculative)

6.2.2 Implications for Quantum Complexity Theory

6.3 Future Work

6.4 Summary

Acknowledgments

Data and Code Availability

ORCID

References

Lemma 2 ( $L^{1}$ Ball Volume).

4.2 Single-Qubit Operations ( $\ell=1<d/2$ )

4.3 Two-Qubit Operations ( $\ell=2\geq d/2$ )