🔬 condensed matter

Efficient Block Encoding of Structured Hamiltonians by Separating Where and What

This paper introduces an efficient block encoding method for structured Hamiltonians that separates the selection of interaction support from the application of operators using permute-act-unpermute circuits, significantly reducing the non-Clifford $T$ -gate cost by scaling with system size rather than the number of terms, without requiring translational symmetry or factorized coefficients.

Original authors: Alessandro Summer, François Jamet

Published 2026-10-05

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Alessandro Summer, François Jamet

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

To understand the challenge this research addresses, one must first look at how scientists hope to use quantum computers to simulate the natural world. The goal is to model complex systems, such as the behavior of electrons in a new material or the dynamics of a chemical reaction, by mimicking their quantum rules. To do this, researchers translate the physical laws governing a system into a mathematical object called a Hamiltonian. This object is essentially a massive list of instructions that tells the computer how the system's energy changes over time. However, for a quantum computer to execute these instructions, it must break them down into a specific sequence of operations. The most expensive part of this process, in terms of the computer's resources and time, is a step called "block encoding." This step prepares the system to be manipulated, and its cost has traditionally been tied directly to the sheer number of terms in the instruction list. If a system has thousands of interacting parts, the cost of simulating it has historically grown in direct proportion to that number, making large-scale simulations prohibitively expensive.

A team of researchers at Alice & Bob in Paris has found a way to break this bottleneck by changing how they organize these instructions. Instead of treating every interaction as a unique, isolated event, they realized that many physical systems share a hidden structure: the same types of forces act repeatedly across different locations. For example, in a ring of atoms, the way two neighbors interact is often identical to how any other pair of neighbors interacts, just at a different spot. The researchers developed a new method that separates the question of "where" an interaction happens from the question of "what" that interaction actually is. By decoupling these two elements, they created a circuit design that reuses the same computational machinery for every location, rather than rebuilding it for every single term. This approach allows the cost of simulating the system to grow only with the size of the system itself, rather than with the total number of interactions, which can be vastly larger.

The core of their innovation is a three-step process they call "permute–act–unpermute." Imagine a library where you need to apply a specific stamp to a book, but the books are scattered across a vast room. The old method would require a librarian to walk to every single book, pick it up, apply the stamp, and put it back, repeating this for every book individually. The new method works differently. First, the librarian uses a clever sorting mechanism to gather all the books that need the same stamp and move them to a single, fixed desk. Once the books are at the desk, the stamp is applied once. Finally, the books are sorted back to their original places. In the quantum circuit, the "sorting" is done by a network of swaps that moves the specific qubits (quantum bits) involved in an interaction to a fixed target area. The "stamp" is the actual quantum operation applied to that fixed area. Because the sorting mechanism depends only on the geometry of the system—how the atoms are arranged—it can be reused for every interaction of that type. This means that even if the system has millions of interactions, the computer only needs to perform the expensive sorting step a number of times proportional to the number of atoms, not the number of interactions.

The researchers tested this idea on two very different physical models to prove its versatility. The first was a Heisenberg ring, a simple model of a chain of magnetic spins where each spin interacts only with its immediate neighbors. In this case, the interactions are local and repetitive. The second model was the Anderson impurity model, which describes a small, complex core of interacting particles surrounded by a large "bath" of non-interacting particles. This model combines local interactions with long-range, all-to-all connections, representing a much more chaotic and difficult scenario. In both cases, the new method dramatically reduced the computational cost. For the simple ring, the number of expensive operations required dropped by a factor of three compared to the best existing methods. For the complex impurity model, the reduction was about 1.7 times, even as the size of the surrounding bath grew to thousands of particles. These improvements were achieved without increasing the number of temporary memory bits the computer needs to hold the calculation, keeping the physical requirements of the machine manageable.

A second, more subtle refinement in their work involves how the computer handles temporary data during the sorting process. When the computer moves qubits around, it creates temporary values that must be erased before the next step to avoid errors. The researchers found that in many cases, they could keep these temporary values alive across the "stamping" step and simply update them, rather than erasing and recalculating them from scratch. This "bridged" approach cuts the cost of certain operations in half, provided the update can be done with simple, low-cost logic. While this saving was most effective in the complex impurity model, where it reduced the cost of specific sub-steps, the primary driver of the overall efficiency was the separation of location and action. The researchers proved mathematically that their sorting networks are the most efficient possible for the types of connections they studied, meaning there is no hidden, more efficient way to perform this specific task.

The significance of this work lies in its ability to make large-scale quantum simulations feasible. By showing that the cost of simulating a system depends on its physical layout rather than the sheer volume of its interactions, the researchers have removed a major barrier to studying complex materials and chemical processes. Their method works for systems with simple, repeating patterns as well as those with complex, all-to-all connections, suggesting it can be applied to a wide range of problems in physics and chemistry. The results indicate that as quantum computers grow larger, they will be able to tackle problems that were previously out of reach, not just by adding more power, but by organizing the work in a way that respects the natural structure of the universe. The researchers have provided a blueprint for building these simulations more efficiently, ensuring that the computational resources are spent on the physics of the problem rather than the overhead of the calculation.

Technical Summary: Efficient Block Encoding of Structured Hamiltonians by Separating Where and What

Problem Statement
Fault-tolerant quantum simulation of many-body systems relies heavily on block encodings of Hamiltonians, where the non-Clifford cost (specifically the $T$ -gate count) is paid at every query. Standard approaches, such as the Linear Combination of Unitaries (LCU) method using unary iteration, treat Hamiltonian terms as a flat list. In these constructions, the Select operation applies a unitary based on a label register. For a Hamiltonian with $L$ terms, the cost of Select typically scales linearly with $L$ .

