Computational Bounds for $f$-Routing

1 Introduction

• The protocol routes an unknown quantum challenge to Vf(x,y), while classical copy-and-forward attacks and sufficiently entangled non-local quantum computation motivate the security problem [Vai03] [BK11] [BCF+14].An explicit function with superlogarithmic-entanglement security remains open: almost all Boolean functions provide security at n-qubit storage, but typically require exponentially large evaluation circuits.Source: §1 · pp. 2, 4

1.1 Main Results

• A uniformly generated strategy that succeeds on every input with sufficiently small error implies f ∈ QSZK(poly(nq)) for arbitrary quantum channels, and deterministic-time bounds for restricted strategies.The reduction turns f(x, y) into an instance of the complement of Quantum State Distinguishability, which is complete for QSZK [Wat02] [Wat09].Source: §1.1 · pp. 4–5

1.2 Explicit Security

• For arbitrary channels, the work gives unconditional security against polynomially many adversary qubits by allowing higher honest evaluation space; restricted models permit faster honest evaluation.Polynomial Pauli sparsity or logarithmically many T gates allows polynomial honest time, whereas larger sparsity and T-gate budgets in Table 1 allow quasipolynomial honest time.Source: §1.1 · p. 5, §1.2 · p. 7

1.1 Main Results

• Explicit Pauli-sparse strategies imply f ∈ DTIME(poly(nqs)), while Clifford+T strategies with t magic gates imply f ∈ DTIME(poly(nq2^t)).The corresponding time-hierarchy corollaries give explicit functions secure against these restricted strategies.Source: §1.1 · pp. 5–6
• The reduction uses mid-protocol fidelity: successful routing leaves the reference nearly uncorrelated with the unintended recipient and correlated with the intended recipient.For sufficiently small error, approximating F0(x, y) to small constant additive error determines f(x, y); the characterization extends [ACM25] to nonzero error on both output values.Source: §1.1 · p. 6

1.2 Explicit Security

• Pauli sparsity limits shared entanglement to O(log s) ebits, but the Clifford+T magic-gate count t alone does not restrict the number of shared ebits.An s-term Pauli expansion has Schmidt rank at most s, while e shared EPR pairs require s ≥ 2^e; e ebits can also be prepared using Clifford gates alone.Source: §1.2 · p. 7

1.3 Discussion

• The fidelity-gap reduction avoids the linear communication-complexity ceiling that constrained earlier lower-bound approaches [BCS22] [ACCM25].For non-explicit uniform Pauli-sparse strategies, the reduction yields f ∈ BQTIME(T), but a uniform quantum time hierarchy with polynomial overhead is unknown.Source: §1.3 · p. 7
• A possible extension of He’s advice-to-promise technique to quantum computation would yield a polynomial-time bounded-error quantum routing function that defeats admissible strategies on all promised inputs.The function may return ⊥ outside the promise; the stated implication is conditional on that technique generalizing to quantum computation and yielding a polynomial time hierarchy for prBQTIME.Source: §1.3 · p. 8
• The results permit security against everywhere-correct strategies with q = 2^O(n) qudits under suitable bounds on circuit size, description length, and uniform generation time.This is compatible with the universal attack from the CDS reduction of [ABM+24, Corollary 68], which uses 2^O(sqrt(n) log n) resource qubits via CDS protocols.Source: §1.3 · p. 8
• The CDS-to-INDEX bound permits unrestricted local computation, while direct evaluation of its message formulas takes 2^n evaluations of f, a cost charged in this model.The reduction uses the truth table Dy = (f(z, y)) for z in {0,1}^n [ABM+24, Section 6.3], and the formulas are from [LVW17, Figure 5].Source: §1.3 · p. 8
• The approach directly relates the mid-protocol state to computing f(x, y), yielding computational bounds and algorithms for explicit Pauli-sparse and (q, t)-uniform Clifford+T strategies.Allerstorfer et al. [ABM+24, Theorem 23] established an equivalence between qudit f-routing and CDQS; the paper identifies a quantity that determines f(x, y) and bounds its computation using adversaries’ success parameters.Source: §1.3 · p. 8
• The QSZK(T) statements are not directly comparable to [AKL+25], whose proof and simulation communication costs do not bound local computation time.The paper’s time-bounded statements account for uniform circuit generation and resource-state preparation.Source: §1.3 · p. 8

2 Proof Overview

• The pre-communication circuits prepare the midpoint state without computing f(x, y), allowing the fidelity test to distinguish the two possible routing outcomes.The adversaries’ local channels and register partitions depend only on their respective inputs.Source: §2 · p. 9
• A constant gap between midpoint fidelities F0 and F1 determines f(x, y), reducing its computation to estimating state fidelity.The quantities measure how close each adversary’s joint state with the reference is to a product of its marginals; the intended recipient retains the reference entanglement.Source: §2 · p. 9

