Planar #CSP Equality Corresponds to Quantum Isomorphism -- A Holant Viewpoint

• URL: http://arxiv.org/abs/2212.03335v3
• Date: Fri, 5 May 2023 19:20:30 GMT
• Title: Planar #CSP Equality Corresponds to Quantum Isomorphism -- A Holant Viewpoint
• Authors: Jin-Yi Cai (University of Wisconsin-Madison) and Ben Young (University of Wisconsin-Madison)
• Abstract summary: Graph homomorphism is the special case where each of $mathcalF$ and $mathcalF'$ contains a single symmetric 0-1-valued binary constraint function. We show that any pair of sets $mathcalF$ and $mathcalF'$ of real-valued, arbitrary-arity constraint functions give the same value on any planar #CSP instance.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, Man\v{c}inska and Roberson proved that two graphs $G$ and $G'$ are quantum isomorphic if and only if they admit the same number of homomorphisms from all planar graphs. We extend this result to planar #CSP with any pair of sets $\mathcal{F}$ and $\mathcal{F}'$ of real-valued, arbitrary-arity constraint functions. Graph homomorphism is the special case where each of $\mathcal{F}$ and $\mathcal{F}'$ contains a single symmetric 0-1-valued binary constraint function. Our treatment uses the framework of planar Holant problems. To prove that quantum isomorphic constraint function sets give the same value on any planar #CSP instance, we apply a novel form of holographic transformation of Valiant, using the quantum permutation matrix $\mathcal{U}$ defining the quantum isomorphism. Due to the noncommutativity of $\mathcal{U}$'s entries, it turns out that this form of holographic transformation is only applicable to planar Holant. To prove the converse, we introduce the quantum automorphism group Qut$(\mathcal{F})$ of a set of constraint functions $\mathcal{F}$, and characterize the intertwiners of Qut$(\mathcal{F})$ as the signature matrices of planar Holant$(\mathcal{F}\,|\,\mathcal{EQ})$ quantum gadgets. Then we define a new notion of (projective) connectivity for constraint functions and reduce arity while preserving the quantum automorphism group. Finally, to address the challenges posed by generalizing from 0-1 valued to real-valued constraint functions, we adapt a technique of Lov\'asz in the classical setting for isomorphisms of real-weighted graphs to the setting of quantum isomorphisms.

Related papers

• Geometry of degenerate quantum states, configurations of $m$-planes and invariants on complex Grassmannians [55.2480439325792]
  We show how to reduce the geometry of degenerate states to the non-abelian connection $A$. We find independent invariants associated with each triple of subspaces. Some of them generalize the Berry-Pancharatnam phase, and some do not have analogues for 1-dimensional subspaces.
  arXiv  Detail & Related papers  (2024-04-04T06:39:28Z)
• Quantum Current and Holographic Categorical Symmetry [62.07387569558919]
  A quantum current is defined as symmetric operators that can transport symmetry charges over an arbitrary long distance. The condition for quantum currents to be superconducting is also specified, which corresponds to condensation of anyons in one higher dimension.
  arXiv  Detail & Related papers  (2023-05-22T11:00:25Z)
• Quantum isomorphism of graphs from association schemes [0.0]
  We show that any two Hadamard graphs on the same number of vertices are quantum isomorphic. This follows from a more general recipe for showing quantum isomorphism of graphs arising from certain association schemes.
  arXiv  Detail & Related papers  (2022-09-10T03:22:28Z)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
  arXiv  Detail & Related papers  (2022-08-12T15:05:07Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  We show how all properties of a quantum manifold of states are fully described by a gauge-invariant Bargmann. We show how our results have immediate applications to the modern theory of polarization.
  arXiv  Detail & Related papers  (2022-05-30T18:01:34Z)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  The observables associated with a quantum system $S$ form a non-commutative algebra $mathcal A_S$. It is assumed that a density matrix $rho$ can be determined from the expectation values of observables. Abelian algebras do not have inner automorphisms, so the measurement apparatus can determine mean values of observables.
  arXiv  Detail & Related papers  (2021-12-14T16:29:53Z)
• 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)
• Classification of equivariant quasi-local automorphisms on quantum chains [0.0]
  We classify automorphisms on quantum chains, allowing both spin and fermionic degrees of freedom, that are equivariant with respect to a local symmetry action of a finite symmetry group $G$. We find that the equivalence classes are uniquely labeled by an index taking values in $mathbbQ cup sqrt2 mathbbQ times mathrmHom(G, mathbbZ_2) times H2(G, U(1))$.
  arXiv  Detail & Related papers  (2021-06-03T21:41:05Z)
• Representation of symmetry transformations on the sets of tripotents of spin and Cartan factors [0.0]
  We prove that in order that the description of the spin will be relativistic, it is not enough to preserve the projection lattice equipped with its natural partial order and denoteity. This, in particular, extends a result of Moln'ar to the wider setting of atomic JBW$*$-triples not containing rank-one Cartan factors.
  arXiv  Detail & Related papers  (2021-01-03T17:21:02Z)
• Classical Dynamics from Self-Consistency Equations in Quantum Mechanics -- Extended Version [0.0]
  We propose a new mathematical approach to Bona's non-linear generalization of quantum mechanics. It highlights the central role of self-consistency. Some new mathematical concepts are introduced, which are possibly interesting by themselves.
  arXiv  Detail & Related papers  (2020-09-10T16:20:25Z)
• Graph Homomorphism Convolution [19.94778871237204]
  We show that graph homomorphism numbers provide a natural invariant (isomorphism invariant and $mathcalF$-invariant) embedding maps which can be used for graph classification. By choosing $mathcalF$ whose elements have bounded tree-width, we show that the homomorphism method is efficient compared with other methods.
  arXiv  Detail & Related papers  (2020-05-03T23:56: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.