Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy

Chenghua Liu; Guangxu Yang; Minbo Gao; Tianyi Zhang

Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy

T0 review · 0 major / 4 minor · reviewed 2026-07-10 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A matrix-discrepancy method yields the first tight one-way quantum lower bounds for collision finding and streaming triangle finding.

desk verdict Tight one-way quantum lower bounds for two search problems via a clean matrix-discrepancy method that actually works. read the letter →

arxiv 2607.08517 v1 pith:TIW72M3O submitted 2026-07-09 quant-ph

Minbo Gao , Chenghua Liu , Guangxu Yang , Tianyi Zhang This is my paper

classification quant-ph

keywords one-wayquantumcommunicationsearchproblemsmatrixdiscrepancycollisionfindingtrianglestreamingPOVMpackingnoncommutativeKhintchine

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Search problems allow many correct answers, so standard quantum lower-bound tools that reduce everything to a single yes/no bit lose power. This paper treats Bob’s entire family of measurement operators as one object and bounds their joint correlation with valid witnesses by a matrix-discrepancy quantity. The resulting technique produces an Ω(N^{1/4}) one-way quantum communication lower bound for bipartite collision finding, matching the classical birthday-paradox protocol, and an Ω(√Δ_V) one-pass quantum streaming lower bound for triangle finding on a natural hard family of graphs. In that regime the bound recovers the classical space lower bound without relying on a Boolean-Hidden-Matching reduction that fails for quantum protocols. The same packing-and-concentration argument therefore shows that quantum communication and streaming enjoy no asymptotic advantage for these two search tasks in the stated parameter ranges.

What carries the argument

Matrix discrepancy of a centered PSD packing: after the Bob-side validity factors are absorbed into operators P_ω that sum to at most the identity, the protocol’s advantage is at most the expected operator norm of ∑(X_ω−EX_ω)P_ω, which is controlled by Khintchine plus a tailored concentration bound on the largest grouped block.

What would settle it

Exhibit either a one-way quantum protocol for ColFind_{N,N+Ω(N)} that uses o(N^{1/4}) qubits and still succeeds with constant probability on uniform inputs, or a one-pass quantum streaming algorithm that finds a triangle on the hard family with o(√Δ_V) qubits of space.

Watch

Extended reading notes

Core claim

One-way quantum protocols for search relations can be controlled directly by converting Bob’s POVM into a positive-semidefinite packing, subtracting the trivial guessing baseline, and bounding the remaining centered operator by a matrix-discrepancy estimate obtained from non-commutative Khintchine and matrix-concentration inequalities. Applied to collision finding this yields a tight Ω(N^{1/4}) qubit lower bound; applied to streaming triangle finding it yields an Ω(√Δ_V) space lower bound matching the best classical upper bound up to logs.

Load-bearing premise

Every successful protocol must induce a packing of positive-semidefinite operators whose grouped norms are forced by the problem’s combinatorial structure to obey the matrix-concentration bounds used in the discrepancy estimate.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This paper closes a real gap: the first tight Ω(N^{1/4}) one-way quantum communication lower bound for bipartite collision finding (improving Göös–Jain’s Ω(N^{1/12})), and the first nontrivial quantum streaming lower bound Ω(√Δ_V) for triangle finding that matches the classical √Δ_V term in the natural regime T=Θ(m), Δ_E=O(1), Δ_V≤m^{2/3}. Both are obtained by the same reusable technique rather than ad-hoc reductions.

What is new is the measurement-discrepancy approach. Search problems produce whole POVMs, not a single acceptance operator. They absorb Bob-side validity into a PSD packing, center out the trivial baseline, and bound the remaining advantage by matrix Khintchine plus matrix Chernoff/Bernstein under the packing constraints forced by POVM normalization. The collision proof uses a random bipartition + bucket operators; the triangle proof uses the hard distribution with random bijections and a streaming-to-communication reduction. Both arguments are written out completely (Lemmas 3.1–3.2, 4.4–4.6, Theorems 1.1–1.2). The method also recovers the classical Kallaugher–Price √Δ_V lower bound without Boolean Hidden Matching, which is useful because BHM collapses quantumly.

