Discovering Algorithms with Computational Language Processing
This work addresses the challenge of algorithm design for researchers and practitioners in combinatorial optimization and quantum computing, representing a novel method rather than an incremental improvement.
The authors tackled the problem of automating algorithm discovery by representing algorithms as sequences of computational tokens and using an ensemble Monte Carlo tree search guided by reinforcement learning to chain them. Their framework rediscovered, improved, and generated new algorithms that substantially outperform existing methods for strongly NP-hard combinatorial optimization problems and foundational quantum computing approaches.
Algorithms are the engine for reproducible problem-solving. We present a framework automating algorithm discovery by conceptualizing them as sequences of operations, represented as tokens. These computational tokens are chained using a grammar, enabling the formation of increasingly sophisticated procedures. Our ensemble Monte Carlo tree search (MCTS) guided by reinforcement learning (RL) explores token chaining and drives the creation of new tokens. This methodology rediscovers, improves, and generates new algorithms that substantially outperform existing methods for strongly NP-hard combinatorial optimization problems and foundational quantum computing approaches such as Grover's and Quantum Approximate Optimization Algorithm. Operating at the computational rather than code-generation level, our framework produces algorithms that can be tailored specifically to problem instances, not merely classes.