Name
Abstract | ||
|---|---|---|
This paper presents an important result addressing a fundamental question in synthesizing binary reversible logic circuits for quantum computation. We show that any even-reversible-circuit of n (n3) qubits can be realized using NOT gate and Toffoli gate (‘2’-Controlled-Not gate), where the numbers of Toffoli and NOT gates required in the realization are bounded by $(n + \lfloor \frac{n}{3} \rfloor)(3 \times 2^{2n-3}-2^{n+2})$ and $4n(n + \lfloor \frac{n}{3} \rfloor)2^n$, respectively. A provable constructive synthesis algorithm is derived. The time complexity of the algorithm is $\frac{10}{3}n^2 \cdot 2^n$. Our algorithm is exponentially lower than breadth-first search based synthesis algorithms with respect to space and time complexities. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11750321_35 | TAMC |
Keywords | Field | DocType |
binary reversible logic circuit,synthesis algorithm,group theory,important result,provable constructive synthesis algorithm,quantum computation,fundamental question,breadth-first search,binary reversible circuit,toffoli gate,time complexity,controlled-not gate,breadth first search | Discrete mathematics,Combinatorics,Logic gate,Group theory,Quantum computer,Quantum logic,Time complexity,Mathematics,Binary number,Toffoli gate,Bounded function | Conference |
Volume | ISSN | ISBN |
3959 | 0302-9743 | 3-540-34021-1 |
Citations | PageRank | References |
12 | 0.84 | 8 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guowu Yang | 1 | 309 | 42.99 |
| Xiaoyu Song | 2 | 318 | 46.99 |
| William N. N. Hung | 3 | 304 | 34.98 |
| Fei Xie | 4 | 213 | 18.85 |
| Marek A. Perkowski | 5 | 809 | 118.04 |