Optimising Matrix Product State Simulations of Shor's Algorithm

Aidan Dang; Charles D. Hill; Lloyd C. L. Hollenberg

doi:10.22331/q-2019-01-25-116

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

Published:	2019-01-25, volume 3, page 116
Eprint:	arXiv:1712.07311v4
Doi:	https://doi.org/10.22331/q-2019-01-25-116
Citation:	Quantum 3, 116 (2019).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

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.

Featured image: Application of a nearest-neighbour gate on two qudits to a matrix product state in canonical form.

► BibTeX data

@article{Dang2019optimisingmatrix,
  doi = {10.22331/q-2019-01-25-116},
  url = {https://doi.org/10.22331/q-2019-01-25-116},
  title = {Optimising {M}atrix {P}roduct {S}tate {S}imulations of {S}hor's {A}lgorithm},
  author = {Dang, Aidan and Hill, Charles D. and Hollenberg, Lloyd C. L.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {3},
  pages = {116},
  month = jan,
  year = {2019}
}

► 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] Thien Nguyen, Dmitry Lyakh, Eugene Dumitrescu, David Clark, Jeff Larkin, and Alexander McCaskey, "Tensor Network Quantum Virtual Machine for Simulating Quantum Circuits at Exascale", ACM Transactions on Quantum Computing 4 1, 1 (2023).

[2] Honghui Shang, Li Shen, Yi Fan, Zhiqian Xu, Chu Guo, Jie Liu, Wenhao Zhou, Huan Ma, Rongfen Lin, Yuling Yang, Fang Li, Zhuoya Wang, Yunquan Zhang, and Zhenyu Li, SC22: International Conference for High Performance Computing, Networking, Storage and Analysis 1 (2022) ISBN:978-1-6654-5444-5.

[3] Dennis Willsch, Madita Willsch, Fengping Jin, Hans De Raedt, and Kristel Michielsen, "Large-Scale Simulation of Shor’s Quantum Factoring Algorithm", Mathematics 11 19, 4222 (2023).

[4] Kouichi Okunishi, Tomotoshi Nishino, and Hiroshi Ueda, "Developments in the Tensor Network — from Statistical Mechanics to Quantum Entanglement", Journal of the Physical Society of Japan 91 6, 062001 (2022).

[5] Maxime Dupont, Nicolas Didier, Mark J. Hodson, Joel E. Moore, and Matthew J. Reagor, "Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm", PRX Quantum 3 4, 040339 (2022).

[6] Andrés Gómez, Álvaro Leitao, Alberto Manzano, Daniele Musso, María R. Nogueiras, Gustavo Ordóñez, and Carlos Vázquez, "A Survey on Quantum Computational Finance for Derivatives Pricing and VaR", Archives of Computational Methods in Engineering 29 6, 4137 (2022).

[7] Jakob Unfried, Johannes Hauschild, and Frank Pollmann, "Fast time evolution of matrix product states using the QR decomposition", Physical Review B 107 15, 155133 (2023).

[8] Shi-Ju Ran, "Encoding of matrix product states into quantum circuits of one- and two-qubit gates", Physical Review A 101 3, 032310 (2020).

[9] Samuel Jaques and Thomas Häner, "Leveraging State Sparsity for More Efficient Quantum Simulations", ACM Transactions on Quantum Computing 3 3, 1 (2022).

[10] Gilberto J. Díaz T, Carlos J. Barrios H., Luiz A. Steffenel, and Jean F. Couturier, Communications in Computer and Information Science 1660, 205 (2022) ISBN:978-3-031-23820-8.

[11] G. A. L. White, C. D. Hill, and L. C. L. Hollenberg, "Truncated phase-based quantum arithmetic: Error propagation and resource reduction", Physical Review A 108 5, 052608 (2023).

[12] Yi-Ting Chen, Collin Farquhar, and Robert M. Parrish, "Low-rank density-matrix evolution for noisy quantum circuits", npj Quantum Information 7 1, 61 (2021).

[13] Manas Sajjan, Junxu Li, Raja Selvarajan, Shree Hari Sureshbabu, Sumit Suresh Kale, Rishabh Gupta, Vinit Singh, and Sabre Kais, "Quantum machine learning for chemistry and physics", Chemical Society Reviews 51 15, 6475 (2022).

[14] He-Liang Huang, Xiao-Yue Xu, Chu Guo, Guojing Tian, Shi-Jie Wei, Xiaoming Sun, Wan-Su Bao, and Gui-Lu Long, "Near-term quantum computing techniques: Variational quantum algorithms, error mitigation, circuit compilation, benchmarking and classical simulation", Science China Physics, Mechanics & Astronomy 66 5, 250302 (2023).

[15] Maxime Dupont, Nicolas Didier, Mark J. Hodson, Joel E. Moore, and Matthew J. Reagor, "Entanglement perspective on the quantum approximate optimization algorithm", Physical Review A 106 2, 022423 (2022).

[16] Shuvro Chowdhury, Kerem Y. Çamsari, and Supriyo Datta, "Emulating Quantum Circuits With Generalized Ising Machines", IEEE Access 11, 116944 (2023).

[17] Holm Gero Hümmler, Relativer Quantenquark 105 (2019) ISBN:978-3-662-58419-4.

[18] 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).

[19] Baonan Wang, Feng Hu, Haonan Yao, and Chao Wang, "Prime factorization algorithm based on parameter optimization of Ising model", Scientific Reports 10, 7106 (2020).

[20] Baonan Wang, Xiaoting Yang, and Dan Zhang, "Research on Quantum Annealing Integer Factorization Based on Different Columns", Frontiers in Physics 10, 914578 (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2024-08-16 12:16:52) and SAO/NASA ADS (last updated successfully 2024-08-16 12:16:53). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.