CANOE: Classically Assisted Non-Orthogonal Eigensolver

1. Problem Statement

In the early fault-tolerant regime of quantum computing, hardware resources (qubit count, coherence time, gate fidelity) are limited. While hybrid quantum-classical algorithms like the Variational Quantum Eigensolver (VQE) and Non-Orthogonal Variational Quantum Eigensolver (NOVQE) offer a path forward, they face specific bottlenecks:

• Expressivity vs. Cost: Purely quantum approaches (e.g., Krylov subspace methods) require many quantum states to reach chemical accuracy, which is resource-intensive. Purely classical approaches (e.g., Selected Configuration Interaction) require an exponentially large number of determinants to capture strong correlations.
• Overlap Estimation: Hybrid methods require calculating overlap and Hamiltonian matrix elements between quantum states and classical basis states. Naive approaches like full state tomography scale exponentially ($O(4^n)$), while existing efficient methods like classical shadow tomography still suffer from exponential scaling with system size for specific operators or require massive sampling.
• Numerical Instability: Combining a large number of classical determinants with a small set of quantum states often creates a highly non-orthogonal basis with near-linear dependencies. This leads to an ill-conditioned overlap matrix ($S$), causing numerical instability in generalized eigenvalue solvers (e.g., LOBPCG) and amplifying sampling noise.

2. Methodology: The CANOE Framework

The authors propose CANOE (Classically Assisted Non-Orthogonal Eigensolver), a hybrid framework that distributes the construction of the variational basis between classical and quantum hardware.

A. Hybrid Ansatz Construction

The trial wavefunction is defined as a linear combination of two distinct sectors:
$$|\psi\rangle = \sum_{i=1}^{N_c} c_i |\phi^c_i\rangle + \sum_{j=1}^{N_q} c_j |\phi^q_j\rangle$$

• Classical Sector ($N_c$): A large pool ($10^4 - 10^6$) of classical basis states, specifically Slater determinants selected via Selected Heat-Bath Configuration Interaction (SHCI). These are computationally cheap to generate and manipulate.
• Quantum Sector ($N_q$): A small set ($10 - 100$) of quantum-prepared states. In this work, these are Krylov states generated by time-evolving a Hartree-Fock reference state: $|\phi^q_j\rangle = e^{-iH t_j} |HF\rangle$. These states capture complex correlations difficult to represent classically.

B. Overlap Estimation: Histogram-Based Protocol

To solve the generalized eigenvalue problem $H\mathbf{c} = \lambda S\mathbf{c}$, the overlap matrix $S$ must be evaluated. The matrix is partitioned into three blocks:

1. $S_{cc}$ (Classical-Classical): Identity matrix (computed classically).
2. $S_{qq}$ (Quantum-Quantum): Measured via Hadamard tests on quantum hardware.
3. $S_{cq}$ (Classical-Quantum): The bottleneck.

Key Innovation: The authors introduce a histogram-based overlap estimation method to efficiently compute $S_{cq}$ without full tomography.

• Mechanism: Instead of measuring individual overlaps, the method prepares interference states between a quantum state $|\phi^q_j\rangle$ and a batch of classical states $|\chi\rangle = \frac{1}{\sqrt{m}}\sum |s\rangle$.
• Measurement: Ancilla-assisted circuits measure joint histograms in the computational (Z) basis.
• Estimator: An unbiased estimator for the complex overlap amplitude $\langle s | \phi^q_j \rangle$ is derived from the difference between interference histograms and reference histograms.
• Hamiltonian Elements: Using the property that Pauli strings map computational basis states to other basis states, Hamiltonian matrix elements are reconstructed classically from these overlap estimates, avoiding additional quantum measurements.
• Scaling: This method scales linearly with the number of qubits (via batching) rather than exponentially, significantly reducing sampling overhead compared to classical shadows for Z-basis projections.

C. Stabilization: Schur-Complement Formulation

To address the ill-conditioning caused by linear dependencies in the hybrid basis:

• The overlap matrix $S$ is block-decomposed.
• The authors utilize the Schur complement of the quantum sector ($S_{schur} = M - U^\dagger U$).
• Strategies:
  1. Deflation: Eigenvectors of $S_{schur}$ with eigenvalues below a threshold are discarded, reducing the subspace dimension.
  2. Pseudo-Inverse: A regularized pseudo-inverse is used to construct a preconditioner for the LOBPCG solver.
• This approach avoids direct inversion of the full ill-conditioned matrix, stabilizing the eigenvalue computation while preserving physical content.

3. Key Results

The authors validated CANOE through numerical simulations on a strongly correlated 76-qubit Chromium atom system (38 spatial orbitals, 14 electrons) and a benchmark set of smaller molecules ($H_4, H_2O, NH_3, HCN, CO_2, COCl_2$).

• Expressivity & Complementarity:
  • Purely quantum Krylov subspaces reached chemical accuracy with $\approx 8$ states.
  • Purely classical SHCI required $\approx 10^5$ determinants.
  • Hybrid Synergy: Adding just one quantum state allowed for the removal of $\approx 3,000$ classical determinants while maintaining the same energy accuracy. The quantum states provided "directions" orthogonal to the classical space, while classical states provided a dense background.
• Sampling Efficiency:
  • The histogram-based method outperformed classical shadow tomography in terms of shot complexity for the specific task of Z-basis projections.
  • Numerical benchmarks showed that chemical accuracy could be approached at moderate sampling costs ($10^7$ shots per molecule for smaller systems).
• Stability Analysis:
  • The study revealed that in the presence of sampling noise, aggressive deflation (removing weakly independent directions) often yields better results than trying to resolve them, as noise can destroy the variational structure.
  • The Schur-complement stabilization successfully mitigated numerical instability, allowing the solver to converge even with near-singular overlap matrices.

4. Significance and Impact

• Practical Early-Fault-Tolerant Strategy: CANOE offers a concrete roadmap for achieving quantum advantage in the near term by leveraging the "cheap" classical resources for the bulk of the basis set while using scarce quantum resources only for the most expressive, hard-to-classify directions.
• Resource Optimization: By shifting the computational burden of overlap estimation to classical post-processing (via histograms), CANOE drastically reduces the quantum sampling cost compared to full tomography or standard shadow methods.
• Robustness: The integration of Schur-complement stabilization provides a necessary solution to the numerical instability inherent in large-scale non-orthogonal bases, a critical hurdle for practical implementation.
• Scalability: Extrapolations suggest that for a 100-qubit system, CANOE could reach chemical accuracy with a total sampling cost of $\sim 10^{10}$ shots. While high, this is orders of magnitude lower than estimates for VQE ($\sim 10^{13}$) and potentially more feasible than fully coherent fault-tolerant algorithms (like QPE) for specific early-fault-tolerant hardware constraints.

In summary, CANOE represents a sophisticated hybrid architecture that balances the expressive power of quantum dynamics with the scalability of classical configuration interaction, supported by novel measurement protocols and numerical stabilization techniques.