2.1 Fidelity Bounds

• Successful recovery by one adversary forces the other’s joint state with the reference to be approximately a product state.The proof uses the purity of the EPR pair, the decoder, and Uhlmann’s theorem to establish this decoupling.Source: §2.1 · pp. 9–11

2.2 Faster Algorithms for Computationally Bounded Adversaries

• For arbitrary channels, estimating the midpoint fidelity gives a QSZK protocol with verifier time polynomial in the strategy’s resources and circuit-generation time.The states can be prepared from the resource-preparation and pre-communication circuits with polynomial overhead.Source: §2.2 · p. 11
• For general computationally bounded adversaries, the paper exploits circuit structure to reduce fidelity estimation to a small matrix and derive time bounds for computing f.The resulting algorithms support security for functions requiring more time than the corresponding successful strategies allow.Source: §2.2 · p. 11
• Clifford+T strategies with at most t magic gates reduce fidelity estimation to a logical state of O(t) qubits, giving deterministic time poly(2^t, q).The method separates fixed factors while preserving the Schmidt coefficients needed for the fidelity.Source: §2.2 · pp. 11–12
• The Clifford+T reduction uses stabilizer decompositions and nullity bounds to isolate the small logical state and compute its amplitudes.The decomposition has at most 2^t stabilizer terms, while the nullity is at most t.Source: §2.2 · pp. 11–12
• Pauli-sparse unitaries reduce the fidelity calculation to singular values of an at-most-s-by-s matrix, computable in time poly(q, s).When sparse descriptions are not supplied, quantum learning identifies significant Pauli coefficients before the same computation.Source: §2.2 · p. 13

3.1 Quantum Information

• Fidelity is nondecreasing under quantum channels, and its angle obeys a triangle inequality.These facts support comparisons between states before and after decoding.Source: §3.1 · pp. 13–14

3.2 Numerical Analysis

• A deterministic algorithm computes the singular values of a rational-entry matrix, including its trace norm, to additive error δ in polynomial time.Entry truncation uses O(log(ab/δ)) fractional bits while keeping the total singular-value-sum error at most δ.Source: §3.2 · p. 14

3.3 Setup

• A uniform routing strategy is generated by five fixed deterministic machines specifying resource preparation and the adversaries’ pre- and post-communication channels.The setup bounds the channel registers and combined generated-description size, and defines correctness input by input.Source: §3.3 · pp. 14–16
• The protocol begins with shared entanglement, samples x and y, applies local pre-communication channels, exchanges systems, then applies post-communication channels based on b=f(x, y).The verifiers test the routed register Q_b.Source: §3.3 · p. 15, Figure 2 · p. 16

4 The Universal Fidelity Gap

• The universal fidelity gap applies to any f-routing strategy that is (1−ε)-correct on an input with f(x, y) = 1.The section presents the gap as its main theorem.Source: §4 · p. 16
• The quantitative fidelity bounds remain valid for nonzero error, unlike the cited perfect 1-sided-error result.For perfect 1-sided error, Asadi, Culf, and May [ACM25, Lemma 5] established F0 = 1 and F1 < 1.Source: §4 · p. 16

4.1 Soundness Separability

• The soundness-separability argument chooses a state τA and uses fidelity inequalities to derive a lower bound on F0.The proof plans to choose τA so that α, β ≥ 1−ε, then substitute those bounds to obtain the lower bound.Source: §4.1 · p. 17

4.2 Completeness inseparability

• 1−2ε is a lower bound on tr(Φσ) in the completeness-inseparability analysis.The proof compares states by measuring whether they pass the EPR test.Source: §4.2 · pp. 18–19

5 Security from Time-Bounded QSZK Hardness

• The reduction works by reproducing intermediate strategy information as efficiently preparable states whose fidelity determines f(x, y).Converting the fidelity gap to a trace-distance gap supplies the connection to Quantum State Distinguishability.Source: §5 · p. 19
• A uniformly generated strategy that is (1−ε)-correct on every input, for sufficiently small ε, implies f ∈ QSZK(Tattack).The section defines QSZK(T) by a verifier time bound and a simulator running in polynomial time in the verifier's time.Source: §5 · pp. 19–20
• The deterministic space hierarchy provides unconditional choices of hard functions because QSZK(T) is contained in DSPACE(T^a).The section uses QSZK(T) ⊆ QIP(T) ⊆ DSPACE(T^a) for a universal constant a.Source: §5 · p. 20

