Exponential quantum advantages for decoded quantum interferometry in the streaming setting

1 Introduction

• Streaming makes memory and input passes explicit resources; prior one-pass quantum optimization advantages cited here can be matched by constant-pass classical algorithms.The paper asks whether quantum algorithms can instead outperform many-pass classical algorithms for natural problems.Source: §1 · p. 3
• At 75.001%, no classical algorithm using N^c passes and N^(1/2+c) space can solve the stated OPI setting, even with unlimited time.Source: §1 · p. 3

1.1 Problem setup

• Hermite OPI extends polynomial fitting to constraints on values and high-order derivatives; the polynomial aims to match as many of these constraints as possible.Hasse derivatives express the derivative constraints over finite fields.Source: §1 · p. 3, §1.1 · p. 4

1.2 Our results

• 93.301% is achievable for Hermite OPI with one pass, polylog(N) space, and polylog(N) time per entry; at 75.001%, classical algorithms require N^c passes and N^c space, even with unlimited time.The quantum per-entry time includes generating the final answer.Source: §1 · p. 3
• The quantum tradeoff reaches every fixed approximation ratio below α⋆ with one pass, O(qℓlog q) space, and polynomial preprocessing, update, and postprocessing time.For ratios below 1, one-pass quantum algorithms retain the same space bound and polynomial preprocessing and update time, but may require exponential-time postprocessing.Source: §1.2 · p. 5

1.3 Related work

• The paper situates its result among DQI and other Regev-reduction approaches, distinguishing its unconditional streaming space–pass advantages for OPI and Hermite OPI.It also identifies stronger approximation guarantees, classical tradeoffs, and other code families as open directions.Source: §1.3 · p. 6, §1.4 · p. 7

2.1 Triply efficient quantum streaming at 93% approximation

• One pass prepares the product error state by phase-flipping stream entries, then a controlled operation produces the target state.The subsequent projection and syndrome erasure enable Fourier interference to sample a polynomial according to its score.Source: §2.1 · p. 9
• Every fixed approximation ratio α < α⋆ is achievable by the one-pass quantum streaming algorithm.Its quantum state is projected onto uniquely decodable errors before Fourier interference samples a high-scoring polynomial.Source: §2.1 · pp. 8–10

2.2 Doubly efficient quantum streaming at 1 −ε approximation

• Near-1 approximation uses sampled coordinates to resolve decoding ambiguity, with the final score remaining roughly α · n.The higher projection cutoff can include errors sharing a syndrome; exhaustive search decodes accepted errors, preserving space but making the process time-inefficient.Source: §2.2 · p. 10

2.3 Classical lower bounds

• The classical lower bound uses multi-party communication complexity and Hermite-code list recovery to show that p-pass streaming algorithms need eΩℓ,α space.The proof adapts hidden-derivative interpolation to length-ℓ jets and extends a communication-protocol argument to streaming.Source: §2.3 · pp. 11, 13

2.4 Classical upper bounds

• The classical algorithm for Theorem 1.8 samples positive addresses in one pass and searches for a polynomial matching enough sampled entries.List-recovery bounds exclude low-score accepted polynomials, while a second-moment argument shows a high-score certificate survives sampling.Source: §2.4 · p. 13

• Hermite interpolation prescribes length-ℓ jets at distinct points, and any such assignments at n points determine a unique polynomial of degree less than ℓn.The jet specifies the polynomial modulo (X − a)^ℓ.Source: §3 · p. 14
• The Hermite code represents degree-less-than-K polynomials by their jets at n evaluation points; for ℓ = 1 it is Reed–Solomon, and generally it is a univariate multiplicity code.The HOPI objective is to find a codeword matching as many prescribed allowed jets as possible, up to an α-approximation of the optimum.Source: §3 · p. 15
• The preliminaries provide a deterministic unique decoder and a list-recovery bound for the Hermite code.The cited decoding implementation uses O(nℓlog q) space and polynomial time; the list-recovery theorem applies for α > 3/4 under its stated parameter conditions.Source: §3 · pp. 15–16

4 Triply efficient quantum streaming below α⋆approximation

• For every fixed α < α⋆, a one-pass quantum streaming algorithm solves HOPI using O(qℓlog q) space and poly(q, ℓ) preprocessing, update, and postprocessing time.The algorithm prepares a product state, projects onto errors within the decoding radius, then applies syndrome decoding and Fourier interference.Source: §4 · p. 16, §4.2 · p. 20

4.1 The algorithm with access to the whole input

• The algorithm chooses a product error state whose typical weight stays below the decoding threshold while its expected score exceeds αn.A binomial-weight construction and projection onto errors of weight at most d enable syndrome compression and Fourier sampling.Source: §4.1 · p. 18

4.2 Implementation in one streaming pass

