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.

The benchmarks used are representative of quantum circuit
applications in **reversible logic**, **quantum 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.

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 |

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 |

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 |

Using intances 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 wich 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.

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 |

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. Viamontes, Igor L. Markov, John P. Hayes, and The Regents of the University of Michigan. All rights reserved.