Polynomial-Time Solution to the Fermion Sign Problem via Ramanujan's Mock Theta Functions.

complexity class. Empirical validation on high-density Goldstein-Mayer lattices confirms this shift; we report the successful resolution of a 10,000 * 10,000 basis matrix (Range [-5000, 5000]) in under 28.5988 seconds, maintaining a precision floor of 1.4 * 10^{-8}. Our ``Mock Modular'' framework reveals that the sign problem is not an intrinsic property of matter, but an artifact of holomorphic incompleteness, offering a transformative pathway for room-temperature superconductivity, post-quantum cryptography, and early-stage clinical diagnostics.

DOI: 10.5281/zenodo.19057804

Related papers

Ramanujan's Mock Theta Functions and the Fermion Sign Problem: A Combinatorial Resolution

PRAKASH VAITHYANATHAN

The Fermion Sign Problem is the fundamental computational barrier to simulatingstrongly correlated quantum matter, traditionally categorized as an NP-hard challenge thatscales exponentially with system size. Here, we present a polynomial-time resolution tothis decades-old bottleneck by establishing a rigorous isomorphism between fermionic con-figuration space and the combinatorial theory of integer partitions. We prove that thefermionic exchange sign is topologically protected by the parity of Dyson’s Rank, whichmaps the oscillating partition function directly onto Ramanujan’s third-order mock thetafunctions. By utilizing Zwegers’ Theorem to complete these functions via a non-holomorphicshadow—identified as the dissipative Goldstone modes of the condensate—we demonstratethat ground-state energies can be recovered in O(N^4) time. This ”Mock Modular” frame-work reveals that the sign problem is not an intrinsic property of fermionic matter, buta mathematical artifact of holomorphic incompleteness. Our results offer a transformativepathway for the rapid discovery of room-temperature superconductors, the development ofpost-quantum cryptographic protocols, and the design of ultra-sensitive quantum sensorsfor the early detection of neurodegenerative biomarkers in clinical diagnostics.The Fermion Sign Problem is the fundamental computational barrier to simulatingstrongly correlated quantum matter, traditionally categorized as an NP-hard challenge thatscales exponentially with system size. Here, we present a polynomial-time resolution tothis decades-old bottleneck by establishing a rigorous isomorphism between fermionic con-figuration space and the combinatorial theory of integer partitions. We prove that thefermionic exchange sign is topologically protected by the parity of Dyson’s Rank, whichmaps the oscillating partition function directly onto Ramanujan’s third-order mock thetafunctions. By utilizing Zwegers’ Theorem to complete these functions via a non-holomorphicshadow—identified as the dissipative Goldstone modes of the condensate—we demonstratethat ground-state energies can be recovered in O(N^4) time. This ”Mock Modular” frame-work reveals that the sign problem is not an intrinsic property of fermionic matter, buta mathematical artifact of holomorphic incompleteness. Our results offer a transformativepathway for the rapid discovery of room-temperature superconductors, the development ofpost-quantum cryptographic protocols, and the design of ultra-sensitive quantum sensorsfor the early detection of neurodegenerative biomarkers in clinical diagnostics.

Mar 16, 20260 citations

Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations

Matthias Troyer, U.‐J. Wiese

Quantum Monte Carlo simulations, while being efficient for bosons, suffer from the "negative sign problem" when applied to fermions--causing an exponential increase of the computing time with the number of particles. A polynomial time solution to the sign problem is highly desired since it would provide an unbiased and numerically exact method to simulate correlated quantum systems. Here we show that such a solution is almost certainly unattainable by proving that the sign problem is nondeterministic polynomial (NP) hard, implying that a generic solution of the sign problem would also solve all problems in the complexity class NP in polynomial time.Quantum Monte Carlo simulations, while being efficient for bosons, suffer from the "negative sign problem" when applied to fermions--causing an exponential increase of the computing time with the number of particles. A polynomial time solution to the sign problem is highly desired since it would provide an unbiased and numerically exact method to simulate correlated quantum systems. Here we show that such a solution is almost certainly unattainable by proving that the sign problem is nondeterministic polynomial (NP) hard, implying that a generic solution of the sign problem would also solve all problems in the complexity class NP in polynomial time.

arXiv:cond-mat/0408370Physical Review LettersMay 4, 20051,250 citations

Fermion sign bounds theory in quantum Monte Carlo simulation

Xu Zhang, Gaopei Pan, Xiao Yan Xu +1 more

