Two-particle scattering on general graphs
Summarize this article with:
AbstractQuantum walks in general graphs, or more specifically scattering on graphs, encompass enough complexity to perform universal quantum computation. Any given quantum circuit can be broken down into single- and two-qubit gates, which can then be translated into subgraphs – gadgets – that implement such unitaries on the logical qubits, simulated by particles traveling along a sparse graph. In this work, we start to develop a full theory of multi-particle scattering on graphs and give initial applications to build multi-particle gadgets with different properties.Featured image: The main object of study are particles traveling towards a general graph G and then scattering to different rails, e.g, rails 1 and 2 in the picture.► BibTeX data@article{LimaKeller2026twoparticle, doi = {10.22331/q-2026-03-23-2038}, url = {https://doi.org/10.22331/q-2026-03-23-2038}, title = {Two-particle scattering on general graphs}, author = {Lima Keller, Luna and Jost Brod, Daniel}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2038}, month = mar, year = {2026} }► References [1] Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, pages 333–342, New York, NY, USA, 2011. Association for Computing Machinery. ISBN 9781450306911. 10.1145/1993636.1993682. URL https://doi.org/10.1145/1993636.1993682. https://doi.org/10.1145/1993636.1993682 [2] Daniel J. Brod and Joshua Combes. A passive cphase gate via cross-kerr nonlinearities. Phys. Rev. Lett., 117: 080502, Aug 2016. 10.1103/PhysRevLett.117.080502. URL https://doi.org/10.1103/PhysRevLett.117.080502. https://doi.org/10.1103/PhysRevLett.117.080502 [3] Daniel J. Brod, Joshua Combes, and Julio Gea-Banacloche. Two photons co- and counterpropagating through $n$ cross-kerr sites. Phys. Rev. A, 94: 023833, Aug 2016. 10.1103/PhysRevA.94.023833. URL https://doi.org/10.1103/PhysRevA.94.023833. https://doi.org/10.1103/PhysRevA.94.023833 [4] Andrew M. Childs. Universal computation by quantum walk. Phys. Rev. Lett., 102: 180501, 2009. 10.1103/PhysRevLett.102.180501. https://doi.org/10.1103/PhysRevLett.102.180501 [5] Andrew M. Childs and David Gosset. Levinson's theorem for graphs ii. Journal of Mathematical Physics, 53 (10): 102207, 2012. 10.1063/1.4757665. https://doi.org/10.1063/1.4757665 [6] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC '03, pages 59–68, New York, NY, USA, 2003. Association for Computing Machinery. ISBN 1581136749. 10.1145/780542.780552. URL https://doi.org/10.1145/780542.780552. https://doi.org/10.1145/780542.780552 [7] Andrew M. Childs, David Gosset, and Zak Webb. Universal computation by multiparticle quantum walk. Science, 339 (6121): 791–794, 2013. 10.1126/science.1229957. https://doi.org/10.1126/science.1229957 [8] J. M. Cook. Convergence to the møller wave-matrix. Journal of Mathematics and Physics, 36 (1-4): 82–87, 1957. https://doi.org/10.1002/sapm195736182. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/sapm195736182. https://doi.org/10.1002/sapm195736182 [9] Barbara M. DiVincenzo, David P. Terhal. Fermionic linear optics revisited. Foundations of Physics, 35: 1967–1984, 2005. 10.1007/s10701-005-8657-0. https://doi.org/10.1007/s10701-005-8657-0 [10] Shanhui Fan, Şükrü Ekin Kocabaş, and Jung-Tsung Shen. Input-output formalism for few-photon transport in one-dimensional nanophotonic waveguides coupled to a qubit. Phys. Rev. A, 82: 063821, Dec 2010. 10.1103/PhysRevA.82.063821. URL https://doi.org/10.1103/PhysRevA.82.063821. https://doi.org/10.1103/PhysRevA.82.063821 [11] Edward Farhi and Sam Gutmann. Quantum computation and decision trees. Phys. Rev. A, 58: 915–928, 1998. 10.1103/PhysRevA.58.915. https://doi.org/10.1103/PhysRevA.58.915 [12] M. N. Hack. On convergence to the møller wave operators.
Il Nuovo Cimento (1955-1965), 9: 731–733, 1958. https://doi.org/10.1007/BF02740912. https://doi.org/10.1007/BF02740912 [13] L. Rodman I. Gohberg, P. Lancaster. Matrix Polynomials. Society for Industrial and Applied Mathematics (SIAM), 2009. https://doi.org/10.1137/1.9780898719024. https://doi.org/10.1137/1.9780898719024 [14] Barry Simon Michael Reed. Methods of modern mathematical physics, vol III: Scattering theory. Academic Press, 1979. [15] D. B. Pearson. Singular continuous measures in scattering theory. Communications in Mathematical Physics, 60: 13–36, 02 1978. 10.1007/BF01609472. https://doi.org/10.1007/BF01609472 [16] Dmitry Ryndyk. Theory of Quantum Transport at Nanoscale. Springer Cham, 2016. https://doi.org/10.1007/978-3-319-24088-6. https://doi.org/10.1007/978-3-319-24088-6 [17] Jun John Sakurai. Modern quantum mechanics. Addison-Wesley, Reading, MA, 1994. https://doi.org/10.1017/9781108499996. https://doi.org/10.1017/9781108499996 [18] Luna Lima e Silva and Daniel Jost Brod. Two-Particle Scattering on Non-Translation Invariant Line Lattices. Quantum, 8: 1308, April 2024. ISSN 2521-327X. 10.22331/q-2024-04-04-1308. URL https://doi.org/10.22331/q-2024-04-04-1308. https://doi.org/10.22331/q-2024-04-04-1308 [19] John R. Taylor. Scattering Theory: The Quantum Theory of Nonrelativistic Collisions. John Wiley & Sons, Inc., New York, 1972. https://doi.org/10.1063/1.3128052. https://doi.org/10.1063/1.3128052 [20] Zhaohua Tian and Xue-Wen Chen. Passive and deterministic controlled-phase gate for single-photon wavepackets based on time-reversal symmetric photon transport, 2024. URL https://arxiv.org/abs/2312.10719. arXiv:2312.10719 [21] Françoise Tisseur and Karl Meerbergen. The quadratic eigenvalue problem. SIAM Review, 43, 08 2001. 10.1137/S0036144500381988. https://doi.org/10.1137/S0036144500381988 [22] Martin Varbanov and Todd A. Brun. Quantum scattering theory on graphs with tails. Phys. Rev. A, 80: 052330, 2009. 10.1103/PhysRevA.80.052330. https://doi.org/10.1103/PhysRevA.80.052330 [23] Martin Varbanov, Hari Krovi, and Todd A. Brun. Hitting time for the continuous quantum walk. Phys. Rev. A, 78: 022324, Aug 2008. 10.1103/PhysRevA.78.022324. URL https://doi.org/10.1103/PhysRevA.78.022324. https://doi.org/10.1103/PhysRevA.78.022324 [24] Shanshan Xu, Eden Rephaeli, and Shanhui Fan. Analytic properties of two-photon scattering matrix in integrated quantum systems determined by the cluster decomposition principle. Phys. Rev. Lett., 111: 223602, Nov 2013. 10.1103/PhysRevLett.111.223602. URL https://doi.org/10.1103/PhysRevLett.111.223602. https://doi.org/10.1103/PhysRevLett.111.223602Cited byCould not fetch Crossref cited-by data during last attempt 2026-03-23 08:29:19: Could not fetch cited-by data for 10.22331/q-2026-03-23-2038 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-03-23 08:29:19: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractQuantum walks in general graphs, or more specifically scattering on graphs, encompass enough complexity to perform universal quantum computation. Any given quantum circuit can be broken down into single- and two-qubit gates, which can then be translated into subgraphs – gadgets – that implement such unitaries on the logical qubits, simulated by particles traveling along a sparse graph. In this work, we start to develop a full theory of multi-particle scattering on graphs and give initial applications to build multi-particle gadgets with different properties.Featured image: The main object of study are particles traveling towards a general graph G and then scattering to different rails, e.g, rails 1 and 2 in the picture.► BibTeX data@article{LimaKeller2026twoparticle, doi = {10.22331/q-2026-03-23-2038}, url = {https://doi.org/10.22331/q-2026-03-23-2038}, title = {Two-particle scattering on general graphs}, author = {Lima Keller, Luna and Jost Brod, Daniel}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2038}, month = mar, year = {2026} }► References [1] Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, pages 333–342, New York, NY, USA, 2011. Association for Computing Machinery. ISBN 9781450306911. 10.1145/1993636.1993682. URL https://doi.org/10.1145/1993636.1993682. https://doi.org/10.1145/1993636.1993682 [2] Daniel J. Brod and Joshua Combes. A passive cphase gate via cross-kerr nonlinearities. Phys. Rev. Lett., 117: 080502, Aug 2016. 10.1103/PhysRevLett.117.080502. URL https://doi.org/10.1103/PhysRevLett.117.080502. https://doi.org/10.1103/PhysRevLett.117.080502 [3] Daniel J. Brod, Joshua Combes, and Julio Gea-Banacloche. Two photons co- and counterpropagating through $n$ cross-kerr sites. Phys. Rev. A, 94: 023833, Aug 2016. 10.1103/PhysRevA.94.023833. URL https://doi.org/10.1103/PhysRevA.94.023833. https://doi.org/10.1103/PhysRevA.94.023833 [4] Andrew M. Childs. Universal computation by quantum walk. Phys. Rev. Lett., 102: 180501, 2009. 10.1103/PhysRevLett.102.180501. https://doi.org/10.1103/PhysRevLett.102.180501 [5] Andrew M. Childs and David Gosset. Levinson's theorem for graphs ii. Journal of Mathematical Physics, 53 (10): 102207, 2012. 10.1063/1.4757665. https://doi.org/10.1063/1.4757665 [6] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC '03, pages 59–68, New York, NY, USA, 2003. Association for Computing Machinery. ISBN 1581136749. 10.1145/780542.780552. URL https://doi.org/10.1145/780542.780552. https://doi.org/10.1145/780542.780552 [7] Andrew M. Childs, David Gosset, and Zak Webb. Universal computation by multiparticle quantum walk. Science, 339 (6121): 791–794, 2013. 10.1126/science.1229957. https://doi.org/10.1126/science.1229957 [8] J. M. Cook. Convergence to the møller wave-matrix. Journal of Mathematics and Physics, 36 (1-4): 82–87, 1957. https://doi.org/10.1002/sapm195736182. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/sapm195736182. https://doi.org/10.1002/sapm195736182 [9] Barbara M. DiVincenzo, David P. Terhal. Fermionic linear optics revisited. Foundations of Physics, 35: 1967–1984, 2005. 10.1007/s10701-005-8657-0. https://doi.org/10.1007/s10701-005-8657-0 [10] Shanhui Fan, Şükrü Ekin Kocabaş, and Jung-Tsung Shen. Input-output formalism for few-photon transport in one-dimensional nanophotonic waveguides coupled to a qubit. Phys. Rev. A, 82: 063821, Dec 2010. 10.1103/PhysRevA.82.063821. URL https://doi.org/10.1103/PhysRevA.82.063821. https://doi.org/10.1103/PhysRevA.82.063821 [11] Edward Farhi and Sam Gutmann. Quantum computation and decision trees. Phys. Rev. A, 58: 915–928, 1998. 10.1103/PhysRevA.58.915. https://doi.org/10.1103/PhysRevA.58.915 [12] M. N. Hack. On convergence to the møller wave operators.
Il Nuovo Cimento (1955-1965), 9: 731–733, 1958. https://doi.org/10.1007/BF02740912. https://doi.org/10.1007/BF02740912 [13] L. Rodman I. Gohberg, P. Lancaster. Matrix Polynomials. Society for Industrial and Applied Mathematics (SIAM), 2009. https://doi.org/10.1137/1.9780898719024. https://doi.org/10.1137/1.9780898719024 [14] Barry Simon Michael Reed. Methods of modern mathematical physics, vol III: Scattering theory. Academic Press, 1979. [15] D. B. Pearson. Singular continuous measures in scattering theory. Communications in Mathematical Physics, 60: 13–36, 02 1978. 10.1007/BF01609472. https://doi.org/10.1007/BF01609472 [16] Dmitry Ryndyk. Theory of Quantum Transport at Nanoscale. Springer Cham, 2016. https://doi.org/10.1007/978-3-319-24088-6. https://doi.org/10.1007/978-3-319-24088-6 [17] Jun John Sakurai. Modern quantum mechanics. Addison-Wesley, Reading, MA, 1994. https://doi.org/10.1017/9781108499996. https://doi.org/10.1017/9781108499996 [18] Luna Lima e Silva and Daniel Jost Brod. Two-Particle Scattering on Non-Translation Invariant Line Lattices. Quantum, 8: 1308, April 2024. ISSN 2521-327X. 10.22331/q-2024-04-04-1308. URL https://doi.org/10.22331/q-2024-04-04-1308. https://doi.org/10.22331/q-2024-04-04-1308 [19] John R. Taylor. Scattering Theory: The Quantum Theory of Nonrelativistic Collisions. John Wiley & Sons, Inc., New York, 1972. https://doi.org/10.1063/1.3128052. https://doi.org/10.1063/1.3128052 [20] Zhaohua Tian and Xue-Wen Chen. Passive and deterministic controlled-phase gate for single-photon wavepackets based on time-reversal symmetric photon transport, 2024. URL https://arxiv.org/abs/2312.10719. arXiv:2312.10719 [21] Françoise Tisseur and Karl Meerbergen. The quadratic eigenvalue problem. SIAM Review, 43, 08 2001. 10.1137/S0036144500381988. https://doi.org/10.1137/S0036144500381988 [22] Martin Varbanov and Todd A. Brun. Quantum scattering theory on graphs with tails. Phys. Rev. A, 80: 052330, 2009. 10.1103/PhysRevA.80.052330. https://doi.org/10.1103/PhysRevA.80.052330 [23] Martin Varbanov, Hari Krovi, and Todd A. Brun. Hitting time for the continuous quantum walk. Phys. Rev. A, 78: 022324, Aug 2008. 10.1103/PhysRevA.78.022324. URL https://doi.org/10.1103/PhysRevA.78.022324. https://doi.org/10.1103/PhysRevA.78.022324 [24] Shanshan Xu, Eden Rephaeli, and Shanhui Fan. Analytic properties of two-photon scattering matrix in integrated quantum systems determined by the cluster decomposition principle. Phys. Rev. Lett., 111: 223602, Nov 2013. 10.1103/PhysRevLett.111.223602. URL https://doi.org/10.1103/PhysRevLett.111.223602. https://doi.org/10.1103/PhysRevLett.111.223602Cited byCould not fetch Crossref cited-by data during last attempt 2026-03-23 08:29:19: Could not fetch cited-by data for 10.22331/q-2026-03-23-2038 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-03-23 08:29:19: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.