{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:27:22Z","timestamp":1740137242937,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T00:00:00Z","timestamp":1569283200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T00:00:00Z","timestamp":1569283200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"crossref","award":["2011\/03\/D\/ST6\/00413"],"award-info":[{"award-number":["2011\/03\/D\/ST6\/00413"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2011\/03\/D\/ST6\/00413"],"award-info":[{"award-number":["2011\/03\/D\/ST6\/00413"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n              <jats:p>In this paper, we demonstrate that the efficiency of quantum spatial search can be significantly altered by malicious manipulation of the input data in the client\u2013server model. We achieve this by exploiting exceptional configuration effect on Szegedy spatial search and proposing a framework suitable for analysing efficiency of attacks on quantum search algorithms. We provide the analysis of proposed attacks for different models of random graphs. The obtained results demonstrate that quantum algorithms in general are not secure against input data alteration.<\/jats:p>","DOI":"10.1007\/s11128-019-2459-3","type":"journal-article","created":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T07:02:57Z","timestamp":1569308577000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Impact of the malicious input data modification on the efficiency of quantum spatial search"],"prefix":"10.1007","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6320-7699","authenticated-orcid":false,"given":"Adam","family":"Glos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8790-101X","authenticated-orcid":false,"given":"Jaros\u0142aw Adam","family":"Miszczak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,24]]},"reference":[{"issue":"2","key":"2459_CR1","doi-asserted-by":"publisher","first-page":"022314","DOI":"10.1103\/PhysRevA.70.022314","volume":"70","author":"AM Childs","year":"2004","unstructured":"Childs, A.M., Goldstone, J.: Spatial search by quantum walk. Phys. Rev. A 70(2), 022314 (2004)","journal-title":"Phys. Rev. A"},{"issue":"7671","key":"2459_CR2","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1038\/nature23458","volume":"549","author":"AW Harrow","year":"2017","unstructured":"Harrow, A.W., Montanaro, A.: Quantum computational supremacy. Nature 549(7671), 203\u2013209 (2017)","journal-title":"Nature"},{"issue":"7671","key":"2459_CR3","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1038\/nature23461","volume":"549","author":"DJ Bernstein","year":"2017","unstructured":"Bernstein, D.J., Lange, T.: Post-quantum cryptography. Nature 549(7671), 188 (2017)","journal-title":"Nature"},{"issue":"10","key":"2459_CR4","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/2494568","volume":"56","author":"R Van Meter","year":"2013","unstructured":"Van Meter, R., Horsman, C.: A blueprint for building a quantum computer. Commun. ACM 56(10), 84\u201393 (2013)","journal-title":"Commun. ACM"},{"key":"2459_CR5","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s11128-010-0201-2","volume":"10","author":"M Saeedi","year":"2011","unstructured":"Saeedi, M., Wille, R., Drechsler, R.: Synthesis of quantum circuits for linear nearest neighbor architectures. Quantum Inf. Process. 10, 355\u2013377 (2011)","journal-title":"Quantum Inf. Process."},{"issue":"10","key":"2459_CR6","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1038\/nphoton.2010.214","volume":"4","author":"L Lydersen","year":"2010","unstructured":"Lydersen, L., Wiechers, C., Wittmann, C., Elser, D., Skaar, J., Makarov, V.: Hacking commercial quantum cryptography systems by tailored bright illumination. Nat. Photonics 4(10), 686\u2013689 (2010)","journal-title":"Nat. Photonics"},{"issue":"10","key":"2459_CR7","doi-asserted-by":"publisher","first-page":"100501","DOI":"10.1103\/PhysRevLett.116.100501","volume":"116","author":"S Chakraborty","year":"2016","unstructured":"Chakraborty, S., Novo, L., Ambainis, A., Omar, Y.: Spatial search by quantum walk is optimal for almost all graphs. Phys. Rev. Lett. 116(10), 100501 (2016)","journal-title":"Phys. Rev. Lett."},{"key":"2459_CR8","doi-asserted-by":"crossref","unstructured":"Broadbent, A., Fitzsimons, J., Kashefi, E.: Universal blind quantum computation. In: 2009 50th Annual IEEE Symposium on Foundations of Computer Science. IEEE, pp.\u00a0517\u2013526 (2009)","DOI":"10.1109\/FOCS.2009.36"},{"key":"2459_CR9","doi-asserted-by":"publisher","first-page":"220503","DOI":"10.1103\/PhysRevLett.119.220503","volume":"119","author":"S Chakraborty","year":"2017","unstructured":"Chakraborty, S., Novo, L., Di Giorgio, S., Omar, Y.: Optimal quantum spatial search on random temporal networks. Phys. Rev. Lett. 119, 220503 (2017)","journal-title":"Phys. Rev. Lett."},{"key":"2459_CR10","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s11128-018-1844-7","volume":"17","author":"A Glos","year":"2018","unstructured":"Glos, A., Krawiec, A., Kukulski, R., Pucha\u0142a, Z.: Vertices cannot be hidden from quantum spatial search for almost all random graphs. Quantum Inf. Process. 17, 81 (2018)","journal-title":"Quantum Inf. Process."},{"key":"2459_CR11","doi-asserted-by":"crossref","unstructured":"Nahimovs, N., Santos, R.A.: Adjacent vertices can be hard to find by quantum walks. In: SOFSEM 2017: SOFSEM 2017: Theory and Practice of Computer Science, LNCS, vol.\u00a010139, pp.\u00a0256\u2013267 (2017)","DOI":"10.1007\/978-3-319-51963-0_20"},{"key":"2459_CR12","unstructured":"Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings of the 16th ACM-SIAM SODA, pp.\u00a01099\u20131108 (2005)"},{"key":"2459_CR13","doi-asserted-by":"crossref","unstructured":"Nahimovs, N., Rivosh, A.: Exceptional configurations of quantum walks with Grover\u2019s coin. In: International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Springer, pp.\u00a079\u201392 (2015)","DOI":"10.1007\/978-3-319-29817-7_8"},{"issue":"7","key":"2459_CR14","doi-asserted-by":"publisher","first-page":"1016","DOI":"10.1134\/S1995080218070144","volume":"39","author":"K Khadiev","year":"2018","unstructured":"Khadiev, K., Nahimovs, N., Santos, R.: On the probability of finding marked connected components using quantum walks. Lobachevskii J. Math. 39(7), 1016\u20131023 (2018)","journal-title":"Lobachevskii J. Math."},{"issue":"3","key":"2459_CR15","doi-asserted-by":"publisher","first-page":"032334","DOI":"10.1103\/PhysRevA.94.032334","volume":"94","author":"K Pr\u016bsis","year":"2016","unstructured":"Pr\u016bsis, K., Vihrovs, J., Wong, T.G.: Stationary states in quantum walk search. Phys. Rev. A 94(3), 032334 (2016)","journal-title":"Phys. Rev. A"},{"key":"2459_CR16","unstructured":"Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the FOCS 2004. IEEE, pp.\u00a032\u201341 (2004)"},{"key":"2459_CR17","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s11128-017-1667-y","volume":"16","author":"TG Wong","year":"2017","unstructured":"Wong, T.G.: Equivalence of Szegedy\u2019s and coined quantum walks. Quantum Inf. Process. 16, 215 (2017)","journal-title":"Quantum Inf. Process."},{"issue":"6684","key":"2459_CR18","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684), 440 (1998)","journal-title":"Nature"},{"issue":"5439","key":"2459_CR19","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A-L Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509\u2013512 (1999)","journal-title":"Science"},{"issue":"1","key":"2459_CR20","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert, R., Barab\u00e1si, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74(1), 47 (2002)","journal-title":"Rev. Mod. Phys."},{"key":"2459_CR21","volume-title":"Cambridge Studies in Advanced Mathematics. Modern Graph Theory","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Cambridge Studies in Advanced Mathematics. Modern Graph Theory, 2nd edn. Cambridge University Press, Cambridge (2001)","edition":"2"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-019-2459-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11128-019-2459-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-019-2459-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T23:15:06Z","timestamp":1600816506000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-019-2459-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,24]]},"references-count":21,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["2459"],"URL":"https:\/\/doi.org\/10.1007\/s11128-019-2459-3","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"type":"print","value":"1570-0755"},{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2019,9,24]]},"assertion":[{"value":"11 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"343"}}