A Pipeline for Solving Edge-Matching Puzzles and Their Implications for Protein Folding

Progress in quantum computation offers new opportunities for addressing longstanding combinatorial challenges. One such challenge is the Eternity II edge-matching puzzle, consisting of 256 tiles, which has resisted solution despite extensive community effort. The computational complexity of this NP-complete problem exceeds the capacity of current quantum annealing processors but lies within reach of hybrid quantum-classical solvers. Testing a quadratic unconstrained binary optimization (QUBO) model of a puzzle on a D-Wave hybrid solver demonstrates a complete solution only for puzzle instances up to 64 tiles. Simulated quantum annealing fails on this benchmark, whereas an original classical heuristic, “nucleation with deduction”, succeeds. To approach the full Eternity II puzzle, I developed a MATLAB package that integrates multiple quantum and classical approaches, including neural-network transformers and gradient-based refinement. A multistage computation pipeline is demonstrated successfully on a puzzle comparable in complexity to Eternity II and with a known solution, based on multiple hybrid optimization steps with both “hard” and “soft” constraint formulations, identification of persistent substructures, and a final classical refinement stage. The resulting optimization problem involves ∼100,000 logical variables and requires partial initialization. Intriguingly, solving this puzzle mirrors the “end game” of protein folding, a process that nature completes in mere fractions of a second, seemingly defying expectations set by the Levinthal paradox. The prospect of predicting protein structure by quantum annealing is reviewed in light of these results.