error.tex

% =====================================================================
%  Two counterexamples to the k-source-subgraph-freeness tester of
%  Apers, Magniez, Sen, Szabo, "Quantum property testing in sparse
%  directed graphs" (arXiv:2410.05001; APPROX/RANDOM 2025, art. 32).
%
%  Self-contained: needs amsmath, amssymb, amsthm, and the theorem
%  environments declared below (delete them if your thesis already
%  defines theorem/proposition/lemma/remark).
% =====================================================================

% \usepackage{amsmath,amssymb,amsthm}
% \newtheorem{theorem}{Theorem}[section]
% \newtheorem{proposition}[theorem]{Proposition}
% \newtheorem{lemma}[theorem]{Lemma}
% \newtheorem{definition}[theorem]{Definition}
% \theoremstyle{remark}
% \newtheorem{remark}[theorem]{Remark}

\section{Two counterexamples to the tester}
\label{sec:counterexamples}

Throughout this section, $\mathrm{AMSS}$ denotes the algorithm of
Section~3.2 of the original work, and we keep its notation: $H$ is a
pattern digraph on $h$ vertices with $k$ source components, $G$ is an
$N$-vertex digraph accessed in the unidirectional model through the
oracle $\mathcal O^{\mathrm{out}}_G : V \times [d] \to V \cup \{\bot\}$,
only out-degrees are bounded (by $d$), and $G$ is $\varepsilon$-far from
$H$-free if at least $\varepsilon d N$ edges must be modified to make it
$H$-free. We write $B^+_\ell(v)$ for the set of vertices reachable from
$v$ by a directed path of length at most $\ell$, so that a depth-$\ell$
BFS from $v$ costs at most $d^\ell$ queries and reveals exactly the
subgraph induced on $B^+_\ell(v)$ together with the outgoing edges of its
vertices.

We recall the marking condition of the algorithm verbatim: at level $i$,
a vertex $v$ is marked if there exist $u_j \in \mathcal S_j$ for each
$j \in [i-1]$ such that $u_1, \ldots, u_{i-1}$ and $v$ lie in $i$
different source components \emph{of an $H$-subgraph of $G$}. We call
this the \emph{semantic} marking condition, and we call \emph{local} the
weaker condition obtained by asking only that
$\bigcup_{j} B^+_h(u_j) \cup B^+_h(v)$ contain a valid partial copy of
$H$, i.e.\ an embedding of the subgraph of $H$ generated by the first $i$
source components. Section~\ref{sec:cex-oracle} shows that the semantic
condition is not decidable within the claimed query budget, and
Section~\ref{sec:cex-algorithm} shows that the algorithm is incorrect
\emph{under either reading}.

\subsection{The pattern graph}

\begin{definition}\label{def:H0}
	Let $H_0$ be the digraph on $V(H_0) = \{a, b, c, z, w\}$ with
	$$E(H_0) = \{\, a \to z,\; b \to z,\; z \to w,\; c \to w \,\}.$$
\end{definition}

\begin{lemma}\label{lem:H0-sources}
	$H_0$ is weakly connected, has $h = 5$ vertices, and its source
	components are exactly $\{a\}, \{b\}, \{c\}$; hence $k = 3$.
\end{lemma}

\begin{proof}
	$H_0$ is acyclic, so every strongly connected subgraph is a single
	vertex. Among the singletons, $\{z\}$ and $\{w\}$ receive incoming edges
	($a \to z$ and $z \to w$), while $a$, $b$, $c$ have in-degree $0$ in
	$H_0$. No larger set induces a strongly connected subgraph: any set of
	two or more vertices of an acyclic digraph fails the condition. Weak
	connectivity is immediate.
\end{proof}

For $k = 3$ the parameters of the algorithm are
$t_i = \Theta\!\left(N^{(2^{k-i}-1)/(2^k-1)}\right)$, that is
\begin{equation}\label{eq:params}
	t_1 = \Theta(N^{3/7}), \qquad t_2 = \Theta(N^{1/7}), \qquad t_3 = 1,
