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

The Journal of Supercomputing

Efficient quantum circuit contraction using tensor decision diagrams

Vicente López-Oliva, José M. Badía, Maribel Castillo

Published Dec 30, 2024• 1 citation
Publisher

Abstract

Abstract Simulating quantum circuits efficiently on classical computers is crucial given the limitations of current noisy intermediate-scale quantum devices. This paper adapts and extends two methods used to contract tensor networks within the fast tensor decision diagram (FTDD) framework. The methods, called iterative pairing and block contraction, exploit the advantages of tensor decision diagrams to reduce both the temporal and spatial cost of quantum circuit simulations. The iterative pairing method minimizes intermediate diagram sizes, while the block contraction algorithm efficiently handles circuits with repetitive structures, such as those found in quantum walks and Grover’s algorithm. Experimental results demonstrate that, in some cases, these methods significantly outperform traditional contraction orders like sequential and cotengra in terms of both memory usage and execution time. Furthermore, simulation tools based on decision diagrams, such as FTDD, show superior performance to matrix-based simulation tools, such as Google tensor networks, enabling the simulation of larger circuits more efficiently. These findings show the potential of decision diagram-based approaches to improve the simulation of quantum circuits on classical platforms.

DOI
10.1007/s11227-024-06836-w

Related papers

Simulation Paths for Quantum Circuit Simulation With Decision Diagrams What to Learn From Tensor Networks, and What Not

Lukas Burgholzer, Alexander Ploier, Robert Wille

Simulating quantum circuits on classical computers is a notoriously hard, yet increasingly important task for the development and testing of quantum algorithms. In order to alleviate this inherent complexity, efficient data structures and methods, such as tensor networks and decision diagrams, have been proposed. However, their efficiency heavily depends on the order in which the individual computations are performed. For tensor networks, the order is defined by so-called contraction plans and a plethora of methods has been developed to determine suitable plans. On the other hand, simulation based on decision diagrams is mostly conducted in a straight-forward, i.e., sequential, fashion thus far. In this work, we study the importance of the path that is chosen when simulating quantum circuits using decision diagrams and show, conceptually and experimentally, that choosing the right simulation path can make a vast difference in the efficiency of classical simulations using decision diagrams. We propose an open-source framework (available at github.com/cda-tum/ddsim) that not only allows to investigate of dedicated simulation paths but also to reuse of existing findings, e.g., obtained from determining contraction plans for tensor networks. Experimental evaluations show that translating strategies from the domain of tensor networks may yield speedups of several factors compared to the state of the art. Furthermore, we design a dedicated simulation path heuristic that allows to improve the performance even further—frequently yielding speedups of several orders of magnitude. Finally, we provide an extensive discussion on what can be learned from tensor networks and what cannot.

arXiv:2203.00703•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Aug 10, 2022•19 citations

Quantum Circuit Simulation with Fast Tensor Decision Diagram

Qirui Zhang, Mehdi Saligane, Hun-Seok Kim +3 more

Quantum circuit simulation is a challenging computational problem crucial for quantum computing research and development. The predominant approaches in this area center on tensor networks, prized for their better concurrency and less computation than methods using full quantum vectors and matrices. However, even with the advantages, array-based tensors can have significant redundancy. We present a novel open-source framework that harnesses tensor decision diagrams to eliminate overheads and achieve significant speedups over prior approaches. On average, it delivers a speedup of 37 × over Google’s TensorNetwork library on redundancy-rich circuits, and 25 × and 144 × over quantum multi-valued decision diagram and prior tensor decision diagram implementation, respectively, on Google random quantum circuits. To achieve this, we introduce a new linear-complexity rank simplification algorithm, Tetris, and edge-centric data structures for recursive tensor decision diagram operations. Additionally, we explore the efficacy of tensor network contraction ordering and optimizations from binary decision diagrams.

arXiv:2401.11362•International Symposium on Quality Electronic Design (ISQED)•Apr 3, 2024•9 citations

Scaling Quantum Circuit Simulation: Optimizations for the FTDD Framework

Vicente López-Oliva, Badía Contelles Jose M., Maribel Castillo Catalán

Classical simulation remains essential for the development of quantum algorithms; however, traditional matrix-based methods struggle with scalability. While the Fast Tensor Decision Diagram (FTDD) framework offers a hybrid approach by combining the strengths of Tensor Networks and Decision Diagrams (DDs) for memory-efficient simulation, its core operations are often bottlenecked by memory management structures. Our primary motivation is to address the high computational and spatial cost associated with the hash tables, as well as to simplify the complexity of the simulation workflow. This work introduces systematic, low-level optimizations to the framework. Our main contribution is the enhancement of the memory management layer for the internal tables. We implemented a node reuse mechanism and designed a controlled strategy for hash table growth. These improvements minimize the memory footprint and reduce the costly hashing overhead inherent in DD-based simulators. We performed a thorough experimental analysis using a diverse set of quantum circuits, which were characterized by well-established metrics. Experimental results demonstrate that our enhancements improve the tool's performance and scalability. Notably, these advancements enable the simulation of complex circuits, such as Quantum Fourier Transform, with hundreds of qubits, on a standard server with 2-Tb of memory.

