[1] Shor, P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484–1509 (1997). doi: 10.1137/S0097539795293172
[2] Grover, L. K. A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. (Association for Computing Machinery, 1996).
[3] Aaronson, S. & Arkhipov, A. The computational complexity of linear optics. Proceedings of the 43rd Annual ACM Symposium on Theory of Computing. (Association for Computing Machinery, 2011).
[4] Harrow, A. W. & Montanaro, A. Quantum computational supremacy. Nature 549, 203–209 (2017). doi: 10.1038/nature23458
[5] Preskill, J. Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018). doi: 10.22331/q-2018-08-06-79
[6] Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019). doi: 10.1038/s41586-019-1666-5
[7] Zhong, H. S. et al. Quantum computational advantage using photons. Science 370, 1460–1463 (2020).
[8] O'Brien, J. L., Furusawa, A. & Vučković, J. Photonic quantum technologies. Nat. Photon. 3, 687–695 (2009). doi: 10.1038/nphoton.2009.229
[9] Aspuru-Guzik, A. & Walther, P. Photonic quantum simulators. Nat. Phys. 8, 285–291 (2012). doi: 10.1038/nphys2253
[10] Flamini, F., Spagnolo, N. & Sciarrino, F. Photonic quantum information processing: a review. Rep. Prog. Phys. 82, 016001 (2019). doi: 10.1088/1361-6633/aad5b2
[11] Broome, M. A. et al. Photonic boson sampling in a tunable circuit. Science 339, 794–798 (2013). doi: 10.1126/science.1231440
[12] Spring, J. B. et al. Boson sampling on a photonic chip. Science 339, 798–801 (2013). doi: 10.1126/science.1231692
[13] Tillmann, M. et al. Experimental boson sampling. Nat. Photon. 7, 540–544 (2013). doi: 10.1038/nphoton.2013.102
[14] Crespi, A. et al. Integrated multimode interferometers with arbitrary designs for photonic boson sampling. Nat. Photon. 7, 545–549 (2013). doi: 10.1038/nphoton.2013.112
[15] Schreiber, A. et al. A 2D quantum walk simulation of two-particle dynamics. Science 336, 55–58 (2012). doi: 10.1126/science.1218448
[16] Tang, H. et al. Experimental quantum fast hitting on hexagonal graphs. Nat. Photon. 12, 754–758 (2018). doi: 10.1038/s41566-018-0282-5
[17] Peruzzo, A. et al. A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5, 4213 (2014). doi: 10.1038/ncomms5213
[18] Santagati, R. et al. Witnessing eigenstates for quantum simulation of hamiltonian spectra. Sci. Adv. 4, eaap9646 (2018). doi: 10.1126/sciadv.aap9646
[19] Kagalwala, K. H. et al. Single-photon three-qubit quantum logic using spatial light modulators. Nat. Commun. 8, 739 (2017). doi: 10.1038/s41467-017-00580-x
[20] Wang, X. L. et al. 18-qubit entanglement with six photons' three degrees of freedom. Phys. Rev. Lett. 120, 260502 (2018). doi: 10.1103/PhysRevLett.120.260502
[21] Reck, M. et al. Experimental realization of any discrete unitary operator. Phys. Rev. Lett. 73, 58–61 (1994). doi: 10.1103/PhysRevLett.73.58
[22] Carolan, J. et al. Universal linear optics. Science 349, 711–716 (2015). doi: 10.1126/science.aab3642
[23] Clements, W. R. et al. Optimal design for universal multiport interferometers. Optica 3, 1460–1465 (2016). doi: 10.1364/OPTICA.3.001460
[24] Saygin, M. Y. et al. Robust architecture for programmable universal unitaries. Phys. Rev. Lett. 124, 010501 (2020). doi: 10.1103/PhysRevLett.124.010501
[25] Cook, S. A. The complexity of theorem-proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing. (Association for Computing Machinery, 1971).
[26] Malik, S. & Zhang, L. T. Boolean satisfiability from theoretical hardness to practical success. Commun. ACM 52, 76–82 (2009). doi: 10.1145/1536616.1536637
[27] Impagliazzo, R. & Paturi, R. On the complexity of k-SAT. J. Comput. Syst. Sci. 62, 367–375 (2001). doi: 10.1006/jcss.2000.1727
[28] Aaronson, S. et al. The power of unentanglement. Theory Comput. 5, 1–42 (2009). doi: 10.4086/toc.2009.v005a001
[29] Blier, H. & Tapp, A. All languages in NP have very short quantum proofs. Proceedings of 2009 Third International Conference on Quantum, Nano and Micro Technologies. (IEEE, 2009).
[30] Chen, J. & Drucker, A. Short multi-prover quantum proofs for SAT without entangled measurements. Preprint at https://arxiv.org/abs/1011.0716">https://arxiv.org/abs/1011.0716 (2010).
[31] Chiesa, A. & Forbes, M. A. Improved soundness for QMA with multiple provers. Chic. J. Theor. Computer Sci. 19, 1–23 (2013). doi: 10.4086/cjtcs.2013.001
[32] Harrow, A. W. & Montanaro, A. Testing product states, quantum Merlin-Arthur games and tensor optimization. J. ACM 60, 3 (2013). doi: 10.1145/2432622.2432625
[33] Brandão, F. G. S. L. & Harrow, A. W. Quantum de finetti theorems under local measurements with applications. Commun. Math. Phys. 353, 469–506 (2017). doi: 10.1007/s00220-017-2880-3
[34] Arrazola, J. M., Diamanti, E. & Kerenidis, I. Quantum superiority for verifying NP-complete problems with linear optics. npj Quantum Inf. 4, 56 (2018). doi: 10.1038/s41534-018-0103-1
[35] Centrone, F. et al. Experimental demonstration of quantum advantage for NP verification with limited information. Nat. Commun. 12, 850 (2021). doi: 10.1038/s41467-021-21119-1
[36] Kitaev, A. Y., Shen, A. H. & Vyalyi, M. N. Classical and Quantum Computation. (American Mathematical Society, 2002).
[37] Watrous, J. Succinct quantum proofs for properties of finite groups. Proceedings 41st Annual Symposium on Foundations of Computer Science. (IEEE, 2000).
[38] Kobayashi, H., Matsumoto, K. & Yamakami, T. Quantum merlin-arthur proof systems: are multiple merlins more helpful to arthur? Proceedings of the 14th International Symposium on Algorithms and Computation. (Springer, 2003).
[39] Garcia-Escartin, J. C. & Chamorro-Posada, P. Swap test and Hong-Ou-Mandel effect are equivalent. Phys. Rev. A 87, 052330 (2013). doi: 10.1103/PhysRevA.87.052330
[40] Hong, C. K., Ou, Z. Y. & Mandel, L. Measurement of subpicosecond time intervals between two photons by interference. Phys. Rev. Lett. 59, 2044–2046 (1987). doi: 10.1103/PhysRevLett.59.2044
[41] Maslov, D. et al. Quantum advantage for computations with limited space. Nat. Phys. (2021). https://doi.org/10.1038/s41567-021-01271-7">https://doi.org/10.1038/s41567-021-01271-7
[42] Wang, J. W. et al. Integrated photonic quantum technologies. Nat. Photon. 14, 273–284 (2020). doi: 10.1038/s41566-019-0532-1
[43] Jain, R. et al. QIP = PSPACE. J. ACM 58, 30 (2011).
[44] Ji, Z. F. et al. MIP*=RE. Preprint at https://arxiv.org/abs/2001.04383">https://arxiv.org/abs/2001.04383 (2020).
[45] Barz, S. et al. Demonstration of blind quantum computing. Science 335, 303–308 (2012). doi: 10.1126/science.1214707
[46] Reichardt, B. W., Unger, F. & Vazirani, U. Classical command of quantum systems. Nature 496, 456–460 (2013). doi: 10.1038/nature12035
[47] Barz, S. et al. Experimental verification of quantum computation. Nat. Phys. 9, 727–731 (2013). doi: 10.1038/nphys2763
[48] Fisher, K. A. G. et al. Quantum computing on encrypted data. Nat. Commun. 5, 3074 (2014). doi: 10.1038/ncomms4074
[49] Liu, Y. K., Christandl, M. & Verstraete, F. Quantum computational complexity of the N-representability problem: QMA complete. Phys. Rev. Lett. 98, 110503 (2007). doi: 10.1103/PhysRevLett.98.110503