As Accurate as Needed, as Efficient as Possible: Approximations in DD-based Quantum Circuit Simulation

Abstract

Quantum computers promise to solve important problems faster than conventional computers. However, unleashing this power has been challenging. In particular, design automation runs into (1) the probabilistic nature of quantum computation and (2) exponential requirements for computational resources on non-quantum hardware. In quantum circuit simulation, Decision Diagrams (DDs) have previously shown to reduce the required memory in many important cases by exploiting redundancies in the quantum state. In this paper, we show that this reduction can be amplified by exploiting the probabilistic nature of quantum computers to achieve even more compact representations. Specifically, we propose two new DD-based simulation strategies that approximate the quantum states to attain more compact representations, while, at the same time, allowing the user to control the resulting degradation in accuracy. We also analytically prove the effect of multiple approximations on the attained accuracy and empirically show that the resulting simulation scheme enables speed-ups up to several orders of magnitudes.

arXiv comment6 pages, 2 figures, to be published at Design, Automation, and Test in Europe 2021

References in corpus (11)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Characterizing Quantum Supremacy in Near-Term Devices
• Quantum algorithms: an overview
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• QuEST and High Performance Simulation of Quantum Computers
• Verification of quantum computation: An overview of existing approaches
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• How to Efficiently Handle Complex Values? Implementing Decision Diagrams for Quantum Computing
• Verifying Results of the IBM Qiskit Quantum Circuit Compilation Flow
• Approximation of Quantum States Using Decision Diagrams

Cited by in corpus (3)

• Tools for Quantum Computing Based on Decision Diagrams
• LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States
• The Basis of Design Tools for Quantum Computing: Arrays, Decision Diagrams, Tensor Networks, and ZX-Calculus