Optimal Quantum Query Bounds for Identifying Classes of 3-Tensors: every list of trilinear forms over is identified with quantum queriesResearch Paper
Motivation
Identifying an unknown function from a known class by querying it is the exact-learning or interpolation problem, and for polynomials over a finite field it is the query side of black-box identity testing. By counting, no classical algorithm, even a randomized one, identifies a member of a class of functions over with fewer than queries. Quantum queries can beat this bound: Bernstein and Vazirani identify a linear functional with one query, Montanaro identifies a -tensor on with queries instead of , and Kothari gives a general bound for Boolean classes. Servedio and Gortler showed that for Boolean functions the quantum saving is at most a cube root, which raises the question of which natural classes reach it.
Trilinear forms are a natural test case. Isomorphism of trilinear forms is the target of many reductions in algebraic complexity and underlies proposed post-quantum signature schemes, so the query complexity of identifying a trilinear form inside a known class (sparse forms, forms isomorphic to a given one, forms of low tensor rank) bears directly on those applications.
Timeline.
- 1997: Bernstein and Vazirani, one quantum query identifies a linear function (BV97); generalized to by de Beaudrap, Cleve and Watrous (2002) and van Dam, Hallgren and Ip (2006).
- 2004: Servedio and Gortler, for Boolean functions quantum queries save at most a cube root over classical ones (SG04).
- 2012: Montanaro, -tensors on are learned with quantum queries.
- 2014: Kothari, an optimal quantum algorithm for oracle identification over Boolean domains.
- 2019–2025: analytic rank of tensors (Gowers–Wolf 2011, Lovett 2019); Lampert (2025) proves that slice rank and analytic rank of trilinear forms agree up to constants and supplies the fiber averaging identity used here.
- 2026: Grigorescu, Juba, Wimmer and Xie, every list of trilinear forms is identified with quantum queries, independent of , with a matching lower bound for some classes.
Setting
Let be a finite field with elements and write for the coordinate space. A trilinear form on is given by its coefficient tensor , with value (TriForm F n, TriForm.eval).
The evaluation oracle of is the unitary with and addition in , extended by the identity on a work register (QAlgorithms.xorOracle (oracle θ)).
A randomized quantum query algorithm (AdaptiveAlg) either halts with an output, or runs a -query quantum circuit (alternating unitaries and oracle calls), measures the whole register, and continues with a next algorithm chosen from the measurement outcome. Classical coins are outcomes of rounds that make no query. outProb A g P is the probability that the output satisfies when the oracle function is ; maxQueries A g is the largest total number of queries over the runs of positive probability on .
The zero locus of is and the analytic rank is
equivalently (AR). The milestones also use the slices and , the fibers , the distribution , and the good set of Definition 2 (sliceU, sliceV, fiber, pZ, Mv, goodSet).
Formalization targets
Goal: Theorem 1 (Main)
For every finite field there is a constant such that for all , every list of trilinear forms on and every there is an algorithm (depending on the list and ) with, for every ,
The factor replaces the printed , which tends to as and then forbids every query; the two agree for .
Milestones
In proof order: one-query Bernstein–Vazirani over (Lemma 1) and tensor–vector contraction (Corollary 5); the Stage 1 prefilter (Lemma 12); Lampert's identity (Lemma 2) and the good-fiber properties (Fact 1); the random-subspace estimate (Lemma 10); learning a low-rank matrix (Lemma 5) and verification tests (Lemma 4); finding a good base point (Theorem 6); the rank bound on a good fiber (Fact 2), the rank inequality (Lemma 11) and iterative pivot reduction (Theorem 7); the slice decomposition, Eqs. (32)–(33); identification of bilinear forms from a list (Theorem 4) and from a weighted list (Theorem 5).
Significance
The bound does not depend on , and it is below the classical for every class of trilinear forms. With the paper's lower bound it shows that trilinear forms reach the cube-root limit of Servedio and Gortler, up to the dependence on . Counting consequences (Corollaries 1–3 of the paper) give queries for forms with monomials, for forms isomorphic to a given form, and for tensor rank .
The result is proved in a 2026 manuscript and has not been formalized. The mission produces a formal statement of the main theorem with one minimal correction, a reusable adaptive query model with an -valued oracle, and the analytic-rank layer (zero locus, fibers, slices, good base points) on which further work on analytic and slice rank can build.
Difficulty
The naive approach, learning the form, costs about queries, and testing candidates one at a time costs or, with Grover search over candidates, about . Neither is independent of and polylogarithmic in . The bound requires three ingredients: random probes, which cheaply eliminate candidates whose difference with has large analytic rank; a structure theorem making the low-analytic-rank residual vanish on a product of subspaces of codimension , found with few queries; and an amortized sequential search over the remaining bilinear slices, in which a costly identification step prunes many candidates. The probabilistic core is Lemma 10 (a Paley–Zygmund and Markov argument on randomly projected slice weights over a uniform random affine subspace) and the pivoting analysis is Lemma 11 with Theorem 7. Each step's failure probability and query count must be tracked through the whole composition.
Formalization scope
- Forms are coefficient tensors on the coordinate space
Fin n → F, for any finite fieldF([Field F] [Fintype F] [DecidableEq F], =Fintype.card F); . - The quantum layer reuses the platform's
QAlgorithms.QueryAlg,xorOracle,finalStateandprob;AdaptiveAlgcopies the shape of the platform's Bool-oracleAdaptiveQueryAlgwith an oracle valued inF. Query counts are worst cases over runs of positive probability on the oracle actually queried, not expectations, except in Theorem 5 (ii), which is printed as an average. - Every algorithm is quantified after its explicit inputs (list, , , , base point, test matrix) and before the oracle. Placing it after the oracle would make every statement trivial (a 0-query lookup), and it is excluded.
- Every is a single constant per field, quantified before all other data. Logarithms are base 2 except where the paper writes . Failure-parameter factors are .
- Analytic rank uses the zero-locus count form. Probabilities over random subspaces and probes are counting ratios over finite uniform sample spaces. A random affine -dimensional subspace is uniform over the affine subspaces of dimension exactly .
- Lemma 5 uses the platform's classical decision trees (
QAlgorithms.RandDecisionTree) with RightMult and LeftMult queries counted separately. - Corrections are disclosed in each item: the goal, Lemma 4 and Theorem 6 (), Lemma 12 (Fig. 8's explicit count and the survival of the true form), Theorem 7 ( in place of , with the algorithm given ), Theorem 5 ( guarded at small ).
Welcome contributions: proofs of the algebraic milestones (Lemma 2, Facts 1–2, Lemma 11, Eqs. (32)–(33)), which need only linear algebra over finite fields; the quantum primitives (Lemma 1, Corollary 5), which are reusable for any -valued oracle; and a library of composition lemmas for AdaptiveAlg (sequencing, amplification, union bounds over rounds).
Selected references
- Elena Grigorescu, Brendan Juba, Karl Wimmer and Ning Xie, Optimal Quantum Query Bounds for Identifying Classes of 3-Tensors, STOC 2027 submission manuscript, 2026 (no public link; held version sha256 c56b0365…).
- Ethan Bernstein and Umesh Vazirani, Quantum complexity theory, SIAM Journal on Computing 26(5):1411–1473, 1997.
- J. Niel de Beaudrap, Richard Cleve and John Watrous, Sharp quantum versus classical query complexity separations, Algorithmica 34(4):449–461, 2002.
- Wim van Dam, Sean Hallgren and Lawrence Ip, Quantum algorithms for some hidden shift problems, SIAM Journal on Computing 36(3):763–778, 2006.
- Rocco A. Servedio and Steven J. Gortler, Equivalences and separations between quantum and classical learnability, SIAM Journal on Computing 33(5):1067–1092, 2004.
- Robin Kothari, An optimal quantum algorithm for the oracle identification problem, STACS 2014, LIPIcs 25:482–493.
- Ashley Montanaro, Quantum search with advice, TQC 2010, pp. 77–93, Springer.
- William T. Gowers and Julia Wolf, Linear forms and higher-degree uniformity for functions on , Geometric and Functional Analysis 21(1):36–69, 2011.
- Shachar Lovett, The analytic rank of tensors and its applications, Discrete Analysis 2019:7.
- Amichai Lampert, Slice rank and analytic rank for trilinear forms, Discrete Analysis 2025. https://arxiv.org/abs/2404.19704