Deterministic exact inversion of an arbitrary $d$-dimensional unitary requires {$\Theta(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.
Randomized product formulas such as qDrift offer a resource-efficient alternative to deterministic Trotter--Suzuki decompositions for Hamiltonian simulation, removing their polynomial dependence on the number of Hamiltonian terms. qDrift, however, is intrinsically limited to first order in the evolution time, so its query complexity remains linear in the inverse of the target accuracy, $1/\epsilon$. We introduce Pathwise Random Hamiltonian Simulation (PRHS), which extends qDrift to arbitrary order by subdividing each time step into $M$ correlated slices, each evolving under a term sampled from a quasi-probability distribution that we construct in closed form and prove unique, with a bias decaying factorially in $M$. Optimizing jointly over the number of slices $M$ and the number of independent blocks $N$ interpolates between the standard qDrift protocol at long times and a high-precision regime where the query cost grows slower than any power of $1/\epsilon$, without requiring ancillary qubits. Numerical simulations of five molecular Hamiltonians confirm this advantage, with PRHS achieving accuracies two to four orders of magnitude beyond qDrift at equal query cost.
Unitary $k$-designs provide a resource-efficient framework for emulating Haar randomness up to the $k$-th order. Quench-based protocols have recently been shown to generate such designs, but achieving this typically requires multiple Hamiltonian realizations, even when using temporal ensembles. Here, we show that no independent Hamiltonians are required: a single chaotic Hamiltonian is sufficient to generate approximate unitary $k$-designs, even when that Hamiltonian is spatially local. We introduce a two-Pauli-kick (2PK) protocol, in which unitary evolution under a fixed Hamiltonian is interspersed with two Pauli operator insertions (kicks). We find that the resulting frame potential approaches the Haar value at long times, with deviations suppressed by the inverse Hilbert-space dimension. We verify this for single realizations of Gaussian random matrices, the Majorana and Spin Sachdev-Ye-Kitaev models, and deterministic local quantum spin chains. Remarkably, in deterministic spin systems, the 2PK protocol generates approximate unitary designs in regimes where quench-based protocols are either inapplicable or fail to converge. Furthermore, our protocol provides a finite-temperature extension of the frame potential and establishes an analytic bound in terms of the equilibrium partition function. We discuss a holographic perspective on this mechanism.
We consider the classical analytic linearization problem for vector fields on the torus $\mathbb{T}^d$ close to a constant vector field $\omega$. Our goals are twofold. First, we provide a geometric framework in which the arithmetic condition governing analytic linearization arises naturally from the orbit of a unimodular lattice associated with $\omega$ under a diagonal flow on $\operatorname{SL}(d,\mathbb{Z})\backslash \operatorname{SL}(d,\mathbb{R})$. Within this framework, a summability condition emerges as the natural criterion for convergence. We prove that it is equivalent to several classical formulations of the Brjuno condition for linear forms, including those involving best approximation vectors and switching times of the diagonal flow. As a byproduct, we obtain a new quantitative linearization theorem with fully explicit estimates. In particular, the loss of analyticity of the conjugacy is controlled by a Brjuno function.
N. Chevallier, J. Dias, Jose Gaivao et al.· 0 citations
For Hamiltonian $H = \sum_j h_j$, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms $\|h_j\|$, time $t$, and trace-distance error $\epsilon$. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case $\|h_j\|$ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in $1/\epsilon$, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.
Alexander Zlokapa, Richard R. Allen, A. Harrow· 2 citations
Berlekamp's algorithm factors a squarefree polynomial $f\in\mathbb{F}_q[x]$ by deterministic linear algebra, reducing the problem to splitting an explicit commutative algebra $B\cong\mathbb{F}_q^r$ into its $r$ simple factors. For large odd $q$, the standard efficient splitting step is randomized, while known derandomizations are conditional on the Extended Riemann Hypothesis. We give an unconditional exact quantum implementation in a circuit model permitting single-qubit rotations through efficiently computable angles. The construction uses an unconditional counting argument. For a block containing $s\ge2$ irreducible factors, a quadratic-character test in odd characteristic and an absolute-trace test in characteristic $2$ yield a nonconstant test element with probability $p_{q,s}\ge\tfrac12$, known exactly in advance and depending only on $q$ and $s$, not on the unknown factorization. Exact amplitude amplification therefore converts each randomized test into a procedure succeeding with certainty after one amplification iteration. The resulting algorithm uses exactly $r-1$ quantum splitting rounds and $O(n^3\log q)$ quantum $\mathbb{F}_q$-operations and $O(n^3)$ classical operations, requiring no primitive root, quadratic non-residue, or distinct-degree preprocessing. The method also splits arbitrary finite-dimensional separable commutative $\\mathbb{F}_q$-algebras given by structure constants. Combined with R'onyai's classical structure theory, which computes the radical deterministically and reduces the remaining tasks deterministically to polynomial factorization, it yields the radical and the Wedderburn decomposition of $A/\mathrm{Rad}(A)$ into minimal two-sided ideals, with certainty, for any $n$-dimensional associative $\mathbb{F}_q$-algebra given by structure constants, using $O(n^4\log q)$ quantum $\mathbb{F}_q$-operations.
We study online search for an unknown affine hyperplane in $\mathbb{R}^D$, for arbitrary fixed finite dimension. Building on a companion self-similar cell reduction and support-function formulation, we ask how the mechanism changes as the normal space grows from $\mathbb{S}^0$ to $\mathbb{S}^{D-1}$. In $D=1$, alternation and productivity yield an equal-ripple principle and the exact stationary constant $9$. In $D=2$, the analogous relative equilibrium is a logarithmic spiral whose bottleneck chord imposes tangency and selects the pitch. For exponential orbits $\Gamma(\sigma)=e^{\kappa\sigma}\omega(\sigma)$, we develop log-directional geometry, exponentially discounted memory, gauges, and recursive hyperspherical parametrizations. Without a shape ansatz, the bottleneck admits a certificate supported by at most $D$ historical suppliers, and at globally worst phases the current point lies on the active face. Within regular chambers we derive exact variation, tangency, pitch, age, and, in $D=3$, delay-system identities. Odd-dimensional obstructions, antipodal subclasses, and harmonic towers provide constraints and explicit candidate families but are not claimed globally optimal. Finally, the N-COMP theorem shows that $C_D^*$ is a computable real for every fixed finite $D$ and that algebraic polygonal $\varepsilon$-optimal cells can in principle be synthesized. Numerical screening through $D=10$ is kept separate from the proved results.
Florentin Koch· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
