Benchmark Results

To demonstrate the practical usefulness of QuIDDPro, it has been compared with a number of simulation methods which all utilize explicit vectors and matrices. Results for simulation with the density matrix model are provided for a number of quantum circuit benchmarks. Results for simulation with the state vector model are provided for instances of Grover’s quantum search algorithm with up to 40 qubits. As the results indicate, QuIDDPro far outperforms the explicit vector/matrix methods. It is also worth noting that stabilizer circuit simulation [8] cannot efficiently simulate most of the density matrix benchmarks or the instances of Grover’s quantum search algorithm.

Density Matrix Results

The benchmarks used are representative of quantum circuit applications in reversible logicquantum communication, quantum error correction, and quantum search. For each benchmark, QuIDDPro is compared with one of the best-known density matrix simulators that uses explicit matrices, QCSim [6]. Any simulator which uses explicit matrices will have similar performance to QCSim. These results are reproduced from [3]. > 2GB indicates that a memory usage cutoff of 2GB was exceeded and therefore simulation could not be finished. The results were obtained by running each simulator on a dual processor Intel Xeon workstation running Linux. All of the benchmarks, in addition to other circuit descriptions, are bundled with the QuIDDPro simulator software.

Performance results for QuIDDPro and QCSim on the reversible logic benchmarks. > 2GB indicates that a memory usage cutoff of 2GB was exceeded and simulation was terminated.
Benchmark No. of Qubits No. of Gates QuIDDPro QCSim
Runtime (s) Peak Memory (MB) Runtime (s) Peak Memory (MB)
rc_adder1 16 24 0.44 0.0625 N/A > 2GB
rc_adder2 16 24 0.44 0.0625 N/A > 2GB
rc_adder3 16 24 0.44 0.0625 N/A > 2GB
rc_adder4 16 24 0.44 0.0625 N/A > 2GB
9sym1 12 29 0.2 0.0586 8.01 128.1
9sym2 12 29 0.2 0.0586 8.02 128.1
9sym3 12 29 0.2 0.0586 8.04 128.1
9sym4 12 29 0.2 0.0586 8 128.1
9sym5 12 29 0.2 0.0586 7.95 128.1
ham15_1 15 148 1.99 0.121 N/A > 2GB
ham15_2 15 148 2.01 0.121 N/A > 2GB
ham15_3 15 148 1.99 0.121 N/A > 2GB

 

Performance results for QuIDDPro and QCSim on the quantum error correction and quantum communication benchmarks. > 2GB indicates that a memory usage cutoff of 2GB was exceeded and simulation was terminated.
Benchmark No. of Qubits No. of Gates QuIDDPro QCSim
Runtime (s) Peak Memory (MB) Runtime (s) Peak Memory (MB)
steaneZ 13 143 0.6 0.672 287 512
steaneX 12 120 0.27 0.68 53.2 128
hadder_bf1 24 49 18.3 1.48 N/A > 2GB
hadder_bf2 24 49 18.7 1.48 N/A > 2GB
hadder_bf3 24 49 18.7 1.48 N/A > 2GB
hadder_pf1 24 51 21.2 1.50 N/A > 2GB
hadder_pf2 24 51 21.2 1.50 N/A > 2GB
hadder_pf3 24 51 20.7 1.50 N/A > 2GB
grover_s1 24 50 2301 94.2 N/A > 2GB
grover_s_bf1 24 71 2208 94.3 N/A > 2GB
grover_s_pf1 24 73 2258 94.2 N/A > 2GB
bb84Eve 9 26 0.02 0.129 0.19 2.0
bb84NoEve 7 14 < 0.01 0.0313 < 0.01 0.152

 