\end{equation}
for a total query complexity
$O\!\left(t_1 + t_2\sqrt{N/t_1} + \sqrt{N/t_2}\right) = O(N^{3/7})
	= O\!\left(N^{\frac12 (1 - \frac{1}{2^3-1})}\right)$, as claimed. Note
that $k = 3$ is the smallest value for which the algorithm performs a
genuine inductive step: the loop of step~2 runs for $i = 2$ only, and the
run consists of one uniform sample, one intermediate Grover level, and
the final Grover search.

\subsection{Counterexample A: the semantic marking condition is not
	local}
\label{sec:cex-oracle}

We first record, in fairness, that for $i = k$ the semantic and local
conditions coincide and are decidable with $O(1)$ queries: this is
exactly what makes the $k = 2$ case of Section~3.1 correct.

\begin{lemma}\label{lem:local-ok}
	Let $u_1, \ldots, u_k \in V$. Whether $u_1, \ldots, u_k$ lie in the $k$
	different source components of an $H$-subgraph of $G$ is determined by
	$\bigcup_{j \in [k]} B^+_h(u_j)$, and can be decided with at most
	$k\, d^{\,h}$ queries.
\end{lemma}

\begin{proof}
	In $H$ every vertex is reachable from the union of the source
	components: in the DAG of strongly connected components of $H$, every
	node is reachable from a node of in-degree $0$, and such a node is a
	source component by definition. Moreover, a source component is strongly
	connected, so from any of its vertices one reaches all of it. As
	$\abs{V(H)} = h$, all these paths have length at most $h - 1$. Hence, if
	$\widetilde H$ is a copy of $H$ with $u_j$ in its $j$-th source
	component, then $V(\widetilde H) \subseteq \bigcup_j B^+_h(u_j)$. It
	therefore suffices to run a depth-$h$ BFS from each $u_j$ and to
	enumerate the (constantly many) maps from $V(H)$ into the resulting
	vertex set.
\end{proof}

For $i < k$ this fails, and not because of a poor choice of
implementation: the missing source components $C_{i+1}, \ldots, C_k$ have
no incoming edges in $H$, so they are not reachable from anything already
discovered, and the edges joining them to the discovered part are
\emph{incoming} edges of known vertices, which the unidirectional model
cannot query.

\begin{proposition}\label{prop:oracle}
	Let $H = H_0$, so $k = 3$, and let $i = 2$. Any bounded-error quantum
	algorithm that, given two vertices $u, v$ and query access to an
	$N$-vertex digraph $G$ with out-degree at most $1$, decides whether $u$
	and $v$ lie in two different source components of an $H_0$-subgraph of
	$G$, must make $\Omega(\sqrt N)$ queries in the worst case. Classically,
	$\Omega(N)$ queries are necessary. This holds even when $u$ and $v$ are
	fixed in advance.
\end{proposition}

\begin{proof}
	Fix $N \ge 5$ and put $V = \{p_1, p_2, z^*, w^*\} \cup X$ with
	$X = \{x_1, \ldots, x_{N-4}\}$. Let $G_\varnothing$ have edge set
	$$E_\varnothing = \{\, p_1 \to z^*,\; p_2 \to z^*,\; z^* \to w^* \,\},$$
	and for $\ell \in [N-4]$ let $G_\ell$ have edge set
	$E_\varnothing \cup \{x_\ell \to w^*\}$. Every vertex has out-degree at
	most $1$ in each of these graphs, so all of them are legal inputs.

	In $G_\ell$, the map $a \mapsto p_1$, $b \mapsto p_2$, $z \mapsto z^*$,
	$w \mapsto w^*$, $c \mapsto x_\ell$ is injective and maps each edge of
	$H_0$ to an edge of $G_\ell$, so it is a copy of $H_0$; by
	Lemma~\ref{lem:H0-sources} its source components are
	$\{p_1\}, \{p_2\}, \{x_\ell\}$, and $p_1, p_2$ lie in two different ones.
	The predicate is therefore $1$ on $(p_1, p_2)$.

	In $G_\varnothing$ the predicate is $0$; indeed $G_\varnothing$ is
	$H_0$-free. In any copy of $H_0$ the image of $z$ has in-degree at least
	$2$ (it receives the images of $a$ and $b$) and the image of $w$ has
	in-degree at least $2$ (it receives the images of $z$ and $c$). In
	$G_\varnothing$ the only vertex of in-degree at least $2$ is $z^*$, so
	both images would have to equal $z^*$, contradicting injectivity.

	Finally, $G_\varnothing$ and $G_\ell$ differ in exactly one entry of the
	input oracle, namely $\mathcal O^{\mathrm{out}}(x_\ell, 1)$, which
	returns $w^*$ in $G_\ell$ and $\bot$ in $G_\varnothing$. An algorithm
	deciding the predicate on all these inputs therefore distinguishes
	$G_\varnothing$ from $G_\ell$ for every $\ell$, i.e.\ solves unstructured
	search over $N - 4$ positions with at most one marked position. The claim
	follows from the optimality of Grover search
	(quantumly, $\Omega(\sqrt{N})$) and from the standard randomized
	adversary bound (classically, $\Omega(N)$).
