⚛️ quantum physics

Amenable groups with nearly exponential sofic profile, and quantum channels that need nearly linear memory

This paper constructs a finitely presented elementary amenable group with a nearly exponential sofic profile and utilizes its properties to define a quantum channel that demonstrates a fundamental trade-off between memory requirements and purity, revealing that while the channel can be exactly implemented with a small pure environment, any approximate imitation using a finite mixed bath requires exponentially large dimension.

Original authors: Seth Douglas, Nidhal Mghirbi

Published 2026-10-06

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Seth Douglas, Nidhal Mghirbi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of mathematics, some structures are so complex they seem to have no end, while others are simple enough to be held in the mind. Between these extremes lie the amenable groups, infinite collections of rules that behave, in a very specific way, like finite ones. Imagine a giant, endless machine where every small, local piece can be perfectly mimicked by a simpler, finite machine. For decades, mathematicians have wondered how close to finite these infinite structures can truly be. If you take a small snapshot of an amenable group, you can recreate its behavior using permutations of a finite set of objects, like shuffling a deck of cards. But how large does that deck need to be to get the shuffling right? This question of size, or "profile," reveals the hidden depth of these groups. If the deck needs to be only slightly larger than the snapshot, the group is very close to finite. If the deck must grow explosively large, the group is far more complex than it appears.

A team of researchers has now constructed a specific, infinitely complex group that pushes this limit to the very edge of what is possible to detect. They built a mathematical object that is amenable—meaning it can be approximated by finite pieces—but one where those finite approximations must be astronomically large to be accurate. The size of the required approximation grows almost as fast as an exponential function, a rate that is nearly the maximum speed at which such complexity can be measured. This discovery is not just an abstract curiosity about infinite shapes; it has a direct, surprising consequence for the future of quantum computing. The same mathematical structure that forces these massive approximations also dictates how much memory a quantum device needs to perform a specific task repeatedly. The researchers found that a device trying to repeat a certain quantum operation many times cannot simply store a small amount of information and reuse it. Instead, if the device is allowed to consume a significant amount of "purity," a resource akin to fresh, uncorrupted energy, the memory required grows nearly linearly with the number of times the operation is performed. However, if the device operates with logarithmic purity, the memory required grows as $n^{1-o(1)}$ , which is strictly sublinear but still approaches linear growth.

The researchers achieved this by reimagining a classic mathematical construction known as a lamplighter group. In the traditional version, imagine a long street with a lamp at every house. A worker walks down the street, turning lamps on and off. The state of the street is defined by which lamps are lit, and the worker's position. The new group the authors built replaces the street with a more complex landscape: instead of lamps on individual houses, the "lamps" are copies of a small, three-element symmetry group sitting on every possible pattern of lit houses. The worker can still move around, but they can also change the pattern of lit houses in complex ways, like flipping a switch that affects a whole neighborhood at once. By carefully arranging these patterns and the rules for moving between them, the team created a system where two distant lamps can be brought together to interact using a surprisingly short sequence of moves. However, the cost of making them interact is hidden in the geometry of the patterns themselves. To bring two specific lamps together, the worker must traverse a path that, while short in steps, requires a massive amount of "area" to fill in the gaps of the mathematical logic. This hidden cost forces any attempt to simulate the group with a finite set of objects to use a number of points that grows nearly exponentially.

This mathematical construction was then translated into a physical scenario involving a quantum channel, which is a device that transforms quantum information. The researchers designed a specific channel that acts on a system of 873 quantum states. They proved that if a device tries to use this channel over and over again, releasing the output before the next input arrives, it faces a strict trade-off. If the device tries to keep its memory usage low, it must spend a large amount of purity, essentially importing fresh, high-quality quantum states for every few uses. If it tries to conserve purity, the memory required to store the state of the system grows as $n^{1-o(1)}$ with the number of uses, which is nearly linear but strictly sublinear. The only way to avoid this massive memory cost is to operate at a specific "rank rate," where the memory and purity requirements both scale with the square root of the number of uses. This result is significant because it provides a concrete example of a quantum process that is theoretically possible to build with a finite environment but is so expensive to approximate that the required resources explode in size.

The study also clarifies the limits of what is known about the "Connes embedding problem," a major question in operator algebras concerning whether certain complex quantum channels can be approximated by finite-dimensional ones. The researchers showed that their specific channel lies in the closure of channels that can be built with finite baths, meaning it can be approximated arbitrarily well. However, they proved that any such approximation requires a bath size that grows exponentially with the desired accuracy. This means that while the channel is not fundamentally "infinite" in a way that makes it impossible to approximate, the cost of getting even a tiny bit of accuracy is prohibitively high. The work connects the abstract geometry of infinite groups to the tangible resource constraints of quantum devices, showing that the deepest mathematical structures can dictate the physical limits of information processing.

