Let $A\cong {\mathbb{C}}^2$, let $W\ne \{0\}$ be a finite-dimensional Hilbert space with a designated unit vector $|0_W⟩$, and put

An input is a unitary $O:M\to M$. Write

For a fixed , the promised family ${\mathcal{O}}_{\delta ,W}$ consists of all such unitaries with

Let $r_O=0$ in the first case and $r_O=1$ in the second. When both answer blocks are nonzero, the generated state can be written as

where the two garbage states are normalized. They may be complex, nonorthogonal, and unrelated across instances. A garbage state multiplying a zero coefficient can be chosen arbitrarily. The action of $O$ on $s^{⟂}$ is unrestricted.

We use the controlled arbitrary-unitary query convention of [1, 2, 4]. The bidirectional oracle is

with orthogonal forward and inverse direction labels. A query applies

Thus the circuit may coherently choose whether to query and in which direction. Oracles are specified as unitaries, not modulo global phase; a phase of an oracle block is observable relative to a non-query branch. Work operations are arbitrary fixed unitaries and are not charged to the query cost.

The public space is $\mathcal{H}={\mathbb{C}}_B^2\otimes \mathbb{C}s$, with basis ${\xi }_b=|b_B⟩s$. An exact purifier is a fixed query circuit $\mathsf{S}$ on $\mathcal{H}\oplus \mathcal{L}$, together with a choice of catalyst $w_O\in \mathcal{L}$ for every promised oracle, satisfying

The circuit has finitely many query gates. Its private space $\mathcal{L}$, query controls, and work unitaries are independent of the unknown oracle; $w_O$ may depend on it. Catalysts here are unnormalized vectors in a direct sum, not auxiliary tensor-product states supplied to an ordinary algorithm. A catalyst is included in the specification of the realization, as it need not be unique [3, Section 7.1].

For such a realization $\mathcal{T}=(\mathsf{S},{(w_O)}_O)$, let $q_{O,j}$ be the queried component immediately before its $j$-th query, when the circuit acts on ${\xi }_0\oplus w_O$. Its Las Vegas query cost and its transduction complexity are, respectively,

Private space may be infinite-dimensional. The constructions below use separable space, with arbitrary fixed work unitaries. Work operations are not subject to a finite-gate synthesis requirement.

For the restricted interface, stack the query vectors using orthogonal query-time labels. We call the realization admissible if, for every $O$, its total query vector has the form

Thus every forward query is supported on the designated input ray and every inverse query on the generated-state ray. The vectors $f_O,g_O$ contain all remaining controls and registers. Different control spaces can be embedded in one common control space. After the query,

where identity operators on controls are suppressed. Define

In both infima, one fixed circuit must serve the entire promised family.

Throughout, inner products are conjugate-linear in the first argument. Consider any exact state-conversion family ${({\xi }_x,{\tau }_x,Q_x)}_{x\in X}$, with one fixed transducer and catalysts $w_x$. If $q_{x,j}$ denotes the component queried at step $j$, telescoping inner products through the circuit gives

Here and below, oracle operators act identically on ancillary and query-time controls. To see the identity, an input-independent work unitary preserves each cross-instance inner product. A query changes that inner product from its pre-query value by $-⟨q_{x,j},(I-Q_x^{\ast }{Q}_y)q_{y,j}⟩$. Summing these changes and subtracting the initial and final inner products cancels $⟨w_x,w_y⟩$, because the catalyst is returned. Orthogonality of the query-time labels then gives (2.10), and ${\parallel v_x\parallel }^2$ is the query cost. This is the transducer form of the adversary identity [2, 4].

For the restricted upper bound we will construct query vectors directly from the generated states. To turn those vectors into a single circuit, we need the converse of (2.10) for the entire oracle family. Equal Gram matrices define an isometry on the closed spans, but in infinite dimension their orthogonal complements need not have equal dimension. An unused summand removes this obstruction.

If query vectors $v_x$ satisfy (2.10), the two families

have equal Gram matrices. The lemma supplies a fixed unitary $U$ with

Applying the oracle on the query summand and then $U$ gives a canonical transducer. Its catalyst is $v_x\oplus 0$, so both its query cost and its transduction complexity are ${\parallel v_x\parallel }^2$. The added summand is non-query space and is unpopulated on every instance. This proves the needed converse without assuming finiteness of $X$; compare [4, Theorem 2.15].

