Quantum Query Lower Bounds and Search Optimality

At an instrument node with outcome maps $({\mathcal{I}}_a{)}_{a\in \mathrm{\Omega }}$, choose a finite Kraus family $(K_{a,r}{)}_r$ for each ${\mathcal{I}}_a$ by [F3]–[F4]. The formula in [F5] shows that their union is a Kraus family for the total map $\mathrm{\Phi }={\sum }_a{\mathcal{I}}_a$. The trace identity in [F3] makes $\mathrm{\Phi }$ trace-preserving, so [F6] gives ${\sum }_{a,r}{K}_{a,r}^{†}{K}_{a,r}=I$.

Label every node of the finite execution tree by the number of oracle calls already made on its path. For each $t<T$, order the finitely many nonoracle nodes in that query-count slice by tree depth, execute each node on histories with its observed-outcome prefix, and use the identity on histories already at their next query or terminal node. This places every next query at one common slot while preserving each branch's transitions; histories that have terminated are inactive in this and every later slot. The retained outcome history identifies the branches that still make a query. On every inactive branch, conditionally swap the caller's entire $N$-level address register with a fresh register of the same dimension initialized to $\mathrm{\mid }0⟩$, and swap the caller's response qubit with a fresh qubit initialized to $\mathrm{\mid }+⟩$, prepared using $H$ from [F11]. The address-register swap is the finite basis permutation exchanging the two ordered register factors; controlling it on the retained history gives a finite input-independent unitary. After the ordinary oracle call, reverse both conditional swaps. On an inactive branch the oracle acts on $\mathrm{\mid }0⟩\mathrm{\mid }+⟩$ as either $I$ or $X$ on the response, both of which fix $\mathrm{\mid }+⟩$; the caller's address and response, including any entanglement with work, are restored. Active branches are unchanged, so this pads the slot without controlled oracle access.

Add a finite label register $L$ with orthonormal basis $\mathrm{\mid }a,r{⟩}_L$ and use the same factor order throughout, defining $V:H\to L\otimes H$ by $V\psi ={\sum }_{a,r}\mathrm{\mid }a,r{⟩}_L\otimes K_{a,r}\psi$. Orthonormality [F9], the adjoint identity [F7], and step 1.1 give $⟨V\psi ,V\varphi ⟩={\sum }_{a,r}⟨K_{a,r}\psi ,K_{a,r}\varphi ⟩=⟨\psi ,\varphi ⟩$; hence $V$ is an isometry. For any density operator $\rho$, projecting the label onto the outcome subspace spanned by $\{\mathrm{\mid }a,r{⟩}_L:r\}$ and discarding the label leaves ${\sum }_r{K}_{a,r}\rho K_{a,r}^{†}$; orthogonality removes all unequal-label cross terms. By [F5] this is exactly ${\mathcal{I}}_a(\rho )$.

In the common codomain $L\otimes H$, let $J\psi =\mathrm{\mid }0{⟩}_L\otimes \psi$ be the clean-ancilla embedding. The images under $J$ and $V$ of one orthonormal basis of $H$ are orthonormal lists of the same finite length in this same finite-dimensional space. Choose a finite spanning basis by [F10]; process it in order, subtracting its projections onto the current list and appending the normalized nonzero remainder. This finite Gram–Schmidt procedure completes each list to an orthonormal basis. Mapping the first completed basis to the second defines a unitary $U$ with $UJ=V$, so the instrument node is realized by an ordinary unitary and retained outcome/Kraus labels.

Keep each observed outcome in an orthogonal record register; hidden Kraus labels remain orthogonal environment labels and are not used by later controls. Induct over the finite execution tree, comparing the unnormalized system density for each observed history after tracing out its hidden labels. A unitary node applies the same branch unitary on every hidden-label subspace, and an instrument node has child reduced density ${\mathcal{I}}_a(\rho )$ by step 2.1, so each history's unnormalized system density agrees with the original instrument computation. At terminal histories, measuring the declared output and ignoring the orthogonal records therefore gives exactly the output law in [F2].

