Exact Bernstein–Vazirani Query Complexity in Characteristic-Two Modal Computation

1 Introduction and contribution boundary

Modal quantum theory retains linear state evolution and a possible/impossible distinction while allowing amplitudes in general fields rather than requiring complex amplitudes and Born probabilities [1, 2]. In characteristic two, familiar sign and phase constructions can collapse, but a failed textbook circuit does not by itself determine exact oracle-query complexity. A lower bound must survive alternative preparations, finite ancillas, adaptive branch-dependent operations, and every complete readout allowed by the model.

This note proves such a bound for Bernstein–Vazirani recovery. Let $s\in {𝔽}_2^n$ and $f_s(x)=s\cdot x$. Under the pointwise characteristic-two oracle contract of Section 2, every exact finite adaptive algorithm recovering all $n$ secret bits uses at least $n$ queries. Under the standard XOR oracle, $n$ queries suffice. Thus

within this modal model. The statement is deliberately stronger than a failure of the usual one-query complex-amplitude circuit: the lower bound allows arbitrary finite ancillas, complete recorded instruments, and branch-dependent future operations, and it permits a broader class of fixed pointwise invertible target actions than the QXOR interface used for the matching upper bound.

The closest methodological antecedents make the novelty boundary important. Polynomial query bounds are established in ordinary quantum query complexity [10], and Farhi, Goldstone, Gutmann and Sipser bound the number of Boolean oracles distinguishable with $k$ standard complex quantum queries by a binomial sum [11]. Exact one-query Boolean promise problems containing Deutsch–Jozsa and Bernstein–Vazirani have also been organized directly in the usual complex quantum model [12], while group-theoretic oracle identification is treated more generally by Copeland and Pommersheim [13]. Montanaro studies exact quantum learning of polynomials whose values lie in finite fields, but with ordinary complex-amplitude quantum computation [14]. Finite-field algebra appears in several nearby but different quantum settings. De Beaudrap, Cleve and Watrous give an exact one-query hidden-linear-structure algorithm over $\mathrm{GF}(2^m)$, but the computation uses ordinary complex Hilbert-space amplitudes and a finite-field QFT; the finite field belongs to the oracle/register algebra rather than the amplitude field [4]. Hanson, Ortiz, Sabry and Tai instead study finite-field amplitudes: they explicitly note that the unrestricted two-valued theory cannot express Deutsch’s algorithm, while for suitable odd-characteristic finite-complex fields they report that deterministic algorithms including Bernstein–Vazirani perform as desired (with the BV statement attributed there to unpublished results) [7]. Modular/ring circuit models [5] and systematic treatments of exact quantum query complexity [15] provide further background. These results are important antecedents, but they do not state the characteristic-two amplitude theorem proved here: the degree variables below are the $n$ secret bits themselves, and the exact readout is modal rather than Hilbert-space orthogonality.

Access-model sensitivity is likewise background rather than a novelty claim. Svozil explicitly formulates exact query complexity in terms of both an answer partition and its oracle access and, for Deutsch’s problem in ordinary complex-unitary computation, shows that changing the response unitary can change the exact one-query cost [17]. Our Deutsch discussion should therefore be read as a characteristic-two contract-level refinement, not as the discovery that oracle encodings matter. James, Ortiz and Sabry had already identified the qualitative failure of Deutsch’s usual advantage in their finite-field setting [3].

The main proof has two complementary forms. First, all terminal histories are embedded in one recorded direct sum. After $q$ queries every recorded coefficient is a multilinear polynomial of degree at most $q$ in the secret bits, so $2^n$ exactly distinguishable secrets cannot fit into the degree-$q$ coefficient span when $q<n$. Second, any nonzero coordinate reserved for one output label becomes a Boolean point-indicator polynomial and therefore has degree $n$. Both arguments depend on exact operational readout, not inspection of a symbolic amplitude table.

For context we also prove one-query obstructions for Deutsch and Deutsch–Jozsa under the same pointwise characteristic-two model. A separate appendix studies a chain-ring kickback example to show that nontrivial eigen-information need not produce an invertible Fourier analyzer. Known one-query modal UNIQUE-SAT is retained as a positive control [8]. The finite checks accompanying this note are reproducibility aids and bounded examples; they are not substitutes for the quantified proofs.

2 Access and readout contract

