{"id":"d90b932c-d376-4e85-a7d2-b4752c4cac1d","arxiv_id":"2506.07724","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves matching upper and lower bounds for distributed quantum sampling, but the lower bound is invalid when the total database size is small relative to the per-element capacity.","lead":"Quantum sampling from a database split across machines is studied, with two new algorithms and a claimed optimality proof. The optimality claim fails for sparse databases, where Grover search gives a strictly better bound.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower bound's hard-input construction fails when M is small relative to kappa, so the claimed Omega(sqrt(nu N/M)) optimality is false; e.g., M=1, nu=N, Grover uses O(sqrt(N)) queries.","rationale":"The reader's weakest_assumption identifies precisely the flaw in the lower-bound proof: Definition 5.4 requires an average multiplicity M_k/m_k >= beta*kappa_k on machine k, but when the total number of elements M is small, no input can meet this condition. I agree. This is the single load-bearing point because the paper's main advertised contribution is optimality (Theorems 5.1 and 5.2, Theorem 1.1). The upper-bound algorithms may be correct, but they are only optimal if the matching lower bound holds for the same parameters, including the public capacity nu. The paper explicitly says that for unknown kappa_j, one may use nu; the proof's 'put all elements on machine k' construction is valid only when M >= beta*nu, so the lower bound is not established for sparse databases. The flaw is not merely a missing constant: a flag-based Grover algorithm prepares the sampling state for M=1 in O(sqrt(N)) queries, whereas the claimed bound with kappa=nu=N is Omega(N). Thus the central optimality claim is false as stated. No other concern is needed; the upper bound is not at issue. Since the reader's verdict is REJECT and this concern supports it, the verdict should remain unchanged.","tokens_in":20657,"tokens_out":15316,"duration_ms":177388,"concrete_test":"Fix n=1, N=10^4, M=1, nu=10^4, kappa_1=10^4, and let c_x=1 for an unknown x. Run the standard amplitude-amplification algorithm: prepare H|0>|0>, then repeat: O, phase on flag register =1, O^dagger, and the Grover diffusion. Track the fidelity to |x> after each iteration. This 2-dimensional simulation is exact. It should reach F>9/16 in about ceil(pi/4*sqrt(N)) ~ 79 iterations, i.e., ~158 oracle queries. Theorem 5.1 predicts Omega(sqrt(kappa_1*N/M)) = Omega(10^4) queries; the gap of ~2 orders of magnitude refutes the lower bound as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central optimality claim rests on Theorems 5.1 and 5.2. Their proof uses hard inputs (Definition 5.4) requiring M_k/m_k >= beta*kappa_k on machine k. In the proof of Theorem 5.1, for the case M < beta^2*kappa_k*N/16, the authors assert that 'we can put all of the elements to the k-th machine to construct the input T satisfying the hard input conditions.' This construction works only if M_k/m_k = M/m_k >= beta*kappa_k. When M is small, say M=1 and kappa_k=nu>1/beta, the ratio is 1, which cannot be a constant fraction of kappa_k. Thus no hard input exists and Lemma 5.7 cannot be instantiated. Since the theorem states a lower bound for all inputs with max multiplicity at most nu, and the paper explicitly says to use nu for unknown kappa_j, the lower bound is unjustified in the sparse regime. This is not a mere proof gap: the claimed bound is actually false. Take n=1, M=1, N large, nu=N, kappa_1=nu. The lower bound is Omega(sqrt(kappa_1 N/M)) = Omega(N). But a flag-based Grover search using the additive oracle O|i,s> = |i,(s+c_i) mod (nu+1)> with c_i=1 for one unknown i prepares |x> with fidelity >9/16 in O(sqrt(N)) sequential queries (each iteration uses O and O^dagger, so 2 queries per iteration). Since O(sqrt(N)) is asymptotically smaller than N, the claimed optimality is false. The upper-bound algorithm is not optimal unless a density condition (e.g., M = Omega(nu)) is added, which the paper does not state.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces distributed quantum sampling in an oblivious communication model, where each machine maintains a multiplicity-counting oracle and a coordinator aims to prepare the quantum sampling state. It proposes a sequential algorithm using O(n sqrt(nu N/M)) queries and a parallel algorithm using O(sqrt(nu N/M)) parallel queries, and claims both are optimal via adversary-based lower bounds. The algorithmic constructions are elegant and appear correct as reductions to amplitude amplification. However, the central optimality claim is not supported: the lower bound proof relies on hard inputs that need not exist when the total database size M is small, and the advertised lower bound in terms of the public capacity nu is actually false in the sparse regime.","tokens_in":21041,"tokens_out":17309,"duration_ms":219698,"significance":"If the optimality claims were correct, the paper would establish a tight distributed analogue of the centralized quantum sampling barrier and give a clean model for distributed quantum databases. The upper-bound algorithms are simple, well-motivated, and correctly reduce the problem to amplitude amplification, which is a genuine strength. The adversarial lower bound is the main contribution, though, and it fails as stated: the proof cannot instantiate its hard inputs when M is small relative to nu, and a concrete single-marked-element instance admits a Grover-style algorithm with O(sqrt(N)) queries, contradicting the advertised Omega(nu N/M) lower bound. The result therefore does not establish optimality in the parameter regimes covered by the theorems.","major_comments":[{"comment":"The hard-input condition (8) requires M_k/m_k >= beta*kappa_k. Since M_k <= M and m_k >= 1, every input satisfies M_k/m_k <= M. Thus, when M < beta*kappa_k, no input satisfies the hard-input condition. In the proof of Theorem 5.1, the assertion that for M < beta^2*kappa_k*N/16 one can 'put all of the elements to the k-th machine' to construct a hard input is false when kappa_k > 1/beta and M is small: putting all elements on machine k gives M_k/m_k = 1 only if all M elements are distinct, which is not >= beta*kappa_k. Consequently Lemma 5.7 cannot be instantiated, and equation (13) is unjustified.","section":"Section 5.2, Definition 5.4 and proof of Theorem 5.1"},{"comment":"The advertised lower bound Omega(sqrt(nu N/M)) is false as stated. Take n=1, N large, M=1, and nu=N, with the single machine storing one element i*. The target state is |i*>. The counting oracle O|i,s> = |i,(s+c_i) mod (nu+1)> allows the coordinator to compute c_i into an auxiliary register with one query, apply an input-independent phase flip on the condition c_i > 0, and uncompute with O^dagger. This simulates the standard Grover sign-flip oracle with two oracle calls per iteration, so |i*> can be prepared with constant fidelity using O(sqrt(N)) queries. The claimed lower bound would be Omega(sqrt(nu N/M)) = Omega(N), which is asymptotically larger.","section":"Theorem 1.1 and abstract, optimality in terms of nu"},{"comment":"Even if the formal lower bound in Theorem 5.1 is read as a bound in terms of the actual maximum multiplicities kappa_j, the statement 'For the case where kappa_j is unknown, we can just use nu for kappa_j' is invalid for a lower bound. Replacing kappa_j by a larger quantity nu strengthens the bound, and this strengthening is only legitimate if there exist inputs with kappa_j = Omega(nu). When M < nu, the actual maximum multiplicity on any machine is at most M, so no such input exists; the M=1 example above shows the strengthened bound is false.","section":"Transition from kappa_j to nu in Theorem 5.1"},{"comment":"The parallel lower bound inherits the same defect: Lemma 5.9 invokes the proof of Lemma 5.7, which requires hard inputs satisfying M_k/m_k >= beta*kappa_k. The same small-M obstruction applies, and the max_j Omega(sqrt(kappa_j N/M)) bound cannot be converted into the advertised max_j Omega(sqrt(nu N/M)) bound without an additional density assumption such as M = Omega(nu). No such assumption appears in the theorem statements or in Theorem 1.1.","section":"Section 5.4, Theorem 5.2"}],"minor_comments":[{"comment":"The headings of Theorem 4.3 and Theorem 4.5 contain typos: 'seqential qeries' and 'qantum sampling with parallel qeries' should be 'sequential queries' and 'quantum sampling with parallel queries'.","section":"Section 4, headings"},{"comment":"Several cross-references are inconsistent: Definition 5.5 refers to 'Theorem 5.4' where Definition 5.4 is meant; Lemmas 5.6 and 5.7 refer to 'Theorem 5.5' instead of Definition 5.5; and Proposition C.1 refers to 'Theorem 5.6' instead of Lemma 5.6. The introductory paragraph of Section 5 also calls Lemma 5.7 and Lemma 5.8 'Theorem 5.7' and 'Theorem 5.8'.","section":"Section 5 cross-references"},{"comment":"The condition nu >= M/(N*epsilon) in Theorem 4.3 is not discussed or motivated; if epsilon is the approximation parameter, it couples the allowed error with the database parameters in a way that deserves explanation, since the later lower bound does not impose this condition.","section":"Section 4.1, condition in Theorem 4.3"}],"recommendation":"reject","confidential_remarks":"The central claim of the paper, optimality of the two algorithms in terms of the public capacity nu, is false in the sparse regime M << nu. The lower-bound proof cannot be repaired by a local patch because the dependence on nu is fundamentally wrong: a single marked element can be found by Grover search with O(sqrt(N)) queries, while the advertised lower bound is Omega(N). I recommend rejection rather than major revision, since the main theorem as stated is contradicted by a valid input instance within the paper's own model."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know: the paper's headline claim—that the sequential and parallel algorithms are optimal—does not survive contact with the sparse regime. The upper-bound side is fine: the distributed database model is a reasonable new entry point, and the construction of the D operator from local additive oracles (2n sequential calls or 4 parallel calls) is a genuinely clean idea. The amplitude amplification argument goes through and gives O(n sqrt(nu N/M)) sequential and O(sqrt(nu N/M)) parallel queries. That part deserves credit. The problem is the lower bound. Theorem 5.1 and 5.2 rely on hard inputs (Definition 5.4) that require M_k/m_k >= beta*kappa_k on machine k. In the proof of Theorem 5.1, for the case M < beta^2 kappa_k N/16, the authors say they can 'put all of the elements to the k-th machine' to construct such an input. That works only when the total mass M is large enough. If M=1 and kappa_k=N, then M_k/m_k=1, which cannot be a constant fraction of N. So no hard input exists and Lemma 5.7 cannot be instantiated. This is not a technical gap; it is a real falsification. For n=1, M=1, nu=N, the target state is a single unknown basis state, and the standard Grover search prepares it with O(sqrt(N)) queries using the additive oracle (via phase kickback on the multiplicity register). The claimed lower bound is Omega(sqrt(nu N/M)) = Omega(N). That is asymptotically false. The paper even says to substitute nu for unknown kappa_j, so the claimed optimality in Theorem 1.1 is wrong. A density condition like M = Omega(nu) might rescue a matching bound, but the paper does not state one. There is also a minor oddity: Theorem 4.3 lists a condition nu >= M/(N epsilon) that is never used or explained; likely a typo, but it should be cleaned up. Net assessment: the model and the algorithms are a useful contribution, but the main optimality result is not just unproven—it is false. The paper deserves serious referee attention because the algorithmic part and the model are worth salvaging, but the authors need to fix or restrict the lower bound before this is publishable. If I were the editor, I would send it to review with a clear directive to address the sparse counterexample.","headline":"The distributed sampling model and the D-operator algorithm are new and sound, but the claimed optimality lower bound is false as stated; a single-machine Grover counterexample breaks it.","tokens_in":21502,"tokens_out":2653,"would_cite":false,"duration_ms":34136,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that distributed quantum sampling can be done with $O(n\\sqrt{\\nu N/M})$ sequential queries and $O(\\sqrt{\\nu N/M})$ parallel queries, and that both bounds are optimal in the oblivious communication model.","keywords":["quantum sampling","distributed databases","quantum query complexity","oblivious communication model","amplitude amplification","Grover oracle","adversary method","sequential and parallel queries"],"falsifier":"Exhibit an oblivious distributed quantum sampling algorithm that uses $o(n\\sqrt{\\nu N/M})$ sequential queries or $o(\\sqrt{\\nu N/M})$ parallel queries while preparing a state with fidelity above $9/16$ on the hard-input family of Definition 5.4. If such a protocol exists, the claimed optimality is false; if not, the remaining test is whether a new hard distribution can cover the sparse regime where the current hard-input condition fails.","tokens_in":20442,"feed_emoji":"⚛️","tokens_out":10163,"duration_ms":107618,"temperature":0.7,"pith_summary":"The paper starts the study of quantum sampling in a distributed setting: a coordinator must prepare the state $\\frac{1}{\\sqrt{M}}\\sum_{i}\\sqrt{c_i}|i\\rangle$ for a database split across $n$ machines, where each machine only answers simple multiplicity queries. Its main results are matching upper and lower bounds: $O(n\\sqrt{\\nu N/M})$ sequential queries and $O(\\sqrt{\\nu N/M})$ parallel queries, both optimal among oblivious protocols. The algorithms let each machine act as a local Grover oracle, combine the oracles into one distributing operator, and then run zero-error amplitude amplification; the optimality proof uses an adversary-style potential that grows as queries reveal one machine's support. If the paper is right, distributing a database does not change the essential quantum cost of sampling: the same square-root barrier appears, and the sequential model pays only an extra factor of $n$ that simultaneous queries remove.","feed_headline":"Distributed quantum sampling is optimal in both query models","feed_subtitle":"Sequential and parallel query counts are tight, so splitting data across machines costs no extra query rounds.","key_machinery":"The central object is the distributing operator $D$, defined by $D|i,0\\rangle = \\sqrt{c_i/\\nu}\\,|i,0\\rangle + \\sqrt{(\\nu-c_i)/\\nu}\\,|i,1\\rangle$, which maps the uniform state to a superposition whose target amplitude is $\\sqrt{M/(\\nu N)}$. Each machine implements a local oracle $O_j|i,s\\rangle = |i,(s+c_{ij}) \\bmod (\\nu+1)\\rangle$, and these oracles are composed to realize $D$ with $2n$ sequential queries or $4$ parallel queries. The same operator carries both directions: amplitude amplification over $D$ gives the upper bounds, while the lower bound analyzes the potential $D_t = \\mathbb{E}_{T\\in\\mathcal{T}}\\|\\,|\\psi^T_t\\rangle - |\\psi_t\\rangle\\,\\|^2$, the expected separation between the algorithm's state on hard inputs $T$ and its state when machine $k$ is empty.","core_discovery":"On its own terms, the paper's discovery is a pair of tight query-complexity bounds for distributed quantum sampling in the oblivious communication model, where the order of queries is fixed in advance. It constructs a sequential algorithm making $O(n\\sqrt{\\nu N/M})$ oracle calls and a parallel algorithm making $O(\\sqrt{\\nu N/M})$ simultaneous oracle calls, each preparing the sampling state with zero error under the stated parameter condition. It then proves matching lower bounds of $\\Omega(\\sum_j \\sqrt{\\kappa_j N/M})$ for sequential protocols and $\\Omega(\\max_j \\sqrt{\\kappa_j N/M})$ for parallel protocols, where $\\kappa_j$ is the capacity of machine $j$, using hard inputs formed by permuting the support of a single machine's dataset. The authors read these bounds as showing that the fundamental barrier for distributed quantum sampling is the same as in the centralized setting, despite the extra constraints of distributed storage.","pith_inferences":["Beyond the paper: the oblivious assumption is doing load-bearing work; a direct next question is whether adaptive, non-oblivious communication can beat the sequential factor $n$, since the lower-bound potential relies on the query order being fixed in advance.","Beyond the paper: the oracle's local update property suggests the same algorithms can track dynamically changing databases with little recomputation, a direction the paper mentions but does not develop.","Beyond the paper: in the sparse regime where the hard-input condition of the lower bound fails (for instance when total data $M$ is tiny compared with $\\nu N$), the tight complexity is not settled by these theorems, and the square-root barrier could be tested there."],"forward_implications":["A coordinator can prepare the global sampling state from $n$ separate databases with $O(n\\sqrt{\\nu N/M})$ sequential oracle calls, and no oblivious sequential algorithm can do asymptotically better.","With simultaneous queries, the factor $n$ disappears: $O(\\sqrt{\\nu N/M})$ parallel queries suffice and are optimal in the oblivious parallel model.","The lower bounds apply even when all databases are disjoint, so the unavoidable cost reflects locating support across machines rather than duplicate storage.","Because the optimal query counts match the centralized square-root barrier up to the known parameters, adding a distributed architecture does not create a new essential quantum difficulty for sampling."],"supporting_citations":[{"why":"supplies the Grover search framework and the local oracle form that each machine implements.","marker":"[12]"},{"why":"provides the zero-error amplitude amplification theorem used to convert the distributing operator into exact sampling.","marker":"[9]"},{"why":"supplies the optimality proof for Grover search that the lower-bound argument extends to the distributed setting.","marker":"[27]"},{"why":"provides the quantum adversary method behind the hard-input potential analysis.","marker":"[3]"},{"why":"defines the oblivious communication model with a predetermined query order that the paper's upper and lower bounds target.","marker":"[17]"}],"fun_headline_variants":["Distributed quantum sampling matches centralized query cost","Tight quantum sampling bounds for distributed data","Optimal query costs for distributed quantum sampling","Distributed quantum sampling is tight in both query models"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower-bound proof assumes that, for the machine under analysis, one can find a hard input in which that machine holds a constant share of the total data and its elements appear on average at least a fixed fraction of the machine's capacity; when the total dataset is too small, no such input exists, so optimality is proven only outside that sparse regime.","fun_headline_variants_meta":{"raw":{"variants":["Distributed quantum sampling matches centralized query cost","Tight quantum sampling bounds for distributed data","Optimal query costs for distributed quantum sampling","Distributed quantum sampling is tight in both query models"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000772,"raw_usage":{"total_tokens":3371,"prompt_tokens":854,"completion_tokens":2517,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":470,"completion_tokens_details":{"reasoning_tokens":2460}},"tokens_in":470,"tokens_out":2517,"duration_ms":20161,"temperature":1.0,"reasoning_tokens":2460,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:30:37.567600+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit an oblivious distributed quantum sampling algorithm that uses $o(n\\sqrt{\\nu N/M})$ sequential queries or $o(\\sqrt{\\nu N/M})$ parallel queries while preparing a state with fidelity above $9/16$ on the hard-input family of Definition 5.4. If such a protocol exists, the claimed optimality is false; if not, the remaining test is whether a new hard distribution can cover the sparse regime where the current hard-input condition fails.","supporting_citations":[{"cited_title":"2022.Bounds on Oblivious Multiparty Quantum Communication Complexity","cited_arxiv_id":null,"evidence_quote":"defines the oblivious communication model with a predetermined query order that the paper's upper and lower bounds target."}],"review_version":1}