Sign problems in fermion quantum Monte Carlo (QMC) simulation appears to be an extremely hard problem. Traditional lore passing around for years tells people that when there is a sign problem, the average sign in QMC simulation approaches zero exponentially fast with the space-time volume of the configurational space. We, however, analytically show this is not always the case and manage to find physical bounds for the average sign. Our understanding is based on a direct connection between the sign bounds and a well-defined partition function of the reference system and could distinguish when the bounds have the usual exponential scaling and when they are bestowed on an algebraic scaling at the low-temperature limit. We analytically explain such algebraic sign problems found in flat-band moir\'e lattice models at the low-temperature limit. At finite temperature, a domain-size argument based on sign bounds also explains the connection between sign behavior and finite-temperature phase transition. Sign bounds, as a well-defined observable, may have the ability to ease or even make use of the sign problem.Sign problems in fermion quantum Monte Carlo (QMC) simulation appears to be an extremely hard problem. Traditional lore passing around for years tells people that when there is a sign problem, the average sign in QMC simulation approaches zero exponentially fast with the space-time volume of the configurational space. We, however, analytically show this is not always the case and manage to find physical bounds for the average sign. Our understanding is based on a direct connection between the sign bounds and a well-defined partition function of the reference system and could distinguish when the bounds have the usual exponential scaling and when they are bestowed on an algebraic scaling at the low-temperature limit. We analytically explain such algebraic sign problems found in flat-band moir\'e lattice models at the low-temperature limit. At finite temperature, a domain-size argument based on sign bounds also explains the connection between sign behavior and finite-temperature phase transition. Sign bounds, as a well-defined observable, may have the ability to ease or even make use of the sign problem.

arXiv:2112.06139Physical review. B./Physical review. BJul 13, 202224 citations

Universality and critical exponents of the fermion sign problem

Rubem Mondaini, Sabyasachi Tarat, Richard T. Scalettar

Initial characterizations of the fermion sign problem focused on its evolution with spatial lattice size $L$ and inverse temperature $\ensuremath{\beta}$, emphasizing the implications of the exponential nature of the decay of the average sign $\ensuremath{\langle}\mathcal{S}\ensuremath{\rangle}$ for the complexity of its solution and associated limitations of quantum Monte Carlo studies of strongly correlated materials. Early interest was also on the evolution of $\ensuremath{\langle}\mathcal{S}\ensuremath{\rangle}$ with density $\ensuremath{\rho}$, either because commensurate filling is often associated with special symmetries for which the sign problem is absent, or because particular fillings are often primary targets, e.g., those densities, which maximize superconducting transition temperature (the top of the ``dome'' of cuprate systems). Here we describe an analysis of the sign problem, which demonstrates that the spin-resolved sign $\ensuremath{\langle}{\mathcal{S}}_{\ensuremath{\sigma}}\ensuremath{\rangle}$ already possesses signatures of universal behavior traditionally associated with order parameters, even in the absence of symmetry protection that makes $\ensuremath{\langle}\mathcal{S}\ensuremath{\rangle}=1$. When appropriately scaled, $\ensuremath{\langle}{\mathcal{S}}_{\ensuremath{\sigma}}\ensuremath{\rangle}$ exhibits universal crossings and data collapse. Moreover, we show these behaviors occur in the vicinity of quantum critical points of three well-understood models, exhibiting either second-order or Kosterlitz-Thouless phase transitions. Our results pave the way for using the average sign as a minimal correlator that can potentially describe quantum criticality in a variety of fermionic many-body problems.Initial characterizations of the fermion sign problem focused on its evolution with spatial lattice size $L$ and inverse temperature $\ensuremath{\beta}$, emphasizing the implications of the exponential nature of the decay of the average sign $\ensuremath{\langle}\mathcal{S}\ensuremath{\rangle}$ for the complexity of its solution and associated limitations of quantum Monte Carlo studies of strongly correlated materials. Early interest was also on the evolution of $\ensuremath{\langle}\mathcal{S}\ensuremath{\rangle}$ with density $\ensuremath{\rho}$, either because commensurate filling is often associated with special symmetries for which the sign problem is absent, or because particular fillings are often primary targets, e.g., those densities, which maximize superconducting transition temperature (the top of the ``dome'' of cuprate systems). Here we describe an analysis of the sign problem, which demonstrates that the spin-resolved sign $\ensuremath{\langle}{\mathcal{S}}_{\ensuremath{\sigma}}\ensuremath{\rangle}$ already possesses signatures of universal behavior traditionally associated with order parameters, even in the absence of symmetry protection that makes $\ensuremath{\langle}\mathcal{S}\ensuremath{\rangle}=1$. When appropriately scaled, $\ensuremath{\langle}{\mathcal{S}}_{\ensuremath{\sigma}}\ensuremath{\rangle}$ exhibits universal crossings and data collapse. Moreover, we show these behaviors occur in the vicinity of quantum critical points of three well-understood models, exhibiting either second-order or Kosterlitz-Thouless phase transitions. Our results pave the way for using the average sign as a minimal correlator that can potentially describe quantum criticality in a variety of fermionic many-body problems.

