Asymptotically optimal synthesis of reversible circuits
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910700210749440 |
|---|---|
| author | Li, Xian Wu Lvzhou |
| author_facet | Li, Xian Wu Lvzhou |
| contents | Reversible circuits have been studied extensively and intensively, and have plenty of applications in various areas, such as digital signal processing, cryptography, and especially quantum computing. In 2003, the lower bound $Ω(2^n n/\log n)$ for the synthesis of $n$-wire reversible circuits was proved. Whether this lower bound has a matching upper bound was listed as one of the future challenging open problems in the survey (M. Saeedi and I. L Markov, ACM Computing Surveys, 45(2):1-34, 2013). In this paper we propose an algorithm to implement an arbitrary $n$-wire reversible circuit with no more than $O(2^n n/\log n)$ elementary gates, and thus close the open problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_06074 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Asymptotically optimal synthesis of reversible circuits Li, Xian Wu Lvzhou Quantum Physics Reversible circuits have been studied extensively and intensively, and have plenty of applications in various areas, such as digital signal processing, cryptography, and especially quantum computing. In 2003, the lower bound $Ω(2^n n/\log n)$ for the synthesis of $n$-wire reversible circuits was proved. Whether this lower bound has a matching upper bound was listed as one of the future challenging open problems in the survey (M. Saeedi and I. L Markov, ACM Computing Surveys, 45(2):1-34, 2013). In this paper we propose an algorithm to implement an arbitrary $n$-wire reversible circuit with no more than $O(2^n n/\log n)$ elementary gates, and thus close the open problem. |
| title | Asymptotically optimal synthesis of reversible circuits |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2302.06074 |