Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Improved quantum supersampling for quantum ray tracing

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

Ray tracing algorithm is a category of rendering algorithms that calculate pixel colors by simulating light rays in parallel. The quantum supersampling has achieved a quadratic speedup over classical Monte Carlo method, but its output image contains many detached abnormal noisy dots. In this paper, we improve quantum supersampling by replacing the QFT-based phase estimation in quantum supersampling with a robust quantum counting scheme. We do simulation experiments to show that the quantum ray tracing with improved quantum supersampling does perform better than classical path tracing algorithm as well as the original form of quantum supersampling.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Algorithm 1
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Data availability statement

The data that support the findings of this study available from the corresponding author upon reasonable request.

References

  1. Whitted, T.: An improved illumination model for shaded display. Commun. ACM 23, 343–349 (1980). https://doi.org/10.1145/358876.358882

    Article  Google Scholar 

  2. Cook, R.L., Porter, T., Carpenter, L.: Distributed ray tracing. Comput. Graph. 18, 137–145 (1984). https://doi.org/10.1145/800031.808590

    Article  Google Scholar 

  3. Kajiya, J.T.: The rendering equation. In: Proceedings of the 13th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH vol. 20, 143–150 (1986). https://doi.org/10.1145/15922.15902

  4. Haines, E., Akenine-Möller, T.: Ray Tracing Gems: High-Quality and Real-Time Rendering with DXR and Other APIs. Apress, New York (2019)

    Book  Google Scholar 

  5. Akenine-Mller, T., Haines, E., Hoffman, N.: Real-Time Rendering, 4th edn. A. K. Peters Ltd, Natick (2018)

    Book  Google Scholar 

  6. Zeng, Z., Liu, S., Yang, J., Wang, L., Yan, L.-Q.: Temporally reliable motion vectors for real-time ray tracing. Comput. Graph. Forum 40(2), 79–90 (2021). https://doi.org/10.1111/cgf.142616

    Article  Google Scholar 

  7. Schied, C., Kaplanyan, A., Wyman, C., Patney, A., Chaitanya, C.R.A., Burgess, J., Liu, S., Dachsbacher, C., Lefohn, A., Salvi, M.: Spatiotemporal variance-guided filtering: Real-time reconstruction for path-traced global illumination. In: Proceedings of High Performance Graphics. HPG ’17. Association for Computing Machinery, New York, NY, USA (2017). https://doi.org/10.1145/3105762.3105770

  8. Nielsen, M.A., Chuang, I.: Quantum computation and quantum information. Am. Assoc. Phys. Teach. 70, 558–559 (2002)

    ADS  Google Scholar 

  9. Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325 (1997). https://doi.org/10.1103/PhysRevLett.79.325

    Article  ADS  Google Scholar 

  10. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484–1509 (1997). https://doi.org/10.1137/S0097539795293172

    Article  MathSciNet  MATH  Google Scholar 

  11. Lanzagorta, M., Uhlmann, J.K.: Hybrid quantum-classical computing with applications to computer graphics. ACM SIGGRAPH 2005 Courses, SIGGRAPH 2005 (2005). https://doi.org/10.1145/1198555.1198723

  12. Caraiman, S.: Quantum computer graphics algorithms. Buletinul Institutului Politehnic din Iasi, Sectia Automatica si Calculatoare 62(4), 21–38 (2012)

    MathSciNet  MATH  Google Scholar 

  13. Johnston, E.R.: Quantum supersampling. ACM SIGGRAPH 2016 Talks (2016). https://doi.org/10.1145/2897839

  14. Shimada, N.H., Hachisuka, T.: Quantum coin method for numerical integration. Comput. Graph. Forum 39, 243–257 (2020). https://doi.org/10.1111/cgf.14015

    Article  Google Scholar 

  15. Abrams, D.S., Williams, C.P.: Fast quantum algorithms for numerical integrals and stochastic processes. arXiv (1999)

  16. Santos, L.P., Bashford-Rogers, T., Barbosa, J., Navrátil, P.: Towards quantum ray tracing (2022). https://doi.org/10.48550/arxiv.2204.12797

  17. Durr, C., Hoyer, P.: A quantum algorithm for finding the minimum. arXiv (1996)

  18. Giovannetti, V., Lloyd, S., Maccone, L.: Quantum random access memory. Phys. Rev. Lett. 100(16), 160501 (2008)

    Article  MathSciNet  MATH  ADS  Google Scholar 

  19. Suzuki, Y., Uno, S., Raymond, R., Tanaka, T., Onodera, T., Yamamoto, N.: Amplitude estimation without phase estimation. Quantum Inf. Process. (2019). https://doi.org/10.1007/s11128-019-2565-2

    Article  MATH  Google Scholar 

  20. Lu, X., Lin, H.: Unbiased quantum phase estimation. arXiv preprint arXiv:2210.00231 (2022)

  21. Feynman, R.P.: Simulating physics with computers. Int. J. Theor. Phys. 21(6), 467–488 (1982). https://doi.org/10.1007/BF02650179

    Article  MathSciNet  Google Scholar 

  22. Feynman, R.P.: Quantum mechanical computers. Found. Phys. 16(6), 507–531 (1986). https://doi.org/10.1007/BF01886518

    Article  MathSciNet  ADS  Google Scholar 

  23. Takahashi, Y., Tani, S., Kunihiro, N.: Quantum addition circuits and unbounded fan-out. Quantum Inf. Comput. 10, 872–890 (2009). https://doi.org/10.26421/qic10.9-10-12

    Article  MathSciNet  MATH  Google Scholar 

  24. Brassard, G., Hoyer, P., Tapp, A.: Quantum counting. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 1443 LNCS, pp. 820–831 (1998). https://doi.org/10.1007/BFb0055105

  25. Kitaev, A.Y.: Quantum measurements and the abelian stabilizer problem. arXiv: https://arxiv.org/abs/quant-ph/9511026v1 (1995)

  26. Mosca, M., Ekert, A.: The hidden subgroup problem and eigenvalue estimation on a quantum computer. In: NASA International Conference on Quantum Computing and Quantum Communications, pp. 174–188 (1998). Springer

  27. Dobšíček, M., Johansson, G., Shumeiko, V., Wendin, G.: Arbitrary accuracy iterative quantum phase estimation algorithm using a single ancillary qubit: A two-qubit benchmark. Phys. Rev. A 76(3), 030306 (2007)

    Article  ADS  Google Scholar 

  28. Dobšíček, M.: Quantum computing, phase estimation and applications. arXiv (2008). https://doi.org/10.48550/arxiv.0803.0909

  29. Brassard, G., Hoyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. Contemp. Math. 305, 53–74 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  30. Svore, K.M., Hastings, M.B., Freedman, M.: Faster phase estimation. Quantum Inf. Comput. 14, 306–328 (2013). https://doi.org/10.26421/qic14.3-4-7

    Article  MathSciNet  Google Scholar 

  31. Wiebe, N., Granade, C.: Efficient Bayesian phase estimation. Phys. Rev. Lett. 117, 010503 (2016). https://doi.org/10.1103/PHYSREVLETT.117.010503/FIGURES/5/MEDIUM

    Article  ADS  Google Scholar 

  32. Wie, C.R.: Simpler quantum counting. Quantum Inf. Comput. (2019). https://doi.org/10.26421/QIC19.11-12

  33. Aaronson, S., Rall, P.: Quantum approximate counting, simplified. In: Symposium on simplicity in algorithms, pp. 24–32 (2020). SIAM

  34. Grinko, D., Gacon, J., Zoufal, C., Woerner, S.: Iterative quantum amplitude estimation. NPJ Quantum Inf. 7, 1–6 (2021). https://doi.org/10.1038/s41534-021-00379-1

    Article  Google Scholar 

  35. Plekhanov, K., Rosenkranz, M., Fiorentini, M., Lubasch, M.: Variational quantum amplitude estimation. Quantum 6, 670 (2022). https://doi.org/10.22331/q-2022-03-17-670

    Article  Google Scholar 

  36. Arrighetti, W.: The academy color encoding system (aces): a professional color-management framework for production, post-production and archival of still and motion pictures. J. Imaging 3(4), 40 (2017)

    Article  Google Scholar 

  37. Fuchs, H., Kedem, Z.M., Naylor, B.F.: On visible surface generation by a priori tree structures. ACM SIGGRAPH Comput. Graph. 14, 124–133 (1980). https://doi.org/10.1145/965105.807481

    Article  Google Scholar 

  38. Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18, 509–517 (1975). https://doi.org/10.1145/361002.361007

    Article  MATH  Google Scholar 

  39. Hapala, M., Havran, V.: Review: Kd-tree traversal algorithms for ray tracing. Comput. Graph. Forum 30, 199–213 (2011). https://doi.org/10.1111/j.1467-8659.2010.01844.x

    Article  Google Scholar 

  40. Clark, J.H.: Hierarchical geometric models for visible surface algorithms. Commun. ACM 19, 547–554 (1976). https://doi.org/10.1145/360349.360354

    Article  MATH  Google Scholar 

Download references

Acknowledgements

This work is supported by the National Natural Science Foundation of China under Grant nos. 62272406, 61872316, and the National Key Research and Development Plan of China under Grant no. 2020YFB1708900.

Author information

Authors and Affiliations

  1. School of Mathematical Science, Zhejiang University, Hangzhou, 310027, Zhejiang, China

    Xi Lu & Hongwei Lin

Authors
  1. Xi Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hongwei Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hongwei Lin.

Ethics declarations

Conflict of interest

The authors report no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lu, X., Lin, H. Improved quantum supersampling for quantum ray tracing. Quantum Inf Process 22, 359 (2023). https://doi.org/10.1007/s11128-023-04114-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-023-04114-x

Keywords

Search

Navigation