2024/05/13 by Tatsuki Odake, Satoshi Yoshida, Odake, Tatsuki +3 · 4 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Complexity and Algorithms in Graphs #DNA and Biological Computing #Distributed systems and fault tolerance #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2405.07625
openalex publication_date 2024/05/13 · openalex created_date 2024/05/15 · openalex updated_date 2026/07/28
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, which hold even if the input unitary is an unknown logarithmic-depth unitary. Specifically, our lower bound of d2 for unitary inversion demonstrates the asymptotic optimality of the deterministic exact inversion protocol, which operates with O(d2) 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.