Computer Science

Computer Science ›› 2024, Vol. 51 ›› Issue (9): 80-86.doi: 10.11896/jsjkx.230300215

• High Performance Computing • Previous Articles     Next Articles

Simulation of Limited Entangled Quantum Fourier Transform Based on Matrix Product State

LIU Xiaonan1,2, LIAN Demeng2,3, DU Shuaiqi2,3, LIU Zhengyu2,3   

  1. 1 State Key Laboratory of Mathematical Engineering and Advanced Computing(Information Engineering University),Zhengzhou 450000,China
    2 National Supercomputing Center in Zhengzhou,Zhengzhou 450000,China
    3 School of Computer and Artificial Intelligence,Zhengzhou University,Zhengzhou 450000,China
  • Received:2023-03-29 Revised:2023-07-28 Online:2024-09-15 Published:2024-09-10
  • About author:LIU Xiaonan,born in 1977,Ph.D,associate professor,master's supervisor.His main research interests include quantum algorithm and high-perfor-mance parallel computation.
    LIAN Demeng,born in 1999,postgra-duate.His main research interests include quantum algorithm and high-performance computing.
  • Supported by:
    National Natural Science Foundation of China(61972413,61701539).

PDF (PC)

370

Abstract: Unlike classical computing,qubits in quantum computing can be in the superposition state and entangled state can be formed between multiple qubits.Representing a quantum state composed of n qubits requires storing 2 to the nth power amplitudes.The exponential memory cost makes large-scale quantum simulation difficult.Using the HIP-Clang language,based on the heterogeneous programming model of CPU+DCU and representing the quantum state with the matrix product state,quantum Fourier transform is simulated.By combining the characteristics of the matrix product state and analyzing the quantum Fourier transform circuit,unnecessary tensor contraction operations and orthogonalization construction are reduced during simulation implementation.Tensor contraction during simulation is analyzed and the TTGT algorithm is used to complete tensor contraction operations while utilizing DCU's parallel processing capabilities to improve efficiency.Simulation results are analyzed and the correctness of the simulation is verified through amplitude error and semi-classical Draper quantum adder results.Analyzing simulation scale,when the entanglement entropy of the quantum state is maximum,using 16GB of memory can simulate up to 24bit quantum states at most,while when the entanglement of the quantum state is limited,it can simulate hundreds of qubits of quantum Fourier transform.

Key words: Quantum simulation, Quantum Fourier transform, Matrix product state, Heterogeneous computing, DCU, HIP-Clang

CLC Number: 

  • TP385
