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.
AI Summary
The paper studies exact, deterministic transposition and inversion of an unknown unitary using only forward oracle queries in fixed causal order. It separates queries used to prepare an input-independent program state from processing queries acting on the data, and asks whether the program can be returned unchanged for reuse.
For $U\in\mathrm{SU}(3)$, three queries prepare a singlet–adjoint catalyst. Four additional queries implement $U^\top$, returning the catalyst unchanged and uncorrelated with the output. Two transpositions within an antisymmetric encoding implement $U^\dagger$ with eight processing queries. Reuse gives total costs $3+4m$ and $3+8m$ for $m$ transpositions and inversions, respectively. The construction uses a two-query representation-theoretic encoder, a fixed flip, and a two-query decoder realizable with forward queries. Processing requires a 90-dimensional memory outside the queried qutrit.
For arbitrary $d\ge2$, a differential completely positive response argument and Choi positivity establish processing lower bounds $q_\top\ge d+1$ and $q_\dagger\ge d^2-1$, even for finitely prepared programs consumed during processing. Both qutrit constructions attain these bounds. Saturation and polynomial constraints additionally show that four-query qutrit transposition requires at least three preparation queries. The paper supplies exact symbolic circuit checks and reports Lean formalizations.
The bounds do not settle unrestricted single-use query optimality: the constructions use seven and eleven total queries, while cited analytic lower bounds are six and nine. A matching memory lower bound remains open, and the catalytic construction is qutrit-specific.
No sign of AI-generated text
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
We construct exact deterministic circuits for transposing and inverting an unknown qutrit unitary U∈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∈SU(d), d≥2, require at least d+1 and d2−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 paper studies exact, deterministic transposition and inversion of an unknown unitary using only forward oracle queries in fixed causal order. It separates queries used to prepare an input-independent program state from processing queries acting on the data, and asks whether the program can be returned unchanged for reuse.
For U∈SU(3), three queries prepare a singlet–adjoint catalyst. Four additional queries implement U⊤, returning the catalyst unchanged and uncorrelated with the output. Two transpositions within an antisymmetric encoding implement U† with eight processing queries. Reuse gives total costs 3+4m and 3+8m for m transpositions and inversions, respectively. The construction uses a two-query representation-theoretic encoder, a fixed flip, and a two-query decoder realizable with forward queries. Processing requires a 90-dimensional memory outside the queried qutrit.
For arbitrary d≥2, a differential completely positive response argument and Choi positivity establish processing lower bounds q⊤≥d+1 and q†≥d2−1, even for finitely prepared programs consumed during processing. Both qutrit constructions attain these bounds. Saturation and polynomial constraints additionally show that four-query qutrit transposition requires at least three preparation queries. The paper supplies exact symbolic circuit checks and reports Lean formalizations.
The bounds do not settle unrestricted single-use query optimality: the constructions use seven and eleven total queries, while cited analytic lower bounds are six and nine. A matching memory lower bound remains open, and the catalytic construction is qutrit-specific.
Recent developments have revealed deterministic and exact protocols for performing complex conjugation, inversion, and transposition of a general d-dimensional unknown unitary operation using a finite number of queries to a black-box unitary operation. In this Letter, we establish analytical lower bounds for the query complexity of unitary inversion, transposition, and complex conjugation, which hold even if the input unitary is an unknown logarithmic-depth unitary. Specifically, our lower bound of d^{2} for unitary inversion demonstrates the asymptotic optimality of the deterministic exact inversion protocol, which operates with O(d^{2}) queries. We introduce a novel framework utilizing differentiation to derive these lower bounds on query complexity for general differentiable functions f: SU(d)→SU(d). As a corollary, we prove that a catalytic protocol-a new concept recently noted in the study of exact unitary inversion-is impossible for unitary complex conjugation. Furthermore, we extend our framework to the partially known setting, where the input unitary operation is promised to be within a subgroup of SU(d) and the probabilistic setting, where transformations succeed probabilistically.
We report a deterministic and exact protocol to reverse any unknown qubit-unitary operation, which simulates the time inversion of a closed qubit system. To avoid known no-go results on universal deterministic exact unitary inversion, we consider the most general class of protocols transforming unknown unitary operations within the quantum circuit model, where the input unitary operation is called multiple times in sequence and fixed quantum circuits are inserted between the calls. In the proposed protocol, the input qubit-unitary operation is called 4 times to achieve the inverse operation, and the output state in an auxiliary system can be reused as a catalyst state in another run of the unitary inversion. We also present the simplification of the semidefinite programming for searching the optimal deterministic unitary inversion protocol for an arbitrary dimension presented by M. T. Quintino and D. Ebler [Quantum 6, 679 (2022)2521-327X10.22331/q-2022-03-31-679]. We show a method to reduce the large search space representing all possible protocols, which provides a useful tool for analyzing higher-order quantum transformations for unitary operations.
Symmetry plays a crucial role in the design and analysis of quantum protocols. This result shows a canonical circuit decomposition of a (G×H)-invariant quantum comb for compact groups G and H using the corresponding Clebsch--Gordan transforms, which naturally extends to the G-covariant quantum comb. By using this circuit decomposition, we propose a parametrized quantum comb with group symmetry, and derive the optimal quantum comb which transforms an unknown unitary operation U∈SU(d) into its inverse U† or transpose U⊤. From numerics, we find a deterministic and exact unitary transposition protocol for d=3 with 7 queries to U. This protocol improves upon the protocol shown in the previous work, which requires 13 queries to U.
Transducers (Belovs, Jeffery and Yolcu, 2024) are a quantum computing framework describing a quantum algorithm as a unitary converting an input state into a target state using a catalyst, an auxiliary vector that is left unchanged. They are a powerful tool in quantum algorithm design, especially in the context of quantum query complexity: feasible points of the (dual) adversary semidefinite program directly translate into transducers and the optimal transduction complexity is equal to the adversary bound, i.e. the Las Vegas complexity, which is known to characterize bounded-error quantum query complexity. Moreover, contrary to bounded-error algorithms, transducers compose exactly, which limits overheads due to controlling errors in algorithms constructed by composition. Constructing efficient, let alone optimal, transducers in terms of quantum query complexity nevertheless remains a hard task since it still requires solving the adversary SDP and constructing the unitary to obtain an explicit algorithm. In this paper, we show how using the symmetry group of state-conversion problems simplifies both steps. First, using a symmetrization argument, we prove an optimal catalyst can always be chosen covariant under a representation of the symmetry group. Second, we prove that the transducer intertwines two different representations of the group and can thus be chosen block diagonal in the isotypic decomposition of the Hilbert space. Using those methods, we then derive optimal transducers, with optimal constants, for different widely used quantum algorithmic primitives, such as unstructured search, amplitude amplification and amplitude estimation. Our approach extends previous work on the use of representation theory to compute adversary lower bounds (Høyer, Lee, and {\v S}palek, 2007; Ambainis, Magnin, Roetteler and Roland, 2011) to the systematic construction of optimal algorithms.
This paper addresses the problem of designing universal quantum circuits to transform k uses of a d-dimensional unitary input operation into a unitary output operation in a probabilistic heralded manner. Three classes of protocols are considered, parallel circuits, where the input operations can be performed simultaneously, adaptive circuits, where sequential uses of the input operations are allowed, and general protocols, where the use of the input operations may be performed without a definite causal order. For these three classes, we develop a systematic semidefinite programming approach that finds a circuit which obtains the desired transformation with the maximal success probability. We then analyze in detail three particular transformations: unitary transposition, unitary complex conjugation, and unitary inversion. For unitary transposition and unitary inverse, we prove that for any fixed dimension d, adaptive circuits have an exponential improvement in terms of uses k when compared to parallel ones. For unitary complex conjugation and unitary inversion we prove that if the number of uses k is strictly smaller than $d\ensuremath{-}1$, the probability of success is necessarily zero. We also discuss the advantage of indefinite causal order protocols over causal ones and introduce the concept of delayed input-state quantum circuits.
Polynomial transformations of data encoded in quantum operations are a building block of quantum algorithms, and their query complexity measures how often those operations are used. For multiple variables, existing methods either realize restricted polynomial families or implement monomials separately at a query cost exponential in the number of variables. We present a quantum circuit that implements every multivariate trigonometric polynomial up to an explicit normalization. The circuit processes one variable coherently over the frequency components of the remaining variables, allowing all components to share the same signal queries. Each variable is queried exactly as many times as its degree in the polynomial, and we prove that this query complexity is optimal. We further extend the construction to commuting unitaries. The resulting circuit applies the multivariate polynomial simultaneously across their shared eigenbasis, using the minimum numbers of forward and inverse queries to each unitary. We also study trainable rotations with fixed preparation and a local readout of the last input. At query depth at least two, independent uniform initialization gives every active readout gradient a variance lower bound set by its squared branch weight and the inverse square root of the depth, uniformly over data states and dimensions. For supervised squared loss, retaining sample correlations gives an initialization gradient-variance bound in terms of targets and input spectra. This also bounds the expected loss decrease after the first exact gradient step with a specified step size. These results provide a scalable and practical solution for developing multivariate quantum algorithms and quantum learning models.