Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913083840004096 |
|---|---|
| author | Rosenthal, Gregory |
| author_facet | Rosenthal, Gregory |
| contents | We prove that any $n$-qubit unitary can be implemented (i) approximately in time $\tilde O\big(2^{n/2}\big)$ with query access to an appropriate classical oracle, and also (ii) exactly by a circuit of depth $\tilde O\big(2^{n/2}\big)$ with one- and two-qubit gates and $2^{O(n)}$ ancillae. The proofs involve similar reductions to Grover search. The proof of (ii) also involves a linear-depth construction of arbitrary quantum states using one- and two-qubit gates (in fact, this can be improved to constant depth with the addition of fanout and generalized Toffoli gates) which may be of independent interest. We also prove a matching $Ω\big(2^{n/2}\big)$ lower bound for (i) and (ii) for a certain class of implementations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_07992 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Query and Depth Upper Bounds for Quantum Unitaries via Grover Search Rosenthal, Gregory Quantum Physics Computational Complexity We prove that any $n$-qubit unitary can be implemented (i) approximately in time $\tilde O\big(2^{n/2}\big)$ with query access to an appropriate classical oracle, and also (ii) exactly by a circuit of depth $\tilde O\big(2^{n/2}\big)$ with one- and two-qubit gates and $2^{O(n)}$ ancillae. The proofs involve similar reductions to Grover search. The proof of (ii) also involves a linear-depth construction of arbitrary quantum states using one- and two-qubit gates (in fact, this can be improved to constant depth with the addition of fanout and generalized Toffoli gates) which may be of independent interest. We also prove a matching $Ω\big(2^{n/2}\big)$ lower bound for (i) and (ii) for a certain class of implementations. |
| title | Query and Depth Upper Bounds for Quantum Unitaries via Grover Search |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2111.07992 |