{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T20:08:44Z","timestamp":1775678924713,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,9,2]],"date-time":"2015-09-02T00:00:00Z","timestamp":1441152000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2015,9,2]],"date-time":"2015-09-02T00:00:00Z","timestamp":1441152000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Sci Rep"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using the Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the spatial quantum search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal spatial search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.<\/jats:p>","DOI":"10.1038\/srep13304","type":"journal-article","created":{"date-parts":[[2015,9,2]],"date-time":"2015-09-02T09:43:10Z","timestamp":1441186990000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":82,"title":["Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs"],"prefix":"10.1038","volume":"5","author":[{"given":"Leonardo","family":"Novo","sequence":"first","affiliation":[]},{"given":"Shantanav","family":"Chakraborty","sequence":"additional","affiliation":[]},{"given":"Masoud","family":"Mohseni","sequence":"additional","affiliation":[]},{"given":"Hartmut","family":"Neven","sequence":"additional","affiliation":[]},{"given":"Yasser","family":"Omar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,9,2]]},"reference":[{"key":"BFsrep13304_CR1","doi-asserted-by":"crossref","unstructured":"Aharonov, Y., Davidovich, L. & Zagury, N. Quantum random walks. Physical Review A 48, 1687 (1993).","DOI":"10.1103\/PhysRevA.48.1687"},{"key":"BFsrep13304_CR2","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1103\/PhysRevA.58.915","volume":"58","author":"E Farhi","year":"1998","unstructured":"Farhi, E. & Gutmann, S. Quantum computation and decision trees. Physical Review A 58, 915 (1998).","journal-title":"Physical Review A"},{"key":"BFsrep13304_CR3","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1080\/00107151031000110776","volume":"44","author":"J Kempe","year":"2003","unstructured":"Kempe, J. Quantum random walks: an introductory overview. Contemporary Physics 44, 307 (2003).","journal-title":"Contemporary Physics"},{"key":"BFsrep13304_CR4","doi-asserted-by":"crossref","unstructured":"Aharonov, D., Ambainis, A., Kempe, J. & Vazirani, U. Quantum walks on graphs. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, 50 (ACM, 2001).","DOI":"10.1145\/380752.380758"},{"key":"BFsrep13304_CR5","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1142\/S0219749906002195","volume":"4","author":"V Kendon","year":"2006","unstructured":"Kendon, V. Quantum walks on general graphs. International Journal of Quantum Information 4, 791 (2006).","journal-title":"International Journal of Quantum Information"},{"key":"BFsrep13304_CR6","first-page":"603","volume":"61","author":"D Reitzner","year":"2012","unstructured":"Reitzner, D., Nagaj, D. & Buzek, V. Quantum walks. Acta Physica Slovaca 61, 603 (2012).","journal-title":"Acta Physica Slovaca"},{"key":"BFsrep13304_CR7","doi-asserted-by":"publisher","first-page":"1015","DOI":"10.1007\/s11128-012-0432-5","volume":"11","author":"SE Venegas-Andraca","year":"2012","unstructured":"Venegas-Andraca, S. E. Quantum walks: a comprehensive review. Quantum Information Processing 11, 1015\u20131106 (2012).","journal-title":"Quantum Information Processing"},{"key":"BFsrep13304_CR8","doi-asserted-by":"publisher","first-page":"042304","DOI":"10.1103\/PhysRevA.74.042304","volume":"74","author":"Y Omar","year":"2006","unstructured":"Omar, Y., Paunkovi\u0107, N., Sheridan, L. & Bose, S. Quantum walk on a line with two entangled particles. Physical Review A 74, 042304 (2006).","journal-title":"Physical Review A"},{"key":"BFsrep13304_CR9","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1126\/science.1229957","volume":"339","author":"AM Childs","year":"2013","unstructured":"Childs, A. M., Gosset, D. & Webb, Z. Universal computation by multiparticle quantum walk. Science 339, 791 (2013).","journal-title":"Science"},{"key":"BFsrep13304_CR10","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/s00220-009-0930-1","volume":"294","author":"AM Childs","year":"2010","unstructured":"Childs, A. M. On the relationship between continuous-and discrete-time quantum walk. Communications in Mathematical Physics 294, 581 (2010).","journal-title":"Communications in Mathematical Physics"},{"key":"BFsrep13304_CR11","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. Physical Review A 70, 022314 (2004).","journal-title":"Physical Review A"},{"key":"BFsrep13304_CR12","doi-asserted-by":"crossref","unstructured":"Childs, A. M. et al. Exponential algorithmic speedup by a quantum walk. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, 59-68 (ACM, 2003).","DOI":"10.1145\/780542.780552"},{"key":"BFsrep13304_CR13","doi-asserted-by":"publisher","first-page":"180501","DOI":"10.1103\/PhysRevLett.102.180501","volume":"102","author":"AM Childs","year":"2009","unstructured":"Childs, A. M. Universal computation by quantum walk. Physical Review Letters 102, 180501 (2009).","journal-title":"Physical Review Letters"},{"key":"BFsrep13304_CR14","doi-asserted-by":"publisher","first-page":"174106","DOI":"10.1063\/1.3002335","volume":"129","author":"M Mohseni","year":"2008","unstructured":"Mohseni, M., Rebentrost, P., Lloyd, S. & Aspuru-Guzik, A. Environment-assisted quantum walks in photosynthetic energy transfer. The Journal of chemical physics 129, 174106 (2008).","journal-title":"The Journal of chemical physics"},{"key":"BFsrep13304_CR15","doi-asserted-by":"publisher","first-page":"033003","DOI":"10.1088\/1367-2630\/11\/3\/033003","volume":"11","author":"P Rebentrost","year":"2009","unstructured":"Rebentrost, P., Mohseni, M., Kassal, I., Lloyd, S. & Aspuru-Guzik, A. Environment-assisted quantum transport. New Journal of Physics 11, 033003 (2009).","journal-title":"New Journal of Physics"},{"key":"BFsrep13304_CR16","doi-asserted-by":"publisher","first-page":"113019","DOI":"10.1088\/1367-2630\/10\/11\/113019","volume":"10","author":"MB Plenio","year":"2008","unstructured":"Plenio, M. B. & Huelga, S. F. Dephasing-assisted transport: quantum networks and biomolecules. New Journal of Physics 10, 113019 (2008).","journal-title":"New Journal of Physics"},{"key":"BFsrep13304_CR17","doi-asserted-by":"publisher","first-page":"105106","DOI":"10.1063\/1.3223548","volume":"131","author":"F Caruso","year":"2009","unstructured":"Caruso, F., Chin, A. W., Datta, A., Huelga, S. F. & Plenio, M. B. Highly efficient energy excitation transfer in light-harvesting complexes: The fundamental role of noise-assisted transport. The Journal of Chemical Physics 131, 105106 (2009).","journal-title":"The Journal of Chemical Physics"},{"key":"BFsrep13304_CR18","doi-asserted-by":"publisher","first-page":"207901","DOI":"10.1103\/PhysRevLett.91.207901","volume":"91","author":"S Bose","year":"2003","unstructured":"Bose, S. Quantum communication through an unmodulated spin chain. Physical Review Letters 91, 207901 (2003).","journal-title":"Physical Review Letters"},{"key":"BFsrep13304_CR19","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1142\/S0219749910006514","volume":"8","author":"APerfect Kay","year":"2010","unstructured":"Kay, A. Perfect, efficient, state transfer and its application as a constructive tool. International Journal of Quantum Information 8, 641 (2010).","journal-title":"International Journal of Quantum Information"},{"key":"BFsrep13304_CR20","doi-asserted-by":"crossref","unstructured":"Mohseni, M., Omar, Y., Engel, G. S. & Plenio, M. B. Quantum effects in biology (Cambridge University Press, 2014).","DOI":"10.1017\/CBO9780511863189"},{"key":"BFsrep13304_CR21","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1142\/S0219749909005389","volume":"7","author":"S Bose","year":"2009","unstructured":"Bose, S., Casaccino, A., Mancini, S. & Severini, S. Communication in xyz all-to all quantum networks with a missing link. International Journal of Quantum Information 7, 713 (2009).","journal-title":"International Journal of Quantum Information"},{"key":"BFsrep13304_CR22","doi-asserted-by":"publisher","first-page":"210502","DOI":"10.1103\/PhysRevLett.112.210502","volume":"112","author":"J Janmark","year":"2014","unstructured":"Janmark, J., Meyer, D. A. & Wong, T. G. Global symmetry is unnecessary for fast quantum search. Physical Review Letters 112, 210502 (2014).","journal-title":"Physical Review Letters"},{"key":"BFsrep13304_CR23","doi-asserted-by":"publisher","first-page":"2403","DOI":"10.1103\/PhysRevA.57.2403","volume":"57","author":"E Farhi","year":"1998","unstructured":"Farhi, E. & Gutmann, S. Analog analogue of a digital quantum computation. Physical Review A 57, 2403 (1998).","journal-title":"Physical Review A"},{"key":"BFsrep13304_CR24","first-page":"225","volume":"45","author":"C Lanczos","year":"1950","unstructured":"Lanczos, C. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Nat\u2019l Bur. Std. 45, 225 (1950).","journal-title":"J. Res. Nat\u2019l Bur. Std."},{"key":"BFsrep13304_CR25","doi-asserted-by":"publisher","first-page":"070504","DOI":"10.1103\/PhysRevLett.112.070504","volume":"112","author":"I Foulger","year":"2014","unstructured":"Foulger, I., Gnutzmann, S. & Tanner, G. Quantum search on graphene lattices. Physical Review Letters 112, 070504 (2014).","journal-title":"Physical Review Letters"},{"key":"BFsrep13304_CR26","doi-asserted-by":"publisher","first-page":"052337","DOI":"10.1103\/PhysRevA.89.052337","volume":"89","author":"AM Childs","year":"2014","unstructured":"Childs, A. M. & Ge, Y. Spatial search by continuous-time quantum walks on crystal lattices. Physical Review A 89, 052337 (2014).","journal-title":"Physical Review A"},{"key":"BFsrep13304_CR27","unstructured":"Aaronson, S. & Ambainis, A. Quantum search of spatial regions. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 200 (IEEE Computer Society, Washington, DC, USA, 2003)."},{"key":"BFsrep13304_CR28","doi-asserted-by":"publisher","first-page":"204309","DOI":"10.1063\/1.4807084","volume":"138","author":"M Mohseni","year":"2013","unstructured":"Mohseni, M., Shabani, A., Lloyd, S., Omar, Y. & Rabitz, H. Geometrical effects on energy transfer in disordered open quantum systems. The Journal of chemical physics 138, 204309 (2013).","journal-title":"The Journal of chemical physics"},{"key":"BFsrep13304_CR29","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1140\/epjb\/e2007-00281-5","volume":"59","author":"M Jafarizadeh","year":"2007","unstructured":"Jafarizadeh, M., Sufiani, R., Salimi, S. & Jafarizadeh, S. Investigation of continuous-time quantum walk by using Krylov subspace-Lanczos algorithm. The European Physical Journal B-Condensed Matter and Complex Systems 59, 199\u2013216 (2007).","journal-title":"The European Physical Journal B-Condensed Matter and Complex Systems"},{"key":"BFsrep13304_CR30","doi-asserted-by":"publisher","first-page":"062332","DOI":"10.1103\/PhysRevA.75.062332","volume":"75","author":"H Krovi","year":"2007","unstructured":"Krovi, H. & Brun, T. Quantum walks on quotient graphs. Physical Review A 75, 062332 (2007).","journal-title":"Physical Review A"},{"key":"BFsrep13304_CR31","doi-asserted-by":"publisher","first-page":"012323","DOI":"10.1103\/PhysRevA.79.012323","volume":"79","author":"D Reitzner","year":"2009","unstructured":"Reitzner, D., Hillery, M., Feldman, E. & Bu\u017eek, V. Quantum searches on highly symmetric graphs. Physical Review A 79, 012323 (2009).","journal-title":"Physical Review A"},{"key":"BFsrep13304_CR32","doi-asserted-by":"publisher","first-page":"2813","DOI":"10.1007\/s11128-013-0563-3","volume":"12","author":"R Sufiani","year":"2013","unstructured":"Sufiani, R. & Bahari, N. Quantum search in structured database using local adiabatic evolution and spectral methods. Quantum Information Processing 12, 2813\u20132831 (2013).","journal-title":"Quantum Information Processing"},{"key":"BFsrep13304_CR33","doi-asserted-by":"publisher","first-page":"030602","DOI":"10.1103\/PhysRevLett.113.030602","volume":"113","author":"Z-X Gong","year":"2014","unstructured":"Gong, Z.-X., Foss-Feig, M., Michalakis, S. & Gorshkov, A. V. Persistence of locality in systems with power-law interactions. Physical Review Letters 113, 030602 (2014).","journal-title":"Physical Review Letters"},{"key":"BFsrep13304_CR34","doi-asserted-by":"publisher","first-page":"015301","DOI":"10.1088\/1751-8113\/48\/1\/015301","volume":"48","author":"A Kumar","year":"2015","unstructured":"Kumar, A. & Sarovar, M. On model reduction for quantum dynamics: symmetries and invariant subspaces. Journal of Physics A: Mathematical and Theoretical 48, 015301 (2015).","journal-title":"Journal of Physics A: Mathematical and Theoretical"},{"key":"BFsrep13304_CR35","unstructured":"Farhi, E., Goldstone, J., Gutmann, S. & Sipser, M. Quantum computation by adiabatic evolution. quant-ph\/0001106 (2000)."},{"key":"BFsrep13304_CR36","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00440-004-0423-2","volume":"133","author":"J Kempe","year":"2005","unstructured":"Kempe, J. Discrete Quantum Walks Hit Exponentially Faster. Probability Theory and Related Fields 133, 215\u2013235 (2005).","journal-title":"Probability Theory and Related Fields"},{"key":"BFsrep13304_CR37","first-page":"6989","volume":"1312","author":"L Novo","year":"2013","unstructured":"Novo, L., Mohseni, M. & Omar, Y. Disorder-assisted quantum transport in suboptimal decoherence regimes. arXiv. 1312, 6989 (2013).","journal-title":"arXiv."},{"key":"BFsrep13304_CR38","doi-asserted-by":"publisher","first-page":"035102","DOI":"10.1063\/1.4856795","volume":"140","author":"M Mohseni","year":"2014","unstructured":"Mohseni, M., Shabani, A., Lloyd, S. & Rabitz, H. Energy-scales convergence for optimal and robust quantum transport in photosynthetic complexes. The Journal of Chemical Physics 140, 035102 (2014).","journal-title":"The Journal of Chemical Physics"},{"key":"BFsrep13304_CR39","doi-asserted-by":"publisher","first-page":"042706","DOI":"10.1103\/PhysRevE.89.042706","volume":"89","author":"A Shabani","year":"2014","unstructured":"Shabani, A., Mohseni, M., Rabitz, H. & Lloyd, S. Numerical evidence for robustness of environment-assisted quantum transport. Physical Review E 89, 042706 (2014).","journal-title":"Physical Review E"},{"key":"BFsrep13304_CR40","doi-asserted-by":"publisher","first-page":"050502","DOI":"10.1103\/PhysRevLett.109.050502","volume":"109","author":"C Godsil","year":"2012","unstructured":"Godsil, C., Kirkland, S., Severini, S. & Smith, J. Number-theoretic nature of communication in quantum spin systems. Physical Review Letters 109, 050502 (2012).","journal-title":"Physical Review Letters"},{"key":"BFsrep13304_CR41","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1038\/nature13461","volume":"511","author":"P Jurcevic","year":"2014","unstructured":"Jurcevic, P. et al. Quasiparticle engineering and entanglement propagation in a quantum many-body system. Nature 511, 202 (2014).","journal-title":"Nature"},{"key":"BFsrep13304_CR42","doi-asserted-by":"publisher","first-page":"110503","DOI":"10.1103\/PhysRevLett.114.110503","volume":"114","author":"DA Meyer","year":"2015","unstructured":"Meyer, D. A. & Wong, T. G. Connectivity is a poor indicator of fast quantum search. Physical Review Letters 114, 110503 (2015).","journal-title":"Physical Review Letters"},{"key":"BFsrep13304_CR43","doi-asserted-by":"publisher","first-page":"1767","DOI":"10.1007\/s11128-015-0959-3","volume":"14","author":"T Wong","year":"2015","unstructured":"Wong, T. Diagrammatic approach to quantum search. Quantum Information Processing 14, 1767\u20131775 (2015).","journal-title":"Quantum Information Processing"}],"container-title":["Scientific Reports"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.nature.com\/articles\/srep13304","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/srep13304.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/srep13304.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,5]],"date-time":"2023-01-05T22:11:59Z","timestamp":1672956719000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.nature.com\/articles\/srep13304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,2]]},"references-count":43,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2015,10,16]]}},"alternative-id":["BFsrep13304"],"URL":"https:\/\/doi.org\/10.1038\/srep13304","relation":{},"ISSN":["2045-2322"],"issn-type":[{"value":"2045-2322","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,2]]},"assertion":[{"value":"26 February 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2015","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing financial interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"13304"}}