PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yu-Ao Chen

arXiv:2610.12664v1quant-phcs.CCcs.DS

TL;DR

Unknown-unitary transposition and inversion are oracle transformations studied under forward access, with prior protocols taking different approaches. This paper constructs catalytic qutrit circuits and proves processing-query lower bounds; the circuits attain the qutrit bounds while returning the catalyst.

  • Problem

    Forward access to an unknown unitary permits oracle transformations such as transposition and inversion, which prior protocols achieve in different ways.

    Source: p. 1

  • Method

    The construction prepares a catalyst independently of the input, then uses an encode–flip–decode processor for transposition and antisymmetric encoding for inversion.

    Source: pp. 1, 3

  • Results

    Four processing queries for qutrit transposition and eight for inversion attain the respective minimum processing costs, and four-query transposition requires at least three preparation queries.

    Source: p. 3

  • Takeaways & Limitations

    Reusing the returned catalyst implements m transpositions with 3 + 4m queries or m inversions with 3 + 8m queries, including preparation.

    Source: pp. 2–3

    The reported memory bound is Mmin ≤ 90 for pure coherent deterministic protocols in fixed causal order with three preparation and four processing queries.

    Source: p. 4

Abstract

from arXiv · show

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.

Supplemental Material

The supplement develops the catalytic transposition construction, its notation, and the encode–flip–decode processor. It also outlines analytic query-bound proofs, exact circuit checks, and formal verification.

Supplemental Material

  • The supplement gives an analytic proof of four-query catalytic transposition, from catalyst preparation and transpose covariance to the representation construction.It also establishes optimal processing costs and the preparation cost at the four-query threshold, with exact symbolic and Lean verification described in Sec. S6.Source: Supplemental Material · p. 5

SUMMARY OF NOTATION

  • The notation table collects recurring symbols and basic conventions, with locally used symbols defined at first occurrence; in the fixed a = 4/5 construction, HS, HP, HA, and H have dimensions 3, 65, 90, and 270.Source: SUMMARY OF NOTATION · p. 6

S1. TRANSPOSITION ALGORITHM AND CATALYST PREPARATION

  • The construction separates three-query catalyst preparation from four-query processing, which applies U^⊤ and restores the catalyst for reuse.The processor encodes data and catalyst with two queries, applies a fixed flip, reverses the encoder with two more queries, then exchanges the catalyst’s adjoint factors.Source: S1. TRANSPOSITION ALGORITHM AND… · p. 8, S1.1. Transposition algorithm · p. 8

S1.1. Transposition algorithm

  • The qutrit processor is deterministic and uses four forward queries; its catalyst is prepared deterministically with three forward queries.The construction’s catalyst can be prepared before the data arrive, independently of the input state.Source: S1.1. Transposition algorithm · p. 8

S1.2. Notation and intermediate maps

This section sets the coordinate and representation conventions for the qutrit circuit and defines its intermediate maps. The weighted direct sum of three isometric components supplies the encoded input state used in the processor.

Intermediate representation space

  • The intermediate space is a 45-dimensional direct sum of three representation sectors, physically embedded in the 270-dimensional workspace.Its sectors are V ⊗ Sym2 V, Sym2(V*) ⊗ V*, and V ⊗ V*.Source: S1.2. Notation and intermediate maps · p. 9

Intermediate maps

  • The weighted map Φα combines three isometric components, and its weights make the combined map an isometric embedding.The main text uses α = 1/5; the squared weights sum to one.Source: S1.2. Notation and intermediate maps · p. 10

Construction principle

  • Transpose covariance reduces encoder construction to matching seeds at U = I, after which fixed encodings and queries determine the output representation at each stage.The section specifies the fixed embeddings, phases, and unitary completions used for the encoder, flip, and reversed decoder.Source: S1.2. Notation and intermediate maps · p. 10

S1.3. Catalyst preparation

The catalyst is prepared before the data arrive using the singlet–adjoint decomposition and at most three forward queries. Transpose covariance then reduces the circuit design to seed reconstruction and normalization.

S1.3. Catalyst preparation

  • The catalyst family can be prepared deterministically with at most three forward queries, independently of the data to be transformed.Two forward queries realize U* through the antisymmetric construction, and one further query supplies U for the singlet–adjoint preparation.Source: S1.3. Catalyst preparation · p. 10

