-
Quantum computing has been proven to be powerful, however, there are still great challenges for building real quantum computers due to the requirements of both fault-tolerance and universality. People still lack a systematic way to design fast quantum algorithms and identify the key quantum resources. In this work, we develop a resource-theoretic approach to characterize universal quantum computing models and the universal resources for quantum computing.
Our theory combines the framework of universal quantum computing model (UQCM) and the quantum resource theory (QRT). The former has played major roles in quantum computing, while the later was developed mainly for quantum information theory. Putting them together proves to be 'win-win': on one hand, using QRT can provide a resource-theoretic characterization of a UQCM, the relation among models and inspire new ones, and on the other hand, using UQCM offers a framework to apply resources, study relation among resources and classify them.
In quantum theory, we mainly study states, evolution, observable, and probability from measurements, and this motivates the introduction of different families of UQCMs. A family also includes generations depending on a hierarchical structure of resource theories. We introduce a table of UQCMs by first classifying two categories of models: one referring to the format of information, and one referring to the logical evolution of information requiring quantum error-correction codes. Each category contains a few families of models, leading to more than one hundred of them in total. Such a rich spectrum of models include some well-known ones that people use, such as the circuit model, the adiabatic model, but many of them are relatively new and worthy of more study in the future. Among them are the models of quantum von Neumann architectures established recently. This type of architecture or model circumvents the no-go theorems on both the quantum program storage and quantum control unit, enabling the construction of more complete quantum computer systems and high-level programming.
Correspondingly, each model is captured by a unique quantum resource. For instance, in the state family, the universal resource for the circuit model is coherence, for the local quantum Turing machine is bipartite entanglement, and for the cluster-state based, also known as measurement-based model is a specific type of entanglement relevant to symmetry-protected topological order. As program-storage is a central feature of the quantum von Neumann architecture, we find the quantum resources for it are quantum memories, which are dynamical resources closely related to entanglement. In other words, our classification of UQCMs also serves as a computational classification of quantum resources. This can be used to resolve the dispute over the computing power of resources, such as interference, entanglement, or contextuality. In all, we believe our theory lays down a solid framework to study computing models, resources, and design algorithms. -
[1] Preskill J 2018 Quantum 2 79
[2] Nielsen M A, Chuang I L 2000 Quantum Computation and Quantum Information (Cambridge U.K.: Cambridge University Press)
[3] Pan J W 2024 Acta Phys. Sin. 73 010301
[4] Bell J S 1966 Rev. Mod. Phys. 38 447
[5] Kraus K 1983 States, Effects, and Operations: Fundamental Notions of Quantum Theory, vol. 190 of Lecture Notes in Physics (Berlin: Springer-Verlag)
[6] Holevo A S 1982 Probabilistic and Statistical Aspect of Quantum Theory (North-Holland, Amsterdam)
[7] Feynman R P 1982 Int. J. Theor. Phys. 21 467
[8] Deutsch D 1985 In Proc. R. Soc. (London), Ser. A, vol. 400 (The Royal Society), pp 97–117
[9] Yao A C C 1993 In Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on (IEEE), pp 352–361
[10] Bernstein E, Vazirani U 1997 SIAM J. Comput. 26 1411
[11] Shor P W 1994 In Proceedings 35th annual symposium on foundations of computer science (IEEE), pp 124–134
[12] Harris D M, Harris S L 2013 Digital design and computer architecture (Elsevier)
[13] Shannon C 1948 The Bell System Technical Journal 27 379
[14] von Neumann J 1993 IEEE Annals of the History of Computing 15 27
[15] Lidar D, Brun T A, editors 2013 Quantum error correction (Cambridge University Press)
[16] Ladd T D, Jelezko F, Laflamme R, Nakamura Y, Monroe C, O’ Brien J L 2010 Nature 464 45
[17] Grover L K 1996 In Proceedings of the twenty-eighth annual ACM Symposium on Theory of Computing
[18] Harrow A W, Hassidim A, Lloyd S 2009 Phys. Rev. Lett.103 150502
[19] Long G L 2011 Int. J. Theor. Phys. 50 1305
[20] Martyn J M, Rossi Z M, Tan A K, Chuang I L 2021 PRX Quantum 2 040203
[21] Watrous J 2018 The Theory of Quantum Information (Cambridge University Press)
[22] Hayashi M 2017 Quantum Information Theory: Mathematical Foundation, 2nd edition (Springer)
[23] Wilde M 2017 Quantum Information Theory (Cambridge University Press)
[24] Chitambar E, Gour G 2019 Rev. Mod. Phys. 91 025001
[25] Wang D S 2023 Commun. Theor. Phys. 75 125101
[26] Albash T, Lidar D A 2018 Rev. Mod. Phys. 90 015002
[27] Nayak C, Simon S H, Stern A, Freedman M, Sarma S D 2008 Rev. Mod. Phys. 80 1083
[28] Childs A M, Gosset D, Webb Z 2013 Science 339 791
[29] Arrighi P 2019 Natural Computing 18 885
[30] Briegel H J, Browne D E, Dür W, Raussendorf R, Van den Nest M 2009 Nat. Phys. 5 19
[31] Barenco A, Bennett C H, Cleve R, DiVincenzo D P, Margolus N, Shor P, Sleator T, Smolin J A, Weinfurter H 1995 Phys. Rev. A 52 3457
[32] DiVincenzo D P 2000. ArXiv:quant-ph/0002077
[33] Nielsen M A, Chuang I L 1997 Phys. Rev. Lett. 79 321
[34] Yang Y, Renner R, Chiribella G 2020 Phys. Rev. Lett. 125 210501
[35] Wang D S 2022 Commun. Theor. Phys. 74 095103
[36] Dawson C M, Nielsen M A 2006 Quantum Inf. Comput. 6 81
[37] Lloyd S 1996 Science 273 1073
[38] Brassard G, Høyer P, Mosca M, Tapp A 2002 Contem. Mathemat. 305 53–74
[39] Knill E, Laflamme R 1997 Phys. Rev. A 55 900
[40] Chiribella G, D’Ariano G M, Perinotti P 2008 Europhys. Lett. 83 30004
[41] Chiribella G, D’Ariano G M, Perinotti P 2008 Phys. Rev.Lett. 101 060401
[42] Chiribella G, D’Ariano G M, Perinotti P 2009 Phys. Rev.A 80 022339
[43] Choi M D 1975 Linear Algebra Appl. 10 285
[44] Bény C, Oreshkov O 2010 Phys. Rev. Lett. 104 120501
[45] Gottesman D 1998 Phys. Rev. A 57 127
[46] Wang D S, Zhu G, Okay C, Laflamme R 2020 Phys. Rev.Res. 2 033116
[47] Wang D S, Wang Y J, Cao N, Zeng B, Laflamme R 2022 New J. Phys. 24 023019
[48] Zhou S, Liu Z W, Jiang L 2021 Quantum 5 521
[49] Yang Y, Mo Y, Renes J M, Chiribella G, Woods M P 2022 Phys. Rev. Res. 4 023107
[50] Kubica A, Demkowicz-Dobrzański R 2021 Phys. Rev. Lett. 126 150503
[51] Viola L, Knill E, Lloyd S 1999 Phys. Rev. Lett. 82 2417
[52] Kitaev A Y 2003 Ann. Phys. 303 2
[53] Ryan W E, Lin S 2009 Channel Codes: Classical and Modern (Cambridge University Press)
[54] Breuckmann N P, Eberhardt J N 2021 PRX Quantum 2 040101
[55] Wang D S, Liu Y D, Wang Y J, Luo S 2024 Phys. Rev. A 110 032413
[56] Coecke B, Fritz T, Spekkens R W 2016 Information and Computation 250 59
[57] Horodecki R, Horodecki P, Horodecki M, Horodecki K 2009 Rev. Mod. Phys. 81 865
[58] Streltsov A, Adesso G, Plenio M B 2017 Rev. Mod. Phys. 89 041003
[59] Wang D S 2021 Quantum Engineering 2 e85
[60] Wang D S 2020 Quant. Infor. Comput. 20 0213
[61] Raussendorf R, Briegel H J 2001 Phys. Rev. Lett. 86 5188
[62] Nielsen M A 2006 Reports on Math. Phys. 57 147
[63] Wang D S, Stephen D T, Raussendorf R 2017 Phys. Rev. A 95 032312
[64] Stephen D T, Wang D S, Prakash A, Wei T C, Raussendorf R 2017 Phys. Rev. Lett. 119 010504
[65] Raussendorf R, Okay C, Wang D S, Stephen D T, Nautrup H P 2019 Phys. Rev. Lett. 122 090501
[66] Molina A, Watrous J 2019 Proc. Royal Soc. A 475 20180767
[67] Paetznick A, Reichardt B W 2013 Phys. Rev. Lett. 111 090505
[68] Tóth G, Apellaniz I 2014 J. Phys. A: Math. Theor. 47 424006
[69] Affleck I, Kennedy T, Lieb E H, Tasaki H 1987 Phys. Rev. Lett. 59 799
[70] Fannes M, Nachtergaele B, Werner R F 1992 Commun. Math. Phys. 144 443
[71] Perez-Garcia D, Verstraete F, Wolf M, Cirac J 2007 Quantum Inf. Comput. 7 401
[72] Sarovar M, Proctor T, Rudinger K, Young K, Nielsen E, Blume-Kohout R 2020 Quantum 4 321
[73] Crépeau C, Gottesman D, Smith A 2002 In STOC ’ 02: Proc. 34rd Annual ACM Symp. Theory of Computing.p 643
[74] Broadbent A, Fitzsimons J, Kashefi E 2009 In Proceedings of the 50th Annual Symposium on Foundations of Computer Science (IEEE Computer Society, Los Alamitos, CA, 2009). pp 517–527
[75] Myers J M 1997 Phys. Rev. Lett. 78 1823
[76] Cirac J I, Pérez-García D, Schuch N, Verstraete F 2021 Rev. Mod. Phys. 93 045003
[77] Wehner S, Elkouss D, Hanson R 2018 Science 362 303
[78] Wang D S 2019 Int. J. Mod. Phys. B 33 1930004
[79] Wang D S 2020 Phys. Rev. A 101 052311
[80] Van den Nest M, Dür W, Vidal G, Briegel H J 2007 Phys. Rev. A 75 012337
[81] Van den Nest M, Dür W, Miyake A, Briegel H J 2007 New J. Phys. 9 204
[82] Gross D, Flammia S T, Eisert J 2009 Phys. Rev. Lett. 102 190501
[83] Bremner M J, Mora C, Winter A 2009 Phys. Rev. Lett. 102 190502
[84] Gu Z C, Wen X G 2009 Phys. Rev. B 80 155131
[85] Chen X, Gu Z C, Wen X G 2011 Phys. Rev. B 83 035107
[86] Schuch N, Pérez-García D, Cirac I 2011 Phys. Rev. B 84 165139
[87] Bartolucci S, Birchall P, Bombin H, Cable H, Dawson C, Gimeno-Segovia M, Johnston E, Kieling K, Nickerson N, Pant M, Pastawski F, Rudolph T, Sparrow C 2023 Nat. Commun. 14 912
[88] Kitaev A, Shen A H, Vyalyi M N 2002 Classical and Quantum Computation, vol. 47 of Graduate Studies in Mathematics (Providence: American Mathematical Society)
[89] Wocjan P, Roetteler M, Janzing D, Beth T 2002 Quant. Infor. Comput. 2 133
[90] Dodd J L, Nielsen M A, Bremner M J, Thew R T 2002 Phys. Rev. A 65 040301
[91] Cubitt T S, Montanaro A, Piddock S 2018 Proceedings of the National Academy of Sciences 115 9497
[92] Kohler T, Piddock S, Bausch J, Cubitt T 2021 Ann. Henri Poincaré 23 223–254
[93] Kohler T, Piddock S, Bausch J, Cubitt T 2022 PRX Quantum 3 010308
[94] Berry D W, Ahokas G, Cleve R, Sanders B C 2007 Commun. Math. Phys. 270 359
[95] Cirac J I, Zoller P 2012 Nat. Phys. 8 264
[96] Shepherd D J, Franz T, Werner R F 2006 Phys. Rev. Lett. 97 020502
[97] Janzing D 2007 Phys. Rev. A 75 012307
[98] Nagaj D, Wocjan P 2008 Phys. Rev. A 78 032311
[99] Nagaj D 2012 Phys. Rev. A 85 032330
[100] Lloyd S, Terhal B 2016 New J. Phys. 18 023042
[101] Toffoli T, Margolus N 1987 Cellular Automata Machines: A new environment for modeling (MIT Press)
[102] Bisio A, D’ Ariano G M, Tosini A 2015 Ann. Phys. 354 244
[103] Heim B, Rønnow T F, Isakov S V, Troyer M 2015 Science 348 215
[104] Villanueva A, Najafi P, Kappen H J 2023 J. Phys. A: Math. Theor. 56 465304
[105] Bravyi S, DiVincenzo D P, Oliveira R I, Terhal B M 2008 Quantum Infor. Comput. 8 0361
[106] Zhang J, Kyaw T H, Filipp S, Kwek L C, Sjöqvist E, Tong D 2023 Phys. Reports 1027 1
[107] Wootters W K 1987 Ann. Phys. 176 1
[108] Gross D 2006 J. Math. Phys. 47 122107
[109] Bravyi S, Kitaev A 2005 Phys. Rev. A 71 022316
[110] Popescu S, Rohrlich D 1994 Found. Phys. 24 379
[111] Spekkens R W 2008 Phys. Rev. Lett. 101 020401
[112] Spekkens R W 2005 Phys. Rev. A 71 052108
[113] Bennett C H, Brassard G, Crépeau C, Jozsa R, Peres A, Wootters W K 1993 Phys. Rev. Lett. 70 1895
[114] Gottesman D, Chuang I L 1999 Nature 402 390
[115] Long G L 2006 Commun. Theor. Phys. 45 825
[116] Childs A M, Wiebe N 2012 Quant. Infor. Comput. 12 901
[117] Berry D W, Childs A M, Cleve R, Kothari R, Somma R D 2015 Phys. Rev. Lett. 114 090502
[118] Wei S, Long G L 2016 Quantum Infor. Processing 15 1189
[119] Zhou X, Leung D W, Chuang I L 2000 Phys. Rev. A 62 052316
[120] Broadbent A 2016 Phys. Rev. A 94 022318
[121] Clauser J F, Horne M A, Shimony A, Holt R A 1969 Phys. Rev. Lett. 23 880
[122] Vaidman L 2003 Phys. Rev. Lett. 90 010402
[123] Brassard G, Buhrman H, Linden N, Méthot A A, Tapp A, Unger F 2006 Phys. Rev. Lett. 96 250401
[124] Chitambar E, Leung D, Mančinska L, Ozols M, Winter A 2014 Commun. Math. Phys. 328 303
[125] Bennett C H, DiVincenzo D P, Smolin J A 1997 Phys. Rev. Lett. 78 3217
[126] Gheorghiu A, Kapourniotis T, Kashefi E 2019 Theory of Computing Systems 63 715–808
[127] Wang D S 2024 Chin. Phys. B 33 080302
[128] Horodecki M, Shor P, Ruskai M B 2003 Rev. Math. Phys. 15 629
[129] Rosset D, Buscemi F, Liang Y C 2018 Phys. Rev. X 8 021033
[130] Li L, Hall M J W, Wiseman H M 2018 Phys. Reports 759 1
[131] Eastin B, Knill E 2009 Phys. Rev. Lett. 102 110502
[132] Degen C L, Reinhard F, Cappellaro P 2017 Rev. Mod. Phys. 89 035002
[133] Yoder T J, Takagi R, Chuang I L 2016 Phys. Rev. X 6 031039
[134] Zeng B, Chen X, Zhou D L, Wen X G 2019 Quantum Information Meets Quantum Matter (Springer-Verlag New York)
[135] Koenig R, Kuperberg G, Reichardt B W 2010 Ann. Phys. 325 2707
[136] Brown B J, Loss D, Pachos J K, Self C N, Wootton J R 2016 Rev. Mod. Phys. 88 045005
[137] Sarma S D, Freedman M, Nayak C 2015 npj Quantum Information 1 15001
[138] Harper F, Roy R, Rudner M S, Sondhi S L 2020 Ann. Rev. Condensed Matter Phys. 11 345
[139] Khodjasteh K, Lidar D A 2008 Phys. Rev. A 78 012355
[140] Verstraete F, Wolf M M, Cirac J I 2009 Nat. Phys. 5 633
[141] Anderson J T, Duclos-Cianci G, Poulin D 2014 Phys. Rev. Lett. 113 080501
[142] Liu Y T, Wang K, Liu Y D, Wang D S 2023 Entropy 25 1187
[143] Araujo M, Feix A, Costa F, Brukner C 2014 New J. Phys. 16 093026
[144] Bengtsson I, Życzkowski K 2006 Geometry of Quantum States (Cambridge U.K.: Cambridge University Press)
[145] Wang K, Wang D S 2023 New J. Phys. 25 043013
[146] Bennett C H, Brassard G 1984 In Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing (Bangalore, India, (IEEE, New York)),p 175–179
[147] Morris J, Saggio V, Gocanin A, Dakic B 2022 Adv. Quantum Technol. 5 2100118
[148] Huang H L, Wu D, Fan D, Zhu X 2020 Sci. China Inf. Sci. 63 180501
[149] Wang J, Sciarrino F, Laing A, Thompson M G 2020 Nat. Photonics 14 273–284
[150] Editorial 2022 Nat. Rev. Phys. 4 1
[151] Ma Y, Ma Y Z, Zhou Z Q, Li C F, Guo G C 2021 Nat. Commun. 12 2381
[152] Chiribella G, D’Ariano G M, Perinotti P 2008 Phys. Rev. Lett. 101 180501
[153] Gutoski G, Watrous J 2007 In Proceedings of the 39th ACM Symposium on Theory of Computing.p 565574
[154] Mehta P, Bukov M, Wang C H, Day A G R, Richardson C, Fisher C K, Schwab D J 2019 Phys. Reports 810 1
[155] Lim D, Doriguello J F, Rebentrost P 2023. ArXiv:quantph/2304.02262
[156] Dunjko V, Briegel H J 2018 Rep. Prog. Phys. 81 074001
[157] Verdon G, Pye J, Broughton M 2018. ArXiv:quantph/1806.09729
[158] Benedetti M, Lloyd E, Sack S, Fiorentini M 2019 Quantum Science and Technology 4 043001
[159] Huang H Y, Kueng R, Preskill J 2021 Phys. Rev. Lett. 126 190505
[160] Caro M C 2024 ACM Trans. Quantum Comput. 5 2
[161] Cleve R, Ekert A, Macchiavello C, Mosca M 1998 Proc. R. Soc. (London), Ser. A 454 339
[162] Jozsa R, Linden N 2003 Proc. R. Soc. (London), Ser. A 459 2011
[163] Steane A M 2003 Studies in History and Philosophy of Modern Physics 34 469
[164] Van den Nest M 2013 Phys. Rev. Lett. 110 060504
[165] Howard M, Wallman J, Veitch V, Emerson J 2014 Nature 510 351"
[166] Giovannetti V, Maccone L, Morimae T, Rudolph T G 2013 Phys. Rev. Lett. 111 230501
[167] Holevo A S 1977 Rep. Math. Phys. 12 273
[168] Tajima H, Shiraishi N, Saito K 2018 Phys. Rev. Lett. 121 110403
[169] Chiribella G, Yang Y, Renner R 2021 Phys. Rev. X 11 021014
[170] Weedbrook C, Pirandola S, García-Patrón R, Cerf N J, Ralph T C, Shapiro J H, Lloyd S 2012 Rev. Mod. Phys. 84 621
[171] Xu K, Fan H 2022 Chin. Phys. B 31 100304
[172] Emerson J, Weinstein Y S, Saraceno M, Lloyd S, Cory D G 2003 Science 302 2098
[173] Qin D, Xu X, Li Y 2022 Chin. Phys. B 31 090306
[174] Smith G, Yard J 2008 Science 321 1812
[175] Sauerwein D, Wallach N R, Gour G, Kraus B 2018 Phys. Rev. X 8 031020
[176] Google Quantum AI and Collaborators 2024. ArXiv preprint arXiv:2408.13687
Metrics
- Abstract views: 47
- PDF Downloads: 1
- Cited By: 0
下载:
