License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.119
URN: urn:nbn:de:0030-drops-164601
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16460/
de Beaudrap, Niel ;
Kissinger, Aleks ;
van de Wetering, John
Circuit Extraction for ZX-Diagrams Can Be #P-Hard
Abstract
The ZX-calculus is a graphical language for reasoning about quantum computation using ZX-diagrams, a certain flexible generalisation of quantum circuits that can be used to represent linear maps from m to n qubits for any m,n ≥ 0. Some applications for the ZX-calculus, such as quantum circuit optimisation and synthesis, rely on being able to efficiently translate a ZX-diagram back into a quantum circuit of comparable size. While several sufficient conditions are known for describing families of ZX-diagrams that can be efficiently transformed back into circuits, it has previously been conjectured that the general problem of circuit extraction is hard. That is, that it should not be possible to efficiently convert an arbitrary ZX-diagram describing a unitary linear map into an equivalent quantum circuit. In this paper we prove this conjecture by showing that the circuit extraction problem is #P-hard, and so is itself at least as hard as strong simulation of quantum circuits. In addition to our main hardness result, which relies specifically on the circuit representation, we give a representation-agnostic hardness result. Namely, we show that any oracle that takes as input a ZX-diagram description of a unitary and produces samples of the output of the associated quantum computation enables efficient probabilistic solutions to NP-complete problems.
BibTeX - Entry
@InProceedings{debeaudrap_et_al:LIPIcs.ICALP.2022.119,
author = {de Beaudrap, Niel and Kissinger, Aleks and van de Wetering, John},
title = {{Circuit Extraction for ZX-Diagrams Can Be #P-Hard}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {119:1--119:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16460},
URN = {urn:nbn:de:0030-drops-164601},
doi = {10.4230/LIPIcs.ICALP.2022.119},
annote = {Keywords: ZX-calculus, circuit extraction, quantum circuits, #P}
}
|
Keywords: |
|
ZX-calculus, circuit extraction, quantum circuits, #P |
|
Collection: |
|
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
28.06.2022 |
