Analytical Lower Bound on Query Complexity for Transformations of Unknown Unitary Operations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918234840629248 |
|---|---|
| author | Odake, Tatsuki Yoshida, Satoshi Murao, Mio |
| author_facet | Odake, Tatsuki Yoshida, Satoshi Murao, Mio |
| contents | 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 $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: \mathrm{SU}(d)\to \mathrm{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 $\mathrm{SU}(d)$ and the probabilistic setting, where transformations succeed probabilistically. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_07625 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Analytical Lower Bound on Query Complexity for Transformations of Unknown Unitary Operations Odake, Tatsuki Yoshida, Satoshi Murao, Mio Quantum Physics 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 $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: \mathrm{SU}(d)\to \mathrm{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 $\mathrm{SU}(d)$ and the probabilistic setting, where transformations succeed probabilistically. |
| title | Analytical Lower Bound on Query Complexity for Transformations of Unknown Unitary Operations |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2405.07625 |