Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.03686

Efficient Block Encoding of Structured Hamiltonians by Separating Where and What

Alessandro Summer, François Jamet

quant-phcond-mat.stat-mechcond-mat.str-elSubmitted Oct 2, 2026• Announced Oct 5, 2026• 2 citations• Revised Oct 5, 2026 (v2)
v1 · Oct 2, 2026v2 · Oct 5, 2026
arXivHTMLPDF

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.

Little sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Optimal T-Count for Block Encodings of Fermionic and Spin Hamiltonians

Jiaxin Ma, Kevin J. Joven, Yuan Liu

We determine the non-Clifford $T$-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford$+T$ model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an $n$-qubit operator with $a$ clean ancillas and at most $s$ $T$ gates can be compressed to use at most $\min\{a,n+2s\}$ ancillas, without increasing the absolute error or $T$-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error $ε$, a volume-covering argument combined with circuit counting gives the worst-case lower bound $Ω(n^2\sqrt{\log(n^4/ε)})$, matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on $n$ spins, we obtain independent lower bounds $Ω(n)$ from stabilizer nullity and $Ω(\log(1/ε))$ from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling $Θ(n+\log(1/ε))$. As an application, we evaluate the $T$-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation $T$-count scales as the query count times the optimal $T$-count per query.

quant-pharXiv:2609.11153•Sep 11, 2026•1 citation

Low-frustration block encodings by patch routing

Minzhao Liu, Abeynaya Gnanasekaran, Ananth Kaushik +4 more

Block-encoding has emerged as a core primitive in many quantum algorithms, including quantum simulation. In this work, we design efficient and extensible methods for generating low-frustration block encodings of frustrated lattice Hamiltonians built from repeated local interaction patches through a technique we call "patch routing". We construct block encodings for a full Hamiltonian by first block-encoding a small local patch and then using a SWAP-style routing network to coherently apply the local patch encoding across the lattice. The expensive, local block-encoding cost is paid only once per query and is independent of lattice size, whereas the comparatively inexpensive routing network grows linearly with the lattice size, dominating at large sizes. Our method allows for a hierarchical structure in which larger patches can be block-encoded with small normalization factors, albeit at a higher (local, non-extensive) block-encoding cost, thereby reducing overall query complexity in an algorithm. We exploit symmetries and algebraic structures in local interactions to construct efficient block encodings, and we apply these techniques to the Heisenberg, Fermi-Hubbard, and honeycomb spin-liquid models. For a $120\times 120$ square-lattice $J_1$-$J_2$ Heisenberg model near maximal frustration ($J_2/J_1=0.4-0.6$), our methods result in a $15-17\times$ reduction in the leading $T$ cost per qubitized-QPE run (ignoring initial state preparation and overlap) relative to prior state-of-the-art Pauli LCU constructions. Corresponding reductions are approximately $3\times$ for the $120\times120$ Fermi-Hubbard model at half-filling. For time evolution of the honeycomb spin-liquid model on $120\times120$ unit cells, the leading cost is reduced by $5\times$. Our framework provides a systematic way forward for larger and more accurate fault-tolerant simulations of real-world quantum systems.

quant-pharXiv:2610.32946•Oct 26, 2026•1 citation

Clifford Circuit Synthesis for Distributed Quantum Architectures with Arbitrary Network Topology

Tuomas Laakkonen

To achieve large-scale fault-tolerant quantum computation, it may be easier to combine many small sets of qubits than to construct a single large set. For example via quantum error correction with block codes, or distributed quantum processors utilizing shared entanglement. In these regimes, the time or error budget of the overall quantum computation may be dominated by non-local operations. Hence, it is worthwhile to minimize the number of these operations. We consider the case where both non-local and local connectivity may be arbitrarily restricted, and give an asymptotically optimal synthesis method for distributed CNOT and Clifford circuits, based on block-matrix Gaussian elimination. We extend this to all Clifford+RZ circuits by generalizing the Pauli exponential circuit representation; this naturally integrates with existing methods for optimizing T-count. As an application, we show how to implement CNOT circuits in a CSS code encoding n logical qubits in k blocks using O(nk) inter-block transversal CNOTs and intra-block Pauli measurements.

quant-pharXiv:2608.13543•Aug 14, 2026•0 citations

$T$-efficient unitary synthesis via block-sparse Hamiltonian simulation

Diyi Liu, Shuchen Zhu, Wibe Albert de Jong +3 more

