A stabilizer-aware query barrier for vectorization lower bounds

Vectorization query bounds: a proved restricted search barrier and its oracle gap

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

For an action of G on X, vectorization asks for an element g such that $g\cdot x=y$ from the given pair x,y. A generic group model accesses abstract group elements through prescribed operation oracles rather than exploiting their particular representations. Quantum query lower bounds count oracle accesses under a specified quantum-access model.

Statement recorded in the supplied source.

Quantum lower bounds for group-theoretic problems in the generic group model

We would like to solidify the credentials of group-theoretic cryptography as post-quantum by developing lower bounds for the quantum complexity of problems arising in group theory. It would be especially nice to develop such a bound for the vectorisation problem, since this underpins many hardness problems in the area. [S2]

Scope qualification.

The source requests lower bounds, but does not specify a group family, a target bound, or one oracle-access convention.

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness.

Short English statement

Can quantum lower bounds be proved for group-theoretic cryptographic problems, especially recovering a group action element?

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 20001316 (AIM-CRYPTOGRAPHY-0003). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 AIM Workshop Problem Lists, original problem source linked by catalogue record AIM-CRYPTOGRAPHY-0003 http://aimpl.org/postquantgroup/1/.

Verbatim supplied catalogue question

Quantum lower bounds for group-theoretic problems in the generic group model

We would like to solidify the credentials of group-theoretic cryptography as post-quantum by developing lower bounds for the quantum complexity of problems arising in group theory. It would be especially nice to develop such a bound for the vectorisation problem, since this underpins many hardness problems in the area.

Attempt and results

We attempt a quantum lower bound through equality tests of candidate transporters. The resulting theorem is correct for a restricted oracle, but the reduction needed to apply it to a full group-action oracle fails. Keeping that distinction is essential to the source's broad lower-bound question.

The relation differs from recovery of a sampled representative.

Let a finite group $G$ act on $X$, fix $x$, and put $K=\operatorname{Stab}(x)$. If $y=s\cdot x$, then $g\cdot x=y$ exactly when $g\in sK$: apply $s^{-1}$ and use the definition of $K$. If $s$ is uniform on $G$, conditional on $y$ it is uniform on the fiber $sK$, because all its elements had equal prior probability. An estimator using only $y$ and randomness independent of $s$ therefore guesses that particular sampled $s$ with probability at most $1/|K|$. Vectorization instead accepts any element of the fiber, so this information bound is not a lower bound on success in the actual relation problem.

A self-contained quantum lower bound for a candidate-test oracle.

Partition a finite candidate set into $L$ equal fibers $C_1,\ldots,C_L$. An unknown fiber $C_i$ is chosen uniformly. The only input-dependent oracle is the reversible membership test $O_i|g,b\rangle=|g,b\mathbin\oplus\mathbf1_{g\in C_i}\rangle$; all other gates and initial states are independent of $i$. The algorithm makes $q$ queries and outputs one candidate. Purify intermediate randomness and measurements into registers, so it suffices to use unit vectors and a final projective measurement after adding an output register. Let $\psi_i$ be the final state on $O_i$, and $\psi_0$ the final state on the all-zero oracle. Just before query $t$ on the all-zero run, let $P_i$ project onto query candidates in $C_i$. The projectors partition the query register, so $\sum_i\|P_i\phi_t\|^2=1$. A telescoping hybrid, replacing one oracle call at a time while keeping all remaining transformations unitary, gives \[ \|\psi_i-\psi_0\|\le2\sum_{t=1}^q\|P_i\phi_t\|. \] One can obtain this directly by subtracting the two time recurrences: insert $O_i\phi_t$ between $O_i\psi_{i,t}$ and $O_0\phi_t$; the previous-state difference retains its norm and $O_i-O_0$ has norm at most two on $P_i$ and vanishes on its complement. Cauchy--Schwarz now gives $\sum_i\|\psi_i-\psi_0\|^2\le4q^2$. Let $Q_i$ project onto outputs in $C_i$. For each $i$, $\|Q_i\psi_i\|\le\|Q_i\psi_0\|+\|\psi_i-\psi_0\|$. Applying the Euclidean triangle inequality across the index $i$ and using $\sum_i\|Q_i\psi_0\|^2\le1$ yields \[ \frac1L\sum_i\Pr_i(\hbox{output in }C_i) \le\frac{(2q+1)^2}{L}. \] Thus a fixed positive average success probability requires $q=\Omega(\sqrt L)$ as $L\to\infty$. The proof includes output without a final verification query and does not assume all candidate labels are distinct as group witnesses; fibers explicitly account for stabilizers.

The first gap in promoting the bound.

For group-action vectorization, one can implement the candidate test by evaluating $g\cdot x$ and comparing with $y$. This simulates the weaker membership oracle using the stronger action oracle. A lower bound for the weaker oracle does not therefore lower-bound algorithms using the stronger one; the simulation goes in the wrong direction for that inference. For an extreme representation example, let $G=X=\mathbb Z/L\mathbb Z$ act by translation on canonical residue encodings. From $x,y$, the transporter $y-x$ is obtained immediately by subtraction, even though a model exposing only yes/no tests of unknown candidates has the proved search lower bound. This is not a generic-encoding lower-bound counterexample: it shows why the source must fix which representation and operations are available.

Context, adversarial audit, and gap

The official AIM workshop description confirms the quantum cryptanalysis agenda; exact AIMPL wording remains supplied-snapshot material because page retrieval failed. The audit checked stabilizer coset orientation, purification, query/output projectors, and simulation direction. The restricted hybrid argument is a standard search proof rederived in full, not a new bound for the full-action or generic-group model. No computational experiment was run.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. A complete candidate-membership query lower bound does not transfer to a coherent full-action oracle; no lower bound in a fully specified source-relevant generic-group model is obtained.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Official AIM workshop description, Post-quantum group-based cryptography, 29 April--3 May 2024; inspected for provenance and scope. AIMPL section pages failed retrieval, so exact question text comes from the supplied snapshot. https://aimath.org/workshops/upcoming/postquantgroup/.

Final status

Unresolved in this attempt. A complete candidate-membership query lower bound does not transfer to a coherent full-action oracle; no lower bound in a fully specified source-relevant generic-group model is obtained.