Performance results for QuIDDPro and QCSim on the quantum search benchmark. The number of qubits (and therefore the search space) is increased in each instance. The oracle used in every instance finds one item in the search space. > 2GB indicates that a memory usage cutoff of 2GB was exceeded and simulation was terminated.
No. of Qubits No. of Gates QuIDDPro QCSim
Runtime (s) Peak Memory (MB) Runtime (s) Peak Memory (MB)
5 32 0.05 0.0234 0.01 0.00781
6 50 0.07 0.0391 0.01 0.0352
7 84 0.11 0.043 0.08 0.152
8 126 0.16 0.0586 0.54 0.625
9 208 0.27 0.0742 3.64 2.50
10 324 0.42 0.0742 23.2 10.0
11 520 0.66 0.0898 151 40.0
12 792 1.03 0.105 933 160
13 1224 1.52 0.141 5900 640
14 1872 2.41 0.125 N/A > 2GB
15 2828 3.62 0.129 N/A > 2GB
16 4290 5.55 0.145 N/A > 2GB
17 6464 8.29 0.152 N/A > 2GB
18 9690 12.7 0.246 N/A > 2GB
19 14508 18.8 0.199 N/A > 2GB
20 21622 28.9 0.203 N/A > 2GB

State Vector Results

Using instances of Grover’s quantum search algorithm up to 40 qubits in size, QuIDDPro has been compared with three different implementations of state vector simulation which all use explicit vectors and clever matrix multiplication techniques that avoid explicit creation of the operator (gate) matrices. Performance results are provided for 10 to 40 qubit instances of Grover’s quantum search algorithm with two different oracles. Oracle 1 is an oracle which finds one element in the search space, and Oracle 2 is a “mod-1024” oracle which finds elements whose ten least significant index bits are 1. “Octave” indicates performance results for an Octave implementation, “Matlab” indicates performance results for a Matlab implementation, and “Blitz++” indicates performance results for a C++ implementation which uses the Blitz++ library. Any simulator which uses explicit matrices will have similar performance to the Blitz++ implementation if it is compiled, or it will have similar performance to the Matlab and Octave implementations if it is interpreted. These results are reproduced from [4]. > 24hrs indicates that a runtime cutoff of 24 hours was exceeded. > 1.5GB indicates that a memory usage cutoff of 1.5GB was exceeded. If any simulation method exceeded either cutoff, simulation was terminated. NA indicates that after one week of running, the memory usage was still steadily growing, preventing a peak memory usage measurement. The results were obtained by running each simulation method on a dual processor Intel Xeon workstation running linux.

 

Performance results for QuIDDPro, Blitz++, Matlab, and Octave on the quantum search benchmark using Oracle 1. The number of qubits (and therefore the search space) is increased in each instance. > 24hrs indicates that a runtime cutoff of 24 hours was exceeded, while > 1.5GB indicates that a memory usage cutoff of 1.5GB was exceeded. If either or both cutoffs were exceeded, simulation was terminated. NA indicates that after one week of running, the memory usage was still steadily growing, preventing a peak memory usage measurement.
No. of Qubits QuIDDPro Blitz++ Matlab Octave
Runtime (s) Peak Memory (MB) Runtime (s) Peak Memory (MB) Runtime (s) Peak Memory (MB) Runtime (s) Peak Memory (MB)
10 0.33 9.38e-2 0.15 3.52e-2 6.64 1.05e-2 80.6 2.64e-2
11 0.54 0.121 0.48 8.20e-2 22.5 2.07e-2 2.65e2 5.47e-2
12 0.83 0.137 1.49 0.176 74.2 4.12e-2 8.36e2 0.105
13 1.30 0.137 4.70 0.309 2.55e2 8.22e-2 2.75e3 0.213
14 2.01 0.137 14.6 0.559 1.06e3 0.164 1.03e4 0.426
15 3.09 0.137 44.7 1.06 6.76e3 0.328 4.82e4 0.837
16 4.79 0.145 1.35e2 2.06 > 24hrs 0.656 > 24hrs 1.74
17 7.36 0.172 4.09e2 4.06 > 24hrs 1.31 > 24hrs 3.34
18 11.3 0.172 1.23e3 8.06 > 24hrs 2.62 > 24hrs 4.59
19 17.1 0.172 3.67e3 16.1 > 24hrs 5.24 > 24hrs 13.4
20 26.2 0.172 1.09e4 32.1 > 24hrs 10.5 > 24hrs 27.8
21 39.7 0.195 3.26e4 64.1 > 24hrs N/A > 24hrs 55.6
22 60.5 0.207 > 24hrs 1.28e2 > 24hrs N/A > 24hrs N/A
23 92.7 0.207 > 24hrs 2.56e2 > 24hrs N/A > 24hrs N/A
24 1.40e2 0.223 > 24hrs 5.12e2 > 24hrs N/A > 24hrs N/A
25 2.08e2 0.230 > 24hrs 1.02e3 > 24hrs N/A > 24hrs N/A
26 3.12e2 0.238 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
27 4.72e2 0.254 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
28 7.07e2 0.262 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
29 1.08e3 0.277 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
30 1.57e3 0.297 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
31 2.35e3 0.301 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
32 3.53e3 0.305 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
33 5.23e3 0.320 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
34 7.90e3 0.324 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
35 1.15e4 0.348 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
36 1.71e4 0.352 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
37 2.57e4 0.371 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
38 3.82e4 0.375 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
39 5.64e4 0.395 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A
40 8.23e4 0.398 > 24hrs > 1.5GB > 24hrs N/A > 24hrs N/A

 

