PROSE AID ONLY — use PDF/page images and exact source for mathematics.

PDF PAGE 1
Exact Bernstein–Vazirani Query Complexity in Characteristic-Two
Modal Computation
Adaptive complete readout, oracle contracts, and related obstructions
Brian Theory
Revised research draft, 27 September 2026
Abstract
We study exact oracle-query complexity for linear modal computation over fields of char-
acteristic two under an explicit operational contract: finite-dimensional state spaces, arbitrary
finite ancillas, finite adaptive trees, and complete recorded linear instruments with every possible
terminal label required to be correct. The main result is an exact Bernstein–Vazirani bound.
Recovering ann-bit secret requires at leastn pointwise queries even when the fixed invertible
target actions may vary with recorded history, while the standard XOR interface attains the
bound withn queries. The lower bound follows from a recorded-branch multilinear expansion
whose degree grows by at most one per query; we also give a point-indicator proof and a worked
two-bit example. Related results show that one query cannot solve Deutsch or distinguish con-
stant from balanced Deutsch–Jozsa promises under the same characteristic-two pointwise model.
General dependence of query complexity on oracle access, polynomial lower-bound methods, and
exact oracle-identification bounds have substantial prior antecedents; the contribution claimed
here is the narrower characteristic-two exact theorem under the stated adaptive modal readout
contract, not those general ideas. Appendices isolate a ring-valued kickback example and provide
reproducible finite checks.
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. Lets∈ Fn
2 and fs(x) =s·x.
Under the pointwise characteristic-two oracle contract of Section 2, every exact finite adaptive
algorithm recovering alln secret bits uses at leastn queries. Under the standard XOR oracle,n
queries suffice. Thus
QQXOR
exact (BVn) =n
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
1

PDF PAGE 2
and Sipser bound the number of Boolean oracles distinguishable withk 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 whosevalues 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 overGF(2m), 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 then 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. Afterq queries every recorded coefficient is a multilinear polynomial of
degree at mostq in the secret bits, so2n exactly distinguishable secrets cannot fit into the degree-q
coefficient span whenq <n. Second, any nonzero coordinate reserved for one output label becomes
a Boolean point-indicator polynomial and therefore has degreen. 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-dimensionalF-vector
space. Its state is a nonzero vector. Independent carriers compose by⊗F. Secret-independent
invertible gates and injections, including appending a fixed nonzero ancilla, are allowed.
2

