Decision Diagrams for Symbolic Verification of Quantum Circuits

EasyChair Preprint 10649

Abstract

With the rapid development of quantum computing, automatic verification of quantum circuits becomes more and more important. While several decision diagrams (DDs)  have been introduced in quantum circuit simulation and verification, none of them supports symbolic computation. Algorithmic manipulations of symbolic objects, however, have been identified as crucial, if not indispensable, for several verification tasks. This paper proposes the first decision-diagram approach for operating symbolic objects and verifying quantum circuits with symbolic terms. As a notable example, our symbolic tensor decision diagrams (symbolic TDD) could verify the functionality of the 160-qubit quantum Fourier transform circuit within three minutes. Moreover, as demonstrated on Bernstein-Vazirani algorithm, Grover's algorithm, and the bit-flip error correction code, the symbolic TDD enables efficient verification of quantum circuits with user-supplied oracles and/or classical controls.

Keyphrases: decision diagram, simulation, symbolic verification

@booklet{EasyChair:10649,
  author    = {Xin Hong and Wei-Jia Huang and Wei-Chen Chien and Yuan Feng and Min-Hsiu Hsieh and Sanjiang Li and Chia-Shun Yeh and Mingsheng Ying},
  title     = {Decision Diagrams for Symbolic Verification of Quantum Circuits},
  howpublished = {EasyChair Preprint 10649},
  year      = {EasyChair, 2023}}