Graph isomorphism and Gaussian boson sampling
From MaRDI portal
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)
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.
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
Cites work
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- A classical approach to the graph isomorphism problem using quantum walks
- A graph isomorphism algorithm using signatures computed via quantum walk search model
- A modular functor which is universal for quantum computation
- Coined quantum walks lift the cospectrality of graphs and trees
- Combinatorics and complexity of partition functions
- Drum Shapes and Isospectral Graphs
- Graph isomorphism in quasipolynomial time (extended abstract)
- Multivariate distributions and the moment problem
- On quantum field theory — I: explicit solution of Dyson’s equation in electrodynamics without use of feynman graphs
- On the exact evaluation of certain instances of the Potts partition function by quantum computers
- Phase-modified CTQW unable to distinguish strongly regular graphs efficiently
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- QUBO formulations for the graph isomorphism problem and related problems
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Simulation of topological field theories by quantum computers
- The Jones polynomial: quantum algorithms and applications in quantum complexity theory
- The computational complexity of linear optics
Cited in
(5)- Entanglement entropy in the ground state of supersymmetric fermion lattice models
- Applications of the Lambert-Tsallis \(W_q\) function in quantum photonic Gaussian boson sampling
- Classical benchmarking of Gaussian boson sampling on the Titan supercomputer
- Nonnegativity for hafnians of certain matrices
- Vibronic spectra of molecules – an experiment with a quantum computer simulator
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)
