RESEARCH / Focused target
Removing intermediate memory resets can increase permutation approximation error
RELEASED FOUNDATIONS / PROPOSED CONNECTION
Research connections
All source anchors (1)
- D5/S3/StatisticalMechanics/ThermalRecallTruncationRefutation.resultAbsent from this graph
Problem
The question
J. Czartowski, A. de Oliveira Junior and K. Korzekwa, Thermal Recall: Memory-Assisted Markovian Thermal Processes, PRX Quantum 4, 040304 (2023), arXiv:2303.12840v2, introduce a memory-assisted protocol for approximating permutations by sequential two-level thermalisations. Conjecture 1, “Improved convergence,” is stated in the source TeX TR.tex, lines 417–427:
In the infinite temperature limit, $\beta=0$, and for an $N$-dimensional memory, $\widetilde{\mathcal{P}}^{{\Pi}}$ gives a better approximation of a permutation $\Pi$ than $\mathcal{P}^{\Pi}$: $$\delta\left( \Pi \mathbf p,\tilde{\mathbf q}\right) \leq \delta\left( \Pi \mathbf p, \mathbf{q}\right),$$ where $\tilde{\mathbf{q}}$ and $\mathbf{q}$ are defined via $\widetilde{\mathcal{P}}^{{\Pi}}(\mathbf{p}\otimes \boldsymbol\eta_M) = \tilde{\mathbf{q}}\otimes \boldsymbol\eta_M$ and $\mathcal{P}^{{\Pi}}(\mathbf{p}\otimes \boldsymbol\eta_M) = \mathbf{q}\otimes \boldsymbol\eta_M$.
The repository proposition claim is the following exact finite reading. For every $d,n\in\mathbb N$, $p:\mathrm{Fin},d\to\mathbb R$, and word $w:\mathrm{List}(\mathrm{Fin},d\times\mathrm{Fin},d)$, if $0<n$, $(\forall i,\ 0\le p(i))$, $\sum_i p(i)=1$, StrictAnti p, and IsReducedNeighbourWord p w, then
[
\operatorname{totalVariation}(\operatorname{applySwaps}(p,w),\operatorname{truncatedOutput}(n,p,w))
\le
\operatorname{totalVariation}(\operatorname{applySwaps}(p,w),\operatorname{resetOutput}(n,p,w)).
]
Here applySwaps folds the word by precomposing with each Equiv.swap; totalVariation is one half of the finite sum of absolute coordinate differences. average replaces the values at two selected joint states by their arithmetic mean. block applies these averages for every first memory index and, inside each round, every second memory index, both in increasing List.finRange order. joint couples $p$ to a uniform memory, reset replaces a joint state by the product of its system marginal and that uniform memory, truncatedOutput folds the blocks without intermediate resets, and resetOutput folds a reset after each block. IsReducedNeighbourWord requires, at every position, an increasing index pair whose two current population values are ordered with no current value strictly between them.
The Lean declaration is result : \lnot claim.
Motivation
Our foothold
The conjecture would make the protocol without intermediate memory resets, which lets memory correlations pass between successive transpositions, uniformly at least as accurate as the protocol that resets the memory after each transposition. Such a guarantee would control the approximation error for the reduced neighbour-transposition words used to reach permutation vertices of the infinite-temperature thermal cone. A counterexample identifies a limit of that guarantee and separates one-block convergence behaviour from compositions of blocks.
Gap
Missing bridges
The bounded literature check recorded in issue #23571 found no settlement in the source, the listed citing works, or the repository records. The source TeX and the closest cited papers were checked for this conjecture; the search scope is recorded in that issue.
not-found-in-searched-scope.
Route
Proposed approach
- The module defines the infinite-temperature elementary operation
average, the nested-round operationblock, the uniform-memory couplingjoint, the memoryreset, and the two folded outputs. The outer fold ofblockuses the first memory index $k$ in increasing order; the inner fold uses the second index $l$ in increasing order, matching the textual order of the source protocol. - It defines
IsReducedNeighbourWordfrom the current population functionr := applySwaps p (w.take n): for every $n<w.length$, with $z=w[n]$, it requires $z.1<z.2$, $r(z.2)<r(z.1)$, and $\forall c,\ \neg(r(z.2)<r(c)\land r(c)<r(z.1))$. The propositionclaimthen adds exactly the positivity, mass, strict-order and reduced-word hypotheses displayed above. - The witness is the private vector $p=(1/2,1/4,2/9,1/36)$ on
Fin 4and the word $w=[(0,1),(2,3),(0,3)]$. The private theoreminstance_hypothesesprovesProbability p ∧ StrictAnti p ∧ IsReducedNeighbourWord p w; itsProbabilitycomponent supplies $(\forall i,\ 0\le p(i))$ and $\sum_i p(i)=1$, and the application ofclaimalso supplies $0<2$. - The private theorem
target_valuesgivesapplySwaps p w = (2/9,1/2,1/36,1/4). The theoremjoint_valuesgives the eight joint entries forjoint 2 p. The three theoremstruncated_block_one,truncated_block_two, andtruncated_block_threeevaluate the three successive blocks without resets. The corresponding reset path is evaluated byreset_block_one,reset_block_two_raw,reset_block_two,reset_block_three_raw, andreset_block_three. -
The private theorems
\operatorname{totalVariation}(\operatorname{applySwaps}(p,w),\operatorname{resetOutput}(2,p,w))+1/144. ]truncated_valuesandreset_valuestherefore give [ \operatorname{truncatedOutput}(2,p,w)=(31/144,13/32,29/288,5/18), ] and [ \operatorname{resetOutput}(2,p,w)=(2/9,13/32,29/288,13/48). ] The private theoremdistance_gapproves the exact identity [ \operatorname{totalVariation}(\operatorname{applySwaps}(p,w),\operatorname{truncatedOutput}(2,p,w)) - The theorem
resultassumesclaim, instantiates it at $d=4$, $n=2$, this $p$ and this $w$ with all of the hypotheses frominstance_hypotheses, and combines the resulting inequality withdistance_gapto derive a contradiction.
Falsifier
What would falsify this route
The refutation would not apply to the source conjecture if the Lean operations differed from the source's infinite-temperature protocol. In particular, a mismatch in the increasing round or inner-step order, in the marginal reset, in the total-variation normalization, or in the interpretation of a reduced neighbour word would break the source-to-module correspondence. The module uses zero-based Fin indices; its word corresponds to the source's successive exchanges of levels $1,2$, then $3,4$, then $1,4$. The formal result covers the stated reduced-word reading only; it does not settle non-reduced words, non-neighbour words, finite temperature, or asymptotic memory-size claims.
Evidence
Evidence to collect
The canonical source is D5/S3/StatisticalMechanics/ThermalRecallTruncationRefutation.lean.
- Proof. It proves
result : ¬ claim. - Axioms.
#print axiomsonresultreports onlypropext,Classical.choice, andQuot.sound; the module contains nosorry,native_decide, or new axiom.
Frozen state: Golden/Frozen/state/D5/S3/StatisticalMechanics/ThermalRecallTruncationRefutation.lean.json.
Declaration statements:
result:sha256:b74f629ecf698a2b8ecadfffb51ff6bde06fea9b88867ecb46856bf89baed48b;claim:sha256:8449e5c22b65b2844c85279c8e2f30fb750baf564d63de1e7a8400749ce1ba60.
Triage
Scope assessment
Tier 1 conjecture of a 2023 PRX Quantum paper with numerical support, preregistered in issue #23571 before any Lean.
theorem; resolution refuted.
The module is admitted under the open-problem-resolution basis of CLAUDE.md §3.2; its per-declaration proof shapes are bind-only definitions and private lemmas consumed on the proof path of result. There is no digestion atom.
What the settlement shows
Proved by result: the formal proposition claim is false.
Computed, not formalized (orchestrator, Claude Code/Opus, recorded in #23571): the instance also violates the conjecture under the three other readings of the loop order and with the other reduced word of the same permutation, in exact rational arithmetic.
Argued, not formalized.
- The mechanism is correlation transfer. Each block is a sequence of linear averages on joint system-memory cells. A reset discards the joint correlations by replacing the state with its system marginal times a uniform memory; omitting the reset carries those correlations into the next block. For a composition of reduced transpositions, the carried correlations can move mass in a direction that increases the final distance to the ideal permutation, as the certified witness demonstrates.
- The missing structure is a condition controlling those cross-block correlations. The source conjecture imposes reduced neighbour ordering but no condition that prevents a later block from exploiting the correlations created by an earlier block. A restriction to a single $\beta$-cycle or another class with a separate convergence argument could survive; this module does not prove such a restriction.
- The source's claim that the truncated protocol is uniformly advantageous for arbitrary reduced compositions is therefore unavailable under this formal reading. The source's separate finite-temperature statements, asymptotic $O(N^{-1/2})$ estimates, and Conjecture 2 are outside
claimand are not settled byresult.
ASSUMED-UNVERIFIED
Unverified assumptions
The literature check is bounded to the source, the cited-work search and repository searches recorded in issue #23571; it does not establish exhaustive worldwide novelty or priority. The broader numerical searches and the source's numerical reports are not formalized. The interpretation of the source's one-based protocol notation as the module's zero-based Fin operations is checked for the stated word and loop order, but a formal equivalence for every alternative protocol convention is not supplied. The mechanism discussion, the surviving restricted classes, all non-reduced or non-neighbour words, finite-temperature behaviour, and asymptotic statements in $N$ remain unverified by this module.