The stress-test concern about packings that might evade the concentration bounds does not hold: every protocol induces a packing that satisfies exactly the hypotheses of those lemmas (P_ω ⪰ 0, ∑P_ω ⪯ I, and the pointwise bounds). Residual risk is ordinary human-proof error, not a conceptual hole. Soft spots are minor and already flagged by the authors: the triangle result is only for one-pass and a restricted parameter regime; multi-pass and the full classical parameterization remain open. Citations look solid and non-circular.

This is for people working on quantum communication complexity, streaming lower bounds, or matrix concentration methods. It deserves a serious referee. I would engage with it and expect it to be cited.

Referee Report

0 major / 4 minor

Summary. The paper develops a matrix-discrepancy method for one-way quantum communication lower bounds on search relations. Bob's POVM is converted into a PSD packing by absorbing Bob-side validity factors; after subtracting the trivial baseline, the success probability is controlled by the expected operator norm of a centered random matrix sum under packing constraints, which is bounded via noncommutative Khintchine and matrix concentration. The method yields two applications: a tight Ω(N^{1/4}) one-way quantum lower bound for bipartite collision finding ColFind_{N,M} when M>N (Theorem 1.1), improving the prior Ω(N^{1/12}) bound, and an Ω(√Δ_V) one-pass quantum streaming space lower bound for triangle finding on a hard family with m edges, T=Θ(m), Δ_E=O(1) and 1≤Δ_V≤m^{2/3} (Theorem 1.2), matching the classical upper bound of Jayaram–Kallaugher up to logs and recovering the classical Kallaugher–Price lower bound without Boolean Hidden Matching.

Significance. The contribution is substantial. Search problems with many valid outputs have resisted standard quantum lower-bound techniques; the measurement-discrepancy framework gives a direct, packing-based route that applies uniformly to both applications. Closing the quantum gap for collision finding to the birthday-paradox upper bound, and obtaining the first nontrivial quantum streaming lower bound that recovers the classical √Δ_V dependence in a regime where Boolean Hidden Matching is unavailable, are clear advances. The proofs are fully written from first principles (PSD packing extraction, centering, decoupling, matrix Khintchine/Chernoff), and the method also recovers a known classical lower bound by an independent argument. Residual risk is ordinary human-proof error rather than a conceptual hole.

minor comments (4)

