Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
- URL: http://arxiv.org/abs/2404.10913v1
- Date: Tue, 16 Apr 2024 21:17:59 GMT
- Title: Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
- Authors: Piotr Mitosek,
- Abstract summary: We show that circuit extraction for phase-free ZH calculus is $mathord#mathrm P$-hard.
We also show that two closely related problems are $mathrmNPmathord#mathrm P$-complete.
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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- 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 ${\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.
Related papers
- Provably learning a multi-head attention layer [55.2904547651831]
Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models.
In this work, we initiate the study of provably learning a multi-head attention layer from random examples.
We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
arXiv Detail & Related papers (2024-02-06T15:39:09Z) - Parity vs. AC0 with simple quantum preprocessing [0.0]
We study a hybrid circuit model where $mathsfAC0$ operates on measurement outcomes of a $mathsfQNC0$ circuit.
We find that while $mathsfQNC0$ is surprisingly powerful for search and sampling tasks, that power is "locked away" in the global correlations of its output.
arXiv Detail & Related papers (2023-11-22T20:27:05Z) - On the Pauli Spectrum of QAC0 [2.3436632098950456]
We conjecture that the Pauli spectrum of $mathsfQAC0$ satisfies low-degree concentration.
We obtain new circuit lower bounds and learning results as applications.
arXiv Detail & Related papers (2023-11-16T07:25:06Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model.
This learning model is widely used as an abstract computational model for most generic learning algorithms.
arXiv Detail & Related papers (2023-05-09T20:53:27Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation.
For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
We study the complexity of PAC learning halfspaces in the presence of Massart noise.
We show that no-time Massart halfspace learners can achieve error better than $Omega(eta)$, even if the optimal 0-1 error is small.
arXiv Detail & Related papers (2022-07-28T17:50:53Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations.
The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
arXiv Detail & Related papers (2022-06-17T17:55:43Z) - Circuit Extraction for ZX-diagrams can be #P-hard [0.0]
Some applications for the ZX-calculus rely on being able to efficiently translate a ZX-diagram back into a quantum circuit of comparable size.
In this paper we show that the circuit extraction problem is #P-hard, and so is itself at least as hard as strong simulation of quantum circuits.
arXiv Detail & Related papers (2022-02-18T13:50:24Z) - Quantum double aspects of surface code models [77.34726150561087]
We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry.
We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
arXiv Detail & Related papers (2021-06-25T17:03:38Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
We prove under the theoretical complexity of the non-concentration hierarchy that approximating the output probabilities to within $2-Omega(nlogn)$ is hard.
We show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including trivial circuit with identity gates.
arXiv Detail & Related papers (2021-02-03T09:20:32Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
We establish the first general connection between the design of quantum algorithms and circuit lower bounds.
Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
arXiv Detail & Related papers (2020-12-03T14:03:20Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.