Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Conference on Quantum Computing and Engineering (QCE)

GraFeyn: Efficient Parallel Sparse Simulation of Quantum Circuits

Sam Westrick, Pengyu Liu, Byeongjee Kang, Colin McDonald, Mike Rainey, Mingkuan Xu, Jatin Arora, Yongshan Ding, Umut A. Acar

Published Sep 15, 2024• 7 citations
Publisher

Abstract

Many circuit simulators use either a Schrodinger-based or Feynman-based approach, which have complementary strengths. Schrödinger-based simulators maintain a state vector by synchronously updating it after each gate (or group of gates), ensuring time efficiency at the cost of exponential space. In contrast, Feynman-based simulators use low space but require high time to compute the sum of exponentially many independent Feynman paths. Because they treat paths as independent, Feynman-based simulators miss opportunities to take advantage of sparsity from destructive interference. In this paper, we present a hybrid Schrödinger-Feynman technique which takes advantage of sparsity by selectively synchronizing Feynman paths. Our hybrid technique partitions the circuit into kernels (groups of gates) and uses Feynman simulation within each kernel. It then synchronizes across the kernels by using Schrödinger-style simulation. We parallelize our approach by representing the simulation as a graph, leveraging state-of-the-art parallel graph algorithms. By selecting kernels carefully, we show that our approach can simulate hundreds of qubits efficiently (in both time and space) on just a single multicore node. In certain “sparse” circuits, we are able to improve running times by multiple orders of magnitude.

DOI
10.1109/qce60285.2024.00132

Related papers

Joint Cutting for Hybrid Schrödinger-Feynman Simulation of Quantum Circuits

Laura S. Herzog, Lukas Burgholzer, Christian Ufrecht +2 more

Despite the continuous advancements in size and robustness of real quantum devices, reliable large-scale quantum computers are not yet available. Hence, classical simulation of quantum algorithms remains crucial for testing new methods and estimating quantum advantage. Pushing classical simulation methods to their limit is essential, particularly due to their inherent exponential complexity. Besides the established Schrödinger-style full statevector simulation, so-called Hybrid Schrödinger-Feynman (HSF) approaches have shown promise to make simulations more efficient. HSF simulation employs the idea of “cutting” the circuit into smaller parts, reducing their execution times. This, however, comes at the cost of an exponential overhead in the number of cuts. Inspired by the domain of Quantum Circuit Cutting, we propose an HSF simulation method based on the idea of “joint cutting” to significantly reduce the aforementioned overhead. This means that, prior to the cutting procedure, gates are collected into “blocks” and all gates in a block are jointly cut instead of individually. We investigate how the proposed refinement can help decrease simulation times and highlight the remaining challenges. Experimental evaluations show that “joint cutting” can outperform the standard HSF simulation by up to a factor $\approx 4000 \times$ and the Schrödinger-style simulation by a factor $\approx 200 \times$ for suitable instances. The implementation is available at https://github.com/cda-tum/mqt-qsim-joint-cutting.

arXiv:2502.06959•ACM/IEEE Design Automation Conference (DAC)•Jun 22, 2025•0 citations

Om hybrida Schrödinger-Feynman simulatorer : Grunder och analys

Frej Larssen

Quantum computation simulators are essential to test algorithms when real quantum computers are not available. Schrödinger-style simulators store the full state vector that propagates through the circuit. Since the size of the state vector grow exponentially with more qubits, the memory is often a serious constraint for simulators on classical systems. In this work, we conduct an in-depth study of partitioning hybrid Schrödinger-Feynman (HSF) simulators. We develop formal definitions of such simulators and analyze their performance theoretically in terms of time and memory complexity. We propose an alternative version of partitioning HSF-simulators that enables parallelization over partitions, and show that it is useful for shallow circuits. We also arrive at a formula for the time consumption of HSF-simulators using checkpointing. We verify that our formulas coincide with experimental measurements.

•Jan 1, 2025•0 citations

Atlas: Hierarchical Partitioning for Quantum Circuit Simulation on GPUs (Extended Version)

Mingkuan Xu, Shiyi Cao, Xupeng Miao +2 more

This paper presents techniques for theoretically and practically efficient and scalable Schrödinger-style quantum circuit simulation. Our approach partitions a quantum circuit into a hierarchy of subcircuits and simulates the subcircuits on multi-node GPUs, exploiting available data parallelism while minimizing communication costs. To minimize communication costs, we formulate an Integer Linear Program that rewards simulation of "nearby" gates on "nearby" GPUs. To maximize throughput, we use a dynamic programming algorithm to compute the subcircuit simulated by each kernel at a GPU. We realize these techniques in Atlas, a distributed, multi-GPU quantum circuit simulator. Our evaluation on a variety of quantum circuits shows that Atlas outperforms state-of-the-art GPU-based simulators by more than 2$\times$ on average and is able to run larger circuits via offloading to DRAM, outperforming other large-circuit simulators by two orders of magnitude.