S2. TRANSPOSE-COVARIANT MAPS

  • Transpose covariance relates the coherent maps at different U values and lets the construction match their seed maps at U = I.The formulation retains amplitudes and phases while fixed encodings and queries change the output representation.Source: S2. TRANSPOSE-COVARIANT MAPS · p. 11

S2.1. Transpose-covariant maps

  • The intermediate maps obey transpose covariance for specified product-group representations, and their weighted direct sum is covariant as well.The stated direct-sum covariance holds for every 0 ≤ α ≤ 1/2.Source: S2.1. Transpose-covariant maps · p. 11

S2.2. Seed reconstruction and normalization

  • A covariant family is reconstructed from its seed at I, so matching seeds in the same output representation makes the families agree for every U.Irreducibility also makes the norm of the seed output constant across normalized inputs, allowing isometry to be checked at I.Source: S2.2. Seed reconstruction and… · p. 12

S2.3. Representation blocks and seed coefficients

The section counts allowed covariant seeds by representation multiplicity, showing when a branch vanishes or has a seed fixed up to a scalar. Tensor–Hom duality recasts that count as a representation multiplicity, with examples selecting the antisymmetric seed and excluding a branch.

S2.3. Representation blocks and seed coefficients

  • A (λ, µ) block is an embedded subspace where the two group variables act on separate representation factors.Its dimension is dλdµ, and multiple copies of the same type may occur.Source: S2.3. Representation blocks and seed… · p. 13
  • A branch’s seed space has dimension m, the multiplicity of ¯3 in g ↦ λ(g) ⊗ µ(g∗); m=0 kills it, while m=1 fixes its seed up to a scalar.The independent coefficients correspond to copies of the input representation in the restricted block action.Source: S2.3. Representation blocks and seed… · pp. 13–14
  • The (3, ¯3) block splits as 6 ⊕ ¯3, and the input maps only to the once-occurring antisymmetric ¯3, fixing the seed as bA.The antisymmetric encoding supplies this fixed seed when b=1.Source: S2.3. Representation blocks and seed… · p. 14

S2.4. Tensor–Hom duality and seed multiplicities

  • Tensor–Hom duality reduces seed counting to the multiplicity of λ in ¯3 ⊗ µ.The correspondence is implemented by contraction with a Bell vector in a compatible basis.Source: S2.4. Tensor–Hom duality and seed… · p. 14
  • For λ=6 and µ=¯6, the 10 seed vanishes, so reconstruction removes that branch for every U.The decompositions 3 ⊗ 6 = 8 ⊕ 10 and ¯3 ⊗ ¯6 = 8 ⊕ 10 allow only the left 8 to carry a seed.Source: S2.4. Tensor–Hom duality and seed… · p. 15

S2.5. Fixed encodings and query updates

Fixed encodings and forward queries carry transpose covariance along a representation path, while a seed-preserving fixed flip implements the desired transpose action without another query. These tools are assembled into the construction’s encoder, flip, and reversed decoder.

S2.5. Fixed encodings and query updates

  • A fixed encoding independent of U preserves transpose covariance when it intertwines the original and new output representations.This is the covariance-preserving encoding condition used in the construction.Source: S2.5. Fixed encodings and query updates · p. 15
  • Alternating fixed encodings and queries traces a representation path: each query replaces h∗ on the query qutrit by g while preserving memory and input actions.The single-query identity supplies the update used by the circuit.Source: S2.5. Fixed encodings and query updates · p. 15

S2.6. A fixed-flip criterion

  • A fixed unitary flip implements the desired U⊤ action without another query when it exchanges the representation actions and fixes the seed.Seed reconstruction extends these conditions from the seed to the whole family.Source: S2.6. A fixed-flip criterion · p. 16

S3. CONSTRUCTION AND VERIFICATION

  • The construction uses a two-query path to Φ1/5, then a fixed flip and reversed decoder to complete the four-query processor and restore the catalyst.The fixed gates act on prescribed subspaces of a 270-dimensional workspace and are extended to physical unitaries.Source: S3. CONSTRUCTION AND VERIFICATION · p. 16

S3.1. Initial representation blocks

  • The catalyst carries (1, 1) ⊕ (8, 8); transposing its second adjoint factor gives the required right action while the data couples to the first.The second adjoint factor remains the right 8 in each resulting block.Source: S3.1. Initial representation blocks · p. 17

S3.2. The two-query encoder

The two-query encoder selects occupied representation blocks with its first query and maps them to the intermediate family with its second. Its phases are fixed by the seeds, and the prescribed isometries extend to unitary gates on the common workspace.

