The Arun Kernel

Abstract

After Tang (2018) and the dequantization wave of 2018–2023, most exponential QML separations collapsed: any quantum algorithm relying only on low-rank or low-stable-rank inputs admits a polylog classical sketch. We propose a problem class — Theta-Modular Kernel Estimation (TMKE) — where the input data are q-expansion coefficients of weight-k cusp forms on Γ₀(N), and the kernel is a SWAP-test fidelity between two such states. Under the Generalised Ramanujan Conjecture, the inputs have stable rank Θ(N), defeating the Frieze–Kannan–Vempala dequantization scheme. The quantum algorithm runs in O(log N · poly(k)); the best classical lower bound (assuming GRC) is Ω(√N). Three [GAPs] are explicit. The structural ingredient is borrowed from Ramanujan's 1916 conjecture on τ(n) — the original example of a sequence too rigid for random sketches.

The identity

K_Δ(f, g)  =  |⟨ψ_f | ψ_g⟩|²,    |ψ_f⟩ = (1/‖a_f‖) ∑_{n=1}^N a_f(n) |n⟩,    |a_f(p)| ≤ 2 p^{(k-1)/2}     (3)

The donor — where the structure comes from

Sketch

The gaps

• [GAP K1]Classical lower bound under GRC

  Stable rank Θ(N) defeats known sketches but does not prove no polytime classical algorithm exists. A formal reduction from a standard hardness assumption is missing.

• [GAP K2]Multiplicative-structure attack

  Hecke multiplicativity a_f(mn) = a_f(m)a_f(n) is rich enough that a number-theoretic classical attack might exist. We have not ruled it out.

• [GAP K3]Loader cost in practice

  Computing a_f(n) for n up to N is fast (Sage, modular symbols), but encoding into a quantum state takes Ω(N) gates without QRAM, swamping the SWAP-test advantage.

Toy

@guppy
def arun_kernel(f_state: qubit[4], g_state: qubit[4], anc: qubit) -> bool:
    # K_Delta(f, g) = |<psi_f | psi_g>|^2  via SWAP test.
    # Stable rank Theta(N) under GRC -- [GAP K1] -- defeats dequantization.
    h(anc)
    for i in range(4):
        cswap(anc, f_state[i], g_state[i])
    h(anc)
    return measure(anc)  # P(0) = (1 + |<f|g>|^2) / 2

Failure modes — what would refute this

Prior art

• A quantum-inspired classical algorithm for recommendation systemsaccepted
  Tang · 2018 · arXiv:1807.04271

  The dequantization that started it all. TMKE is a candidate survivor; every QML claim now has to show why Tang's machinery does not apply.

• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learningaccepted
  Chia, Gilyén, Li, Lin, Wang, Lloyd · 2020 · arXiv:1910.06151

  Generalised Tang to a unified framework. The stable-rank dependence is explicit; TMKE attacks exactly that dependence.

• La conjecture de Weil. Iaccepted
  Deligne · 1974

  Proves the Ramanujan-Petersson bound used to lower-bound stable rank. The load-bearing classical theorem.

• Quantum random access memorycontested
  Giovannetti, Lloyd, Maccone · 2008 · arXiv:0708.1879

  The amplitude-encoding loader. Realism of QRAM is itself contested (Aaronson 2015) — see [GAP K3].

• Read the fine printaccepted
  Aaronson · 2015

  The 'fine print' on QML claims. TMKE is explicitly designed to survive each numbered objection — but [GAP K3] is the one most likely to bite.

• Quantum-inspired algorithms in practiceaccepted
  Arrazola, Delgado, Bardhan, Lloyd · 2020 · arXiv:1905.10415

  Sobering practical assessment: Tang-style algorithms are fast in theory but lose hard to BLAS in practice. TMKE has to win at small N too, not just asymptotically.

• On the absence of barren plateaus in quantum convolutional neural networks (withdrawn version)contested
  Pesah, Cerezo, Wang et al. · 2021 · arXiv:2011.02966

  Negative control: a QML separation claim later rebutted by Cerezo–Larocca–Schatzki–Coles 2024. TMKE must avoid the same fate (over-claiming structure that does not survive scrutiny).

• Ramanujan, 'On certain arithmetical functions'accepted
  Ramanujan · 1916

  The original τ-function paper. Source of the conjecture Deligne later proved.

Next steps

1. Implement the Hecke-eigenvalue classical estimator and run it head-to-head against the quantum SWAP test ([GAP K2]). This is the most likely refutation.
2. Formalise [GAP K1] as a reduction from a query-complexity lower bound rather than a circuit one — easier proof, weaker statement.
3. Build a Selene benchmark at N = 64 with hash-state preparation; measure end-to-end gate count ([GAP K3]).
4. Speak with Ewin Tang directly; if she sees an obvious sketch we missed, the project ends in one conversation. (This is a feature.)

Research log

• 2026-06-26 · Arun Nadarasa
  Realised that Ramanujan's τ-function bound is exactly the property dequantization needs to fail. Wrote up TMKE in 2 hours.
• 2026-06-26 · Arun Nadarasa
  Hecke multiplicativity ([GAP K2]) is the obvious classical attack. Drafting the estimator before anything else.
• 2026-06-26 · Arun Nadarasa
  N=16 Selene toy run on Δ vs E_12-65520/691·Δ (orthogonal in the Petersson inner product). Fidelity 0.04 ± 0.02. Toy works.