[1]SHOR P W.Algorithms for quantum computation:discrete loga-rithms and factoring[C]//Proceedings 35th Annual Symposiumon Foundations of Computer Science.IEEE,1994:124-134.
[2]HARROW A W,HASSIDIM A,LLOYD S.Quantum algorithm for linear systems of equations[J].Physical Review Letters,2009,103(15):150502.
[3]NIELSEN M A,CHUANG I L.Quantum computation andquantum information[M]. Cambridge: Cambridge University Press,2010:217-221.
[4]LI X W,FU X,YAN F,et al.Current status and future develop-ment of quantum computing research[J].China Engineering Science,2022,24(4):133-144.
[5]BROWNE D E.Efficient classical simulation of the quantumFourier transform[J].New Journal of Physics,2007,9(5):146.
[6]XIE J M,HU W F,HAN I,et al.Quantum Fourier Transform Simulation Based on “Songshan” Supercomputer System[J].Computer Science,2021,48(12):36-42.
[7]LIU X N,JING L N,WANG L X,et al.Large-scale Quantum Fourier Transform Simulation Based on SW26010[J].Computer Science,2020,47(8):93-97.
[8]WOOLFE K J,HILL C D,HOLLENBERG L C L.Scale inva-riance and efficient classical simulation of the quantum Fourier transform[J].arXiv:1406.0931,2014.
[9]SAITOH A.Fast and Accurate Simulation of Quantum Computing by Multi-Precision Mps:Recent Development[M]//Phy-sics,Mathematics,and All that Quantum Jazz.2014:49-69.
[10]GAWATZ R,BALRAM A.Matrix Product State Based Algorithms[J/OL].https://qdev.nbi.ku.dk/student_theses/RGawatz_Msc.pdf.
[11]EKERT A,KNIGHT P L.Entangled quantum systems and the Schmidt decomposition[J].American Journal of Physics,1995,63(5):415-423.
[12]SCHOLLWÖCK U.The density-matrix renormalization groupin the age of matrix product states[J].Annals of Physics,2011,326(1):96-192.
[13]FOWLER A G,DEVITT S J,HOLLENBERG L C L.Imple-mentation of Shor's algorithm on a linear nearest neighbour qubit array[J].Quantum Information & Computation,2004,4(4):237-251.
[14]BEAUREGARD S.Circuit for Shor's algorithm using 2n＋3 qubits[J].Quantum Information & Computation,2003,3(2):175-185.
[1] HAO Meng, TIAN Xueyang, LU Gangzhao, LIU Yi, ZHANG Weizhe, HE Hui. Transplantation and Optimization of Graph Matching Algorithm Based on Domestic DCUHeterogeneous Platform [J]. Computer Science, 2024, 51(4): 67-77.
[2] FENG Yan, WANG Rui-cong. Quantum Voting Protocol Based on Quantum Fourier Transform Summation [J]. Computer Science, 2022, 49(5): 311-317.
[3] XIE Jing-ming, HU Wei-fang, HAN Lin, ZHAO Rong-cai, JING Li-na. Quantum Fourier Transform Simulation Based on “Songshan” Supercomputer System [J]. Computer Science, 2021, 48(12): 36-42.
[4] YANG Wang-dong, WANG Hao-tian, ZHANG Yu-feng, LIN Sheng-le, CAI Qin-yun. Survey of Heterogeneous Hybrid Parallel Computing [J]. Computer Science, 2020, 47(8): 5-16.
[5] LIU Xiao-nan, JING Li-na, WANG Li-xin, WANG Mei-ling. Large-scale Quantum Fourier Transform Simulation Based on SW26010 [J]. Computer Science, 2020, 47(8): 93-97.
[6] ZHANG Long-xin, ZHOU Li-qian, WEN Hong, XIAO Man-sheng, DENG Xiao-jun. Energy Efficient Scheduling Algorithm of Workflows with Cost Constraint in Heterogeneous Cloud Computing Systems [J]. Computer Science, 2020, 47(8): 112-118.
[7] ZHANG Shuai, XU Shun, LIU Qian, JIN Zhong. Cell Verlet Algorithm of Molecular Dynamics Simulation Based on GPU and Its Parallel Performance Analysis [J]. Computer Science, 2018, 45(10): 291-294.
[8] WEI Jian-wen, XU Zhi-geng, WANG Bing-qiang, Simon SEE and James LIN. Accelerating Gene Clustering on Heterogeneous Clusters [J]. Computer Science, 2017, 44(3): 20-22.
[9] WANG Ya-hui and YAN Song-yuan. New Quantum Algorithm for Breaking RSA [J]. Computer Science, 2016, 43(4): 24-27.
[10] HUA Hui-you, CHEN Qi-mai, LIU Hai, ZHANG Yang and YUAN Pei-quan. Hybrid Kmeans with KNN for Network Intrusion Detection Algorithm [J]. Computer Science, 2016, 43(3): 158-162.
[11] ZENG Zhiping, XIAO Haidong and ZHANG Xinpeng. Construction Ｈeterogeneous Ｃomputing Ｐlatforms and Ｓensitive Ｄata Ｐrotection Ｂased on Ｄomestic X86 Ｐrocessors [J]. Computer Science, 2015, 42(Z11): 317-322.
[12] FAN Fu-you, YANG Guo-wu, ZHANG Yan and YANG Gang. Three-valued Quantum Elementary and Implementation of Quantum Fourier Transform Circuit [J]. Computer Science, 2015, 42(7): 57-61.
[13] LI Bin, WANG Jin-song and HUANG Wei. Novel Global Kmeans Clustering Algorithm for Big Data [J]. Computer Science, 2015, 42(12): 247-250.
[14] HAO Shui-xia,ZENG Guo-sun,MA Xiao-xin and XU Jin-chao. Similarity-driven Fine-grained Parallel Task Reconfigurable Algorithm [J]. Computer Science, 2013, 40(9): 44-50.
[15] . Research and Implementation of Column-based Database Schedule [J]. Computer Science, 2013, 40(3): 142-146.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.