arXiv:2610.03686
Efficient Block Encoding of Structured Hamiltonians by Separating Where and What
Alessandro Summer, François Jamet
Abstract
In fault-tolerant block encodings of structured Hamiltonians, the support geometry can set how the non-Clifford cost of SELECT scales with the system size, however many operators act on each support. We construct permute-act-unpermute circuits: a CSWAP network fixed by this geometry brings a selected support to a fixed target register, a shared local circuit acts there, and the permutation is undone. The operators add only an $XZ$ mask on this register, at a cost independent of the system size, and one query can mix several support geometries. For two-site supports, we establish and attain the minimum CSWAP count within address-controlled networks of site transpositions. Compiled for Pauli terms, these circuits use $8\mathrm{S}N+o(N)$ $T$ gates with $O(\log N)$ permutation work qubits, where $N$ is the number of system qubits and $\mathrm{S}$ is determined by the support geometry, with $\mathrm{S}=1$ for nearest-neighbour interactions and $\mathrm{S}=3/2$ for all-to-all pairs; in both cases the correction is $O(\log N)$. We also introduce a bridged CSWAP, which remembers the logical value of its temporary AND across the target action and repairs it from the prepared labels, so that the inverse CSWAP undoes the exchange without recomputing the value. When the repair is Clifford, it halves the $T$ count of a matched forward-inverse CSWAP pair at the cost of one retained work qubit. For a Heisenberg ring, the complete block-encoding query reduces the $T$ count by a factor approaching $3$ as the system size grows, relative to flat and product-wise Pauli walks. For a five-orbital Anderson impurity model, which combines nearest-neighbour and all-to-all support geometries, the reduction is about $1.7$ at large bath sizes, relative to the cheapest of three comparators, each built from the methods of the references it follows.
AI Summary
The paper asks how support geometry and repeated local operators can reduce fault-tolerant Hamiltonian block-encoding costs. It constructs SELECT as permute–act–unpermute: an address-controlled CSWAP network moves the selected support to a fixed register, where a shared circuit applies the operator. For Pauli LCUs, additional operator classes change only a local $XZ$ mask; coefficient-loading costs remain in PREPARE. For pair supports on $N$ sites, the minimum number of CSWAPs within address-controlled site-transposition networks is $\lceil N+\chi/2-3\rceil$, where $\chi$ is the support graph’s chromatic number. A backwards-reachability lower bound and matching swap-tree constructions establish this count. The resulting SELECT costs $8N+O(\log N)$ $T$ gates for nearest-neighbour supports and $12N+O(\log N)$ for all-to-all pairs, with $O(\log N)$ permutation workspace. A “bridged” CSWAP retains and repairs its temporary AND across the target action, halving a matched forward–inverse pair’s $T$ cost when repair is Clifford, at one retained ancilla per pair. Complete-query accounting gives asymptotic reductions of $3\times$ for a Heisenberg ring and about $1.7\times$ for a five-orbital Anderson impurity model against the stated comparators. Incorporating measured lookup erasure into the structured AIM comparator reduces the latter advantage to $4/3$. These are constant-factor gains; bridging affects only subleading terms in the examples. CSWAP optimality excludes control-computation costs and other permutation primitives. Efficient controls depend on address encoding, and optimal leading counts for complete supports of four or more sites remain open.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.