• A single stream pass exactly prepares the product state |Ψ⟩ using O(qℓlog q) space and poly(q, ℓ) preprocessing, update, and postprocessing time.The final algorithm supplies this state to the projection and decoding steps; its failure probability is Oα(1/q), at most 0.01 for sufficiently large q.Source: §4.2 · pp. 19–20

5 Doubly efficient quantum streaming at every approximation

• For every α<1, Theorem 1.6 gives a one-pass quantum algorithm using O(qℓlog q) space and q^O(qℓ) postprocessing time.It requires q ≥ Ωα(ℓlog(ℓ+1)); the implemented algorithm has failure probability Oα(1/q).Source: §5 · p. 20, §5.2 · p. 24

5.1 The algorithm with access to the whole input

• Randomly augmenting the syndrome distinguishes errors: for each fixed error, the chance it is not isolated is at most 1/n.Retained errors are then uniquely decodable within Bd+2; exhaustive search implements decoding using small space but exponential time.Source: §5.1 · pp. 21–23
• The probability that projection succeeds but the output score is below αn is Oα(1/n), a joint probability bound, not a conditional bound given successful projection.Adding rejection probability δn, total algorithm failure is at most Oα(1/n)=Oα(1/q); this calculation does not require a lower bound on ∥ΦR∥ for each individual R.Source: §5.1 · pp. 23–24

5.2 Implementation in one streaming pass

• The streaming phase prepares the product state in one pass; postprocessing tests isolation and decodes by exhaustive search using O(qℓlog q) space and q^O(qℓ) time.The search enumerates at most q^O(qℓ) candidates, reusing work registers.Source: §5.2 · p. 24

6 Classical streaming lower bounds

• For α>3/4, Theorem 1.7 establishes a space lower bound for randomized p-pass classical algorithms solving (α,q,ℓ)-HOPI.The theorem applies for integers ℓ,p≥1 and primes q≥3.Source: §6 · pp. 24–25
• The proof uses gadgetless lifting and structure-versus-randomness techniques to reduce general communication protocols to subcube-like protocols.The streaming lower bound follows by simulating a p-pass streaming algorithm as a multiparty communication protocol.Source: §6 · p. 25, §6.2 · p. 29

6.1 Communication lower bound for subcube protocols

• In the subcube protocol argument, list recovery limits the dangerous codewords to L candidates, and a union bound yields communication cost Ω(T).Each candidate’s success probability is bounded using its still-unexposed queries.Source: §6.1 · pp. 26–27

6.2 Communication lower bound for general protocols

• A density-restoring refinement converts general protocols into subcube-like ones while preserving their output and controlling expected codimension.The resulting lower-bound argument applies to general protocols, with the refinement’s implicit constant independent of the number of parties.Source: §6.2 · pp. 28–29

A Calculations for the headline theorems

• For original OPI, a one-pass quantum algorithm achieves (1−ε)-approximation using O(√(N log N)) space and polynomial preprocessing-update time.Its postprocessing time is exponential, as stated in the headline theorem.Source: A Calculations for the headline theorems · p. 35
• For original OPI, a one-pass quantum algorithm achieves (α⋆−ε)-approximation using O(√(N log N)) space and polynomial preprocessing-update-postprocessing time.This is the theorem’s efficient-time approximation guarantee.Source: A Calculations for the headline theorems · p. 35
• For every integer p ≥ 1, every randomized p-pass classical (3/4 + ε)-approximation requires space at least p · (log N)^Oε(1).Source: A Calculations for the headline theorems · p. 35
• For ℓ=⌊q^(1/C)⌋, streaming Hermite OPI has one-pass quantum algorithms for (1−ε) and (α⋆−ε) approximation with polylogarithmic space and polynomial update time.The stated space is O((log N)^(C+1)); the latter approximation also has polynomial postprocessing time.Source: A Calculations for the headline theorems · pp. 35–36

B Optimum of random Hermite OPI instances

• The proof counts polynomials satisfying all rows and establishes Var(Z)≤E[Z], then applies Chebyshev’s inequality to bound the probability that Z=0.The expectation is q^Kρ^n.Source: B Optimum of random Hermite OPI… · pp. 36–37
• Under the hard input distribution, Pr[OPT<n] is at most e^-Ω(nℓlog q).Thus OPT=n with probability 1−e^-Ω(nℓlog q).Source: B Optimum of random Hermite OPI… · pp. 36–37

C List-recovery bound of Hermite codes