In the technical overview and in §3.2 the packing is written both as ∑P_ω ⪯ I and, in one place, with a ⪰ symbol; the intended relation is the upper bound forced by POVM normalization. A single consistent notation would avoid momentary confusion.
Lemma 3.2 and Lemma 4.6 invoke matrix Chernoff/Bernstein with a universal constant C or K; a one-line pointer to the precise form used (e.g., Tropp's matrix Chernoff) would make the numerical factors easier to track.
In the streaming reduction (proof of Theorem 1.2), the construction of q disjoint copies and dummy edges is clear, but a short remark that the algorithm's public randomness is shared and not charged to space would match the model stated in §2.1.
Typographical: 'Göös' appears with inconsistent diacritics in the abstract and introduction; 'eO' / 'eΩ' notation for polylog factors is introduced late and could be defined once at first use.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the lower bounds are derived from first-principles matrix concentration under POVM packing constraints forced by any protocol.

full rationale

The paper's central claims (Theorems 1.1–1.2) follow a self-contained derivation chain: any one-way quantum protocol induces a success operator H_a whose expectation is at most E∥H_a∥ (by Tr(ρH)≤∥H∥); Bob-side validity is absorbed into a PSD packing {P_ω} satisfying exactly the hypotheses of the matrix-Khintchine and matrix-Chernoff lemmas (P_ω⪰0, ∑P_ω⪯I, and the pointwise bounds P_{i,j}⪯I/√N or P_{x,i,z,y}⪯I/s); the centered discrepancy G_a is then bounded by those standard inequalities, yielding the communication/space lower bounds. Prior results (Göös–Jain, Kallaugher–Price, Jayaram–Kallaugher, etc.) appear only for comparison of upper/lower bounds or for the known classical streaming upper bound; none is load-bearing for the new quantum discrepancy argument, and none is a self-citation that already encodes the target Ω(N^{1/4}) or Ω(√Δ_V) quantity. There is no fitted parameter renamed as a prediction, no self-definitional loop, no uniqueness theorem imported from the authors, and no ansatz smuggled via citation. The derivation is therefore independent of its inputs by construction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The work is pure mathematics. It rests on standard operator inequalities and concentration tools plus the usual modeling assumptions of one-way quantum communication and one-pass quantum streaming; no free parameters are fitted and no new physical entities are postulated.

assumptions (5)

standard math Self-adjoint matrix Khintchine inequality (Lemma 2.2 / Tropp, Vershynin) controlling the expected spectral norm of a Rademacher sum of fixed self-adjoint matrices.
Invoked repeatedly to bound centered operator sums after packing (Lemmas 3.1, 4.4).
standard math Matrix Chernoff / Bernstein tail bounds for independent PSD summands with bounded operator norm.
Used to control the largest bucket / block norm after averaging over right-side labels or random bijections (Lemmas 3.2, 4.6).
domain assumption One-way quantum protocols without shared entanglement; Bob’s strategy is an arbitrary POVM on the received density matrix.
Standard model stated in Definition 2.7; success probability is the expected trace against valid POVM elements.
domain assumption One-pass insertion-only quantum streaming model with space equal to the number of qubits retained between edge arrivals.
Used for the streaming-to-communication reduction that produces TripTri(r,s).
ad hoc to paper Hard distribution for triangles: random bijections F_i, random 0-1 matrix A, random bijection C, with parameters √s ≤ r ≤ s and disjoint copies to reach m edges.
Definition 4.1 and Proposition 4.3; chosen so that T=Θ(m), Δ_E≤1, Δ_V=Θ(s) while remaining hard for quantum protocols.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy." pith.science (2026). https://pith.science/paper/TIW72M3O

@misc{pith2026260708517,
  author       = {Pith},
  title        = {Pith review of: Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TIW72M3O}},
  note         = {Machine review of arXiv:2607.08517}
}

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 $\Omega(N^{1/4})$ one-way quantum communication lower bound. Previously, the best-known quantum communication lower bound for collision finding was $\Omega(N^{1/12})$ due to G\"o\"os 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 $\Omega\left(\sqrt{\Delta_V}\right)$ for graphs with $m$ edges, $\Theta(m)$ triangles, and constant $\Delta_E$, where $\Delta_V$ and $\Delta_E$ denote the maximum number of triangles sharing a common vertex and edge, respectively, under the condition that $1\le \Delta_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.

Figures

Figures reproduced from arXiv: 2607.08517 by the authors.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

98 extracted references · 98 canonical work pages

[1]

, title =

Ambainis, Andris and Nayak, Ashwin and Ta-Shma, Amnon and Vazirani, Umesh V. , title =. Journal of the ACM , volume =. 2002 , doi =

work page 2002
[2]

Quantum Cryptanalysis of Hash and Claw-Free Functions , booktitle =

Brassard, Gilles and H. Quantum Cryptanalysis of Hash and Claw-Free Functions , booktitle =. 1998 , doi =

work page 1998
[3]

Quantum Lower Bound for the Collision Problem

Aaronson, Scott , title =. Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2002) , pages =. 2002 , doi =. quant-ph/0111102 , archivePrefix =

work page Pith review arXiv 2002
[4]

Quantum lower bounds for the collision and the element distinctness problems

Shi, Yaoyun , title =. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002) , pages =. 2002 , doi =. quant-ph/0112086 , archivePrefix =

work page Pith review arXiv 2002
[5]

Quantum walk algorithm for element distinctness

Ambainis, Andris , title =. SIAM Journal on Computing , volume =. 2007 , doi =. quant-ph/0311001 , archivePrefix =

work page Pith review arXiv 2007
[6]

, title =

Bar-Yossef, Ziv and Kumar, Ravi and Sivakumar, D. , title =. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) , pages =

work page 2002
[7]

