How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing

1. John Kallaugher 
2. Ojas Parekh 
3. Nadezhda Voronova 

Sign up to identify related papers:

1. Advice Coins for Classical and Quantum Computation. In Automata, Languages and Programming, volume 6755, pages 61–72. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011.
2. The space complexity of approximating the frequency moments. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, pages 20–29, New York, NY, USA, 1996. Association for Computing Machinery.
3. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’02, pages 623–632, Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics.
4. How hard is counting triangles in the streaming model? In Automata, Languages, and Programming, pages 244–254. Springer, 2013.
5. Optimal streaming approximations for all boolean Max-2CSPs and Max-kSAT. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 330–341. IEEE, 2020.
6. Graham Cormode. Data sketching. Communications of the ACM, 60(9):48–55, 2017.
7. Probabilistic counting algorithms for data base applications. Journal of Computer and System Sciences, 31(2):182–209, 1985.
8. The power of quantum fourier sampling. arXiv preprint arXiv:1507.05592, 2015.
9. Exponential separation for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput., 38(5):1695–1708, 2008.
10. Learning with finite memory. The Annals of Mathematical Statistics, 41(3):765–782, 1970.
11. Quantum Chebyshev’s Inequality and Applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 69:1–69:16, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
12. An optimal algorithm for triangle counting in the stream. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), volume 207 of LIPIcs, pages 11:1–11:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
13. The space complexity of recognizing well- parenthesized expressions in the streaming model: The index function revisited. IEEE Transactions on Information Theory, 60(10):6646–6668, October 2014.
14. John Kallaugher. A quantum advantage for a natural streaming problem. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 897–908, 2022.
15. A hybrid sampling scheme for triangle counting. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1778–1797. SIAM, 2017.
16. The quantum and classical streaming complexity of quantum and classical Max-Cut. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 498–506. IEEE, 2022.
17. Exponential quantum space advantage for approximating maximum directed cut in the streaming model. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1805–1815, 2024.
18. François Le Gall. Exponential separation of quantum and classical online space complexity. In Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, SPAA ’06, pages 67–73, New York, NY, USA, July 2006. Association for Computing Machinery.
19. Andrew McGregor. Graph stream algorithms: a survey. SIGMOD Record, 43(1):9–20, 2014.
20. Ashley Montanaro. The quantum complexity of approximating the frequency moments. Quantum Info. Comput., 16(13–14):1169–1190, October 2016.
21. Robert Morris. Counting large numbers of events in small registers. Commun. ACM, 21(10):840–842, oct 1978.
22. Quantum computation and quantum information. Cambridge university press, 2010.
23. Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303–332, 1999.
24. Noah G Singer. Oblivious algorithms for the Max-k𝑘kitalic_kAND problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2023.
25. Improved streaming algorithms for maximum directed cut via smoothed snapshots. In 2023 IEEE 64nd Annual Symposium on Foundations of Computer Science (FOCS), 2023.
26. An efficient quantum algorithm for preparation of uniform quantum superposition states. Quantum Information Processing, 23(2):38, 2024.
27. Mark M Wilde. Quantum information theory. Cambridge University Press, 2 edition, 2017.