Contraction Heuristics using Tensor Decision Diagram Size Estimation for Quantum Circuit Equivalence Checking
Authors
Olsen, Simon Brun ; Larsen, Christian Bøgh
Term
4. term
Education
Publication year
2024
Submitted on
2024-05-31
Pages
19
Abstract
At kontrollere om to kvantekredsløb gør det samme (ækvivalenstjek) afhænger i høj grad af, hvordan kredsløbene repræsenteres og behandles på en klassisk computer. Denne afhandling arbejder med Tensor Decision Diagrams (TDD’er), en kompakt datastruktur til at repræsentere kvanteporte og -kredsløb. Ved ækvivalenstjek med TDD’er findes der mange mulige rækkefølger til at kombinere dele af diagrammet—såkaldte kontraktionsplaner—og den valgte rækkefølge påvirker tids- og hukommelsesforbrug markant. Eksisterende heuristikker til at vælge en kontraktionsplan tager kun højde for de underliggende tensorer, ikke for de faktiske TDD-størrelser, der opstår undervejs. Dermed går man glip af potentiale for bedre planer. Afhandlingen introducerer en metode til at estimere, hvor stor en TDD bliver efter en kontraktion, og bruger dette til at udvikle nye heuristikker. For at lave disse estimater trænes en model baseret på et neuralt netværk på et speciallavet datasæt. Forudsigelserne anvendes i to heuristikker: én, der planlægger og kontraherer i diskrete vinduer, og én baseret på Monte Carlo Tree Search. Derudover evalueres to håndlavede heuristikker. Den første, Lookahead, udfører faktiske kontraktioner frem for at nøjes med estimater. Den anden, EMIT, efterligner Lookahead ved at prioritere kontraktion af de TDD’er, der hidtil er kontraheret mindst. Alle heuristikkerne evalueres på benchmark-kredsløb. På udvalgte kredsløb giver den neurale model fordele i forhold til eksisterende heuristikker. Lookahead overgår eksisterende heuristikker, fordi den ikke kræver indledende planlægning. EMIT er samlet set den hurtigste på de fleste kredsløb, da den hverken har en omfattende planlægningsfase eller ekstra dyre kontraktioner. Samlet set overgår metoderne state-of-the-art værktøjer til kontraktionsplanlægning ved TDD-baseret ækvivalenstjek og opnår køretider, der er på niveau med de bedste ækvivalenstjekkere.
Verifying that two quantum circuits behave the same (equivalence checking) depends strongly on how the circuits are represented and manipulated on a classical computer. This thesis uses Tensor Decision Diagrams (TDDs), a compact data structure for representing quantum gates and circuits. When checking equivalence with TDDs, there are many possible orders for combining parts of the diagram—called contraction plans—and the chosen order has a major impact on time and memory. Existing heuristics for choosing a contraction plan consider only the underlying tensors, not the actual sizes of the resulting TDDs, leaving performance untapped. The thesis introduces a method to estimate how large a TDD will become after a contraction and uses it to design new heuristics. To make these estimates, a neural network model is trained on a custom dataset. Its predictions drive two heuristics: one that plans and contracts in discrete windows, and one based on Monte Carlo Tree Search. Two hand-crafted heuristics are also evaluated. The first, Lookahead, performs actual contractions instead of relying on estimates. The second, EMIT, imitates Lookahead by prioritizing the TDDs that have been contracted the least. All heuristics are evaluated on benchmark circuits. On selected circuits, the neural-network–guided approach improves over existing heuristics. Lookahead outperforms existing heuristics because it avoids an initial planning phase. EMIT is the fastest overall on most circuits, as it has neither an elaborate planning step nor additional costly contractions. Overall, the methods outperform state-of-the-art contraction-planning tools for TDD-based equivalence checking and achieve runtimes comparable to state-of-the-art equivalence checkers.
[This summary has been rewritten with the help of AI based on the project's original abstract]
Keywords
Kvante ; Datastruktur ; Tensor
Documents