Resource-efficient Quantum Algorithms for Selected Hamiltonian Subspace Diagonalization

This paper introduces a resource-efficient quantum selected configuration interaction (QSCI) algorithm in the configuration interaction matrix (CIM) framework with optimal qubit scaling and novel error mitigation, and further proposes a hybrid quantum-classical QSHCI variant that achieves performance comparable to classical heat-bath CI while significantly reducing quantum resource requirements.

The Gist

The Big Picture: Finding a Needle in a Haystack

Imagine you are trying to find the absolute best way to arrange a massive jigsaw puzzle (the molecule). In the world of quantum chemistry, this "puzzle" is the Hamiltonian, a giant mathematical map of how all the electrons in a molecule interact.

The problem? For big molecules, this puzzle has more pieces than there are atoms in the universe. Trying to solve the whole thing at once is impossible for even the fastest supercomputers.

The Solution: Instead of trying to solve the whole puzzle, scientists use a strategy called QSCI (Quantum Selected Configuration Interaction). Think of it like hiring a smart assistant (the quantum computer) to scan the puzzle and say, "Hey, these 100 pieces here look like they belong in the final picture. Ignore the rest." Then, a regular computer solves the small puzzle made of just those 100 pieces.

The Problem with Old Assistants

Previous versions of this "assistant" were a bit clumsy. They spoke a language (Second Quantization) that required a huge number of "bits" (qubits) to do the job. It was like trying to carry a library of books just to read one page. They were inefficient and wasted resources.

The New Approach: The "CIM" Framework

The authors of this paper introduced a new, super-efficient assistant called CIM-QSCI.

1. The Library Analogy (Qubit Efficiency)
Imagine you have a library with 1 million books.

• Old Way: You need 1 million different shelves (qubits) to store them, even if you only want to read one book.
• New Way (CIM): You realize you can organize the books using a clever index system. Now, you only need about 20 shelves to find any book in that million-book library.
• The Result: The new algorithm uses logarithmic scaling. Instead of needing a shelf for every single electron configuration, it needs a number of shelves equal to the number of digits in the total count. This saves a massive amount of "space" on the quantum computer.

2. The "Stochastic" Tour Guide (Approximate Evolution)
To find the right puzzle pieces, the quantum computer has to "evolve" a starting guess into a better guess.

• Old Way: The computer takes a very precise, step-by-step tour of the molecule. It's like walking every single street in a city to find a coffee shop. It's accurate but takes forever and gets tired (noisy) quickly.
• New Way (qDRIFT): The authors use a "Stochastic" (randomized) approach. Imagine a tour guide who says, "Let's take a taxi to the general area, then walk randomly for a bit." It's not a perfect path, but it gets you to the right neighborhood much faster. By doing this "random walk" many times and combining the results, they get the answer without needing a perfect, exhausting path.

3. The "Error-Catching Net" (Bit-Flip Mitigation)
Quantum computers are noisy. Sometimes, a "0" accidentally flips to a "1" (a bit-flip error).

• The Metaphor: Imagine you are sending a secret code using a specific pattern of lights (e.g., always an even number of lights on). If a light flickers and breaks the pattern, you know immediately, "Hey, that's a mistake!"
• The Fix: The authors added one extra "check" qubit. If the pattern breaks (an odd number of lights), they throw that result away. If it's close but broken, they use math to guess which original pattern it was supposed to be and fix it. This cleans up the data without needing expensive error-correction hardware.

The "Heat-Bath" Upgrade (QSHCI)

Even with the new efficient assistant, the results were good, but not quite as good as the best classical methods (like HCI).

• The Analogy: Imagine the assistant is picking puzzle pieces by rolling dice. Sometimes the dice roll a piece that looks okay but isn't the best fit.
• The Fix (QSHCI): They upgraded the assistant to use a "Heat-Bath" strategy. Instead of just rolling dice, the assistant now looks at the pieces it already has and asks, "Which missing piece connects best to what I have?" It's a smarter, more targeted search.
• The Result: This new QSHCI method performed just as well as the best classical supercomputer methods, but it did it using the quantum computer's unique ability to sample possibilities.