PDF PAGE 3
A complete linear instrument is a finite family
Lb :V −→Vb, L :V −→
⨁
b
Vb, v ↦−→(Lbv)b,
whose combined mapL is injective. Equivalently,⋂
b kerLb ={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 whenLbv̸= 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 functionf on a finite address setX, a query node acts on address sectors as
Of =
⨁
x∈X
Gf (x), G 0,G 1∈ GL(W ). (1)
The targetW may include finite working space; untouched ancillas tensor with the identity. At
each recorded node the pair(G0,G 1) is fixed independently ofx 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 thestandard XOR interface, denoted QXOR:
Of|x,y,a⟩ =|x,y +f(x),a⟩, y ∈ F2.
Here G0 =I and G1 =X = ( 0 1
1 0 ) on a two-dimensional target. The bit labels are embedded in
F. These upper bounds are not asserted for arbitrary invertible pairs: ifG0 =G1, every oracle is
identical and no nonconstant property can be recovered with any number of queries.
Secret-independent preparation−→pointwise oracleOf−→complete instrument(Lb)b−→
recorded histories.
Each history chooses its next secret-independent map or query. All terminal histories are
retained in⨁
hVh and grouped by output label.
Separate ablation: inspecting the full coefficient description of a state. This extra access is
excluded from the operational query contract.
Figure 1: The access/readout boundary. The arrows denote linear maps and recorded outcomes,
not stochastic transitions.
Lemma 2.1 (Exact discrimination). LetSi⊂V\{ 0} be nonempty sets with required labelsi, and
Ui = spanFSi. A complete linear readout exactly distinguishes these labels if and only if∑
iUi is a
direct sum.
3

PDF PAGE 4
Proof. Record every output of the readout in a direct sum, grouping output spaces by label. Each
state inSi has zero components in every other label group. Linearity gives the same property for
Ui. An injective map taking theUi into disjoint coordinate groups forces their sum to be direct.
Conversely choose bases of theUi, concatenate them, and extend to a basis ofV. The dual-basis
readout, with the corresponding label on each coordinate, distinguishes the sets. Unused coordinates
may receive any label.
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.
Lemma 2.2 (Complete recorded evolution). A finite secret-independent tree of complete instruments
and injective gates induces an injective linear map from its root space into the direct sum of its
terminal spaces. For any fixed oracle, an algorithm satisfying the contract has a nonzero total
terminal record.
Proof. At a terminal node use the identity. Induct upward. If the descendant mapsTb are injective,
the compositev↦→(TbLbv)b is injective because the instrument’s combined map is injective. Injective
gates and fixed invertible oracle calls preserve this property. This induction applies separately to
every fixed oracle, including when some individual branches vanish. Early termination is represented
by a terminal block in the same direct sum; a branch impossible for one secret contributes a zero
block rather than disappearing from the common record space.
3 Main result: exact Bernstein–Vazirani recovery
The secret iss∈ Fn
2 and
fs(x) =s·x =
n∑
j=1
sjxj (mod 2), x ∈ Fn
2.
Exact success means recovering the entire secrets.
Lemma 3.1 (Recorded monomial bound). For every nodeu in the fixed algorithm tree, letd(u) be
the number of query nodes on the root-to-u path and letψu(s) denote the branch state there, with
ψu(s) = 0 when that history is impossible for secrets. Then ψu(s) is a vector-valued multilinear
function of the secret bits of degree at mostd(u). Consequently, for an algorithm with at mostq
queries, its total terminal recordΨs can be written
Ψs =
∑
J⊆{1,...,n}
|J|≤q

∏
j∈J
sj

cJ (2)
in a fixed finite direct sum of terminal spaces, with coefficient vectorscJ independent ofs.
Proof. Work with polynomial functions on the Boolean cube, equivalently in the quotient
F [s1,...,s n]/(s2
1−s1,...,s 2
n−sn),
so replacings2
j bysj preserves every evaluation and never increases degree. We prove the node-local
statement directly on the fixed syntactic tree. The root state is constant, hence has degree zero.
4

PDF PAGE 5
A secret-independent linear gate, injection, or instrument componentLb acts coefficientwise on a
vector-valued polynomial and cannot increase its degree. In particular, the child state at a recorded
instrument outcome is always the formal vectorLbψu(s); whether this vector evaluates to zero for
a particular secret is a semantic statement about branch possibility, not a nonlinear selector that
changes the tree or the map.
At a query node, on Boolean inputs and in characteristic two,
fs(x) =
n∑
j=1
sjxj
as a scalar equality inF. SinceGb =G0 +b(G0 +G1) for b∈{ 0, 1},
Os =O0 +
n∑
j=1
sjAj, A j =
⨁
x
xj(G0 +G1),
where G0,G 1 and hence theAj are the matrices fixed at that recorded node. Applying this affine
degree-one operator to a branch state of degree at mostd(u) gives degree at mostd(u) + 1. Thus
induction over the tree provesdegψu≤d(u) at every node, including nodes reached only for some
secrets. Recorded-history dependence causes different nodes to carry different fixed maps; it does
not introduce a secret-dependent map inside any node.
Every terminal state therefore has degree at most its query depth, at mostq. Taking their
direct sum and concatenating coefficients of the same monomial gives(2). Early termination merely
contributes a terminal block at smaller degree. Arbitrary finite ancillas enlarge coefficient vectors but
create no additional monomials. If inverse queries are separately supplied,G−1
b =G−1
0 +b(G−1
0 +G−1
1 )
on b∈{ 0, 1}, so the same induction applies.
Theorem 3.2 (Exact characteristic-two Bernstein–Vazirani bound). LetF be any field of charac-
teristic two. Consider a finite adaptive algorithm satisfying Section 2, with arbitrary finite ancillas
and with each oracle node using a fixed pointwise invertible pair independent of the secret. If the
algorithm exactly recovers everys∈ Fn
2 with worst-caseq queries, thenq≥ n. Under standard
QXOR access,n queries suffice. Hence
QQXOR
exact (BVn) =n.
Proof. The terminal spaces are grouped by output labels. Exactness putsΨs entirely in its own label
group, and Lemma 2.2 makes it nonzero. The2n vectors Ψs are consequently linearly independent.
This conclusion already includes any information carried by the classical history: the history is a
direct-sum coordinate ofΨs, and a secret-dependent pattern of zero and nonzero branches cannot
create vectors outside the coefficient span of Lemma 3.1. By that lemma, the records lie in the span
of at most
D(n,q ) =
min(q,n)∑
j=0
(
n
j
)
coefficient vectors. Forq <n, D(n,q )< 2n, a contradiction. For the upper bound, standard XOR
queries at then unit addressesej givefs(ej) =sj on separate basis targets. Retaining those targets
and reading them in the basis recoverss exactly.
5

PDF PAGE 6
The obstruction already appears for two secret bits. Forn = 2 and one query, Lemma 3.1
has the form
Ψs1s2 =c∅ +s1c1 +s2c2.
Summing the four records over(s1,s 2)∈ F2
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 countD(n,q )< 2n.
Alternative point-indicator proof. Fix a secrets⋆. Since Ψs⋆̸= 0 in its own output-label
block, choose one coordinate functional on that block with valuea̸= 0 on Ψs⋆. Applied to(2), it
gives a multilinear polynomialp(s) of degree at mostq. Exactness forcesp(s) = 0 for everys̸=s⋆
and p(s⋆) =a. Multilinear polynomials have unique evaluations on the Boolean cube, so
p(s) =a
∏
j:s⋆
j =1
sj
∏
j:s⋆
j =0
(1 +sj).
Its coefficient ofs1··· sn is a̸= 0, so degp =n. Thereforeq≥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 paritys·x is the degree-one
scalar sum∑
jsjxj in F, so each pointwise query is affine linear in then secret bits. In ordinary
complex-amplitude quantum computation, the standard BV phase is(−1)s·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 onlyn secret bits; the
degree-q space therefore has dimension∑
j≤q
(n
j
)
. This promise-specific collapse is what yieldsq≥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].
Theorem 4.1 (Deutsch). Under (1), no exact algorithm using at most one query determines
f(0) +f(1). Under QXOR the exact query complexity is two.
Proof. First consider a fixed nonzero prequery state, written in address sectors(a0,a 1), including
the target and ancilla coordinates. Writevij for the state after the oracle withf(0) =i,f (1) =j,
and put ∆ =G0 +G1. In characteristic two,
v00 +v11 =v01 +v10 = (∆a0, ∆a1) =w.
If w̸= 0, the constant-state span and balanced-state span have a nonzero intersection. Lemma 2.1
excludes an exact subsequent complete readout. Ifw = 0, the two sector differences vanish separately,
6

