Optimised Fermion-Qubit Encodings for Quantum Simulation with Reduced Transpiled Circuit Depth

This paper introduces a deterministic optimization method for ternary tree fermion-qubit encodings that reduces Pauli-weight and transpiled circuit depth by approximately 26.5% for water molecule simulations without requiring ancillae or altering the underlying tree structure.

The Gist

Imagine you are trying to simulate a complex chemical reaction, like how water molecules interact, using a quantum computer. To do this, you have to translate the rules of chemistry (which involve "fermions," a type of subatomic particle) into the language of the quantum computer (which uses "qubits").

This translation process is called an encoding. Think of it like trying to fit a large, awkward piece of furniture (the chemistry problem) into a moving truck (the quantum computer).

The Problem: The "Moving Truck" is Too Small and Clunky

Currently, the most common way to do this translation is like using a standard, rigid packing method (called the Jordan-Wigner encoding). It works, but it's often inefficient.

• The Issue: When you pack the furniture this way, you end up with a lot of empty space, or you have to move the same item back and forth many times just to get it to the right spot. In quantum computing terms, this means the computer has to perform too many "gates" (operations) to solve the problem.
• The Consequence: Because current quantum computers are small and prone to errors, these extra, unnecessary steps make the simulation too slow or too error-prone to be useful. It's like trying to drive a heavy truck with the parking brake on.

The Solution: A Smarter Packing Strategy

The authors of this paper developed a new, smarter way to pack the furniture. They call their method TOPP-HATT.

Here is how it works, using a simple analogy:

1. The Tree Structure: Imagine the quantum computer's connections as a family tree. Some encodings force the furniture into a specific, rigid tree shape. The authors say, "Let's keep that tree shape exactly as it is, because changing the tree's structure is too hard and might break the computer's layout."
2. The Shuffle: Instead of changing the tree, they simply shuffle the labels on the branches. Imagine you have a set of suitcases (the chemical parts) and a set of shelves (the quantum bits). The old method just puts Suitcase A on Shelf 1, Suitcase B on Shelf 2, and so on.
3. The Optimization: The new method looks at the specific chemical problem and asks: "If I put Suitcase A on Shelf 3 and Suitcase B on Shelf 1, will the computer have to walk back and forth less?" They use a deterministic (step-by-step, guaranteed) algorithm to find the best arrangement of labels without ever changing the underlying tree structure.

The Results: A Faster, Smoother Ride

The paper tested this method on water molecules (a standard test case) and compared it to the old ways of packing.

• The "Before" and "After": They measured the "circuit depth," which is essentially the length of the journey the quantum computer has to take.
• The Improvement: By using their new shuffling method, they reduced the length of the journey by about 25% on average.
  • For unoptimized circuits, the reduction was 24.7%.
  • For circuits already optimized for specific hardware, the reduction was 26.5%.

Why This Matters (According to the Paper)

The authors emphasize that this is a deterministic method. Unlike previous methods that used "trial and error" (like flipping a coin to see if a new arrangement is better), this method follows a strict set of rules to guarantee a good result every time.

They also note that this method works well with encodings designed specifically for the physical layout of quantum chips (like the "Bonsai" algorithm), ensuring that the "furniture" stays on connected "shelves" so the computer doesn't have to waste time moving things around.

In summary: The paper presents a new, reliable way to rearrange how chemical problems are mapped onto quantum computers. By simply shuffling the labels on the existing connections rather than rebuilding the connections themselves, they can significantly shorten the time and effort required to run simulations, making the most of the limited quantum computers we have today.

Technical Summary

1. Problem Statement

Simulating fermionic systems (e.g., molecules) on gate-based quantum computers requires mapping fermionic operators to qubit operators, a process known as fermion-qubit encoding. The choice of encoding significantly impacts the efficiency of quantum simulations, specifically regarding:

• Circuit Depth: The number of quantum gates required.
• Pauli-weight: The number of non-identity Pauli operators in a string, which correlates with gate errors and measurement overhead.
• Device Connectivity: The physical layout of qubits on a quantum processor (QPU).

Existing approaches face a trade-off:

1. Hamiltonian-Optimized Encodings: Construct encodings based on the specific Hamiltonian to minimize coefficients but often result in tree structures incompatible with the QPU, requiring expensive SWAP gates to move information between non-adjacent qubits.
2. Device-Optimized Encodings: Construct encodings based on the QPU connectivity graph (e.g., using the Bonsai algorithm) but fail to exploit the specific structure of the Hamiltonian, leading to suboptimal gate counts.
3. Stochastic Optimization: Previous attempts to combine these goals used stochastic methods (e.g., simulated annealing), which are not guaranteed to find global minima and are sensitive to initial conditions.

The Core Challenge: There is a need for a deterministic method that optimizes the mapping of fermionic modes to qubits within a fixed tree structure (specifically Ternary Trees) to reduce circuit depth and Pauli-weight without altering the underlying graph topology or requiring ancillary qubits.

