CS Paper Radar

Exponential Quantum Memory Advantage for Late-Graph Smoothness and Spectral Estimation

Burhan Gülbahar

cs.IT quant-pheess.SP ·submitted 2026-11-16 18:00 UTC · v1
theory

Abstract

Graph signal processing tests how smoothly the decisions of next-generation massive sensor networks with $N$ nodes vary over their neighbour graph. Memory becomes the bottleneck when the neighbour graph arrives only after data erasure, a late-graph setting motivated by dispersed sensor networks and telemetry. We analyse three collection scenarios, reliable rounds, continuous broadcast and ordered capture, and test the Dirichlet energy $\mathcal E_G=\mathbf z^{\mathsf T}\mathbf L\mathbf z/N$ of the fused decision map $\mathbf z\in\{\pm1\}^N$, with late-graph Laplacian $\mathbf L$, against two thresholds. Hidden Matching uses $O(\log N)$ qubits on fused bits, but in reliable rounds and continuous broadcast, where nodes report $b$ sub-bits separately, a classical record buffer before it uses $O(N b)$ bits; classical methods need $Ω(\sqrt N)$ bits in the worst case. The recently introduced Quantum Oracle Sketching builds quantum oracles from random data streams without storing them. We combine coherent loading of separately reported sub-bits, exact in reliable rounds and by Quantum Oracle Sketching in continuous broadcast, with nonlinear fusion and Hidden Matching readout. The register count $R$ does not grow with $N$, and the memory is $O(\log N)$ logical qubits and classical bits, at fixed $b$, graph bounds, thresholds and error targets: an exponential memory advantage over every classical receiver and over Hidden Matching with that buffer. We prove unbiasedness in reliable rounds, preparation bounds in continuous broadcast, classical lower bounds and, for a planner-supplied multi-hop coefficient stream, spectral error bounds. Broadcast simulations match analytic averages at $N=1024$, without resolved bias growth up to $N=2^{20}$. Fault-tolerant hardware, gate rates and, in continuous broadcast, report counts remain open.

Comment
19 pages, 8 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds

cs.CC quant-ph ·2026-09-30 ·Paul Beame, Blake Holman, Niels Kornerup
theoryhot direction similarity 0.68
Abstract · 46 pages, submitted to QIP 2027. New version fixes the displayed abstract and makes some minor corrections to fix the parameters used in res…

Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an $Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ lower bound on the number of queries that a fully general quantum algorithm with at most $S$ qubits of memory requires to sort $n$ numbers from $[n^2]$. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family $H$ from $n$ bits to $m$ bits, almost all hash functions in $H$ require any algorithm with at most $S$ qubits of memory to make $Ω(nm/S)$ quantum queries to input $x$ in order to compute $h(x)$, even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing $h(x)$ with both $h$ and $x$ as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.

0.27

Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds

cs.DS quant-ph ·2026-10-05 ·Nadezhda Voronova
theory similarity 0.67
Abstract

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\le N^{1/2-δ}$ and every fixed $δ\in(0,1/2)$, even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through $r=Θ(\sqrt 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.

0.29

A Quantum Lower Bound for Triangle Finding

cs.DS quant-ph ·2026-11-04 ·Arjan Cornelissen, Amin Shiraz Gilani, Xingyu Zhou
theory similarity 0.65
Abstract · 37 pages

Triangle finding is a fundamental problem in graph theory that has played a central role in the development of quantum algorithmic techniques. For $N$-vertex graphs given by their adjacency matrices, a long line of work has improved the quantum query upper bound from $O(N^{3/2})$ to $O(N^{5/4})$. However, the best known lower bound has remained the elementary $Ω(N)$ bound obtained from unstructured search. We prove the first superlinear quantum query lower bound for triangle finding, showing that $Ω(N^{13/12})$ queries are necessary. Our result also implies the same lower bound for triangle detection and for detecting every fixed connected non-bipartite graph. The proof builds on the compressed oracle approach of Zhandry and the transfer approaches of Belovs. It compares the computation on graphs with a planted triangle to the computation on random graphs conditioned to be triangle-free, through a map on the input registers that almost commutes with every query. We average over local changes to the input while preserving its distribution, through a procedure known as conditional resampling. Our main technical contribution is a set of estimates that let us control the query error under this averaging, despite the dependence introduced by conditioning a dense graph to be triangle-free.

0.48

Planted Cliques and Quantum Symmetry-Adapted Measurements

cs.CC quant-ph ·2026-09-30 ·Vojtech Havlicek, Jordan Docter, Subhash Khot
theory similarity 0.65
Abstract · 21 pages, no figures. Revised it to improve clarity and readability. VH takes responsibility for the previous submission prepared under a ti…

We study how quantum encodings and symmetry-adapted measurements preserve information for planted-clique detection from one classical graph. For $k=\lfloor n^{1/2-\varepsilon}\rfloor$, with fixed $0<\varepsilon<1/2$, detection is statistically possible but conjectured hard for polynomial-time classical algorithms. For a compact binary phase encoding, we prove that constant-advantage detection requires $Ω(n^{1+2\varepsilon}\ln^2 n)$ copies of the phase state of the same graph, even under arbitrary joint measurements. In the large-copy limit, the optimal decision rule thresholds the total number of $k$-cliques in the graph and its complement, but this characterization provides no efficient detector. We therefore explore measurements guided by the symmetries of the input distributions, starting with the efficient Schur transform on the full graph register. We show that weak Schur sampling, which measures only the representation label, depends only on edge count and has vanishing distinguishing power in this regime. When the label and multiplicity registers are discarded, the remaining quantum states are almost perfectly distinguishable. We show that the support of the planted state occupies only a vanishing fraction of the graph Hilbert space. Any subspace containing it still permits near-perfect detection if its relative dimension also vanishes. This gives us freedom to choose a subspace that is easier to measure. We propose exploring subgroup isotypic measurements to find such subspaces. Whether they can yield an efficient detector remains open. Finally, we show that a single supplied coherent quantum sample permits efficient detection, yielding a conditional computational separation from one classical sample under quantum planted-clique hardness.

0.32

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

cs.CR quant-ph ·2026-10-05 ·Keshav Bhateja, Mehdi Esmaili, Atul Mantri
benchmark similarity 0.64
Abstract

Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes by their ideal probabilities. We study what a high XEB score certifies about an untrusted quantum device. In the quantum query model, we show that the honest sampler's ideal score acts as a Tsirelson bound for efficient devices and certified randomness. First, exceeding the ideal score by a constant requires $Ω(N^{1/3})$ queries for the Haar and Fourier oracle ensembles with $N$ outcomes, and this bound is tight; this proves an earlier conjecture for Haar-random states and extends it to Fourier sampling. Second, for Fourier sampling and for Haar-random states accessed through the canonical state-preparation oracle, the $n$-bit output of a device that makes polynomially many queries and scores within $o(1)$ of the ideal score has $n-O(\log n)$ bits of smooth min-entropy, even against an adversary who is entangled with the device and later learns the oracle; this is nearly optimal. As a corollary, sampling the collision distribution, which is proportional to the square of the ideal distribution, has query complexity $Θ(N^{1/3})$, and a coherent version of the same algorithm approximately prepares quantum Hadamard products of states with uniform amplitude magnitudes. Both lower bounds rest on progress measures that bound the excess over the ideal score and increase only slightly with each query. For Fourier sampling the measure is the norm of the coherent amplitudes for removing pairs in a purification of the random function, combining the polynomial method with the compressed oracle technique; for Haar-random states it is the square root of the average level in an expansion in Dirichlet orthogonal polynomials, controlled by an exact identity for the effect of one observation.

0.09

Quantum Computing for Network Security Classification: Near-Term Classification and Long-Term Memory Efficiency

cs.AI quant-phcs.LG ·2026-09-29 ·Yuqing Li, Poonam Bala Nehru, Yunpeng Zhang, Danindu Gammanpilage, Xin Jin +2 more
similarity 0.63
Abstract

Quantum computing has already been explored in several network-security applications. However, how quantum computing may contribute to network-security classification in both the near term and the longer term has not been systematically discussed. This paper studies this question through two complementary experiments. First, we evaluate near-term quantum-kernel support vector machines (SVMs) on practical network-security classification tasks and compare them with classical SVM baselines on KDD Cup 1999, CICIDS2017, and BoT-IoT. Across these runs, quantum kernels are competitive. They can match or improve classical baselines in some settings, while classical RBF kernels remain stronger in others. This suggests that near-term quantum-kernel methods should be evaluated as practical, dataset-dependent alternatives to classical kernels rather than as uniformly superior replacements. Second, we use quantum oracle sketching (QOS) to study a longer-term memory advantage for classification with streaming classical samples. In QOS, samples are processed online and used to incrementally construct an approximate quantum oracle, which provides coherent query access for downstream quantum algorithms without retaining the entire dataset. Under the QOS-inspired machine-size estimate, comparable accuracy corresponds to a substantially smaller effective memory-size proxy than explicit sparse/QRAM-style storage. Compared with a simple streaming proxy, the result is more nuanced because aggressive feature filtering can make the streaming dimension small. This suggests that the long-term value of quantum computing for network-security classification may lie in memory-efficient data access rather than immediate runtime speedup. Together, these experiments show how quantum computing may contribute to network-security classification from near-term classification performance and longer-term memory efficiency.

0.08

Quantum Private Information Retrieval on Forests

cs.IT cs.CRcs.NIeess.SP+1 ·2026-11-02 ·Mohamed Nomeir, Sennur Ulukus
theory similarity 0.63
Abstract

We consider the problem of graph private information retrieval (PIR) in the quantum setting. We focus on a specific type of graphs, namely the forest graphs. A forest graph is a union of disjoint trees. We consider the quantum setting where all the servers share an entangled state. Each server is allowed to send only one qudit per retrieval round. We design a scheme for the forest graphs that achieves the rate of $\frac{3}{N}$. The scheme uses a GHZ state as the initial entangled state between the servers prior to the scheme initiation. We compare our scheme with the only work done in the literature that considered the quantum setting of graph PIR. We show that our scheme is more efficient in this setting. We derive the quantum capacity for the case of $G=3K_2$, which is equal to $4/6$. $G=3K_2$ is a special case of the forest graph. We design a scheme that is specialized for this graph, achieving a rate equal to $4/6$ and provide the corresponding matching upper bound, establishing it as the capacity.

0.23

Exponential quantum advantages for decoded quantum interferometry in the streaming setting

cs.CC quant-phcs.DS ·2026-10-01 ·Kewen Wu, Guangxu Yang
theoryhot direction similarity 0.63
Abstract

Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025). For a natural optimization problem, known as optimal polynomial intersection (OPI), it achieves approximation guarantees in regimes where all known classical algorithms require exponential time. Besides time, space is another central resource: storing and manipulating a massive input can be very challenging, especially when logical qubits carry substantial fault-tolerant implementation overhead. This motivates the following question: does DQI yield quantum advantages in memory, and can we prove it unconditionally? We give an affirmative answer to this question in the streaming setting. In particular, we consider a natural generalization of OPI using Hermite interpolation and Hasse derivatives, which asks for a low-degree polynomial satisfying as many constraints on its values and derivatives as possible. As a concrete example, we show [Quantum efficiency.] An adaptation of the DQI algorithm produces a polynomial satisfying $93\%$ of the constraints; moreover, it only reads the input stream in one pass, uses polylogarithmic space, and has polylogarithmic computation time per stream entry. [Classical hardness.] Any classical algorithm that produces an answer satisfying just $76\%$ of the constraints requires polynomial space, even if it can read the input stream with polynomially many passes and can use unlimited time. Our result provides a complete tradeoff curve for the tunable parameters, and implies that DQI has provable quantum advantages for the original OPI problem.

0.51