PDF PAGE 7
so all fourvij are identical. They are nonzero because the oracle is invertible; discrimination is
again impossible. An arbitrary query-free continuation is an injective recorded map by Lemma 2.2
and cannot remove either obstruction.
For an adaptive algorithm with at most one query, unfold its finite query-free prefix. Its branches
have states independent off, with at least one nonzero state. A nonzero terminal branch in that
prefix would give the same possible answer for everyf, violating exactness. Thus some nonzero
prefix branch reaches a query. Conditional on this branch, the preceding argument applies to its
nonzero state and query-free continuation. Since every possible branch must be correct, the whole
algorithm is impossible.
For the upper bound, query0 and 1 on basis states into separate initialized targets, retain both
answers, and label their basis readout by their XOR. Exactly two standard oracle calls suffice.
Theorem 4.2 (Deutsch–Jozsa, one-query obstruction). Forn≥ 2 and N = 2n addresses, no exact
one-query algorithm with fixed invertible pointwise actions distinguishes constant from balanced
Boolean functions. Under QXOR,
2≤Qexact(DJn)≤N/2 + 1.
Proof. Partition the addresses into four equally sized nonempty blocksA,B,C,D . LetfAB,f AC,f BC
be the indicator functions of the named unions. They are balanced and their pointwise XOR is zero.
Each oracle block isG0 +f(x)(G0 +G1), so
OfAB +OfAC +OfBC =O0.
Applied to any nonzero preparation, the constant-zero state, which is nonzero, lies in the balanced-
state span. Lemma 2.1 rules out exact readout. The same query-free-prefix argument as in
Theorem 4.1 covers arbitrary finite adaptivity. For the upper bound, queryN/2 + 1 distinct
addresses on basis states and retain the answers. Under the promise, agreement implies constancy
and any disagreement implies balance.
The casen = 1 is Deutsch. The theorem does not establish the optimal multi-query complexity
for largern. 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 thesecret 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
7