2. Methodology: TOPP-HATT

The authors propose TOPP-HATT (Topology-Preserving Hamiltonian Adaptive Ternary Tree), a deterministic algorithm that optimizes the enumeration of Majorana operators within a pre-defined Ternary Tree (TT) structure.

Key Concepts

• Majorana-String Encodings: Fermionic operators are decomposed into Majorana operators ($\gamma$), which are then mapped to Pauli strings.
• Ternary Trees (TTs): A graph structure where nodes represent qubits and edges represent Pauli operators ($X, Y, Z$). Leaves represent Majorana operators.
• Optimization Goal: Minimize the Pauli-weight ($W_P$) and the coefficient-scaled Pauli-weight ($W_{CP}$), which is critical for stochastic algorithms like qDRIFT.

The Algorithm (TOPP-HATT)

The method iteratively assigns fermionic modes to leaves in the tree while preserving the tree's topology and vacuum state properties:

1. Setup: A "naive" tree is constructed where fermionic mode indices match qubit indices.
2. Restrictions: To ensure validity, the algorithm enforces:
   • Operator Independence: Ensures Pauli strings satisfy anti-commutation relations.
   • Tree Structure Preservation: Nodes and their children remain fixed; only leaf assignments change.
   • Vacuum Preservation: Ensures the fermionic vacuum state maps to the qubit $|0\rangle^{\otimes N}$ state. This is achieved by strictly pairing leaves (e.g., if a leaf is assigned $\gamma_{2k}$, its pair must be $\gamma_{2k+1}$).
3. Iterative Loop:
   • The algorithm identifies "active nodes" (nodes at the maximum distance from the root that have no unassigned children).
   • For each active node, it calculates the Cartesian product of all possible valid leaf assignments for its edges.
   • It evaluates the Pauli-weight of the resulting Hamiltonian terms for each combination.
   • It selects the assignment that minimizes the weight, updates the tree, and reduces the Hamiltonian (simplifying terms where indices become identical).
4. Output: A re-ordered enumeration of Majorana operators that minimizes the cost function for the specific Hamiltonian while maintaining the original tree topology.

3. Key Contributions

• Deterministic Optimization: Unlike previous stochastic methods, TOPP-HATT guarantees a consistent, reproducible result without the risk of getting stuck in local minima.
• Topology Preservation: The method optimizes within a fixed tree structure. This allows it to be applied to encodings derived from specific device connectivity graphs (e.g., heavy-hex lattices) without breaking the hardware constraints.
• Broad Applicability: The method works for standard encodings (Jordan-Wigner, Bravyi-Kitaev, Parity, JKMN) and Hamiltonian-adaptive encodings (Huffman, HATT).
• No Ancillae or Overhead: The optimization reduces circuit depth and Pauli-weight without adding extra qubits or SWAP gates.

4. Results

The method was tested on the water molecule ($H_2O$) in the STO-3G basis (14 modes) and various other molecules in STO-3G and 6-31G bases.

• Pauli-Weight Reduction:
  • For standard encodings, TOPP-HATT consistently reduced both the average Pauli-weight and the coefficient-scaled Pauli-weight compared to naive enumerations and simulated annealing.
  • The method was most effective for linear encodings (Jordan-Wigner, Parity) but also showed improvements for binary (Bravyi-Kitaev) and ternary (JKMN) trees.
• qDRIFT Circuit Depth:
  • The authors applied TOPP-HATT as a pre-processing step for the qDRIFT algorithm (a stochastic time-evolution method).
  • Untranspiled Circuits: Average reduction in circuit depth of 24.7%.
  • Transpiled Circuits: After compiling for a 20-qubit IQM Garnet device topology, the average reduction was 26.5%.
  • Specific improvements for the Jordan-Wigner encoding were ~20% (untranspiled) and ~19% (transpiled).
• Computational Cost:
  • The algorithm is computationally efficient. Runtime scales approximately as $|H_\gamma|^{1.47}$ (where $|H_\gamma|$ is the number of Hamiltonian terms).
  • The inner loop is highly parallelizable.

5. Significance

This work addresses a critical bottleneck in near-term quantum simulation: the high circuit depth required for fermionic simulations. By providing a deterministic, low-cost, and topology-preserving optimization method, TOPP-HATT enables:

• Co-design: It bridges the gap between Hamiltonian-specific optimization and hardware constraints, allowing researchers to use device-native encodings without sacrificing simulation accuracy or efficiency.
• Error Reduction: Lower Pauli-weight directly translates to fewer gates, reducing the accumulation of gate errors and readout errors, which is vital for Noisy Intermediate-Scale Quantum (NISQ) devices.
• Scalability: The method's favorable scaling and deterministic nature make it suitable for pre-processing larger molecular systems as quantum hardware improves.

In summary, TOPP-HATT offers a practical, immediate improvement for quantum chemistry simulations by optimizing how fermionic systems are mapped to qubits, resulting in significantly shallower and more robust quantum circuits.