Simulations of Shor's algorithm using matrix product states

DOI10.1007/S11128-017-1587-XMaRDI QIDQ1674568zbMATH OpenOpenAlexWikidataFDO

Authors Peng Zhang

Publication date 25 October 2017

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.07644

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Factorization (11Y05)

Abstract: We show that under the matrix product state formalism the states produced in Shor's algorithm can be represented using O(max($4l{r}^2$, $2^{2l}$)) space, where l is the number of bits in the number to factorise, and r is the order and the solution to the related order-finding problem. The reduction in space compared to an amplitude formalism approach is significant, allowing simulations as large as 42 qubits to be run on a single processor with 32GB RAM. This approach is readily adapted to a distributed memory environment, and we have simulated a 45 qubit case using 8 cores with 16GB RAM in approximately one hour.

Recommendations

• QUANTUM-STATISTICAL SIMULATIONS FOR QUANTUM CIRCUITS
• scientific article
• scientific article; zbMATH DE number 2013812
• Scalability of Shor’s algorithm with a limited set of rotation gates
• Implementation of Shor's algorithm on a linear nearest neighbour qubit array

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 5320229 (Why is no real title available?)
• scientific article; zbMATH DE number 5320241 (Why is no real title available?)
• scientific article; zbMATH DE number 2013812 (Why is no real title available?)
• scientific article; zbMATH DE number 1406150 (Why is no real title available?)
• A practical introduction to tensor networks: Matrix product states and projected entangled pair states
• Colloquium: Quantum annealing and analog quantum computation
• Massively parallel quantum computer simulator
• On the role of entanglement in quantum-computational speed-up
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• QCMPI: A parallel environment for quantum computing
• ScaLAPACK Users' Guide

Cited in

(4)

• Scalability of Shor’s algorithm with a limited set of rotation gates
• Fast and accurate simulation of quantum computing by multi-precision MPS: recent development
• The Fraunhofer quantum computing simulator
• Efficient Construction of Functional Representations for Quantum Algorithms

Describes a project that uses

Uses Software

• QCMPI
• ScaLAPACK

This page was built for publication: Simulations of Shor's algorithm using matrix product states

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1674568)