aiqbench analysis
This paper advances the theoretical understanding of Ising and Clifford quantum computers by extending classical simulation limits from braidings to measurements. It establishes rigorous complexity class separations between P and PSPACE under specific circuit generator assumptions, clarifying the computational boundaries of these models.
Computational Power of Clifford and Ising Quantum Computers
From arXiv
Full textarXiv:2611.13347v1 Announce Type: new Abstract: We extend the efficient classical simulation of Ising quantum computers from braidings to measurements. We investigate several different definitions of efficient Clifford quantum computation by varying the power of the circuit generator. In case the circuit generator can see the entire input, we give a detailed proof that efficient simulation of classical computation would imply the separation of complexity classes $\mathbf{P}$ and $\mathbf{PSPACE}$. If the circuit generator sees only the input length, we prove that Clifford quantum computers decide what we call affine languages.
Abstract:We extend the efficient classical simulation of Ising quantum computers from braidings to measurements. We investigate several different definitions of efficient Clifford quantum computation by varying the power of the circuit generator. In case the circuit generator can see the entire input, we give a detailed proof that efficient simulation of classical computation would imply the separation of complexity classes $\mathbf{P}$ and $\mathbf{PSPACE}$. If the circuit generator sees only the input length, we prove that Clifford quantum computers decide what we call affine languages.
Quantum Physics (quant-ph); Computational Complexity (cs.CC); Quantum Algebra (math.QA)
arXiv:2611.13347 [quant-ph]
(or arXiv:2611.13347v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2611.13347 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 184 words


