Reversible reciprocal circuits

This page lists the benchmarks for the reversible reciprocal circuits reported in

Mathias Soeken, Martin Roetteler, Nathan Wiebe, and Giovanni De Micheli: Design automation and design space exploration for quantum computers, Design Automation and Test in Europe, 2017.

Results with Symbolic Functional Reversible Synthesis

	`INTDIV` ( n )			`NEWTON` ( n )
n	qubits	T count	files	qubits	T count	files
4	7	597	Verilog · PLA · REAL	7	589	Verilog · PLA · REAL
5	9	1613	Verilog · PLA · REAL	9	1848	Verilog · PLA · REAL
6	11	5963	Verilog · PLA · REAL	11	6419	Verilog · PLA · REAL
7	13	20008	Verilog · PLA · REAL	13	17867	Verilog · PLA · REAL
8	15	51386	Verilog · PLA · REAL	15	56379	Verilog · PLA · REAL
9	17	142901	Verilog · PLA · REAL	17	148913	Verilog · PLA · REAL
10	19	380009	Verilog · PLA · REAL	19	383891	Verilog · PLA · REAL
11	21	946724	Verilog · PLA · REAL	21	945117	Verilog · PLA · REAL
12	23	2318841	Verilog · PLA · REAL	23	2346319	Verilog · PLA · REAL
13	25	5599538	Verilog · PLA · REAL	25	5645530	Verilog · PLA · REAL
14	27	13148102	Verilog · PLA · REAL	27	13186076	Verilog · PLA · REAL
15	29	30761399	Verilog · PLA · REAL	29	30746528	Verilog · PLA · REAL
16	31	71155258	Verilog · PLA · REAL	31	71259272	Verilog · PLA · REAL

The PLA files have been generated using the ABC commands clp and satclp . The NEWTON designs have been parsed using Yosys and translated into BLIF files to be read with ABC. We used the command stbs -s in RevKit to generate reversible circuit realizations (REAL files). The command gen_reciprocal (see details here ) in RevKit can be used to execute the whole flow (requires to have abc and yosys executables in the $PATH ):

# [N] is a placeholder for the bitwidth
# INTDIV design (-a 0)
gen_reciprocal -a 0 -m 1 --verilog_name rec[N].v --pla_name rec[N].pla [N]
ps -c
write_real rec[N].real

# NEWTON design (-a 1)
gen_reciprocal -a 1 -m 1 --verilog_name rec[N].v --pla_name rec[N].pla [N]
ps -c
write_real rec[N].real

Results with REVS

Info The Verilog (V) and ESOP (E) files are the same for the flows with p = 0 and p = 1

	`INTDIV` ( n ), p = 0			`NEWTON` ( n ), p = 0			`INTDIV` ( n ), p = 1			`NEWTON` ( n ), p = 1
n	qubits	T count	files	qubits	T count	files	qubits	T count	files	qubits	T count	files
5	10	232	V · E · R	10	135	V · E · R	12	241	R	10	135	R
6	12	423	V · E · R	12	294	V · E · R	14	411	R	13	268	R
7	14	791	V · E · R	14	568	V · E · R	17	803	R	17	511	R
8	16	1342	V · E · R	16	1039	V · E · R	20	1349	R	20	1060	R
9	18	2056	V · E · R	18	1894	V · E · R	23	2359	R	22	1850	R
10	20	3415	V · E · R	20	3311	V · E · R	23	3238	R	24	3071	R
11	22	5631	V · E · R	22	5303	V · E · R	29	5244	R	27	4846	R
12	24	8431	V · E · R	24	8423	V · E · R	30	7700	R	29	7136	R
13	26	13414	V · E · R	26	14287	V · E · R	31	11474	R	32	11988	R
14	28	21902	V · E · R	28	21782	V · E · R	37	19063	R	34	19186	R
15	30	33502	V · E · R	30	34815	V · E · R	35	27897	R	37	28635	R
16	32	52376	V · E · R	32	50784	V · E · R	46	42717	R	38	41532	R
17	34	78470	V · E · R	34	95462	V · E · R	41	64089	R	43	76022	R
18	36	119510	V · E · R	36	153414	V · E · R	43	94577	R	44	119657	R
19	38	179095	V · E · R	38	229768	V · E · R	46	138912	R	46	175598	R
20	40	284118	V · E · R	40	349398	V · E · R	48	218341	R	47	263106	R
21	42	422806	V · E · R	42	552496	V · E · R	51	318627	R	51	412488	R
22	44	640351	V · E · R	44	837646	V · E · R	52	476603	R	53	616065	R
23	46	941408	V · E · R	46	1249894	V · E · R	56	684166	R	56	909364	R
24	48	1417327	V · E · R	48	1885742	V · E · R	57	1021041	R	58	1344400	R
25	50	2119663	V · E · R	50	2819902	V · E · R	60	1512893	R	60	1985367	R

The following command in RevKit can be used to execute the whole flow (the flow requires to have abc and yosys executables in the $https://documents.epfl.ch/users/s/so/soeken/www/reciprocals ):

# [N] is a placeholder for the bitwidth
# INTDIV design (-a 0)
gen_reciprocal -a 0 -m 0 --verilog_name rec[N].v --pla_name rec[N].pla [N]
ps -c
write_real rec[N].real

# NEWTON design (-a 1)
gen_reciprocal -a 1 -m 0 --verilog_name rec[N].v --pla_name rec[N].pla [N]
ps -c
write_real rec[N].real

Results with Hierarchical Synthesis

	`INTDIV` ( n )			`NEWTON` ( n )
n	qubits	T count	files	qubits	T count	files
16	892	5607	Verilog · XMG · REAL	10713	73080	Verilog · XMG · REAL
32	3501	21455	Verilog · XMG · REAL	56207	392917	Verilog · XMG · REAL
64	13465	80339	Verilog · XMG · REAL	178653	1264704	Verilog · XMG · REAL
128	51897	308364	Verilog · XMG · REAL	1029441	7033040	Verilog · XMG · REAL

The following script that involves calls to RevKit, ABC and CirKit has been used to generate the circuits. Here, we show the scripts to generate the INTDIV design. Change -a 0 in the gen_reciprocal command to -a 1 to use the NEWTON design.

# [N] is a placeholder for the bitwidth
# RevKit
gen_reciprocal -a 0 --verilog_name rec[N] --only_write [N]
quit

# Use ABC resyn2 iteratively (until no more improvement) to translate Verilog into AIG rec[N].aig
%read rec[N].v
%blast
&put
resyn2; print_stats
resyn2; print_stats
...
write rec[N].aig

# CirKit
read_aiger rec[N].aig
xmglut -k 4
write_verilog -x rec[N].xmg.v
quit

# RevKit
read_verilog -x rec[N].xmg.v
dxs
ps -c
write_real rec[N].real