We first construct a phase purifier whose public input is $s$. The construction has two parts: a reflection whose compression to the plane generated by $s$ records the answer probability, and a line walk that uses this plane without requiring its basis as input. Define

Each controlled call to $R_O$ is implemented by a controlled $O$ query, the known reflection $Z_A$ on the same branch, and a controlled $O^{\ast }$ query. The two oracle queries process equal squared norms.

Fix an oracle and abbreviate $p=p_O$. For , put

The identity ${\parallel P_{O}s\parallel }^2=⟨Os,{\mathrm{\Pi }}_{0}Os⟩=1-p$, and its counterpart for $I-P_O$, show that $u_0,u_1$ are orthonormal. They are respectively $+1$ and $-1$ eigenvectors of $R_O$, and $s=a{u}_0+b{u}_1$. Consequently,

is a unit vector orthogonal to $s$. The plane $E_O=\mathrm{span}\{s,t_O\}$ is invariant, and in its ordered basis $(s,t_O)$,

Equation (3.3) isolates the completion dependence: the matrix is determined by $p$, but its basis vector $t_O$ is not. The rank of $P_O$ and the garbage states do not enter that matrix. The next lemma implements the required walk using the projector onto $s$, so no gate is defined by $t_O$.

Apply the lemma to $R_O$ and (3.3). The cases $p_O=0,1$ satisfy $R_{O}s=s,-s$, respectively, and are covered by the last part of the lemma. The resulting phase transducer therefore works for every promised completion. Its circuit uses only $P_s$, counter shifts, and the pulled-back reflection; the gap is needed only to bound the worst-case cost.

To turn the phase into a bit, take the direct sum of the identity on $\mathbb{C}{\xi }_0$ and the phase transducer on $\mathbb{C}{\xi }_1\oplus \mathcal{L}$. Conjugate this operation by a Hadamard on the public space $\mathrm{span}\{{\xi }_0,{\xi }_1\}$, extended as the identity on $\mathcal{L}$. For the phase catalyst $v_O$, the resulting transformation is

In particular, neither Hadamard acts on the catalyst. Every query vector of the phase transducer is scaled by $1/\sqrt{2}$, halving its cost. Replacing each controlled $R_O$ by its two oracle calls doubles the cost, since the intervening known reflection preserves the queried norm. The factors cancel, giving

The chosen catalyst $w_O=v_O/\sqrt{2}$ satisfies

This proves the unrestricted upper bound. The circuit does not use $\delta$, and (3.11) gives transduction complexity $O(1/\delta )$ on the promised family. One application contains four controlled query gates; the charged resource is their total queried squared norm in (3.10).

Set

Choose ${\theta }_L,{\theta }_H\in (0,\pi /2)$ by

Their difference $\mathrm{\Delta }={\theta }_H-{\theta }_L$ satisfies

A two-instance adversary using only the boundary rotations has filter norm $2\sin (\mathrm{\Delta }/2)$, yielding only . Pairing each rotation with its negative gives the sharper joint filter below.

On $M_0=\mathrm{span}\{|0_A{0}_W⟩,|1_A{0}_W⟩\}$, define four oracles by

All four act as the identity on $M_0^{⟂}$. They are legal inputs for every $W$: their answer probabilities are $\mathrm{\ell }$ or $h$, and their signs can be absorbed into the garbage states. Let $Q_{c,\epsilon }=O_{c,\epsilon }\oplus O_{c,\epsilon }^{\ast }$. When $dimW=1$, the signs in (3.14) are global oracle signs, which are legitimate in the controlled-unitary convention fixed in (2.3).

Write $x=(c_x,{\epsilon }_x)$. The public Gram difference is $F{}_{xy}=\mathbf{1}{}_{\{c{}_x\ne c{}_y\}}$. Let $v_x$ be the total query vectors of any exact purifier on these four instances, and put $C={\max }_x{\parallel v_x\parallel }^2$. Order the instances as $(L,+),(L,-),(H,+),(H,-)$, and set

Each row of $K$ sums to one, so

We compute the norm of the Hermitian filtered operator

The active rotations have a common complex eigenbasis. In either forward eigenchannel, put $z=e^{\pm i\mathrm{\Delta }}$. The low-to-high block of $D$ on the two sign indices is

It is diagonalized by the Hadamard matrix, with eigenvalues $1-\mu z$ and $\mu -z$. Since $\mathrm{Re}z=\mu$,

