Simulations of Shor’s algorithm using matrix product states. (English) Zbl 1373.81155
Summary: We show that under the matrix product state formalism the states produced in Shor’s algorithm can be represented using \(O(\max (4lr^2, 2^{2l}))\) space, where \(l\) is the number of bits in the number to factorise and \(r\) is the order and the solution to the related order-finding problem. The reduction in space compared to an amplitude formalism approach is significant, allowing simulations as large as 42 qubits to be run on a single processor with 32 GB RAM. This approach is readily adapted to a distributed memory environment, and we have simulated a 45-qubit case using 8 cores with 16 GB RAM in approximately 1 h.
MSC:
| 81P68 | Quantum computation |
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
| 11Y05 | Factorization |
References:
| [1] | Nielson, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000) · Zbl 1049.81015 |
| [2] | Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proc. 35th Annu. Symp. Found. of Comput. Sci., pp. 124-134 (1994) |
| [3] | Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484-1509 (1997) · Zbl 1005.11065 · doi:10.1137/S0097539795293172 |
| [4] | Obenland, K.M., Despain, A.M.: A parallel quantum computer simulator. Presented at High Performance Computing (1998) · Zbl 0940.81010 |
| [5] | Niwa, J., Matsumoto, K., Imai, H.: General-purpose parallel simulator for quantum computing. Phys. Rev. A 66, 062317 (2002) · Zbl 1029.68552 · doi:10.1103/PhysRevA.66.062317 |
| [6] | Tabakin, F., Juliá-Díaz, B.: Qcmpi: a parallel environment for quantum computing. Comput. Phys. Commun. 180, 948-964 (2009) · Zbl 1198.81023 · doi:10.1016/j.cpc.2008.11.021 |
| [7] | Raedt, K.D., Michielsen, K., Raedt, H.D., Trieu, B., Arnold, G., Richter, M., Lippert, T., Watanabe, H., Ito, N.: Massive parallel quantum computer simulator. Comput. Phys. Commun. 176, 121-136 (2007) · Zbl 1196.81094 · doi:10.1016/j.cpc.2006.08.007 |
| [8] | Helmholtz Association of German Research Centres, World record: Jülich supercomputer simulates quantum computer, Press release, retrieved from http://www2.fz-juelich.de/portal/index.php?cmd=show&index=163&mid=761 (2010) |
| [9] | Vidal, G.: Efficient classical simulation of slightly entangled quantum computations. Phys. Rev. Lett. 91, 147902-147905 (2003) · doi:10.1103/PhysRevLett.91.147902 |
| [10] | Sanz, M., Egusquiza, I.L., Di Candia, R., Saberi, H., Lamata, L., Solano, E.: Entanglement classification with matrix product states. Sci Rep 5, 1-5 (2015). doi:10.1038/srep30188 · doi:10.1038/srep30188 |
| [11] | Das, A., Chakrabarti, B.K.: Colloquium: quantum annealing and analog quantum computation. Rev. Mod. Phys. 80, 1061-1081 (2008) · Zbl 1205.81058 · doi:10.1103/RevModPhys.80.1061 |
| [12] | Dridi, R., Alghassi, H.: Prime factorization using quantum annealing and computational algebraic geometry, pp. 1-14 (2016). arXiv:1604.05796 |
| [13] | Coppersmith, D.: An approximate Fourier transform useful in quantum factoring, Tech. Rep. RC 19642, T. J. Watson Research Center, IBM Corporation (1994) |
| [14] | Zalka, C.: Fast versions of Shor’s quantum factoring algorithm, quant-ph/9806084 · Zbl 1152.81800 |
| [15] | Beauregard, S.: Circuit for Shor’s algorithm using 2n+3 qubits. Quantum Inf. Comput. 3, 175-185 (2003) · Zbl 1152.81676 |
| [16] | Orus, R.: A practical introduction to tensor networks: matrix product states and projected entangled pair states. Ann. Phys. 349, 117-158 (2014) · Zbl 1343.81003 · doi:10.1016/j.aop.2014.06.013 |
| [17] | Browne, D.E.: Efficient classical simulation of the quantum Fourier transform. New J. Phys. 9, 146 (2007) · doi:10.1088/1367-2630/9/5/146 |
| [18] | Yoran, N., Short, A.J.: Classical simulability and the significance of modular exponentiation in Shor’s algorithm. Phys. Rev. A 76, 060302(R) (2007) · doi:10.1103/PhysRevA.76.060302 |
| [19] | Jozsa, R., Linden, N.: On the role of entanglement in quantum-computational speed-up. Proc. R. Soc. Lond. A 459, 2011-2032 (2003) · Zbl 1092.81518 · doi:10.1098/rspa.2002.1097 |
| [20] | Message passing interface forum. http://www.mpi-forum.org/ |
| [21] | Parallel BLAS. http://www.netlib.org/scalapack/pblas_qref.html · Zbl 1029.68552 |
| [22] | Blackford, L.S., Choi, J., Cleary, A., D’Azevedo, E., Demmel, J., Dhillon, I., Dongarra, J., Hammarling, S., Henry, G., Petitet, A., Stanley, K., Walker, D., Whaley, R.C.: ScaLAPACK Users’ Guide. Society for Industrial and Applied Mathematics, Philadelphia (1997) · Zbl 0886.65022 · doi:10.1137/1.9780898719642 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
