Optimal transducers using symmetries

I. INTRODUCTION

• Transducers compose without error-control overhead, motivating methods for building efficient transducers and algorithms for quantum query problems.The paper's goal is to exploit problem symmetries to construct transducers and apply the methods to standard primitives.Source: §I · pp. 1–2
• Symmetrization guarantees an optimal weakly covariant catalyst, while the transducer unitary intertwines group representations and is block diagonal across irreducible representations.Strong covariance is not always feasible or optimal, so weak covariance is the general guarantee.Source: §I · p. 2
• For Search_N^M, weak covariance is assumed before strong covariance is shown optimal; for Search_N^{≥M}, strong covariance directly matches the lower bound.The catalyst optimization for Search_N^M reduces to a two-dimensional problem.Source: §I · p. 2
• The methods yield explicit transducers with optimal query-complexity constants for unstructured search, amplitude amplification, and amplitude estimation.The paper emphasizes that these are explicit algorithms, beyond previously known bounded-error query complexities.Source: §I · pp. 2–3
• For amplitude amplification, the method derives a lower bound from a subset of inputs and constructs a strongly covariant catalyst that saturates it.The at-least-ε variant requires functional analysis on an infinite-dimensional space C ⊕ L2(R).Source: §I · pp. 2–3
• For amplitude estimation, the target family is π-periodic with inner products depending on angle differences, and catalyst components reduce to two-dimensional optimizations.The symmetry group is U(1), whose characters form the Fourier basis.Source: §I · p. 3

A. State Conversion Problems and Their Equivalence

• A state-conversion problem uses one algorithm and an input-dependent oracle to map each indexed input state to its target state.This framework generalizes function evaluation, where the input state is fixed and the target encodes the function value.Source: A. State Conversion Problems and Their… · p. 4
• Unitary equivalence between state-conversion problems is characterized by the input and target Gram data and the orbit of the relative oracle kernel.Input-independent unitaries transform algorithms between equivalent problems through state preprocessing and oracle-call conjugations.Source: A. State Conversion Problems and Their… · pp. 4–5

B. Quantum Query Complexity

• The adversary bound is an optimization-program objective introduced because direct complexity definitions are hard to use; it characterizes quantum query complexity up to a 1/ε² factor [13] [14] [10] [12] [15].Exact query complexity counts oracle calls for exact conversion, while bounded-error query complexity permits error at most ε.Source: B. Quantum Query Complexity · p. 6

C. Transducers

• A canonical transducer uses an input-independent unitary and an oracle call with input-indexed catalysts; its Gram-matrix condition matches the adversary-bound condition [1].A transducer acts on public and private spaces, using a catalyst that remains unchanged during the conversion.Source: C. Transducers · p. 7

D. Elements of Representation Theory

• The paper uses unitary representations of finite or compact Lie groups and decomposes representation spaces into isotypic components.Strong continuity is imposed for compact Lie groups.Source: D. Elements of Representation Theory · p. 8

3 In short for any function f on G, R

• The input-independent unitary is an intertwiner, whose structure is described blockwise in the isotypic decomposition.Intertwiners are linear maps that commute with the group action.Source: §3 · p. 9

III. SYMMETRIC TRANSDUCERS

• The symmetry group is the maximal subgroup of input bijections preserving the problem’s input, target, and oracle structure.The section characterizes this invariance through representations acting on the relevant spaces.Source: §III · p. 10

A. Symmetries of the Catalyst

• Symmetrizing any transducing algorithm yields a weakly covariant algorithm with no greater transduction complexity, so an optimal weakly covariant algorithm exists.The construction forms a controlled uniform superposition of rotated catalyst families.Source: A. Symmetries of the Catalyst · pp. 10–11
• Strong covariance is not universally attainable or optimal: Problem 7 has no strongly covariant solution, while in Problem 8 covariance can waste redundant oracle information.Problem 7 is a single-marked-item search variation with cyclic symmetry C_n.Source: A. Symmetries of the Catalyst · pp. 10–11
• Weak covariance confines each catalyst to the subspace invariant under the stabilizer of its input.This restriction can reduce the space in which optimal catalysts must be sought.Source: A. Symmetries of the Catalyst · p. 11