•Apr 27, 2026•0 citations

Contraction Heuristics for Tensor Decision Diagrams

Christian Bøgh Larsen, Simon Brun Olsen, Kim G. Larsen +1 more

In this paper, we study the equivalence problem for quantum circuits: Given two quantum circuits, are they equivalent? We reduce this problem to the contraction problem of a tensor network. The order in which the contraction operations between tensors are applied has a crucial impact on efficiency, which is why many heuristics have been proposed. In this work, we use an efficient representation of tensors as a tensor decision diagram. Since existing contraction heuristics do not perform well in combination with these diagrams, we propose two new contraction heuristics. We demonstrate experimentally that our heuristics outperform other state-of-the-art heuristics. We also demonstrate that our framework yields state-of-the-art performance for equivalence checking.

Entropy•Dec 5, 2024•2 citations

A Tensor Network based Decision Diagram for Representation of Quantum Circuits

Xin Hong, Xiangzhen Zhou, Sanjiang Li +2 more

Tensor networks have been successfully applied in simulation of quantum physical systems for decades. Recently, they have also been employed in classical simulation of quantum computing, in particular, random quantum circuits. This article proposes a decision diagram style data structure, called Tensor Decision Diagram (TDD), for more principled and convenient applications of tensor networks. This new data structure provides a compact and canonical representation for quantum circuits. By exploiting circuit partition, the TDD of a quantum circuit can be computed efficiently. Furthermore, we show that the operations of tensor networks essential in their applications (e.g., addition and contraction) can also be implemented efficiently in TDDs. A proof-of-concept implementation of TDDs is presented and its efficiency is evaluated on a set of benchmark quantum circuits. It is expected that TDDs will play an important role in various design automation tasks related to quantum circuits, including but not limited to equivalence checking, error detection, synthesis, simulation, and verification.

arXiv:2009.02618•ACM Transactions on Design Automation of Electronic Systems•Feb 18, 2022•54 citations

Exploiting Arbitrary Paths for the Simulation of Quantum Circuits with Decision Diagrams

Lukas Burgholzer, Alexander Ploier, Robert Wille

The classical simulation of quantum circuits is essential in the development and testing of quantum algorithms. Methods based on tensor networks or decision diagrams have proven to alleviate the inevitable exponential growth of the underlying complexity in many cases. But the complexity of these methods is very sensitive to so-called contraction plans or simulation paths, respectively, which define the order in which respective operations are applied. While, for tensor networks, a plethora of strategies has been developed, simulation based on decision diagrams is mostly conducted in a straight-forward fashion thus far. In this work, we envision a flow that allows to translate strategies from the domain of tensor networks to decision diagrams. Preliminary results indicate that a substantial advantage may be gained by employing suitable simulation paths-motivating a thorough consideration.

