Variational approach to imaginary time propagation towards the solution of hard combinatorial problems

This thesis presents and evaluates a variational approach designed to address 3-SAT problems at critical clause density, examining how parameter-space trajectories generated by deterministic time-dependent variational principle (TDVP) dynamics, seeded by an initial imaginary-time evolution, can steer the ansatz toward low-energy configurations and, ultimately, the ground states of the encoded instances. Each Boolean formula is mapped to a spin Hamiltonian, whose low-energy spectrum encodes the satisfying assignments. Within this framework, the algorithm employs an ansatz constructed as a superposition of uncorrelated Bloch-disk product states. The initialization is carried out via a short imaginary-time evolution, starting from a transverse-field-like state with equal overlap with all classical configurations. During this preliminary phase, no parameter optimization is performed; instead, the procedure systematically generates and expands a set of product states, steering their linear combination toward energetically favorable regions. After a predefined number of iterations, the process transitions to a fully variational phase, during which both the amplitudes and the local spin orientations are refined by applying the TDVP in imaginary time. To address computational costs and memory usage, several mitigation strategies have been implemented. During the expansion phase, the parameter space is meticulously compressed, retaining only the most relevant contributions. In the subsequent phase, variational updates are carried out within an effective subspace of the manifold, selected at each step from the full set of directions. Numerical stability is further enhanced through the regularization of the local metric tensor and the resolution of the corresponding linear system via MINRES-QLP, thereby circumventing the explicit inversion of large, dense, and ill-conditioned matrices. Within this context, the combined imaginary-time evolution and TDVP scheme systematically drives the ansatz toward energetically favorable configurations, even for challenging 3-SAT instances, as long as the problem size remains within a relatively moderate range. At the same time, the analysis reveals structural bottlenecks whose impact becomes increasingly severe as the spin count grows. The rapid escalation of both memory consumption and wall-clock time is directly tied to the dimension of the manifold generated by the imaginary-time expansion, which grows drastically with both system size and expansion depth. This severely limits the scale of the instances that can be feasibly addressed. Overall, this work shows that imaginary-time dynamics and variational geometry can be repurposed as a deterministic heuristic for an NP-complete problem such as 3-SAT, while also clarifying where and why intrinsic limitations on scalability arise.