S3.2. The two-query encoder

  • The first query selects three occupied representation blocks, and the second maps them to the intermediate family.The lemma specifies a two-query circuit using fixed unitary gates G0, G1, and G2 on H.Source: S3.2. The two-query encoder · p. 18
  • The encoding and decoding phases are fixed through their seeds.The construction uses these seeds to determine the phase choices.Source: S3.2. The two-query encoder · p. 18
  • The resulting isometries extend to unitaries on the common workspace.The circuit’s fixed gates act on H.Source: S3.2. The two-query encoder · p. 18

S3.2.1. First encoding and query

The first encoding exposes the query qutrit through right embeddings, then a forward query and representation selection determine the surviving output branches. A worked branch shows how seed constraints remove unwanted components while preserving the amplitude of the survivor.

S3.2.1. First encoding and query

  • A right embedding σ → ¯3 ⊗ µ exposes the query qutrit with action h∗, while memory retains (λ, µ) and the seed rule selects nonzero output branches.The rule is applied to the output representation after the forward query.Source: S3.2.1. First encoding and query · p. 18
  • The first memory M1 has dimension 90 and is identified with HA through fixed orthonormal bases, with the query qutrit placed first.Its summands have dimensions 9, 36, and 45.Source: S3.2.1. First encoding and query · p. 19
  • For right memories 3 and ¯6, the decompositions ¯3 ⊗ 3 = 1 ⊕ 8 and ¯3 ⊗ ¯6 = 8 ⊕ 10 determine candidate branches, while zero-seed branches vanish for every U.The 10 and ¯10 representations are inequivalent.Source: S3.2.1. First encoding and query · p. 20
  • In the worked (6, 8) branch, only (8, ¯6) survives the first query, and its amplitude is preserved through isometric encoding, query, and decoding.The seed constraint removes the left 10 candidate.Source: S3.2.2. A worked branch: (6, 8) to (8,… · p. 20

S3.2.3. First recoupling and the fixed multiplicity rotation

The first recoupling constructs an isometric decoding from ordered branch contractions, then combines two equivalent W8 ⊗ V copies with a fixed multiplicity rotation. The chosen amplitudes are preserved through these operations.

S3.2.3. First recoupling and the fixed multiplicity rotation

S3.2.4. Second encoding and query

The second query uses a fixed encoding into a 30-dimensional memory and places the two left-adjoint blocks in orthogonal antisymmetric and symmetric sectors. Representation constraints eliminate the 15 branch.

S3.2.4. Second encoding and query

  • The second-query carrier M3 = Sym2 V ⊕ (W8 ⊗ V*) has dimension 30.The encoding defines an isometry E2 from the 75-dimensional M2 space into HS ⊗ M3.Source: S3.2.4. Second encoding and query · pp. 21–22
  • The left-adjoint blocks enter orthogonal antisymmetric and symmetric sectors under the second-query encoding.The embeddings together fill the 72-dimensional space associated with the common 24-dimensional memory.Source: S3.2.4. Second encoding and query · p. 22
  • The 15 representation branch vanishes because the right-memory decomposition permits only 3 and ¯6 branches.The left candidates are 3 ⊗ 8 = 3 ⊕ ¯6 ⊕ 15, while right memory ¯3 permits only ¯3 ⊗ ¯3 = 3 ⊕ ¯6.Source: S3.2.4. Second encoding and query · p. 22

S3.2.5. Second recoupling and the final decoding

The second recoupling identifies the final decoding while preserving the chosen amplitudes. The prescribed fixed gates extend to unitaries independent of U and act on the evolving family within their designated subspaces.

S3.2.5. Second recoupling and the final decoding

  • The second recoupling’s normalized target basis is related to its source basis through Gram relations.The resulting representation also matches that of Φ1/5 in the natural left–right factor order.Source: S3.2.5. Second recoupling and the… · pp. 23–24
  • The second recoupling preserves the chosen amplitudes because O2 maps source coefficients to target coefficients and fixes the chosen vector.O1 and O2 express the same seeds in different coupling bases; Omerge combines the equivalent copies.Source: S3.2.5. Second recoupling and the… · p. 23
  • Seed identifications determine the final decoding D2 between two 45-dimensional physical subspaces.The three input images have dimensions 18, 18, and 9, specifying the full source of D2.Source: S3.2.5. Second recoupling and the… · p. 23

S3.2.6. Completing the fixed gates on the workspace

  • The prescribed isometries extend to U-independent unitary gates, and the evolving family stays within their prescribed domains.The gates are completed to unitaries by completing orthonormal bases of their source and image.Source: S3.2.6. Completing the fixed gates on… · p. 24

S3.3. The fixed flip

The fixed flip changes the intermediate representation as specified by the construction, after which decoding and restoration return the catalyst. The paper also establishes dimension-dependent processing lower bounds for finite-prepared program states, including when processing consumes them.

S3.3. The fixed flip

  • The fixed flip intertwines the representation with the exchanged, conjugated actions, and its physical midpoint map acts after the flip.The proof uses equal first two coefficients and specified relations among the component maps.Source: S3.3. The fixed flip · p. 24

S3.4. Decoding and catalyst restoration

  • The four-query circuit returns the complete catalyst, and its endpoint holds for entangled data inputs as well.The catalyst is prepared with three forward queries before the data arrive.Source: S3.4. Decoding and catalyst restoration · p. 25
  • For each known a in [4/5, 1], parameter-specific gates give the same four-query endpoint for every U in SU(3).The parameter family and its assumptions are identified in the Lean verification entry.Source: S3.4. Decoding and catalyst restoration · p. 26

S4. PROCESSING BOUNDS WITH A CONSUMABLE PROGRAM STATE

  • Exact processing requires at least d + 1 queries for transposition and d^2 − 1 for inversion, independently of finite preparation cost.The bounds hold in fixed causal order even when processing consumes the program state.Source: S4. PROCESSING BOUNDS WITH A… · pp. 26, 28

S5. PREPARATION LOWER BOUND FOR QUTRIT TRANSPOSITION

At the four-processing-query threshold, exact qutrit transposition needs at least three preparation queries, and the construction attains both costs. The proof rules out two-query preparation by reducing it to an impossible three-query processor.

S5. PREPARATION LOWER BOUND FOR QUTRIT TRANSPOSITION

  • At q=4, exact qutrit transposition needs at least 3 preparation queries, and the construction attains both costs.The lower bound applies to an arbitrary finite-dimensional program space.Source: S5. PREPARATION LOWER BOUND FOR QUTRIT… · pp. 28–29
  • Assuming only 2 preparation queries forces the first-query prefix to be U-independent, leaving a fixed encoding and only 3 processing queries.The resulting protocol would contradict the four-query processing lower bound.Source: S5. PREPARATION LOWER BOUND FOR QUTRIT… · p. 29
  • The proof derives symmetry constraints on quadratic program-state slices, then shows rank-one inputs make every slice vanish.The rank-one argument uses a common two-dimensional kernel to force each slice to zero.Source: S5. PREPARATION LOWER BOUND FOR QUTRIT… · p. 29
  • Those constraints force quadratic entries to factor through 2×2 minors and the adjugate; the resulting fixed program state plus G0 contradicts the three-query processor bound.The proof identifies the resulting map as right multiplication by a constant matrix before deriving the contradiction.Source: S5. PREPARATION LOWER BOUND FOR QUTRIT… · p. 29

S6. COMPUTER-ASSISTED ANALYSIS

Computer-assisted checks verify the fixed catalytic circuit and formalize the paper's exact results. The auxiliary-memory calculation gives a 90-dimensional upper bound, but a matching lower bound remains open.

S6.1. Symbolic circuit verification

  • All 810 polynomial-entry differences vanish exactly, verifying the fixed a=4/5 catalytic identity on SU(3).The notebook verifies the circuit gates, three-query preparation, and four-query processor; a separate script also tests circuits at finitely many parameters and SU(3) matrices.Source: S6.1. Symbolic circuit verification · p. 30

S6.2. Lean verification of S1–S5

  • Lean 4 formalizes S1–S5 and the repeated-use constructions, with theorem assumptions and protocol-model coverage recorded.The replay audits dependencies and rejects sorryAx.Source: S6.2. Lean verification of S1–S5 · p. 30

S6.3. Computational observation on auxiliary dimension

  • The 90-dimensional construction establishes Mmin ≤90, while Mmin=90 remains a candidate and a general matching lower bound is open.A coefficient-chain reduction from every admissible physical protocol and the resulting physical-memory rank bound remain to be established.Source: S6.3. Computational observation on… · pp. 30–31
Loading 2610.12664v1…