Quantum Query Advantage Requires Space

1 Introduction

• Known time–space lower-bound methods use output items as a progress measure and do not directly extend to Boolean-output problems.The paper therefore requires a different progress measure.Source: §1 · p. 3
• The central question is whether workspace size can determine the existence of a quantum query advantage; Hao, Huang, and Liu [HHL26] left this open for one-bit outputs and worst-case query complexity.Their prior result showed that optimal quantum query complexity for short-output problems can require large workspace in the quantum random oracle model.Source: §1 · p. 3

1.1 Main Results

• ℓ-Sum-Filtered Parity selects structured tuples using H and asks for the parity of the corresponding G-bits, producing a one-bit oracle problem.The definition assigns Boolean values to tuples and sets the parity of the empty set to zero.Source: §1.1 · pp. 4–5
• A deterministic classical algorithm solves ℓ-Sum-Filtered Parity with O(M) queries and O(M log N) bits of space.It stores H, enumerates the filtered set, then queries G on selected tuples.Source: §1.1 · p. 4, §1.2 · p. 5
• For ℓ=4, R(f)=D(f)=Θ(M^21/20), and for every fixed 0<η<1/100 with S≤O(M^(1/100−η)), Q(f)<R(f)<QS(f).The result is for an explicit family of total Boolean functions.Source: §1.1 · p. 5

1.2 Technique Overview

• The proof combines compressed-oracle capacity bounds [HHL26] with a new parity-to-capacity inequality: constant-advantage parity computation requires K(A)=Ω(M).Capacity measures how much of G has been recorded on tuples satisfying the sum constraint defined by H.Source: §1 · p. 4, §1.2 · p. 6
• To obtain a total Boolean function, the construction cuts off the tail of |YH| while preserving the lower bound, then adds an independent OR block to calibrate randomized query complexity.The account states that tail truncation leaves the upper bound untouched.Source: §1.2 · p. 6

2.1 Size of the Filtered Subset

• Conditioning on ℓ−1 H-values leaves exactly one final value that makes an ℓ-tuple sum to zero modulo N.The size analysis expresses |YH| as a sum of indicator variables, with covariance terms for distinct sets vanishing and Chebyshev bounds applied to the tails.Source: §2.1 · pp. 6–7

2.2 Compressed Oracle and the Computational Model

• The H and G registers store their respective random oracles in the compressed-oracle view.The query workspace for either oracle uses O(log N) qubits when ℓ is fixed.Source: §2.2 · p. 8
• Compressed oracles maintain H and G databases in superposition, with oracle queries acting as interactions between the databases and the working registers.The working registers W and Q together contain at most S qubits.Source: §2.2 · pp. 7–8
• Compressed-oracle access gives the same output as standard-oracle access for an unbounded quantum algorithm.Source: §2.2 · p. 8

• With probability 1−O(M^-1), the deterministic algorithm uses M queries to H, at most M queries to G, and O(M log N)-bit space.Source: §3 · p. 9
• The algorithm stores H, enumerates YH, and queries each corresponding G-bit once, stopping with output 0 if more than M tuples are found.The cutoff changes the output only with probability O(M^-1).Source: §3 · p. 9

4 Parity Forces Recording Capacity

• The target is the parity of G-bits indexed by the H-selected domain, so predicting it with advantage requires recording weight on G.Source: §4 · p. 9

4.1 Introducing the capacity.

• For fixed H, the selected recording capacity is KH(A), and K(A) is its expectation over uniformly random H.Source: §4.1 · p. 10

4.2 The success probability as observable value

• The final measurement is represented by a Hermitian operator B on WQ with norm at most 1, defining the conditional success bias βH.Source: §4.2 · p. 10

4.3 An exact parity-to-capacity inequality

• The parity-to-capacity inequality relates β and K through (1 − 2K/|Y|)^2 + β^2 ≤ 1.Source: §4.3 · p. 12

4.4 Averaging over H

• Constant advantage in solving ℓ-Sum-Filtered Parity forces selected recording capacity K(A) to grow as Ω(M).The averaging argument uses that the relevant scale μ is Θ(M).Source: §4.4 · pp. 12–13