Insert one such ordinary call in each of the $T$ slots, using input-independent history controls for active and padded branches. Steps 1.1–4.1 preserve every output probability, and step 1.2 pads only branches with fewer than $T$ calls. Thus the resulting pure-state circuit has exactly $T$ ordinary XOR calls and the original output distribution.

Applying the displayed $O_x$ twice to a basis vector gives $\mathrm{\mid }j,(b\oplus x_{j+1})\oplus x_{j+1},w⟩=\mathrm{\mid }j,b,w⟩$. Thus it is an involution on the declared product basis.

By [F1], [F2], and [F4], the input and response basis vectors, tensored with any work basis, form a finite orthonormal basis. Step 1.1 shows that $O_x$ permutes this basis, so its linear extension is unitary. For $N=2^n$ it is the standard query in [F3] with the address labeling fixed in the Definition; for general $N$ it is the same XOR permutation on the $N$-level address basis.

For each address $j$, ${\mathrm{\Pi }}_j=\mathrm{\mid }j⟩⟨j\mathrm{\mid }\otimes I$ is self-adjoint and idempotent by [F1]–[F3], so it is an orthogonal projection. If $j\mathrm{\ne }k$, orthogonality gives ${\mathrm{\Pi }}_j{\mathrm{\Pi }}_k=0$.

The address vectors form a complete basis by [F1]–[F2], hence ${\sum }_{j=0}^{N-1}\mathrm{\mid }j⟩⟨j\mathrm{\mid }=I$ and therefore ${\sum }_{j=0}^{N-1}{\mathrm{\Pi }}_j=I$ on address, response, and work registers. If a no-query basis state is adjoined, the same basis expansion includes its projection and the search-address sum is then at most $I$.

By [F1] and [F4], choose an orthonormal eigenbasis $(e_j)$ for $E$. Positivity of $E$ and $I-E$ puts each eigenvalue ${\lambda }_j$ in $[0,1]$. For $w={\sum }_j{w}_j{e}_j$, $\mathrm{\parallel }Ew{\mathrm{\parallel }}^2={\sum }_j{\lambda }_j^2\mathrm{\mid }{w}_j{\mathrm{\mid }}^2\le {\sum }_j\mathrm{\mid }{w}_j{\mathrm{\mid }}^2=\mathrm{\parallel }w{\mathrm{\parallel }}^2$. For a unit $u={\sum }_j{u}_j{e}_j$, [F5]–[F6] give $\mathrm{tr}(P_{u}E)={\sum }_j{\lambda }_j\mathrm{\mid }{u}_j{\mathrm{\mid }}^2=⟨Eu,u⟩$. Thus the same acceptance expectation and contraction estimate hold for every two-outcome POVM.

Put $\delta =\psi -\varphi$. The acceptance-probability difference equals $⟨E\delta ,\psi ⟩+⟨E\varphi ,\delta ⟩$. By [F2], unit normalization, and step 1.1, its absolute value is at most $\mathrm{\parallel }E\delta \mathrm{\parallel }\mathrm{\parallel }\psi \mathrm{\parallel }+\mathrm{\parallel }E\varphi \mathrm{\parallel }\mathrm{\parallel }\delta \mathrm{\parallel }\le 2\mathrm{\parallel }\delta \mathrm{\parallel }$. The probability gap in [F3] is at least $1\mathrm{/}3$, so $\mathrm{\parallel }\psi -\varphi \mathrm{\parallel }\ge 1\mathrm{/}6$.

On each address block other than $i-1$, the two oracle actions in [F1] agree; on block $i-1$, the singleton oracle applies Pauli $X$ to the response and the zero oracle applies identity. Hence $O_{e_i}-O_{0^N}={\mathrm{\Pi }}_{i-1}(X-I){\mathrm{\Pi }}_{i-1}$, where $X-I$ acts on response and identities act on address and work.

