Introduction

Relation to
Other Techniques


Benchmark Results

What's New

User's Guide (.pdf)

Request Software

References

Quantum Circuits Group

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 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.


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_adder116240.440.0625N/A> 2GB
rc_adder216240.440.0625N/A> 2GB
rc_adder316240.440.0625N/A> 2GB
rc_adder416240.440.0625N/A> 2GB
9sym112290.20.05868.01128.1
9sym212290.20.05868.02128.1
9sym312290.20.05868.04128.1
9sym412290.20.05868128.1
9sym512290.20.05867.95128.1
ham15_1151481.990.121N/A> 2GB
ham15_2151482.010.121N/A> 2GB
ham15_3151481.990.121N/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)
steaneZ131430.60.672287512
steaneX121200.270.6853.2128
hadder_bf1244918.31.48N/A> 2GB
hadder_bf2244918.71.48N/A> 2GB
hadder_bf3244918.71.48N/A> 2GB
hadder_pf1245121.21.50N/A> 2GB
hadder_pf2245121.21.50N/A> 2GB
hadder_pf3245120.71.50N/A> 2GB
grover_s12450230194.2N/A> 2GB
grover_s_bf12471220894.3N/A> 2GB
grover_s_pf12473225894.2N/A> 2GB
bb84Eve9260.020.1290.192.0
bb84NoEve714< 0.010.0313< 0.010.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)
5320.050.02340.010.00781
6500.070.03910.010.0352
7840.110.0430.080.152
81260.160.05860.540.625
92080.270.07423.642.50
103240.420.074223.210.0
115200.660.089815140.0
127921.030.105933160
1312241.520.1415900640
1418722.410.125N/A> 2GB
1528283.620.129N/A> 2GB
1642905.550.145N/A> 2GB
1764648.290.152N/A> 2GB
18969012.70.246N/A> 2GB
191450818.80.199N/A> 2GB
202162228.90.203N/A> 2GB

State Vector Results

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.


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)
100.339.38e-20.153.52e-26.641.05e-280.62.64e-2
110.540.1210.488.20e-222.52.07e-22.65e25.47e-2
120.830.1371.490.17674.24.12e-28.36e20.105
131.300.1374.700.3092.55e28.22e-22.75e30.213
142.010.13714.60.5591.06e30.1641.03e40.426
153.090.13744.71.066.76e30.3284.82e40.837
164.790.1451.35e22.06> 24hrs0.656> 24hrs1.74
177.360.1724.09e24.06> 24hrs1.31> 24hrs3.34
1811.30.1721.23e38.06> 24hrs2.62> 24hrs4.59
1917.10.1723.67e316.1> 24hrs5.24> 24hrs13.4
2026.20.1721.09e432.1> 24hrs10.5> 24hrs27.8
2139.70.1953.26e464.1> 24hrsN/A> 24hrs55.6
2260.50.207> 24hrs1.28e2> 24hrsN/A> 24hrsN/A
2392.70.207> 24hrs2.56e2> 24hrsN/A> 24hrsN/A
241.40e20.223> 24hrs5.12e2> 24hrsN/A> 24hrsN/A
252.08e20.230> 24hrs1.02e3> 24hrsN/A> 24hrsN/A
263.12e20.238> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
274.72e20.254> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
287.07e20.262> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
291.08e30.277> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
301.57e30.297> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
312.35e30.301> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
323.53e30.305> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
335.23e30.320> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
347.90e30.324> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
351.15e40.348> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
361.71e40.352> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
372.57e40.371> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
383.82e40.375> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
395.64e40.395> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/A
408.23e40.398> 24hrs> 1.5GB> 24hrsN/A> 24hrsN/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)
130.6170.1372.470.2521.31e28.22e-21.39e30.218
140.6620.1415.420.5637.26e20.1643.75e30.436
150.7050.14511.71.064.27e30.3281.11e40.873
160.7560.17224.92.062.23e40.6563.70e41.74
170.8050.17653.44.06> 24hrs1.31> 24hrs3.34
180.8630.1801.13e28.06> 24hrs2.62> 24hrs4.59
190.9100.1802.39e216.1> 24hrs5.24> 24hrs13.4
200.9650.1955.15e232.1> 24hrs10.5> 24hrs27.8
211.030.1991.14e364.1> 24hrsN/A> 24hrs55.6
221.090.2072.25e31.28e2> 24hrsN/A> 24hrsN/A
231.150.2155.21e32.56e2> 24hrsN/A> 24hrsN/A
241.210.2271.02e45.12e2> 24hrsN/A> 24hrsN/A
251.280.2382.19e41.02e3> 24hrsN/A> 24hrsN/A
261.350.246> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
271.410.256> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
281.490.266> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
291.550.297> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
301.630.301> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
311.710.305> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
321.780.324> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
331.860.328> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
341.940.348> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
352.030.352> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
362.120.375> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
372.210.375> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
382.290.395> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
392.370.398> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/A
402.470.408> 1.5GB> 1.5GB> 24hrsN/A> 24hrsN/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.