Generalized Complexity Distances and Non-Invertible Symmetries

This paper generalizes quantum gate complexity and geometric distance measures to non-invertible symmetries in quantum field theories, demonstrating that such symmetries define parallel computation schemes involving post-selection and revealing that their simple objects can be computationally highly complex.

The Gist

Imagine you have a giant, magical library of quantum states. In the old days of physics, we thought of "symmetries" (rules that keep things the same) like a strict dance troupe. Every dancer (operator) had a specific partner, and if you paired them up, they always formed a perfect, predictable circle. This was like a Group: if you did move A then move B, you always ended up in a specific spot C.

But recently, physicists discovered a new, weirder kind of symmetry. Let's call them "Non-Invertible Symmetries."

Think of these not as a dance troupe, but as a magic trick.

• If you do move A and then move B, you don't just end up in one spot. You end up in a superposition of spots. You might be in spot C, or spot D, or a mix of both.
• Worse (or better?), you can't always "undo" the move. If you try to reverse the action, the magic doesn't just go back to the start; it might vanish or turn into something else entirely.

This paper by Heckman, Hicks, and Murdia asks a big question: How do we measure the "difficulty" or "distance" of these magic tricks?

Here is the breakdown of their ideas using everyday analogies:

1. The Magic Trick as a "Parallel Universe" Computer

The authors realized that these weird, non-reversible symmetries can be understood as a specific type of quantum computer operation called a Linear Combination of Unitaries (LCU).

• The Old Way (Standard Quantum Gates): Imagine you have a single robot arm that can move a block. To get from Point A to Point B, the robot takes a specific path.
• The New Way (Non-Invertible Symmetries): Imagine you have a machine that splits the block into three parallel universes.
  • In Universe 1, the robot moves the block left.
  • In Universe 2, the robot moves the block right.
  • In Universe 3, the robot leaves it alone.
  • Then, at the end, you use a special "filter" (called post-selection) to look at only the outcome where the block ended up in a specific spot.

The "Non-Invertible Symmetry" is the whole process of splitting the universe, doing different things, and filtering the result. It's like running a parallel computation and then betting on the outcome you want.

2. Measuring the "Distance" (Complexity)

In standard physics, if you want to know how "far" two rotations are, you just measure the angle between them on a circle. But since these new symmetries are messy (they involve mixing and filtering), you can't just use a protractor.

The authors invented a new Ruler for Quantum Magic.

• The Analogy: Imagine you have a reference photo of a room (a "mixed state"). You want to see how different two new photos are from the original.
• The Method: Instead of just comparing the pixels, they ask: "If I apply this magic symmetry to the room, how much does the 'fingerprint' of the room change?"
• They created a formula that measures this "fingerprint change." If the change is small, the symmetry is "close" to doing nothing. If the change is huge, the symmetry is "far away" and very complex.

3. The Big Surprise: Simple Things are Actually Hard

The most exciting part of the paper is their discovery about "Simple Objects."

In math, the "simple objects" of a symmetry category are like the basic building blocks (the atoms of the symmetry). You might think, "Oh, these are the simplest things; they should be easy to do."

The authors found the opposite.
When they measured the "distance" (or computational cost) of these simple objects, they found they were maximally complex.

• The Metaphor: Imagine a Rubik's Cube. You might think the "simple" move is just turning one face. But in this new quantum world, even turning one face requires you to run a massive, parallel computation across many universes and filter the results perfectly.
• The Result: These "simple" symmetries are actually the hardest things to simulate on a computer. They are so complex that they are "maximally distant" from doing nothing.

4. Why Does This Matter?

Why should a regular person care about quantum magic tricks?

1. New Physics: It helps us understand the deep structure of the universe. It turns out the universe has "symmetries" that are much richer and weirder than we thought.
2. Quantum Computing: It tells us that to simulate these new symmetries, we need powerful computers. It sets a benchmark for how hard it is to break or simulate these rules.
3. Holography (The Universe as a Hologram): The authors hint that this "distance" might explain why some parts of the universe (like black holes or the "bulk" of space) are so computationally complex. It connects the math of symmetry to the geometry of space-time.

Summary

The paper takes a weird, new kind of quantum rule (Non-Invertible Symmetry), realizes it's basically a "parallel universe computer with a filter," and invents a new ruler to measure how hard it is to perform. They discovered that the "simplest" rules in this new system are actually the most computationally difficult to pull off, turning our intuition about simplicity on its head.

Technical Summary

1. Problem Statement

The paper addresses the challenge of defining and quantifying the complexity and proximity of non-invertible symmetries in Quantum Field Theories (QFTs).