B. Symmetry Theorem for the Trandsucer

• A weakly covariant transducer has an input-independent unitary S◦ that intertwines the group representations on X and T, enabling isotypic block decomposition.If the representations on the orthogonal complements are equivalent, the intertwining can extend globally; if the representations are equal, the global decomposition follows.Source: B. Symmetry Theorem for the Trandsucer · pp. 11–12

A. Unstructured Search and Amplitude Amplification on Single Orbit

• For single-orbit search, the method optimizes over weakly covariant catalysts and finds that the optimal solution is strongly covariant.The trivial-representation subproblem relaxes the others, reducing the catalyst optimization to two dimensions.Source: A. Unstructured Search and Amplitude… · p. 12, §1 · p. 14

1. Unstructured search with M marked elements

• Fixed-M search recovers the result of Bennett, Bernstein, Brassard and Vazirani [29], with a smaller constant than Zalka’s [30] under the paper’s Las Vegas complexity setting.The authors distinguish their Las Vegas comparison from Zalka’s minimum fixed-oracle case.Source: §1 · p. 13
• The search transducer’s unitary separates into isotypic blocks, including a symmetric subspace and its orthogonal complement.The figure depicts the oracle-controlled action and the conversion from the uniform input branch to the target branch while retaining the catalyst branch.Source: §1 · p. 14, Figure 4 · p. 15

2. Amplitude amplification with a fixed amplitude

• The fixed-amplitude task converts |ξ⟩ to its projection on the marked subspace using access to a reflection around |ξ⟩.The marked-space reflection is treated as free in this query-complexity formulation.Source: §2 · p. 15
• A lower bound from a two-input subproblem is matched by a strongly covariant catalyst, establishing optimality for fixed-amplitude amplification.The lower bound matches the one for search; the paper gives the optimal value as W = β/(2ε), where β = √(1 − ε^2).Source: §2 · pp. 16–18
• The symmetry’s isotypic decomposition separates marked and unmarked spaces, so the transducer can be built from blocks acting on each.The corresponding two-dimensional block unitaries are fixed up to a phase.Source: §2 · p. 18

B. Unstructured Search and Amplitude Amplification on Multiple Orbits

• The section treats lower-bound variants of both unstructured search and amplitude amplification by replacing fixed promises with lower bounds.The supplied passages give the detailed lower-bound and matching-catalyst results for search.Source: B. Unstructured Search and Amplitude… · p. 19
• Search with at least M marked elements has the same transduction complexity as fixed-M search, and its catalyst matches the fixed-M case when exactly M elements are marked.The authors establish the lower bound by restricting inputs to Hamming weight M, then show that a catalyst saturating this bound is optimal.Source: B. Unstructured Search and Amplitude… · pp. 19–20
• For the at-least-M search promise, the input set separates into orbits indexed by bitstrings’ Hamming weight.The symmetric group acts by permuting indices; restricting to the weight-M orbit recovers the fixed-M search problem.Source: B. Unstructured Search and Amplitude… · p. 20

2. Amplitude amplification with unknown initial amplitude

• Amplitude amplification with initial amplitude at least ε recovers the fixed-amplitude transduction complexity.The construction uses the value W(P) = √(1 − ε^2)/(2ε) and a catalyst represented in the workspace C ⊕ L2(R).Source: §2 · pp. 22, 24
• The catalyst is directly sought as strongly covariant, with its cost checked against the fixed-ε subproblem’s lower bound.The input is decomposed into normalized marked and unmarked components and an amplitude parameter s.Source: §2 · pp. 22–23
• The construction realizes the catalyst’s Gram kernel with vectors gs(t) = √(2s)e^(−st) in L2(R+).For s in [ε, 1], their span is L2(R+).Source: §2 · pp. 24–25
• The initial workspace does not provide matching orthogonal-complement dimensions for the unmarked-space block, so the workspace is enlarged to C ⊕ L2(R).The extension supplies infinite-dimensional complements needed for the unitary construction.Source: §2 · pp. 22, 25, 26

