Optimising Matrix Product State Simulations of Shor’s Algorithm

Aidan Dang, Charles D. Hill, and Lloyd C. L. Hollenberg

Centre for Quantum Computation and Communication Technology, School of Physics, The University of Melbourne, Parkville, Victoria 3010, Australia

We detail techniques to optimise high-level classical simulations of Shor's quantum factoring algorithm. Chief among these is to examine the entangling properties of the circuit and to effectively map it across the one-dimensional structure of a matrix product state. Compared to previous approaches whose space requirements depend on $r$, the solution to the underlying order-finding problem of Shor's algorithm, our approach depends on its factors. We performed a matrix product state simulation of a 60-qubit instance of Shor's algorithm that would otherwise be infeasible to complete without an optimised entanglement mapping.

► BibTeX data

► References

[1] S. Aaronson and A. Arkhipov, in STOC '11 Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing (ACM, New York, 2011) pp. 333-342.
https://doi.org/10.1145/1993636.1993682

[2] M. J. Bremner, R. Jozsa, and D. J. Shepherd, Proc. Royal Soc. A 467, 459 (2011).
https://doi.org/10.1098/rspa.2010.0301

[3] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Nat. Phys. 14, 595 (2018).
https://doi.org/10.1038/s41567-018-0124-x

[4] S. Bravyi and D. Gosset, Phys. Rev. Lett. 116, 250501 (2016).
https://doi.org/10.1103/PhysRevLett.116.250501

[5] E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, T. Magerlein, E. Solomonik, and R. Wisnieff, (2017), arXiv:1710.05867.
arXiv:1710.05867

[6] P. W. Shor, SIAM J. Comput. 26, 1484 (1997).
https://doi.org/10.1137/S0097539795293172

[7] R. L. Rivest, A. Shamir, and L. Adleman, Commun. ACM 21, 120 (1978).
https://doi.org/10.1145/359340.359342

[8] T. Dierks and E. Rescorla, The Transport Layer Security (TLS) Protocol Version 1.2, RFC 5246 (RFC Editor, 2008).
https://doi.org/10.17487/RFC5246

[9] D. J. Bernstein, ``Introduction to post-quantum cryptography,'' in Post-Quantum Cryptography, edited by D. J. Bernstein, J. Buchmann, and E. Dahmen (Springer Berlin Heidelberg, Berlin, Heidelberg, 2009) pp. 1-14.
https://doi.org/10.1007/978-3-540-88702-7_1

[10] L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang, Nature 414, 883 (2001).
https://doi.org/10.1038/414883a

[11] B. P. Lanyon, T. J. Weinhold, N. K. Langford, M. Barbieri, D. F. V. James, A. Gilchrist, and A. G. White, Phys. Rev. Lett. 99, 250505 (2007).
https://doi.org/10.1103/PhysRevLett.99.250505

[12] C.-Y. Lu, D. E. Browne, T. Yang, and J.-W. Pan, Phys. Rev. Lett. 99, 250504 (2007).
https://doi.org/10.1103/PhysRevLett.99.250504

[13] E. Lucero, R. Barends, Y. Chen, J. Kelly, M. Mariantoni, A. Megrant, P. O'Malley, D. Sank, A. Vainsencher, J. Wenner, T. White, Y. Yin, A. N. Cleland, and J. M. Martinis, Nat. Phys. 8, 719 (2012).
https://doi.org/10.1038/nphys2385

[14] D. S. Wang, C. D. Hill, and L. C. L. Hollenberg, Quantum Inf. Process. 16, 176 (2017).
https://doi.org/10.1007/s11128-017-1587-x

[15] G. Vidal, Phys. Rev. Lett. 91, 147902 (2003).
https://doi.org/10.1103/PhysRevLett.91.147902

[16] R. Orús, Ann. Phys. (N. Y.) 349, 117 (2014).
https://doi.org/10.1016/j.aop.2014.06.013

[17] U. Schollwöck, Ann. Phys. (N. Y.) 326, 96 (2011).
https://doi.org/10.1016/j.aop.2010.09.012

[18] G. Vidal, Phys. Rev. Lett. 98, 070201 (2007a).
https://doi.org/10.1103/PhysRevLett.98.070201

[19] K. J. Woolfe, C. D. Hill, and L. C. L. Hollenberg, Quantum Inf. Comput. 17, 1 (2017).
https://doi.org/10.26421/QIC17.1-2

[20] F. Verstraete and J. I. Cirac, (2004), arXiv:cond-mat/​0407066.
arXiv:cond-mat/0407066

[21] G. Vidal, Phys. Rev. Lett. 99, 220405 (2007b).
https://doi.org/10.1103/PhysRevLett.99.220405

[22] E. Dumitrescu, Phys. Rev. A 96, 062322 (2017).
https://doi.org/10.1103/PhysRevA.96.062322

[23] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary ed. (Cambridge University Press, Cambridge, 2010).
https://doi.org/10.1017/CBO9780511976667

[24] W. Szpankowski and V. Rego, Computing 43, 401 (1990).
https://doi.org/10.1007/BF02241658

[25] R. Orús and J. I. Latorre, Phys. Rev. A 69, 052308 (2004).
https://doi.org/10.1103/PhysRevA.69.052308

[26] M. Frigo, SIGPLAN Not. 39, 642 (2004).
https://doi.org/10.1145/989393.989457

[27] J. Poulson, B. Marker, R. A. van de Geijn, J. R. Hammond, and N. A. Romero, ACM Trans. Math. Softw. 39, 13:1 (2013).
https://doi.org/10.1145/2427023.2427030

[28] E. R. Jessup and D. C. Sorensen, SIAM J. Matrix Anal. Appl. 15, 530 (1994).
https://doi.org/10.1137/S089547989120195X

[29] E. Anderson, Z. Bai, C. Bischof, L. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen, LAPACK Users' Guide, Third ed. (Society for Industrial and Applied Mathematics, Philadelphia, 1999).
https://doi.org/10.1137/1.9780898719604

[30] R. L. Graham, T. S. Woodall, and J. M. Squyres, in Parallel Processing and Applied Mathematics: 6th International Conference, PPAM 2005, Poznań, Poland, September 11-14, 2005, Revised Selected Papers, edited by R. Wyrzykowski, J. Dongarra, N. Meyer, and J. Waśniewski (Springer Berlin Heidelberg, Berlin, Heidelberg, 2006) pp. 228-239.
https://doi.org/10.1007/11752578_29

[31] ``The Pawsey Supercomputing Centre,'' https:/​/​www.pawsey.org.au/​ (2017).
https:/​/​www.pawsey.org.au/​

[32] Q. Wang, X. Zhang, Y. Zhang, and Q. Yi, in SC '13 Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis (ACM, New York, 2013) pp. 25:1-25:12.
https://doi.org/10.1145/2503210.2503219

Cited by

[1] Alexander McCaskey, Eugene Dumitrescu, Mengsu Chen, Dmitry Lyakh, and Travis Humble, "Validating quantum-classical programming models with tensor network simulations", PLoS ONE 13 12, e0206704 (2018).

The above citations are from SAO/NASA ADS (last updated 2019-04-25 21:30:38). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2019-04-25 20:51:45).