Experimental verification of group non-membership in optical circuits

Kai Sun; Zi-Jian Zhang; Fei Meng; Bin Cheng; Zhu Cao; Jin-Shi Xu; Man-Hong Yung; Chuan-Feng Li; Guang-Can Guo

doi:10.1364/PRJ.427897

[1] P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. 35th Annual Symposium on Foundations of Computer Science, 124-134(1994).

[2] A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, D. A. Spielman. Exponential algorithmic speedup by a quantum walk. 35th Annual ACM Symposium on Theory of Computing, 59-68(2003).

[3] M. A. Nielsen, I. Chuang. Quantum Computation and Quantum Information(2002).

[4] S. Goldwasser, S. Micali, C. Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18, 186-208(1989).

[5] J. Watrous. PSPACE has constant-round quantum interactive proof systems. Theor. Comput. Sci., 292, 575-588(2003).

[6] F. Centrone, N. Kumar, E. Diamanti, I. Kerenidis. Experimental demonstration of quantum advantage for NP verification with limited information. Nat. Commun., 12, 850(2021).

[7] A. Broadbent, J. Fitzsimons, E. Kashefi. Universal blind quantum computation. 50th Annual IEEE Symposium on Foundations of Computer Science, 517-526(2009).

[8] J. F. Fitzsimons, E. Kashefi. Unconditionally verifiable blind quantum computation. Phys. Rev. A, 96, 012303(2017).

[9] S. Barz, J. F. Fitzsimons, E. Kashefi, P. Walther. Experimental verification of quantum computation. Nat. Phys., 9, 727-731(2013).

[10] A. Broadbent, Z. Ji, F. Song, J. Watrous. Zero-knowledge proof systems for QMA. IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 31-40(2016).

[11] A. B. Grilo, W. Slofstra, H. Yuen. Perfect zero knowledge for quantum multiprover interactive proofs. IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 611-635(2019).

[12] Z. Ji, A. Natarajan, T. Vidick, J. Wright, H. Yuen. MIP*= RE(2020).

[13] A. Natarajan, J. Wright. NEEXP is contained in MIP. IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 510-518(2019).

[14] M. Sipser. Introduction to the theory of computation. ACM SIGACT News, 27, 27-29(1996).

[15] A. Y. Kitaev, A. Shen, M. N. Vyalyi. Classical and Quantum Computation(2002).

[16] J. Watrous. Quantum computational complexity(2008).

[17] D. Aharonov, T. Naveh. Quantum NP - a survey(2002).

[18] H. Kobayashi, K. Matsumoto, T. Yamakami. Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur?. Algorithms and Computation, 189-198(2003).

[19] L. Babai. Trading group theory for randomness. 7th Annual ACM Symposium on Theory of Computing, 421-429(1985).

[20] L. Babai. Bounded round interactive proofs in finite groups. SIAM J. Discrete Math., 5, 88-111(1992).

[21] J. Watrous. Succinct quantum proofs for properties of finite groups. 41st Annual Symposium on Foundations of Computer Science, 537-546(2000).

[22] J. Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2, 79(2018).

[23] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, J. M. Martinis. Quantum supremacy using a programmable superconducting processor. Nature, 574, 505-510(2019).

[24] L. Babai. Local expansion of vertex-transitive graphs and random generation in finite groups. 23rd Annual ACM Symposium on Theory of Computing, 164-174(1991).

[25] L. Babai, E. Szemerédi. On the complexity of matrix group problems I. 25th Annual Symposium on Foundations of Computer Science, 229-240(1984).

[26] P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, P. H. Eberhard. Ultrabright source of polarization-entangled photons. Phys. Rev. A, 60, R773-R776(1999).

[27] K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, G.-C. Guo. Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination. Npj Quantum Inf., 4, 12(2018).