Optimising Matrix Product State Simulations of Shor's Algorithm

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.

8 pages, 2 figures, 2 tables. v2 using PDFLaTeX compiler. v3 to include extra references. v4 for publication in Quantum

References in corpus (7)

• The density-matrix renormalization group in the age of matrix product states
• Classical simulation of infinite-size quantum lattice systems in one spatial dimension
• Experimental demonstration of Shor's algorithm with quantum entanglement
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral
• A tree tensor network approach to simulating Shor's algorithm

Cited by in corpus (14)

• Quantum Machine Learning for Chemistry and Physics
• Encoding of Matrix Product States into Quantum Circuits of One- and Two-Qubit Gates
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Developments in the Tensor Network -- from Statistical Mechanics to Quantum Entanglement
• Validating Quantum-Classical Programming Models with Tensor Network Simulations
• An entanglement perspective on the quantum approximate optimization algorithm
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• Stabilizer Tensor Networks with Magic State Injection
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Benchmarking treewidth as a practical component of tensor-network--based quantum simulation
• Fast Time-Evolution of Matrix-Product States using the QR decomposition
• Emulating Quantum Interference with Generalized Ising Machines
• Quantum computing topological invariants of two-dimensional quantum matter
• Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem