Graph isomorphism and Gaussian boson sampling
Open accessThe DOI matches its Crossref record; 13 of the 13 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904
Quantum Algorithm for Linear Systems of Equations
Harrow, A. W., Hassidim, A., & Lloyd, S. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.150502 · Cited by 3,325 · cited 1×
“Quantum algorithms with a superpolynomial runtime advantage have also been proposed for linear systems [5, 6], semidefinite programming [7, 8], knot invariants [9–11], and partition functions [12–14], among many others.”
BackgroundQuantum computational advantage using photons
Zhong, H.-S., Wang, H., Deng, Y.-H., Chen, M.-C., Peng, L.-C., Luo, Y.-H., Qin, J., Wu, D., Ding, X., Hu, Y., et al. (2020) · Science · doi:10.1126/science.abe8770 · Cited by 2,405
The computational complexity of linear optics
Aaronson, S., & Arkhipov, A. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993682 · Cited by 874
Childs, A. M., Kothari, R., & Somma, R. D. (2017) · SIAM Journal on Computing · doi:10.1137/16m1087072 · Cited by 646 · cited 1×
“Quantum algorithms with a superpolynomial runtime advantage have also been proposed for linear systems [5, 6], semidefinite programming [7, 8], knot invariants [9–11], and partition functions [12–14], among many others.”
BackgroundA Modular Functor Which is Universal¶for Quantum Computation
Freedman, M. H., Larsen, M., & Wang, Z. (2002) · Communications in Mathematical Physics · doi:10.1007/s002200200645 · Cited by 573
Hamilton, C. S., Kruse, R., Sansoni, L., Barkhofen, S., Silberhorn, C., & Jex, I. (2017) · Physical Review Letters · doi:10.1103/physrevlett.119.170501 · Cited by 503 · cited 5×
“Given a detection event n , its measurement probability was shown in [27] to be where × ··· × ∈ which we view as a column vector (even though β is a complex conjugate of a complex β (entrywise), we consider β i as a new variable).”
BackgroundMethodInfluentialDetailed study of Gaussian boson sampling
Kruse, R., Hamilton, C. S., Sansoni, L., Barkhofen, S., Silberhorn, C., & Jex, I. (2019) · Physical Review A · doi:10.1103/physreva.100.032326 · Cited by 180 · cited 1×
“In this work, we present an approach to graph isomorphism which uses a near-term quantum computational device, namely a photonics-based Gaussian boson sampling apparatus [27, 28].”
MethodTwo-particle quantum walks applied to the graph isomorphism problem
Gamble, J. K., Friesen, M., Zhou, D., Joynt, R., & Coppersmith, S. N. (2010) · Physical Review A · doi:10.1103/physreva.81.052313 · Cited by 145 · cited 2×
“…approach to investigate the effectiveness of graph isomorphism proposals; if a particular certificate will always fail to distinguish two non-isomorphic SRGs, this can be shown to be because all elements of a certificate, as well as their multiplicities, are functions of SRG family parameters [26].”
Background
Cited by
Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
Zhong, H.-S., Deng, Y.-H., Qin, J., Wang, H., Chen, M.-C., Peng, L.-C., Luo, Y.-H., Wu, D., Gong, S.-Q., Su, H., et al. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.180502 · Cited by 434
Photonic implementation of boson sampling: a review
Brod, D. J., Galvão, E. F., Crespi, A., Osellame, R., Spagnolo, N., & Sciarrino, F. (2019) · Advanced Photonics · doi:10.1117/1.ap.1.3.034001 · Cited by 159
Implementing graph-theoretic quantum algorithms on a silicon photonic quantum walk processor
Qiang, X., Wang, Y., Xue, S., Ge, R., Chen, L., Liu, Y., Huang, A., Fu, X., Xu, P., Yi, T., et al. (2021) · Science Advances · doi:10.1126/sciadv.abb8375 · Cited by 96
Experimental Gaussian Boson sampling
Zhong, H.-S., Peng, L.-C., Li, Y., Hu, Y., Li, W., Qin, J., Wu, D., Zhang, W., Li, H., Zhang, L., et al. (2019) · Science Bulletin · doi:10.1016/j.scib.2019.04.007 · Cited by 73
Error mitigation on a near-term quantum photonic device
Su, D., Israel, R., Sharma, K., Qi, H., Dhand, I., & Brádler, K. (2021) · Quantum · doi:10.22331/q-2021-05-04-452 · Cited by 19
Self-citation
Metadata
- Authors
- Brádler, K., Friedland, S., Izaac, J., Killoran, N., & Su, D.
- Venue
- Special Matrices
- Publisher
- Walter de Gruyter GmbH
- Published
- 2021-01-01
- Volume
- 9
- Issue
- 1
- Pages
- 166-196
- ISSN
- 2300-7451 (ISSN-L)
- OpenAlex
- W2898444729
- Cited by
- 47
- References
- 13
- FWCI
- 2.38
- Type
- journal article
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Graph isomorphism and Gaussian boson sampling. https://app.cochat.ai/papers/10.1515/spma-2020-0132
- The paper
- Brádler, K., Friedland, S., Izaac, J., Killoran, N., & Su, D. (2021). Graph isomorphism and Gaussian boson sampling. Special Matrices. https://doi.org/10.1515/spma-2020-0132
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.