The Results: What Did They Find?

They tested this on two molecules: Nitrogen (N2) and Naphthalene (a component of mothballs).

1. Efficiency: They achieved the same accuracy as other quantum methods but used significantly fewer resources (fewer qubits and simpler circuits).
2. Accuracy: Their new "Heat-Bath" version (QSHCI) matched the performance of the best classical methods.
3. The Catch: The "preparation" phase (getting the puzzle ready before the quantum computer starts) is still a bit heavy on classical computers. It's like having a very fast race car, but it takes a long time to pack the car into the trailer. They hope to fix this in the future.

Summary

This paper is about building a leaner, smarter quantum assistant for chemistry.

• It uses a better filing system (CIM) to save space.
• It uses a randomized tour (qDRIFT) to save time.
• It uses a pattern-checking net to catch errors.
• It uses a smarter search strategy (Heat-Bath) to get the best results.

It proves that we don't need massive, perfect quantum computers to solve complex chemistry problems; we just need clever algorithms that work well with the imperfect, noisy machines we have today.

Technical Summary

1. Problem Statement

Quantum chemistry simulations, particularly for strongly correlated systems, face a classical computational bottleneck due to the exponential growth of the Hilbert space. While Variational Quantum Eigensolvers (VQE) are popular for Noisy Intermediate-Scale Quantum (NISQ) devices, they suffer from issues like barren plateaus, lack of variational bounds, and high sensitivity to noise.

Alternative stochastic approaches, such as Quantum Selected Configuration Interaction (QSCI) and Sample-based Quantum Diagonalization (SQD), have emerged. However, existing QSCI/SQD algorithms are formulated in second quantization (Fock space). This approach requires a number of qubits equal to the number of orbitals, leading to inefficient resource usage. Furthermore, these methods often struggle to match the accuracy of classical Heat-bath Configuration Interaction (HCI) while maintaining low quantum resource overhead.

2. Methodology

The authors propose a new framework called CIM-QSCI (Configuration Interaction Matrix - Quantum Selected CI), which operates in first quantization, followed by an enhanced variant called CIM-QSHCI (Quantum Selected Heat-bath CI).

A. The CIM Framework (First Quantization)

Instead of mapping the problem to Fock space (orbitals), the algorithm uses the CI-Matrix (CIM), where the basis states are Configuration State Functions (CSFs).

• Qubit Efficiency: The number of qubits required is exactly $\lceil \log_2(N_{CSF}) \rceil + 1$, where $N_{CSF}$ is the number of CSFs. This is significantly more efficient than second-quantized approaches which scale linearly with the number of orbitals.
• Memory Efficiency: The CIM is constructed in single-precision (32-bit), halving the memory footprint compared to standard double-precision classical methods, without sacrificing final accuracy (as the final subspace diagonalization is done in double precision).
• Decomposition: The CIM is decomposed into a weighted sum of Pauli strings using the Fast Walsh-Hadamard Transform (FWHT). This adds a preprocessing cost of $O(N^2 \log N)$ but enables the optimal qubit scaling.

B. Approximate Evolution (qDRIFT)

To evolve the initial state (Hartree-Fock determinant) toward the ground state, the authors utilize a stochastic approximate Trotterization based on the qDRIFT algorithm.

• Truncation: The Hamiltonian terms are probabilistically truncated based on their coefficients ($\alpha_{r,s}$).
• Repetition: To maintain accuracy despite truncation, the evolution is repeated $r$ times. The total number of terms sampled across repetitions satisfies $r \times n_a \approx 2\lambda^2 t^2 / \epsilon$, ensuring the full Hilbert space is explored while keeping individual circuit depths shallow.

C. Error Mitigation: Single-Bit Flip

A novel single-bit flip error mitigation scheme is introduced for the CIM framework.

• Mechanism: An extra qubit is added to ensure the parity (sum of bits) of the physical CSF bitstrings is always even (or odd).
• Post-selection: Any measurement resulting in the wrong parity is identified as a bit-flip error and discarded.
• Recovery: Non-physical bitstrings (those with wrong parity) that are Hamming distance 1 from a physical state are corrected and mapped back to the most likely physical state, recovering data that would otherwise be discarded.

