Constructing ${\mathrm{NP}}^{\#\mathrm{P}}$-complete problems and $\#\mathrm{P}$-hardness of circuit extraction in phase-free ZH

Abstract

The ZH calculus is a graphical language for quantum computation reasoning. The phase-free variant offers a simple set of generators that guarantee universality. ZH calculus is effective in MBQC and analysis of quantum circuits constructed with the universal gate set Toffoli+H. While circuits naturally translate to ZH diagrams, finding an ancilla-free circuit equivalent to a given diagram is hard. Here, we show that circuit extraction for phase-free ZH calculus is $\#\mathrm{P}$-hard, extending the existing result for ZX calculus. Another problem believed to be hard is comparing whether two diagrams represent the same process. We show that two closely related problems are ${\mathrm{NP}}^{\#\mathrm{P}}$-complete. The first problem is: given two processes represented as diagrams, determine the existence of a computational basis state on which they equalize. The second problem is checking whether the matrix representation of a given diagram contains an entry equal to a given number. Our proof adapts the proof of Cook-Levin theorem to a reduction from a non-deterministic Turing Machine with access to $\#\mathrm{P}$ oracle.

24 pages, 4 figures, based on author's QPL 2023 talk with the same title