Algebraic Speedups for Exact Inversion of Hamiltonian Evolutions

Technical Summary: Algebraic Speedups for Exact Inversion of Hamiltonian Evolutions

Problem Statement
Reversing a many-body quantum evolution is a fundamental operation for protocols such as Loschmidt echoes, echo-based verification, and out-of-time-order correlator (OTOC) measurements. Ideally, reversing an evolution $U = e^{-iHt}$ requires implementing $U^\dagger = e^{iHt}$. However, in experimental settings, while the interaction graph and allowed coupling terms (the generators $H_j$) are known, the realized coupling strengths and detunings (the parameters $x_j$) are often imperfectly calibrated or drift over time.

The central problem addressed is the deterministic exact inversion of a unitary family $U(x) = \exp(i \sum_j x_j H_j)$ where the generators $H_j$ are known but the coefficients $x$ are hidden. The goal is to determine the minimal number of forward calls to $U(x)$ required to implement $U(x)^\dagger$ (up to a global phase) for every allowed $x$, without estimating $x$. While deterministic exact inversion of an arbitrary $d$-dimensional unitary generally requires $\Theta(d^2)$ queries, this paper investigates whether the algebraic structure of specific Hamiltonian families can reduce this cost to a polynomial or even constant dependence on the system size, rather than the exponential dependence on the full Hilbert space dimension.

Methodology
The authors employ a framework of quantum combs, where a fixed quantum circuit interleaves $q$ forward calls to $U(x)$ with parameter-independent gates. The analysis proceeds in three stages based on the algebraic properties of the generators:

1. Commuting Hamiltonians (Fixed Eigenbasis):
   For families where generators commute, the system possesses a fixed eigenbasis. The authors define the set of eigenvalues $\Lambda$ and analyze the additive structure of sums of these eigenvalues. They establish that the optimal query number is determined by whether a specific additive relation can be satisfied: for every distinct eigenvalue $\lambda$, there must exist a sum of $q$ eigenvalues (with repetition) that equals a common target value $c - \lambda$. This reduces the problem to finding the minimum $q$ such that $c - \Lambda \subseteq \Sigma_q(\Lambda)$, where $\Sigma_q(\Lambda)$ is the set of all sums of $q$ elements from $\Lambda$.

2. General (Non-Commuting) Hamiltonians:
   For non-commuting generators, the eigenbasis depends on $x$, rendering the spectral approach inapplicable. Instead, the authors utilize Wedderburn decomposition from the theory of finite-dimensional matrix algebras. They show that the algebra generated by the known Hamiltonian terms decomposes into a direct sum of inequivalent matrix families (symmetry sectors). Crucially, they prove that repeated copies of the same symmetry sector (passive multiplicities) do not increase the query complexity. The problem reduces to inverting the inequivalent active blocks and then coherently combining their inverses.

3. Phase Alignment:
   To combine inverses from different sectors into a global inverse, the authors derive a sufficient condition for phase synchronization. They show that if the residual phases from the inversion of each sector can be matched (often by padding with extra forward calls), a coherent global inverse can be constructed. This condition depends on the trace vectors of the restricted generators.

Key Contributions and Results

• Exact Query Bounds for Commuting Families: The paper provides an exact formula for the reversing cost $\kappa(\Lambda)$ for one-parameter and multi-parameter commuting families. The cost is determined solely by the distinct joint-eigenvalue vectors, independent of eigenspace multiplicities. For a system with $K$ distinct eigenspaces, the cost is bounded by $K-1$.
• Reduction via Wedderburn Decomposition: For general families, the authors prove that the query complexity is governed by the dimensions of the inequivalent irreducible representations ($d_\alpha$) rather than the total Hilbert space dimension. The upper bound for the query number is given by $\sum_\alpha (q_\alpha + 1) - 1$, where $q_\alpha$ is the cost to invert the $\alpha$-th sector.
• Application to Physical Models: The authors apply these theoretical bounds to three specific many-body systems, demonstrating significant speedups over "dimension-only" benchmarks (which treat the space as an arbitrary unitary):
  • Tavis-Cummings Dynamics: For a system of $n$ emitters coupled to $M$ modes with an excitation cutoff $N$, the reversing cost is $O_{M,N}(1)$, independent of $n$. This contrasts with the $O(n^{2N})$ cost for an arbitrary unitary.
  • Collective-Spin Echo: For Ising- and Lipkin–Meshkov–Glick-type Hamiltonians, the cost is $O(n^3)$, improving upon the $O(4^n)$ dimension-only benchmark.
  • Passive Multimode Links: For $n$ optical modes with an unknown Hermitian coupling matrix, the cost is $O(Nn^2)$ for $N$ photons. For specific structures like circulant couplings (ring topology) or rank-one bright-mode families, the cost reduces to $O(n)$ or even $O(1)$ (specifically $q=n$ and $q=2$ respectively for $N=2$).

Significance
The paper establishes that structure-dependent bounds can drastically reduce the cost of reversing unknown quantum dynamics. The primary significance lies in demonstrating that a rapidly growing many-body Hilbert space does not necessarily imply an intractable inversion problem; much of the space may consist of redundant copies of the same unknown action, which can be bypassed via algebraic reduction.

The work distinguishes between Hamiltonian simulation (governed by locality, sparsity, and time) and Hamiltonian inversion (governed by the ability to coherently combine forward evolutions to reproduce the inverse). The authors argue that exact spectral relations can make inversion cheap, even when simulation might be costly, and that this "coherent reversibility" serves as an independent resource for quantum control and sensing, particularly in scenarios where nuisance parameters are unknown but the interaction structure is fixed.