Graph isomorphism and Gaussian boson sampling

DOI10.1515/SPMA-2020-0132zbMATH Open1476.05108arXiv1810.10644OpenAlexW2898444729MaRDI QIDQ825567FDOQ825567

Authors: Kamil Brádler, S. Friedland, Nathan Killoran, Daiqin Su, Josh A. Izaac 

Publication date: 17 December 2021

Published in: Special Matrices (Search for Journal in Brave)

Abstract: We introduce a connection between a near-term quantum computing device, specifically a Gaussian boson sampler, and the graph isomorphism problem. We propose a scheme where graphs are encoded into quantum states of light, whose properties are then probed with photon-number-resolving detectors. We prove that the probabilities of different photon-detection events in this setup can be combined to give a complete set of graph invariants. Two graphs are isomorphic if and only if their detection probabilities are equivalent. We present additional ways that the measurement probabilities can be combined or coarse-grained to make experimental tests more amenable. We benchmark these methods with numerical simulations on the Titan supercomputer for several graph families: pairs of isospectral nonisomorphic graphs, isospectral regular graphs, and strongly regular graphs.

Full work available at URL: https://arxiv.org/abs/1810.10644

Recommendations

• Classical benchmarking of Gaussian boson sampling on the Titan supercomputer
• A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems
• The classical complexity of boson sampling
• Boson sampling with non-identical single photons
• A classical approach to the graph isomorphism problem using quantum walks

zbMATH Keywords

strongly regular graphgraph isomorphismHafnianGaussian boson samplingquantum GI algorithm

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Determinants, permanents, traces, other special matrix functions (15A15)

Cites Work

• Multivariate distributions and the moment problem
• Simulation of topological field theories by quantum computers
• Title not available (Why is that?)
• A modular functor which is universal for quantum computation
• The Jones polynomial: quantum algorithms and applications in quantum complexity theory
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• The computational complexity of linear optics
• A classical approach to the graph isomorphism problem using quantum walks
• A graph isomorphism algorithm using signatures computed via quantum walk search model
• On the exact evaluation of certain instances of the Potts partition function by quantum computers
• Coined quantum walks lift the cospectrality of graphs and trees
• Drum Shapes and Isospectral Graphs
• Combinatorics and complexity of partition functions
• Graph isomorphism in quasipolynomial time (extended abstract)
• QUBO formulations for the graph isomorphism problem and related problems
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Phase-modified CTQW unable to distinguish strongly regular graphs efficiently
• On quantum field theory — I: explicit solution of Dyson’s equation in electrodynamics without use of feynman graphs

Cited In (5)

• Applications of the Lambert-Tsallis \(W_q\) function in quantum photonic Gaussian boson sampling
• Limitations of quantum coset states for graph isomorphism
• Nonnegativity for hafnians of certain matrices
• Entanglement entropy in the ground state of supersymmetric fermion lattice models
• Classical benchmarking of Gaussian boson sampling on the Titan supercomputer

This page was built for publication: Graph isomorphism and Gaussian boson sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q825567)