English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The ZX-calculus is a graphical language for reasoning about quantumcomputation using ZX-diagrams, a certain flexible generalisation of quantumcircuits that can be used to represent linear maps from $m$ to $n$ qubits forany $m,n \geq 0$. Some applications for the ZX-calculus, such as quantumcircuit optimisation and synthesis, rely on being able to efficiently translatea ZX-diagram back into a quantum circuit of comparable size. While severalsufficient conditions are known for describing families of ZX-diagrams that canbe efficiently transformed back into circuits, it has previously beenconjectured that the general problem of circuit extraction is hard. That is,that it should not be possible to efficiently convert an arbitrary ZX-diagramdescribing a unitary linear map into an equivalent quantum circuit. In thispaper we prove this conjecture by showing that the circuit extraction problemis #P-hard, and so is itself at least as hard as strong simulation of quantumcircuits. In addition to our main hardness result, which relies specifically onthe circuit representation, we give a representation-agnostic hardness result.Namely, we show that any oracle that takes as input a ZX-diagram description ofa unitary and produces samples of the output of the associated quantumcomputation enables efficient probabilistic solutions to NP-complete problems.

Circuit Extraction for ZX-diagrams can be #P-hard