Algebraic Speedups for Exact Inversion of Hamiltonian Evolutions

• URL: http://arxiv.org/abs/2607.29382v2
• Date: Tue, 04 Aug 2026 02:54:22 GMT
• Title: Algebraic Speedups for Exact Inversion of Hamiltonian Evolutions
• Abstract summary: We show that additive relations among distinct eigenvalues determine the optimal query number exactly.<n>We also give a sufficient phase-alignment condition under which family-specific structure can reduce the query number.<n>These results establish structure-dependent bounds for reversing the unknown dynamics arising in Tavis-Cummings out-of-time-order correlator protocols.
• Score: 4.384296961818558
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Deterministic exact inversion of an arbitrary $d$-dimensional unitary requires {$Θ(d^2)$} coherent forward calls in the worst case. We ask how this cost changes for Hamiltonian evolution $U(x)=\exp(i\sum_j x_jH_j)$ when the generators are known but the parameters are hidden. For one-parameter families with a fixed eigenbasis, we show that additive relations among the distinct eigenvalues determine the optimal query number exactly, and we construct the corresponding inversion protocol. For general families, we prove that repeated symmetry sectors do not affect the exact query complexity and give an automatic construction for combining inverses from inequivalent active sectors. We also give a sufficient phase-alignment condition under which family-specific structure can reduce the query number. These results establish structure-dependent bounds for reversing the unknown dynamics arising in Tavis-Cummings out-of-time-order correlator protocols, collective-spin echo verification, and passive multimode links, without requiring prior knowledge or explicit estimation of the underlying coupling strengths.

Related papers

• Pathwise Random Hamiltonian Simulation [0.0]
  We introduce Pathwise Random Hamiltonian Simulation (PRHS), which extends qDrift to arbitrary order by subdividing each time step into $M$ correlated slices.<n>PRHS achieves accuracies two to four orders of magnitude beyond qDrift at equal query cost.
  arXiv  Detail & Related papers  (2026-08-30T12:37:58Z)
• Postselection-Free Reconstruction of Monitored SPT Flux-Charge Responses [1.599072005190786]
  A class of monitored topological invariants compares ordinary and symmetry-twisted quantum trajectories with identical records.<n>We replace the twisted quantum experiment by uniformly randomized symmetry eigenstates with known charges, ordinary-boundary monitoring, and an offline twist decoder.
  arXiv  Detail & Related papers  (2026-08-16T01:52:10Z)
• When Rates Are Geometric: Rate-Certificate Transfer for Contact Splittings in Optimization [0.0]
  A contact Hamiltonian $H$ on $J1(mathbbRn)$ obeys the intrinsic decay identity $dot H = -H,partial_s H$.<n>An augmented energy $mathcalE$ built from $H$ is a continuous-time rate certificate whenever $mathcalE$ controls the objective gap.
  arXiv  Detail & Related papers  (2026-07-26T13:12:58Z)
• Beyond Value Benchmarks: Measuring Value-Structure Alignment in Large Language Models via Symmetric Q-Sorts [47.02978329409663]
  We propose a symmetric human-LLM evaluation framework, grounded in Q methodology, to measure value-structure alignment.<n>Under our protocol, humans and models sort an identical 140-item moral statement set into a shared nine-column forced distribution.<n>We evaluate 12 LLMs across four model families via 240 replicated Q-sorts at two temperature settings.
  arXiv  Detail & Related papers  (2026-06-20T08:15:41Z)
• Geometric Factual Recall in Transformers [57.48371649045765]
  A common view casts internal weight matrices as associative memories over pairs of embeddings, requiring memorization counts that scale linearly with the number of facts.<n>We develop a theoretical and empirical account of an alternative, emphgeometric form of memorization in which learned embeddings encode structure directly.<n>In a controlled setting where a single-layer transformer must memorize random vectors from subjects to a shared attribute set, we prove that a logarithmic embedding dimension suffices.<n>We extend these results to the multi-hop setting, providing constructions with and without chain-of-thought that exhibit a provable
  arXiv  Detail & Related papers  (2026-05-12T17:22:22Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses.<n>We establish a fundamental lower bound on the expected number of queries needed to achieve a desired confidence in the accuracy of the clustering.<n>We develop a computationally feasible variant of the Generalized Likelihood Ratio statistic and show that its performance gap to the lower bound can be accurately empirically estimated.
  arXiv  Detail & Related papers  (2026-02-05T14:16:47Z)
• Identification and Estimation of Simultaneous Equation Models Using Higher-Order Cumulant Restrictions [5.882065571122133]
  Identifying structural parameters in linear simultaneous-equation models is a longstanding challenge.<n>We show that neither zero covariance proofs nor whitening is necessary to identify structural parameters.<n>Our framework provides a transparent overidentification test.
  arXiv  Detail & Related papers  (2025-01-12T11:27:39Z)
• Analytical Lower Bound on Query Complexity for Transformations of Unknown Unitary Operations [0.0]
  We establish analytical lower bounds for the query complexity of unitary inversion, transposition, and complex conjugation.<n>Our lower bound of $d2$ for unitary inversion demonstrates the optimality of the deterministic exact inversion protocol.<n>We extend our framework to the partially known setting, where the input unitary operation is promised to be within $mathrmSU(d)$ and the probabilistic subgroup setting.
  arXiv  Detail & Related papers  (2024-05-13T10:35:50Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• Sampled Transformer for Point Sets [80.66097006145999]
  sparse transformer can reduce the computational complexity of the self-attention layers to $O(n)$, whilst still being a universal approximator of continuous sequence-to-sequence functions. We propose an $O(n)$ complexity sampled transformer that can process point set elements directly without any additional inductive bias.
  arXiv  Detail & Related papers  (2023-02-28T06:38:05Z)
• On the order problem in construction of unitary operators for the Variational Quantum Eigensolver [0.0]
  One of the main challenges in the Variational Quantum Eigensolver (VQE) framework is construction of the unitary transformation. We propose an approach based on the Lie algebra - Lie group connection and corresponding closure relations that systematically eliminates the order problem.
  arXiv  Detail & Related papers  (2020-03-16T17:55:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.