Satoshi Yoshida - Analytical lower bound on query complexity for universal transformation of unitary operations

Analytical lower bound on query complexity for universal transformation of unitary operations

Ce séminaire, donné par Satoshi Yoshida, aura lieu le 21 May 2025, à 14:0. Il aura lieu en salle Not specified.

Vous trouverez un plan du campus ici.

Résumé

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 work, we establish analytical lower bounds for the query complexity of unitary inversion, transposition, and complex conjugation. 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) \to 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 probabilistic setting, where transformations must succeed with a certain probability, revealing a potential trade-off between the number of queries and the required success probability. Reference https://arxiv.org/abs/2405.07625