Light as a Solution to Puzzles AboutLight

James W. Robinson

Shahar Seifer

ABSTRACT 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.

Yuma Tamura, Akira Suzuki, Takaaki Mizuki

The 15-puzzle is a puzzle game played with 15 square tiles numbered from 1 to 15 on a 4 × 4 board. It has been popular for generations because of its simplicity and challenge. The (w × h)-puzzle is a generalization of the 15-puzzle, which is played with wh − 1 square tiles numbered from 1 to wh − 1 on a w × h board. Solving the (w × h)-puzzle is NP-hard, and hence it is valuable to know its solution. In this paper, we apply the concept of zero-knowledge proof to the (w × h)-puzzle. We propose a physical zero-knowledge proof protocol, in which a prover who knows a solution to the (w × h)-puzzle can convince a verifier that the prover knows the solution without revealing any information about it. We also design physical zero-knowledge proof protocols of two token swapping problems closely related to the (w × h)-puzzle.

E. Lommel

J. J. Thomson

Tobias J. Haist

I present a method for optical computing based on white-light interferometry. The problem to be solved is coded by optical path lengths and the superposition of all possible paths that a photon can travel is used for computing the solution. The solution itself is chosen by interference with the reference light. Several gedankenexperiments demonstrate how this method can be used for solving computational hard problems. Especially, I will introduce the basic principle with two maze-type puzzles and then concentrate on how the method can be employed for performing ultra-fast (sub-ps) digital-optical arithmetic with arbitrary precision.