Learning the closest Slater determinant

Technical Summary: Learning the Closest Slater Determinant

Problem Definition
The paper addresses the fundamental task of finding the Slater determinant that maximizes fidelity with an arbitrary $n$-fermion quantum state $\rho$ (pure or mixed) defined on $m$ fermionic modes. Formally, given a state $\rho$ and an error tolerance $\epsilon > 0$, the goal is to find a Slater determinant $|S\rangle \in \mathcal{S}$ such that:
$$\langle S|\rho|S\rangle \geq \text{OPT} - \epsilon$$
where $\text{OPT} = \max_{|S\rangle \in \mathcal{S}} \langle S|\rho|S\rangle$.

This problem is distinct from the Hartree-Fock approximation, which minimizes energy expectation values over a Hamiltonian; here, the target state $\rho$ is fixed, and the objective is purely geometric (maximizing overlap). The problem is inherently non-convex because the manifold of Slater determinants is nonlinear, posing challenges for heuristic optimization methods like gradient ascent which may get trapped in local optima.

Methodology
The authors propose both classical and quantum algorithms to solve this problem, relying on a three-stage procedure:

1. Estimation of the 1-RDM: The first step involves estimating the single-particle reduced density matrix (1-RDM), $\gamma_{ij} = \text{Tr}(c^\dagger_j c_i \rho)$.
   • In the classical setting, the algorithm assumes efficient query access to the amplitudes of a succinct classical description (e.g., tensor networks or neural quantum states) and efficient sampling of few-body observables.
   • In the quantum setting, the algorithm assumes access to copies of the state $\rho$ and uses quantum tomography (specifically fermionic classical shadows) to estimate $\gamma$.
2. Active Space Truncation: The estimated 1-RDM $\hat{\gamma}$ is diagonalized to obtain natural orbitals and their occupations. The algorithm truncates the Hilbert space to an "active space" $\mathcal{A}$ comprising orbitals with occupations above a threshold ($\sim \epsilon/n$). Theoretical proofs show that restricting the search to this subspace incurs at most an additive error of $\epsilon/2$ (or similar) in the fidelity, provided the estimation error of the 1-RDM is sufficiently small. The dimension of this active space is bounded by $O(n^2/\epsilon)$.
3. Discretized Search:
   • Classical Algorithm: The algorithm constructs an $\epsilon$-covering net over the manifold of Slater determinants built from the active space. It explicitly enumerates this net, evaluates the fidelity for each point, and returns the maximum.
   • Quantum Algorithm: The algorithm employs a Quantum Threshold Search (QTS) routine (based on Badescu and O'Donnell) applied to the projectors of the covering net. This allows finding the best Slater determinant with high probability using a number of copies of $\rho$ that scales polylogarithmically with the size of the net, rather than linearly.

Key Results and Complexity
The paper establishes upper bounds (algorithms) and matching lower bounds (hardness) for the problem:

• Classical Runtime: The classical algorithm runs in time $m \cdot \text{poly}(n, 1/\epsilon)$. Specifically, the runtime is exponential in $n$ and $1/\epsilon$ (roughly $\exp(O(\frac{n^3}{\epsilon} \log \frac{n}{\epsilon}))$) but polynomial in the number of modes $m$.
• Quantum Sample Complexity: The quantum algorithm requires $\text{poly}(m, n, 1/\epsilon)$ copies of $\rho$. However, the runtime remains exponential in $n$ and $1/\epsilon$.
• Hardness Lower Bounds:
  • In $n$ (Particle Number): Assuming the Exponential Time Hypothesis (ETH) and the hardness of the $n$-Multicolored Clique problem, no classical algorithm can solve this problem in time $f(n)m^{o(n)}$. This implies the exponential dependence on $n$ is essentially unavoidable for classical algorithms.
  • In $1/\epsilon$ (Precision): Assuming $\text{NP} \not\subseteq \text{BPP}$ (classical) or $\text{NP} \not\subseteq \text{BQP}$ (quantum), no algorithm can solve the problem in time polynomial in $1/\epsilon$. This is proven by reducing the problem to the quantum separability problem, which is known to be NP-hard when the state is close to the boundary of separable states.

Optimization Landscape and the $2/3$ Threshold
A significant theoretical contribution is the characterization of the optimization landscape. The authors prove a sharp transition at a fidelity of $F = 2/3$:

• Above $F = 2/3$: If a Slater determinant $|S\rangle$ is a stationary point of the fidelity function (satisfying a condition analogous to the Brillouin condition in Hartree-Fock theory) and has fidelity $F > 2/3$, it is guaranteed to be the unique global maximum. In this regime, the landscape is "benign" with no spurious stationary points.
• Below $F = 2/3$: The landscape can contain spurious stationary points (local optima) that are not globally optimal. The authors construct "adversarial" states where stationary points exist arbitrarily close to $F=2/3$ from below, proving that the $2/3$ threshold is sharp and cannot be improved for a general, state-independent guarantee.

Numerical Validation
The authors apply their classical algorithm to the Fermi-Hubbard model:

• They extract the closest Slater determinant from ground states obtained via exact diagonalization and Neural Quantum States (NQS).
• They demonstrate that simple gradient ascent, when initialized randomly, often fails to reach the global optimum as the system size increases, frequently getting stuck in local optima with fidelities well below the global maximum.
• Numerical experiments on various state ensembles (random, weakly correlated, physical) confirm that spurious stationary points generally lie below the $2/3$ threshold, with the $2/3$ bound being tight only for specifically constructed adversarial states.

Significance
The paper provides the first algorithms with rigorous performance guarantees for learning the closest Slater determinant to an arbitrary fermionic state. Its significance lies in:

1. Algorithmic Guarantees: Offering provable solutions for agnostic tomography of fermionic states, a task previously reliant on heuristics without convergence guarantees.
2. Complexity Characterization: Establishing that the problem is computationally hard in both particle number and precision, setting limits on what can be efficiently achieved classically or quantumly.
3. Geometric Insight: Identifying the $2/3$ fidelity threshold as a critical transition point where local optimization becomes globally reliable, providing a practical criterion for validating optimization results in quantum chemistry and condensed matter physics.
4. Practical Utility: Demonstrating the extraction of natural orbital bases and particle-hole excitation structures from complex many-body states (like those represented by NQS), aiding in the interpretability of quantum simulations.