{"id":"ef25b556-f2eb-47f7-9391-749148ef5293","arxiv_id":"2411.15015","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"A postselected quantum algorithm encodes graph connectivity into GHZ states and claims constant measurement complexity, but its success probability shrinks exponentially with graph size.","lead":"This preprint proposes a quantum algorithm that claims to test whether a graph is connected using just two measurements. The catch is that the algorithm relies on non-unitary projection gates that succeed only with probability that shrinks exponentially as the graph grows.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O(1) measurement claim rests on an unproven ancilla implementation of non-unitary projectors; without it the algorithm requires exponentially many runs.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap: the non-unitary spider gates are not physically implemented as unitary channels, and the ancilla remedy is asserted rather than derived. I find that concern decisive. The paper's own text concedes the missing piece ('left as an open question'), and the numerical simulation explicitly ignores the very state decay that determines the number of runs, so it provides no independent support for the O(1) measurement count. The probability formula in Eq. (8a) is also not generally correct (for k components the per-measurement probability that all components agree is 2^{1-k}, not 1/k), but the central rejection does not depend on that arithmetic error. No formal verification or parameter-free derivation backs the ancilla claim. My recommendation is therefore unchanged from the reader: reject the paper because the central complexity claim is unsupported.","tokens_in":16665,"tokens_out":8755,"duration_ms":92580,"concrete_test":"Analytically instantiate the ancilla gadget of Figure 6 for one two-qubit Z spider with input |++> and one ancilla in |0>, and compute the postselected success probability. If it is 1/2 or 1/4 rather than 1, compute the compounded success probability for a connected graph with m (or n-1) edges; exponential decay 2^{-Ω(n)} contradicts the O(1) row of Table II. As a complementary empirical check, modify the supplied Yao notebook to include the ancilla gadget and record the number of shots needed to observe the GHZ branch for path graphs with n = 4, 6, 8; if the shot count grows with n, the constant-measurement claim fails.","verdict_should_be":"REJECT","load_bearing_attack":"The central claim is that two measurements suffice because the circuit maps |0^n> to a product of GHZ states. But each edge gate is a rank-2 projector; starting from |+^n>, the desired branch after all projections has norm squared ≈ 2^{k-n} for k connected components, so it is reached with exponentially small probability. The paper acknowledges this as 'state decay' and lists O(2^n) measurements without ancillas in Table II. The O(1) row therefore depends entirely on the assertion in Section IV.D that ancillas remedy the decay. That section explicitly says 'How many ancilla qubits are necessary to avoid a state decay is left as an open question,' and the proposed replacement (Figure 6 plus m ancillas) is only a verbal sketch. A rank-deficient projector implemented by a unitary plus measurement necessarily has rejected branches; the probability of keeping the desired branch, and how the ancilla gadget avoids an exponential product over m edges, is never computed. Thus the constant-measurement claim is unsupported by both the bare non-unitary construction and the ancilla variant. The simulation in Appendix A also cannot help, since it 'ignores state decay.'","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a quantum algorithm for undirected graph connectivity that encodes each edge as a two-qubit Z-spider (a non-unitary projector) and relies on the ZX-calculus fusion rule to argue that every connected component becomes a multi-qubit GHZ state. The authors claim that two measurements suffice to decide connectivity in constant time O(1), that connected components can be found with a linear number of measurements, and that the circuit depth is bounded above and below by graph-dependent expressions. They acknowledge a 'state decay' caused by the non-unitary gates, propose ancilla qubits as a remedy, and provide a Julia/Yao simulation notebook.","tokens_in":16863,"tokens_out":8731,"duration_ms":83292,"significance":"The central idea of using abelian idempotent projectors from ZX calculus to merge graph edges into a collective GHZ-like condition is original and, as a purely algebraic construction, is elegant. The paper is also unusually honest about the main obstacle: without ancillas the algorithm requires exponentially many runs. If a deterministic ancilla implementation with O(1) acceptance probability existed, the constant-measurement claim would be remarkable. However, no such implementation is derived, and the argument as it stands leaves the main claim unsupported. Strengths of the manuscript include a self-contained derivation of the projector-fusion mechanism, an explicit numerical notebook for the ideal postselected behavior, and a clear identification of the state-decay problem, even though the proposed solution is only sketched.","major_comments":[{"comment":"The constant-measurement claim is unsupported because the ancilla remedy is not derived. Section IV.D states that 'How many ancilla qubits are necessary to avoid a state decay is left as an open question' and then asserts a trade-off between O(2^n) calls without ancillas and O(1) calls with m ancillas. A Z-spider is a rank-2 projector, and from the initial state |+^n> the postselected subspace for k connected components has dimension 2^k, so the acceptance probability of the full sequence is 2^{k-n}. Any unitary-plus-measurement implementation of the same projectors has the same acceptance probability unless the rejected branches are coherently recovered, and the manuscript provides no mechanism or calculation for such recovery. The O(1) row in Table II is therefore an assumption, not a result.","section":"IV.D and Table II"},{"comment":"The failure probability formula for disconnected graphs is incorrect for k>2. In the ideal postselected state, the k connected component states are independent fair bits, so in a single measurement the probability that all fragments give the same outcome is 2/2^k = 2^{1-k}, not 1/k as written in Eq. (8a). Over M measurements the failure probability is (2^{1-k})^M, not 1/k^M. For example, with k=3 and M=2, Eq. (8a) gives an error of 1/9, whereas the actual error is 1/16. This does not rescue the constant-measurement claim, since the dominant issue is the exponentially small state-preparation probability, but the statistical analysis as written is wrong.","section":"IV.B.1, Eq. (8a)"},{"comment":"The statement that the non-unitary spider gates can be executed with certainty on the states used in the algorithm is incorrect. Equation (3) shows that a Z-spider has success probability 1 only when its input is already GHZ-like. In the algorithm, the first edge gate acts on |++...> after Hadamards on |0^n>, and the acceptance probability of that single gate is 1/2; the product over all edges is exponentially small. The Discussion's claim that 'the operation can be executed with certainty' contradicts the state-decay analysis in Section IV.D and should be removed or carefully qualified.","section":"III.C and Discussion"},{"comment":"The claimed depth lower bound is not a proven bound. The text introduces it as 'The best experimental fit is one of the form ...' and adds that 'This fit still underestimates the behavior for large n but provides a reasonable lower bound.' A numerical fit with fitted exponent 0.88 and prefactor 2 is not a mathematical lower bound. The depth analysis should clearly distinguish rigorously proven upper bounds from empirical estimates, otherwise the paper's depth contribution is overstated.","section":"IV.C, Eq. (14), and Appendix B.2"},{"comment":"The numerical simulation cannot validate the algorithm's success probability because it 'ignores state decay' and samples from the remaining state after the projectors. This is equivalent to sampling from the ideal postselected state, not from the physical measurement statistics of the non-unitary circuit. The notebook may be useful for checking the algebraic fusion and the ideal measurement patterns, but it does not provide evidence for the feasibility of the constant-measurement claim, which is precisely about the probability of reaching that postselected state.","section":"Appendix A"}],"minor_comments":[{"comment":"The text calls the edge gate 'nilpotent, N^2 = N'; an operator satisfying N^2 = N is idempotent, not nilpotent. The property that repeated edges do not cancel is idempotence, and the terminology should be corrected.","section":"Section II"},{"comment":"The number of measurements for connected components is stated as M = 2|G_k| and described as 'sublinear time.' Since |G_k| can be as large as n, this is linear in the number of nodes, not sublinear; the abstract's 'linear number of measurements' is the correct characterization.","section":"IV.B.2"},{"comment":"Figure 6 is under-specified: the MX measurement basis is not defined, the way the circuit implements the Z-spider projector is only sketched, and the success probability of the shown translation is never computed. A concrete circuit and its acceptance probability are needed before the ancilla remedy can be assessed.","section":"Figure 6 and IV.D"},{"comment":"The general formula N(n',\\lambda)=\\binom{n'+1}{2\\lambda} is asserted after deriving only the \\lambda=2 case. A proof for all \\lambda, or a citation to a source for the closed form, is needed to make the upper-bound derivation rigorous.","section":"Appendix B.1"},{"comment":"The row labeled 'Time \\times space' is not a standard complexity measure; the product of the number of measurements and the number of qubits has no clear operational meaning and should either be defined or removed.","section":"Table II"},{"comment":"The claimed generality to graphs with self-loops is not supported by the construction: a two-qubit Z-spider requires two distinct wires, and the mapping of a self-loop to such a gate is not described.","section":"Introduction and IV.A"}],"recommendation":"reject","confidential_remarks":"The manuscript identifies its own central weakness: without ancillas the algorithm requires exponentially many measurements, and the ancilla-based O(1) remedy is explicitly left as an open question. On reading the paper, the stress-test concern lands: the rank-2 projector construction gives an exponentially small acceptance probability that a unitary-plus-measurement implementation cannot remove without coherent recovery of rejected branches. Because the main claim depends on this missing piece, I do not see a path to acceptance within the current scope. The algebraic fusion idea may be worth developing further, but the constant-measurement claim as stated is not supported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me give you my take on 2411.15015. The core construction is genuinely neat: map each edge to a Z-spider projector, and because spiders of the same color fuse, the whole connected component collapses to a single GHZ projector. The postselected circuit does exactly that, and the paper is clear about the abelian/nilpotent requirements that force this choice. That part is worth publishing as an observation.\n\nThe problem is the advertised complexity. The projection onto the GHZ subspace for a graph with k components succeeds with probability 2^{k-n} (for a connected graph, 2^{1-n}). The paper admits this in Section IV.D as 'state decay' and lists O(2^n) measurements without ancillas. But the O(1) claim leans entirely on the ancilla remedy, which is never worked out. Figure 6 is a unitary-plus-measurement implementation of a rank-deficient projector; it necessarily has rejected branches, and the paper explicitly leaves the number of ancillas as an open question. So the constant-measurement result is not established. This is the load-bearing flaw, and the stress-test note is right about it.\n\nThe measurement statistics are also off. Equation (8a) says the failure probability for a disconnected graph is 1/k^M. With k GHZ components, the probability that a single run gives an all-equal bitstring is 2^{1-k}, so after M runs the failure probability is 2^{M(1-k)}, not 1/k^M. For k=2 they coincide; for larger k they don't. Since the two-measurement 3/4 success probability is computed from these formulas, the error affects the main claim even within the paper's own model.\n\nThe depth 'lower bound' in Eq. (14) is a curve fit, and the paper says so. That's not a bound, it's a heuristic. And the simulation ignores state decay, so it verifies only the postselected branch, not the actual measurement process. The paper is transparent about that, but it doesn't help the central claim.\n\nOverall: the construction is a clean example of ZX-calculus reasoning and a useful warning about postselection, but as a quantum algorithm for connectivity it doesn't work as advertised. I'd send it to a serious referee because the basic idea deserves scrutiny, but the title and abstract need to be reframed and either the ancilla method proved or removed. It would be instructive in a reading group as a case study.","headline":"The ZX-spider construction is sound as a postselected projection, but the constant-measurement claim relies on an unproven ancilla gadget and the failure statistics are wrong.","tokens_in":17371,"tokens_out":3741,"would_cite":false,"duration_ms":35792,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","05C40","68R10"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"The paper argues that graph connectedness can be decided with two quantum measurements, because non-unitary ZX-calculus gates placed on edges fuse into one GHZ state per connected component.","keywords":["graph connectivity","quantum algorithm","ZX calculus","non-unitary gates","GHZ states","constant measurement complexity","connected components","state decay"],"falsifier":"Implement each two-qubit Z spider as a concrete unitary circuit with ancilla qubits, for instance via the Bell-measurement replacement shown in the paper, run the full algorithm on a graph with $n$ nodes, and estimate the probability that the output state is the intended tensor product of GHZ states. If that probability decays exponentially in $n$ or in the number of edges, or if a constant success probability requires the number of ancillas to grow with $n$, then the claimed O(1) measurement count is not achieved by that implementation.","tokens_in":16454,"feed_emoji":"🔗","tokens_out":12371,"duration_ms":109569,"temperature":0.7,"pith_summary":"The paper proposes a quantum algorithm that decides whether an undirected graph is connected using a constant number of measurements: two measurements of all qubits, regardless of how many nodes or edges the graph has. The construction maps each node to a qubit and each edge to a non-unitary two-qubit gate from ZX calculus; the fusion rule of these gates contracts all edges inside a connected component into a single projective gate, placing that component into a GHZ state. Each connected component then appears as a block of qubits whose measurement outcomes are perfectly correlated, so two measurement rounds distinguish one block from more than one block with success probability $3/4$. The same machinery identifies the individual connected components with a number of measurements proportional to the number of components. The paper is open about a cost: the projective gates dissipate state amplitude, and the ancilla-based remedy that would make the O(1) claim clean is stated as an open question.","feed_headline":"Two quantum measurements decide if a graph is connected","feed_subtitle":"Non-unitary ZX gates fuse a component's edges into one projector, so two shots reveal connectivity.","key_machinery":"The load-bearing object is the Z spider of ZX calculus: a multi-legged non-unitary tensor whose matrix has value $1$ in the top-left entry, $e^{i\\alpha}$ in the bottom-right entry, and zeros elsewhere; as a map it is a projector onto the two-dimensional subspace spanned by $|0\\cdots0\\rangle$ and $|1\\cdots1\\rangle$. Its contraction rule lets two same-colour spiders that share a wire fuse into a single spider whose phase is the sum of the two phases, so the entire edge set of a connected component collapses to one spider on that component's qubits. Because the spider gates are abelian and nilpotent, repeated edges and self-loops leave the contraction unchanged, which is what lets the algorithm accept multigraphs and graphs with loops. This contraction is what turns the unordered list of edges into a global statement about the graph without ever sorting the edges.","core_discovery":"The paper's central claim is that the connectedness of an undirected graph can be encoded as a product of GHZ states by a contractible set of non-unitary gates. For an edge $\\{n_i,n_j\\}$ the algorithm applies a two-qubit Z spider, whose matrix has a single $1$ in the first entry and a single $e^{i\\alpha}$ in the last entry and zeros elsewhere; the ZX fusion rule then contracts every connected cluster of edge-spiders into one spider touching the qubits of that cluster. Each cluster spider projects the cluster into the subspace $\\mathrm{span}\\{|0\\cdots0\\rangle, e^{i\\alpha}|1\\cdots1\\rangle\\}$, i.e. into a GHZ state. The final state is $\\bigotimes_k |\\mathrm{GHZ}\\rangle_k$ over the connected components, and because each GHZ block measures independently as all-zero or all-one, two simultaneous measurements of all qubits decide connectedness with success probability $3/4$. The paper further claims that successive measurement rounds, combined with the XOR operation, reveal the partition into connected components in $O(|G_k|)$ measurements.","pith_inferences":["If the ancilla construction is made explicit and shown to preserve amplitude, this would give a graph decision algorithm whose measurement count is independent of graph size; the paper's own open question about the ancilla count means the practical constant-time claim is conditional.","The same spider-contraction route could be tried for other global graph properties that are partition-like, such as bipartiteness or strong connectivity, by choosing projective gates whose fixed states encode those properties; the paper's discussion points in this direction.","The state-decay problem may be unavoidable rather than technical: any unitary implementation of a projector has success probability equal to the input's overlap with the target subspace, so the constant-call claim may end up moving the exponential cost into ancilla count or gate depth instead of measurement count.","A direct testable extension is to run the algorithm on current hardware using the Bell-measurement GHZ construction from the paper and compare the block-correlation pattern of the measured shots with the true connected components of random graphs; the paper's simulation ignores decay, so hardware data would probe exactly the missing assumption."],"forward_implications":["Graph connectedness becomes a constant-measurement decision problem: two shots of the prepared state determine, with probability $3/4$, whether the graph has one component or several, independent of the node and edge counts.","Connected components can be recovered by repeated measurements: a number of all-qubit measurement rounds of order $O(|G_k|)$, combined by XOR, classifies qubits into their GHZ blocks.","The algorithm applies to every undirected graph, including graphs with repeated edges and self-loops, because the Z-spider gates are abelian and nilpotent.","The circuit depth is bounded between $O(\\lceil m/n \\rceil)$ and $O(m)$ when edge gates on disjoint nodes are parallelized, with an average-case upper bound derived from integer partitions.","Without ancillas the algorithm needs $O(2^n)$ measurement calls because of state decay; with ancillas the paper claims the call count drops to $O(1)$ at a total cost of $O(n+m)$ qubits."],"supporting_citations":[{"why":"Defines the ZX-calculus spiders and the fusion rule used to contract edge gates into one spider per component.","marker":"[37]"},{"why":"Provides the theory of non-unitary quantum circuits and the ancilla-based implementation on which the O(1) claim depends.","marker":"[41]"},{"why":"Gives the prior quantum graph-connectivity algorithms whose runtimes this paper compares against and claims to improve.","marker":"[33]"},{"why":"Cited by the paper to warn that ignoring non-unitary state decay leads to nonsensical results; it motivates the ancilla discussion.","marker":"[48]"},{"why":"Supplies the Bell-measurement construction used to argue that the GHZ-state preparation behind the algorithm is feasible on current hardware.","marker":"[56]"},{"why":"Establishes ZX calculus as a language for linear maps and composition, grounding the spider notation the algorithm is built on.","marker":"[35]"}],"fun_headline_variants":["Two quantum measurements tell if a graph is connected","Constant-measurement quantum test for graph connectivity","Non-unitary ZX gates cut graph connectivity to two shots","Graph connectivity from two entangled projective measurements","Quantum graph connectivity: two measurements suffice"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithm's O(1)-measurement claim rests on the assumption that the non-unitary spider gates can be implemented with ancilla qubits without losing the state amplitude; the paper states that the number of ancillas needed to prevent state decay is an open question and does not prove that the ancilla version succeeds deterministically.","fun_headline_variants_meta":{"raw":{"variants":["Two quantum measurements tell if a graph is connected","Constant-measurement quantum test for graph connectivity","Non-unitary ZX gates cut graph connectivity to two shots","Graph connectivity from two entangled projective measurements","Quantum graph connectivity: two measurements suffice"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000343,"raw_usage":{"total_tokens":1853,"prompt_tokens":882,"completion_tokens":971,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":498,"completion_tokens_details":{"reasoning_tokens":901}},"tokens_in":498,"tokens_out":971,"duration_ms":9812,"temperature":1.0,"reasoning_tokens":901,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:37:21.112825+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement each two-qubit Z spider as a concrete unitary circuit with ancilla qubits, for instance via the Bell-measurement replacement shown in the paper, run the full algorithm on a graph with $n$ nodes, and estimate the probability that the output state is the intended tensor product of GHZ states. If that probability decays exponentially in $n$ or in the number of edges, or if a constant success probability requires the number of ancillas to grow with $n$, then the claimed O(1) measurement count is not achieved by that implementation.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the ZX-calculus spiders and the fusion rule used to contract edge gates into one spider per component."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the theory of non-unitary quantum circuits and the ancilla-based implementation on which the O(1) claim depends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the prior quantum graph-connectivity algorithms whose runtimes this paper compares against and claims to improve."},{"cited_title":"Terashima and M","cited_arxiv_id":null,"evidence_quote":"Cited by the paper to warn that ignoring non-unitary state decay leads to nonsensical results; it motivates the ancilla discussion."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Bell-measurement construction used to argue that the GHZ-state preparation behind the algorithm is feasible on current hardware."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes ZX calculus as a language for linear maps and composition, grounding the spider notation the algorithm is built on."}],"review_version":1}