{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,22]],"date-time":"2026-07-22T10:48:22Z","timestamp":1784717302419,"version":"3.55.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,9,30]],"date-time":"2021-09-30T00:00:00Z","timestamp":1632960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>Semantic knowledge graphs are large-scale triple-oriented databases for knowledge representation and reasoning. Implicit knowledge can be inferred by modeling the tensor representations generated from knowledge graphs. However, as the sizes of knowledge graphs continue to grow, classical modeling becomes increasingly computationally resource intensive. This article investigates how to capitalize on quantum resources to accelerate the modeling of knowledge graphs. In particular, we propose the first quantum machine learning algorithm for inference on tensorized data, i.e., on knowledge graphs. Since most tensor problems are NP-hard [18], it is challenging to devise quantum algorithms to support the inference task. We simplify the modeling task by making the plausible assumption that the tensor representation of a knowledge graph can be approximated by its low-rank tensor singular value decomposition, which is verified by our experiments. The proposed sampling-based quantum algorithm achieves speedup with a polylogarithmic runtime in the dimension of knowledge graph tensor.<\/jats:p>","DOI":"10.1145\/3467982","type":"journal-article","created":{"date-parts":[[2021,9,30]],"date-time":"2021-09-30T17:35:15Z","timestamp":1633023315000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Quantum Machine Learning Algorithm for Knowledge Graphs"],"prefix":"10.1145","volume":"2","author":[{"given":"Yunpu","family":"Ma","sequence":"first","affiliation":[{"name":"Ludwig Maximilian University of Munich"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Volker","family":"Tresp","sequence":"additional","affiliation":[{"name":"Ludwig Maximilian University of Munich &amp; Siemens CT"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,9,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1219092.1219097"},{"key":"e_1_2_1_2_1","volume-title":"Quantum machine learning. Nature 549, 7671","author":"Biamonte Jacob","year":"2017","unstructured":"Jacob Biamonte , Peter Wittek , Nicola Pancotti , Patrick Rebentrost , Nathan Wiebe , and Seth Lloyd . 2017. Quantum machine learning. Nature 549, 7671 ( 2017 ), 195. Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. 2017. Quantum machine learning. Nature 549, 7671 (2017), 195."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376746"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999792.2999923"},{"key":"e_1_2_1_5_1","first-page":"1","article-title":"The power of block-encoded matrix powers: Improved regression techniques via faster hamiltonian simulation","volume":"33","author":"Chakraborty Shantanav","year":"2019","unstructured":"Shantanav Chakraborty , Andras Gilyen , and Stacey Jeffery . 2019 . The power of block-encoded matrix powers: Improved regression techniques via faster hamiltonian simulation . In ICALP. 33 : 1 \u2013 33 :14. Shantanav Chakraborty, Andras Gilyen, and Stacey Jeffery. 2019. The power of block-encoded matrix powers: Improved regression techniques via faster hamiltonian simulation. In ICALP. 33:1\u201333:14.","journal-title":"ICALP."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/070711621"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"022315","DOI":"10.1103\/PhysRevA.97.022315","article-title":"Continuous-variable quantum Gaussian process regression and quantum singular value decomposition of nonsparse low-rank matrices","volume":"97","author":"Das Siddhartha","year":"2018","unstructured":"Siddhartha Das , George Siopsis , and Christian Weedbrook . 2018 . Continuous-variable quantum Gaussian process regression and quantum singular value decomposition of nonsparse low-rank matrices . Phys. Rev. A 97 , 2 (2018), 022315 . Siddhartha Das, George Siopsis, and Christian Weedbrook. 2018. Continuous-variable quantum Gaussian process regression and quantum singular value decomposition of nonsparse low-rank matrices. Phys. Rev. A 97, 2 (2018), 022315.","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896305696"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623623"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509922"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3304889.3304950"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02650179"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039494"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316366"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.100.160501"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 2019 IEEE International Conference on Systems, Man and Cybernetics.","author":"Gu Lejia","year":"2019","unstructured":"Lejia Gu , Wang Xiaoqiang , and Zhang Guofeng . 2019 . Quantum higher order singular value decomposition . In Proceedings of the 2019 IEEE International Conference on Systems, Man and Cybernetics. Lejia Gu, Wang Xiaoqiang, and Zhang Guofeng. 2019. Quantum higher order singular value decomposition. In Proceedings of the 2019 IEEE International Conference on Systems, Man and Cybernetics."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512329"},{"key":"e_1_2_1_19_1","unstructured":"Iordanis Kerenidis and Anupam Prakash. 2016. Quantum recommendation systems. arxiv:1603.08675. Retrieved from https:\/\/arxiv.org\/abs\/1603.08675.  Iordanis Kerenidis and Anupam Prakash. 2016. Quantum recommendation systems. arxiv:1603.08675. Retrieved from https:\/\/arxiv.org\/abs\/1603.08675."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3454287.3454659"},{"key":"e_1_2_1_21_1","volume-title":"Quantum measurements and the Abelian Stabilizer Problem. Electron. Colloquium Comput. Complex. 3, 3","author":"Kitaev Yu","year":"1996","unstructured":"A.\u00a0 Yu Kitaev . 1996. Quantum measurements and the Abelian Stabilizer Problem. Electron. Colloquium Comput. Complex. 3, 3 ( 1996 ). A.\u00a0Yu Kitaev. 1996. Quantum measurements and the Abelian Stabilizer Problem. Electron. Colloquium Comput. Complex. 3, 3 (1996)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479800368354"},{"key":"e_1_2_1_23_1","volume-title":"Universal quantum simulators. Science 273, 5278","author":"Lloyd Seth","year":"1996","unstructured":"Seth Lloyd . 1996. Universal quantum simulators. Science 273, 5278 ( 1996 ), 1073\u20131078. https:\/\/science.sciencemag.org\/content\/273\/5278\/1073. Seth Lloyd. 1996. Universal quantum simulators. Science 273, 5278 (1996), 1073\u20131078. https:\/\/science.sciencemag.org\/content\/273\/5278\/1073."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys3029"},{"key":"e_1_2_1_25_1","unstructured":"Farzaneh Mahdisoltani Joanna Biega and Fabian\u00a0M. Suchanek. 2013. Yago3: A knowledge base from multilingual wikipedias. In CIDR. https:\/\/www.semanticscholar.org\/paper\/YAGO3%3A-A-Knowledge-Base-from-Multilingual-Mahdisoltani-Biega\/6c5b5adc3830ac45bf1d764603b1b71e5f729616.  Farzaneh Mahdisoltani Joanna Biega and Fabian\u00a0M. Suchanek. 2013. Yago3: A knowledge base from multilingual wikipedias. In CIDR. https:\/\/www.semanticscholar.org\/paper\/YAGO3%3A-A-Knowledge-Base-from-Multilingual-Mahdisoltani-Biega\/6c5b5adc3830ac45bf1d764603b1b71e5f729616."},{"key":"e_1_2_1_26_1","unstructured":"Nam\u00a0H. Nguyen Petros Drineas and Trac\u00a0D. Tran. 2010. Tensor sparsification via a bound on the spectral norm of random tensors. arxiv:1005.4732. Retrieved from https:\/\/arxiv.org\/abs\/1005.4732.  Nam\u00a0H. Nguyen Petros Drineas and Trac\u00a0D. Tran. 2010. Tensor sparsification via a bound on the spectral norm of random tensors. arxiv:1005.4732. Retrieved from https:\/\/arxiv.org\/abs\/1005.4732."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3104482.3104584"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2015.2483592"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/3016100.3016172"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.130503"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.97.012327"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-017-1603-1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242667"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316310"},{"key":"e_1_2_1_36_1","unstructured":"Ryota Tomioka and Taiji Suzuki. 2014. Spectral norm of random tensors. arxiv:1407.1870. Retrieved from https:\/\/arxiv.org\/abs\/1407.1870.  Ryota Tomioka and Taiji Suzuki. 2014. Spectral norm of random tensors. arxiv:1407.1870. Retrieved from https:\/\/arxiv.org\/abs\/1407.1870."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/W15-4007"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/3045390.3045609"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289464"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2871393.2871400"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.120.050502"},{"key":"e_1_2_1_42_1","unstructured":"Bishan Yang Wen-tau Yih Xiaodong He Jianfeng Gao and Li Deng. 2014. Embedding entities and relations for learning and inference in knowledge bases. arxiv:1412.6575. Retrieved from https:\/\/arxiv.org\/abs\/1412.6575.  Bishan Yang Wen-tau Yih Xiaodong He Jianfeng Gao and Li Deng. 2014. Embedding entities and relations for learning and inference in knowledge bases. arxiv:1412.6575. Retrieved from https:\/\/arxiv.org\/abs\/1412.6575."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899352045"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3467982","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3467982","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:19:05Z","timestamp":1750191545000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3467982"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,30]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3467982"],"URL":"https:\/\/doi.org\/10.1145\/3467982","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,30]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}