D. Quantum Selected Heat-bath CI (QSHCI)

Recognizing that standard CIM-QSCI did not match classical HCI performance, the authors introduced QSHCI.

• Hybrid Approach: It replaces the deterministic heat-bath sampling of classical HCI with quantum sampling from the QSCI process.
• Acceptance Criterion: A configuration $k$ is added to the subspace if $|H_{ki}c_i| > \sqrt{P_k}v$, where $P_k$ is the probability of sampling configuration $k$ on the quantum computer, and $v$ is a user-defined variance factor. This allows the algorithm to adaptively select the most relevant configurations based on quantum measurements.

3. Key Contributions

1. First CIM-based QSCI: Introduction of the first QSCI algorithm using the CI-Matrix (first quantization), achieving optimal qubit scaling of $\lceil \log_2(N_{CSF}) \rceil$.
2. Resource Efficiency: Demonstrated that CIM-QSCI achieves accuracy comparable to or better than second-quantized SQD methods (like LUCJ-SQD and SqDRIFT) using significantly fewer qubits and gate counts.
3. Novel Error Mitigation: Developed a single-bit flip mitigation scheme tailored for first quantization that recovers non-physical bitstrings, improving data efficiency.
4. QSHCI Algorithm: Proposed an augmented algorithm that integrates quantum sampling into the heat-bath CI workflow, achieving performance comparable to classical HCI.
5. Hardware Validation: Successfully benchmarked the algorithms on quantum hardware (Rigetti Ankaa-3) and emulators for $N_2$ and naphthalene.

4. Results

The algorithms were tested on the $N_2$ bond stretch problem (a benchmark for strong correlation) and naphthalene (a polycyclic aromatic hydrocarbon).

• $N_2$ Simulation:
  • CIM-QSCI: Achieved similar accuracy to the exact diagonalization curve and outperformed LUCJ-SQD at large bond distances. On hardware, it matched the accuracy of SqDRIFT but with fewer resources.
  • CIM-QSHCI: Produced results comparable to classical HCI. While HCI still showed slightly lower error (due to more efficient determinant selection), QSHCI achieved similar accuracy with a significantly smaller subspace Hamiltonian size compared to standard QSCI.
• Naphthalene Simulation:
  • CIM-QSCI: Achieved chemical accuracy (0.0016 Hartree) with a subspace size of ~40-70%. It required 5 times fewer circuits than SqDRIFT to achieve similar accuracy because it strictly sampled only symmetry-adapted ($A_g$) CSFs, avoiding the redundancy of second-quantized methods.
  • CIM-QSHCI: Outperformed all other QSCI variants and classical CCSD, approaching the accuracy of classical HCI.
• Resource Comparison:
  • Qubits: CIM methods required 14–18 qubits, whereas second-quantized methods required 20+ qubits for the same active spaces.
  • Gate Depth: The use of approximate Trotterization and circuit compression (Approximation Degree 0.5) allowed deep circuits to run on current hardware with reduced error accumulation.

5. Significance and Outlook

• NISQ Suitability: The CIM-QS(H)CI algorithms are uniquely suited for NISQ devices due to their logarithmic qubit scaling and shallow circuit depths achieved via stochastic evolution.
• Memory Advantage: By constructing the Hamiltonian in single-precision, the method allows for the simulation of larger systems on classical hardware that would otherwise be memory-intractable.
• Future Directions: The primary bottleneck identified is the $O(N^2 \log N)$ preprocessing cost for constructing the CIM and Pauli decomposition. Future work aims to optimize this via efficient CIM access models. Additionally, refining the QSHCI selection strategy to match the efficiency of classical HCI remains a key goal.

In conclusion, this work demonstrates that shifting from second to first quantization (CIM) combined with stochastic evolution and hybrid sampling strategies offers a viable, resource-efficient path toward accurate quantum chemistry simulations on near-term hardware.