The team's findings rest on a rigorous proof that links the geometry of the group to the entropy of the quantum memory. They demonstrated that a single use of the device reveals an approximate representation of the group's structure within the device's memory. Because the group requires such a large number of points to be modeled accurately, the memory must carry a corresponding amount of information, or entropy. This connection is tight and unavoidable; the more accurately the device tries to mimic the channel, the more memory it must hold. The researchers did not simulate this behavior on a computer but provided a mathematical proof that holds for any device attempting to perform the task. They also established that the group they built is a subgroup of a larger, well-known group called Brin's group, which implies that this group also contains a chunk with a nearly exponential profile. This suggests that the phenomenon is not an isolated oddity but a feature that can appear in other complex, finitely presented groups.

In the end, the paper offers a clear picture of a boundary in mathematics and physics. It shows that there are amenable groups that are "nearly" as complex as the most complex groups can be, and that this complexity translates directly into a memory cost for quantum machines. The device described is not a theoretical impossibility, but a practical challenge: it can be built, but only at a steep price. The researchers have mapped out exactly how steep that price is, showing that for a certain class of quantum operations, the memory required is not a fixed constant but a growing burden that scales nearly linearly with time, specifically as $n^{1-o(1)}$ . This work bridges the gap between the abstract world of infinite symmetries and the concrete reality of quantum engineering, proving that the shape of a mathematical group can determine the size of a quantum memory.

Technical Summary: Amenable Groups with Nearly Exponential Sofic Profile, and Quantum Channels that Need Nearly Linear Memory

1. Problem Statement

The paper addresses two interconnected problems in geometric group theory and quantum information theory:

Group Theory: How far from finite can an amenable group be? Specifically, the authors investigate the sofic profile $\sigma_E(r)$ of a group chunk $E$ . This function measures the minimum number of points required to model a finite subset of a group via permutations such that the multiplication table is correct and distinct elements are separated on all but a $1/r$ fraction of points. While it was known that amenable groups have finite sofic profiles, the growth rate of these profiles was an open question. Cornulier had asked if a sofic group could have a profile that is unbounded but not linear in $r$ . Previous work by the authors on Houghton's group $H_3$ established a superpolynomial profile ( $\exp(r^{0.129})$ ), but the theoretical ceiling for such counting arguments is $\exp(O(r))$ . The question remains: can an amenable group approach this exponential ceiling?
Quantum Information: What is the memory cost of repeatedly applying a quantum channel? Specifically, the paper considers a device that applies a fixed channel $\Phi$ $n$ times sequentially, releasing the output before the next input arrives. The device has a memory register that is never fully reset but may swap qubits (exchange) and start with or import "purity" (entropy deficit). The goal is to determine the trade-off between the memory size $Q$ , the purity budget $B$ , and the number of uses $n$ , particularly for channels that lie in the closure of those with finite tracial factorizations.

2. Methodology

Group Construction: Configuration Lamps

