“Quantum Ray Marching for Reformulating Light Transport Simulation” by Mosier, McGuire and Hachisuka
Conference:
Type(s):
Title:
- Quantum Ray Marching for Reformulating Light Transport Simulation
Session/Category Title:
- \nabla f = ?
Presenter(s)/Author(s):
Abstract:
The use of quantum computers in computer graphics has gained interest in recent years, especially for the application to rendering. The current state of the art in quantum rendering relies on Grover’s search for finding ray intersections in $O(\sqrt{M})$ for $M$ primitives. This quantum approach is faster than the naive approach of $O(M)$ but slower than $O(\log M)$ of modern ray tracing with an acceleration data structure. Furthermore, this quantum ray tracing method is fundamentally limited to casting one ray at a time, leaving quantum rendering scales for the number of rays the same as non-quantum algorithms. We present a new quantum rendering method, quantum ray marching, based on the reformulation of ray marching as a quantum random walk. Our work is the first complete quantum rendering pipeline capable of light transport simulation and remains asymptotically faster than non-quantum counterparts. Our quantum ray marching can trace an exponential number of paths with polynomial cost, and it leverages quantum numerical integration to converge in $O(1/N)$ for $N$ estimates as opposed to non-quantum $O(1/\sqrt{N})$. These properties led to first quantum rendering that is asymptotically faster than non-quantum Monte Carlo rendering. We numerically tested our algorithm by rendering 2D and 3D scenes.
References:
[1]
Dorit Aharonov. 2003. A Simple Proof that Toffoli and Hadamard are Quantum Universal. arxiv:quant-ph/0301040 [quant-ph]
[2]
Yakir Aharonov, Luiz Davidovich, and Nicim Zagury. 1993. Quantum Random Walks. Phys. Rev. A 48 (Aug 1993), 1687–1690. Issue 2. https://doi.org/10.1103/PhysRevA.48.1687
[3]
Rashid Ahmad, Uzma Sajjad, and Muhammad Sajid. 2020. One-dimensional Quantum Walks with a Position-Dependent Coin. Communications in Theoretical Physics 72, 6 (2020), 65101–.
[4]
Carolina Alves, Luís Paulo Santos, and Thomas Bashford-Rogers. 2019. A Quantum Algorithm for Ray Casting Using an Orthographic Camera. In 2019 International Conference on Graphics and Interaction (ICGI) (2019-11). IEEE, Faro, Portugal, 56–63. https://doi.org/10.1109/ICGI47575.2019.8955061
[5]
Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. 1995. Elementary Gates for Quantum Computation. Phys. Rev. A 52 (Nov 1995), 3457–3467. Issue 5. https://doi.org/10.1103/PhysRevA.52.3457
[6]
Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu. 2023. Quantum Algorithm for Estimating Volumes of Convex Bodies. ACM Transactions on Quantum Computing 4, 3, Article 20 (may 2023), 60 pages. https://doi.org/10.1145/3588579
[7]
D. Deutsch. 1989. Quantum Computational Networks. Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences 425, 1868 (1989), 73–90. http://www.jstor.org/stable/2398494
[8]
Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. 2008. Quantum Random Access Memory. Phys. Rev. Lett. 100 (Apr 2008), 160501. Issue 16. https://doi.org/10.1103/PhysRevLett.100.160501
[9]
Lov K. Grover. 1996. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (Philadelphia, Pennsylvania, USA) (STOC ’96). Association for Computing Machinery, New York, NY, USA, 212–219. https://doi.org/10.1145/237814.237866
[10]
Eric R. Johnston. 2016. Quantum Supersampling. In ACM SIGGRAPH 2016 Talks (2016-07-24) (SIGGRAPH ’16). Association for Computing Machinery, New York, NY, USA, 1. https://doi.org/10.1145/2897839.2927422
[11]
Eric R. Johnston, Nic Harrigan, and Mercedes Gimeno-Segovia. 2019. Programming Quantum Computers: Essential Algorithms and Code Samples. O’Reilly Media, Sebastopol, California, USA. https://www.oreilly.com/library/view/programming-quantum-computers/9781492039679/
[12]
Karthik S. Joshi, S. K. Srivatsa, and R. Srikanth. 2018. Path Integral Approach to One-dimensional Discrete-time Quantum Walk. arxiv:1803.00448 [quant-ph]
[13]
James T. Kajiya. 1986. The Rendering Equation. Comput. Graph. (Proc. SIGGRAPH) 20, 4 (1986), 143–150.
[14]
Marco Lanzagorta and Jeffrey K. Uhlmann. 2005. Hybrid Quantum-Classical Computing with Applications to Computer Graphics. In ACM SIGGRAPH 2005 Courses (2005-07-31) (SIGGRAPH ’05). Association for Computing Machinery, New York, NY, USA, 2–es. https://doi.org/10.1145/1198555.1198723
[15]
Christiane Lemieux. 2009. Monte Carlo and Quasi-Monte Carlo Sampling. Springer New York, New York, USA. https://books.google.ca/books?id=wj5OyydZ5bkC
[16]
Yongming Li and Ariel Neufeld. 2023. Quantum Monte Carlo algorithm for solving Black-Scholes PDEs for high-dimensional option pricing in finance and its proof of overcoming the curse of dimensionality. arxiv:2301.09241 [quant-ph]
[17]
Xi Lu and Hongwei Lin. 2022a. A Framework for Quantum Ray Tracing. arxiv:2203.15451 [quant-ph]
[18]
Xi Lu and Hongwei Lin. 2022b. Improved Quantum Supersampling for Quantum Ray Tracing. arxiv:2208.05171 [quant-ph]
[19]
Kouhei Nakaji. 2020. Faster amplitude estimation. Quantum Information and Computation 20, 13&14 (nov 2020), 1109–1123. https://doi.org/10.26421/qic20.13-14-2
[20]
Patrick Rebentrost, Brajesh Gupt, and Thomas R Bromley. 2018. Quantum computational finance: Monte Carlo pricing of financial derivatives. Physical Review A 98, 2 (2018), 022321.
[21]
Luís Paulo Santos, Thomas Bashford-Rogers, João Barbosa, and Paul Navrátil. 2022. Towards Quantum Ray Tracing. arxiv:2204.12797 [cs.GR]
[22]
Naoharu H. Shimada and Toshiya Hachisuka. 2020. Quantum Coin Method for Numerical Integration. Computer graphics forum 39, 6 (2020), 243–257.
[23]
Ingo Wald and Vlastimil Havran. 2006. On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N). In 2006 IEEE Symposium on Interactive Ray Tracing. IEEE, Salt Lake City, UT, USA, 61–69. https://doi.org/10.1109/RT.2006.280216
[24]
Shengbin Wang, Zhimin Wang, Guolong Cui, Lixin Fan, Shangshang Shi, Ruimin Shang, Wendong Li, Zhiqiang Wei, and Yongjian Gu. 2020. Quantum Amplitude Arithmetic. arxiv:2012.11056 [quant-ph]
[25]
Manuela Weigold, Johanna Barzen, Frank Leymann, and Marie Salm. 2022. Data Encoding Patterns for Quantum Computing. In Proceedings of the 27th Conference on Pattern Languages of Programs (Virtual Event) (PLoP ’20). The Hillside Group, USA, Article 2, 11 pages.
[26]
Turner Whitted. 1979. An Improved Illumination Model for Shaded Display. SIGGRAPH Comput. Graph. 13, 2 (aug 1979), 14. https://doi.org/10.1145/965103.807419
[27]
Stefan Woerner and Daniel J Egger. 2019. Quantum risk analysis. npj Quantum Information 5, 1 (2019), 15.
[28]
Yiheng Xie, Towaki Takikawa, Shunsuke Saito, Or Litany, Shiqin Yan, Numair Khan, Federico Tombari, James Tompkin, Vincent sitzmann, and Srinath Sridhar. 2022. Neural Fields in Visual Computing and Beyond. Computer Graphics Forum 41, 2 (2022), 641–676. https://doi.org/10.1111/cgf.14505 arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.14505
