{"id":"b4e622c7-f28b-4c64-b3af-e83335eff859","arxiv_id":"2509.02909","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A quantum pebble that emits repeated copies of a port-encoding qubit lets an oblivious agent walk to a treasure in D steps using D pebbles.","lead":"This paper proposes a quantum pebble, a device placed by an oracle that emits copies of the same qubit state encoding the port number toward a hidden treasure. A memoryless agent can follow the path in D steps with D pebbles, but the paper's headline measurement count misses a factor of the graph degree.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's per-node measurement bound omits the factor Δ/2 required by the protocol's own accounting in Section 4.2.","rationale":"The reader's weakest_assumption was the idealized infinite-copy single-state quantum pebble source. That is an explicit model definition and not an internal inconsistency: if the source emits fresh copies in the same state, the protocol's measurement logic is well-defined. The more load-bearing internal issue is the mismatch between the stated measurement complexity in Theorem 3 and the protocol's own accounting in Section 4.2. The reader's rationale does mention this factor-Δ/2 mismatch, so there is partial agreement; however, the reader did not elevate it to the weakest assumption. This mismatch directly affects the central claim: the abstract and Theorem 3 advertise O((log D + log Δ)/log(1/δ)) measurements per node, but the protocol requires n measurements in each of Δ/2 bases, giving a factor Δ/2 larger total. Since δ depends on Δ, this is asymptotically a factor of Δ in the final expression. The error is localized and fixable, so it reinforces the CONDITIONAL verdict rather than justifying rejection. The D-step traversal using D quantum pebbles remains coherent under the model's assumptions.","tokens_in":14222,"tokens_out":12809,"duration_ms":152288,"concrete_test":"Recompute the total number of measurements per node in the general protocol, fixing a concrete instance such as Δ = 100, D = 10^6, and target failure probability 1/D. Choose n exactly as in the proof of Theorem 3 (so that Δδ^n ≤ 1/D), then count total measurements as (Δ/2)n. Compare this number to the bound stated in Theorem 3. If the ratio is Δ/2, the theorem is missing the required factor. More generally, re-derive the proof with N_total as the variable: the union bound gives N_total ≥ (Δ/2)(log(DΔ))/log(1/δ), which differs from the stated bound by the same factor Δ/2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The general protocol in Section 4.2 states: 'the agent at node v measures the qubits emitted from the quantum pebble at v, n times in each of the M^(j) basis. This requires a total of nΔ/2 measurements at each node.' Yet Theorem 3 claims 'The agent needs to make O((log D + log Δ)/(log 1/δ)) measurements at each node,' and its proof chooses n = O((log D + log Δ)/(log 1/δ)). If n is the number of measurements per basis, then the true per-node cost is (Δ/2)·n = O(Δ(log D + log Δ)/log(1/δ)). If n is instead intended to be the total number of measurements, then the failure-probability calculation must use n/(Δ/2) measurements per basis, and solving Δδ^{n/(Δ/2)} ≤ 1/D again gives n = O(Δ(log D + log Δ)/log(1/δ)). Either way, the stated bound is missing a factor of Δ/2. Because log(1/δ) = log(1/cos²(π/2Δ)) ∼ π²/(4Δ²), the claimed bound is O(Δ²(log D + log Δ)), while the protocol's actual per-node cost is O(Δ³(log D + log Δ)). This does not break the D-step search itself, but it undermines the headline asymptotic efficiency claim, which is a central quantitative contribution of the paper.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies treasure hunt in anonymous graphs (unlabeled vertices, port-labeled edges) by an oblivious agent. It first proves (Theorem 1) that deterministic strategies using classical pebbles cannot guide an oblivious agent to a treasure. It then introduces 'quantum pebbles,' idealized sources that repeatedly emit qubits in a fixed but unknown state, and proposes a protocol in which an oracle places one quantum pebble on each vertex of a shortest s-t path. The pebble at a vertex encodes the next port number in the qubit state; the agent measures the emitted qubits in several bases and, with high probability, decodes the correct port. The paper develops the construction for Δ=4 (Section 3) and for general maximum degree Δ (Section 4), proving Theorem 3: a randomized strategy using D quantum pebbles finds the treasure in D steps and uses O((log D + log Δ)/log(1/δ)) measurements per node, where δ = cos²(π/(2Δ)). A final remark argues that encoding the whole path in one qubit is not more efficient. The claimed D-step traversal time is correct in spirit, but the quantitative measurement bound stated in the abstract, Theorem 3, and conclusion is missing a factor of Δ/2 that the protocol itself requires.","tokens_in":14533,"tokens_out":7579,"duration_ms":86876,"significance":"If the main claim held as stated, the paper would contribute a genuinely novel use of quantum information as a distributed advice mechanism: a memoryless agent could follow a precomputed shortest path by decoding port numbers from repeated measurements of identical qubits, something impossible with classical pebbles. The paper's strengths are its self-contained protocol, the explicit construction of the measurement bases, and the elementary union-bound analysis of the decoding error. The central decoding idea (Lemmas 3 and 4) is sound. However, the headline quantitative contribution is overstated by a factor of Δ/2, and after the correct accounting the per-node measurement bound is O(Δ(log D + log Δ)/log(1/δ)) = O(Δ³(log D + log Δ)), not O((log D + log Δ)/log(1/δ)) = O(Δ²(log D + log Δ)). The protocol also has a formal inconsistency in port numbering, and Remark 3 cites nonexistent theorem/lemma numbers. The idealized infinite-copy emitter is a modeling assumption that should be stated more carefully, but it is not internally inconsistent.","major_comments":[{"comment":"The paper's own accounting gives the per-node measurement cost as nΔ/2, not n. Section 4.2 states: 'the agent at node v measures the qubits emitted from the quantum pebble at v, n times in each of the M^(j) basis. This requires a total of nΔ/2 measurements at each node.' Yet Theorem 3 and the abstract state that the agent makes O((log D + log Δ)/log(1/δ)) measurements per node, and the proof of Theorem 3 chooses n = O((log D + log Δ)/log(1/δ)). If n is measurements per basis, the per-node cost is (Δ/2)n = O(Δ(log D + log Δ)/log(1/δ)). If n is instead intended as the total number of measurements, then the failure-probability calculation must use n/(Δ/2) measurements per basis; solving Δδ^(n/(Δ/2)) ≤ 1/D again gives n = O(Δ(log D + log Δ)/log(1/δ)). Thus the stated bound is wrong by a factor of Δ/2 either way. Since log(1/δ) = Θ(1/Δ²), the claimed bound is O(Δ²(log D + log Δ)) while the pr","section":"Section 4.2 and Theorem 3"},{"comment":"The model in Section 1 defines port numbers in the range [0:deg(v)-1], but the encoding in Section 3.2 uses port numbers 1,2,3,4 for Δ=4, and the general encoding f(j) in Section 4.2 maps port numbers 1,...,Δ (with the example '1,4,3,2,4,1'). As written, the protocol cannot handle port 0, which is a valid port in the stated model. This is a formal correctness gap in the presented algorithm. The fix is straightforward—either revise the model to say ports are 1,...,deg(v), or shift the encoding so that port 0 is handled—but the discrepancy should be addressed explicitly.","section":"Section 1 vs. Section 3.2/4.2"},{"comment":"Remark 3 claims that encoding the entire path in a single quantum pebble is not more efficient, and the conclusion lists this as a proven contribution. However, the argument cites 'Theorem 9,' 'Lemma 7,' and 'Lemma 11,' none of which exist in the manuscript (the relevant results are Theorem 3, Lemma 4, and Lemma 5). The proof also conflates Δ^D (the number of paths) with ΔD (used in the angle and bounds in Lemma 5), and it does not rigorously justify why the number of required bases is Δ^D/2. Because the secondary claim is presented as a proof, the missing references and notation errors make it unverifiable. This should be repaired or the remark downgraded to a conjecture.","section":"Remark 3"}],"minor_comments":[{"comment":"The phrase 'δ is an upper bound on the probability that the correct state is observed when measured in a particular basis' is misleading. In Lemma 4, δ bounds the probability of obtaining a definite-looking outcome when measuring a state from a different basis (i.e., a wrong-basis outcome), not the probability of observing the correct state. Please rephrase for clarity.","section":"Theorem 3 statement"},{"comment":"The proof says measurements are taken 'n + 1 times' but the protocol and theorem use n; the notation should be harmonized. Also 'faliure' is a typo.","section":"Lemma 2"},{"comment":"Several typos and spacing issues: 'a a total of D quantum pebbles' in Theorem 3; 'port-node' instead of 'port number'; 'cos 2' without a superscript in the proof of Theorem 3; 'only of the the measurements' in Lemma 1. A careful proofreading pass is needed.","section":"Throughout"},{"comment":"The emitter model assumes the quantum pebble can produce arbitrarily many fresh qubits in the same unknown state without being depleted or disturbed by measurements. This is an idealized assumption; the paper acknowledges decoherence but could more explicitly state that the analysis is in a noiseless, infinite-copy source model and that a physical implementation or error model is left open.","section":"Definition 1 / Section 3.2"},{"comment":"The sentence 'the agent can take as many measurements as needed' is important because it is what avoids a no-cloning obstruction; it could be highlighted as a modeling assumption rather than an aside.","section":"Section 3.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is a proof-of-concept that a version of the main idea is sound, but the central measurement-complexity claim is incorrect by a factor of Δ/2 and the formal port-number inconsistency needs fixing. The internal references in Remark 3 (Theorem 9, Lemma 7, Lemma 11) suggest an incompletely revised draft. With focused corrections, the core contribution can become publishable; in its current form it should not be accepted as is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should read this as a promising but rough draft. The core idea is genuinely new: a quantum pebble that emits identical qubits, encoding the next port number in a set of measurement bases, lets an oblivious agent walk a precomputed path in D steps. The construction of the bases (Lemma 4) and the union-bound argument in Theorem 3 are essentially correct. The deterministic classical-model impossibility in Theorem 1 is a nice contrast. I agree with the reader that the central decoding argument is sound and the flaws are repairable.\n\nThe main problem is the measurement complexity. The protocol in Section 4.2 explicitly says the agent measures n times in each of the Δ/2 bases, requiring nΔ/2 measurements per node. Theorem 3 and the abstract claim only O((log D + log Δ)/(log 1/δ)) measurements per node. Since δ = cos²(π/(2Δ)), log(1/δ) is on the order of 1/Δ², so the true total is O(Δ³(log D + log Δ)) per node, not O(Δ²(log D + log Δ)). This is a real quantitative error in the paper's headline claim, but it does not break the D-step search itself.\n\nOther soft spots are minor but worth fixing: the paper uses port numbers 1 through Δ while the model defines ports 0 through deg(v)−1; the \"without loss of generality\" that Δ is even is unexplained (odd degrees are simply not covered); and Remark 3 is a mess—it references Theorem 9, Lemma 7, and Lemma 11 that do not exist, and its comparison argument is too sketchy to follow. The remark should be either rewritten or removed.\n\nThe broader significance concern is fair: a classical pebble with Δ distinguishable colors would achieve the same D-step traversal deterministically. The quantum advantage only holds against identical classical pebbles. The authors should engage with that comparison explicitly.\n\nWho is this for? Readers working on anonymous graph search, advice complexity, or quantum-inspired distributed models. It deserves a serious referee: the core is sound, the errors are local, and the model is worth discussing. My recommendation: send to peer review, require a major revision that fixes the factor Δ/2, the port indexing, the even-Δ assumption, and cleans up Remark 3.","headline":"A novel quantum-pebble encoding with a basically sound core protocol, but the headline measurement bound is off by a factor Δ/2 and several addressable gaps need cleaning.","tokens_in":15036,"tokens_out":5965,"would_cite":false,"duration_ms":62309,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A memoryless agent can find a treasure in an anonymous graph in D steps by measuring qubits emitted by quantum pebbles.","keywords":["quantum pebbles","anonymous graphs","oblivious agents","treasure hunt","quantum measurement","port numbers","advice complexity","distributed search"],"falsifier":"Prepare a qubit in one of the four states used for degree-4 graphs, measure it n times in a wrong basis, and count how often all n outcomes agree. The paper's general bound treats this ambiguity as at most cos^2(pi/8)^n, while the degree-4 section uses 2^{-n}; an experiment measuring the actual rate of ambiguous runs would settle which bound governs and therefore whether the promised measurement count per node is correct.","tokens_in":14076,"feed_emoji":"⚛️","tokens_out":8674,"duration_ms":95311,"temperature":0.7,"pith_summary":"The paper tries to show that an agent with no memory can still solve treasure hunt in anonymous graphs, where classical pebbles provably cannot guide an oblivious searcher, if each pebble is replaced by a quantum source that repeatedly emits the same unknown qubit state. The agent does not need to remember anything: at each node it performs repeated measurements of emitted qubits in several rotated bases, and the only basis that yields a deterministic outcome tells it which port to take. The claimed result is that D quantum pebbles placed along a shortest path let the agent reach a treasure at distance D in exactly D moves, with O((log D + log Delta)/(log 1/delta)) measurements per node and high success probability. If true, this would be the first constructive role for quantum information as a navigation aid in anonymous distributed search, and a way around a classical impossibility.","feed_headline":"Quantum pebbles let memoryless agents find treasure in D steps","feed_subtitle":"Oblivious searchers, which fail with classical pebbles, decode port numbers from repeated quantum measurements.","key_machinery":"The load-bearing object is a family of measurement bases M(j) = {(|0> + e^{ij phi}|1>)/sqrt(2), (|0> - e^{ij phi}|1>)/sqrt(2)} for j = 0, ..., Delta/2 - 1, with phi = pi/Delta. Port number 2i+1 is encoded as |i+> and port number 2i+2 as |i->. A qubit in one of these states, measured in its own basis, gives a deterministic outcome; measured in any other basis it gives each outcome with probability at most delta = cos^2(pi/(2 Delta)). Repeated measurement in all bases therefore identifies the port number, and the emitter-based quantum pebble supplies the many identical copies needed for the repeated trials.","core_discovery":"The paper's central claim is Theorem 3: there is a randomized strategy, using at most one quantum pebble per node on the shortest path—D pebbles total—that lets an oblivious agent find the treasure in D steps. The oracle encodes the port number of the next edge as one of Delta/2 two-dimensional bases: port 2i+1 is the state |i+> and port 2i+2 is |i->. The agent measures emitted qubits n times in every basis. In the single correct basis the outcome is deterministic; in each wrong basis, a run of n identical outcomes that could mislead the agent has probability at most delta^n, with delta = cos^2(pi/(2 Delta)), and union-bounding over the wrong bases gives per-node failure probability at most","pith_inferences":["A direct test of the idea: if the pebble emitted a classical bit string rather than identical qubits, the agent would need to remember earlier bits to form the string; identical quantum states are what make repeated measurements a memoryless decoder, suggesting the same trick could replace memory in other state-estimation tasks.","The paper works with two-outcome projective measurements; using a qudit or a POVM with more outcomes would cut the measurement count, pointing to a resource tradeoff between pebble dimension and agent measurement time.","The authors' own remark that the angle bound is pessimistic implies n could be reduced by tracking the actual basis separations; an improved analysis of the bounding lemma would strengthen the theorem without changing the protocol.","Since the oracle must know the shortest path and place pebbles, the quantum advantage is in the guidance channel, not in discovering the path; the method would combine naturally with any path-finding preprocessing."],"forward_implications":["An oblivious agent can navigate a precomputed shortest path in anonymous graphs, making only local look-measure-move decisions, with no memory of earlier rounds.","D quantum pebbles suffice for a high-probability treasure hunt in D steps, matching the shortest-path lower bound in time.","The quantum protocol is strictly more expressive than classical pebbles for oblivious agents: the classical one-bit presence signal is provably insufficient, while the quantum state carries a port choice.","The per-node measurement budget grows only logarithmically in D and Delta (up to the 1/log(1/delta) factor), so the dominant cost stays linear in the distance.","A single-pebble encoding of the whole path is not a shortcut; it requires exponentially many bases and is provably no faster than the per-node encoding."],"supporting_citations":[{"why":"Defines the deterministic treasure hunt problem in unweighted graphs and gives almost-optimal algorithms, setting the problem context this paper extends.","marker":"[7]"},{"why":"Provides the pebble-guided optimal treasure hunt for non-oblivious agents in anonymous graphs, the classical baseline this quantum strategy is compared against.","marker":"[13]"},{"why":"Supplies the projective measurement formalism and Born-rule probabilities that the protocol's basis measurements rely on.","marker":"[21]"}],"fun_headline_variants":["Quantum pebbles guide memoryless agents to treasure in D steps","Oblivious agents find treasure with quantum pebbles alone","Quantum pebbles crack anonymous graph search for oblivious agents","Memoryless searchers succeed via quantum pebble guidance","Anonymous graphs: quantum pebbles beat classical limits"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing premise is that a quantum pebble is an unlimited source that keeps emitting qubits in the same fixed, unknown state, so the agent can take as many identical copies as it wants; if emissions are finite, noisy, or the state drifts, the measurement budget and the D-step guarantee no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["Quantum pebbles guide memoryless agents to treasure in D steps","Oblivious agents find treasure with quantum pebbles alone","Quantum pebbles crack anonymous graph search for oblivious agents","Memoryless searchers succeed via quantum pebble guidance","Anonymous graphs: quantum pebbles beat classical limits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000204,"raw_usage":{"total_tokens":1280,"prompt_tokens":853,"completion_tokens":427,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":597,"completion_tokens_details":{"reasoning_tokens":343}},"tokens_in":597,"tokens_out":427,"duration_ms":4940,"temperature":1.0,"reasoning_tokens":343,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T11:18:32.300484+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Prepare a qubit in one of the four states used for degree-4 graphs, measure it n times in a wrong basis, and count how often all n outcomes agree. The paper's general bound treats this ambiguity as at most cos^2(pi/8)^n, while the degree-4 section uses 2^{-n}; an experiment measuring the actual rate of ambiguous runs would settle which bound governs and therefore whether the promised measurement count per node is correct.","supporting_citations":[{"cited_title":"ACM Transactions on Al- gorithms 19(3), 1–32 (2023)","cited_arxiv_id":null,"evidence_quote":"Defines the deterministic treasure hunt problem in unweighted graphs and gives almost-optimal algorithms, setting the problem context this paper extends."},{"cited_title":"Theoretical Computer Science922, 61–80 (2022)","cited_arxiv_id":null,"evidence_quote":"Provides the pebble-guided optimal treasure hunt for non-oblivious agents in anonymous graphs, the classical baseline this quantum strategy is compared against."},{"cited_title":"Cambridge university press (2010)","cited_arxiv_id":null,"evidence_quote":"Supplies the projective measurement formalism and Born-rule probabilities that the protocol's basis measurements rely on."}],"review_version":1}