Name
Abstract | ||
|---|---|---|
Reversible circuits play an important role in quantum computing. This paper studies the realization problem of reversible circuits. For any n-bit reversible function, we present a constructive synthesis algorithm. Given any n-bit reversible function, there are N distinct input patterns different from their corresponding outputs, where N@?2^n, and the other (2^n-N) input patterns will be the same as their outputs. We show that this circuit can be synthesized by at most 2n@?N '(n-1)'-CNOT gates and 4n^2@?N NOT gates. The time and space complexities of the algorithm are @W(n@?4^n) and @W(n@?2^n), respectively. The computational complexity of our synthesis algorithm is exponentially lower than that of breadth-first search based synthesis algorithms. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.tcs.2010.11.031 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
input pattern,CNOT gate,Group theory,reversible circuit,n-bit reversible function,constructive synthesis algorithm,breadth-first search,corresponding output,synthesis algorithm,Permutation,N distinct input pattern,computational complexity,Reversible logic | Journal | 412 |
Issue | ISSN | Citations |
17 | Theoretical Computer Science | 2 |
PageRank | References | Authors |
0.39 | 10 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guowu Yang | 1 | 309 | 42.99 |
| Fei Xie | 2 | 213 | 18.85 |
| William N. N. Hung | 3 | 304 | 34.98 |
| Xiaoyu Song | 4 | 318 | 46.99 |
| Marek A. Perkowski | 5 | 809 | 118.04 |