We develop a perfectly distributable quantum-classical streaming algorithm that processes signed edges to efficiently estimate the counts of triangles of diverse signed configurations in the single pass edge stream. Our approach introduces a quantum sketch register for processing the signed edge stream, together with measurement operators for query-pair calls in the quantum estimator, while a complementary classical estimator accounts for triangles not captured by the quantum procedure. This hybrid design yields a polynomial space advantage over purely classical approaches, extending known results from unsigned edge stream data to the signed setting. We quantify the lack of balance on random signed graph instances, showcasing how the classical and hybrid algorithms estimate balance in practice.
We develop a perfectly distributable quantum-classical streaming algorithm that processes signed edges to efficiently estimate the counts of triangles of diverse signed configurations in the single pass edge stream. Our approach introduces a quantum sketch register for processing the signed edge stream, together with measurement operators for query-pair calls in the quantum estimator, while a complementary classical estimator accounts for triangles not captured by the quantum procedure. This hybrid design yields a polynomial space advantage over purely classical approaches, extending known results from unsigned edge stream data to the signed setting. We quantify the lack of balance on random signed graph instances, showcasing how the classical and hybrid algorithms estimate balance in practice.
How can random order change the role of quantum memory in streaming? Later classical input can restore the usefulness of a quantum state consumed by earlier queries. We call this replenishment.
We construct an artificial problem based on Hidden Matching, with repeated coordinate data and online matching requests. It admits a one-pass quantum algorithm using polylogarithmic space in uniformly random order, but unconditionally requires polynomial space both classically in random order and quantumly when all updates precede the requests.
To prove the quantum lower bound, we strengthen the consumability bounds of Gilboa, Jain, and McClean for Multiple Hidden Matching. Without prior entanglement, any quantum encoding supporting r independent matching requests requires Ω(r) qubits for r≤N1/2−δ and every fixed δ∈(0,1/2), even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through r=Θ(N).
We also adapt Kallaugher's triangle-counting algorithm to uniformly random streams in which every edge is repeated equally often. Rebuilding the quantum sketch and resampling the classical estimator improve its expected-space bound in suitable parameter regimes.
Finally, we extend the robust Noisy Gap Cycle framework of Assadi and Sundaresan to quantum streaming. A quantum communication lower bound for Block Hidden XOR yields an Ω(n) space lower bound in random edge order for large enough cycles, with consequences for several graph problems.
Thus random order can enable replenishment of small quantum representations, while substantial space requirements persist for other tasks.
Data streaming, in which a large dataset is received as a "stream" of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA `06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input. We give a one-pass quantum streaming algorithm for one of the best studied problems in classical graph streaming - the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.
Triangles capture higher-order structures in graphs and are fundamental to applications such as clustering and network analysis. To enable efficient use of such structures at scale, we study the problem of triangle cut sparsification, which aims to reduce the graph size while approximately preserving triangle counts across every cut. We investigate quantum algorithms for this problem, using triangle listing as our main technical ingredient. In particular, we present a quantum algorithm for triangle listing that, for a graph with n vertices, m edges, and t triangles, runs in time Tq-list=O(min(n5/4t7/12+n7/6t7/9,m+m3/4t1/2,n3/2t1/2)), improving upon the best known classical bounds over a broad range of parameters. Our algorithm is based on a heavy-light vertex partition and an extension of triangle detection via quantum walks and Grover search. Leveraging this result, we design a quantum algorithm for constructing ε-triangle cut sparsifiers of size O(n/ε2) in time O(Tq-list+mn/ε). Finally, we demonstrate applications to clustering algorithms based on triangle-related measures and prove a lower bound of Ω(n/ε2) on the size of any ε-triangle cut sparsifiers.
Data streaming, in which a large dataset is received as a “stream” of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA '06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input. We give a one-pass quantum streaming algorithm for one of the best-studied problems in classical graph streaming-the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.
We study one-way quantum communication lower bounds for search problems. Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of a quantum protocol jointly.
As applications of our method, we establish the first tight quantum lower bounds for two fundamental search problems in some natural parameter regimes: collision finding and triangle finding. For collision finding, we prove a tight Ω(N1/4) one-way quantum communication lower bound. Previously, the best-known quantum communication lower bound for collision finding was Ω(N1/12) due to Göös and Jain (RANDOM 2022), and no stronger bound was known even under the one-way restriction. For triangle finding in graph streams, we prove a one-pass quantum streaming space lower bound of Ω(ΔV) for graphs with m edges, Θ(m) triangles, and constant ΔE, where ΔV and ΔE denote the maximum number of triangles sharing a common vertex and edge, respectively, under the condition that 1≤ΔV≤m2/3. This constitutes the first nontrivial quantum space lower bound in this regime, matching the classical upper bound of Jayaram and Kallaugher (RANDOM 2021) up to logarithmic factors. Notably, our method also recovers the classical lower bound of Kallaugher and Price (SODA 2017) through an entirely different argument, avoiding their Boolean-Hidden-Matching reduction that breaks down for quantum protocols.
Data streaming, in which a large dataset is received as a stream of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA `06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input.
We give a one-pass quantum streaming algorithm for one of the best studied problems in classical graph streaming - the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.