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