\end{proof}

\begin{remark}
	Proposition~\ref{prop:oracle} contradicts the accounting of the query
	complexity, where the cost of one evaluation of the marking oracle is
	taken to be that of a depth-$h$ BFS, hence $O(1)$. It does not by itself
	refute the algorithm: one may simply replace the semantic condition by
	the local one, which \emph{is} decidable with $O(k\,d^{\,h}) = O(1)$
	queries. Section~\ref{sec:cex-algorithm} shows that this replacement does
	not repair anything, because the algorithm already fails when the
	semantic condition is granted for free.
\end{remark}

\subsection{Counterexample B: the tester fails on the hub instance}
\label{sec:cex-algorithm}

\begin{definition}[Hub instance]\label{def:hub}
	Let $N$ be a multiple of $10$ and $d \ge 1$. The digraph $G_N$ on $N$
	vertices consists of two parts with no edges between them.
	\begin{itemize}
		\item \emph{Honest part.} $N/10$ pairwise vertex-disjoint copies of
		      $H_0$, the $m$-th one on the vertices
		      $a_m, b_m, c_m, z_m, w_m$, using $N/2$ vertices in total.
		\item \emph{Decoy part.} Three vertices $z^*, w^*, c^*$ and a set $P$
		      of $N/2 - 3$ further vertices, with edges
		      $$z^* \to w^*, \qquad c^* \to w^*, \qquad p \to z^*
			      \;\; \text{for every } p \in P .$$
	\end{itemize}
\end{definition}

Every vertex of $G_N$ has out-degree at most $1$, so $G_N$ is a legal
input for every degree bound $d \ge 1$. The in-degree of $z^*$ is
$\abs{P} = N/2 - 3$, which the unidirectional model explicitly permits.

