Simulating Quantum Circuits Using Efficient Tensor Network Contraction Algorithms with Subexponential Upper Bound.

Area of Science:

• Quantum Computing
• Computational Complexity
• Quantum Information Theory

Background:

• Tensor network contractions are crucial for simulating quantum systems.
• Classical simulation of quantum circuits faces computational challenges, especially in higher dimensions.
• Efficient algorithms are needed to overcome the exponential scaling of quantum computations.

Purpose of the Study:

• To derive a rigorous upper bound on the classical computation time for finite-ranged tensor network contractions in d≥2 dimensions.
• To demonstrate that quantum circuits with specific gate types can be simulated in subexponential time classically.
• To develop and implement an algorithm that achieves practical speedups for quantum circuit simulations.

Main Methods:

• Derivation of a rigorous upper bound for tensor network contraction complexity.
• Development and implementation of a novel algorithm for optimizing contraction order.
• Benchmarking the algorithm against standard and state-of-the-art simulation methods.

Main Results:

• A subexponential time upper bound for classical simulation of certain quantum circuits is established.
• The implemented algorithm significantly reduces computational time in practice, outperforming naive and advanced methods.
• Speedups of several orders of magnitude are observed for 2D quantum circuits on an 8x8 lattice.
• Efficient contraction schemes are obtained for various quantum circuit types, including Sycamore and random circuits.

Conclusions:

• The derived upper bound provides theoretical backing for efficient classical simulation of quantum circuits.
• The developed algorithm offers a practical and significantly faster approach to simulating quantum computations.
• This work advances the field of quantum computation simulation, with implications for understanding quantum advantage and resource estimation.