Graph isomorphism and Gaussian boson sampling
arXiv:1810.10644 · doi:10.1515/spma-2020-0132
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.
arXiv commentClose to the published version
References in corpus (22)
- Quantum algorithm for solving linear systems of equations
- Quantum computational advantage using photons
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Gaussian Boson Sampling
- Graph Isomorphism in Quasipolynomial Time
- Simulation of topological field theories by quantum computers
- A detailed study of Gaussian Boson Sampling
- Two-particle quantum walks applied to the graph isomorphism problem
- Classical approach to the graph isomorphism problem using quantum walks
- A modular functor which is universal for quantum computation
- Gaussian Boson Sampling for perfect matchings of arbitrary graphs
- Trading inverses for an irrep in the Solovay-Kitaev theorem
- Permanents in linear optical networks
- Experimental quantum annealing: case study involving the graph isomorphism problem
- Graph isomorphism and adiabatic quantum computing
- Non-interacting multi-particle quantum random walks applied to the graph isomorphism problem for strongly regular graphs
- Quantum algorithms for spin models and simulable gate sets for quantum computation
- On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
- Graph isomorphisms in quasi-polynomial time
- Comparing algorithms for graph isomorphism using discrete- and continuous-time quantum random walks
- On quantum invariants and the graph isomorphism problem
- A duality at the heart of Gaussian boson sampling
Cited by in corpus (25)
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- Quantum Indistinguishability by Path Identity: The awakening of a sleeping beauty
- A quantum hardware-induced graph kernel based on Gaussian Boson Sampling
- Experimental Gaussian Boson Sampling
- Quantum Experiments and Graphs II: Quantum Interference, Computation and State Generation
- Scalable and Programmable Phononic Network with Trapped Ions
- Quantum Machine Learning for Finance
- Training Gaussian Boson Sampling Distributions
- Quantum Experiments and Hypergraphs: Multi-Photon Sources for Quantum Interference, Quantum Computation and Quantum Entanglement
- Non-linear Boson Sampling
- Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design
- Error mitigation on a near-term quantum photonic device
- Graph Picture of Linear Quantum Networks and Entanglement
- Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
- Certification of Gaussian Boson Sampling via graph theory
- Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimization
- A Quadratic Speedup in the Optimization of Noisy Quantum Optical Circuits
- Linear multiport photonic interferometers: loss analysis of temporally-encoded architectures
- Holographic Gaussian Boson Sampling with Matrix Product States on 3D cQED Processors
- Sample efficient graph classification using binary Gaussian boson sampling
- Validation of a noisy Gaussian boson sampler via graph theory
- A duality at the heart of Gaussian boson sampling
- Realistic photon-number resolution in Gaussian boson sampling
- Optical Quantum Computing
- Towards graph classification with Gaussian Boson Sampling by embedding graphs on the X8 photonic chip