Bar-Yossef, Ziv and Jayram, T. S. and Kerenidis, Iordanis , title =. SIAM Journal on Computing , volume =. 2008 , doi =

work page 2008
[8]

Advances in Cryptology -- CRYPTO 2018, Part II , editor =

Bauer, Balthazar and Farshim, Pooya and Mazaheri, Sogol , title =. Advances in Cryptology -- CRYPTO 2018, Part II , editor =. 2018 , doi =

work page 2018

Show all 98 references

[9]

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , pages =

Beame, Paul and Whitmeyer, Michael , title =. 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , pages =. 2025 , doi =

2025
[10]

and Chakrabarti, Amit , title =

Bera, Suman K. and Chakrabarti, Amit , title =. 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) , pages =. 2017 , doi =

2017
[11]

Automata, Languages, and Programming , editor =

Braverman, Vladimir and Ostrovsky, Rafail and Vilenchik, Dan , title =. Automata, Languages, and Programming , editor =. 2013 , doi =. 1304.1458 , archivePrefix =

2013 arXiv
[12]

Theoretical Computer Science , volume =

Cormode, Graham and Jowhari, Hossein , title =. Theoretical Computer Science , volume =. 2017 , doi =

2017
[13]

, title =

Gasarch, William I. , title =. 2022 , howpublished =

2022
[14]

SIAM Journal on Computing , volume =

Gavinsky, Dmitry and Kempe, Julia and Kerenidis, Iordanis and Raz, Ran and de Wolf, Ronald , title =. SIAM Journal on Computing , volume =. 2008 , doi =. quant-ph/0611209 , archivePrefix =

2008 arXiv
[15]

Approximation, Randomization, and Combinatorial Optimization

G. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) , pages =. 2022 , doi =. 2208.00029 , archivePrefix =

2022 arXiv
[16]

36th Computational Complexity Conference (CCC 2021) , pages =

Itsykson, Dmitry and Riazanov, Artur , title =. 36th Computational Complexity Conference (CCC 2021) , pages =. 2021 , doi =

2021
[17]

Approximation, Randomization, and Combinatorial Optimization

Jayaram, Rajesh and Kallaugher, John , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) , pages =. 2021 , doi =. 2105.01785 , archivePrefix =

2021 arXiv
[18]

2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages =

Kallaugher, John , title =. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2022 , doi =. 2106.04633 , archivePrefix =

2021 arXiv
[19]

2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages =

Kallaugher, John and Kapralov, Michael and Price, Eric , title =. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2018 , doi =. 1808.04995 , archivePrefix =

2018 arXiv
[20]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) , pages =

Kallaugher, John and Price, Eric , title =. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) , pages =. 2017 , doi =. 1610.02066 , archivePrefix =

2017 arXiv
[21]

and Zhou, Samson , title =

Kapralov, Michael and Musipatla, Amulya and Tardos, Jakab and Woodruff, David P. and Zhou, Samson , title =. arXiv preprint arXiv:2107.02578 , year =

arXiv
[22]

1991 , doi =

Ledoux, Michel and Talagrand, Michel , title =. 1991 , doi =

1991
[23]

Lust-Piquard, Fran. In. Comptes Rendus de l'Acad
[24]

Non-Commutative Khintchine and Paley Inequalities , journal =

Lust-Piquard, Fran. Non-Commutative Khintchine and Paley Inequalities , journal =. 1991 , doi =

1991
[25]

, title =

Tropp, Joel A. , title =. Foundations and Trends in Machine Learning , volume =. 2015 , doi =. 1501.01571 , archivePrefix =

2015 arXiv
[26]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024) , pages =

Yang, Guangxu and Zhang, Jiapeng , title =. Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024) , pages =. 2024 , doi =

2024
[27]

SIAM Journal on Computing , volume =

Itai, Alon and Rodeh, Michael , title =. SIAM Journal on Computing , volume =. 1978 , doi =

1978
[28]

Algorithmica , volume =

Alon, Noga and Yuster, Raphael and Zwick, Uri , title =. Algorithmica , volume =. 1997 , doi =

1997
[29]

Ryan , title =