The orthogonal projection is contractive and $X$ preserves norm because it permutes the two orthonormal response basis vectors; thus $\mathrm{\parallel }(X-I){\mathrm{\Pi }}_{i-1}\psi \mathrm{\parallel }\le \mathrm{\parallel }X{\mathrm{\Pi }}_{i-1}\psi \mathrm{\parallel }+\mathrm{\parallel }{\mathrm{\Pi }}_{i-1}\psi \mathrm{\parallel }=2\mathrm{\parallel }{\mathrm{\Pi }}_{i-1}\psi \mathrm{\parallel }$. Step 1.1 and idempotence of ${\mathrm{\Pi }}_{i-1}$ give the claimed bound.

If $N=M$, the procedure returns after one direct raw oracle call, which has the required action. Suppose $N<M$. The comparison recurrence maintains $E_r=1$ exactly when the first $r$ bits of $j$ and $N$ agree, and $L_r=1$ exactly when the first differing bit has $j$-bit $0$ and $N$-bit $1$. Induction on $r$ therefore gives $v=L_m=1$ iff $j<N$. The controlled transpositions in [F1] preserve $j$ and $v$ and send a clean $Q_N$ basis state $\mathrm{\mid }0⟩$ to $\mathrm{\mid }j⟩$ when $v=1$ and $j<N$, and leave it at $\mathrm{\mid }0⟩$ otherwise. Thus the raw query address is an $N$-level basis state that equals $j$ on valid padded addresses and $0$ on invalid ones.

In the $N<M$ branch, when $v=1$, [F4] swaps the caller's response $b$ into $r$; the raw oracle then changes it to $b\oplus x_{j+1}$, and reversing the swap returns exactly this bit to the caller and leaves $r=\mathrm{\mid }+⟩$, which the final $H$ maps to $\mathrm{\mid }0⟩$. When $v=0$, the route sets $q=0$, which is valid because $N\ge 1$, while $r=\mathrm{\mid }+⟩$; the raw query applies either $I$ or $X$ to $r$, both of which fix $\mathrm{\mid }+⟩$, and the caller's response is unchanged. The final $H$ again returns $r$ to $\mathrm{\mid }0⟩$.

The raw oracle preserves its address, so the inverse controlled routing permutation clears $Q_N$ after the response swap is undone. By step 1.2 the helper response is then $\mathrm{\mid }+⟩$, so the prescribed $H$ has returned it to $\mathrm{\mid }0⟩$. Reversing the comparison circuit clears $v$ and its work registers. In both branches the resulting action on each padded-address basis state is $\mathrm{\mid }j,b⟩\mapsto \mathrm{\mid }j,b\oplus x_{j+1}⟩$ for $j<N$ and $\mathrm{\mid }j,b⟩\mapsto \mathrm{\mid }j,b⟩$ for $j\ge N$; linearity gives the same zero-completed action on every superposition. Exactly one raw oracle call occurred in either branch, and no controlled call was used.

If $T=0$, both inputs give the same circuit and hence the final vectors agree, so the inequality holds with empty sum. Suppose $T\ge 1$. For each $r=0,\dots ,T$, define $h_r$ as the final state of the circuit that uses the zero oracle in its first $r$ query slots and the $e_i$ oracle in its remaining $T-r$ slots. Then $h_0={\psi }_T^i$ and $h_T={\psi }_T^0$.

For each $1\le r\le T$, the circuits defining $h_{r-1}$ and $h_r$ have the same state immediately before query slot $r$: they have used the zero oracle for the first $r-1$ calls. This pre-query state is ${\psi }_{r-1}^0$. At slot $r$ the oracle changes from $O_{e_i}$ to $O_{0^N}$; after that slot both circuits use the same suffix, whose unitaries preserve norm. By [F2], $\mathrm{\parallel }{h}_{r-1}-h_r\mathrm{\parallel }\le 2\sqrt{q_{r-1,i}}$.