Performance results for QuIDDPro, Blitz++, Matlab, and Octave on the quantum search benchmark using Oracle 2. The number of qubits (and therefore the search space) is increased in each instance. > 24hrs indicates that a runtime cutoff of 24 hours was exceeded, while > 1.5GB indicates that a memory usage cutoff of 1.5GB was exceeded. If either or both cutoffs were exceeded, simulation was terminated. NA indicates that after one week of running, the memory usage was still steadily growing, preventing a peak memory usage measurement.
No. of Qubits QuIDDPro Blitz++ Matlab Octave
Runtime (s) Peak Memory (MB) Runtime (s) Peak Memory (MB) Runtime (s) Peak Memory (MB) Runtime (s) Peak Memory (MB)
13 0.617 0.137 2.47 0.252 1.31e2 8.22e-2 1.39e3 0.218
14 0.662 0.141 5.42 0.563 7.26e2 0.164 3.75e3 0.436
15 0.705 0.145 11.7 1.06 4.27e3 0.328 1.11e4 0.873
16 0.756 0.172 24.9 2.06 2.23e4 0.656 3.70e4 1.74
17 0.805 0.176 53.4 4.06 > 24hrs 1.31 > 24hrs 3.34
18 0.863 0.180 1.13e2 8.06 > 24hrs 2.62 > 24hrs 4.59
19 0.910 0.180 2.39e2 16.1 > 24hrs 5.24 > 24hrs 13.4
20 0.965 0.195 5.15e2 32.1 > 24hrs 10.5 > 24hrs 27.8
21 1.03 0.199 1.14e3 64.1 > 24hrs N/A > 24hrs 55.6
22 1.09 0.207 2.25e3 1.28e2 > 24hrs N/A > 24hrs N/A
23 1.15 0.215 5.21e3 2.56e2 > 24hrs N/A > 24hrs N/A
24 1.21 0.227 1.02e4 5.12e2 > 24hrs N/A > 24hrs N/A
25 1.28 0.238 2.19e4 1.02e3 > 24hrs N/A > 24hrs N/A
26 1.35 0.246 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
27 1.41 0.256 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
28 1.49 0.266 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
29 1.55 0.297 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
30 1.63 0.301 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
31 1.71 0.305 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
32 1.78 0.324 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
33 1.86 0.328 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
34 1.94 0.348 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
35 2.03 0.352 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
36 2.12 0.375 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
37 2.21 0.375 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
38 2.29 0.395 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
39 2.37 0.398 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A
40 2.47 0.408 > 1.5GB > 1.5GB > 24hrs N/A > 24hrs N/A

Copyright © 2004, 2005, 2006, 2007 George F. ViamontesIgor L. MarkovJohn P. Hayes, and The Regents of the University of Michigan. All rights reserved.