Polynomial-Time Computability of the Lattice Theta Function

A computational investigation into whether the lattice theta function can be evaluated in polynomial time for general complex symmetric matrices of large dimension.

Θ(A, d) = Σx ∈ Zn exp(2πi (x+d)T A (x+d))
Quantum Physics Computational Complexity Open Problem

Key Findings

Summary of experimental results across dimensions n = 1 to 15

exp(1.61n)
Exponential Scaling Rate
Term count growth with dimension n
6x105x
General vs Diagonal Gap at n=7
39.15s general vs 6.4e-5s diagonal
0.230
CVP Distance Recovered
Matching true value by t = 5

Experimental Results

Interactive charts from computational experiments

Computation Time vs Dimension
Number of Terms vs Dimension
Truncation Radius vs Eigenvalue
Computation Time vs Eigenvalue
Tractability Frontier: Diagonal (Polynomial) vs General (Exponential)
Theta Magnitude vs Scaling Parameter t
CVP Distance Estimation via Theta
Condition Number Before/After LLL
LLL Improvement Ratio by Dimension
Primal vs Dual (Poisson) Computation Time

Detailed Data

Numerical results from all experiments

Scaling Experiment (Direct Summation)
nTermsTime (s)Time LLL (s)
170.00010.0001
2250.00010.0002
31250.00030.0004
46250.00240.0034
53,1250.38690.1014
615,6250.03400.9601
778,1253.83393.2964
CVP Distance from Theta Function
t|Theta|Est. min norm2
0.51.085-0.026
1.03.23e-10.180
2.05.91e-20.225
5.07.28e-40.230
10.05.30e-70.230
20.02.80e-130.230
50.04.16e-320.230
100.01.73e-630.230

True CVP distance: 0.230 (brute-force computed)

Main Conclusions

Evidence regarding the open problem of polynomial-time computability

  • Exponential Scaling Confirmed The summation domain grows as exp(1.61n) for typical random matrices, spanning five orders of magnitude from n=1 to n=7. This is consistent with the conjecture that no polynomial-time algorithm exists for general A.
  • LLL Reduction Is Insufficient Lattice reduction provides at most polynomial improvement. The improvement ratio drops below 1.0 for n >= 4, indicating that LLL cannot overcome the exponential barrier.
  • Poisson Duality Is Complementary Primal and dual sums have inverse convergence rates. In our experiments the primal consistently outperformed the dual, and neither achieves polynomial time across all parameter regimes.
  • Sharp Tractability Frontier Diagonal matrices admit O(n * R) polynomial computation, while general dense matrices require O((2R+1)^n) exponential effort. The gap exceeds 600,000x by dimension n=7.
  • CVP Hardness Connection The theta function encodes the Closest Vector Problem (NP-hard) through the scaling limit. Estimates converge to the true CVP distance 0.230 by t = 5, confirming the hardness encoding.
  • Quantum Algorithms May Help The quantum-physics origin of this problem, combined with Regev's work on lattice problems, suggests that quantum polynomial-time algorithms may exist even if classical ones cannot.