The authors construct a specific finitely presented elementary amenable group $\Gamma$ . The construction is a "lamplighter" variant where the "lamps" (copies of the symmetric group $S_3$ ) are not placed on the points of a ray (as in Houghton's group) but on finite binary configurations of the three rays of Houghton's group $H_3$ .

The Lighter: The group of affine maps acting on the space of configurations $V = \mathbb{F}_2^Y$ . This includes permutations of points (from $H_3$ ), translations (flipping a point), and transvections (adding one point to another).
The Lamps: A copy of $S_3$ sits at every finite configuration.
Key Mechanism: The group $H_3$ moves points, while affine maps move configurations. Crucially, $N$ points carry $2^N$ configurations (lamps). The authors show that any two lamps can be brought together (commuted) using a sequence of moves where each step involves at most three points. The cost of commuting two lamps is governed by the Dehn function of $H_3$ , which is polynomial. Consequently, the "area" required to commute $2^N$ lamps is polylogarithmic in the number of lamps, rather than polynomial in the distance.

The Counting Criterion

The lower bounds on the sofic profile rely on a "counting criterion" (Theorem 2.1, adapted from [26]). The principle is:

If a group contains many copies of a finite group (here $S_3$ ) that are "cheaply" transported to many locations (via short words), and the pairwise commutators of these copies have small "area" (few relations needed to make them commute), then any approximate representation of the group must be large.
Approximately commuting copies of $S_3$ carry entropy. If $N$ such copies commute cheaply, the dimension $D$ of the representation must satisfy $\log D \gtrsim N$ .
The authors construct a set of 25 relations in $\Gamma$ that force $2^N$ copies of $S_3$ to commute with an area bound $\Lambda_N \approx N^{2+\kappa}$ (where $\kappa \approx 12.75$ ).

Quantum Channel Construction

The group $\Gamma$ is converted into a gadget channel $\Phi$ on $\mathbb{C}^{873}$ .

Gadget Channel: A channel constructed from a finite set of group relations. It evaluates the relations in the regular representation and traces out the group algebra.
One-Round Theorem: The core engine linking the group to the channel is a "weighted one-round theorem" (Theorem 10.1). It states that a single round of a causal service (device) that approximates the gadget channel reveals an approximate representation of the group on the device's memory. The "defect" of this representation is related to the square root of the leakage and entropy production of that round.
Amplification: By applying the one-round theorem to the $2^N$ cheaply commuting copies of $S_3$ in $\Gamma$ , the authors derive a lower bound on the memory entropy required to simulate $n$ uses of the channel.

Upper Bounds

The upper bounds are derived from sofic models of $\Gamma$ . The authors construct models using affine hashing:

They map configurations to a finite hash space using random affine maps.
These models are significantly smaller than those derived from Følner sets (which are doubly exponential in size for $\Gamma$ ).
These models directly yield devices (causal services) that approximate the channel, providing the upper bounds on memory and purity.

3. Key Contributions and Results

Theorem A: The Group $\Gamma$

The authors prove the existence of a finitely presented elementary amenable group $\Gamma$ with a chunk $E$ having a sofic profile $\sigma_E(r)$ that is nearly exponential:
$\exp\left( c \frac{r}{(\log r)^\kappa} \right) \le \sigma_E(r) \le \exp(C r \log r)$
where $\kappa = 6 + \log 107 < 12.75$ .

Significance: This is the first amenable group shown to have a profile approaching the theoretical ceiling of $\exp(O(r))$ allowed by the counting criterion. The exponent is $1+o(1)$ .
Unitary Models: The same relations control unitary models, showing that any unitary representation satisfying the relations with small defect must have a dimension $D$ such that $\log D \gtrsim \epsilon^{-2} / (\log(1/\epsilon))^{2\kappa}$ .
Embedding: $\Gamma$ embeds into Brin's group $3V$ (a finitely presented simple group of unknown soficity), implying $3V$ also has a chunk with a nearly exponential profile.

Theorem B: The Quantum Channel

The group $\Gamma$ defines an explicit quantum channel $\Phi$ on $\mathbb{C}^{873}$ with Choi rank $r^*=130$ . The channel lies in the closure of channels with finite tracial factorizations.

Memory vs. Purity: For $n$ uses, if the device has a purity budget $B$ (where $\log n \le B \le c_0 n$ ), the memory $Q$ must satisfy:
$Q \ge c \frac{n}{B (\log n)^{2\kappa}}$
Conversely, exact services exist with $Q \le K (n/B) \log(2n/B)$ .
Rank Rate: At the optimal exchange rate (the "rank rate" $J \le \frac{n}{2} \log r^*$ ), the memory scales as $Q \approx \sqrt{n}$ (up to polylogarithmic factors), and this is achieved with purity of the same order.
Significance: This establishes a sharp trade-off between memory and purity for a channel that is "cheap" to use once but "expensive" to use many times. It demonstrates that even for channels in the closure of finite-tracial channels, repeated use can require memory that grows nearly linearly with $n$ if purity is low.

Theorem C: Finite Environments

The channel $\Phi$ is factorizable and lies in the closure of channels with finite tracial factorizations. However, any finite-dimensional bath that approximates $\Phi$ to accuracy $u$ must have dimension:
$\dim \ge \exp\left( c u^{-1} / (\log(1/u))^{2\kappa} \right)$
This quantifies the "distance" of $\Phi$ from having a finite tracial factorization, showing that the dimension of the required bath grows nearly exponentially as the accuracy improves.

4. Significance and Claims

The paper claims to resolve the question of how large the sofic profile of an amenable group can be, demonstrating that it can be nearly exponential, close to the limit of what the counting method can detect.

In the context of quantum information, the paper provides:

Explicit Examples: A concrete quantum channel where the memory cost for sequential use is high, contrasting with channels that can be simulated with fixed finite memory.
Quantitative Bounds: Precise asymptotic bounds on the trade-off between memory, purity, and the number of uses, showing that memory and purity trade at a fixed rate ( $Q \cdot B \approx n^{1+o(1)}$ ).
Connection to Physics: The results imply that local lattice systems in $\nu$ dimensions require time at least $\delta^{-1/\nu}$ to produce such a channel to accuracy $\delta$ . It also notes that while autonomous limits of self-adjoint dynamics are generally "cheap," a bounded non-local Hamiltonian can produce a channel with the same expensive memory/purity trade-off.

The authors emphasize that the "engine" of these results is the one-round theorem, which links the memory of a single round of a device to an approximate representation of the underlying group. This allows the geometric properties of the group (the cost of commuting lamps) to be directly translated into resource constraints for quantum devices.

The paper does not claim to solve the soficity of Brin's group $3V$ or Thompson's group $F$ , but rather uses the embedding of $\Gamma$ into $3V$ to show that if $3V$ is sofic, it must have chunks with nearly exponential profiles. Similarly, the results on Thompson's group $V$ are conditional on the amenability of $F$ . The paper remains modest about the constants involved, noting that the polylogarithmic factors have large exponents and the lower bounds only take effect for very large $n$ .