Vassilevska Williams, Virginia and Williams, R. Ryan , title =. Journal of the ACM , volume =. 2018 , doi =

2018
[30]

Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011) , pages =

Roditty, Liam and Vassilevska Williams, Virginia , title =. Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011) , pages =. 2011 , doi =. 1104.2882 , archivePrefix =

2011 arXiv
[31]

Quantum Algorithms for the Triangle Problem , journal =

Magniez, Fr. Quantum Algorithms for the Triangle Problem , journal =. 2007 , doi =. quant-ph/0310134 , archivePrefix =

2007 arXiv
[32]

Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing , booktitle =

Lee, Troy and Magniez, Fr. Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing , booktitle =. 2013 , doi =. 1210.1014 , archivePrefix =

2013 arXiv
[33]

Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments , booktitle =

Le Gall, Fran. Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments , booktitle =. 2014 , doi =. 1407.0085 , archivePrefix =

2014 arXiv
[34]

SIAM Journal on Discrete Mathematics , volume =

Alon, Noga and Kaufman, Tali and Krivelevich, Michael and Ron, Dana , title =. SIAM Journal on Discrete Mathematics , volume =. 2008 , doi =

2008
[35]

and Porat, Ely and R

Ngo, Hung Q. and Porat, Ely and R. Worst-Case Optimal Join Algorithms , booktitle =. 2012 , doi =. 1203.1952 , archivePrefix =

2012 arXiv
[36]

and Itzkovitz, Shalev and Kashtan, Nadav and Chklovskii, Dmitri B

Milo, Ron and Shen-Orr, Shai S. and Itzkovitz, Shalev and Kashtan, Nadav and Chklovskii, Dmitri B. and Alon, Uri , title =. Science , volume =. 2002 , doi =

2002
[37]

Experimental and Efficient Algorithms (WEA 2005) , editor =

Schank, Thomas and Wagner, Dorothea , title =. Experimental and Efficient Algorithms (WEA 2005) , editor =. 2005 , doi =

2005
[38]

Theoretical Computer Science , volume =

Latapy, Matthieu , title =. Theoretical Computer Science , volume =. 2008 , doi =. cs/0609116 , archivePrefix =

2008 arXiv
[39]

Proceedings of the 20th International Conference on World Wide Web (WWW 2011) , pages =

Suri, Siddharth and Vassilvitskii, Sergei , title =. Proceedings of the 20th International Conference on World Wide Web (WWW 2011) , pages =. 2011 , doi =

2011
[40]

Triangle Finding and Listing in

Izumi, Taisuke and Le Gall, Fran. Triangle Finding and Listing in. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC 2017) , pages =. 2017 , doi =. 1705.09061 , archivePrefix =

2017 arXiv
[41]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019) , pages =

Chang, Yi-Jun and Pettie, Seth and Zhang, Hengjie , title =. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019) , pages =. 2019 , doi =

2019
[42]

37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) , pages =

Izumi, Taisuke and Le Gall, Fran. 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) , pages =. 2020 , doi =. 1908.11488 , archivePrefix =

2020 arXiv
[43]

Kremer, Ilan , title =
[44]

, title =

Razborov, Alexander A. , title =. Izvestiya: Mathematics , volume =. 2003 , doi =. quant-ph/0204025 , archivePrefix =

2003 arXiv
[45]

Random Structures & Algorithms , volume =

Linial, Nati and Shraibman, Adi , title =. Random Structures & Algorithms , volume =. 2009 , doi =

2009
[46]

Foundations and Trends in Theoretical Computer Science , volume =

Lee, Troy and Shraibman, Adi , title =. Foundations and Trends in Theoretical Computer Science , volume =. 2009 , doi =

2009
[47]

, title =

Sherstov, Alexander A. , title =. SIAM Journal on Computing , volume =. 2011 , doi =. 0906.4291 , archivePrefix =

2011 arXiv
[48]

Transactions of the American Mathematical Society , volume =

Spencer, Joel , title =. Transactions of the American Mathematical Society , volume =
[49]

and Raghavendra, Prasad and Shetty, Abhishek , title =