We construct Clifford+$T$ circuits implementing arbitrary $n$-qubit unitaries with worst-case $T$-count $\widetilde{O}(N^{8/7})$ at constant operator-norm error, where $N=2^n$, improving the previous exponent $5/4$. The construction uses $\widetilde{O}(N^{6/7})$ clean ancillas. The main idea is to reduce the data addressed by each query to the block-encoding circuit for a sparse piece while controlling the additional simulation work needed to combine the pieces. We simulate a Hermitian logarithm of the target by flattening its traceless part with a two-layer random similarity transformation, randomly partitioning the transformed generator into block-sparse Hermitian pieces, and combining their evolutions using qDRIFT. For a target operator-norm error $ε\in(0,1/2)$, let $L=\log_2(N/ε)$, the qubit count plus the requested bits of accuracy. By successively correcting the approximation error, we obtain a circuit using $\widetilde{O}(N^{8/7}L^{3/7}+NL)$ $T$ gates and $\widetilde{O}(N)$ clean ancillas whenever $L\le N$. We also prove that, at constant precision, the exponent $8/7$ is optimal within a sequential block-SELECT model.

quant-pharXiv:2610.18589•Oct 14, 2026•0 citations

Beyond Orbital Rotations: Correlation-Rank Limits and Clifford-Accessible Measurement, from Algebra and Global Optimization

Federico Zahariev, Vanda Glezakou

One should not assume that reconstructing an electronic observable with a smaller set of measurement settings will cut the number of repetitions in proportion. Each setting is simply a basis change and qubit readout, but the savings are not guaranteed to be commensurate. Take two electrons of opposite spin in two spatial orbitals: the orbital degree of freedom of each electron acts as a logical qubit and rotations are independent in the spin sectors. From the observable's one- and two-qubit coefficients we derive an exact floor for the setting count and a decomposition to meet it in no more than three settings. With fewer settings, the minimum error in the two-qubit correlation coefficients is set by the singular values left out. A case in point is an exchange with equal nonzero couplings on the three Pauli axes. This demands three orbital settings yet only one joint measurement. We offer a Clifford circuit for four physical qubits to effect the necessary mapping of Pauli products under conjugation. In the case of a one-parameter family of logical singlet-triplet mixtures, the orbital-to-Clifford shot cost ratio is three at maximum mixing and trends toward 3/2 near the logical singlet. Where spin sectors may be mixed, isotropic exchange needs one orbital setting. For spin-conserving Hamiltonians with $N$ spatial orbitals encoded via Jordan-Wigner, the $X$-rank, the binary rank of the $X$ parts of its strings, of any commuting Pauli string family is no more than $2(N-1)$. Searches with the Robust Adaptive Nature-inspired Global Explorer (RANGE) reach this limit for CH$_4$, with the rank of the Hamiltonian support vouching for the maximality of the search values. And for all nonidentity Pauli strings on $n$ qubits, semidefinite witnesses from the Lovász theta number give a lower bound on the Clifford setting count that agrees with the integer cover and counting bounds at $2^n+1$.

quant-pharXiv:2607.16869•Jul 21, 2026•0 citations

Low-gate-count block encodings for second-quantized fermionic Hamiltonians

Diyi Liu, Shuchen Zhu, Lin Lin +2 more

Efficient block encoding of many-body Hamiltonians is a central requirement for quantum algorithms in scientific computing, particularly in the early fault-tolerant era. In this work, we introduce new explicit constructions for block encoding second-quantized Hamiltonians that substantially reduce Clifford+T gate complexity and ancilla overhead. By utilizing a data lookup strategy based on the SWAP architecture for the sparsity oracle $O_C$, and a direct sampling method for the amplitude oracle $O_A$ with SELECT-SWAP architecture, we achieve a T count that scales as $\mathcal{\tilde{O}}(\sqrt{L})$ with respect to the number of interaction terms $L$ in general second-quantized Hamiltonians. We also achieve an improved constant factor in the Clifford gate count of our oracle. Furthermore, we design a block encoding that directly targets the $η$-particle subspace, thereby reducing the subnormalization factor from $\mathcal{O}(L)$ to $\mathcal{O}(\sqrt{L})$, and improving fault-tolerant efficiency when simulating systems with fixed particle numbers. Building on the block encoding framework developed for general many-body Hamiltonians, we extend our approach to electronic Hamiltonians whose coefficient tensors exhibit translation invariance or possess decaying structures. Our results provide a practical path toward early fault-tolerant quantum simulation of many-body systems, substantially lowering resource overheads compared to previous methods.

