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.
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.
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.
Abstract Quantum computing holds the potential to solve complex problems currently beyond the capabilities of classical computers by exploiting the principles of quantum mechanics. However, due to the immaturity of such computers and the inability to know the state of the circuit during execution, efficient quantum simulators on classical computers are needed. This paper compares different methods for the contraction of quantum circuits represented as tensor networks. Tensor Decision Diagrams (TDD) are used to implement two contraction ordering methods that exploit the structure of the circuits to reduce temporal and spatial costs. Experimental results show that these methods improve other well established approaches and that they are faster that other well-known simulation tools based on other circuit representations. In addition, an analysis of different implementations of the same quantum algorithm highlights the impact of gate sets on contraction efficiency.
Verifying whether two quantum circuits realize the same unitary is vital for optimization and compilation. However, approaches based on tensor network contraction often suffer from exponential blow-ups, not least since finding an optimal contraction order is NP-hard. We address this by employing tensor decision diagrams and formulating contraction as a sequential decision-making task. A reinforcement learning agent, trained via proximal policy optimization with a graph neural network policy, learns contraction orders to minimize both floating-point operations and peak memory. Our evaluation shows that the learned policy consistently outperforms heuristic baselines in running time while maintaining competitive memory usage, highlighting the potential of AI for scalable quantum circuit verification.
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.
Despite the rapid development of quantum computing these years, state-of-the-art quantum devices still contain only a limited number of qubits. One possible way to execute more realistic algorithms in near-term quantum devices is to employ dynamic quantum circuits (DQCs). In DQCs, measurements can happen during the circuit, and their outcomes can be processed with classical computers and used to control other parts of the circuit. This technique can help significantly reduce the qubit resources required to implement a quantum algorithm. In this paper, we give a formal definition of DQCs and then characterise their functionality in terms of ensembles of linear operators, following the Kraus representation of superoperators. We further interpret DQCs as tensor networks, implement their functionality as tensor decision diagrams (TDDs), and reduce the equivalence of two DQCs to checking if they have the same TDD representation. Experiments show that embedding classical logic into conventional quantum circuits does not incur a significant time and space burden.
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.