The triangle inequality gives $\mathrm{\parallel }{\psi }_T^i-{\psi }_T^0\mathrm{\parallel }=\mathrm{\parallel }{h}_0-h_T\mathrm{\parallel }\le {\sum }_{r=1}^T\mathrm{\parallel }{h}_{r-1}-h_r\mathrm{\parallel }\le 2{\sum }_{t=0}^{T-1}\sqrt{q_{t,i}}$. The normal form [F1] preserves the output distribution, so this bound applies to the original algorithm's pure-state realization.

If $T=0$, [F1] gives zero distance for every $i$, so the sum is zero. If $T\ge 1$, squaring [F1] and applying [F3] to the real numbers $\sqrt{q_{t,i}}$ gives $\mathrm{\parallel }{\psi }_T^i-{\psi }_T^0{\mathrm{\parallel }}^2\le 4T{\sum }_{t=0}^{T-1}{q}_{t,i}$; each $q_{t,i}$ is nonnegative because it is a squared norm.

Summing over $i$ and interchanging finite sums, completeness and orthogonality in [F2] give ${\sum }_{i=1}^N{q}_{t,i}={\sum }_{j=0}^{N-1}\mathrm{\parallel }{\mathrm{\Pi }}_j{\psi }_t^0{\mathrm{\parallel }}^2=\mathrm{\parallel }{\psi }_t^0{\mathrm{\parallel }}^2=1$ for each $t$. Therefore ${\sum }_i\mathrm{\parallel }{\psi }_T^i-{\psi }_T^0{\mathrm{\parallel }}^2\le 4T{\sum }_{t<T}1=4T^2$.

Since ${\sin }^2\theta =t\mathrm{/}N$, [F5] gives $\cos (2\theta )=1-2t\mathrm{/}N=q$. Define $c_r=\cos (2r\theta )$. Then $c_0=1=T_0(q)$ and $c_1=q=T_1(q)$.

For every integer $r\ge 1$, applying [F3] and [F4] with $x=2r\theta$ and $y=2\theta$ and adding the identities gives $c_{r+1}=2\cos (2\theta )c_r-c_{r-1}=2q{c}_r-c_{r-1}$. This is the same recurrence as $T_r(q)$; the initial values in step 1.1 and induction on $r$ give $c_r=T_r(q)$ for every $r\ge 0$.

Setting $r=2k+1$ in step 2.1 and applying the power-reduction identity [F5] gives $(1-T_{2k+1}(q))\mathrm{/}2=(1-\cos ((4k+2)\theta ))\mathrm{/}2={\sin }^2((2k+1)\theta )$. By [F2] this is the actual Grover success probability.

The procedure of [F1] makes $k$ Grover iterates and one verification. By [F2] each iterate needs one padded bit query, and [F3] replaces every one of those calls and the verification with exactly one raw query. Therefore the total raw query count is at most $K+1$.

Since $K=\lceil \sqrt{M}\rceil \le \sqrt{M}+1$, we have $K+1\le \sqrt{M}+2\le 3\sqrt{M}$ because $M\ge 1$. By [F5], $3\sqrt{M}<3\sqrt{2N}$. Thus the worst-case standard bit-query cost is at most $3\sqrt{2N}$ by [F4]. None of the reversible address tests, classical recurrence steps, or gates were counted as oracle invocations, so this estimate makes no claim about their cost.

Let a bounded-error decision algorithm use $T$ queries. Apply [F2] and use the common final acceptance event. For each $i$, correctness [F5] gives acceptance at least $2\mathrm{/}3$ on $e_i$ and at most $1\mathrm{/}3$ on $0^N$. By [F3], $\mathrm{\parallel }{\psi }_T^i-{\psi }_T^0\mathrm{\parallel }\ge 1\mathrm{/}6$.

Summing the squares of these $N$ inequalities gives $N\mathrm{/}36\le {\sum }_i\mathrm{\parallel }{\psi }_T^i-{\psi }_T^0{\mathrm{\parallel }}^2$. By [F4], the right side is at most $4T^2$, so $T\ge \sqrt{N}\mathrm{/}12$.

