Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

A Quantum Algorithmfor the Sub-graph Isomorphism Problem

A Quantum Algorithmfor the Sub-graph Isomorphism Problem We propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Quantum Computing Association for Computing Machinery

A Quantum Algorithmfor the Sub-graph Isomorphism Problem

Download PDF
34 pages

Loading next page...
 
/lp/association-for-computing-machinery/a-quantum-algorithmfor-the-sub-graph-isomorphism-problem-1zT3nUR8Qa
Publisher
Association for Computing Machinery
Copyright
Copyright © 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ISSN
2643-6809
eISSN
2643-6817
DOI
10.1145/3569095
Publisher site
See Article on Publisher Site

Abstract

We propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term.

Journal

ACM Transactions on Quantum Computing – Association for Computing Machinery

Published: Feb 24, 2023

Keywords: Optimization

References

  • Qiskit: An Open-source Framework for Quantum Computing, Zenodo, DOI:https://zenodo
    [,
  • On convex relaxation of graph isomorphism
    [,
  • Number Theory
    [,
  • Graph isomorphism is low for ZPP(NP) and other lowness results
    [,
  • Adiabatic quantum graph matching with permutation matrix constraints
    [,
  • Q-Match: Iterative shape matching via quantum annealing
    [,
  • Modern Graph Theory (1st ed
    [,
  • A subgraph isomorphism algorithm and its application to biochemical data
    [,
  • QUBO formulations for the graph isomorphism problem and related problems
    [,
  • On the variational perspectives to the graph isomorphism problem
    [,
  • Thirty years of graph matching in pattern recognition
    [,
  • The complexity of theorem-proving procedures
    [,
  • A (sub)graph isomorphism algorithm for matching large graphs
    [,
  • Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition
    [,
  • Graph matching using the interference of continuous-time quantum walks
    [,
  • Graph matching using the interference of discrete-time quantum walks
    [,
  • On random graphs I
    [,
  • Incremental graph pattern matching
    [,
  • Graph isomorphism and adiabatic quantum computing
    [,
  • Exact and approximate graph matching using random walks
    [,
  • Limitations of quantum coset states for graph isomorphism
    [,
  • Quantum-assisted quantum compiling
    [,
  • Quantum query complexity of subgraph isomorphism and homomorphism
    [,
  • An in-depth comparison of subgraph isomorphism algorithms in graph databases
    [,
  • The quantum algorithm for graph isomorphism problem
    [,
  • Time constrained continuous subgraph search over streaming graphs
    [,
  • Semidefinite relaxation of quadratic optimization problems
    [,
  • Best approximate quantum compiling problems
    [,
  • When subgraph isomorphism is really hard, and why this matters for graph databases
    [,
  • Practical graph isomorphism, II
    [,
  • On the impossibility of a quantum sieve algorithm for graph isomorphism
    [,
  • Subgraph Isomorphism Search In Massive Graph Data
    [,
  • An exponentially more efficient optimization algorithm for noisy quantum computers
    [,
  • Advanced Linear Algebra
    [,
  • Lie Groups: An Introduction through Linear Groups
    [,
  • The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions
    [,
  • Dagger compact closed categories and completely positive maps: (Extended abstract)
    [,
  • Synthesis of quantum-logic circuits
    [,
  • AllDifferent-based filtering for subgraph isomorphism
    [,
  • In-memory subgraph matching: An in-depth study
    [,
  • Stochastic gradient descent for hybrid quantum-classical optimization
    [,
  • QFAST: Conflating search and numerical optimization for scalable quantum circuit synthesis
    [,
  • Experimental quantum annealing: Case study involving the graph isomorphism problem
    [,