Parallelizing quantum simulation with decision diagrams
- URL: http://arxiv.org/abs/2312.01570v1
- Date: Mon, 4 Dec 2023 02:00:24 GMT
- Title: Parallelizing quantum simulation with decision diagrams
- Authors: Shaowen Li, Yusuke Kimura, Hiroyuki Sato, Junwei Yu, Masahiro Fujita
- Abstract summary: Classical computers face a critical obstacle in simulating quantum algorithms.
Quantum states reside in a Hilbert space whose size grows exponentially to the number of subsystems, i.e., qubits.
This work explores several strategies for parallelizing decision diagram operations, specifically for quantum simulations.
- Score: 2.5999037208435705
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent technological advancements show promise in leveraging quantum
mechanical phenomena for computation. This brings substantial speed-ups to
problems that are once considered to be intractable in the classical world.
However, the physical realization of quantum computers is still far away from
us, and a majority of research work is done using quantum simulators running on
classical computers. Classical computers face a critical obstacle in simulating
quantum algorithms. Quantum states reside in a Hilbert space whose size grows
exponentially to the number of subsystems, i.e., qubits. As a result, the
straightforward statevector approach does not scale due to the exponential
growth of the memory requirement. Decision diagrams have gained attention in
recent years for representing quantum states and operations in quantum
simulations. The main advantage of this approach is its ability to exploit
redundancy. However, mainstream quantum simulators still rely on statevectors
or tensor networks. We consider the absence of decision diagrams due to the
lack of parallelization strategies. This work explores several strategies for
parallelizing decision diagram operations, specifically for quantum
simulations. We propose optimal parallelization strategies. Based on the
experiment results, our parallelization strategy achieves a 2-3 times faster
simulation of Grover's algorithm and random circuits than the state-of-the-art
single-thread DD-based simulator DDSIM.
Related papers
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties?
We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.
We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
arXiv Detail & Related papers (2024-08-22T08:21:28Z) - Parallel Quantum Computing Simulations via Quantum Accelerator Platform Virtualization [44.99833362998488]
We present a model for parallelizing simulation of quantum circuit executions.
The model can take advantage of its backend-agnostic features, enabling parallel quantum circuit execution over any target backend.
arXiv Detail & Related papers (2024-06-05T17:16:07Z) - Multi-mode Cavity Centric Architectures for Quantum Simulation [12.40374538847457]
Near-term quantum computing technologies grapple with huge complexity overheads, hindering their ability to induce algorithms.
One class of problems of interest is Quantum Simulation, whereby quantum systems are simulated using a quantum computer.
One technology of particular interest is the multi-mode superconducting resonator capable of storing multiple qubits in one device.
arXiv Detail & Related papers (2023-09-27T20:16:44Z) - A Reorder Trick for Decision Diagram Based Quantum Circuit Simulation [0.4358626952482686]
We study two classes of quantum circuits on which the state-of-the-art decision diagram based simulators failed to perform well in terms of simulation time.
We propose a simple and powerful reorder trick to boost the simulation of such quantum circuits.
arXiv Detail & Related papers (2022-11-14T04:55:25Z) - Quantum communication complexity of linear regression [0.05076419064097732]
We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems.
We propose an efficient quantum protocol for quantum singular value transformation.
arXiv Detail & Related papers (2022-10-04T13:27:01Z) - An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian
Simulation [55.41644538483948]
Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates.
We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions.
The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
arXiv Detail & Related papers (2021-08-06T19:38:03Z) - Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems.
We propose an algorithm to implement imaginary time propagation on a quantum computer.
arXiv Detail & Related papers (2021-02-24T12:48:00Z) - Quantum walk processes in quantum devices [55.41644538483948]
We study how to represent quantum walk on a graph as a quantum circuit.
Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
arXiv Detail & Related papers (2020-12-28T18:04:16Z) - Faster Schr\"odinger-style simulation of quantum circuits [2.0940228639403156]
Recent demonstrations of superconducting quantum computers by Google and IBM fueled new research in quantum algorithms.
We advance Schr"odinger-style simulation of quantum circuits that is useful standalone and as a building block in layered simulation algorithms.
arXiv Detail & Related papers (2020-08-01T08:47:24Z) - Bit-Slicing the Hilbert Space: Scaling Up Accurate Quantum Circuit
Simulation to a New Level [10.765480856320018]
We enhance quantum circuit simulation in two dimensions: accuracy and scalability.
Experimental results demonstrate that our method can be superior to the state-of-the-art for various quantum circuits.
arXiv Detail & Related papers (2020-07-18T01:26:40Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.