arXiv:2207.09026Physical review. B./Physical review. BJun 29, 202321 citations

Sign Problem in Quantum Monte Carlo Simulation

Gaopei Pan, Zi Yang Meng

Sign problem in quantum Monte Carlo (QMC) simulation appears to be an extremely hard yet interesting problem. In this article, we present a pedagogical overview on the origin of the sign problem in various quantum Monte Carlo simulation techniques, ranging from the world-line and stochastic series expansion Monte Carlo for boson and spin systems to the determinant and momentum-space quantum Monte Carlo for interacting fermions. We point out the basis dependency of the sign problem and summarize the progresses to cure, ease and even make use of the sign problem over the years, such as symmetry analysis of the underlying Hamiltonian, basis optimization in writting down the partition functions and many others. Moreover, we state that although traditional lore saying that in case of sign problem, the average sign in QMC simulation approaches zero exponentially fast with the space-time volume of the configurational space, there are recent breakthroughs showing this is not always the case and based on the properties of the partition function for finite size systems, one could distinguish when the average sign has the usual exponential scaling and when it is bestowed with an algebraic scaling at the low temperature limit. Fermionic QMC simulations with such algebraic sign problems have been successfully carried out for extended Hubbard-type and quantum Moiré lattice models.Sign problem in quantum Monte Carlo (QMC) simulation appears to be an extremely hard yet interesting problem. In this article, we present a pedagogical overview on the origin of the sign problem in various quantum Monte Carlo simulation techniques, ranging from the world-line and stochastic series expansion Monte Carlo for boson and spin systems to the determinant and momentum-space quantum Monte Carlo for interacting fermions. We point out the basis dependency of the sign problem and summarize the progresses to cure, ease and even make use of the sign problem over the years, such as symmetry analysis of the underlying Hamiltonian, basis optimization in writting down the partition functions and many others. Moreover, we state that although traditional lore saying that in case of sign problem, the average sign in QMC simulation approaches zero exponentially fast with the space-time volume of the configurational space, there are recent breakthroughs showing this is not always the case and based on the properties of the partition function for finite size systems, one could distinguish when the average sign has the usual exponential scaling and when it is bestowed with an algebraic scaling at the low temperature limit. Fermionic QMC simulations with such algebraic sign problems have been successfully carried out for extended Hubbard-type and quantum Moiré lattice models.

arXiv:2204.08777Apr 19, 20227 citations

Efficient Quantum Monte Carlo through Cluster Expansions

Jorge Sánchez-Segovia, Álvaro M. Alhambra