and therefore $\parallel C_z\parallel =2\delta$. The high-to-low block is $C_z^{\ast }$. The square of the corresponding Hermitian block is $\mathrm{diag}(C_z{C}_z^{\ast },C_z^{\ast }{C}_z)$, so the Hermitian block has norm $2\delta$. The inverse direction replaces $z$ by $\overline{z}$, and the common identity action on $M_0^{⟂}$ contributes zero. Ancillary and query-time controls only amplify these operators by an identity. Hence

Multiplying (2.10) by ${\mathrm{\Gamma }}_{xy}$, summing over the four instances, and applying (3.19) gives

Thus $C\ge 1/(2\delta )$. The four-instance family embeds into every nonzero workspace, so this lower bound and (3.10) prove (1.1).

Index the full promised family by $x$, and write ${\varphi }_x=O_{x}s$, $p_x={\parallel {\mathrm{\Pi }}_1{\varphi }_x\parallel }^2$, and $r_x=r_{O_x}$. Its public Gram difference is

The restriction to rays turns the operator-valued adversary identity into a scalar kernel identity. The inverse direction contributes the negative of the forward filter; retaining this sign is essential.

In particular, the admissible optimization depends on an oracle only through its generated state. Its completion disappears from the signed-Gram constraint, even though the fixed transducer must work for every completion.

For opposite labels, (4.2) asks for the reciprocal kernel $1/(1-⟨{\varphi }_x,{\varphi }_y⟩)$. Summing tensor powers of the unit vectors ${\varphi }_x$ would give this kernel formally, but the witness vectors would have infinite norm. The needed modification is to contract the vectors without changing these cross-class inner products. We use the reciprocal rescaling from [1, proof of Theorem 35] and [3, proof of Theorem 13.1], keeping its exact norm bound. Retain $\mathrm{\ell },h,\mu$ from (3.12), and set

For each instance, define

For opposite labels, the rescalings cancel on each answer block, so

At the same time,

Indeed, for a low instance, ${\parallel c_x\parallel }^2={\kappa }^2(1-p_x)+{\kappa }^{-2}{p}_x$ is increasing in $p_x$, so its maximum on the promised interval is attained at $p_x=\mathrm{\ell }$. For a high instance the coefficients are interchanged; the resulting expression decreases in $p_x$ and is maximized at $p_x=h$. Both maxima equal $\mu$.

Thus the rescaling preserves precisely the inner products that occur in the cross-class constraints and makes every vector strictly contractive. Its tensor powers can therefore be summed in the full tensor Fock space

Define

The norm bound (4.6) makes this a well-defined vector with

Moreover, , so its inner products are given by an absolutely convergent geometric series:

This step is valid for complex inner products; no choice of real garbage states is involved.

Let ${\sigma }_x={(-1)}^{r_x}$, and choose

For equal labels, the two Gram terms in (4.2) cancel. For opposite labels, their difference is $⟨{\eta }_x,{\eta }_y⟩$, so (4.9) verifies the constraint. Consequently, Proposition 4.1 gives one fixed admissible transducer with

The Fock space is separable because $M$ is finite-dimensional, and the stabilization adds only a separable non-query summand. The chosen catalyst has the same squared norm as the query cost. Its dependence on the class label in (4.4) and (4.10) is permitted: the work unitary is constructed once from all the Gram relations, and no gate receives the unknown label.

For the lower bound, choose any unit vector $w\in W$ and consider

Each can be the image of $s$ under a unitary: extend $s$ and the chosen image separately to orthonormal bases and map one basis to the other. These are therefore legal low and high instances, and $⟨{\varphi }_{-},{\varphi }_{+}⟩=\mu$. Any feasible witnesses must satisfy

where the inequality is Cauchy–Schwarz applied to $(f_{-},g_{-})$ and $(f_{+},-g_{+})$. At least one cost is at least $1/(1-\mu )$. Together with (4.11), this proves (1.2) and completes the proof of Theorem 1.1.

The opposite signs in (4.10) cancel every same-label constraint without restricting the within-class overlaps of the Fock vectors. This cancellation is essential. With only one query direction, distinct same-label inputs would require orthogonal witnesses, while each must retain a nonzero overlap with a fixed opposite-label witness.

The lower bounds use only finite subfamilies at a time and require no separability assumption. Allowing nonseparable private space therefore cannot lower either optimum, whereas the constructions attain both values on fixed separable spaces. Finite-dimensional approximate realizations of purification are treated in [3, 4].