PDF PAGE 8
Task Lower bound QXOR upper Scope
Deutsch 2 2 Theorem 4.1; the qualitative
obstruction has prior antecedents.
DJ, n≥ 2 2 2 n−1 + 1 Theorem 4.2; the general exact
optimum remains open here.
BV n n Theorem 3.2; arbitrary finite ancillas
and finite adaptive complete recorded
histories.
Simon No general bound Not studied Appendix B reports only a specified
one-query n = 2 scan.
Table 1: Proved bounds. The lower bounds allow fixed pointwise invertible actions at each recorded
query node; every displayed matching or finite upper bound uses standard QXOR.
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 overGF(2m) [4]. This evidence supports treating Theorem 3.2 as a
differentiated specialization. It doesnot 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 belown. 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(G0,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: setA = F2[u]/(u4), use freeA-modules, balance
tensors overA, admit invertibleA-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. LetR = 1 +u and z =R2 = 1 +u2, soR4 =z2 = 1.
Proposition A.1. Forχ = (1,z )T and the standard target flipX, Xχ =zχ. Nevertheless
Hz =
(
1 1
1 z
)
∼ diag(1,u 2)
is singular. Itsn-fold tensor overA, viewed by regular representation overF2, has rank4 + 2n for
n≥ 1 and dimension 4· 2n.
8

PDF PAGE 9
Source Setting Closest antecedent Distinction of this note
Schumacher–
Westmoreland [1, 2]
Modal linear theory over
general fields
Possible/impossible outcomes;
complete operations
Supplies the model background, not
the BV query theorem.
James–Ortiz–Sabry;
Hanson et al. [3, 7]
Finite-field/discrete
quantum amplitudes
F2 qualitative Deutsch
obstruction; reported BV
behavior in suitable odd
characteristic (with that BV
statement attributed there to
unpublished results)
Closest amplitude-field antecedents,
but not the characteristic-two
adaptive exact BV lower bound.
Beals et al.; Farhi et
al. [10, 11]
Standard complex
quantum queries
Degree-per-query and
function-identification
dimension bounds
Their variables and Hilbert-space
readout differ; standard complex
BV remains one-query.
De Beaudrap–Cleve–
Watrous [4]
Complex quantum
algorithm with finite-field
oracle algebra
Exact one-query recovery of
hidden linear structure over
GF(2m)
Finite field labels the oracle/register
structure; amplitudes and readout
remain ordinary complex quantum.
Combarro et al.;
Copeland–
Pommersheim
[12, 13]
Standard complex exact
oracle identification
BV/DJ promise families and
general oracle identification
Different scalar and measurement
models; no characteristic-two
adaptive BV theorem.
Montanaro [14] Complex quantum
learning of
finite-field-valued
polynomials
Exact learning with finite-field
function values
The finite field occurs in the
oracle’s function values, not in the
amplitude field.
Svozil [17] Complex-unitary exact
query theory
Query cost depends on answer
partition and oracle response;
Deutsch response-unitary
criterion
Strong antecedent for access-model
framing; not a characteristic-two
modal amplitude result.
Table 2: Closest methodological and model antecedents. The table is intended to delimit, rather
than inflate, the contribution.
Proof. Xχ = (z, 1)T =z(1,z )T. Adding the first row to the second and then the first column to
the second gives the displayed diagonal form; these are invertible elementary operations. Tensoring
those operations gives diagonal factorsu2k, one for each subset ofk positions. Sinceu4 = 0, only
k = 0, 1 contribute. Multiplication by1 on A has binary rank four; multiplication byu2 has rank
two. There is one first factor andn second factors, giving4 + 2n.
n A dimension Binary dimension Binary rank
1 2 8 6
2 4 16 8
3 8 32 10
4 16 64 12
5 32 128 14
6 64 256 16
Table 3: Finite checks of the balanced-A analyzer in Proposition A.1. Values are generated from
the package-local rerun JSON forn = 1,..., 6. This is a rank table, not a probability distribution.
The character obstruction is elementary. A multiplicative character ofCn
2 into a characteristic-
two field satisfiesa2 = 1, hence (a + 1)2 = 0 and a = 1. Over A, unit-valued characters can be
nontrivial, but every value reduces to1 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 aprimitive eigenvectorwith eigenvalueR. Indeed, if
9

PDF PAGE 10
Xη =Rη, thenη =X 2η =R2η, henceu2η = 0; that is impossible if either coordinate ofη is a unit.
Nonprimitive eigenvectors can nevertheless exist. For example
η = (u2, u2 +u3)T̸= 0 satisfies Xη =Rη,
but neither coordinate is a unit. This distinction corrects the potentially misleading shorthand that
“R is not an eigenvalue.”
A four-level cyclic shiftT|j⟩ =|j+1 mod 4⟩does admit the primitive eigenvector with coordinates
R−j and eigenvalueR. The controlled oracleT f (x) is a different access primitive. In particularRa⊕b
need not equalRaRb: takea =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 anA-target is not permission to move its scalar action onto
an independent binary control register. Under⊗A scalars are balanced; under⊗F2 only binary
scalars are. Equality of two nonzero simple binary tensors forces equality of both factors, since the
only nonzero binary scalar is1. 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 withO(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. PutS = ( 1 0
1 1 ) and use its transpose
ST on the target. Starting at zero, applyS to every address bit, query, applyS to every address
bit again, then applyST to the target, flip every address bit conditional on target1, and applyST
again. With no marked point the final state is the all-zero basis vector. With a single marked point
a it is
|0⟩|0n⟩ +|+⟩X⊗nS⊗n|a⟩, |+⟩ =|0⟩ +|1⟩.
The address factor has coefficient one at0n, 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 repro-
duction 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.
10

PDF PAGE 11
Record Actual scope
Deutsch preparations Exhaustive 15 and 255 nonzero binary preparations in dimensions 4
and 8 for the specified standard one-query oracle.
Oracle-contract checker 552 degenerate oracle matrices with G0 =G1, for address-bit sizes
n = 1, 2, 3 and two shared target permutations. This is not an
enumeration of all algorithms; identical oracle operators give the
unbounded degeneracy immediately.
BV oracle identities Standard-XOR checks for 126 secrets over n = 1,..., 6, together
with smaller recorded operator-span checks. The generaln theorem
comes from Section 3.
UNIQUE-SAT 132 promised instances for n = 1,..., 6, reproducing the known
protocol.
Simon scan 65,535 nonzero preparations in dimension 16, one query, no ancilla,
n = 2, 36 standard oracles and three hidden shifts; no exact
preparation found. No larger or adaptive theorem is inferred.
Phase ranks n = 1,..., 6 agree with 4 + 2n; the standard-flip search finds no
primitiveR eigenvector among 192 primitive candidates, while the
nonprimitive distinction is handled analytically above.
Description-readout ablation Forms and inspects the full coefficient description on supplied small
DJ/BV cases. This deliberately changes the access/readout model
and is not an operational modal algorithm.
Adaptive-tree stress check 400 generated F2 fixed-tree protocols atn = 3, worst-caseq = 2,
with branch-specific second queries, secret-dependent zero branches,
and 200 early-termination cases. Every coordinate had
algebraic-normal-form degree at most 2 and every eight-secret
record matrix had rank at most 7. This is finite stress evidence
only; Lemma 3.1 is the proof.
The description-readout ablation illustrates why a symbolic state description is not free readout.
It forms the coefficient representation of∑
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
[1] B. Schumacher and M. D. Westmoreland, “Modal Quantum Theory,”Foundations of Physics42
(2012), 918–925. https://doi.org/10.1007/s10701-012-9650-z. Preprint: https://arxiv.
org/abs/1010.2929.
[2] B. Schumacher and M. D. Westmoreland, “Almost Quantum Theory,” inQuantum Theory:
Informational Foundations and Foils, Springer (2016), 45–81. Preprint:https://arxiv.org/
abs/1204.0701.
11

PDF PAGE 12
[3] R. P. James, G. Ortiz, and A. Sabry, “Quantum Computing over Finite Fields: Reversible
Relational Programming with Exclusive Disjunctions,” arXiv:1101.3764 (2011).https://arxiv.
org/abs/1101.3764.
[4] J. N. de Beaudrap, R. Cleve, and J. Watrous, “Sharp quantum vs. classical query complex-
ity separations,” Algorithmica 34(4) (2002), 449–461. Preprint: https://arxiv.org/abs/
quant-ph/0011065.
[5] N. de Beaudrap, “On computation with ‘probabilities’ modulo k,” arXiv:1405.7381 (2014).
https://arxiv.org/abs/1405.7381.
[6] A. J. Hanson, G. Ortiz, A. Sabry, and J. Willcock, “The Power of Discrete Quantum Theories,”
arXiv:1104.1630 (2011). https://arxiv.org/abs/1104.1630.
[7] A. J. Hanson, G. Ortiz, A. Sabry, and Y.-T. Tai, “Discrete quantum theories,”Journal of Physics
A: Mathematical and Theoretical47 (2014), 115305.https://doi.org/10.1088/1751-8113/
47/11/115305.
[8] J. Willcock and A. Sabry, “Solving UNIQUE-SAT in a Modal Quantum Theory,”
arXiv:1102.3587 (2011). https://arxiv.org/abs/1102.3587.
[9] P. Diamond and B. Schumacher, “Cloning, deleting, and hiding in modal quantum theory,”
arXiv:2310.04397 (2023). https://arxiv.org/abs/2310.04397.
[10] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf, “Quantum Lower Bounds by
Polynomials,” Journal of the ACM48(4) (2001), 778–797.https://doi.org/10.1145/502090.
502097.
[11] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, “Bound on the number of functions
that can be distinguished with k quantum queries,”Physical Review A 60 (1999), 4331–
4333. https://doi.org/10.1103/PhysRevA.60.4331. Preprint: https://arxiv.org/abs/
quant-ph/9901012.
[12] E. F. Combarro, S. Vallecorsa, A. Di Meglio, A. Piñera, and I. Fernández Rúa, “On a
poset of quantum exact promise problems,”Quantum Information Processing20 (2021), 214.
https://doi.org/10.1007/s11128-021-03156-3.
[13] D. Copeland and J. Pommersheim, “Quantum query complexity of symmetric oracle problems,”
Quantum 5 (2021), 403.https://doi.org/10.22331/q-2021-03-07-403.
[14] A. Montanaro, “The quantum query complexity of learning multilinear polynomials,”Informa-
tion Processing Letters112(11) (2012), 438–442.https://doi.org/10.1016/j.ipl.2012.03.
002.
[15] A. Montanaro, R. Jozsa, and G. Mitchison, “On Exact Quantum Query Complexity,”Algorith-
mica 71 (2015), 775–796.https://doi.org/10.1007/s00453-013-9826-8.
[16] R. de Wolf, “Nondeterministic Quantum Query and Communication Complexities,”SIAM Jour-
nal on Computing32(3) (2003), 681–699.https://doi.org/10.1137/S0097539702407345.
[17] K. Svozil, “Answer Partitions and Oracle Access Determine Quantum Query Complexity,”
arXiv:2605.12675v4 (2026). https://arxiv.org/abs/2605.12675.
[18] Y.-T. Tai,Discrete Quantum Theories and Computing, PhD thesis, Indiana University (2019).
12