  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 ${\mathord{\#}\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}^{\mathord{\#}\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
${\mathord{\#}\mathrm P}$ oracle.