arXiv:2510.08644•Oct 9, 2025•19 citations
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 XZXZXZ 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 8SN+o(N)8\mathrm{S}N+o(N)8SN+o(N) TTT gates with O(log⁡N)O(\log N)O(logN) permutation work qubits, where NNN is the number of system qubits and S\mathrm{S}S is determined by the support geometry, with S=1\mathrm{S}=1S=1 for nearest-neighbour interactions and S=3/2\mathrm{S}=3/2S=3/2 for all-to-all pairs; in both cases the correction is O(log⁡N)O(\log N)O(logN). 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 TTT 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 TTT count by a factor approaching 333 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.71.71.7 at large bath sizes, relative to the cheapest of three comparators, each built from the methods of the references it follows.
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 XZXZXZ mask; coefficient-loading costs remain in PREPARE.
For pair supports on NNN sites, the minimum number of CSWAPs within address-controlled site-transposition networks is ⌈N+χ/2−3⌉\lceil N+\chi/2-3\rceil⌈N+χ/2−3⌉, 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)8N+O(\log N)8N+O(logN) TTT gates for nearest-neighbour supports and 12N+O(log⁡N)12N+O(\log N)12N+O(logN) for all-to-all pairs, with O(log⁡N)O(\log N)O(logN) permutation workspace. A “bridged” CSWAP retains and repairs its temporary AND across the target action, halving a matched forward–inverse pair’s TTT cost when repair is Clifford, at one retained ancilla per pair.
Complete-query accounting gives asymptotic reductions of 3×3\times3× for a Heisenberg ring and about 1.7×1.7\times1.7× 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/34/34/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.
We determine the non-Clifford TTT-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford+T+T+T model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an nnn-qubit operator with aaa clean ancillas and at most sss TTT gates can be compressed to use at most min⁡{a,n+2s}\min\{a,n+2s\}min{a,n+2s} ancillas, without increasing the absolute error or TTT-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error εεε, a volume-covering argument combined with circuit counting gives the worst-case lower bound Ω(n2log⁡(n4/ε))Ω(n^2\sqrt{\log(n^4/ε)})Ω(n2log(n4/ε)​), matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on nnn spins, we obtain independent lower bounds Ω(n)Ω(n)Ω(n) from stabilizer nullity and Ω(log⁡(1/ε))Ω(\log(1/ε))Ω(log(1/ε)) from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling Θ(n+log⁡(1/ε))Θ(n+\log(1/ε))Θ(n+log(1/ε)). As an application, we evaluate the TTT-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation TTT-count scales as the query count times the optimal TTT-count per query.
Block-encoding has emerged as a core primitive in many quantum algorithms, including quantum simulation. In this work, we design efficient and extensible methods for generating low-frustration block encodings of frustrated lattice Hamiltonians built from repeated local interaction patches through a technique we call "patch routing". We construct block encodings for a full Hamiltonian by first block-encoding a small local patch and then using a SWAP-style routing network to coherently apply the local patch encoding across the lattice. The expensive, local block-encoding cost is paid only once per query and is independent of lattice size, whereas the comparatively inexpensive routing network grows linearly with the lattice size, dominating at large sizes. Our method allows for a hierarchical structure in which larger patches can be block-encoded with small normalization factors, albeit at a higher (local, non-extensive) block-encoding cost, thereby reducing overall query complexity in an algorithm. We exploit symmetries and algebraic structures in local interactions to construct efficient block encodings, and we apply these techniques to the Heisenberg, Fermi-Hubbard, and honeycomb spin-liquid models. For a 120×120120\times 120120×120 square-lattice J1J_1J1​-J2J_2J2​ Heisenberg model near maximal frustration (J2/J1=0.4−0.6J_2/J_1=0.4-0.6J2​/J1​=0.4−0.6), our methods result in a 15−17×15-17\times15−17× reduction in the leading TTT cost per qubitized-QPE run (ignoring initial state preparation and overlap) relative to prior state-of-the-art Pauli LCU constructions. Corresponding reductions are approximately 3×3\times3× for the 120×120120\times120120×120 Fermi-Hubbard model at half-filling. For time evolution of the honeycomb spin-liquid model on 120×120120\times120120×120 unit cells, the leading cost is reduced by 5×5\times5×. Our framework provides a systematic way forward for larger and more accurate fault-tolerant simulations of real-world quantum systems.
To achieve large-scale fault-tolerant quantum computation, it may be easier to combine many small sets of qubits than to construct a single large set. For example via quantum error correction with block codes, or distributed quantum processors utilizing shared entanglement. In these regimes, the time or error budget of the overall quantum computation may be dominated by non-local operations. Hence, it is worthwhile to minimize the number of these operations. We consider the case where both non-local and local connectivity may be arbitrarily restricted, and give an asymptotically optimal synthesis method for distributed CNOT and Clifford circuits, based on block-matrix Gaussian elimination. We extend this to all Clifford+RZ circuits by generalizing the Pauli exponential circuit representation; this naturally integrates with existing methods for optimizing T-count. As an application, we show how to implement CNOT circuits in a CSS code encoding n logical qubits in k blocks using O(nk) inter-block transversal CNOTs and intra-block Pauli measurements.
TTT-efficient unitary synthesis via block-sparse Hamiltonian simulation
We construct Clifford+TTT circuits implementing arbitrary nnn-qubit unitaries with worst-case TTT-count O~(N8/7)\widetilde{O}(N^{8/7})O(N8/7) at constant operator-norm error, where N=2nN=2^nN=2n, improving the previous exponent 5/45/45/4. The construction uses O~(N6/7)\widetilde{O}(N^{6/7})O(N6/7) clean ancillas. The main idea is to reduce the data addressed by each query to the block-encoding circuit for a sparse piece while controlling the additional simulation work needed to combine the pieces. We simulate a Hermitian logarithm of the target by flattening its traceless part with a two-layer random similarity transformation, randomly partitioning the transformed generator into block-sparse Hermitian pieces, and combining their evolutions using qDRIFT. For a target operator-norm error ε∈(0,1/2)ε\in(0,1/2)ε∈(0,1/2), let L=log⁡2(N/ε)L=\log_2(N/ε)L=log2​(N/ε), the qubit count plus the requested bits of accuracy. By successively correcting the approximation error, we obtain a circuit using O~(N8/7L3/7+NL)\widetilde{O}(N^{8/7}L^{3/7}+NL)O(N8/7L3/7+NL) TTT gates and O~(N)\widetilde{O}(N)O(N) clean ancillas whenever L≤NL\le NL≤N. We also prove that, at constant precision, the exponent 8/78/78/7 is optimal within a sequential block-SELECT model.
One should not assume that reconstructing an electronic observable with a smaller set of measurement settings will cut the number of repetitions in proportion. Each setting is simply a basis change and qubit readout, but the savings are not guaranteed to be commensurate. Take two electrons of opposite spin in two spatial orbitals: the orbital degree of freedom of each electron acts as a logical qubit and rotations are independent in the spin sectors. From the observable's one- and two-qubit coefficients we derive an exact floor for the setting count and a decomposition to meet it in no more than three settings. With fewer settings, the minimum error in the two-qubit correlation coefficients is set by the singular values left out. A case in point is an exchange with equal nonzero couplings on the three Pauli axes. This demands three orbital settings yet only one joint measurement. We offer a Clifford circuit for four physical qubits to effect the necessary mapping of Pauli products under conjugation. In the case of a one-parameter family of logical singlet-triplet mixtures, the orbital-to-Clifford shot cost ratio is three at maximum mixing and trends toward 3/2 near the logical singlet. Where spin sectors may be mixed, isotropic exchange needs one orbital setting. For spin-conserving Hamiltonians with NNN spatial orbitals encoded via Jordan-Wigner, the XXX-rank, the binary rank of the XXX parts of its strings, of any commuting Pauli string family is no more than 2(N−1)2(N-1)2(N−1). Searches with the Robust Adaptive Nature-inspired Global Explorer (RANGE) reach this limit for CH4_44​, with the rank of the Hamiltonian support vouching for the maximality of the search values. And for all nonidentity Pauli strings on nnn qubits, semidefinite witnesses from the Lovász theta number give a lower bound on the Clifford setting count that agrees with the integer cover and counting bounds at 2n+12^n+12n+1.
Efficient block encoding of many-body Hamiltonians is a central requirement for quantum algorithms in scientific computing, particularly in the early fault-tolerant era. In this work, we introduce new explicit constructions for block encoding second-quantized Hamiltonians that substantially reduce Clifford+T gate complexity and ancilla overhead. By utilizing a data lookup strategy based on the SWAP architecture for the sparsity oracle OCO_COC​, and a direct sampling method for the amplitude oracle OAO_AOA​ with SELECT-SWAP architecture, we achieve a T count that scales as O~(L)\mathcal{\tilde{O}}(\sqrt{L})O~(L​) with respect to the number of interaction terms LLL in general second-quantized Hamiltonians. We also achieve an improved constant factor in the Clifford gate count of our oracle. Furthermore, we design a block encoding that directly targets the ηηη-particle subspace, thereby reducing the subnormalization factor from O(L)\mathcal{O}(L)O(L) to O(L)\mathcal{O}(\sqrt{L})O(L​), and improving fault-tolerant efficiency when simulating systems with fixed particle numbers. Building on the block encoding framework developed for general many-body Hamiltonians, we extend our approach to electronic Hamiltonians whose coefficient tensors exhibit translation invariance or possess decaying structures. Our results provide a practical path toward early fault-tolerant quantum simulation of many-body systems, substantially lowering resource overheads compared to previous methods.