Contraction Heuristics using Tensor Decision Diagram Size Estimation for Quantum Circuit Equivalence Checking

Olsen, Simon Brun ; Larsen, Christian Bøgh

4. term

Computer Science, Master

2024

2024-05-31

19 pages

Quantum circuit equivalence checking inherently depends on how quantum circuits are represented on a classical computer. Tensor Decision Diagrams (TDDs) efficiently represent quantum gates and quantum circuits. TDDs allow the equivalence checking process to be done in multiple possible orderings, called contraction plans. Current contraction plan heuristics do not consider the sizes of TDDs but only the tensors they are based on. This leaves unexplored potential in the heuristics for constructing efficient contraction plans. This unexplored potential is the focus of this thesis. A way of estimating the size of a TDD resulting from a contraction is devised to create new heuristics. To predict such sizes, we train a neural network model on a custom dataset. The prediction model is then used to create two different heuristics: a heuristic that plans and contracts in discrete windows and a heuristic based on Monte Carlo tree search. Two handcrafted heuristics are also evaluated. The first, Lookahead, does the actual contractions as opposed to estimating them. The second, called EMIT, emulates the Lookahead heuristic by contracting the TDDs that have been contracted the least. All the contraction planning heuristics are evaluated on benchmark circuits. We conclude that using the neural network model has advantages over existing heuristics on select circuits. The Lookahead heuristic outperforms existing heuristics as it requires no initial planning time. The EMIT heuristic is the fastest overall on most circuits as it neither has an elaborate planning step nor additional expensive contractions. We outperform state-of-the-art contraction planning tools on equivalence checking using TDDs, and we achieve results comparable in time with state-of-the-art equivalence checking tools.

Kvante ; Datastruktur ; Tensor

Download
View record in AAU Student Projects