Quantum Polymorphisms and Commutativity Gadgets

• URL: http://arxiv.org/abs/2511.23445v1
• Date: Fri, 28 Nov 2025 18:37:36 GMT
• Title: Quantum Polymorphisms and Commutativity Gadgets
• Authors: Lorenzo Ciardo, Gideo Joubert, Antoine Mottet,
• Abstract summary: We give a full characterisation of the existence of commutativity gadgets for relational structures.<n>We prove that the entangled CSP parameterised by odd cycles is undecidable.<n>We establish a quantum version of Galois connection for entangled CSPs in the case of non-oracular quantum homomorphisms.
• Score: 2.8726155411976535
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce the concept of quantum polymorphisms to the complexity theory of non-local games. We use this notion to give a full characterisation of the existence of commutativity gadgets for relational structures, introduced by Ji as a method for achieving quantum soundness of classical CSP reductions. Prior to our work, a classification was only known in the Boolean case [Culf--Mastel, STOC'25]. As an application of our framework, we prove that the entangled CSP parameterised by odd cycles is undecidable. Furthermore, we establish a quantum version of Galois connection for entangled CSPs in the case of non-oracular quantum homomorphisms.

Related papers

• Hardness of classically sampling quantum chemistry circuits [0.0]
  We extend the scope to address quantum advantage in tasks relevant to chemistry and physics.<n>We show that a class of unitary cluster Jastrow (UCJ) ansatz can be used to perform arbitrary quantum-time computations.<n>Our demonstration, worst-case nonsimbility of UCJ, would potentially imply quantum advantage in quantum algorithms for chemistry and physics.
  arXiv  Detail & Related papers  (2025-04-17T12:34:33Z)
• Relational Quantum Geometry [0.0]
  We identify non-commutative or quantum geometry as a mathematical framework which unifies three objects. We first provide a rigorous account of the extended phase space, and demonstrate that it can be regarded as a classical principal bundle with a Poisson manifold base. We conclude that the quantum orbifold is equivalent to the G-framed algebra proposed in prior work.
  arXiv  Detail & Related papers  (2024-10-14T19:29:27Z)
• Quantum channels, complex Stiefel manifolds, and optimization [45.9982965995401]
  We establish a continuity relation between the topological space of quantum channels and the quotient of the complex Stiefel manifold. The established relation can be applied to various quantum optimization problems.
  arXiv  Detail & Related papers  (2024-08-19T09:15:54Z)
• Efficient classical simulation of quantum computation beyond Wigner positivity [0.0]
  We present the generalization of the CNC formalism, based on closed and noncontextual sets of Pauli observables, to the setting of odd-prime-dimensional qudits.
  arXiv  Detail & Related papers  (2024-07-14T22:25:13Z)
• Quantum Advantage and CSP Complexity [1.90365714903665]
  Information-processing tasks modelled by homomorphisms between relational structures can witness quantum advantage when entanglement is used as a computational resource. We prove that the occurrence of quantum advantage is determined by the same type of algebraic structure that captures the polymorphism identities of CSPs.
  arXiv  Detail & Related papers  (2024-04-19T21:23:03Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• The Min-Entropy of Classical-Quantum Combs for Measurement-Based Applications [0.5999777817331317]
  We formalise multi-round learning processes using a generalisation of classical-quantum states, called classical-quantum combs. We focus attention on an array of problems derived from measurement-based quantum computation (MBQC) and related applications.
  arXiv  Detail & Related papers  (2022-12-01T15:01:19Z)
• Chaos in coupled Kerr-nonlinear parametric oscillators [0.0]
  We investigate complex dynamics, i.e., chaos, in two coupled nondissipative KPOs at a few-photon level. We conclude that some of them can be regarded as quantum signatures of chaos, together with energy-level spacing statistics.
  arXiv  Detail & Related papers  (2021-10-08T10:35:12Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• Quantum information spreading in a disordered quantum walk [50.591267188664666]
  We design a quantum probing protocol using Quantum Walks to investigate the Quantum Information spreading pattern. We focus on the coherent static and dynamic disorder to investigate anomalous and classical transport. Our results show that a Quantum Walk can be considered as a readout device of information about defects and perturbations occurring in complex networks.
  arXiv  Detail & Related papers  (2020-10-20T20:03:19Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
  arXiv  Detail & Related papers  (2020-04-24T17:58:10Z)
• From a quantum theory to a classical one [117.44028458220427]
  We present and discuss a formal approach for describing the quantum to classical crossover. The method was originally introduced by L. Yaffe in 1982 for tackling large-$N$ quantum field theories.
  arXiv  Detail & Related papers  (2020-04-01T09:16:38Z)

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.