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