arXiv:2408.09055•Aug 17, 2024•2 citations

Atlas: Hierarchical Partitioning for Quantum Circuit Simulation on GPUs

Mingkuan Xu, Shiyi Cao, Xupeng Miao +2 more

This paper presents techniques for theoretically and practically efficient and scalable Schrödinger-style quantum circuit simulation. Our approach partitions a quantum circuit into a hierarchy of subcircuits and simulates the subcircuits on multinode GPUs, exploiting available data parallelism while minimizing communication costs. To minimize communication costs, we formulate an Integer Linear Program that rewards simulation of “nearby” gates on “nearby” GPUs. To maximize throughput, we use a dynamic programming algorithm to compute the subcircuit simulated by each kernel at a GPU. We realize these techniques in Atlas, a distributed, multi-GPU quantum circuit simulator. Our evaluation on a variety of quantum circuits shows that Atlas outperforms state-of-the-art GPU-based simulators by more than $2 \times$ on average and is able to run larger circuits via offloading to DRAM, outperforming other large-circuit simulators by two orders of magnitude.

International Conference for High Performance Computing, Networking, Storage and Analysis (SC)•Nov 17, 2024•9 citations

Fewer Histories, Faster Paths: Distributed Quantum Circuit Feynman Simulation via History Reduction, Checkpointing, and Pruning

Frej Larssen, Luca Pennati, Erik M. Åsgrim +2 more

We present a distributed method for exact sparse-output quantum circuit simulation based on the pure Feynman sum-over-histories formulation. The method computes selected computational-basis amplitudes exactly and addresses the exponential growth of the path sum through a reduced history formulation based on internal-wire assignments, determinism propagation, artificial sources, pruning, and checkpointed reuse. Boundary constraints are propagated through deterministic and wire-preserving gates, and explicit branching variables are introduced only where residual ambiguity remains. Shared work across related histories is captured via an autotuned checkpointed partition. The parallel execution model combines decomposition over requested outputs with concurrent history evaluation, while a dynamic server-worker architecture mitigates load imbalance from irregular branching and pruning. Across the circuit families studied, the method adapts to different structural regimes of the reduced history space: zero artificial sources for QFT under backward analysis, substantial speedups from checkpointing and autotuning for amplitude amplification, and a runtime-fidelity tradeoff from threshold pruning for QAOA. On quantum walk circuits, it reconstructs exact selected-output distributions up to 100 qubits and achieves 85% parallel efficiency on 8,192 CPU cores of a supercomputer.

arXiv:2608.01467•Aug 2, 2026•0 citations

Graph Partitioning Approach for Fast Quantum Circuit Simulation

Jaekyung Im, Seokhyeong Kang

