Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy $\epsilon$, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an $n$-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time $T\ge1$, with circuit depth $O(T\log(nT/\epsilon))$ and gate count $O(nT\log(nT/\epsilon))$. This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb–Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization. Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time $T$ in the stated regime and sufficiently small fixed error $\epsilon$, any nearest-neighbor quantum circuit simulating these dynamics requires depth $\Omega(\log n/\log\log n)$. This matches our $O(\log n)$ upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.

The von Neumann, Tsallis, and R\'enyi entropies are fundamental measures of quantum information. A common estimation strategy multiplies the worst-case costs of spectral transformation and statistical readout, leaving gaps to query lower bounds. We reduce this overhead with multi-level algorithms that use local normalization and precision allocation, while variable-time estimation accounts for the probability of reaching expensive spectral tests. With controlled purified access and its inverse, we obtain bounds for additive error $\varepsilon$, rank upper bound $R$, and fixed order $\alpha$. Tsallis entropy estimation has near-optimal rank-independent query complexity $\widetilde O(\varepsilon^{-1/(\alpha-1)})$ for $1<\alpha<2$, when the allowed dimension and rank accommodate the lower-bound instances, and $\widetilde O(1/\varepsilon)$ for $\alpha\ge2$, where $\widetilde O$ suppresses logarithmic factors. The first saves a factor $1/\varepsilon$; the second extends known integer-order scaling to noninteger orders. We also improve the von Neumann entropy bound from $\widetilde O(R/\varepsilon^2)$ to $\widetilde O(R/\varepsilon)$ and obtain $\widetilde O(R/\varepsilon)$ for noninteger R\'enyi orders $1<\alpha<3$, with further bounds at other orders. Our functional-estimation theorem replaces the global product by a sum of local costs weighted by function magnitudes and spectral masses. We further estimate fixed logarithmic moments and entropy variance using $\widetilde O(R/\varepsilon)$ queries, providing efficient access to fluctuation parameters that enter finite-blocklength quantum compression and pure-state entanglement conversion. More broadly, our framework extends beyond entropy to a broad class of density-matrix functionals, offering a systematic approach toward optimal query complexity in quantum spectral estimation.

Random unitary operations are a fundamental resource for quantum information processing, yet provably generating them with experimentally available controls remains challenging. Existing approaches often require calculating higher-order operator expectation values, relying on statistical assumptions about the experimental Hamiltonian's spectrum to make these calculations tractable. We show how to implement random unitaries by a sequence of evolutions generated by a fixed Hamiltonian conjugated by a global control operator. We give a geometric argument that establishes exponential convergence to the uniform random (Haar) measure on the accessible unitary group under uniform parameter sampling, beyond a finite sequence-length threshold that we bound. We show this holds when the connected Lie subgroup generated by the conjugated Hamiltonians is closed. Native dynamics and global control thus provide a constructive route to uniform randomness, with applications to many experimental platforms including Rydberg atoms, bosons and fermions in optical lattices, transmons, and trapped ions.

Coherent uncomputation can be as costly as the computation itself, creating substantial spacetime overheads that can be prohibitive on early fault-tolerant quantum computers. We develop an algebraic framework for measurement-based uncomputation (MBU) through a quantum error-correction picture: measurements of the garbage register induce relative phases analogous to errors causing non-trivial syndromes. Accepting only zero-syndrome outcomes achieves post-selected MBU, removing the need for an uncomputation oracle at the cost of a probabilistic success rate determined by the affine rank of the populated garbage support. This rank can be much smaller than the number of garbage qubits, as illustrated through an example of the HHL algorithm. We then derive a structural condition under which the original uncomputation oracle can be reused to correct the phase for all measurement outcomes. No correction is required for the zero syndrome, while corrections for non-zero syndromes can be further adapted to individual measurement outcomes for simpler circuits, as illustrated by existing modular-arithmetic, QROM, and QRAM MBU constructions. Phase-correction circuits can be further simplified by co-optimising their implementation with the representation of the measurement-induced phases. Selecting which syndrome classes to correct interpolates between post-selected, partially corrected, and deterministic MBU, enabling trade-offs among correction cost, workspace, and repetitions.

T-state cultivation is a resource-efficient protocol producing logical T states but recent benchmarks show that its logical error rate is considerably higher than intended i.e. than S-state cultivation, which is the analogous protocol for producing logical S states. In this paper, we explain this T-S discrepancy by analytically showing, under circuit-level depolarising noise, that distance-3 (-5) T-state cultivation has fault distance 2 (3) due to Pauli hook errors that propagate to coherent Clifford errors after its final double-check circuit; such errors remain Pauli in S-state cultivation, which consequently retains fault distance 3 (5). As part of our analysis we derive a general formula, and an $\mathcal O(n^3)$-time algorithm for fixed logical-qubit count, for the acceptance probability of a logical mixed state afflicted with a Clifford error, where $n$ is the physical qubit count. We then design flags that detect the malignant hook errors in cultivation, improving the pre-escape logical error rate from $\Theta(p^3)$ to $\Theta(p^5)$. At noise level $p =10^{-3}$, this is a 4.9$\times$ improvement, costing a 1.36$\times$ increase in attempts per accepted shot.