\begin{lemma}[Classification of the copies]\label{lem:copies}
	The copies of $H_0$ in $G_N$ are exactly:
	\begin{enumerate}
		\item[(i)] the $N/10$ honest copies, with source vertex set
		      $\{a_m, b_m, c_m\}$ (up to exchanging the roles of $a$ and $b$);
		\item[(ii)] the \emph{decoy copies}
		      $a \mapsto p,\; b \mapsto p',\; z \mapsto z^*,\; w \mapsto w^*,\;
			      c \mapsto c^*$ for distinct $p, p' \in P$, with source vertex set
		      $\{p, p', c^*\}$.
	\end{enumerate}
	In particular, every copy contained in the decoy part uses $c^*$, so no
	two decoy copies are source-disjoint.
\end{lemma}

\begin{proof}
	Let $\varphi$ be a copy of $H_0$ in $G_N$. As in the proof of
	Proposition~\ref{prop:oracle}, $\varphi(z)$ and $\varphi(w)$ have
	in-degree at least $2$ in $G_N$, and $\varphi(z) \to \varphi(w)$ is an
	edge. The vertices of in-degree at least $2$ in $G_N$ are: $z_m$
	(in-neighbours $a_m, b_m$), $w_m$ (in-neighbours $z_m, c_m$), $z^*$
	(in-neighbours $P$) and $w^*$ (in-neighbours $z^*, c^*$). Among these,
	$w_m$ and $w^*$ have out-degree $0$, so $\varphi(z) \in \{z_m, z^*\}$,
	and since $z_m$ and $z^*$ have out-degree $1$ we get
	$(\varphi(z), \varphi(w)) = (z_m, w_m)$ or $(z^*, w^*)$.

	If $(\varphi(z), \varphi(w)) = (z_m, w_m)$, then $\varphi(a), \varphi(b)$
	are two distinct in-neighbours of $z_m$, hence $\{a_m, b_m\}$, and
	$\varphi(c)$ is an in-neighbour of $w_m$ different from $z_m$, hence
	$c_m$: we obtain the $m$-th honest copy. If
	$(\varphi(z), \varphi(w)) = (z^*, w^*)$, then $\varphi(a), \varphi(b)$
	are two distinct elements of $P$ and $\varphi(c)$ is an in-neighbour of
	$w^*$ different from $z^*$, hence $c^*$: we obtain a decoy copy. The
	source vertex sets follow from Lemma~\ref{lem:H0-sources}.
\end{proof}

\begin{lemma}[Farness]\label{lem:far}
	$G_N$ is $\varepsilon$-far from $H_0$-free for every
	$\varepsilon \le 1/(10d)$.
\end{lemma}

\begin{proof}
	The $N/10$ honest copies are pairwise vertex-disjoint, hence pairwise
	edge-disjoint. Adding edges cannot destroy a copy, so any $H_0$-free
	graph obtained from $G_N$ must delete at least one edge from each of
	them, i.e.\ at least $N/10$ edges. The normalised distance is therefore
	at least $(N/10)/(dN) = 1/(10d)$.
\end{proof}

\begin{lemma}[Marked sets]\label{lem:marked}
	Let $\mathcal S_1 \subseteq V$ with $\mathcal S_1 \cap P \ne \varnothing$.
	Then the set $B_2$ of vertices marked at level $2$ satisfies
	$$P \setminus \mathcal S_1 \;\subseteq\; B_2 \;\subseteq\;
		\bigl(P \cup \{c^*\} \cup \mathcal A\bigr) \setminus \mathcal S_1,
		\qquad \text{where } \abs{\mathcal A} \le 2 \abs{\mathcal S_1},$$
	and this holds for the semantic and for the local marking condition
	alike.
\end{lemma}

\begin{proof}
	Fix $p \in \mathcal S_1 \cap P$. For every $p' \in P \setminus \{p\}$ the
	pair $(p, p')$ lies in two different source components of a decoy copy by
	Lemma~\ref{lem:copies}, so $p'$ is marked semantically; the same copy
	witnesses the local condition. Likewise $c^*$ is marked. Conversely, if
	$v$ is marked then $v$ shares a copy with some $u \in \mathcal S_1$; by
	Lemma~\ref{lem:copies}, either that copy is a decoy one, whence
	$v \in P \cup \{c^*\}$, or it is the honest copy $m$ and
	$u \in \{a_m, b_m, c_m\}$, in which case $v$ is one of the at most two
	remaining source vertices of that copy. Collecting these over
	$u \in \mathcal S_1$ gives the set $\mathcal A$ with
	$\abs{\mathcal A} \le 2\abs{\mathcal S_1}$. For the local condition the
	same enumeration applies, since a partial copy with respect to two source
	components of $H_0$ is a pair $u, v$ with a common out-neighbour $\zeta$
	such that $\zeta$ has an out-neighbour, or a pair whose induced structure
	is $u \to \zeta \to \omega \leftarrow v$; in $G_N$ both force
	$\zeta \in \{z_m, z^*\}$ exactly as above.
\end{proof}

\begin{theorem}\label{thm:failure}
	Fix $d \ge 1$ and $\varepsilon \le 1/(10d)$, and run the algorithm on
	$G_N$ with the parameters~\eqref{eq:params}, granting it the semantic
	marking oracle at unit cost. Then
	$$\Pr[\text{the algorithm outputs \textsc{Accept}}] \;=\; 1 - O(N^{-1/7}),$$
	although $G_N$ is $\varepsilon$-far from $H_0$-free. The same holds for
	the local marking oracle.
\end{theorem}

\begin{proof}
	Write $\mathcal E_1 = \{\mathcal S_1 \cap P \ne \varnothing\}$,
	$\mathcal E_2 = \{\mathcal S_2 \subseteq P\}$ and
	$\mathcal E_3 = \{c^* \notin \mathcal S_1\}$.

	\emph{Step 1: $\Pr[\overline{\mathcal E_1}]$ is exponentially small.}
	$\mathcal S_1$ consists of $t_1$ independent uniform vertices and
	$\abs{P}/N = 1/2 - 3/N$, so
	$\Pr[\overline{\mathcal E_1}] = (1/2 + 3/N)^{t_1} \le 2^{-t_1/2}$ for
	$N$ large. Similarly
	$\Pr[\overline{\mathcal E_3}] \le t_1/N = O(N^{-4/7})$.

	\emph{Step 2: the algorithm does not stop early, and
		$\Pr[\overline{\mathcal E_2} \mid \mathcal E_1] = O(N^{-3/7})$.}
	Condition on $\mathcal E_1$. By Lemma~\ref{lem:marked}, at any moment
	during the level-$2$ loop
	$$\abs{B_2} \;\ge\; \abs{P} - \abs{\mathcal S_1} - t_2
		\;=\; \frac N2 - 3 - t_1 - t_2 \;\ge\; \frac N3$$
	for $N$ large. In particular $\abs{B_2} \ge t_1 \ge t_0$, so by Theorem~2.2
	of the original work each Grover call succeeds with high constant
	probability and returns a uniformly random element of $B_2$; after
	$\Theta(t_2)$ calls the algorithm collects $t_2$ vertices with high
	probability and proceeds to step~3, never reaching the branch that stops
	the loop. Again by Lemma~\ref{lem:marked},
	$$\abs{B_2 \setminus P} \;\le\; 2 t_1 + 1 ,$$
	so each individual call returns a vertex outside $P$ with probability at
	most $(2t_1+1)/(N/3) \le 7 t_1 / N$. A union bound over the
	$\Theta(t_2)$ calls gives
	$$\Pr[\overline{\mathcal E_2} \mid \mathcal E_1]
		\;=\; O\!\left(\frac{t_1 t_2}{N}\right)
		\;=\; O\!\left(N^{\frac37 + \frac17 - 1}\right)
		\;=\; O\!\left(N^{-3/7}\right).$$

	\emph{Step 3: on $\mathcal E_2 \cap \mathcal E_3$ the level-$3$ marked
		set is a singleton.} Let $B_3$ be the set of vertices $v$ for which there
	are $u_1 \in \mathcal S_1$, $u_2 \in \mathcal S_2$ such that
	$u_1, u_2, v$ lie in the three different source components of a copy of
	$H_0$. Fix such a triple and let $\widetilde H$ be the copy. Since
	$u_2 \in \mathcal S_2 \subseteq P$ and $u_2$ is a source vertex of
	$\widetilde H$, Lemma~\ref{lem:copies} forces $\widetilde H$ to be a
	decoy copy, whose source vertex set is $\{u_2, p', c^*\}$ for some
	$p' \in P$. Hence $\{u_1, v\} = \{p', c^*\}$. As $c^* \notin \mathcal S_1$
	by $\mathcal E_3$, we must have $u_1 = p'$ and $v = c^*$. Conversely
	$c^* \in B_3$, taking $u_1 \in \mathcal S_1 \cap P$ and any
	$u_2 \in \mathcal S_2$ distinct from it. Therefore $B_3 = \{c^*\}$ and
	$\abs{B_3} = 1$.

	\emph{Step 4: the final Grover search misses it.} The last step performs
	a Grover search over $V \setminus \mathcal S'_2$ with the budget
	$q = O(\sqrt{N/t_2})$ dictated by the analysis. Each evaluation of the
	marking predicate is one oracle call, and there is a unique marked
	element among $\Theta(N)$ candidates. By the optimality of Grover search,
	any $q$-query algorithm finds a unique marked element with probability
	$O(q^2/N) = O(1/t_2) = O(N^{-1/7})$.

	\emph{Conclusion.} The algorithm outputs \textsc{Reject} only if it
	exhibits a copy of $H_0$ at step~4, hence only if one of the events
	above fails:
	$$\Pr[\textsc{Reject}] \;\le\; 2^{-t_1/2} + O(N^{-3/7}) + O(N^{-4/7})
		+ O(N^{-1/7}) \;=\; O(N^{-1/7}).$$
	For the local marking oracle, Lemma~\ref{lem:marked} gives the same
	$B_2$; and at level $3$ the local and semantic conditions coincide by
	Lemma~\ref{lem:local-ok}, since $i = k$. The bound is unchanged.
\end{proof}

Since a tester must accept an $\varepsilon$-far input with probability at
most $1/3$, and $1 - O(N^{-1/7}) > 1/3$ for $N$ large, the algorithm is
not an $\varepsilon$-tester for $H_0$-freeness. Note that boosting by a
constant number of independent repetitions does not help: one would need
$\Theta(t_2) = \Theta(N^{1/7})$ repetitions, raising the query complexity
to $\Theta(N^{4/7})$.

\begin{remark}[The construction is robust]\label{rem:robust}
	Three natural repairs fail on variants of the same instance.
	\begin{enumerate}
		\item \emph{Changing the oracle} does not help, by
		      Theorem~\ref{thm:failure}.
		\item \emph{Deduplicating by the signature of the partial copy} --
		      keeping at most one collected vertex per distinct image
		      $\{\varphi(z), \varphi(w)\}$ -- fails on the multi-hub variant:
		      take $\sqrt N$ hubs $z_1, \ldots, z_{\sqrt N}$, each with
		      $\Theta(\sqrt N)$ in-neighbours, all of them with a single
		      outgoing edge to a common $w^*$, plus $c^* \to w^*$. The
		      signatures $\{z_l, w^*\}$ are pairwise distinct, so
		      deduplication accepts them all, yet every copy through $w^*$
		      still uses $c^*$ and the level-$3$ marked set is again
		      $\{c^*\}$.
		\item \emph{Reordering the source components} repairs the instance of
		      Definition~\ref{def:hub} (searching for $c$ first leaves no
		      decoy), but the order is fixed in advance by the algorithm,
		      whereas the adversary chooses $G$ afterwards; a symmetrised
		      gadget defeats any fixed order.
	\end{enumerate}
\end{remark}

\begin{remark}[Larger $k$]
	For $k > 3$, replace $H_0$ by the pattern with source components
	$\{a_1\}, \ldots, \{a_{k-1}\}, \{c\}$, edges $a_j \to z$ for
	$j \in [k-1]$, $z \to w$ and $c \to w$, and let the hub $z^*$ have
	$\Theta(N)$ in-neighbours. The same computation applies with the
	parameters~\eqref{eq:params} for the corresponding $k$.
\end{remark}

\subsection{Diagnosis}
\label{sec:diagnosis}

The two counterexamples isolate three independent defects. We state them
in increasing order of severity.

\paragraph{(D1) The cost of the marking oracle.}
The marking condition is stated semantically -- membership in an actual
$H$-subgraph of $G$ -- while its cost is accounted for as that of a
depth-$h$ BFS. The two are consistent when $i = k$, which is the only
case arising for $k = 2$, and this is why Section~3.1 is correct as
written. For $i < k$ they are not, by Proposition~\ref{prop:oracle}. The
defect is one of presentation and is repaired by adopting the local
condition.

\paragraph{(D2) Abundance is not implied by extendability.}
The inductive step of the correctness argument asserts that a constant
fraction of the collected $(i-1)$-partial solutions can be extended to
complete $H$-instances by \emph{disjoint} remaining source components,
and concludes that $\Omega(t_{i-1})$ vertices are marked at the next
level. What the induction actually needs is only the conclusion:
$\abs{B_{i}} = \Omega(t_{i-1})$, since otherwise the budget
$O(\sqrt{N/t_{i-1}})$ of the next Grover search is insufficient. The
implication from the hypothesis to the conclusion requires the
disjointness, and nothing in the algorithm enforces it. In the hub
instance every collected partial solution is extendable -- the hypothesis
holds with constant $1$ -- yet they all extend through the single vertex
$c^*$, and the conclusion fails as badly as possible: $\abs{B_3} = 1$.
Extendability and multiplicity of extensions are distinct properties, and
only the second one propagates the induction.

\paragraph{(D3) The marked set is never bounded from above.}
Even before the disjointness issue, the argument uses the uniformity of
Grover's output to transfer a lower bound on the number of \emph{good}
marked vertices into a lower bound on the number of good vertices
\emph{collected}. This transfer costs a factor $\abs{G_i}/\abs{B_i}$,
and $\abs{B_i}$ is never estimated. In the hub instance
$\abs{G_2} = O(t_1)$ while $\abs{B_2} = \Theta(N)$, so the collected set
contains no good vertex at all with probability $1 - o(1)$. Note that the
base case is not affected: at level $1$ the sampling is uniform over $V$,
and Proposition~3.2 lower-bounds the density of good vertices in $V$.
From level $2$ on the sampling is uniform over the marked set, a
distribution about which Proposition~3.2 says nothing. This is precisely
where the induction changes measure without justification.

\paragraph{Why the analogy with multi-collision finding breaks.}
In the multi-collision algorithm that the construction generalises, a
partial solution is a set of indices carrying a common value, and it is
identified by that value. Distinct values give disjoint extension sets,
and the number of extensions of a partial solution is the multiplicity of
its value; extendability and disjoint extendability therefore coincide,
and the induction is automatic. In digraphs, the extension set of a
partial copy is a set of in-neighbours of a specific vertex, and distinct
partial copies may share it entirely. Unbounded in-degree -- which the
unidirectional model allows, and which is exactly the feature that makes
the problem hard classically -- lets $\Theta(N)$ copies of $H$ funnel
through one vertex.

\paragraph{(D4) Two further inaccuracies.}
Independently of the above, the branch that outputs \textsc{Reject} when
fewer than $t_i$ vertices are found at an intermediate level destroys
completeness: under the semantic condition an $H$-free graph has no
marked vertex at level $2$, so every $H$-free graph would be rejected.
The branch must output \textsc{Accept}, which also makes the tester
one-sided, rejection then occurring only at step~4, where a copy is
exhibited. Moreover, the Grover search of level $i$ should range over
$V \setminus (\mathcal S'_{i-1} \cup \mathcal S_i)$: since the output is
uniform over the marked set, without excluding the vertices already
collected in the current round the same vertex may be returned twice, and
with the parameters~\eqref{eq:params} one has $t_i^2 / t_{i-1} =
	\Theta(1)$, so such repetitions are not negligible.

\subsection{What remains valid}
\label{sec:remains}

None of the above touches the following.
\begin{itemize}
	\item Proposition~3.2, whose proof is correct and which we use
	      throughout.
	\item The case $k = 2$ of Section~3.1, by
	      Lemma~\ref{lem:local-ok}.
	\item The special case of $k$-star-freeness, for which the abundance
	      invariant holds automatically: a centre of in-degree at least $k$
	      makes all of its in-neighbours good, while a centre of in-degree
	      less than $k$ contributes at most $k-2$ marked vertices per
	      sampled vertex, so $\abs{B_i \setminus G_i} = O(t_1)$. This is
	      also the only case for which the matching lower bound is proved.
	\item The lower bound of Theorem~1.2 and the whole of Sections~4
	      and~5.
	\item The query-complexity accounting itself: granted the invariant
	      $\abs{B_i} = \Omega(t_{i-1})$, the budget
	      $O(t_1 + \sum_i t_{i+1}\sqrt{N/t_i})$ and the optimisation
	      leading to~\eqref{eq:params} are correct.
\end{itemize}
In particular, Theorem~1.1 is \emph{not} refuted: what
Theorem~\ref{thm:failure} refutes is the correctness of one specific
algorithm for one specific pattern, and the upper bound may well hold via
a modified algorithm. Recovering it is the subject of the next section.