Quantum-inspired Algorithm for the Collatz Conjecture

Abstract

We develop and benchmark a quantum-inspired algorithmic framework that maps the classical 3n + 1 Collatz function onto a quantum circuit intended for execution on a qubit array. Starting from a uniform superposition of all 2^L binary seeds, the circuit deterministically applies the transformation n → 3n + 1 followed by pointer-mediated division by 2^K sequence that removes every trailing power of two. The algorithm uses Clifford+Toffoli primitives and is tailored for efficient classical emulation via matrix product state techniques that each elementary layer is expressed as a uniform matrix product operator whose bond dimension is bounded by four, while a greedy SVD compression routine controls entanglement growth. Our results illustrate the potential of quantum parallelism to explore challenging problems in discrete dynamics, while remaining compatible with classical device constraints.

Date of Award	2025
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology
Supervisor	Hoi Chun PO (Supervisor)