Improving gate-level simulation of quantum circuits
From MaRDI portal
Abstract: Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and the vectors modeling qubit states grow exponentially with an increase in the number of qubits. However, by using a novel data structure called the Quantum Information Decision Diagram (QuIDD) that exploits the structure of quantum operators, a useful subset of operator matrices and state vectors can be represented in a form that grows polynomially with the number of qubits. This subset contains, but is not limited to, any equal superposition of n qubits, any computational basis state, n-qubit Pauli matrices, and n-qubit Hadamard matrices. It does not, however, contain the discrete Fourier transform (employed in Shor's algorithm) and some oracles used in Grover's algorithm. We first introduce and motivate decision diagrams and QuIDDs. We then analyze the runtime and memory complexity of QuIDD operations. Finally, we empirically validate QuIDD-based simulation by means of a general-purpose quantum computing simulator QuIDDPro implemented in C++. We simulate various instances of Grover's algorithm with QuIDDPro, and the results demonstrate that QuIDDs asymptotically outperform all other known simulation techniques. Our simulations also show that well-known worst-case instances of classical searching can be circumvented in many specific cases by data compression techniques.
Recommendations
- Improved BDD Algorithms for the Simulation of Quantum Circuits
- Storing the Quantum Fourier Operator in the QuIDD Data Structure
- Graph-based simulation of quantum computation in the density matrix representation
- QCL implementation of quantum search algorithms
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
Cited in
(20)- Graph-based simulation of quantum computation in the density matrix representation
- Improved gap estimates for simulating quantum circuits by adiabatic evolution
- Model Checking for Verification of Quantum Circuits
- QuanPath: achieving one-step communication for distributed quantum circuit simulation
- Improving quantum computation by optimized qubit routing
- Efficient algorithm for full-state quantum circuit simulation with DD compression while maintaining accuracy
- Improved quantum circuit modelling based on Heisenberg representation
- Quantum Circuit Simulation
- Efficient implementation of LIMDDs for quantum circuit simulation
- Quantum walks: a comprehensive review
- Workflow of the Grover algorithm simulation incorporating CUDA and GPGPU
- Binary superposed quantum decision diagrams
- Parallel computational structure of noisy quantum circuits simulation
- Effective simulation of state distribution in qubit chains
- Quantum QR decomposition in the computational basis
- Improved BDD Algorithms for the Simulation of Quantum Circuits
- Context-aware quantum simulation of a matrix stored in quantum memory
- Quantum simulation from the bottom up: the case of rebits
- A modeling and verification framework for optical quantum circuits
- Computing with highly mixed states (extended abstract)
This page was built for publication: Improving gate-level simulation of quantum circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2573093)