5.1 Reduction to Quantum State Distinguishability

• The reduction maps the language Lf to coQSDα,β in time polynomial in n, q, log d, L, and τ.It deterministically constructs two circuit descriptions whose state fidelity gives a trace-distance gap for the QSD instance.Source: §5 · p. 19, §5.1 · pp. 21–22

6.1 Main Results

• A reduced state prepared by an (L, t)-Clifford+T circuit on q qubits has a product of its marginals preparable by a circuit on 2q qubits with at most 2L gates and 2t magic gates.Source: §6.1 · p. 23
• A deterministic classical algorithm approximates reduced-state fidelity in time poly(2^t, L, qρ + qσ, log(1/δ)).It takes the two Clifford+T circuits and δ as input.Source: §6.1 · p. 23

6.2 Preliminaries

• Stabilizer-state partial projections can be computed deterministically in poly(q, p, |A|, |B|) time, and reduced-state fidelity is the sum of singular values of the associated matrix.The singular values are obtained from a vectorization whose Schmidt coefficients equal those singular values.Source: §6.2 · p. 24

6.3 From Clifford+T circuits to (m, ν)-Stabilizer Decompositions

• Given Wρ and Wσ, the algorithm computes an explicit stabilizer decomposition of |χ⟩ with at most 2^(2t) terms, running in time poly(2^t, L, qρ + qσ).Source: §6.3 · pp. 25–26

6.4 Fidelity from (m, ν)-Stabilizer Decompositions

• Local Clifford unitaries transform a pure vector with an (m, ν)-stabilizer decomposition into a form with a residual vector on at most 2ν qubits; for explicit decompositions, this form is computable in polynomial time.Source: §6.4 · p. 28
• Amplitudes of |γ⟩ are computable in deterministic time poly(2^(2ν), ℓ), enabling a δ-additive fidelity estimate from the trace norm of its coefficient matrix.The singular values of the coefficient matrix give the Schmidt coefficients used in the fidelity calculation.Source: §6.4 · pp. 28–29

6.5 Proof of Lemma 6.14

• Local Clifford reductions decompose the stabilizer state into local |0⟩ factors, Bell pairs, and GHZ states; the resulting |γ⟩ has support on at most 2ν qubits.The required stabilizer-tableau transformations are computable in polynomial time.Source: §6.5 · pp. 29–31

7.1 Definitions and Security Results

• A unitary is (q, s)-Pauli-sparse when it acts on q qubits with at most s nonzero Pauli coefficients; explicit descriptions can be computed classically in time poly(s, q).Source: §7.1 · p. 31
• For a reduced state of a (q, s)-Pauli-sparse unitary, the product of its marginals is itself a reduced state of a (2q, s²)-Pauli-sparse unitary.Source: §7.1 · p. 31
• Theorem 7.4 gives algorithms for approximating the mid-protocol fidelity, using deterministic classical time for explicit strategies and bounded-error quantum time for non-explicit ones.The explicit runtime is O(τ) + poly(ds)(q + log(1/δ)); the non-explicit runtime is O(τ) + poly(q, d, s, L, 1/δ).Source: §7.1 · p. 32
• Explicit, uniformly generated (q, s)-Pauli-sparse strategies imply f ∈ DTIME(τ + (n + dsq)^c0), while non-explicit strategies imply f ∈ BQTIME(τ + (n + L + dsq)^c0).The result assumes the strategy is (1 − ε)-correct on every input at every input length for sufficiently small ε.Source: §7.1 · p. 32

7.2 Explicit Unitaries

• For explicit sparse unitaries, reduced-state fidelity can be computed to additive error δ by a deterministic classical algorithm in time poly(s)(q + log(1/δ)).Source: §7.2 · p. 32

7.3 Deferred Technical Lemmas

• A state prepared by an explicit (q, s)-Pauli-sparse unitary has an efficiently computable subsystem factorization with at most s columns, because its Schmidt rank across that partition is at most s.Source: §7.3 · p. 33

7.4 Non-explicit Unitaries

• For non-explicit sparse unitaries, learning Pauli coefficients supports bounded-error quantum fidelity estimation in time poly(q, s, L, 1/δ).The learned sparse descriptions are used to extend the explicit-unitary fidelity method.Source: §7.4 · p. 34

• The authors state that research direction, discoveries, lemma statements, and hypotheses originated with them.Source: AI Disclosure · p. 36
• ChatGPT’s Sol 5.6 assisted the authors in proving the results.Source: AI Disclosure · p. 36
• The authors repeatedly revised and interacted with ChatGPT to produce the final proofs.Source: AI Disclosure · p. 36