Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
Pages 1805 - 1815
Abstract
While the search for quantum advantage typically focuses on speedups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work has shown such advantages for data stream problems, in which elements arrive and must be processed sequentially without random access, but these have been restricted to specially-constructed problems Le Gall, SPAA ‘06 or polynomial advantage Kallaugher, FOCS ‘21. We show an exponential quantum space advantage for the maximum directed cut problem. This is the first known exponential quantum space advantage for any natural streaming problem. This also constitutes the first unconditional exponential quantum resource advantage for approximating a discrete optimization problem in any setting.
Our quantum streaming algorithm 0.4844-approximates the value of the largest directed cut in a graph stream with n vertices using polylog(n) space, while previous work by Chou, Golovnev, and Velusamy FOCS ’20 implies that obtaining an approximation ratio better than 4/9 ≈ 0.4444 requires Ω(√n) space for any classical streaming algorithm. Our result is based on a recent O(√n) space classical streaming approach by Saxena, Singer, Sudan, and Velusamy FOCS ’23, with an additional improvement in the approximation ratio due to recent work by Singer APPROX ’23.
References
[1]
Noga Alon, Yossi Matias, and Mario Szegedy. 1996. The Space Complexity of Approximating the Frequency Moments. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC ’96). Association for Computing Machinery, New York, NY, USA. 20–29. isbn:0897917855 https://doi.org/10.1145/237814.237823
[2]
Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. 2002. 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). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. 623–632. isbn:0-89871-513-X http://dl.acm.org/citation.cfm?id=545381.545464
[3]
Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick. 2022. Separating MAX 2-AND, MAX DI-CUT and MAX CUT. arXiv preprint arXiv:2212.11191.
[4]
Vladimir Braverman, Rafail Ostrovsky, and Dan Vilenchik. 2013. How hard is counting triangles in the streaming model? In Automata, Languages, and Programming. Springer, 244–254.
[5]
Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy. 2020. Optimal streaming approximations for all boolean Max-2CSPs and Max-kSAT. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). 330–341.
[6]
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028.
[7]
Uriel Feige and Shlomo Jozeph. 2015. Oblivious algorithms for the maximum directed cut problem. Algorithmica, 71 (2015), 409–428.
[8]
Philippe Flajolet. 1985. Approximate counting: a detailed analysis. BIT Numerical Mathematics, 25, 1 (1985), 113–134.
[9]
Philippe Flajolet and G. Nigel Martin. 1985. Probabilistic counting algorithms for data base applications. J. Comput. System Sci., 31, 2 (1985), 182–209. issn:0022-0000 https://doi.org/10.1016/0022-0000(85)90041-8
[10]
Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. 2008. Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography. SIAM J. Comput., 38, 5 (2008), 1695–1708.
[11]
Rahul Jain and Ashwin Nayak. 2014. The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited. IEEE Transactions on Information Theory, 60, 10 (2014), Oct., 6646–6668. issn:1557-9654 https://doi.org/10.1109/TIT.2014.2339859
[12]
Rajesh Jayaram and John Kallaugher. 2021. 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) (LIPIcs, Vol. 207). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 11:1–11:11.
[13]
John Kallaugher. 2022. A Quantum Advantage for a Natural Streaming Problem. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). 897–908.
[14]
John Kallaugher and Ojas Parekh. 2022. The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). 498–506.
[15]
John Kallaugher, Ojas Parekh, and Nadezhda Voronova. 2023. Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model. arXiv preprint arXiv:2311.14123.
[16]
Michael Kapralov and Dmitry Krachun. 2019. An Optimal Space Lower Bound for Approximating MAX-CUT. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019). Association for Computing Machinery, New York, NY, USA. 277–288. isbn:9781450367059 https://doi.org/10.1145/3313276.3316364
[17]
Michael Lewin, Dror Livnat, and Uri Zwick. 2002. Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems. In International Conference on Integer Programming and Combinatorial Optimization. 67–82.
[18]
Robert Morris. 1978. Counting Large Numbers of Events in Small Registers. Commun. ACM, 21, 10 (1978), oct, 840–842. issn:0001-0782 https://doi.org/10.1145/359619.359627
[19]
Ashwin Nayak and Dave Touchette. 2017. Augmented Index and Quantum Streaming Algorithms for DYCK(2). In Proceedings of the 32nd Computational Complexity Conference (CCC ’17). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, DEU. Article 23, 21 pages. isbn:9783959770408
[20]
Prasad Raghavendra. 2008. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the fortieth annual ACM symposium on Theory of computing. 245–254.
[21]
Lee Rhodes, Kevin Lang, Alexander Saydakov, Edo Liberty, and Justin Thaler. 2013. DataSketches: A library of stochastic streaming algorithms.
[22]
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, and Santhoshini Velusamy. 2023. Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots. In 2023 IEEE 64nd Annual Symposium on Foundations of Computer Science (FOCS).
[23]
Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, and Santhoshini Velusamy. 2023. Streaming complexity of CSPs with randomly ordered constraints. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 4083–4103. https://doi.org/10.1137/1.9781611977554.ch156
[24]
Peter W Shor. 1999. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41, 2 (1999), 303–332.
[25]
Noah G Singer. 2023. Oblivious Algorithms for the Max-kAND Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023).
Index Terms
- Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
Recommendations
Integrable quantum computation
Integrable quantum computation is defined as quantum computing via the integrable condition, in which two-qubit gates are either nontrivial unitary solutions of the Yang---Baxter equation or the Swap gate (permutation). To make the definition clear, in ...
Contextuality Supplies the Magic for Quantum Computation
ISMVL '15: Proceedings of the 2015 IEEE 45th International Symposium on Multiple-Valued LogicWe know that quantum mechanics enables the performance of computational and cryptographic tasks that are impossible (or impracticable) using only classical physics. It seems natural to examine manifestations of inherently quantum behaviour as potential ...
Visualization of the Quantum Fourier Transform Using a Quantum Computer Simulator
The quantum Fourier transform (QFT) is a key subroutine of quantum algorithms for factoring and simulation and is the heart of the hidden-subgroup problem, the solution of which is expected to lead to the development of new quantum algorithms. The QFT ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2024
2049 pages
ISBN:9798400703836
DOI:10.1145/3618260
- General Chairs:
- Bojan Mohar,
- Igor Shinkar,
- Program Chair:
- Ryan O'Donnell
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 June 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Sandia National Laboratories
- NSF (National Science Foundation)
Conference
STOC '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Upcoming Conference
STOC '25
- Sponsor:
- sigact
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 173Total Downloads
- Downloads (Last 12 months)173
- Downloads (Last 6 weeks)40
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in