Hopkins, Samuel B. and Raghavendra, Prasad and Shetty, Abhishek , title =. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022) , pages =. 2022 , doi =. 2110.10099 , archivePrefix =

2022 arXiv
[50]

Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022) , pages =

Dadush, Daniel and Jiang, Haotian and Reis, Victor , title =. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022) , pages =. 2022 , doi =. 2111.03171 , archivePrefix =

2022 arXiv
[51]

and Boedihardjo, March T

Bandeira, Afonso S. and Boedihardjo, March T. and van Handel, Ramon , title =. Inventiones Mathematicae , volume =. 2023 , doi =. 2108.06312 , archivePrefix =

2023 arXiv
[52]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023) , pages =

Bansal, Nikhil and Jiang, Haotian and Meka, Raghu , title =. Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023) , pages =. 2023 , doi =. 2208.11286 , archivePrefix =

2023 arXiv
[53]

IEEE Transactions on Information Theory , volume =

Ahlswede, Rudolf and Winter, Andreas , title =. IEEE Transactions on Information Theory , volume =. 2002 , doi =. quant-ph/0012127 , archivePrefix =

2002 arXiv
[54]

, title =

Tropp, Joel A. , title =. Foundations of Computational Mathematics , volume =. 2012 , doi =. 1004.4389 , archivePrefix =

2012 arXiv
[55]

Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003) , pages =

Jain, Rahul and Radhakrishnan, Jaikumar and Sen, Pranab , title =. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003) , pages =. 2003 , doi =. quant-ph/0303138 , archivePrefix =

2003 arXiv
[56]

Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2015) , pages =

Touchette, Dave , title =. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2015) , pages =. 2015 , doi =. 1404.3733 , archivePrefix =

2015 arXiv
[57]

SIAM Journal on Computing , volume =

Klauck, Hartmut , title =. SIAM Journal on Computing , volume =. 2007 , doi =. quant-ph/0106160 , archivePrefix =

2007 arXiv
[58]

Quantum Information & Computation , volume =

Shi, Yaoyun and Zhu, Yufan , title =. Quantum Information & Computation , volume =. 2009 , eprint =

2009
[59]

Automata, Languages and Programming (ICALP 2010) , series =

Lee, Troy and Zhang, Shengyu , title =. Automata, Languages and Programming (ICALP 2010) , series =. 2010 , doi =. 1003.1443 , archivePrefix =

2010 arXiv
[60]

32nd Computational Complexity Conference (CCC 2017) , pages =

Anshu, Anurag and Ben-David, Shalev and Garg, Ankit and Jain, Rahul and Kothari, Robin and Lee, Troy , title =. 32nd Computational Complexity Conference (CCC 2017) , pages =. 2017 , doi =

2017
[61]

Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2012) , pages =

Fiorini, Samuel and Massar, Serge and Pokutta, Sebastian and Tiwary, Hans Raj and de Wolf, Ronald , title =. Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2012) , pages =. 2012 , doi =

2012
[62]

Lifts of Convex Sets and Cone Factorizations , journal =

Gouveia, Jo. Lifts of Convex Sets and Cone Factorizations , journal =. 2013 , doi =. 1111.3164 , archivePrefix =

2013 arXiv
[63]

Positive Semidefinite Rank , journal =

Fawzi, Hamza and Gouveia, Jo. Positive Semidefinite Rank , journal =. 2015 , doi =. 1407.4095 , archivePrefix =

2015 arXiv
[64]

Mathematical Programming , volume =

Lee, Troy and Wei, Zhaohui and de Wolf, Ronald , title =. Mathematical Programming , volume =. 2017 , doi =. 1407.4308 , archivePrefix =

2017 arXiv
[65]

Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012) , pages =

Samuel Fiorini and Serge Massar and Sebastian Pokutta and Hans Raj Tiwary and Ronald de Wolf , title =. Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012) , pages =. 2012 , doi =

2012
[66]

Lifts of Convex Sets and Cone Factorizations , journal =

Jo. Lifts of Convex Sets and Cone Factorizations , journal =. 2013 , doi =

2013
[67]