Many physically relevant Hamiltonians possess significant structure: a small repertoire of local operators (e.g., fields, hopping, exchange) recurs over many supports arranged by a specific geometry (e.g., nearest-neighbor bonds, plaquettes, or all-to-all couplings). In flat-list implementations, the cost grows with the product of the number of operator classes and the number of supports, leading to redundant computations. For example, a flat walk over a Heisenberg ring with $N$ sites and six operator classes per site incurs a cost proportional to $24N$ , whereas the structural redundancy suggests a lower bound is possible.

Methodology
The authors propose a "permute–act–unpermute" architecture for the Select operation that decouples the selection of where an operator acts from what operator is applied.

Separation of Roles:
The Hamiltonian is rewritten as $H = \sum_{j,b} \alpha_{j,b} \Pi_j^{-1} P_T^{(b)} \Pi_j$ .
- Where: The address $j$ selects a support (a set of qubits). A permutation $\Pi_j$ moves this selected support to a fixed target register $T$ of $n_T$ qubits.
- What: A fixed target action $P_T^{(b)}$ applies the operator labeled by $b$ on the fixed register $T$ .
- Unpermute: The inverse permutation $\Pi_j^{-1}$ restores the system register.
This separation ensures that the cost of moving qubits (the permutation) depends only on the geometry of the supports, while the cost of applying the operator depends only on the operator class. These costs add rather than multiply.
Permutation via CSWAP Networks:
The permutation $\Pi_j$ is constructed using Controlled-SWAP (CSWAP) networks derived from swap trees.
- The number of CSWAPs required is determined by the "support geometry," specifically the minimum number of groups ( $\chi$ ) into which sites can be partitioned such that no support contains two sites from the same group.
- For nearest-neighbor bonds (bipartite graphs), $\chi=2$ , allowing the use of two swap trees (one for even sites, one for odd) to bring the selected pair to the target.
- For all-to-all pairs, $\chi=N$ , requiring a more complex network.
- The authors prove that for pair supports, their construction achieves the minimum CSWAP count within address-controlled networks of site transpositions.
Bridged CSWAPs:
A standard CSWAP implementation involves a temporary logical AND (work bit) that is computed, used, and erased (closed). In a matched forward-inverse pair, the standard approach recomputes this work bit for the inverse permutation.
- The authors introduce a "bridged CSWAP" where the work bit is retained across the target action.
- If the target action changes the parity of the data qubits by a known amount $\delta$ (determined by the prepared labels), the work bit is repaired via a Clifford gate ( $X^{c\delta}$ ) before the inverse permutation.
- When the repair is Clifford, this saves one "opening" (4 $T$ gates) per pair, halving the cost of the matched pair at the expense of one live ancilla qubit.

Key Contributions

Structural Decoupling: The paper establishes a framework where the $T$ -gate cost of Select scales with the system size $N$ and the support geometry, rather than the total number of terms $L$ .
Optimal CSWAP Counts: For pair supports, the authors prove that their CSWAP network achieves the minimum count for address-controlled transpositions. The cost is $8SN + O(\log N)$ , where $S$ is a geometry-dependent density ( $S=1$ for nearest-neighbor, $S=3/2$ for all-to-all).
Bridged CSWAPs: A novel technique to reduce the $T$ -count of matched permutation pairs by retaining and repairing temporary AND values, provided the parity change is predictable from the control registers.
Compilation of Specific Models: The framework is instantiated for two distinct Hamiltonian families:
1. Heisenberg Ring: A nearest-neighbor model.
2. Anderson Impurity Model (AIM): A hybrid model combining nearest-neighbor bath chains and an all-to-all impurity core.

Results
The paper provides resource estimates for complete block-encoding queries, comparing the proposed method against the lowest-cost compiled baselines (flat walks, register masks, and tree-based Selects) at unchanged normalization and comparable peak ancilla counts.

Heisenberg Ring:
- The proposed method achieves a $T$ -count of $8N + O(\log N)$ .
- This is a reduction by a factor approaching 3 compared to the best flat-walk comparator ( $24N$ ).
- The reduction arises because the permutation cost is paid once per position, independent of the six operator classes per site.
Anderson Impurity Model (AIM):
- For large bath sizes ( $n_{bath} \gg n_{imp}$ ), the complete query requires approximately 1.7 times fewer $T$ gates than the cheapest matched comparator.
- The leading cost is dominated by the one-body sector (bath chains), which scales as $8N$ . The all-to-all interaction sector contributes subleading terms.
- The bridging technique reduces costs in the chain-front permutation and interaction sectors, though the dominant savings still come from the separation of "where" and "what."

Significance and Claims
The paper claims that exploiting the repeated local structure of Hamiltonians allows for a fundamental reduction in the non-Clifford cost of block encodings.

Scalability: For structured Hamiltonians, the cost of Select grows linearly with system size $N$ regardless of the number of terms, provided the support size is fixed. This contrasts with flat-list approaches where cost grows with the product of supports and operator classes.
Geometry Dependence: The leading cost is determined solely by the connectivity (geometry) of the Hamiltonian, not the number or values of coupling coefficients. This implies that power-law couplings cost the same as uniform ones in this framework.
Modesty: The authors note that for the specific models studied, the bridging technique provides savings primarily in subleading terms, while the dominant gain comes from the separation of permutation and action. They acknowledge that for supports of three or more sites, the minimum CSWAP count is not fully resolved for all geometries, and the optimal balance between minimum permutation size and nonlinear control costs remains an open question.

The work suggests that future block encodings should be designed around the geometry and repeated local structure of the Hamiltonian rather than a flat enumeration of Pauli terms.

Technical Summary: Efficient Block Encoding of Structured Hamiltonians by Separating Where and What

More like this