Let $F$ be a field of characteristic two; it need not be finite. The main lower bound is algebraic and therefore also covers infinite characteristic-two fields, although several discrete-quantum antecedents cited below specialize to finite fields. At every node an algorithm has a finite-dimensional $F$-vector space. Its state is a nonzero vector. Independent carriers compose by ${\otimes }_F$. Secret-independent invertible gates and injections, including appending a fixed nonzero ancilla, are allowed.

A complete linear instrument is a finite family

whose combined map $L$ is injective. Equivalently, ${\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{b}ker<!--\; FUNCTION\; APPLICATION\; -->L_b=\{0\}$; this common-kernel condition is the modal analogue already used for unconditional operations in the foundational modal framework [2]. Branch $b$ is possible exactly when $L_{b}v\ne 0$. All branches are retained as classical histories; subsequent operations may depend on the history. Coordinate readout in any complete dual basis is included. There is no probability, normalization, postselection, removal of inconvenient possible branches, or free access to a coefficient list.

An algorithm is a finite tree with a secret-independent nonzero root preparation. The tree is syntactic and secret-independent: every recorded history is a fixed node whether or not that history is possible for a particular secret, and an impossible history is represented by the zero vector in that node space. Every terminal branch has an output label. Exactness means that, for each promised oracle, every possible terminal label is correct. The query bound is the maximum number of oracle calls on a root-to-leaf path, including paths impossible for some secrets. Terminal internal states may be retained. Query complexity here counts only oracle uses, not the number of secret-independent gates or the dimension of retained workspace.

For a Boolean function $f$ on a finite address set $X$, a query node acts on address sectors as

The target $W$ may include finite working space; untouched ancillas tensor with the identity. At each recorded node the pair $(G_0,G_1)$ is fixed independently of $x$ and of the hidden oracle. Different recorded nodes may use different fixed pairs, copied to appropriate ancillas and surrounded by secret-independent preprocessing. This node-wise generality is allowed in the lower bounds. Inverse access, if separately supplied, has the same affine Boolean dependence and does not change those lower bounds.

The matching upper bounds use the standard XOR interface, denoted QXOR:

Here $G_0=I$ and $G_1=X=\left(\begin{array}{cc}0& 1\\ 1& 0\\ \end{array}\right)$on a two-dimensional target. The bit labels are embedded in $F$. These upper bounds are not asserted for arbitrary invertible pairs: if $G_0=G_1$, every oracle is identical and no nonconstant property can be recovered with any number of queries.

The singleton version is the familiar modal fact that linearly independent states can be perfectly distinguished, whereas a dependent family cannot [9]; Lemma 2.1 is the label-span form needed below.

3 Main result: exact Bernstein–Vazirani recovery

The secret is $s\in {𝔽}_2^n$ and

Exact success means recovering the entire secret $s$.

The obstruction already appears for two secret bits. For $n=2$ and one query, Lemma 3.1 has the form

Summing the four records over $(s_1,s_2)\in {𝔽}_2^2$ gives zero: each coefficient occurs an even number of times. Exact recovery would place the four nonzero records in four disjoint output-label subspaces, hence make them linearly independent. The displayed dependence is therefore impossible. The general proof replaces this four-state relation by the dimension count $D(n,q)<2^n$.

Alternative point-indicator proof. Fix a secret $s^{\star }$. Since ${\mathrm{\Psi }}_{s^{\star }}\ne 0$ in its own output-label block, choose one coordinate functional on that block with value $a\ne 0$ on ${\mathrm{\Psi }}_{s^{\star }}$. Applied to (2), it gives a multilinear polynomial $p(s)$ of degree at most $q$. Exactness forces $p(s)=0$ for every $s\ne s^{\star }$ and $p(s^{\star })=a$. Multilinear polynomials have unique evaluations on the Boolean cube, so

Its coefficient of $s_1\cdots s_n$ is $a\ne 0$, so $deg<!--\; FUNCTION\; APPLICATION\; -->p=n$. Therefore $q\ge n$. This proof is a useful cross-check of the dimension argument, not a claim of a new general polynomial method; point-indicator and nondeterministic polynomial ideas have extensive antecedents in ordinary query complexity [10, 16].

The characteristic-two dependence is essential to this proof. The parity $s\cdot x$ is the degree-one scalar sum ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_j{s}_j{x}_j$ in $F$, so each pointwise query is affine linear in the $n$ secret bits. In ordinary complex-amplitude quantum computation, the standard BV phase is ${(-1)}^{s\cdot x}$ and the one-query algorithm is available; one cannot replace that multiplicative sign character by the scalar sum used above. The result therefore does not contradict the standard one-query BV algorithm or the one-query exact promise-problem classifications in the complex model [12].

The coefficient-span bound is structurally related to ordinary polynomial and oracle-identification bounds, but its parameterization is different. Farhi et al. treat the truth-table values of a Boolean oracle as variables and obtain a binomial bound in the address-domain size [11]. Here the promised BV family makes every truth-table entry a characteristic-two linear form in only $n$ secret bits; the degree-$q$ space therefore has dimension ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{j\le q}\left(\genfrac{}{}{0.0pt}{}{n}{j}\right)$. This promise-specific collapse is what yields $q\ge n$ even though ordinary complex BV is solvable with one query.

4 Deutsch and Deutsch–Jozsa as related access obstructions

The following results are included to mark the same access/readout boundary on familiar promise problems. Their role is secondary to Theorem 3.2. The qualitative finite-field Deutsch obstruction is known [3], and the broader principle that exact query cost can change with the response unitary is explicit in recent ordinary complex-unitary work [17].

The case $n=1$ is Deutsch. The theorem does not establish the optimal multi-query complexity for larger $n$. Failure of the conventional Hadamard circuit is a weaker statement than the quantified one-query obstruction proved here; neither statement is an all-search impossibility theorem.

5 Discussion, prior art, and limitations

The contribution is best viewed as a focused exact-query result rather than a new general theory of oracle access. The most relevant comparisons are summarized in Table 2. In particular, Svozil’s access-dependent Deutsch analysis makes clear that response-unitary sensitivity is not unique to characteristic-two modal computation [17]. Farhi et al. and Beals et al. establish the broader polynomial/dimension methodology in standard quantum query complexity [11, 10]. The narrower point here is that, under modal amplitudes of characteristic two, the BV promise turns each oracle query into an affine degree-one operation in the secret bits, and exact modal recovery then forces degree $n$ even with finite adaptive complete readout.

A final theorem-level search through 27 September 2026, including the closest modal/discrete, exact-query, polynomial-method, finite-field-QFT, and oracle-identification literature, did not locate a prior theorem with the full combination used in Theorem 3.2: characteristic-two amplitudes, exact recovery of all BV secrets, arbitrary finite ancillas, finite adaptive complete recorded instruments, and the stated pointwise invertible lower-bound interface. The closest finite-field hits separate cleanly by model: Hanson et al. use finite-field amplitudes but place their positive BV discussion in suitable odd characteristic and attribute the specific BV behavior there to unpublished results [7], whereas de Beaudrap, Cleve and Watrous use ordinary complex amplitudes for a different hidden-linear-structure oracle over $\mathrm{GF}(2^m)$ [4]. This evidence supports treating Theorem 3.2 as a differentiated specialization. It does not certify historical firstness, and no such firstness claim is made.

The theorem is significant chiefly because it converts a qualitative loss of familiar phase structure into a sharp, model-robust exact query cost. The one-query complex BV algorithm is not merely unavailable in its textbook form: within the stated characteristic-two modal contract, no alternative finite adaptive exact algorithm can reduce the QXOR cost below $n$. At the same time, known one-query modal UNIQUE-SAT [8] shows that the model is not uniformly query-weak; the obstruction is task- and access-specific.

Several limitations should remain explicit. The theorem concerns exact all-branches-correct output, not bounded-error or probabilistic success. It assumes a finite adaptive tree, not unbounded stopping. It permits only secret-independent linear state transformations between queries. The matching upper bound is for QXOR, not every pair $(G_0,G_1)$. The Deutsch–Jozsa theorem is only a one-query obstruction. No general Simon or unstructured-search lower bound is claimed. The ring calculation in Appendix A is a separate algebraic boundary and is not an automatic extension of the field theorem.

A Ring-valued kickback boundary

This appendix changes scalar domains explicitly: set $A=𝔽2[u]∕(u4)$, use free $A$-modules, balance tensors over $A$, admit invertible $A$-linear gates, and test possibility by nonzero contraction. It is a worked algebraic boundary, not an automatic extension of the field-query lower bounds to all ring algorithms. Let $R=1+u$ and $z=R^2=1+u^2$, so $R^4=z^2=1$.

The character obstruction is elementary. A multiplicative character of $C_2^n$ into a characteristic-two field satisfies $a^2=1$, hence ${(a+1)}^2=0$ and $a=1$. Over $A$, unit-valued characters can be nontrivial, but every value reduces to $1$ modulo $(u)$. A square character matrix of size greater than one therefore reduces to the all-ones matrix and has nonunit determinant. This concerns an order-two group in characteristic two, not all finite-field transforms or odd-order groups.

The standard two-level flip does not admit a primitive eigenvector with eigenvalue $R$. Indeed, if $\mathit{X\eta }=\mathit{R\eta }$, then $\eta =X^2\eta =R^2\eta$, hence $u^2\eta =0$; that is impossible if either coordinate of $\eta$ is a unit. Nonprimitive eigenvectors can nevertheless exist. For example

but neither coordinate is a unit. This distinction corrects the potentially misleading shorthand that “$R$ is not an eigenvalue.”

A four-level cyclic shift $T|j⟩=|j+1mod4⟩$ does admit the primitive eigenvector with coordinates $R^{-j}$ and eigenvalue $R$. The controlled oracle $T^{f(x)}$ is a different access primitive. In particular $R^{a\oplus b}$ need not equal $R^a{R}^b$: take $a=b=1$. A generic clean compute–control–uncompute construction uses two standard XOR calls, so one such synthesized cyclic oracle must not be silently charged as one QXOR query. This statement concerns that construction; it is not a universal lower bound on every possible implementation of the cyclic access primitive.

Finally, literal binary expansion of an $A$-target is not permission to move its scalar action onto an independent binary control register. Under ${\otimes }_A$ scalars are balanced; under ${\otimes }_{{𝔽}_2}$ only binary scalars are. Equality of two nonzero simple binary tensors forces equality of both factors, since the only nonzero binary scalar is $1$. Kickback calculations must retain their tensor base.

B Positive control, finite checks, and reproducibility

The known one-query UNIQUE-SAT protocol of Willcock and Sabry [8] applies to the promise of no marked address or exactly one. It uses the same QXOR interface with $O(n)$ other gates. Its existence prevents interpreting the preceding obstructions as the claim that characteristic-two modal computation has no query advantages.

For completeness, one can check the protocol algebraically. Put $S=\left(\begin{array}{cc}1& 0\\ 1& 1\\ \end{array}\right)$and useits transpose $S^T$ on the target. Starting at zero, apply $S$ to every address bit, query, apply $S$ to every address bit again, then apply $S^T$ to the target, flip every address bit conditional on target $1$, and apply $S^T$ again. With no marked point the final state is the all-zero basis vector. With a single marked point $a$ it is

The address factor has coefficient one at $0^n$, so the all-zero coefficient cancels. The state is nonzero because all gates are invertible. Thus a complete coordinate readout distinguishes the promise cases exactly. This is a reproduction and notation-level verification of the cited construction, not a new algorithm.

The accompanying supplement contains two evidence layers. First, the recovered portfolio reproduction supplement preserves the original runner, pinned requirements, provenance, input/output hashes, and a completed full-run manifest. Second, a P02-targeted rerun package executes the independent checks, oracle-contract checker, and the capability stages that generate the data used below. The targeted package also includes a new deterministic table generator whose input is the package-local phase JSON; it is clearly marked as a reconstruction and is not represented as the missing historical complete_p02.py script.

The description-readout ablation illustrates why a symbolic state description is not free readout. It forms the coefficient representation of ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_x|x,f(x)⟩$ and then inspects it classically; under that stronger interface, the small supplied DJ and BV instances expose the answer after one algebraic oracle application. Constructing the same description with a classical point oracle requires querying its addresses, and printing a full support table carries output cost. The ablation therefore identifies a changed access model, not a speedup under Section 2.

The Simon scan is similarly bounded evidence only. Conventional sign/diffusion formulas also collapse in characteristic two, but neither observation supplies a general Simon or search lower bound. The quantified claims of this paper rest on the proofs, while the supplement records executable checks of finite instances, algebra identities, data provenance, and the generated appendix table.

References