NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

• URL: http://arxiv.org/abs/2407.10635v1
• Date: Mon, 15 Jul 2024 11:48:09 GMT
• Title: NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
• Authors: Prem Nigam Kar, David E. Roberson, Tim Seppelt, Peter Zeman,
• Abstract summary: We show that each level of the NPA hierarchy of SDP relaxations for quantum isomorphism of graphs is equivalent to homomorphism indistinguishability over an appropriate class of planar graphs. This homomorphism indistinguishability characterization also allows us to give a randomized-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.
• Score: 0.18749305679160366
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Man\v{c}inska and Roberson~[FOCS'20] showed that two graphs are quantum isomorphic if and only if they are homomorphism indistinguishable over the class of planar graphs. Atserias et al.~[JCTB'19] proved that quantum isomorphism is undecidable in general. The NPA hierarchy gives a sequence of semidefinite programming relaxations of quantum isomorphism. Recently, Roberson and Seppelt~[ICALP'23] obtained a homomorphism indistinguishability characterization of the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism. We prove a quantum analogue of this result by showing that each level of the NPA hierarchy of SDP relaxations for quantum isomorphism of graphs is equivalent to homomorphism indistinguishability over an appropriate class of planar graphs. By combining the convergence of the NPA hierarchy with the fact that the union of these graph classes is the set of all planar graphs, we are able to give a new proof of the result of Man\v{c}inska and Roberson~[FOCS'20] that avoids the use of the theory of quantum groups. This homomorphism indistinguishability characterization also allows us to give a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.

Related papers

• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• Probing Graph Representations [77.7361299039905]
  We use a probing framework to quantify the amount of meaningful information captured in graph representations. Our findings on molecular datasets show the potential of probing for understanding the inductive biases of graph-based models. We advocate for probing as a useful diagnostic tool for evaluating graph-based models.
  arXiv  Detail & Related papers  (2023-03-07T14:58:18Z)
• Planar #CSP Equality Corresponds to Quantum Isomorphism -- A Holant Viewpoint [0.0]
  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.
  arXiv  Detail & Related papers  (2022-12-06T21:38:40Z)
• 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)
• Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling [0.0]
  A graph can be represented as a point set in enough dimensions using a simplex embedding and sampling. The isomorphism of them corresponds to the existence of a perfect registration between the point set forms of the graphs. The related idea of equivalence classes suggests that graph canonization may be an important tool in tackling graph isomorphism problem.
  arXiv  Detail & Related papers  (2021-11-15T12:16:21Z)
• 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)
• Relative stability toward diffeomorphisms in deep nets indicates performance [66.51503682738931]
  We show that stability toward diffeomorphisms does not strongly correlate to performance on benchmark data sets of images. We find that the stability toward diffeomorphisms relative to that of generic transformations $R_f$ correlates remarkably with the test error $epsilon_t$. For CIFAR10 and 15 known architectures, we find $epsilon_tapprox 0.2sqrtR_f$, suggesting that obtaining a small $R_f$ is important to achieve good performance.
  arXiv  Detail & Related papers  (2021-05-06T07:03:30Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
  Graph-Augmented Multi-Layer Perceptrons (GA-MLPs) first augments node features with certain multi-hop operators on the graph. We prove a separation in expressive power between GA-MLPs and GNNs that grows exponentially in depth.
  arXiv  Detail & Related papers  (2020-10-28T17:59:59Z)
• Algebraic Neural Networks: Stability to Deformations [179.55535781816343]
  We study algebraic neural networks (AlgNNs) with commutative algebras. AlgNNs unify diverse architectures such as Euclidean convolutional neural networks, graph neural networks, and group neural networks.
  arXiv  Detail & Related papers  (2020-09-03T03:41:38Z)
• 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.