• Full-circle amplitude estimation prepares a target state |fθ⟩ from a fixed input state, with target-state inner products depending only on θ − θ′.Source: C. Amplitude estimation · p. 28
• A square window of width δ makes the state-conversion problem equivalent to estimating θ up to error δ, but its discontinuity gives infinite complexity; smoother windows avoid that issue.Source: C. Amplitude estimation · p. 28
• Θ(δ^-1) is the complexity for smooth windows; unlike the standard decision transducer, the cost is fixed, with error when |θ − θ′| ≤ δ/2.The standard decision transducer has variable cost O((θ − θt)^-1), which can grow when the input is near the threshold.Source: C. Amplitude estimation · p. 28

• The full-circle problem requires the target-state family to be π-periodic because the oracle cannot distinguish angles separated by π.Source: §1 · p. 29
• Strong covariance is possible only for the trivial problem, where g(ω) = 1 for all ω.Source: §1 · p. 30
• The U(1) symmetry yields a decomposition into character modes, and π-antiperiodicity makes the odd Fourier coefficients the relevant nonzero modes.Source: §1 · pp. 30–31
• The optimal catalyst lives in ℓ2(2Z + 1) ⊗ C2, and Proposition 12 states the transduction complexity for full-circle amplitude estimation.Source: §1 · pp. 29, 31

• The interval is restricted to |I| < π; otherwise the problem requires π-periodicity and extends to the full-circle case.Source: §2 · p. 31
• The interval problem has an upper bound on transduction complexity, realized by a catalyst in ℓ2(2Z + 1) ⊗ C2.Source: §2 · p. 31
• Because the interval problem lacks U(1) symmetry, the section can establish feasibility but cannot use symmetry to prove the catalyst optimal.Source: §2 · p. 31
• The construction extends h to [−L, L] for L ≥ |I|, with h(−L) = h(L) = 0, while matching the prescribed function on [−|I|, |I|].Source: §2 · p. 32

• Two counterexamples illustrate that strong covariance may be impossible or may fail to be optimal.Source: D. Example of non-feasible strong… · p. 32

1. No strongly covariant solution

• No strongly covariant feasible point exists for search with a cyclic scalar oracle, while a weakly covariant catalyst is optimal with W = C_N−1.The problem uses inputs indexed by Z_N with H = M = C_N.Source: §1 · pp. 32–33
• The strong-covariance constraint yields a contradiction because one side is real and the other has a nonzero imaginary part.Source: §1 · p. 33
• A feasible weakly covariant catalyst can be chosen, and similar techniques establish its optimality.Source: §1 · p. 33

2. A non-optimal strongly covariant solution with a two-dimensional oracle

• The counterexample is a conversion-to-cosine-kernel problem on Z3 with H = M = C2.Source: §2 · p. 33
• A strongly covariant feasible point has cost α + β < 3/2, yet it is not optimal; the minimum over admissible oracle representations is 2.Only the r = 0 representation admits strongly covariant feasible points, and its minimum is 2.Source: §2 · pp. 33–34

VI. USE OF AI

• The authors used AI for technical proof steps, finding the counterexample, generating figure code, and mathematical and language verification.They state that they take full responsibility for the paper’s text.Source: §VI · p. 35

Appendix A: Proof of Proposition 1.

• For Proposition 1, the constructed map is an isometry onto the target span and extends to a unitary using a unitary between the orthogonal complements.The proof assumes the two orthogonal complements have equal dimension.Source: Appendix A · p. 38

1. Proof of Theorem 5

• Theorem 5’s proof symmetrizes catalysts over rotated inputs, obtaining weak covariance with transduction complexity no greater than the original algorithm’s.The symmetrized catalyst lives in an enlarged private space formed with the group Hilbert space.Source: §1 · pp. 38–39

2. Proof of Theorem 5

• The proof setup identifies the catalyst-augmented input span X and target span T, with T = S°X.Source: Proof of Theorem 7 · p. 39

Proof of Theorem 7.

• Theorem 7’s proof uses that the catalyst-augmented input vectors span X and that T is their image under S°, considering inputs related by the group action.Source: Proof of Theorem 7 · p. 39