[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 (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 |
[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 (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 |