Efficient parallelization of tensor network contraction for simulating quantum computation

Cupjin Huang; Fang Zhang; Michael Newman; Xiaotong Ni; Dawei Ding; Junjie Cai; Xun Gao; Tenghui Wang; Feng Wu; Gengyan Zhang; Hsiang Sheng Ku; Zhengxiong Tian; Junyin Wu; Haihong Xu; Huanjun Yu; Bo Yuan; Mario Szegedy; Yaoyun Shi; Hui Hai Zhao; Chunqing Deng; Jianxin Chen

doi:10.1038/s43588-021-00119-7

Efficient parallelization of tensor network contraction for simulating quantum computation

Cupjin Huang, Fang Zhang, Michael Newman, Xiaotong Ni, Dawei Ding, Junjie Cai, Xun Gao, Tenghui Wang, Feng Wu, Gengyan Zhang, Hsiang Sheng Ku, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, Hui Hai Zhao, Chunqing DengJianxin Chen

Research output: Contribution to journal › Article › peer-review

43 Scopus citations

Abstract

We develop an algorithmic framework for contracting tensor networks and demonstrate its power by classically simulating quantum computation of sizes previously deemed out of reach. Our main contribution, index slicing, is a method that efficiently parallelizes the contraction by breaking it down into much smaller and identically structured subtasks, which can then be executed in parallel without dependencies. We benchmark our algorithm on a class of random quantum circuits, achieving greater than 10⁵ times acceleration over the original estimate of the simulation cost. We then demonstrate applications of the simulation framework for aiding the development of quantum algorithms and quantum error correction. As tensor networks are widely used in computational science, our simulation framework may find further applications.

Original language	English (US)
Pages (from-to)	578-587
Number of pages	10
Journal	Nature Computational Science
Volume	1
Issue number	9
DOIs	https://doi.org/10.1038/s43588-021-00119-7
State	Published - Sep 2021
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computer Science (miscellaneous)
Computer Science Applications
Computer Networks and Communications

Access to Document

10.1038/s43588-021-00119-7

Cite this

Huang, C., Zhang, F., Newman, M., Ni, X., Ding, D., Cai, J., Gao, X., Wang, T., Wu, F., Zhang, G., Ku, H. S., Tian, Z., Wu, J., Xu, H., Yu, H., Yuan, B., Szegedy, M., Shi, Y., Zhao, H. H., ... Chen, J. (2021). Efficient parallelization of tensor network contraction for simulating quantum computation. Nature Computational Science, 1(9), 578-587. https://doi.org/10.1038/s43588-021-00119-7

@article{c4723ee3ceda47f98c037b4677692e4f,

title = "Efficient parallelization of tensor network contraction for simulating quantum computation",

abstract = "We develop an algorithmic framework for contracting tensor networks and demonstrate its power by classically simulating quantum computation of sizes previously deemed out of reach. Our main contribution, index slicing, is a method that efficiently parallelizes the contraction by breaking it down into much smaller and identically structured subtasks, which can then be executed in parallel without dependencies. We benchmark our algorithm on a class of random quantum circuits, achieving greater than 105 times acceleration over the original estimate of the simulation cost. We then demonstrate applications of the simulation framework for aiding the development of quantum algorithms and quantum error correction. As tensor networks are widely used in computational science, our simulation framework may find further applications.",

author = "Cupjin Huang and Fang Zhang and Michael Newman and Xiaotong Ni and Dawei Ding and Junjie Cai and Xun Gao and Tenghui Wang and Feng Wu and Gengyan Zhang and Ku, {Hsiang Sheng} and Zhengxiong Tian and Junyin Wu and Haihong Xu and Huanjun Yu and Bo Yuan and Mario Szegedy and Yaoyun Shi and Zhao, {Hui Hai} and Chunqing Deng and Jianxin Chen",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s).",

year = "2021",

month = sep,

doi = "10.1038/s43588-021-00119-7",

language = "English (US)",

volume = "1",

pages = "578--587",

journal = "Nature Computational Science",

issn = "2662-8457",

publisher = "Springer Nature",

number = "9",

}

Huang, C, Zhang, F, Newman, M, Ni, X, Ding, D, Cai, J, Gao, X, Wang, T, Wu, F, Zhang, G, Ku, HS, Tian, Z, Wu, J, Xu, H, Yu, H, Yuan, B, Szegedy, M, Shi, Y, Zhao, HH, Deng, C & Chen, J 2021, 'Efficient parallelization of tensor network contraction for simulating quantum computation', Nature Computational Science, vol. 1, no. 9, pp. 578-587. https://doi.org/10.1038/s43588-021-00119-7

TY - JOUR

T1 - Efficient parallelization of tensor network contraction for simulating quantum computation

AU - Huang, Cupjin

AU - Zhang, Fang

AU - Newman, Michael

AU - Ni, Xiaotong

AU - Ding, Dawei

AU - Cai, Junjie

AU - Gao, Xun

AU - Wang, Tenghui

AU - Wu, Feng

AU - Zhang, Gengyan

AU - Ku, Hsiang Sheng

AU - Tian, Zhengxiong

AU - Wu, Junyin

AU - Xu, Haihong

AU - Yu, Huanjun

AU - Yuan, Bo

AU - Szegedy, Mario

AU - Shi, Yaoyun

AU - Zhao, Hui Hai

AU - Deng, Chunqing

AU - Chen, Jianxin

PY - 2021/9

Y1 - 2021/9

N2 - We develop an algorithmic framework for contracting tensor networks and demonstrate its power by classically simulating quantum computation of sizes previously deemed out of reach. Our main contribution, index slicing, is a method that efficiently parallelizes the contraction by breaking it down into much smaller and identically structured subtasks, which can then be executed in parallel without dependencies. We benchmark our algorithm on a class of random quantum circuits, achieving greater than 105 times acceleration over the original estimate of the simulation cost. We then demonstrate applications of the simulation framework for aiding the development of quantum algorithms and quantum error correction. As tensor networks are widely used in computational science, our simulation framework may find further applications.

AB - We develop an algorithmic framework for contracting tensor networks and demonstrate its power by classically simulating quantum computation of sizes previously deemed out of reach. Our main contribution, index slicing, is a method that efficiently parallelizes the contraction by breaking it down into much smaller and identically structured subtasks, which can then be executed in parallel without dependencies. We benchmark our algorithm on a class of random quantum circuits, achieving greater than 105 times acceleration over the original estimate of the simulation cost. We then demonstrate applications of the simulation framework for aiding the development of quantum algorithms and quantum error correction. As tensor networks are widely used in computational science, our simulation framework may find further applications.

UR - http://www.scopus.com/inward/record.url?scp=85119136615&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85119136615&partnerID=8YFLogxK

U2 - 10.1038/s43588-021-00119-7

DO - 10.1038/s43588-021-00119-7

M3 - Article

AN - SCOPUS:85119136615

SN - 2662-8457

VL - 1

SP - 578

EP - 587

JO - Nature Computational Science

JF - Nature Computational Science

IS - 9

ER -

Efficient parallelization of tensor network contraction for simulating quantum computation

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this