Design, Automation, and Test in Europe•Mar 14, 2022•14 citations
Abstract Simulating quantum circuits efficiently on classical computers is crucial given the limitations of current noisy intermediate-scale quantum devices. This paper adapts and extends two methods used to contract tensor networks within the fast tensor decision diagram (FTDD) framework. The methods, called iterative pairing and block contraction, exploit the advantages of tensor decision diagrams to reduce both the temporal and spatial cost of quantum circuit simulations. The iterative pairing method minimizes intermediate diagram sizes, while the block contraction algorithm efficiently handles circuits with repetitive structures, such as those found in quantum walks and Grover’s algorithm. Experimental results demonstrate that, in some cases, these methods significantly outperform traditional contraction orders like sequential and cotengra in terms of both memory usage and execution time. Furthermore, simulation tools based on decision diagrams, such as FTDD, show superior performance to matrix-based simulation tools, such as Google tensor networks, enabling the simulation of larger circuits more efficiently. These findings show the potential of decision diagram-based approaches to improve the simulation of quantum circuits on classical platforms.
Simulating quantum circuits on classical computers is a notoriously hard, yet increasingly important task for the development and testing of quantum algorithms. In order to alleviate this inherent complexity, efficient data structures and methods, such as tensor networks and decision diagrams, have been proposed. However, their efficiency heavily depends on the order in which the individual computations are performed. For tensor networks, the order is defined by so-called contraction plans and a plethora of methods has been developed to determine suitable plans. On the other hand, simulation based on decision diagrams is mostly conducted in a straight-forward, i.e., sequential, fashion thus far. In this work, we study the importance of the path that is chosen when simulating quantum circuits using decision diagrams and show, conceptually and experimentally, that choosing the right simulation path can make a vast difference in the efficiency of classical simulations using decision diagrams. We propose an open-source framework (available at github.com/cda-tum/ddsim) that not only allows to investigate of dedicated simulation paths but also to reuse of existing findings, e.g., obtained from determining contraction plans for tensor networks. Experimental evaluations show that translating strategies from the domain of tensor networks may yield speedups of several factors compared to the state of the art. Furthermore, we design a dedicated simulation path heuristic that allows to improve the performance even further—frequently yielding speedups of several orders of magnitude. Finally, we provide an extensive discussion on what can be learned from tensor networks and what cannot.
Quantum circuit simulation is a challenging computational problem crucial for quantum computing research and development. The predominant approaches in this area center on tensor networks, prized for their better concurrency and less computation than methods using full quantum vectors and matrices. However, even with the advantages, array-based tensors can have significant redundancy. We present a novel open-source framework that harnesses tensor decision diagrams to eliminate overheads and achieve significant speedups over prior approaches. On average, it delivers a speedup of 37 × over Google’s TensorNetwork library on redundancy-rich circuits, and 25 × and 144 × over quantum multi-valued decision diagram and prior tensor decision diagram implementation, respectively, on Google random quantum circuits. To achieve this, we introduce a new linear-complexity rank simplification algorithm, Tetris, and edge-centric data structures for recursive tensor decision diagram operations. Additionally, we explore the efficacy of tensor network contraction ordering and optimizations from binary decision diagrams.
Classical simulation remains essential for the development of quantum algorithms; however, traditional matrix-based methods struggle with scalability. While the Fast Tensor Decision Diagram (FTDD) framework offers a hybrid approach by combining the strengths of Tensor Networks and Decision Diagrams (DDs) for memory-efficient simulation, its core operations are often bottlenecked by memory management structures. Our primary motivation is to address the high computational and spatial cost associated with the hash tables, as well as to simplify the complexity of the simulation workflow. This work introduces systematic, low-level optimizations to the framework. Our main contribution is the enhancement of the memory management layer for the internal tables. We implemented a node reuse mechanism and designed a controlled strategy for hash table growth. These improvements minimize the memory footprint and reduce the costly hashing overhead inherent in DD-based simulators. We performed a thorough experimental analysis using a diverse set of quantum circuits, which were characterized by well-established metrics. Experimental results demonstrate that our enhancements improve the tool's performance and scalability. Notably, these advancements enable the simulation of complex circuits, such as Quantum Fourier Transform, with hundreds of qubits, on a standard server with 2-Tb of memory.
In this paper, we study the equivalence problem for quantum circuits: Given two quantum circuits, are they equivalent? We reduce this problem to the contraction problem of a tensor network. The order in which the contraction operations between tensors are applied has a crucial impact on efficiency, which is why many heuristics have been proposed. In this work, we use an efficient representation of tensors as a tensor decision diagram. Since existing contraction heuristics do not perform well in combination with these diagrams, we propose two new contraction heuristics. We demonstrate experimentally that our heuristics outperform other state-of-the-art heuristics. We also demonstrate that our framework yields state-of-the-art performance for equivalence checking.
Tensor networks have been successfully applied in simulation of quantum physical systems for decades. Recently, they have also been employed in classical simulation of quantum computing, in particular, random quantum circuits. This article proposes a decision diagram style data structure, called Tensor Decision Diagram (TDD), for more principled and convenient applications of tensor networks. This new data structure provides a compact and canonical representation for quantum circuits. By exploiting circuit partition, the TDD of a quantum circuit can be computed efficiently. Furthermore, we show that the operations of tensor networks essential in their applications (e.g., addition and contraction) can also be implemented efficiently in TDDs. A proof-of-concept implementation of TDDs is presented and its efficiency is evaluated on a set of benchmark quantum circuits. It is expected that TDDs will play an important role in various design automation tasks related to quantum circuits, including but not limited to equivalence checking, error detection, synthesis, simulation, and verification.
The classical simulation of quantum circuits is essential in the development and testing of quantum algorithms. Methods based on tensor networks or decision diagrams have proven to alleviate the inevitable exponential growth of the underlying complexity in many cases. But the complexity of these methods is very sensitive to so-called contraction plans or simulation paths, respectively, which define the order in which respective operations are applied. While, for tensor networks, a plethora of strategies has been developed, simulation based on decision diagrams is mostly conducted in a straight-forward fashion thus far. In this work, we envision a flow that allows to translate strategies from the domain of tensor networks to decision diagrams. Preliminary results indicate that a substantial advantage may be gained by employing suitable simulation paths-motivating a thorough consideration.