Research progress in reversible circuit synthesis and optimization

WU Xian; FENG Shiguang; LI Lyuzhou

doi:10.3969/j.issn.1007-5461.2024.04.001

Chinese Journal of Quantum Electronics, Volume. 41, Issue 4, 565(2024)

Research progress in reversible circuit synthesis and optimization

WU Xian... FENG Shiguang* and LI Lyuzhou |Show fewer author(s)

Author Affiliations

School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510006, China

show less

Abstract Get PDF(in Chinese)

Figures & Tables(2)

Fig. 1. A CNOT circuit with $n$ qubits

Download full size

View in Article

Table 1. Comparison between the metrics of two types of reversible circuits

View table

View in Article

Table 1. Comparison between the metrics of two types of reversible circuits

Metric	Linear reversible circuits	General reversible circuits
Lower bound of size	$Ω (\frac{n^{2}}{l o g n})$ ^[9]	$Ω (\frac{2^{n} n}{l o g n})$ ^[10]
Upper bound of size	$O (\frac{n^{2}}{l o g n})$ ^[9,11]	$O (\frac{2^{n} n}{l o g n})$ ^[12,13]
Lower bound of depth (without ancilla)	$Ω (\frac{n}{l o g n})$ ^[9,11]	$Ω (\frac{2^{n}}{l o g n})$ ^[12,13]
Existing upper bound of depth (without ancilla)	$O (\frac{n}{l o g n})$ ^[14]	$O (\frac{2^{n} n}{l o g n})$ ^[12,13]
Lower bound of depth (with $m$ ancillae)	$Ω (\frac{n^{2}}{(n + m) l o g (n + m)})$ ^[14]	-
Existing upper bound of depth (with $m$ ancillae)	$O (m a x \{l o g n, \frac{n^{2}}{(n + m) l o g (n + m)}\})$ ^[14]	-
Lower bound of depth (with arbitrary ancillae)	$Ω (l o g n)$ ^[14]	-
Existing upper bound of depth (with arbitrary ancillae)	$O (l o g n)$ ^[14]	$O (p o l y (n))$ ^[15]

Tools

Get Citation

Copy Citation Text

Xian WU, Shiguang FENG, Lyuzhou LI. Research progress in reversible circuit synthesis and optimization[J]. Chinese Journal of Quantum Electronics, 2024, 41(4): 565

Download Citation

EndNote(RIS)BibTex Plain Text

Set citation alerts for article

Save article for my favorites