Contraction Heuristics for Tensor Decision Diagrams

Entropy (Basel). 2024 Dec 5;26(12):1058. doi: 10.3390/e26121058.

Abstract

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.

Keywords: contraction planning; equivalence checking; heuristics; quantum circuit; tensor decision diagram; tensor network.