• The Hermite generalization asks each polynomial to match both acceptable values and high-order derivatives at evaluation points.The proof extends the hidden-derivative and total-incidence interpolation frameworks to length-ℓ jets.Source: C List-recovery bound of Hermite codes · p. 37
• The proof has four stages: reduce to candidate counting, establish local conditions, construct the interpolation space, and bound the equation’s solutions.The local conditions use a backward Taylor identity and remainder variables for the prescribed derivatives.Source: C List-recovery bound of Hermite codes · pp. 37–38
• A common nonzero auxiliary polynomial is obtained by imposing local multiplicity conditions at every incidence and choosing a space whose dimension exceeds the total condition count.The criterion then forces every polynomial hitting at least t lists to satisfy the common equation.Source: C List-recovery bound of Hermite codes · pp. 38, 40
• The final candidate count uses a differential-root bound after verifying degree and dimension conditions for the constructed space.The proof applies the bound to the common nonzero equation and its low-degree polynomial solutions.Source: C List-recovery bound of Hermite codes · p. 41
• The argument establishes (ζ, T, L)-list recovery by bounding the number of polynomials whose jets hit at least t input lists.The lists are arbitrary, and the resulting bound is |P(F)| ≤ L.Source: C List-recovery bound of Hermite codes · p. 41

D Classical streaming at every approximation

• For α ∈ (3/4, 1), a randomized one-pass classical algorithm solves (α, q, ℓ)-HOPI using Oℓ,α(q^(1+ℓκ(α)) log q) space.The theorem assumes prime q ≥ 3.Source: D Classical streaming at every… · p. 43
• The algorithm’s preprocessing-update time is polynomial in q and ℓ.This is the stated bound for fixed ℓ and α.Source: D Classical streaming at every… · p. 43
• Postprocessing takes q^O(qℓ) time.This is the theorem’s stated postprocessing bound for fixed ℓ and α.Source: D Classical streaming at every… · p. 43

D.1 Analysis of the algorithm

• The uncapped sample must reject every polynomial scoring below αn while admitting at least one high-score polynomial.A union bound handles low-score candidates, while high-score candidates are analyzed through certificates consisting of h positive addresses.Source: §D.1 · pp. 43, 45
• The bounds on the three ranges, e^O(r), e^-Ω(n ln n), and e^-Ω(n/(ln n)^2), let Cauchy–Schwarz yield Pr[Z > 0] ≥ e^-O(r).Source: §D.1 · p. 46
• The probability that no high-score polynomial is accepted is at most e^-Ω(n/(ln n)^8).The bound follows using h = Θ(n) and d = ⌈n/(ln n)^4⌉.Source: §D.1 · p. 46
• With probability at least 0.99, no storage overflow occurs, some candidate passes, and every passing candidate has score at least α OPT.The guarantee combines the overflow bound with the two acceptance bounds.Source: §D.1 · p. 46
• During the pass, the algorithm stores at most BW addresses; afterward, it checks q^K candidate coefficient vectors, with polynomial time per candidate.The stated postprocessing time is q^nℓ/2 polyℓ,α(n, log q) = q^O(qℓ).Source: §D.1 · p. 47

E Efficient classical streaming at 3/4 approximation

• For α ∈ (0, 3/4], a randomized one-pass classical algorithm solves (α, q, ℓ)-HOPI in O(qℓ log q) space and polynomial time.The theorem applies for every sufficiently large prime q and bounds preprocessing, update, and postprocessing time.Source: E Efficient classical streaming at 3/4… · p. 48
• The method interpolates constraints on nearly half the rows and uses random completion to satisfy about half of the remaining rows.It selects interpolation constraints when their first positive records arrive, allowing exact candidate scoring without a second pass.Source: E Efficient classical streaming at 3/4… · p. 48
• The algorithm uses r = 4 and R = 512 candidates, with k0 = n/2 − r rows selected for interpolation.The remaining m = n/2 + r rows are not selected as interpolation constraints.Source: E Efficient classical streaming at 3/4… · p. 48

E.1 Analysis of the algorithm

• Final counters equal the candidates’ exact scores because each relevant positive record arrives after selection and is counted once.Candidates satisfy every selected row; unselected-row scores increment when the candidate jet belongs to that row’s list.Source: §E.1 · p. 49
• Conditioned on successful sampling, candidate jets on unselected rows are four-wise independent Bernoulli variables with mean ρ = (|Σ| −1)/(2|Σ|).The candidate analysis conditions on all planned SampleB calls succeeding.Source: §E.1 · pp. 49–50
• 1/64 probability suffices for a candidate to score at least 3n/4; among R candidates, the chance none does is at most e^-8.Exact score selection returns a successful candidate whenever one exists.Source: §E.1 · p. 50
• Total failure probability is below 0.01, combining candidate failure with the bound on unsuccessful sampling.The bound is e^-8 + 1/400.Source: §E.1 · p. 50
• Space usage is O(nℓlog n) when r and R are constants and B = O(log(nℓ)).The stored candidate vectors use O(Rnℓ) field elements, alongside interpolation and reusable workspace.Source: §E.1 · p. 50
• Preprocessing, per-record updates, and postprocessing take poly(nℓ, log n) time, with no further input access needed to output the winner.The winning vector is explicitly output after selecting the largest score counter.Source: §E.1 · p. 50