Owing to the exponential increase in computational complexity, the fast simulation of the large quantum circuit has become very difficult. This is an important challenge for the utilization of quantum computers because it is closely related to the verification of quantum computation by classical machines. The Hybrid Schrödinger-Feynman simulation seems to be a promising solution, but its application is very limited. To solve this drawback, we propose an improved simulation method based on graph partitioning. Experimental results show that our approach significantly reduces the simulation time of the Hybrid Schrödinger-Feynman simulation.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 16, 2023•4 citations
Many circuit simulators use either a Schrodinger-based or Feynman-based approach, which have complementary strengths. Schrödinger-based simulators maintain a state vector by synchronously updating it after each gate (or group of gates), ensuring time efficiency at the cost of exponential space. In contrast, Feynman-based simulators use low space but require high time to compute the sum of exponentially many independent Feynman paths. Because they treat paths as independent, Feynman-based simulators miss opportunities to take advantage of sparsity from destructive interference. In this paper, we present a hybrid Schrödinger-Feynman technique which takes advantage of sparsity by selectively synchronizing Feynman paths. Our hybrid technique partitions the circuit into kernels (groups of gates) and uses Feynman simulation within each kernel. It then synchronizes across the kernels by using Schrödinger-style simulation. We parallelize our approach by representing the simulation as a graph, leveraging state-of-the-art parallel graph algorithms. By selecting kernels carefully, we show that our approach can simulate hundreds of qubits efficiently (in both time and space) on just a single multicore node. In certain “sparse” circuits, we are able to improve running times by multiple orders of magnitude.
Despite the continuous advancements in size and robustness of real quantum devices, reliable large-scale quantum computers are not yet available. Hence, classical simulation of quantum algorithms remains crucial for testing new methods and estimating quantum advantage. Pushing classical simulation methods to their limit is essential, particularly due to their inherent exponential complexity. Besides the established Schrödinger-style full statevector simulation, so-called Hybrid Schrödinger-Feynman (HSF) approaches have shown promise to make simulations more efficient. HSF simulation employs the idea of “cutting” the circuit into smaller parts, reducing their execution times. This, however, comes at the cost of an exponential overhead in the number of cuts. Inspired by the domain of Quantum Circuit Cutting, we propose an HSF simulation method based on the idea of “joint cutting” to significantly reduce the aforementioned overhead. This means that, prior to the cutting procedure, gates are collected into “blocks” and all gates in a block are jointly cut instead of individually. We investigate how the proposed refinement can help decrease simulation times and highlight the remaining challenges. Experimental evaluations show that “joint cutting” can outperform the standard HSF simulation by up to a factor ≈4000×\approx 4000 \times≈4000× and the Schrödinger-style simulation by a factor ≈200×\approx 200 \times≈200× for suitable instances. The implementation is available at https://github.com/cda-tum/mqt-qsim-joint-cutting.
Quantum computation simulators are essential to test algorithms when real quantum computers are not available. Schrödinger-style simulators store the full state vector that propagates through the circuit. Since the size of the state vector grow exponentially with more qubits, the memory is often a serious constraint for simulators on classical systems. In this work, we conduct an in-depth study of partitioning hybrid Schrödinger-Feynman (HSF) simulators. We develop formal definitions of such simulators and analyze their performance theoretically in terms of time and memory complexity. We propose an alternative version of partitioning HSF-simulators that enables parallelization over partitions, and show that it is useful for shallow circuits. We also arrive at a formula for the time consumption of HSF-simulators using checkpointing. We verify that our formulas coincide with experimental measurements.
This paper presents techniques for theoretically and practically efficient and scalable Schrödinger-style quantum circuit simulation. Our approach partitions a quantum circuit into a hierarchy of subcircuits and simulates the subcircuits on multi-node GPUs, exploiting available data parallelism while minimizing communication costs. To minimize communication costs, we formulate an Integer Linear Program that rewards simulation of "nearby" gates on "nearby" GPUs. To maximize throughput, we use a dynamic programming algorithm to compute the subcircuit simulated by each kernel at a GPU. We realize these techniques in Atlas, a distributed, multi-GPU quantum circuit simulator. Our evaluation on a variety of quantum circuits shows that Atlas outperforms state-of-the-art GPU-based simulators by more than 2×\times× on average and is able to run larger circuits via offloading to DRAM, outperforming other large-circuit simulators by two orders of magnitude.
This paper presents techniques for theoretically and practically efficient and scalable Schrödinger-style quantum circuit simulation. Our approach partitions a quantum circuit into a hierarchy of subcircuits and simulates the subcircuits on multinode GPUs, exploiting available data parallelism while minimizing communication costs. To minimize communication costs, we formulate an Integer Linear Program that rewards simulation of “nearby” gates on “nearby” GPUs. To maximize throughput, we use a dynamic programming algorithm to compute the subcircuit simulated by each kernel at a GPU. We realize these techniques in Atlas, a distributed, multi-GPU quantum circuit simulator. Our evaluation on a variety of quantum circuits shows that Atlas outperforms state-of-the-art GPU-based simulators by more than 2×2 \times2× on average and is able to run larger circuits via offloading to DRAM, outperforming other large-circuit simulators by two orders of magnitude.
We present a distributed method for exact sparse-output quantum circuit simulation based on the pure Feynman sum-over-histories formulation. The method computes selected computational-basis amplitudes exactly and addresses the exponential growth of the path sum through a reduced history formulation based on internal-wire assignments, determinism propagation, artificial sources, pruning, and checkpointed reuse. Boundary constraints are propagated through deterministic and wire-preserving gates, and explicit branching variables are introduced only where residual ambiguity remains. Shared work across related histories is captured via an autotuned checkpointed partition. The parallel execution model combines decomposition over requested outputs with concurrent history evaluation, while a dynamic server-worker architecture mitigates load imbalance from irregular branching and pruning. Across the circuit families studied, the method adapts to different structural regimes of the reduced history space: zero artificial sources for QFT under backward analysis, substantial speedups from checkpointing and autotuning for amplitude amplification, and a runtime-fidelity tradeoff from threshold pruning for QAOA. On quantum walk circuits, it reconstructs exact selected-output distributions up to 100 qubits and achieves 85% parallel efficiency on 8,192 CPU cores of a supercomputer.
Owing to the exponential increase in computational complexity, the fast simulation of the large quantum circuit has become very difficult. This is an important challenge for the utilization of quantum computers because it is closely related to the verification of quantum computation by classical machines. The Hybrid Schrödinger-Feynman simulation seems to be a promising solution, but its application is very limited. To solve this drawback, we propose an improved simulation method based on graph partitioning. Experimental results show that our approach significantly reduces the simulation time of the Hybrid Schrödinger-Feynman simulation.