Tree tensor network approach to simulating Shor's algorithm

2017/05/15 by Eugene Dumitrescu · 2 citations
Computer Science · Physics and Astronomy · #Algorithm #Computer science #Matrix multiplication #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum and electron transport phenomena #Quantum computer #Quantum entanglement #Quantum many-body systems #Quantum mechanics #Qubit #Theoretical computer science #quant-ph

paper · pdf · doi:10.1103/physreva.96.062322

published as Phys. Rev. A 96, 062322 (2017) · 4+ pages, 4 figures, reference added

arxiv created 2017/05/15 · openalex publication_date 2017/12/20 · arxiv updated 2017/12/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

Constructively simulating quantum systems furthers our understanding of qualitative and quantitative features which may be analytically intractable. In this paper, we directly simulate and explore the entanglement structure present in the paradigmatic example for exponential quantum speedups: Shor's algorithm. To perform our simulation, we construct a dynamic tree tensor network which manifestly captures two salient circuit features for modular exponentiation. These are the natural two-register bipartition and the invariance of entanglement with respect to permutations of the top-register qubits. Our construction help identify the entanglement entropy properties, which we summarize by a scaling relation. Further, the tree network is efficiently projected onto a matrix product state from which we efficiently execute the quantum Fourier transform. Future simulation of quantum information states with tensor networks exploiting circuit symmetries is discussed.

Citations

• The quantum FFT can be classically simulated
• Fast quantum modular exponentiation
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Simulating Quantum Computation by Contracting Tensor Networks
• Universality of entanglement and quantum-computation complexity
• Efficient classical simulation of the approximate quantum Fourier transform
• The density-matrix renormalization group in the age of matrix product states
• Fast Quantum Modular Exponentiation Architecture for Shor's Factorization Algorithm
• Quantum Computation and Quantum Information
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Cited by

• Simulating Quantum Circuits with Tree Tensor Networks using Density-Matrix Renormalization Group Algorithm
• Validating quantum-classical programming models with tensor network simulations