Constructing $\mathrmNP^\mathord\#\mathrm P$-complete problems and $\mathord\#\mathrm P$-hardness of circuit extraction in phase-free ZH
<|reference_start|>Constructing $\mathrmNP^\mathord\#\mathrm P$-complete problems and $\mathord\#\mathrm P$-hardness of circuit extraction in phase-free ZH: 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.<|reference_end|>
@article{mitosek2024constructing,
    title={Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and
  ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH},
    author={Piotr Mitosek},
    journal={arXiv preprint arXiv:2404.10913},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.10913},
    primaryClass={quant-ph cs.CC}
}