← All papers
First page of A Catalytic Algorithm for Transposing Unknown Qutrit Unitaries with Tight Query Bounds

A Catalytic Algorithm for Transposing Unknown Qutrit Unitaries with Tight Query Bounds

Yu-Ao Chen

quant-ph Oct 8, 2026 · v1 cs.CC cs.DS
Formalizes the paper's exact results (Secs. S1–S5: catalytic transposition circuit, query lower bounds, repeated-use constructions) in Lean 4 with Mathlib, provided as ancillary sources.
We construct exact deterministic circuits for transposing and inverting an unknown qutrit unitary $U\in\mathrm{SU}(3)$ using only forward queries. Three queries prepare a catalyst independently of the input state. Four further queries implement transposition while returning the catalyst unchanged and uncorrelated with the output. Two uses within an antisymmetric encoding implement inversion with eight processing queries and return the same catalyst. Reusing the catalyst implements $m$ transpositions or inversions with $3+4m$ or $3+8m$ total queries, respectively. More generally, we prove that exact transposition and inversion of an unknown $U\in\mathrm{SU}(d)$, $d\ge2$, require at least $d+1$ and $d^2-1$ processing queries, respectively, in fixed causal order. These processing bounds hold for any program state prepared independently of the input state using finitely many forward queries, even if that state is consumed during processing. Both our catalytic qutrit algorithms attain their respective bounds. Moreover, exact qutrit transposition with four processing queries requires at least three preparation queries, and our construction attains this bound.

The goal is to implement the transpose and the inverse of an unknown qutrit unitary U in SU(3) exactly and deterministically, using only forward queries to U, and to determine the minimal query costs.

Three queries prepare a catalyst state that does not depend on the input. A four-query processor then applies U^T through an encode–flip–decode construction based on transpose-covariant maps and SU(3) representation theory, and returns the catalyst unchanged. Inversion uses two transpositions inside an antisymmetric encoding. Lower bounds come from extending a differential completely positive method to program states that depend on U. Verification combines Mathematica symbolic checks, Python scripts, and a Lean 4/Mathlib formalization of Secs. S1–S5.

Transposition costs 4 processing queries and inversion costs 8. With catalyst reuse, m transpositions take 3+4m total queries and m inversions take 3+8m. For general SU(d) in fixed causal order, transposition needs at least d+1 processing queries and inversion at least d^2−1. Qutrit transposition with four processing queries needs at least three preparation queries, so the construction meets every stated bound.