arXiv:2609.36006
Fast Hamiltonian engineering from cut polytope geometry
Thomas Joachim Friese, Özgün Kum, Aram W. Harrow, Martin Kliesch
Abstract
Hamiltonian engineering (HE) simulates quantum dynamics under a target Hamiltonian using a native entangling system Hamiltonian and restricted control, with applications from quantum gate design to analog quantum simulation. Observing that, for many systems, formulating HE as a linear program only requires specific commutation relations between the control pulses and the system Hamiltonian, we provide a unified framework for broad classes of $2$-local qubit, qudit, and fermionic systems. We reformulate time-optimal HE as a complex $k$-cut polytope problem, with $k$ the number of distinct phases in these commutation relations, and prove it NP-complete for every finite $k$. We therefore relax the polytope to the elliptope and apply a Krivine-type rounding, yielding pulses informed by the system and target Hamiltonians, which we then use in a linear program. We derive how many informed pulses are necessary and sufficient for the linear program to be reliably feasible. Additionally mixing in uniformly sampled pulses guarantees a solution close to the relaxation value from $\mathrm{O}(m)$ pulses, with $m$ the number of interaction terms. Together with upper and lower bounds on the optimal quantum run time, this yields an $\mathrm{O}(\sqrt{m})$ approximation ratio. In benchmarks on a fully connected Ising model, a chiral clock model for qudits, and the fermionic Harper-Hofstadter model, our approach attains near-optimal quantum run times wherever the optimum is computable, reaches run times that saturate with the lattice size in the fermionic case, and outperforms state-of-the-art methods with $\mathrm{O}(m)$ pulses. This establishes a unified approach with provable guarantees to the automatic programming of analog quantum simulators.
AI Summary
The paper studies how to minimize native evolution time when synthesizing a target Hamiltonian by interleaving native dynamics with local pulses. It unifies restricted classes of qubit, qudit, and fermionic systems whose interaction terms acquire relative site phases under conjugation. The coupling ratios define a ray through the complex $k$-cut polytope; its boundary determines the optimal time overhead. Polytope membership is proved NP-complete for every fixed finite $k\geq2$, and NP-hard for continuous phases. The algorithm replaces the polytope by the elliptope, applies inverse-distortion Krivine rounding to generate target-informed pulses, and solves a linear program for their durations. Robust feasibility requires approximately $2D_{\mathrm{eff}}$ samples; the sufficient bound depends on an instance-specific positivity index. Adding uniform samples gives an instance-independent guarantee: $O(m)$ samples, for fixed accuracy and failure probability, achieve overhead at most $(1+\varepsilon)/\hat\gamma$. Frobenius-norm upper bounds and the lower bound $\|M\|_\infty$ imply an $O(\sqrt m)$ approximation ratio. Benchmarks report overheads within 15% of optimum on random 20-qubit Ising targets and within 17% in the median on four-qudit clock-model instances. For Hofstadter lattices up to $20\times20$, informed overheads approach approximately 3.1–4.4, while uniform sampling reaches approximately 48. The framework excludes general two-local Pauli/Weyl interactions and higher-order fermionic terms. The bent-ray search need not find its global optimum. Noncommuting targets require Trotterization; finite-pulse corrections are only sketched. The mixed algorithm is not benchmarked, and its rigorous sampling constants are acknowledged to be loose.
Error found: The abstract overstates the necessary pulse-count result: the proved necessity concerns robust feasibility of a normalized, fixed-run-time LP, not ordinary feasibility of the Hamiltonian-engineering LP.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 51 pages, 10 figures