[1] P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26, 1484-1509(1997).
[2] F. Flamini, N. Spagnolo, F. Sciarrino. Photonic quantum information processing: a review. Rep. Prog. Phys., 82, 016001(2019).
[3] T. Schetz. Trapping ions and atoms optically. J. Phys. B: At. Mol. Opt. Phys., 50, 102001(2017).
[4] T. Xin et al. Nuclear magnetic resonance for quantum computing: techniques and recent achievements. Chin. Phys. B, 27, 020308(2018).
[5] P. Michler. Quantum Dots for Quantum Information Technologies, Nano-Optics and Nanophotonics(2017).
[6] G. Wendin. Quantum information processing with superconducting circuits: a review. Rep. Prog. Phys., 80, 106001(2017).
[7] X. Gu et al. Microwave photonics with superconducting quantum circuits. Phys. Rep., 718-719, 1-102(2017).
[8] A. W. Harrow, A. Montanaro. Quantum computational supremacy. Nature, 549, 203-209(2017).
[9] S. Aaronson, A. Press, A. Arkhipov. The computational complexity of linear optics, 333-342(2011).
[10] L. Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8, 189-201(1979).
[11] A. P. Lund et al. Boson sampling from a Gaussian state. Phys. Rev. Lett., 113, 100502(2014).
[12] D. J. Brod. Complexity of simulating constant-depth boson sampling. Phys. Rev. A, 91, 042316(2015).
[13] S. Barkhofen et al. Driven boson sampling. Phys. Rev. Lett., 118, 020502(2017).
[14] C. S. Hamilton et al. Gaussian boson sampling. Phys. Rev. Lett., 119, 170501(2017).
[15] S. Laibacher, V. Tamma. From the physics to the computational complexity of multiboson correlation interference. Phys. Rev. Lett., 115, 243605(2015).
[16] K. P. Seshadreesan et al. Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states: the quantum-classical divide and computational-complexity transitions in linear optics. Phys. Rev. A, 91, 022334(2015).
[17] J. P. Olson et al. Sampling arbitrary photon-added or photon-subtracted squeezed states is in the same complexity class as boson sampling. Phys. Rev. A, 91, 022317(2015).
[18] A. Neville et al. Classical boson sampling algorithms with superior performance to near-term experiments. Nat. Phys., 13, 1153-1157(2017).
[19] S. Aaronson, A. Arkhipov. Boson sampling is far from uniform. Quantum Inf. Comput., 14, 1383-1423(2014).
[20] E. R. Caianiello. On quantum field theory—I: explicit solution of Dyson’s equation in electrodynamics without use of Feynman graphs. Il Nuovo Cimento, 10, 1634-1652(1953).
[21] L. Troyansky, N. Tishby. Permanent uncertainty: on the quantum evaluation of the determinant and the permanent of a matrix, 1-5(1996).
[22] S. Scheel. Permanents in linear optical networks. Acta Phys. Slovaca, 58, 675(2008).
[23] M. Reck et al. Experimental realization of any discrete unitary operator. Phys. Rev. Lett., 73, 58-61(1994).
[24] W. R. Clements et al. An optimal design for universal multiport interferometers. Optica, 3, 1460-1465(2016).
[25] A. Arkhipov, G. Kuperberg. The bosonic birthday paradox. Geometry and Topology Monographs, 18, 1-7(2012).
[26] L. Gurvits. On the complexity of mixed discriminants and related problems. Lect. Notes Comput. Sci., 3618, 447-458(2005).
[27] L. Stockmeyer. On approximation algorithms for #P. SIAM J. Comput., 14, 849-861(1985).
[28] S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20, 865-877(1991).
[29] P. S. Efraimidis. Weighted random sampling over data streams. Lect. Notes Comput. Sci., 9295, 183-195(2015).
[30] P. Clifford, R. Clifford. The classical complexity of boson sampling, 146-155(2018).
[31] J. S. Liu. Monte Carlo Strategies in Scientific Computing(2008).
[32] J. P. Green et al. Bayesian computation: a summary of the current state, and samples backwards and forwards. Stat. Comput., 25, 835-862(2015).
[33] J. Wu et al. A benchmark test of boson sampling on Tianhe-2 supercomputer. Nat. Sci. Rev., 5, 715-720(2018).
[34] S. Rahimi-Keshari, T. C. Ralph, C. M. Caves. Sufficient conditions for efficient classical simulation of quantum optics. Phys. Rev. X, 6, 021039(2016).
[35] S. Aaronson, D. J. Brod. Boson sampling with lost photons. Phys. Rev. A, 93, 012335(2015).
[36] M. Oszmaniec, D. J. Brod. Classical simulation of photonic linear optics with lost particles. New J. Phys., 20, 092002(2018).
[37] R. Garcia-Patrón, J. J. Renema, V. Shchesnovich. Simulating boson sampling in lossy architectures(2017).
[38] J. J. Renema, V. Shchesnovich, R. Garcia-Patrón. Classical simulability of noisy boson sampling(2018).
[39] M. Jerrum, A. Sinclair, E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM, 51, 671-697(2004).
[40] M. C. Tichy. Sampling of partially distinguishable bosons and the relation to the multidimensional permanent. Phys. Rev. A, 91, 022316(2015).
[41] P. P. Rohde. Boson sampling with photons of arbitrary spectral structure. Phys. Rev. A, 91, 012307(2015).
[42] V. S. Shchesnovich. Partial indistinguishability theory for multiphoton experiments in multiport devices. Phys. Rev. A, 91, 013844(2015).
[43] V. Tamma, S. Laibacher. Multiboson correlation interferometry with arbitrary single-photon pure states. Phys. Rev. Lett., 114, 243601(2015).
[44] J. J. Renema et al. Efficient classical algorithm for boson sampling with partially distinguishable photons. Phys. Rev. Lett., 120, 220502(2018).
[45] V. S. Shchesnovich. Sufficient condition for the mode mismatch of single photons for scalability of the boson-sampling computer. Phys. Rev. A, 89, 022333(2014).
[46] A. Arkhipov. Boson sampling is robust against small errors in the network matrix. Phys. Rev. A, 92, 062326(2015).
[47] A. Leverrier, R. Garcia-Patron. Analysis of circuit imperfections in boson sampling. Quantum Inf. Comput., 15, 489-512(2015).
[48] G. Kalai, G. Kindler. Gaussian noise sensitivity and boson sampling(2014).
[49] X. Gao, L. Duan. Efficient classical simulation of noisy quantum computation(2018).
[50] K. Kruse et al. A detailed study of Gaussian boson sampling(2018).
[51] B. Gupt et al. Classical benchmarking of Gaussian boson sampling on the Titan supercomputer(2018).
[52] A. Björklund. Counting perfect matchings as fast as Ryser, 914-921(2012).
[53] L. Chakhmakhchyan, N. J. Cerf. Boson sampling with Gaussian measurements. Phys. Rev. A, 96, 032326(2017).
[54] A. P. Lund, S. Rahimi-Keshari, T. C. Ralph. Exact boson sampling using Gaussian continuous-variable measurements. Phys. Rev. A, 96, 022301(2017).
[55] N. Quesada, J. M. Arrazola, N. Killoran. Gaussian boson sampling using threshold detectors. Phys. Rev. A, 98, 062322(2018).
[56] J. M. Arrazola, T. R. Bromley. Using Gaussian boson sampling to find dense subgraphs. Phys. Rev. Lett., 121, 030503(2018).
[57] K. Bradler et al. Gaussian boson sampling for perfect matchings of arbitrary graphs. Phys. Rev. A, 98, 032310(2018).
[58] J. M. Arrazola, R. R. Bromley, P. Rebentrost. Quantum approximate optimization with Gaussian boson sampling. Phys. Rev. A, 98, 012322(2018).
[59] J. Huh et al. Boson sampling for molecular vibronic spectra. Nat. Photonics, 9, 615-620(2015).
[60] J. Huh, M.-H. Yung. Vibronic boson sampling: generalized Gaussian boson sampling for molecular vibronic spectra at finite temperature. Sci. Rep., 7, 7462(2017).
[61] B. Peropadre, J. Huh, C. Sabin. Dynamical Casimir effect for Gaussian boson sampling. Sci. Rep., 8, 3751(2018).
[62] S. Laibacher, V. Tamma. Toward quantum computational supremacy of boson sampling with random overlap in the photonic spectra(2018).
[63] M. A. Broome et al. Photonic boson sampling in a tunable circuit. Science, 339, 794-798(2013).
[64] J. B. Spring et al. Boson sampling on a photonic chip. Science, 339, 798-801(2013).
[65] M. Tillmann et al. Experimental boson sampling. Nat. Photonics, 7, 540-544(2013).
[66] A. Crespi et al. Integrated multimode interferometers with arbitrary designs for photonic boson sampling. Nat. Photonics, 7, 545-549(2013).
[67] J. Carolan et al. On the experimental verification of quantum complexity in linear optics. Nat. Photonics, 8, 621-626(2014).
[68] M. Bentivegna et al. Experimental scattershot boson sampling. Sci. Adv., 1, e1400255(2015).
[69] J. Carolan et al. Universal linear optics. Science, 349, 711-716(2015).
[70] J. C. Loredo et al. Boson sampling with single-photon Fock states from a bright solid-state source. Phys. Rev. Lett., 118, 130503(2017).
[71] Y. He et al. Time-bin-encoded boson sampling with a single-photon device. Phys. Rev. Lett., 118, 190501(2017).
[72] H. Wang et al. High-efficiency multiphoton boson sampling. Nat. Photonics, 11, 361-365(2017).
[73] H. Wang et al. Toward scalable boson sampling with photon loss. Phys. Rev. Lett., 120, 230502(2018).
[74] H.-S. Zhong et al. 12-photon entanglement and scalable scattershot boson sampling with optimal entangled-photon pairs from parametric down-conversion. Phys. Rev. Lett., 121, 250505(2018).
[75] S. Paesani et al. Generation and sampling of quantum states of light in a silicon chip(2018).
[76] N. Spagnolo et al. Experimental validation of photonic boson sampling. Nat. Photonics, 8, 615-620(2014).
[77] N. J. Russell et al. Direct dialling of Haar random unitary matrices. New J. Phys., 19, 033007(2017).
[78] R. Osellame, G. Cerullo, R. Ramponi. Femtosecond Laser Micromachining: Photonic and Microfluidic Devices in Transparent Materials, 123(2012).
[79] S. Nolte et al. Femtosecond waveguide writing: a new avenue to three-dimensional integrated optics. Appl. Phys. A, 77, 109-111(2003).
[80] J. B. Spring et al. Chip-based array of near-identical, pure, heralded single-photon sources. Optica, 4, 90-96(2017).
[81] L. Sansoni et al. A two-channel, spectrally degenerate polarization entangled source on chip. npj Quantum Inf., 3, 5(2017).
[82] S. Atzeni et al. Integrated sources of entangled photons at telecom wavelength in femtosecond-laser-written circuits. Optica, 5, 311-314(2018).
[83] J. Wang et al. Multidimensional quantum entanglement with large-scale integrated optics. Science, 360, 285-291(2018).
[84] F. Kaneda, P. Kwiat. High-efficiency single-photon generation via large-scale active time multiplexing(2018).
[85] F. Lenzini et al. Active demultiplexing of single photons from a solid-state source. Laser Photonics Rev., 11, 1600297(2017).
[86] K. R. Motes et al. Scalable boson sampling with time-bin encoding using a loop-based architecture. Phys. Rev. Lett., 113, 120501(2014).
[87] X.-J. Wang et al. Experimental time-resolved interference with multiple photons of different colors. Phys. Rev. Lett., 121, 080501(2018).
[88] S. Laibacher, V. Tamma. Symmetries and entanglement features of inner-mode-resolved correlations of interfering nonidentical photons. Phys. Rev. A, 98, 053829(2018).
[89] C. Gogolin et al. Boson-sampling in the light of sample complexity(2013).
[90] M. Bentivegna et al. Bayesian approach to boson sampling validation. Int. J. Quantum Inf., 12, 1560028(2014).
[91] M. C. Tichy et al. Stringent and efficient assessment of boson-sampling devices. Phys. Rev. Lett., 113, 020502(2014).
[92] M. C. Tichy et al. Zero-transmission law for multiport beam splitters. Phys. Rev. Lett., 104, 220405(2010).
[93] A. Crespi et al. Suppression law of quantum states in a 3D photonic fast Fourier transform chip. Nat. Commun., 7, 10469(2016).
[94] A. Crespi. Suppression laws for multiparticle interference in Sylvester interferometers. Phys. Rev. A, 91, 013811(2015).
[95] C. Dittel, R. Keil, G. Weihs. Many-body quantum interference on hypercubes. Quantum Sci. Technol., 2, 015003(2017).
[96] N. Viggianiello et al. Experimental generalized quantum suppression law in Sylvester interferometers. New J. Phys., 20, 033017(2018).
[97] C. Dittel et al. Totally destructive many-particle interference. Phys. Rev. Lett., 120, 240404(2018).
[98] C. Dittel et al. Totally destructive interference for permutation-symmetric many-particle states. Phys. Rev. A, 97, 062116(2018).
[99] N. Viggianiello et al. Optimal photonic indistinguishability tests in multimode networks. Sci. Bull., 63, 1470-1478(2018).
[100] D. J. Brod et al. Witnessing genuine multiphoton indistinguishability. Phys. Rev. Lett., 122, 063602(2019).
[101] I. Agresti et al. Pattern recognition techniques for boson sampling validation. Phys. Rev. X, 9, 011013(2019).
[102] S.-T. Wang, L.-M. Duan. Certification of boson sampling devices with coarse-grained measurements(2016).
[103] M. Walschaers et al. Statistical benchmark for boson sampling. New J. Phys., 18, 032001(2016).
[104] M. Bentivegna, N. Spagnolo, F. Sciarrino. Is my boson sampler working?. New J. Phys., 18, 041001(2016).
[105] T. Giordani et al. Experimental statistical signature of many-body quantum interference. Nat. Photonics, 12, 173-178(2018).
[106] L. Aolita et al. Reliable quantum certification of photonic state preparations. Nat. Commun., 6, 8498(2015).
[107] K. Liu et al. A certification scheme for the boson sampler. J. Opt. Soc. Am. B, 33, 1835-1841(2016).
[108] V. S. Shchesnovich. Universality of generalized bunching and efficient assessment of boson sampling. Phys. Rev. Lett., 116, 123601(2016).
[109] F. Flamini et al. Benchmarking integrated linear-optical architectures for quantum information processing. Sci. Rep., 7, 15133(2017).
[110] F. G. S. L. Brandão, A. W. Harrow, M. Horodecki. Local random quantum circuits are approximate polynomial-designs. Commun. Math. Phys., 346, 397-434(2016).
[111] C. Moore, S. Mertens. The Nature of Computation(2011).
[112] K. Bradler et al. Graph isomorphism and Gaussian boson sampling(2018).