• Context: Traditional symmetries in QFT are described by unitary representations of groups, where operators satisfy strict group multiplication laws. Recent developments have identified non-invertible symmetries, where the product of operators follows a fusion rule ($X_i X_j = \sum_k N_{ij}^k X_k$) rather than a group law. These operators are not unitary and alter the norm of quantum states.
• The Gap: Standard measures of quantum complexity (e.g., Nielsen's geometric complexity) rely on the geometry of Lie groups ($U(2^N)$) and unitary operators. There is no established framework to define a "distance" or "complexity" for non-invertible operators, which are linear combinations of unitary operators (LCUs) and often involve post-selection.
• Goal: To generalize the concept of gate complexity and distance metrics to include non-invertible symmetries, treating them as a specific class of quantum gates within a broader computational framework.

2. Methodology

A. Interpretation as Linear Combinations of Unitaries (LCUs)

The authors interpret non-invertible symmetry operators as Linear Combinations of Unitaries (LCUs):
$$O_w = \sum_i w_i g_i, \quad \text{with} \quad \sum w_i = 1, \quad w_i \in [0, 1]$$

• Parallel Computation Model: They visualize the action of an LCU as a collection of parallel quantum computations (using unitary gates $U_i$) acting on an ancillary Hilbert space.
• Post-Selection: The desired LCU operation is recovered by applying a "prepare" operator $P_w$ to the ancilla, performing the parallel unitaries, and then post-selecting (projecting) the ancilla back to a specific state (e.g., $|0\rangle$). This maps non-invertible symmetries to the complexity class PostBQP.

B. Defining the Distance Measure

To quantify the "distance" between two operators $X$ and $Y$ (which may be non-unitary), the authors propose a metric based on the distinguishability of quantum states rather than simple operator norms.

• Reference State: They introduce a reference mixed state $\rho$ and its canonical purification $|\psi_\rho\rangle$ in a doubled Hilbert space ($H \otimes H^*$).
• Trace Distance: The distance is defined using the trace distance between the purified states after the operators act on them. For operators $X$ and $Y$, the distance $D_\rho(X, Y)$ is:
  $$D_\rho(X, Y) = \sqrt{1 - \frac{|\langle X, Y \rangle_\rho|^2}{\langle X, X \rangle_\rho \langle Y, Y \rangle_\rho}}$$
  where the inner product is defined as $\langle A, B \rangle_\rho = \text{Tr}(\rho A^\dagger B)$.
• Properties: This metric is scale-invariant, satisfies the triangle inequality, and reduces to standard geometric distances (like the Killing metric) in the limit of unitary operators and maximally mixed states.

C. Infinitesimal Limit and Complexity Metrics

The authors derive an infinitesimal line element $ds^2$ from the distance measure:
$$ds^2 = \frac{\langle dX, dX \rangle}{\langle X, X \rangle} - \left| \frac{\langle X, dX \rangle}{\langle X, X \rangle} \right|^2$$

• This generalizes the Nielsen complexity measure. By introducing a penalty tensor $I_{IJ}$ on the tangent space directions, they can define "generalized complexity metrics" that penalize certain types of operations (e.g., multi-qubit interactions) more heavily, similar to how Nielsen's approach works for unitary gates.

3. Key Contributions

1. Unification of Symmetries and Computation: The paper establishes a rigorous framework viewing non-invertible symmetries as LCUs implementable via parallel quantum circuits with post-selection.
2. Generalized Distance Metric: It provides a novel, information-theoretic distance measure applicable to both continuous and discrete, invertible and non-invertible symmetries. This metric generalizes the Killing metric of Lie groups to the space of LCUs.
3. Complexity of Simple Objects: A counter-intuitive finding is that the "simple objects" (the fundamental generators) of a symmetry category can be computationally maximally complex.
4. Explicit Calculations: The authors compute these distances explicitly for several physical systems, demonstrating the utility of the formalism.

4. Results

The authors applied their distance measure to three distinct examples:

A. 4D O(2) Gauge Theory

• Setup: Maxwell theory with gauged charge conjugation symmetry.
• Result: The distance between electric 1-form symmetry operators depends on the parameter $\alpha$ and the choice of density matrix $\rho$. The metric function $F(\alpha)$ is non-trivial and vanishes at $\alpha=0$, recovering the identity.

B. 2D Rational Conformal Field Theories (RCFTs)

• Setup: Verlinde lines in models like $\widehat{su}(2)_k$ WZW and $(A_p, A_{p'})$ minimal models.
• Low Temperature Limit ($\beta \to \infty$): The distance is dominated by the lowest weight primaries. The distance scales with an exponential suppression factor $\epsilon$ and depends on the modular $S$-matrix elements.
• High Temperature Limit ($\beta \to 0$): The reference state approaches the maximally mixed state. The distance between distinct Verlinde lines becomes maximal ($D=1$), while identical lines have distance 0. This indicates a discrete topology in the high-temperature limit.

C. Symmetric Orbifold CFTs

• Setup: $N$-fold symmetric product of a 2D CFT ($Sym^N \mathcal{C}$), relevant to the D1-D5 system.
• Result: Similar to RCFTs, in the high-temperature limit, the distance between operators corresponding to different conjugacy classes of the symmetric group $S_N$ is maximal ($D=1$).

D. Computational Complexity Conclusion

• In the high-temperature (maximally mixed) limit, the distance between distinct non-invertible symmetry operators is maximal.
• Since the "round" Killing metric serves as a lower bound for gate complexity, this implies that non-invertible symmetries are computationally hard. They cannot be efficiently simulated by a small number of standard unitary gates; they require complex circuits involving post-selection.

5. Significance

• Theoretical Physics: This work bridges the gap between the abstract algebraic structure of generalized symmetries (fusion categories) and concrete quantum computational resources. It suggests that non-invertible symmetries are not just algebraic curiosities but represent high-complexity operations.
• Holography and Quantum Gravity: The authors suggest applications in holographic systems (AdS/CFT). If non-invertible symmetries are maximally complex, they may correspond to complex bulk geometries (e.g., "Python's Lunch" configurations) or specific features in the Symmetry Topological Field Theory (SymTFT) bulk.
• Effective Field Theory (EFT): The existence of a well-defined metric on the space of non-invertible symmetries could play a role analogous to the coset space metric in Goldstone boson EFTs, potentially aiding in the construction of effective actions for systems with spontaneous breaking of non-invertible symmetries.
• Quantum Information: It provides a new tool for analyzing the complexity of quantum channels and non-unitary operations, extending the reach of Nielsen's geometric complexity beyond unitary evolution.

In summary, the paper successfully generalizes the geometric notion of complexity to the realm of non-invertible symmetries, revealing that these "simple" algebraic objects are, in fact, maximally complex from a computational perspective.