Positive Semidefinite Rank , journal =

Hamza Fawzi and Jo. Positive Semidefinite Rank , journal =. 2015 , doi =

2015
[68]

Mathematical Programming , volume =

Troy Lee and Zhaohui Wei and Ronald de Wolf , title =. Mathematical Programming , volume =. 2017 , doi =

2017
[69]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS 1999) , pages =

Ashwin Nayak , title =. Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS 1999) , pages =. 1999 , doi =

1999
[70]

Journal of Computer and System Sciences , volume =

Iordanis Kerenidis and Ronald de Wolf , title =. Journal of Computer and System Sciences , volume =. 2004 , doi =

2004
[71]

Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005) , series =

Stephanie Wehner and Ronald de Wolf , title =. Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005) , series =. 2005 , doi =

2005
[72]

SIAM Journal on Computing , volume =

Hartmut Klauck , title =. SIAM Journal on Computing , volume =. 2007 , doi =

2007
[73]

Proceedings of the 32nd Computational Complexity Conference (CCC 2017) , series =

Ashwin Nayak and Dave Touchette , title =. Proceedings of the 32nd Computational Complexity Conference (CCC 2017) , series =. 2017 , doi =

2017
[74]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2022) , pages =

John Kallaugher and Ojas Parekh , title =. Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2022) , pages =. 2022 , doi =

2022
[75]

A hypercontractive inequality for matrix-valued functions with applications to quantum computing and

Ben-Aroya, Avraham and Regev, Oded and de Wolf, Ronald , booktitle=. A hypercontractive inequality for matrix-valued functions with applications to quantum computing and. 2008 , organization=

2008
[76]

Matrix hypercontractivity, streaming algorithms and

Arunachalam, Srinivasan and Doriguello, Joao F , journal=. Matrix hypercontractivity, streaming algorithms and. 2024 , publisher=

2024
[77]

The Quantum and Classical Streaming Complexity of Quantum and Classical

Kallaugher, John and Wang, Aidan , booktitle=. The Quantum and Classical Streaming Complexity of Quantum and Classical. 2022 , organization=

2022
[78]

Proceedings of the thirty-fourth annual ACM symposium on Theory of computing (STOC) , pages=

Quantum lower bound for the collision problem , author=. Proceedings of the thirty-fourth annual ACM symposium on Theory of computing (STOC) , pages=
[79]

Advances in Cryptology -- CRYPTO 2018 , pages=

Combiners for Backdoored Random Oracles , author=. Advances in Cryptology -- CRYPTO 2018 , pages=. 2018 , organization=

2018
[80]

IEEE Transactions on Information Theory , volume=

Quantum distribution testing , author=. IEEE Transactions on Information Theory , volume=. 2011 , publisher=

2011
[81]

SIAM Journal on Computing , volume=

Quantum algorithms for the triangle problem , author=. SIAM Journal on Computing , volume=. 2007 , publisher=

2007
[82]

36th Computational Complexity Conference (CCC 2021) , pages=

Proof complexity of natural formulas via communication arguments , author=. 36th Computational Complexity Conference (CCC 2021) , pages=. 2021 , organization=

2021
[83]

Triangle Finding and Listing in CONGEST Networks , year =

Izumi, Taisuke and Le Gall, Fran. Triangle Finding and Listing in CONGEST Networks , year =. doi:10.1145/3087801.3087811 , booktitle =

doi
[84]

2012 , isbn =

Dolev, Danny and Lenzen, Christoph and Peled, Shir , title =. 2012 , isbn =. doi:10.1007/978-3-642-33651-5_14 , booktitle =

2012 doi
[85]

arXiv preprint arXiv:1904.08914 , year=

Quantum lower bounds for approximate counting via Laurent polynomials , author=. arXiv preprint arXiv:1904.08914 , year=

1904 arXiv
[86]

2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

Query-to-communication lifting for BPP , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2017 , organization=

2017
[87]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

Resolving matrix spencer conjecture up to poly-logarithmic rank , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=
[88]

International Colloquium on Automata, Languages, and Programming , pages=