Now let a bounded-error finder use $T$ queries. Append a decision step that measures its output and, if it is a coordinate $i$, makes one standard bit query at address $i-1$ with response initialized to $0$; accept exactly when that response is $1$. If the output is none or invalid, reject without a query. On $0^N$ this decision never accepts; on $e_i$ it accepts whenever the finder returns $i$, which has probability at least $2\mathrm{/}3$ by [F1]. This is a bounded-error decision procedure with at most $T+1$ queries, so [F6] and step 2.1 give $T+1\ge \sqrt{N}\mathrm{/}12$.

If $N\ge 576$, then $\sqrt{N}\mathrm{/}12\ge 2$, and step 3.1 gives $T\ge \sqrt{N}\mathrm{/}12-1\ge \sqrt{N}\mathrm{/}24$. If $1\le N<576$, a zero-query finder has the same output law on $0^N$ and $e_1$, yet success would require probability at least $2\mathrm{/}3$ on the disjoint outcomes none and $1$ under this one common law. Their probabilities would sum to at least $4\mathrm{/}3$, impossible; hence $T\ge 1\ge \sqrt{N}\mathrm{/}24$.

If $N=1$, then $M=1$ and the schedule in [F1] includes $k=0$. Its recurrence value is $p_0=(1-(-1))\mathrm{/}2=1$, since $1-2\mathrm{/}M=-1$ and $T_1(q)=q$. The maximizing choice in [F1] has value at least $p_0$, and [F3] identifies every list value with a probability at most $1$, so the selected success probability is $1$. If $N\ge 2$, then $M\ge 2$, so the padded one-mark input in [F5] has ratio $t\mathrm{/}M=1\mathrm{/}M\le 1\mathrm{/}2$.

For $N\ge 2$, [F4] supplies an integer $k\le \lceil \sqrt{M}\rceil$ with actual marked probability at least $1-1\mathrm{/}M$. The recurrence probabilities in [F1] equal these actual probabilities by [F3], so their finite maximizing choice has probability no smaller than that candidate. The $N=1$ case already has probability one by step 1.1.

The simulation in [F2] makes the algorithm's padded Grover evolution exactly the evolution analyzed in step 2.1. Initializing the verification response to $0$ makes its XOR output equal to the queried bit. On a one-mark input, a marked measurement is valid and the final verification returns $1$, so the algorithm returns the correct marked coordinate with probability at least the bound from step 2.1. On $0^N$, every verification query returns $0$, so it returns no with certainty. Finally $M\ge N$ implies $1-1\mathrm{/}M\ge 1-1\mathrm{/}N$.

The lower bound for both tasks is [F1], so each complexity is at least a positive constant times $\sqrt{N}$.

For $N\ge 3$, the one-run success probability in [F2] is at least $1-1\mathrm{/}N\ge 2\mathrm{/}3$. For $N=1$, [F2] gives certainty. For $N=2$, run the fixed-one procedure twice with fresh registers and independent measurements, returning a verified candidate if either run verifies one. Each run has success probability at least $1\mathrm{/}2$ by [F2]; conditional independence of the fresh runs gives failure probability at most $(1-1\mathrm{/}2{)}^2=1\mathrm{/}4$, hence success at least $3\mathrm{/}4$.

Verification prevents a false yes on $0^N$, by [F2] and [F4]. On each singleton input the procedures in step 1.2 return its marked coordinate with probability at least $2\mathrm{/}3$. They are therefore bounded-error solvers for both the decision and finding tasks. The two-run case uses at most twice the cost in [F3], and the other cases use at most one run, so [F5] bounds their worst-case query cost by $6\sqrt{2N}=O(\sqrt{N})$.

Combining steps 1.1 and 2.1 gives matching positive constant lower and upper multiples of $\sqrt{N}$ for both decision and finding. All statements concern standard bit queries; nonoracle gate and preprocessing costs remain separate.