The sign problem remains a major obstacle to extending the success of Monte Carlo methods to generic quantum many-body systems. A powerful alternative relies on cluster expansions, which provide convergent representations of free energies and related quantities, with applications ranging from tensor network contractions to quantum dynamics and circuits. Within their convergence regime, these expansions often yield deterministic polynomial-time algorithms. However, such methods require exhaustive enumeration of connected clusters, leading to a computational overhead of $(N\varepsilon^{-1})^{\mathcal{O}(\logΔ)}$ , where $N$ is the system size, $\varepsilon$ the desired precision, and $Δ$ the interaction-graph degree. This becomes particularly severe in long-range systems, where $Δ\equiv N$ , resulting in quasi-polynomial runtimes. Here, we introduce a Markov chain algorithm that samples cluster expansions directly in the space of connected clusters, replacing deterministic enumeration by Monte Carlo sampling. Because sampling occurs in an abstract cluster space rather than a physical configuration space, the conventional exponential sign problem is absent within the convergence regime. For general polymer models, we establish an FPRAS with runtime $\tilde{\mathcal{O}}(N^4\varepsilon^{-3})$ . For quantum partition functions at temperatures $β\leqβ_{\mathrm{sampling}}\equiv\mathcal{O}(1)$ , this improves to $\tilde{\mathcal{O}}(N^{3+1/D}\varepsilon^{-3})$ , where $D$ is the lattice dimension. The framework directly applies to long-range quantum systems with interactions $\propto1/r^α$ , including $2$ -local models with $α>2D$ .The sign problem remains a major obstacle to extending the success of Monte Carlo methods to generic quantum many-body systems. A powerful alternative relies on cluster expansions, which provide convergent representations of free energies and related quantities, with applications ranging from tensor network contractions to quantum dynamics and circuits. Within their convergence regime, these expansions often yield deterministic polynomial-time algorithms. However, such methods require exhaustive enumeration of connected clusters, leading to a computational overhead of $(N\varepsilon^{-1})^{\mathcal{O}(\logΔ)}$, where $N$ is the system size, $\varepsilon$ the desired precision, and $Δ$ the interaction-graph degree. This becomes particularly severe in long-range systems, where $Δ\equiv N$, resulting in quasi-polynomial runtimes. Here, we introduce a Markov chain algorithm that samples cluster expansions directly in the space of connected clusters, replacing deterministic enumeration by Monte Carlo sampling. Because sampling occurs in an abstract cluster space rather than a physical configuration space, the conventional exponential sign problem is absent within the convergence regime. For general polymer models, we establish an FPRAS with runtime $\tilde{\mathcal{O}}(N^4\varepsilon^{-3})$. For quantum partition functions at temperatures $β\leqβ_{\mathrm{sampling}}\equiv\mathcal{O}(1)$, this improves to $\tilde{\mathcal{O}}(N^{3+1/D}\varepsilon^{-3})$, where $D$ is the lattice dimension. The framework directly applies to long-range quantum systems with interactions $\propto1/r^α$, including $2$-local models with $α>2D$.

quant-pharXiv:2610.03893Oct 6, 20260 citations

P

Initial characterizations of the fermion sign problem focused on its evolution with spatial lattice size

L

and inverse temperature $\ensuremath{\beta}$, emphasizing the implications of the exponential nature of the decay of the average sign $\ensuremath{\langle}\mathcal{S}\ensuremath{\rangle}$ for the complexity of its solution and associated limitations of quantum Monte Carlo studies of strongly correlated materials. Early interest was also on the evolution of $\ensuremath{\langle}\mathcal{S}\ensuremath{\rangle}$ with density $\ensuremath{\rho}$, either because commensurate filling is often associated with special symmetries for which the sign problem is absent, or because particular fillings are often primary targets, e.g., those densities, which maximize superconducting transition temperature (the top of the ``dome'' of cuprate systems). Here we describe an analysis of the sign problem, which demonstrates that the spin-resolved sign $\ensuremath{\langle}{\mathcal{S}}_{\ensuremath{\sigma}}\ensuremath{\rangle}$ already possesses signatures of universal behavior traditionally associated with order parameters, even in the absence of symmetry protection that makes $\ensuremath{\langle}\mathcal{S}\ensuremath{\rangle}=1$. When appropriately scaled, $\ensuremath{\langle}{\mathcal{S}}_{\ensuremath{\sigma}}\ensuremath{\rangle}$ exhibits universal crossings and data collapse. Moreover, we show these behaviors occur in the vicinity of quantum critical points of three well-understood models, exhibiting either second-order or Kosterlitz-Thouless phase transitions. Our results pave the way for using the average sign as a minimal correlator that can potentially describe quantum criticality in a variety of fermionic many-body problems.

(N\varepsilon^{-1})^{\mathcal{O}(\logΔ)}

, where

N

is the system size,

\varepsilon

the desired precision, and

Δ

the interaction-graph degree. This becomes particularly severe in long-range systems, where

Δ\equiv N

, resulting in quasi-polynomial runtimes. Here, we introduce a Markov chain algorithm that samples cluster expansions directly in the space of connected clusters, replacing deterministic enumeration by Monte Carlo sampling. Because sampling occurs in an abstract cluster space rather than a physical configuration space, the conventional exponential sign problem is absent within the convergence regime. For general polymer models, we establish an FPRAS with runtime

\tilde{\mathcal{O}}(N^4\varepsilon^{-3})

. For quantum partition functions at temperatures

β\leqβ_{\mathrm{sampling}}\equiv\mathcal{O}(1)

, this improves to

\tilde{\mathcal{O}}(N^{3+1/D}\varepsilon^{-3})

, where

D

is the lattice dimension. The framework directly applies to long-range quantum systems with interactions

\propto1/r^α

, including

2

-local models with

α>2D