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

This seminar, given by Satoshi Yoshida, will happend on 21 May 2025, at 14:0. It will take place in Room Not specified.

Find a map of the campus here.

Abstract

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