Quantum Distributed Complexity of Set Disjointness on a Line
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
Given \( x,y\in \lbrace 0,1\rbrace ^n \) , Set Disjointness consists in deciding whether \( x_i=y_i=1 \) for some index \( i \in [n] \) . We study the problem of computing this function in a distributed computing scenario in which the inputs \( x \) and \( y \) are given to the processors at the two extremities of a path of length \( d \) . Each vertex of the path has a quantum processor that can communicate with each of its neighbours by exchanging \( \operatorname{O}(\log n) \) qubits per round. We are interested in the number of rounds required for computing Set Disjointness with constant probability bounded away from \( 1/2 \) . We call this problem “Set Disjointness on a Line”. Set Disjointness on a Line was introduced by Le Gall and Magniez [ 14 ] for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path is severely limited. More precisely, their bound applies only when the local memory of each intermediate processor consists of \( \operatorname{O}(\log n) \) qubits. In this work, we prove an unconditional lower bound of \( \widetilde{\Omega }\big (\sqrt [3]{n d^2}+\sqrt {n} \, \big) \) rounds for Set Disjointness on a Line with \( d + 1 \) processors. This is the first non-trivial lower bound when there is no restriction on the memory used by the processors. The result gives us a new lower bound of \( \widetilde{\Omega } \big (\sqrt [3]{n\delta ^2}+\sqrt {n} \, \big) \) on the number of rounds required for computing the diameter \( \delta \) of any \( n \) -node network with quantum messages of size \( \operatorname{O}(\log n) \) in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. In this model, an algorithm computing a bi-variate function \( f \) (such as Set Disjointness) has access to the inputs \( x \) and \( y \) through two separate oracles \( {\mathcal {O}}_x \) and \( {\mathcal {O}}_y \) , respectively. The restriction is that the algorithm is required to alternately make \( d \) queries to \( {\mathcal {O}}_x \) and \( d \) queries to \( {\mathcal {O}}_y \) , with input-independent computation in between queries. The model reflects a “switching delay” of \( d \) queries between a “round” of queries to \( x \) and the following “round” of queries to \( y \) . The information-theoretic technique we use for deriving the round lower bound for Set Disjointness on a Line also applies to the number of rounds in this query model. We provide an algorithm for Set Disjointness in this query model with round complexity that matches the round lower bound stated above, up to a polylogarithmic factor. This presents a barrier for obtaining a better round lower bound for Set Disjointness on the Line. At the same time, it hints at the possibility of better communication protocols for the problem.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.001 |
| Science and technology studies | 0.001 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.001 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it