A direct sum theorem in communication complexity via message compression , author=. International Colloquium on Automata, Languages, and Programming , pages=. 2003 , organization=

2003
[89]

SIAM Journal on Computing , volume=

Near-optimal bounds on the bounded-round quantum communication complexity of disjointness , author=. SIAM Journal on Computing , volume=. 2018 , publisher=

2018
[90]

2025 , isbn =

Huang, Mi-Ying (Miryam) and Mao, Xinyu and Wang, Shuo and Yang, Guangxu and Zhang, Jiapeng , title =. 2025 , isbn =. doi:10.4230/LIPIcs.CCC.2025.33 , booktitle =

2025 doi
[91]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

Quantum communication advantage in tfnp , author=. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=
[92]

Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages=

Exponential separations for one-way quantum communication complexity, with applications to cryptography , author=. Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages=
[93]

2025 Symposium on Simplicity in Algorithms (SOSA) , pages=

How to design a quantum streaming algorithm without knowing anything about quantum computing , author=. 2025 Symposium on Simplicity in Algorithms (SOSA) , pages=. 2025 , organization=

2025
[94]

On Quantum Chosen-Ciphertext Attacks and Learning with Errors

Alagic, Gorjan and Jeffery, Stacey and Ozols, Maris and Poremba, Alexander. On Quantum Chosen-Ciphertext Attacks and Learning with Errors. Leibniz Int. Proc. Inf. 2019. doi:10.4230/LIPIcs.TQC.2019.1

2019 doi
[95]

Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages=

Lower bounds on the size of semidefinite programming relaxations , author=. Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages=
[96]

Exponential

Doriguello, Jo. Exponential. LIPIcs, Volume 158, TQC 2020 , volume =. doi:10.4230/LIPICS.TQC.2020.1 , isbn =

2020 doi
[97]

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) , pages =

Jeffery, Stacey and Le Gall, Fran. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) , pages =. 2016 , volume =. doi:10.4230/LIPIcs.MFCS.2016.54 , annote =

2016 doi
[98]

High-Dimensional Probability: An Introduction with Applications in Data Science , shorttitle =

Vershynin, Roman , year = 2018, series =. High-Dimensional Probability: An Introduction with Applications in Data Science , shorttitle =. doi:10.1017/9781108231596 , isbn =

2018 doi

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.

[1] [1]

, title =

Ambainis, Andris and Nayak, Ashwin and Ta-Shma, Amnon and Vazirani, Umesh V. , title =. Journal of the ACM , volume =. 2002 , doi =

work page 2002

[2] [2]

Quantum Cryptanalysis of Hash and Claw-Free Functions , booktitle =

Brassard, Gilles and H. Quantum Cryptanalysis of Hash and Claw-Free Functions , booktitle =. 1998 , doi =

work page 1998

[3] [3]

Quantum Lower Bound for the Collision Problem

Aaronson, Scott , title =. Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2002) , pages =. 2002 , doi =. quant-ph/0111102 , archivePrefix =

work page Pith review arXiv 2002

[4] [4]

Quantum lower bounds for the collision and the element distinctness problems

Shi, Yaoyun , title =. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002) , pages =. 2002 , doi =. quant-ph/0112086 , archivePrefix =

work page Pith review arXiv 2002

[5] [5]

Quantum walk algorithm for element distinctness

Ambainis, Andris , title =. SIAM Journal on Computing , volume =. 2007 , doi =. quant-ph/0311001 , archivePrefix =

work page Pith review arXiv 2007

[6] [6]

, title =

Bar-Yossef, Ziv and Kumar, Ravi and Sivakumar, D. , title =. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) , pages =

work page 2002

[7] [7]

Bar-Yossef, Ziv and Jayram, T. S. and Kerenidis, Iordanis , title =. SIAM Journal on Computing , volume =. 2008 , doi =

work page 2008

[8] [8]

Advances in Cryptology -- CRYPTO 2018, Part II , editor =

Bauer, Balthazar and Farshim, Pooya and Mazaheri, Sogol , title =. Advances in Cryptology -- CRYPTO 2018, Part II , editor =. 2018 , doi =

work page 2018