Graph comparison via nonlinear quantum search

Abstract

In this paper we present an efficiently scaling quantum algorithm which finds the size of the maximum common edge subgraph for a pair of arbitrary graphs and thus provides a meaningful measure of graph similarity. The algorithm makes use of a two-part quantum dynamic process: in the first part we obtain information crucial for the comparison of two graphs through linear quantum computation. However, this information is hidden in the quantum system with vanishingly small amplitude that even quantum algorithms such as Grover's search are not fast enough to distill the information efficiently. In order to extract the information we call upon techniques in nonlinear quantum computing to provide the speed-up necessary for an efficient algorithm. The linear quantum circuit requires $\mathcal{O}(n^3{\log }^3(n)\log \log (n))$ elementary quantum gates and the nonlinear evolution under the Gross-Pitaevskii equation has a time scaling of $\mathcal{O}(\frac{1}{g}{n}^2{\log }^3(n)\log \log (n))$, where $n$ is the number of vertices in each graph and $g$ is the strength of the Gross-Pitaveskii non-linearity. Through this example, we demonstrate the power of nonlinear quantum search techniques to solve a subset of NP-hard problems.

References in corpus (15)

• Elementary gates for quantum computation
• Ising formulations of many NP problems
• Quantum Algorithms Revisited
• Quantum Networks for Elementary Arithmetic Operations
• Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
• A Quantum Algorithm for Finding the Minimum
• Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
• Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
• DELTACON: A Principled Massive-Graph Similarity Function
• Generalised phase kick-back: the structure of computational algorithms from physical principles
• Optimal state discrimination and unstructured search in nonlinear quantum mechanics
• Quantum Search with General Nonlinearities
• Quantum walk of a Bose-Einstein condensate in the Brillouin zone
• Quantum search with interacting Bose-Einstein condensates
• On nonlinear scattering for quantum walks