Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy

• URL: http://arxiv.org/abs/2607.08517v1
• Date: Thu, 09 Jul 2026 14:11:09 GMT
• Title: Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
• Abstract summary: We study one-way quantum communication lower bounds for search problems.<n>For collision finding, we prove a tight $(N1/4)$ one-way quantum communication lower bound.<n>For triangle finding, we prove a one-pass quantum streaming space lower bound of $left(sqrt_Vright)$ for graphs with $m$ edges, $(m)$ triangles, and constant $_E$.
• Score: 4.843542453440025
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $Ω(N^{1/4})$ one-way quantum communication lower bound. Previously, the best-known quantum communication lower bound for collision finding was $Ω(N^{1/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 $Ω\left(\sqrt{Δ_V}\right)$ 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\le Δ_V\le m^{2/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.

Related papers

• Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid [31.45779401617503]
  Knaster-Tarski fixed-point theorem states that every monotone function over a complete lattice has a fixed point.<n>We prove an $(klog n)$ quantum query lower bound for finding a fixed point of a monotone function on $[n]k$, using the nonnegative spectral adversary method.
  arXiv  Detail & Related papers  (2026-09-03T13:06:12Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• Purest Quantum State Identification [14.22473588576799]
  We introduce the purest quantum state identification, which can be used to improve the accuracy of quantum computation and communication.<n>For incoherent strategies, we derive the first adaptive algorithm achieving error probability $expleft(- Omegaleft(fracN H_1log(K) 2nfracright)$, fundamentally improving quantum property learning.
  arXiv  Detail & Related papers  (2025-02-20T07:42:16Z)
• Rank lower bounds on non-local quantum computation [0.0]
  A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single round of communication and shared entanglement.<n>We study two classes of NLQC, $f$-routing and $f$-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification.
  arXiv  Detail & Related papers  (2024-02-28T19:00:09Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Lower Bounds by Sample-to-Query Lifting [33.82353457014144]
  We propose a new method for proving quantum query lower bounds by a quantum sample-to-query lifting theorem.<n>We provide unified proofs for some known lower bounds, including those for phase/amplitude estimation and Hamiltonian simulation.
  arXiv  Detail & Related papers  (2023-08-03T14:41:49Z)
• Approximate degree lower bounds for oracle identification problems [19.001036556917818]
  We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.
  arXiv  Detail & Related papers  (2023-03-07T14:30:28Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• The NISQ Complexity of Collision Finding [2.9405711598281536]
  A fundamental primitive in modern cryptography, collision-resistant hashing ensures there is no efficient way to find inputs that produce the same hash value. Quantum adversaries now require full-scale computers equipped with the power of NISQ. In this paper, we investigate three different models for NISQ algorithms achieve tight bounds for all of them.
  arXiv  Detail & Related papers  (2022-11-23T13:55:28Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.