• The selected-capacity upper-bound theorem applies to fixed ℓ ≥ 4 and algorithms using S qubits within the stated space range.The range is S = Ω(log N) and S = O(N^(1/((ℓ+1)(2ℓ+1)))).Source: §5 · p. 13
• The one-bit specialization uses the unrestricted ordered zero-sum set, which allows repeated coordinates and all orderings, unlike YH.The strict-ordering condition gives YH as a subset of the unrestricted set.Source: §5 · p. 13
• For ℓ = 4, the specialization has (ℓ+1)(2ℓ+1) = 45.Source: §5 · p. 14

6 Proof of the Separation

• For part (ii), the proof fixes 0 < ε ≤ 1/2 and considers a quantum algorithm as in the theorem.The excerpt does not specify further properties of that algorithm.Source: §6 · p. 14
• The argument invokes Lemma 2.1 and Theorem 4.3 for the fixed algorithm.Source: §6 · p. 14
• The bounds are compared when S = Ω(log N) and S = O(N1/((ℓ+1)(2ℓ+1))).The supplied passage says this comparison yields the next step but does not include its result.Source: §6 · p. 14

7.1 Construction and Main Result

• The construction replaces random-function oracles with arbitrary truth tables, uses a bit encoding for H, discards filtered parity above a size threshold, and XORs in a disjoint OR block.Querying one H value costs log N bit queries.Source: §7.1 · p. 14
• For Ω(log M) ≤ S ≤ M1/100−η, the space-bounded quantum query bound is T = ω(M21/20), exceeding the classical query complexity in this range.The passage requires fixed 0 < η < 1/100; it also states that the construction has a quantum speedup over classical algorithms without the space restriction.Source: §7.1 · p. 15

7.2 Standard Query Facts

• The section invokes the standard query bounds R(OR_L) = Ω(L) and Q(PARITY_k) = Ω(k) in its analysis.Source: §7.2 · p. 15

The corresponding bit-query maps

• The bit-query and standard-query models simulate each other with the same output distribution, at query costs of two standard queries per bit query or r bit queries per standard query.The stated simulations add O(r) or O(log r) qubits, respectively.Source: The corresponding bit-query maps · p. 16

7.3 Unrestricted Query Complexities

• The unrestricted randomized query complexity is Θ(L), with L = ⌈M1+(ℓ−3)/(4(ℓ+1))⌉; the deterministic upper-bound algorithm uses O(M log M) bits of space.The upper-bound algorithm stores H, enumerates the filtered set, and queries either the OR block or selected G-bits with the OR block.Source: §7.3 · p. 16
• Fixing H to a suitable H* and z to zero restricts the function to parity on Θ(M) distinct bits, giving an Ω(M) quantum query lower bound.The excerpt also states that the unrestricted quantum upper bound uses Grover search for the OR part, but its displayed bound is incomplete.Source: §7.3 · p. 17

7.4 The Bounded-Space Reversal

• With z fixed to zero, the algorithm's selected recording capacity is Ω(ε2M), a quantity used to derive the bounded-space tradeoff.The proof applies the capacity bound to the resulting algorithm and combines it with the capacity lemma.Source: §7.4 · p. 17

8.1 Choosing the OR Block

• Choosing L = M1+(ℓ−3)/(4(ℓ+1)) places the OR block at the midpoint of the interval permitting both regimes.For α > cℓ(p), the passage states D = R = Mα+o(1), while the unrestricted quantum algorithm has an upper bound.Source: §8.1 · pp. 17–18
• The OR-block interval cℓ(p) < α < qℓ(p) supports both unrestricted advantage and small-space reversal, and its width is uniquely maximized at p = ℓ−1.At that value, the midpoint is α = 1 + (ℓ−3)/(4(ℓ+1)).Source: §8.1 · p. 18

8.2 Choosing the Filter Scale

• The filter scale M = N1/(ℓ−1) balances the parity-block query scale M + Mℓ−p when ℓ−p = 1.The construction makes the selected set YH the same order as the list of H-values.Source: §8.2 · p. 19