Simulating the quantum Fourier transform, Grover's algorithm, and the quantum counting algorithm with limited entanglement using tensor-networks

Abstract

Quantum algorithms reformulate computational problems as quantum evolutions in a large Hilbert space. Most quantum algorithms assume that the time-evolution is perfectly unitary and that the full Hilbert space is available. However, in practice, the available entanglement may be limited, leading to a reduced fidelity of the quantum algorithms. To simulate the execution of quantum algorithms with limited entanglement, tensor-network methods provide a useful framework, since they allow us to restrict the entanglement in a quantum circuit. Thus, we here use tensor-networks to analyze the fidelity of the quantum Fourier transform, Grover's algorithm, and the quantum counting algorithm as the entanglement is reduced, and we map out the entanglement that is generated during the execution of each algorithm. In all three cases, we find that the algorithms can be executed with high fidelity even if the entanglement is somewhat reduced. Our results are promising for the execution of these algorithms on future quantum computers, and our simulation method based on tensor networks may also be applied to other quantum algorithms.

16 pages, 13 figures

References in corpus (28)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• The density-matrix renormalization group in the age of matrix product states
• Efficient simulation of one-dimensional quantum many-body systems
• The ITensor Software Library for Tensor Network Calculations
• Time-evolution methods for matrix-product states
• Complete 3-Qubit Grover Search on a Programmable Quantum Computer
• What limits the simulation of quantum computers?
• Solving the sampling problem of the Sycamore quantum circuits
• Generic Construction of Efficient Matrix Product Operators
• Perfect Sampling with Unitary Tensor Networks
• TensorCircuit: a Quantum Software Framework for the NISQ Era
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Developments in the Tensor Network -- from Statistical Mechanics to Quantum Entanglement
• Learning Feynman Diagrams with Tensor Trains
• A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
• Quantum Fourier Transform Has Small Entanglement
• Efficient classical simulation of the approximate quantum Fourier transform
• Quantics Tensor Cross Interpolation for High-Resolution, Parsimonious Representations of Multivariate Functions in Physics and Beyond
• Multiscale space-time ansatz for correlation functions of quantum systems based on quantics tensor trains
• Classical simulation of lossy boson sampling using matrix product operators
• Simulating Noisy Quantum Circuits with Matrix Product Density Operators
• Validating Quantum-Classical Programming Models with Tensor Network Simulations
• Simulating quantum circuits using tree tensor networks
• Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation
• Noise effects on purity and quantum entanglement in terms of physical implementability
• Simulation of Quantum Computing on Classical Supercomputers
• Cross-extrapolation reconstruction of low-rank functions and application to quantum many-body observables in the strong coupling regime
• Preservation of entanglement in local noisy channels

Cited by in corpus (7)

• Stabilizer Tensor Networks with Magic State Injection
• Efficient Quantum Circuit Compilation for Near-Term Quantum Advantage
• Quantum computing topological invariants of two-dimensional quantum matter
• Correlated states in super-moiré materials with a kernel polynomial quantics tensor cross interpolation algorithm
• Self-consistent tensor network method for correlated super-moiré matter beyond one billion sites
• Tensor network method for real-space topology in quasicrystal Chern mosaics
• Dynamical cluster-based strategy for improving tensor network algorithms in quantum circuit simulations